Два общих подхода для плоской установки - RANSAC и Hough. Вот один сравнение производительности:
https://www.researchgate.net/publication/259519997_Continuous_plane_detection_in_point-cloud_data_based_on_3D_Hough_Transform
Как и со многими проблемами в вычислительной геометрии и обработки изображений, а не считать, что «быстрый» считают, что является оптимальным для применения с точки зрения производительности, усилий в области развития и Стоимость. Поиск максимально быстрого алгоритма может привести вас к путям ужасающих затрат и сложности, тогда как вы можете реализовать цепочку обработки данных относительно более простых алгоритмов, которые выполняются достаточно быстро, чтобы обеспечить пользователю приятное и приятное впечатление.
Короче говоря, я рекомендую начать с посадки самолета Hough. Алгоритмы преобразования Hough относительно просты в записи (как только вы поймете основы), а параметры настройки являются интуитивно понятными.
https://en.wikipedia.org/wiki/Hough_transform
Одна из причин, чтобы написать свой собственный алгоритм является то, что вы будете в лучшем положении, чтобы понять, какие изменения должны быть сделаны один раз (не если) вы обнаружите данные точки облако шумным и менее хорошо себя вести, чем хотелось бы.
Достижение хорошей скорости будет опираться на ряд факторов, в том числе следующие:
- Точка облака предварительной обработки. Ищите способы разбить облако точек на куски, которые можно обрабатывать быстрее.
- Параметризация. Как только данные предварительно обработаны, вы можете определить более узкие границы поиска для вашего алгоритма соответствия плоскости. Например, только попытка плоскости подходит в пределах нескольких градусов по вертикали. Вам также нужно будет выбрать параметры, чтобы найти баланс между скоростью и качеством подгонки.
- Качество 3D-данных. Это большая тема сама по себе, и чем скорее вы сможете лучше рассмотреть проблемы в данных, тем лучше.
- Что означает «реальное время». Даже для приложений 3D-графики, которые связаны с взаимодействием с пользователем, достижение реального времени, основанного исключительно на спецификациях (обновления в N кадрах/секундах), может быть менее важным, чем представление плавного и простого интерфейса.
- Многопоточность и параллелизм.
- 3D-дисплей. Еще одна большая тема.
Предварительная обработка. Вам не нужно устанавливать плоскости произвольного размера на произвольные точечные облака: вместо этого вам нужно поместиться в стены и, возможно, полы и потолки. Для алгоритмов Hough это означает, что вы можете ограничить диапазон, по которому тестируются параметры, и, следовательно, ускорить обработку.
Вместо того, чтобы пытаться найти всю плоскость, подходящую для полного исходного облака точек, найдите способы разбить облако точек на кластеры подкладок, в которые можно выполнить более эффективные тесты на плоскости.
PCL может рассчитать нормальные поверхности поверхности для вас. Если вы можете идентифицировать кластеры нормалей поверхности, обозначенных примерно в одном и том же направлении, а затем попробуйте самолеты для отдельных кластеров, вы сможете значительно ускорить процесс.
Кроме того, для вашего первого прохода вы, вероятно, захотите уменьшить ваши данные и попробовать поместиться на относительно меньшее количество очков. Это аналогично созданию «пирамиды изображения» для 2D-обработки.
Octrees - это приятные, простые средства для разделения пространства для запросов, испытаний на столкновение и т. Д. Октор делит пространство на восемь узлов или «октантов». Это можно представить, как разрезать куб на восемь кубиков меньшего размера. Затем каждый октант далее делится на восемь октантов и т. Д. Если октант (узел) не содержит точек, вам не нужно разделить его дальше.
https://en.wikipedia.org/wiki/Octree
параметризация. В приведенных выше описаниях должно быть ясно, что если вы можете предварительно обработать данные, упростив и/или разрушив исходное облако необработанных точек, тогда вы сможете протестировать гораздо более узко определенные поисковые запросы, которые будут выполняться быстрее.
В этом случае вам, вероятно, не нужна высокая точность в плоскости. Вы можете создать достаточно хорошие припасы, а затем настроить эти приспособления для создания потолков, стен и полов под прямым углом друг к другу.
3D данные качество. Kinect v2 - это устройство времени пролета с некоторыми проблемами точности измерения. Например, если вы берете одно изображение плоской стены, а затем проверяете значения глубины, вы заметите некоторую непланарную тупость в углах изображения. Если вы посмотрите на диапазон (или стандартное отклонение) значений глубины на каждом (x, y) пикселе над несколькими изображениями, то вы также заметите различия в шуме между центральными пикселями и пикселями края.
Как только вы выполняете плоскую посадку, создайте меру качества посадки. Это требует возврата данных для расчета расстояний между точками для точек, используемых для расчета. (Чтобы ускорить это, используйте только каждую N-ю точку или произвольно отбирайте точки.) Когда вы возитесь с параметрами, вы увидите эффекты с точки зрения скорости и качества.
Реальное время против Заметно гладкое. Если вам нужен только пользователь, чтобы перемещать мебель вокруг в режиме реального времени, должно быть хорошо потратить дольше, генерируя исходную плоскость.
Многопоточность/Параллельность Для обработки ввода данных, плоскость фитинга, и пользовательский интерфейс, который вы будете почти наверняка придется трудно думать о многопоточности. Чтобы протестировать алгоритмы, вы работаете над потоком пользовательского интерфейса только для начала, но это ограничение.
Приложение, подобное этому, запрашивает CUDA или OpenCL. Для 3D-дисплея вы все равно будете использовать графическую карту. Хотя вам не нужно сразу переходить на программирование графического процессора, полезно иметь в виду, как можно распараллеливать алгоритмы.
3D дисплей. Планируете ли вы использовать Direct3D или OpenGL для 3D-дисплея и взаимодействия? Внедрение программного обеспечения, позволяющего пользователю «добавлять 3d-модели разных видов мебели в реальном времени», предполагает, что вам придется полагаться на графическую карту.
Если вы можете отобразить облако точек в трехмерном представлении, возможно, вам даже не нужны плоские припадки. Вы даже можете уйти с обнаружением столкновения: если трехмерная модель стула сталкивается с кластером точек (т. Е. Стены), то вы можете просто обнаружить это столкновение, а не пытаться соответствовать плоскостям для определения границ. Октанты и другие методы разделения пространства помогут ускорить испытания на столкновение.
Компания Matterport (http://matterport.com/) разработала нечто очень похожее на то, что вы описываете. Если ничего другого вы не можете дать своему программному обеспечению, попробуйте и подумайте над тем, что может быть улучшено/адаптировано для ваших нужд.
Это определенно дало мне много о чем подумать и попытаться оптимизировать все. До сих пор я пробовал много встроенных методов, обнаруживающих самолеты в комнате, такие как ransac, prosac, lmeds ... Я сейчас искал учебное пособие по спускам, потому что я довольно новичок в работе с 3D-моделями, но все, что я нахожу, - это объяснения для обработки 2D-изображений. Вы знаете, где я могу найти информацию для 3D-изображений? Также спасибо за то, что нашли время для всей информации до сих пор, я бы даже не рассмотрел hough и предварительную обработку без всего этого :) – Kiiiieeeeuuuw
Время обработки и память, необходимые для шкал Hough с количеством переменных, необходимых для описывают геометрическую форму.Для самолета вам нужны четыре переменные, и простой метод грубой силы потребует много времени и памяти, хотя для вашего приложения вы можете ограничить диапазон поиска (например, только плоскости, близкие к вертикали или горизонтали). Кроме того, метод ускорения изучения локализованных подходов сначала описывается в https://en.wikipedia.org/wiki/Hough_transform#3-D_Kernel-based_Hough_transform_for_plane_detection_.283DKHT.29. – Rethunk