Алгоритмы подгонки 3D-плоскости

Двумя распространенными подходами к подгонке плоскостей являются RANSAC и Hough. Вот одно сравнение производительности:

https://www.researchgate.net/publication/259519997_Continuous_plane_detection_in_point-cloud_data_based_on_3D_Hough_Transform

Как и во многих задачах вычислительной геометрии и обработки изображений, вместо того, чтобы думать о том, что является «самым быстрым», рассмотрите то, что является оптимальным для вашего приложения с точки зрения производительности, усилий по разработке и стоимости. Поиск самого быстрого из возможных алгоритмов может привести вас к ужасающим затратам и сложности, в то время как вы можете реализовать цепочку обработки данных относительно более простых алгоритмов, которые работают достаточно быстро, чтобы предоставить пользователю плавный и приятный опыт.

Короче говоря, я рекомендую начать с посадки самолета Hough. Алгоритмы преобразования Хафа относительно легко написать (после того, как вы усвоите основы), а настройка параметров интуитивно понятна.

https://en.wikipedia.org/wiki/Hough_transform

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

Достижение хорошей скорости зависит от ряда факторов, включая следующие:

• Предварительная обработка облака точек. Ищите способы разбить облако точек на фрагменты, которые можно обрабатывать быстрее.
• Параметризация. После предварительной обработки данных вы можете определить более узкие границы поиска для вашего алгоритма подбора плоскости. Например, только попробуйте плоскость вписаться в пределах нескольких градусов по вертикали. Вам также нужно будет выбрать параметры, чтобы найти баланс между скоростью и качеством подгонки.
• Качество 3D данных. Это большая тема сама по себе, и чем раньше вы сможете внимательно изучить проблемы в данных, тем лучше.
• Что означает «в реальном времени». Даже для приложений 3D-графики, требующих взаимодействия с пользователем, достижение режима реального времени на основе строго заданных спецификаций (обновление с частотой N кадров в секунду) может быть менее важным, чем гладкий и простой интерфейс.
• Многопоточность и параллелизм.
• 3D дисплей. Еще одна большая тема.

Предварительная обработка. Вам не нужно подгонять плоскости произвольного размера к произвольным облакам точек: вместо этого вам нужно подгонять стены и, возможно, полы и потолки. Для алгоритмов Хафа это означает, что вы можете ограничить диапазон, в котором проверяются параметры, и, следовательно, ускорить обработку.

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

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

Кроме того, для вашего первого прохода вы, вероятно, захотите понизить выборку ваших данных и попытаться подобрать относительно меньшее количество точек. Это аналогично созданию «пирамиды изображений» для 2D-обработки.

Октдеревья — это удобные и простые средства разделения пространства для запросов, тестов на столкновение и т. д. Октодерево делит пространство на восемь узлов или «октантов». Это можно представить себе как разрезание куба на восемь меньших кубиков. Затем каждый октант делится еще на восемь октантов и так далее. Если октант (узел) не содержит точек, дальше его делить не нужно.

https://en.wikipedia.org/wiki/Octree

Параметризация. В приведенных выше описаниях должно быть ясно, что если вы можете предварительно обработать данные, упростив и/или разбив исходное необработанное облако точек, вы сможете протестировать гораздо более узкие поисковые запросы, чем будет работать быстрее.

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

Качество 3D-данных. Kinect v2 — это времяпролетное устройство, которому свойственны некоторые проблемы с точностью измерений. Например, если вы возьмете одно изображение плоской стены, а затем проверите значения глубины, вы заметите некоторую неплоскую нелепость в углах изображения. Если вы посмотрите на диапазон (или стандартное отклонение) значений глубины для каждого (x, y) пикселя на нескольких изображениях, то вы также заметите различия в зашумленности между центральными пикселями и краевыми пикселями.

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

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

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

Такое приложение требует CUDA или OpenCL. Для 3D-дисплея вы все равно будете использовать видеокарту. Хотя вам не нужно сразу приступать к программированию на GPU, полезно помнить, как можно распараллелить алгоритмы.

Трехмерное отображение. Планировали ли вы использовать Direct3D или OpenGL для трехмерного отображения и взаимодействия? Внедрение программного обеспечения, позволяющего пользователю «добавлять 3D-модели различных видов мебели в режиме реального времени», предполагает, что вам придется полагаться на видеокарту.

Если вы можете отобразить облако точек в 3D-виде, возможно, вам даже не понадобится подгонка плоскости. Вы даже можете обойтись без обнаружения столкновений: если 3D-модель стула натыкается на группу точек (например, на стену), вы можете просто обнаружить это столкновение, а не пытаться подогнать плоскости для определения границ. Октанты и другие методы разделения пространства помогут ускорить тесты на столкновение.

Компания Matterport (http://matterport.com/) разработала нечто очень похожее на то, что вы описываете. Если нет ничего другого, вы можете попробовать их программное обеспечение и подумать, что можно улучшить / адаптировать для ваших нужд.

Я ценю подробные комментарии Rethunk и предоставляю вариант Local Hough Transform. Но сначала позвольте мне отметить, что существует множество сообщений stackoverflow/stackexchange об обнаружении плоскостей или обнаружении пересекающихся плоскостей. Вот некоторые из них:

• Подгонка плоскости к трехмерному облаку точек в C++
• разница между сегментацией плоскости и подгонкой плоскости
• Плоскость вписывается в трехмерное облако точек
• Подгонка плоскости к 3D-облаку точек с помощью RANSAC
• Быстрая подгонка плоскости ко многим точкам
• https://math.stackexchange.com/questions/1657030/fit-plane-to-3d-data-using-least-squares
• Наиболее подходящая плоскость для 3D-данных

Метод, который я предлагаю, подробно объясняется в публикации на 3DV 2015:

Локальное преобразование Хафа для обнаружения 3D-примитивов, Бертрам Дрост, Слободан Илич, IEEE 3D Vision 2015

Идея основана на выборе двух ориентированных пар точек. Ориентации этих точек сравниваются, чтобы решить, лежат ли точки вместе на плоскости или нет. Вклады всех таких пар точек объединяются в локальном пространстве голосования, где плоскость параметризуется в 0-мерном пространстве голосования (ориентируемая точка полностью определяет плоскость). Техника распространяется на различные примитивы.

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

У меня также есть еще один пост по обмену стеками, объясняющий, как потенциально можно разработать аналогичный метод для ортогональных плоскостей.