novtexmechМехатроника, автоматизация, управлениеMekhatronika, Avtomatizatsiya, Upravlenie1684-64272619-1253Commercial Publisher «New Technologies»10.17587/mau.19.552-560novtexmech-503Research ArticleРОБОТЫ, МЕХАТРОНИКА И РОБОТОТЕХНИЧЕСКИЕ СИСТЕМЫROBOT, MECHATRONICS AND ROBOTIC SYSTEMSТрехмерный вариант метода Хафа в реконструкции внешней среды и навигацииA Three-Dimensional Version of the Hough Method in the Reconstruction of the External Environment and NavigationНосковВ. П.NoskovV. P.

канд. техн. наук, зав. сектором, доц.

Ph. D., Special robotics and mechatronics department, NIISM sector head

noskov_mstu@mail.ruКиселевИ. О.KiselevI. O.

аспирант

kiselev201@rambler.ruМГТУ им. Н. Э. БауманаРоссияBauman Moscow State Technical UniversityRussian Federation201810102018198552560Copyright © Commercial Publisher «New Technologies», 20182018Commercial Publisher «New Technologies»Commercial Publisher «New Technologies»https://mech.novtex.ru/jour/about/submissions#copyrightNoticehttps://mech.novtex.ru/jour/article/view/503

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

The prevailing issues regarding the three-dimensional (3-D) reconstruction of the industrial-urban environment and navigation model can be solved by using the method of selecting linear objects (straight lines and planes) in cloud points. The analysis of the three-dimensional version of the Hough method for selecting planar objects from a cloud of points has been done. A high-speed algorithm which is a development of the Hough method, based on a two-stage transformation of the initial data, taking into account their linear structuring into a three-dimensional parameter space has been proposed. The linear structuring of the input data generated by 3D laser sensors allows efficient selection of planar objects: first to find subsets of points belonging to line segments in the scanning planes, and then to find subsets of line segments belonging to one flat object. Comparative estimates of the computation volumes for the three-dimensional version of the Hough method and the proposed two-stage algorithm are obtained. Estimates give a quadratic and linear dependence on the same parameter, respectively, which provides for real 3D images increased performance in the second case by two orders of magnitude. The effectiveness of the proposed algorithm is confirmed by the results of the operation of the corresponding software and hardware in real environmental conditions. The obtained results of theoretical and experimental studies allow us to conclude that the created algorithm and software-hardware tools provide a transition in real time (in the rate of motion of control objects) from large volumes of initial visual ranging information to semantic information and navigation models. Formed models in an explicit and compact form contain geometric data about the external environment and navigation data about the sensor (control object). The possibility of forming semantic information and navigation models is based on data obtained from on-board sensors and on-board calculators in real time which allows for the present time to solve ongoing tasks for autonomous traffic control of AGV and UAV in the industrial-urban environment and buildings.

