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

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

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

Ответ 1

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

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

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

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

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

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

Ответ 2

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

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

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

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

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

Ответ 3

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

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

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

Ответ 4

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