Обнаружение множества плоскостей из облачного облака

Question

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

Я попытаюсь использовать hough tranform для определения линий, тогда я попытаюсь посмотреть, есть ли три пересекающиеся линии, и они также пересекают две плоскости.

Answer 1

Если данные о точном облаке поступают с датчика глубины, то у вас есть относительно плотная выборка ваших стен. Одна вещь, которую я обнаружил, что хорошо работает с датчиками глубины (например, Kinect или DepthSense), является надежной версией процедуры RANSAC, предложенной @MartinBeckett. Вместо того, чтобы выбирать 3 пункта в случайном порядке, выберите одну точку в случайном порядке и получите соседние точки в облаке. Это можно сделать двумя способами:

1. Правильный способ: использовать структуру данных запроса ближайшего ближайшего соседа, такую ​​как KD-дерево, чтобы получить все точки на некотором небольшом расстоянии от точки запроса.
2. Неаккуратный, но более быстрый способ: используйте район сетки пикселей вашего случайно выбранного пикселя. Это может включать в себя точки, которые далеки от этого в 3D, потому что они находятся на другой плоскости/объекте, но это нормально, поскольку этот пиксель не получит большой поддержки от данных.

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

Оттуда алгоритм RANSAC выполняется как обычно: проверьте, сколько других точек в данных близко к этой плоскости, и найдите плоскость (ы) с максимальной поддержкой. Мне было лучше найти самую большую опорную плоскость, удалить поддерживающие 3D-точки и снова запустить алгоритм, чтобы найти другие «более мелкие» плоскости. Таким образом, вы сможете получить все стены в своей комнате.

РЕДАКТИРОВАТЬ:

Для пояснения выше: поддержка гипотетической плоскости является множество всех 3D точек, расстояние от этой плоскости не более чем некоторый порог (например, 10 см, должен зависеть от глубины модель измерения погрешности датчика). После каждого запуска алгоритма RANSAC выбрана плоскость с наибольшей поддержкой. Все точки, поддерживающие эту плоскость можно использовать для более точного уравнения плоскости (это является более надежной, чем просто с использованием соседних точек) путем выполнения РСА/линейной регрессии на множестве поддержки.

Для продолжения и поиска других плоскостей, поддержка предыдущей итерации должна быть удалена из набора 3D-точек, так что оставшиеся точки лежат на других плоскостях. Это может повторяться до тех пор, пока имеется достаточное количество точек, и лучшая ошибка при установке плоскости не слишком велика. В вашем случае (ищите уголок) вам нужно как минимум 3 перпендикулярных плоскости. Если вы найдете две плоскости с большой опорой, которые примерно параллельны, то это могут быть пол и какой-то счетчик, или две параллельные стены. Либо в комнате нет видимого угла, либо вам нужно искать перпендикулярную плоскость с меньшей поддержкой.

Answer 2

Нормальный подход был бы ransac

1. Pick 3 очка в случайном порядке.
2. Сделайте самолет.
3. Проверьте, находятся ли друг другу точки на плоскости.
4. Если достаточно находятся на самолете - пересчитывать лучший самолет из всех этих точек и удалить их из набора
5. Если бы не попробовать еще 3 очка
6. Stop, когда у вас есть достаточное количество самолетов, или слишком мало точек осталось.

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

1. выбрать небольшой вертикальный диапазон
2. Получить все точки в этом диапазоне
3. Try и подходит 2Д
4. Повторите эти действия для других Z диапазонов
5. Если вы получаете параллельный набор строк в каждом Z, то они, вероятно, имеют плоскость - пересчитайте оптимальную плоскость для очков.

Answer 3

Прежде всего я хотел бы отметить,

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

1. Равномерно образец пространства. Убедитесь, что между точками существует как минимум расстояние $ d $ (например, вы даже можете сделать это CloudCompare с подвыборкой «пробел»)
2. Вычислить нормальные точки облаков в этих точках.
3. Случайно выберите 3 пункта из этого понижающего облака.
4. Каждая ориентированная точка (точка + плоскость) определяет гипотетическую плоскость. Поэтому каждый 3-х точечный набор определяет 3 плоскости. Эти плоскости, если они не параллельны и не пересекаются по прямой, всегда пересекаются в одной точке.
5. Создайте пространство для голосования, чтобы описать угол: пересечение трех плоскостей (точки) может быть допустимой параметризацией. Таким образом, наше пространство параметров имеет 3 свободных параметра.
6. За каждые 3 очка проголосовали в пространстве аккумулятора в угловой точке.
7. Перейдите к (2) и повторите до тех пор, пока все выбранные точки не будут исчерпаны или не пройдены достаточные итерации. Таким образом, мы будем голосовать за все возможные угловые места.
8. Возьмите локальные максимумы пространства аккумулятора. В зависимости от голосов мы будем выбирать углы от пересечения крупнейших самолетов (так как они получат больше голосов) до пересечения небольших самолетов. Самые большие 4, вероятно, являются уголками комнаты. Если нет, то можно было бы рассмотреть и другие локальные максимумы.

Обратите внимание: пространство для голосования является квантованным пространством 3D, а угловое местоположение будет приблизительной оценкой фактического. При желании можно было бы сохранить пересечение плоскостей в этом самом месте и усовершенствовать их (с итеративной оптимизацией, подобной ICP или т. Д.), Чтобы получить очень тонкое угловое положение.

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

Пожалуйста, смотрите здесь, где я потушить список плоских облегающие связанных с этим вопросов на StackOverflow: 3D Plane fitting algorithms