Обнаружение оси вращения от pointcloud
Я пытаюсь автоматически обнаружить ось вращения на 3-м pointcloud.
Другими словами, если я взял маленький 3-й pointcloud, выбрал единственную ось вращения, и сделайте несколько копий точек в различных углах вращения, затем я получаю больший pointcloud.
Вход к моему алгоритму является большим pointcloud, и желаемый вывод является единственной осью симметрии. И в конечном счете я собираюсь вычислить корреспонденции между точками, которые являются вращениями друг друга.
Размер большего pointcloud находится на порядке точек 100K, и количество вращательных сделанных копий неизвестно.
Углы вращения в моем случае имеют постоянные дельты, но не обязательно охватывают 360 градусов. Например, я мог бы иметь 0, 20, 40, 60. Или я мог бы иметь 0, 90, 180, 270. Но я не буду иметь 0, 13, 78, 212 (или если я делаю, я не хочу обнаружить его).
Это походит на проблему машинного зрения, но я испытываю затруднения при выяснении, как точно найти ось. Вход обычно будет очень чистым, близко к точности плавающей.
У меня нет исходного меньшего pointcloud, который вращался/копировался для создания большего pointcloud. Я действительно знаю, что данные являются синтетическим продуктом с очень небольшим количеством шума (это обычно - вывод другой программы).
Мы не можем с готовностью вычислить возможные числа точек в меньшем облаке, потому что прямо вдоль оси точки не дублированы, к сожалению. Если бы мы знали, какие точки приехали ось затем, то мы могли придумать возможные факторы, но затем мы уже решим проблему.
--
Спасибо все для Ваших предложений. Похоже, что мой заключительный алгоритм собирается попытаться придумать клики соответствия точкам с помощью k-nn метрики. Каждая клика даст ось. Я могу затем использовать RANSAC для установки оси к результатам всех клик.
9 ответов
Что ж, следующий подход может быть полезным, но он зависит от специфики ваших данных. Он основан на предположении, что промежуток между соседними позициями достаточно велик (20 градусов, вероятно, нормально), а небольшое облако точек приближается к поверхности (последнее можно преодолеть). Я предлагаю использовать локальное сопоставление признаков (популярный метод компьютерного зрения).
Во-первых, для каждой точки большого облака вы должны вычислить локальные дескрипторы (например, SIFT или SURF для изображений). Самым популярным для облаков точек является изображение вращения :
Johnson, A., & Hebert, M. (1999). Использование вращающихся изображений для эффективного распознавания объектов в загроможденных трехмерных сценах. Транзакции IEEE по анализу шаблонов и машинному интеллекту, 21 (5), 433–449. Citeseer. Получено с http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.8816&rep=rep1&type=pdf .
Здесь используется расширенная модификация:
Endres, F., Plagemann, C., Stachniss, C., & Burgard, W. (2009). Неконтролируемое обнаружение классов объектов из данных диапазона с использованием скрытого распределения Дирихле. В робототехнике: наука и системы. Сиэтл, США.
Если это будет сложно с вычислительной точки зрения, спросите меня, как уменьшить размерность, не теряя при этом много различающей способности. Я сделал это однажды.
Затем вы должны сопоставить дескрипторы, то есть найти ближайших соседей для каждого из них в их многомерном пространстве.Если маленькое облако было повернуто 3 раза, должно быть 3 хороших ближайших соседа. Однако из-за самопересечения облаков спички, вероятно, будут содержать шум. Вам все еще нужно найти ось, которая подходит для большого количества совпадений (хотя и не для всех). Здесь вы можете использовать надежную подгонку, такую как RANSAC (вы должны выполнить некоторую математику, чтобы определить вероятность положения оси относительно найденных совпадений). Обратите внимание, что он отличается от методов, предложенных другими. Вам следует разместить только одну линию вместо семейства плоскостей на основе дескрипторов, а не исходных точек (RANSAC, вероятно, не сможет соответствовать плоскости, имеющей 4-5 правильных точек и 100 000 выбросов).
Также обратите внимание:
Если у вас есть небольшой скан, который не аппроксимирует поверхность, вы должны придумать другой инвариантный дескриптор вращения, а не вращать изображения.
Чтобы вычислить нормали и выполнить поиск, вы можете проверить эту библиотеку: http://graphics.cs.msu.ru/en/science/research/3dpoint/lidark (основной релиз скоро будет).
Некоторые моменты :)
- Если у нас есть 1 начальная точка, которая никогда не вращалась, тогда существует бесконечное количество осей.
- Если у нас есть 1 начальная точка, повернутая 1 раз, то также существует бесконечное количество осей.
- Если у нас есть 1 начальная точка и мы повернем ее 2 раза, то мы сможем найти ось, потому что 3 точки однозначно определяют плоскость. Перпендикуляр, к которому через точку, равноудаленную от каждой из трех точек (1 начальная + 2 повернутых), проходит ось.
- Обратите внимание, что вращение на 360 не имеет смысла.
- Выберите любую точку (P) из облака.
- Проследите геометрическое место (L) точки P (поскольку P вращается вокруг некоторой оси, L должна быть окружностью)
- Перпендикулярно плоскости круга (L), проходящего через его центр, является ось вращение облака.
Я имею в виду, что ось вращения твердого тела такая же, как ось вращения любой отдельной частицы тела. Нам не нужно заботиться обо всех остальных моментах.
1) Если вы найдете центроид C большего облака точек, ISTM исходная ось вращения должна будет пройти через эту точку.
Неважно: я не видел требования, чтобы вращения не охватывали полный круг. Для вашего примера 20,40,60 центроид не будет на оси вращения.
Может быть, поможет следующая ссылка?
«Реконструкция поверхностей вращения с частичной дискретизацией» http://portal.acm.org/citation.cfm?id=980064
Выберите любую точку и найдите две другие точки, равноудаленные от нее. Это должно занять O (n ^ 2) в худшем случае, но эвристика может значительно уменьшить это. Эти три точки однозначно определяют круг. Если есть четвертая точка на одинаковом расстоянии от первой или третьей точки, это значительно повысит вашу уверенность в круге.
Центр круга - это точка на оси, а вектор нормали к окружности - это вектор направления оси.
Зная ось, вы можете определить угол между вращениями и проверить свое предположение по некоторым другим точкам. Если это не так, выберите другую точку и начните заново.
Редактировать: Кстати, очевидно, что это недетерминировано, но если ваши точечные данные настолько чисты, как вы говорите, и вы используете хорошую эвристику, они должны быть довольно точными.
Посмотрите на методы, используемые в стереозрении для вычисления гомографии между двумя изображениями - ваша проблема с наборами облаков точек кажется аналогичной сопоставлению точек на нескольких изображениях одного и того же объекта/сцены. Похоже, что вы можете применить алгоритм RANSAC для вычисления преобразования между наборами облаков точек.
Безумная идея ...
Если одну и ту же точку повернуть вокруг одной оси несколько раз, все точки будут лежать в одной плоскости. В зависимости от вашего набора данных можно было бы обнаружить этот самолет с помощью метода ransac.
Ось вращения будет перпендикулярна этой плоскости, и после определения ее ориентации будет относительно легко определить положение оси.
Вы должны учитывать 2 вещи:
- Угловой размах облака точек.
- Угол поворота.
Теперь, если (поворот> промежуток) решение проще, потому что вам нужно искать подшаблон и, основываясь на его появлении, пытаться сопоставить с более крупным шаблоном.
в случае (вращение Если вы не знаете, в какую категорию вы попадаете, можно с уверенностью предположить, что это второе. Как упоминалось ранее, RANSAC - лучший способ сопоставления с образцом, потому что он занимает меньше времени и дает достойные результаты.
Единственная проблема, с которой вы остались, - это оценка угла пролета мини-облака точек во время инициализация. эту оценку сделать трудно. Поэтому, если у вас достаточно вычислительной мощности / времени, я бы предложил итерацию с шагом в 1 градус. начиная со скромных 5 градусов и далее до 45 градусов. По мере того, как результаты начинают сходиться, увеличивайте угловую точность.
Далее предполагается, что имеется 3 или более копий. Рассмотрим выпуклую оболочку большого облака точек. Найдите две его параллельные грани. Ось вращения будет перпендикулярна им. Если вы найдете более одной пары, просто проверьте каждую ориентацию.
Очевидно, это не работает, если самые крайние точки по оси находятся прямо на оси, однако в общем случае это очень редко.
Поскольку исходное облако точек мало, простейшим решением может быть RANSAC:
- Выбрать три точки наугад
- Вычислить ось вращения для эти точки (линия, перпендикулярная окружности и проходящая через центр)
- Согласуются ли другие точки?
- Если нет, повторяйте до тех пор, пока не будет найдена правильная ось
Вероятность правильной оценки составляет 1 / ((n- 1) (n-2)), где n - количество точек в исходном облаке. Поскольку каждый тест можно выполнить очень быстро, это может быть полезным подходом.