Я ищу алгоритм, способный решить эту проблему.Группировка точек, которые представляют строки
Проблема:
У меня есть следующие уставки:
Я хочу, чтобы сгруппировать точки, которые представляют собой линию (с некоторой эпсилон) в одной группе. Таким образом, оптимальный выход будет что-то вроде:
Некоторые примечания:
- точка принадлежит к одному и только линии.
- Если точка может принадлежать двум строкам, она должна принадлежать самой сильной.
- Линия считается более сильной, чем другая, когда у нее больше точек принадлежности.
- Алгоритм не должен охватывать все точки, поскольку они могут быть выбросами.
- Пространство содержит много выбросов, которые могут достигать 50% от общей площади.
- Производительность имеет решающее значение, в реальном времени это необходимо.
Растворы я нашел до сих пор:
1) Работа с ней как проблема кластеризации:
Основным недостатком этого метода является то, что есть нет прямой показатель расстояния между точками. Метрика расстояния находится на самом кластере (насколько это линейно). Таким образом, я не могу использовать традиционные методы кластеризации, и я должен (насколько я думал) использовать какой-то, например, кластеризацию генетического алгоритма, где оценка происходит на кластере не между двумя точками. Я также не хочу использовать что-то вроде генетического алгоритма. Пока я нацелен на решение в реальном времени.
2) накопительные пары, а затем сделать кластеризацию:
Хотя это трудно сделать кластеризацию на точках непосредственно, я думал извлечения пар точек, а затем попытаться сгруппировать их с другими. Итак, у меня есть расстояние между двумя парами, которые могут представлять линейность (две пары находятся в реальных 4 точках). Откат этого метода заключается в том, как выбрать эти пары? Если я полагаюсь на Ecledian-Distance между ними, это может быть неточным, потому что две точки могут быть настолько близки друг к другу, но они пока не делают линию с другими.
Я ценю любое решение, предложение, подсказку или примечание. Пожалуйста, вы можете спросить о каких-либо разъяснениях.
P.S. Вы можете использовать любую готовую функцию OpenCV, думая о любом решении.
вы посмотрите на обнаружение линии RANSAC? Но ваши линии довольно близки друг к другу, что усложняет ситуацию. И: Если бы вы спросили меня, я бы сгруппировал несколько строк по-разному. – Micka
@ Micka есть ли обнаружение RANSAC Line ((s))? или это просто подходящая линия? –
о различном решении. не проблема, даже если бы это было не так просто –