Как поместить более одной строки в точки данных

Я пытаюсь приспособить более одной строки к списку точек в 2D. Мои очки довольно низки (16 или 32).

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

Привязка одной строки к набору точек не является проблемой, если мы знаем все эти точки на линии или вокруг нее.

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

Как бы вы решили эту проблему? Если я рассмотрю все возможности, например, для групп по 5 баллов для всех 32 точек, то он дает 32 выбора 5 = 201376 возможностей. Я думаю, что требуется слишком много времени, чтобы попробовать все возможности и попытаться подстроить строку ко всем 5-ти строкам.

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

Как вы думаете, возможно ли сделать какое-то преобразование Hough на дискретном наборе данных с таким низким количеством записей?

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

Ответ 1

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

Во-вторых, хорошо известно, что найти глобально оптимальное соответствие даже для двух строк произвольному множеству точек является NP-Hard, поскольку оно может быть сведено к k-значению кластеризации, поэтому я не ожидал бы найти эффективный алгоритм для это. Когда я использовал преобразование Хафа, это было для поиска углов на основе интенсивности пикселей, в теории это, вероятно, применимо к этой проблеме, но это просто приближение, и, вероятно, это займет довольно много работы, чтобы выяснить и реализовать.

Я ненавижу предлагать это, но кажется, что вам может пригодиться, рассматривая проблему несколько иначе. Когда я работал в автономной навигации с лазерным дальномером, мы решили эту проблему, дискретизируя пространство в сетку занятости, которая является по умолчанию. Конечно, это просто предполагает, что стены - это еще один объект, который не является особенно возмутительной идеей ИМО. Помимо этого, можете ли вы предположить, что у вас есть карта стен, и вы просто пытаетесь найти препятствия и локализовать (найти позу) робота? Если это так, существует большое количество документов и технических отчетов по этой проблеме.

Ответ 2

Хороший способ найти строки в таких шумных точечных данных, как использовать RANSAC. Стандартное использование RANSAC заключается в том, чтобы выбрать наилучшую гипотезу (= в этом случае), но вы можете легко выбрать наилучшие 2 или 4 строки с учетом ваших данных. Взгляните на пример здесь: http://www.janeriksolem.net/2009/06/ransac-using-python.html Код Python доступен здесь. http://www.scipy.org/Cookbook/RANSAC

Ответ 3

Часть решения может быть (там, где я начну), чтобы исследовать робота. Вопросы, такие как:

Как быстро робот поворачивается/перемещается?
На каком промежутке находится робот, снимающий лазер?
Где был робот и какова была его ориентация, когда точка была найдена?

Ответы на эти вопросы могут помочь вам лучше, чем пытаться найти какой-то алгоритм, который опирается только на точки. Особенно, когда их очень мало.

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

Ответ 4

Для всех триад, установите линию через них и вычислите, насколько линия отклоняется или нет от точек.

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

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

Я предполагаю, что на втором шаге найдут левую и нижнюю строки, а правую - третью.