A Three-Dimensional Version of the Hough Method in the Reconstruction of the External Environment and Navigation

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.

point cloud, linear primitives, Hough method, far-ranging 3D-image, linear structuring of initial data, geometric and semantic models, navigation

1. 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).

2. 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).

3. 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).

4. 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).

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).

6. 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).

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

8. 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.

9. 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).

10. 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).

11. Konouchine A., Gaganov V., Veznevets V. AMLESAC: A new maximum likelihood robust estimator, Proc. Graphico”, 2005, vol. 5, pp. 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, pp. 3206—3211.

13. Holz D. et al. Real-time plane segmentation using RGB-D cameras, Robot Soccer World Cup, Springer, Berlin, Heidelberg, 2011, pp. 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, no. 5, pp. 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, vol. 16, no. 11, pp. 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. no. 04—05, pp. 261—276.

17. 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).

18. 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.

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, no. 2. pp. 3.

20. 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).

21. Hough P. V. C. Method and means for recognizing complex patterns: patterns, 3069654 USA, 1962.