облако точеклинейные примитивыметод Хафадальнометрическое 3D-изображениелинейная структурированность исходных данныхгеометрическая и семантическая моделинавигацияpoint cloudlinear primitivesHough methodfar-ranging 3D-imagelinear structuring of initial datageometric and semantic modelsnavigationReferencesЛапшов В. С., Носков В. П. и др. Бой в городе. Боевые и обеспечивающие роботы в условиях урбанизированной территории // Известия ЮФУ. Технические науки. 2011. No 3. С. 142—146.Lapshov V. S., Noskov V. P. Boj v gorode. Boevye i obespechivajushhie roboty v uslovijah urbanizirovannoj territorii (Fight in the city. Combat and providing robots in an urbanized area), Izvestija JuFU. Tehnicheskie Nauki, 2011, no. 3, pp. 142—146 (in Russian).Носков А. В., Носков В. П. Распознавание ориентиров в дальнометрических изображениях // Мобильные роботы и мехатронные системы. 2001. С. 179—192.Noskov A. V., Noskov V. P. Raspoznavanie orientirov v dal’nometricheskih izobrazhenijah (Recognition of landmarks in the long-range images), Mobil’nye Roboty i Mehatronnye Sistemy, 2001, pp. 179—192 (in Russian).Носков В. П., Носков А. В. Навигация мобильных роботов по дальнометрическим изображениям // Мехатроника, автоматизация, управление. 2005. No 12. С. 16—21.Noskov V. P., Noskov A. V. Navigacija mobil’nyh robotov po dal’nometricheskim izobrazhenijam (Navigation of mobile robots on the dalometric images), Mkehatronika, Avtomatizatsiya, Upravlenie, 2005, no. 12, pp. 16—21 (in Russian).Носков В. П., Рубцов И. В. Опыт решения задачи автономного управления движением мобильных роботов // Мехатроника, автоматизация, управление. 2005. No 12. С. 21—24.Noskov V. P., Rubcov I. V. Opyt reshenija zadachi avtonomnogo upravlenija dvizheniem mobil’nyh robotov (Experience in solving the problem of autonomous traffic control of mobile robots), Mekhatronika, Avtomatizatsiya, Upravlenie, 2005, no. 12, pp. 21—24 (in Russian).Носков В. П., Рубцов И. В., Романов А. Ю. Формирование объединенной модели внешней среды на основе информации видеокамеры и дальномера // Мехатроника, автоматизация, управление. 2007. No 8. С. 2—5.Noskov V. P., Rubcov I. V., Romanov A. Ju. Formirovanie ob’edinennoj modeli vneshnej sredy na osnove informacii videokamery i dal’nomera (Formation of the integrated model of the external environment on the basis of the information of the video camera and the range finder), Mekhatronika, Avtomatizatsiya, Upravlenie, 2007, no. 8, pp. 2—5 (in Russian).Загоруйко С. Н., Казьмин В. Н., Носков В. П. Навигация БПЛА и 3D-реконструкция внешней среды по данным бортовой СТЗ // Мехатроника, автоматизация, управление. 2014. No 8. С. 62—68.Zagorujko S. N., Kaz’min V. N., Noskov V. P. Navigacija BPLA i 3D-rekonstrukcija vneshnej sredy po dannym bortovoj STZ (Navigation UAV and 3D-reconstruction of the external environment according to the on-board technical vision system), Mekhatronika, Avtomatizatsiya, Upravlenie, 2014, no. 8, pp. 62—68 (in Russian).Segal A., Haehnel A. S. D., Thrun S. Generalized ICP // Proc. of Robotics: Science and Systems (RSS). 2009.Segal A., Haehnel D., Thrun S. Generalized-ICP, Proc. of Robotics: Science and Systems, RSS, 2009.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.Mitra N., Gelfand N., Pottmann H., Guibas L. J. Registration of Point Cloud Data from a Geometric Optimization Perspective, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, 2004, pp. 22—31.Казьмин В. Н., Носков В. П. Выделение геометрических и семантических объектов в дальнометрических изображениях для навигации роботов и реконструкции внешней среды // Известия ЮФУ. Технические науки. 2015. No 10 (171). С. 71—83.Kaz’min V. N., Noskov V. P. Vydelenie geometricheskih i semanticheskih ob’ektov v dal’nometricheskih izobrazhenijah dlja navigacii robotov i rekonstrukcii vneshnej sredy (Isolation of geometric and semantic objects in the long-range images for navigation of robots and reconstruction of the external environment), Izvestija JuFU. Tehnicheskie Nauki, 2015, no. 10 (171), pp. 71—83 (in Russian).Павловский В. Е., Павловский В. В. Технологии SLAM для подвижных роботов // Мехатроника, автоматизация, управление. 2016. No 6. С. 384—394.Pavlovskij V. E., Pavlovskij V. V. Tehnologii SLAM dlja podvizhnyh robotov [SLAM for mobile robots], Mekhatronika, Avtomatizatsiya, Upravlenie, 2016, no. 6, pp. 384—394 (in Russian).Konouchine A., Gaganov V., Veznevets V. AMLESAC: A new maximum likelihood robust estimator // Proc. Graphicon. 2005. Vol. 5. P. 93—100.Konouchine A., Gaganov V., Veznevets V. AMLESAC: A new maximum likelihood robust estimator, Proc. Graphico”, 2005, vol. 5, pp. 93—100.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.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, pp. 3206—3211.Holz D. et al. Real-time plane segmentation using RGB-D cameras // Robot Soccer World Cup. Springer, Berlin, Heidelberg. 2011. P. 306—317.Holz D. et al. Real-time plane segmentation using RGB-D cameras, Robot Soccer World Cup, Springer, Berlin, Heidelberg, 2011, pp. 306—317.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.Comaniciu D., Meer P., Mean shift: A robust approach toward feature space analysis, IEEE Transactions on pattern analysis and machine intelligence, 2002, vol. 24, no. 5, pp. 603—619.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.Berkmann J., Caelli T. Computation of surface geometry and segmentation using covariance techniques, IEEE Transactions on Pattern Analysis and Machine Intelligence, 1994, vol. 16, no. 11, pp. 1114—1116.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.Mitra N. J., Nguyen A., Guibas L. Estimating surface normals in noisy point cloud data, International Journal of Computational Geometry & Applications, 2004, vol. 14. no. 04—05, pp. 261—276.Велижев А., Шаповалов Р., Потапов Д., Третьяк Е., Конушин А. Автоматическая сегментация облаков точек на основе элементов поверхности // Cборник "Труды конференции GraphiCon — 2009". 2009. С. 241—245.Velizhev A., Shapovalov R., Potapov D., Tret’jak E., Konushin A. Avtomaticheskaja segmentacija oblakov tochek na osnove jelementov poverhnosti (Automatic segmentation of point clouds based on surface elements), Trudy konferencii GraphiCon — 2009, 2009, pp. 241—245 (in Russian).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.Sedlacek D., Zara J. Graph cut based point-cloud segmentation for polygonal reconstruction, International Symposium on Visual Computing, Springer, Berlin, Heidelberg, 2009, pp. 218—227.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.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, no. 2. pp. 3.Гошин Е. В., Лошкарева Г. Е. Информационная технология сегментации разноракурсных изображений с использованием трехмерного преобразования Хафа // Матер. Междунар. конференции и молодежной школы "Информационные технологии и нанотехнологии". 2016. С. 342—349.Goshin E. V., Loshkareva G. E. Informacionnaja tehnologija segmentacii raznorakursnyh izobrazhenij s ispol’zovaniem trjohmernogo preobrazovanija Hafa (Information technology for segmentation of different-angle images using the three-dimensional Haught transformation), Izdatel’stvo SGAU, Materialy Mezhdunarodnoj konferencii i molodjozhnoj shkoly "Informacionnye tehnologii i nanotehnologii", 2016, pp. 342—349 (in Russian).Hough P. V. C. Method and means for recognizing complex patterns: пат. 3069654 США. 1962.Hough P. V. C. Method and means for recognizing complex patterns: patterns, 3069654 USA, 1962.

The authors declare that there are no conflicts of interest present.