Итерация многомерного массива и поиск точек, которые образуют квадраты

Question

Часть моего приложения посвящена распознаванию углов всего объекта внутри изображения.Я нашел много способов обнаружения углов, таких как обнаружение углов Харриса и 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

Рассмотрим все пары точек по очереди (N(N-1)/2 из них) и рассмотрим их как диагональ квадрата.Затем вы можете предсказать положение двух других вершин.Есть два варианта:

• использовать структуру местоположения точки, такую ​​как kD-дерево, и выполнять поиск ближнего соседа с фиксированным радиусом (при условии, что вы допускаете небольшой допуск вокруг ожидаемогоlocation);

• выполнить локальный поиск в изображении по спирали от ожидаемого местоположения.

Первый метод будет стоить около O (N²Журнал N) операций и второй O (N² t²), где t - допустимый допуск в пикселях.

Answer 2

Я написал функцию, которая ищет квадратные точки в списке точек и возвращает четыре точки, если они существуют, 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

Если вы хотите получить все квадратов, вам нужно будет изменить мой код и проверить, что каждый квадрат возвращается только один раз.Кроме того, этот код не очень эффективен, возможно, я даже не подумал сделать это просто и стильно.