Алгоритм наилучшего соответствия прямоугольника

Question

Я ищу алгоритм для лучшего соответствия произвольного прямоугольника неупорядоченному набору точек. В частности, я ищу прямоугольник, в котором сумма расстояний точек до любого из краев прямоугольника минимизирована. Я нашел множество наилучших алгоритмов подгонки линий, окружностей и эллипсов, но ни одного для прямоугольника. В идеале, я хотел бы что-то на C, C++ или Java, но не настолько суетливо в языке.

Входные данные обычно состоят из большинства точек, лежащих на или близко к прямоугольнику, с несколькими выбросами. Распределение данных будет неравномерным и вряд ли охватит все четыре угла.

Answer 1

Вот несколько идей, которые могут вам помочь.

Мы можем оценить, находится ли точка на ребре или на углу следующим образом:

1. Соберите точку и ближайших соседей
2. Рассчитать центр тяжести точек
3. Рассчитайте ковариационную матрицу точек следующим образом:
   1. Начать с Covariance = ((0, 0), (0, 0))
   2. Для каждой точки рассчитайте d = point - centroid
   3. Covariance += outer_product(d, d)
4. Вычислить собственные значения ковариации. (например, с SVD)
5. Классифицировать точку:
   • если одно собственное значение велико, а другое очень мало, мы, вероятно, на грани
   • в противном случае мы должны быть на углу

Извлеките все угловые точки и сделайте сегментацию. Выберите четыре сегмента с большинством записей. Центроид этих сегментов являются кандидатами на углы прямоугольника.

Рассчитайте нормализованные векторы направления двух противоположных сторон и рассчитайте их среднее значение. Рассчитайте среднее значение двух других противоположных сторон. Это векторы направления параллелограмма. Если вы хотите прямоугольник, вычислите перпендикулярный вектор для одного из этих направлений и вычислите среднее значение с другим вектором направления. Тогда направления прямоугольника - это средний вектор и перпендикулярный вектор.

Чтобы вычислить углы, вы можете проецировать кандидатов на их направления и перемещать их так, чтобы они образовывали углы прямоугольника.

Answer 2

Вот общая идея. Сделать сетку с мелкими ячейками; рассчитать линию наилучшего соответствия для каждой не слишком пустой ячейки (вычисление является немедленным¹, поиск не выполняется). Присоединяйтесь к соседним ячейкам, следя за тем, чтобы стандартное отклонение улучшалось / не ухудшалось значительно Таким образом, мы обнаруживаем четыре стороны и четыре угла и делим наши точки на четыре группы, каждая из которых принадлежит одной из четырех сторон.

Затем мы отбрасываем угловые ячейки, помещаем настоящий прямоугольник вместо четырех приближенных линий и делаем небольшое восхождение на гору (или что-то еще). Расчет линии наилучшего соответствия может быть увеличен для этого случая, так как две линии параллельны, и мы уже разделили наши точки на четыре группы (для данного прямоугольника мы знаем дельта-y между двумя противоположными сторонами (на одну сторону), поэтому мы просто добавим эту дельта-у к yс нижней группы точек и сделать расчет).

Первоначальная прямоугольная сетка может быть заменена рабочей полосой (скажем, вертикальной). Тогда, по крайней мере, половина полос будет иметь две четко выраженные группировки точек (найдите их, разделив каждую полосу горизонтальными линиями деления на ячейки).

---

¹ Для строки Y = a*X+bминимизируйте сумму квадратов перпендикулярных расстояний точек данных {x_i, y_i} до этой линии. Это напрямую разрешимо для a а также b, Для более вертикальных линий, переверните X и Y.

PS Я интерпретирую проблему как минимизацию суммы квадратов перпендикулярных расстояний каждой точки до ее ближайшей стороны прямоугольника, а не до всех сторон прямоугольника.

Answer 3

Идея линии наилучшего соответствия состоит в том, чтобы вычислить вертикальные расстояния между вашими точками и линией y=ax+b. Затем вы можете использовать исчисление, чтобы найти значения a и b, которые минимизируют сумму квадратов расстояний. Квадрат причины выбран по абсолютному значению, потому что первый дифференцируется в 0.

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

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

Answer 4

Я не совсем уверен, но вы можете поиграть в первые 2 (3?) Измерения над PCA из ваших очков. в большинстве случаев он будет работать достаточно быстро.