迭代多维数组并搜索形成正方形的点

Question

我的应用程序的一部分专门用于识别图像中所有对象的角。我发现了很多检测角点的方法，比如Harris角点检测和GoodFeatureToTrack。经过一些测试，GoodFeatureToTrack 已被证明是最好的解决方案，但我坚持使用多维数组的操作。

如何迭代这种类型的数组来检查点列表中是否有四个坐标形成一个正方形？

image = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)
corners = cv2.goodFeaturesToTrack(image, 150, 0.01, 15)
corners = np.int0(corners) 
print("Points")
for corner in corners:
   x, y = corner.ravel()
   cv2.circle(image, (x, y), 5, (0, 0, 255), -1)
print(corners)

这是实际结果

积分

[[[141 265]]

[[148 176]]

[[136 360]]

[[233 358]]

[[192 218]]

[[130 465]]]

Answer 1

我写了一个函数，它在点列表中寻找正方形形成点，如果存在则 returns 四个点，如果不存在则 None。对于列表中的任意两点，它首先计算它们的差异并将该向量旋转 90 度。然后它检查 point1 + 这个向量 and point2 + 这个向量 or point1 - 这个向量 and point2 - 这个向量在列表中，如果是这样的话 returns 它们。 diffRotated.any() 是否只是为了确保 point1 和 point2 不相同。

def findSquare(points):
    for i, point1 in enumerate(points):
        for point2 in points[i+1:]:
            diffRotated = np.array([point2[1]-point1[1], point1[0]-point2[0]])
            if (diffRotated.any() and np.any(points == point1 + diffRotated) and np.any(points == point2 + diffRotated)):
                return np.array([point1, point2, point1 + diffRotated, point2 + diffRotated])
            elif(diffRotated.any() and np.any(points == point1 - diffRotated) and np.any(points == point2 - diffRotated)):
                return np.array([point1, point2, point1 - diffRotated, point2 - diffRotated])
    return None

为了测试，我在您的列表中添加了两个条目，以便它们与您列表中的其他两个点形成一个正方形：

points = np.array([[141, 265],
                   [148, 176],
                   [136, 360],
                   [233, 358],
                   [192, 218],
                   [130, 465],
                   [145, 167],
                   [ 94, 214]])
print(findSquare(points))
# array([[141, 265],
#        [192, 218],
#        [ 94, 214],
#        [145, 167]])
print(findSquare(points[:-1]))
# None

如果你想获得所有个方块你需要修改我的代码并检查每个方块只返回一次。此外，此代码效率不高，可能有一种我没有想到的方式以 numpy 时尚的方式执行此操作。

Answer 2

依次考虑所有点对（其中 N(N-1)/2 个），并将它们视为正方形的对角线。然后你可以预测其他两个顶点的位置。有两个选项：

使用点定位结构，例如kD树，并执行固定半径的近邻搜索（假设您允许在预期位置周围有一个小的公差）；
在图像中执行局部搜索，从预期位置开始螺旋式搜索。

第一种方法的操作成本约为 O(N² Log N)，第二种方法的成本约为 O(N² t²)，其中 t 是以像素为单位的允许容差。

迭代多维数组并搜索形成正方形的点

Iterate multi-dimensional array and search for points that form squares

python

opencv

numpy

computational-geometry