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

Question

[rmg]

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

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

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

Спасибо заранее за любую помощь или возможные подсказки.

Answer 1

[gimntut]

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

Comments

[rmg]

Этот алгоритм уже опробован на личном опыте? Или это предположение?) Потому что преобразования Хафа тоже хорошо должны были сработать, а получилось, что нет.

[gimntut]

rmg: Это предложение. Обратите внимание, что в предложенном варианте не указывается, как находить прямую. Можете использовать для этого тот же алгоритм Хафа. Хотя, мне кажется, алгоритм Хафа не справится, слева сверху я вижу 2 линии, а справа слева даже 3.

Answer 2

[Mrrl]

Если времени не очень жалко, можно попробовать так:
Перебираем углы от 0 до 180 с шагом, например, 1 градус.
Проектируем точки на прямую, идущую под этим углом к горизонтали.
Ищем на проекции достаточно короткий отрезок, в который попало достаточно много точек.
Ищем методом наименьших квадратов прямую, наилучшим образом приближающую точки, попавшие в этот отрезок.

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

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

Comments

[rmg]

Как оказалось, я не правильно реализовал преобразования Хафа. Две неточности в моей реализации - углы от 0 до 360 и точность, с которой точка должна удовлетворять прямой должен быть сопоставим с шумом. То есть, у меня точность была 0.1 (у меня непрерывное пространство). А разброс был 1-3. Поэтому очень мало точек попадали на каждую прямую.
Теперь другая задача - выделить локальные максимумы.