МЕТОД РАСПОЗНАВАНИЯ ОБЪЕКТОВ ПО ДАННЫМ ЛАЗЕРНОГО СКАНИРОВАНИЯ НА ОСНОВЕ СПЕКТРАЛЬНОЙ ТЕОРИИ ГРАФОВ

А. Н. Каркищенко; С. П. Левашев

А. Н. Каркищенко Южный Федеральный Университет
С. П. Левашев Южный Федеральный Университет

Ключевые слова: Лазерное сканирование, распознавание объектов, матрица Лапласа, спектр графа, инвариант графа

Аннотация

Предлагается метод распознавания объектов по данным лазерного сканирования. Эти данные можно получить сканированием объектов специальным прибором LIDAR (LIght Detection And Ranging) в виде облака точек, которое представляет собой неупорядо-ченный набор точек с координатами трехмерного пространства. Решение многих задач компьютерного зрения и распознавания c использованием данных лазерного сканирования зачастую эффективней, чем с использованием двумерных данных по нескольким причинам. Во-первых, третья координата повышает информативность и способствует более под-робному описанию объекта. Во-вторых, качество облака точек не зависит от погодных условий, при которых проводилось лазерное сканирование. В-третьих, облако точек позво-ляет сохранить масштабы объектов. Современные приборы LIDAR позволяют получить данные высокой детализации с большим количеством точек. Однако использование всех точек для распознавания объектов может привести к большим вычислительным затра-там. Кроме того данные могут содержать зашумления и выбросы, приводящие к ошибкам в распознавании. Для повышения качества распознавания выполняется предварительное сжатие данных при помощи признакового описания в виде дескрипторов, инвариантных к ряду преобразований. Таким образом, с одной стороны снижается зависимость от зашум-лений и выбросов, с другой − уменьшаются вычислительные затраты. В настоящее время для решения задач распознавания объектов, все чаще применяются подходы, связанные с представлением структур анализируемых объектов в виде графов. Предлагаемый метод основывается на использовании структур объектов, которые описываются частями облака точек. Распознавание осуществляется путем сравнения комплексных спектральных разложений графов, характеризующих структуры объектов. Предлагаются способы опре-деления весовых коэффициентов графа структуры на основе пространственных характе-ристик множеств точек. Также предлагается способ предварительного отбора объектов, существенно отличающихся по структуре с использованием собственных значений в спек-тральных разложениях графов. Эффективность предлагаемого подхода демонстрируют результаты экспериментов.

Литература

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.