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

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

我编写了一个函数，它在点列表中查找正方形的点，如果存在，则返回四个点，如果不存在，则返回None。对于列表中的任意两点，它首先计算它们的差值并将此向量旋转90度。然后检查点1+此向量和点2+此向量或点1-此向量和点2-此向量是否在列表中，如果是这样，则返回它们。diffRotated.any()只是为了确保点1和点2不相同。你知道吗

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²logn）个操作，第二种方法花费大约O（N²t²），其中t是允许的像素公差。你知道吗