METHOD OF OBJECT RECOGNITION WIT THE USE OF LASER SCANNING DATA BASED ON SPECTRAL GRAPH THEORY

  • A. N. Karkischenko Southern Federal University
  • S. P. Levashev Southern Federal University
Keywords: Laser scanning, object recognition, Laplace matrix, graph spectrum, graph invariant

Abstract

The paper proposes a method for recognition of objects from laser scanning data. This data can be obtained by scanning objects with a special LIDAR device (LIght Detection And Ranging) in the form of a cloud of points, which is an unordered set of points with coordinates of three-dimensional space. Solving many computer vision and recognition problems using laser scan data is often more efficient than using two-dimensional data for several reasons. Firstly, the third coor-dinate increases the informativeness and promotes a more detailed description of the object. Sec-ondly, the quality of the point cloud does not depend on the weather conditions under which the laser scan was performed. In the third place, a point cloud allows you to keep the scale of objects. Modern LIDAR devices provide data high detail with a lot of points. However, the use of all points for object recognition can lead to large computational costs. In addition, the data may contain noise and outliers, leading to errors in recognition. To improve the quality of recognition, data is pre-compressed using an attribute description in the form of descriptors invariant to some trans-formations. Thus, on the one hand, the dependence on noise and emissions is reduced, on the other hand, computational costs are reduced. At present, for solving problems of object recognition,approaches are increasingly being used that are related to the representation of the structures of the objects being analyzed in the form of graphs. The proposed approach is based on the use of object structures, which are described by parts of a point cloud. Recognition is performed by com-paring the complex spectral decompositions graphs characterizing structure of objects. Methods are proposed for determining the weight coefficients of a structure graph based on the spatial characteristics of the sets of points. It also proposes a method of preliminary selection of objects that differ significantly in structure using eigenvalues in the spectral decompositions of graphs. The effectiveness of the proposed approach is demonstrated by the results of experiments.

References

1. Conte D., Foggia, P., Sansone C., Vento M. Thirty years of graph matching in pattern recogni-tion, International journal of pattern recognition and artificial intelligence, 2004, Vol. 18 (3), pp. 265-298.
2. Cho M., Alahari K., Ponce J. Learning graphs to match, in IEEE Interational Conference on Computer Vision (ICCV), 2013, pp. 25-32.
3. Osada R., Funkhouser T., Chazelle B., Dobkin D. Matching 3D models with shape distribu-tions, Proceedings International Conference on Shape Modeling and Applications, Genova, Italy, 2001, pp. 154-166.
4. Elad M., Tal A., Ar S. Content based retrieval of vrml objects – an iterative and interactive approach, Proceedings Sixth Eurographics Workshop Multimedia, 2001, pp. 97-108.
5. Vranic D.V., Saupe D., Richter J. Tools for 3d-object retrieval: Karhunen-loeve transformand spherical harmonics, IEEE MMSP 2001, 2001, pp. 293-298.
6. Brigham E.O., Morrow R.E. The fast Fourier transform, in IEEE Spectrum, 1967, Vol. 4 (12), pp. 63-70.
7. Tanaka K., Sano M., Mukawa N., Kanek H. 3D object representation using spherical harmonic functions, Proceedings of 1993 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS ’93), Yokohama, Japan, 1993, Vol. 3, pp. 1873-1880.
8. Sundar, H., Silver, D., Gagvani N., Dickinson, S. Skeleton based shape matching and retrieval, 2003 Shape Modeling International, Seoul, South Korea, 2003, pp. 130-139.
9. Feng C., Jalba A.C., Telea A.C. A descriptor for voxel shapes based on the skeleton cut space, Proceedings of the Eurographics 2016 Workshop on 3D Object Retrieval, 2016, Vol. 8 (8), pp. 13-20.
10. Chuang J., Tsai C., Ko M. Skeletonization of three-dimensional object using generalized po-tential field, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, Vol. 22 (11), pp. 1241-1251.
11. Chung F.R.K. Spectral graph theory, American Mathematical Society, 1997.
12. Varun J., Zhang H.A spectral approach to shape-based retrieval of articulated 3D models, Computer-Aided Design, 2007, Vol. 39 (5), pp.398-407.
13. Yang L. k-edge connected neighborhood graph for geodesic distance estimation and nonlinear data projection, Proceedings of International Conference on Pattern Recognition(ICPR), 2004, Vol. 1, pp.196-199.
14. Surazhsky V., Surazhsky T., Kirsanov D. Gortler S.J., Hoppe H. Fast exact and approximate geodesics on meshes, ACM Transactions on Graphics (TOG), 2005, Vol. 24, pp. 553-560.
15. Ng A.Y., Jordan M.I., Weiss Y. On spectral clustering: analysis and an algorithm, Proceedings of Neural Information Processing Systems (NIPS). 2002. Vol. 2 (3). pp. 857-864.
16. Caelli T., Kosinov S. An eigenspace projection clustering method for inexact graph matching, IEEE Transaction on Pattern Analysis and Machine Intelligence, 2004, Vol. 26 (4), pp. 515-519.
17. Levashev S. Segmentation of a point cloud by data on laser scanning intensities, Pattern Recognition and Image Analysis, 2019, Vol. 29 (1), pp. 144-155.
18. van Leuken R.H., Symonova O., Veltkamp R.C., De Amicis R. Complex Fiedler Vectors for Shape Retrieval, Structural, Syntactic, and Statistical Pattern Recognition, 2008, Vol. 5342, pp. 167-176.
19. Tsourakakis C.E. Fast counting of triangles in large real networks without counting: Algo-rithms and laws, IEEE International Conference on Data Mining (ICDM 2008), 2008, Vol. 0, pp. 608-617.
20. Bentley J.M. Multidimensional binary search trees used for associative searching, Communica-tion of the ACM, 1975, Vol. 18, pp. 509-517.
Published
2019-09-24
Issue
No 3 (2019)
Section
SECTION I. INFORMATION PROCESSING ALGORITHMS.