Трехмерный вариант метода Хафа в реконструкции внешней среды и навигации

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

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

1. Лапшов В. С., Носков В. П. и др. Бой в городе. Боевые и обеспечивающие роботы в условиях урбанизированной территории // Известия ЮФУ. Технические науки. 2011. No 3. С. 142—146.

2. Носков А. В., Носков В. П. Распознавание ориентиров в дальнометрических изображениях // Мобильные роботы и мехатронные системы. 2001. С. 179—192.

3. Носков В. П., Носков А. В. Навигация мобильных роботов по дальнометрическим изображениям // Мехатроника, автоматизация, управление. 2005. No 12. С. 16—21.

4. Носков В. П., Рубцов И. В. Опыт решения задачи автономного управления движением мобильных роботов // Мехатроника, автоматизация, управление. 2005. No 12. С. 21—24.

5. Носков В. П., Рубцов И. В., Романов А. Ю. Формирование объединенной модели внешней среды на основе информации видеокамеры и дальномера // Мехатроника, автоматизация, управление. 2007. No 8. С. 2—5.

6. Загоруйко С. Н., Казьмин В. Н., Носков В. П. Навигация БПЛА и 3D-реконструкция внешней среды по данным бортовой СТЗ // Мехатроника, автоматизация, управление. 2014. No 8. С. 62—68.

7. Segal A., Haehnel A. S. D., Thrun S. Generalized ICP // Proc. of Robotics: Science and Systems (RSS). 2009.

8. Mitra N. J. et al. Registration of point cloud data from a geometric optimization perspective // Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing. ACM, 2004. P. 22—31.

9. Казьмин В. Н., Носков В. П. Выделение геометрических и семантических объектов в дальнометрических изображениях для навигации роботов и реконструкции внешней среды // Известия ЮФУ. Технические науки. 2015. No 10 (171). С. 71—83.

10. Павловский В. Е., Павловский В. В. Технологии SLAM для подвижных роботов // Мехатроника, автоматизация, управление. 2016. No 6. С. 384—394.

11. Konouchine A., Gaganov V., Veznevets V. AMLESAC: A new maximum likelihood robust estimator // Proc. Graphicon. 2005. Vol. 5. P. 93—100.

12. Klasing K. et al. Comparison of surface normal estimation methods for range sensing applications // Robotics and Automation, 2009. ICRA’09. IEEE International Conference on. IEEE, 2009. P. 3206—3211.

13. Holz D. et al. Real-time plane segmentation using RGB-D cameras // Robot Soccer World Cup. Springer, Berlin, Heidelberg. 2011. P. 306—317.

14. Comaniciu D., Meer P. Mean shift: A robust approach toward feature space analysis // IEEE Transactions on pattern analysis and machine intelligence. 2002. Vol. 24, N. 5. P. 603—619.

15. Berkmann J., Caelli T. Computation of surface geometry and segmentation using covariance techniques // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1994. Т. 16, No 11. С. 1114—1116.

16. Mitra N. J., Nguyen A., Guibas L. Estimating surface normals in noisy point cloud data // International Journal of Computational Geometry & Applications. 2004. Vol. 14, N. 04n05. P. 261—276.

17. Велижев А., Шаповалов Р., Потапов Д., Третьяк Е., Конушин А. Автоматическая сегментация облаков точек на основе элементов поверхности // Cборник "Труды конференции GraphiCon — 2009". 2009. С. 241—245.

18. Sedlacek D., Zara J. Graph cut based point-cloud segmentation for polygonal reconstruction // International Symposium on Visual Computing. Springer, Berlin, Heidelberg, 2009. P. 218—227.

19. Borrmann D. et al. The 3d hough transform for plane detection in point clouds: A review and a new accumulator design // 3D Research. 2011. Vol. 2, N. 2. P. 3.

20. Гошин Е. В., Лошкарева Г. Е. Информационная технология сегментации разноракурсных изображений с использованием трехмерного преобразования Хафа // Матер. Междунар. конференции и молодежной школы "Информационные технологии и нанотехнологии". 2016. С. 342—349.

21. Hough P. V. C. Method and means for recognizing complex patterns: пат. 3069654 США. 1962.