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

Question

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

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

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

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

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

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

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

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

Answer 1

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

Answer 2

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

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

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

Answer 3

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

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

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

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

Answer 4

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

1. Как быстро робот поворачивается / двигается?
2. На каком интервале робот стреляет лазером?
3. Где был робот и чтобыла ли его ориентация при обнаружении точки?

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

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