@rmg

Как кластеризовать точки по принадлежности к разным (неизвестным) прямым?

Имеется набор точек на декартовой плоскости, которые являются координатами сторон некоторой фигуры (какой именно - неизвестно). Среди точек есть выбросы и точкам присущи случайные отклонения.
9daa96c045f34fb9af509c3de5ac6246.png
На рисунке видно, что фигура состоит из четырех прямых.
Задача: кластеризовать точки по принадлежности к наиболее подходящей прямой, и по возможности - получить параметры этих прямых.

ВАЖНО! Данных слишком мало (например - 100 точек), поэтому преобразование Хафа плохо работает. Нужен какой-то другой метод.

Спасибо заранее за любую помощь или возможные подсказки.
  • Вопрос задан
  • 2328 просмотров
Пригласить эксперта
Ответы на вопрос 2
@gimntut
Приблизительно так:
1. Берем группу близко лежащих точек.
2. Строим по группе точек прямую.
3. Выкидываем из группы точку (точки) которая слишком сильно выбивается из корреляции.
4. Добавляем к группе ближайшую не проверенную точку.
5. Повторяем с п.2 до тех пор пока точки не закончатся.
Так определяется направление одной из линий.
6. Все точки которые соответствуют найденной линии исключаются из общей массы точек и процесс повторяется с п.1
Таким образом будут найдены все линии.
7. Из массива линий нужно исключить линии состоящие из малого числа точек. Скорее всего это линии из точек выброса. А точки входящие в эти линии нужно исключить из общего массива точек.
8. После того, как все линии найдены, нужно найти входящие в них точки из общего массива точек (с учёт предыдущего пункта), т.к. точки могут входить в несколько линий, а из-за п.6 последняя линия не досчитается многих своих точек.
Замечания по п.3:
* Если в результате добавления одной точки выпадают 3 и более точек, то выкидывать нужно добавленную точку, а не те которые перестали подходить для линии.
* Если после добавления новой точки, ни кто из корреляции не выпадает, то и выкидывать ни кого не нужно.
Ответ написан
Mrrl
@Mrrl
Заводчик кардиганов
Если времени не очень жалко, можно попробовать так:
Перебираем углы от 0 до 180 с шагом, например, 1 градус.
Проектируем точки на прямую, идущую под этим углом к горизонтали.
Ищем на проекции достаточно короткий отрезок, в который попало достаточно много точек.
Ищем методом наименьших квадратов прямую, наилучшим образом приближающую точки, попавшие в этот отрезок.

Считаем среднеквадратическое расстояние от этих точек до найденной прямой (сигма)
Ищем все точки из исходного множества, расстояние от которых до этой прямой меньше 3*сигма.
Строим для них наилучшее приближение прямой.
Можно повторить последние три действия несколько раз.

Первая часть алгоритма не опробована. В сущности, это то же преобразование Хафа, но разделённое на этапы. Вторую применял неоднократно.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
28 мая 2020, в 01:17
1000 руб./в час
27 мая 2020, в 23:51
3000 руб./за проект