طبقه‌بندی ابرنقاط لیدار به‌کمک میدان تصادفی مارکوف و تکنیک‌های یادگیری ماشین

نوع مقاله : علمی - پژوهشی

نویسندگان

1 دانشجوی کارشناسی ارشد علوم تصمیم و مهندسی دانش، دانشگاه خوارزمی، تهران

2 استادیار گروه ریاضی و علوم کامپیوتر، دانشگاه خوارزمی، تهران

3 استادیار، مرکز مطالعات سنجش از دور و GIS، دانشگاه شهید بهشتی، تهران

چکیده

امروزه در زمینة مدیریت شهری، رباتیک، تولید بازی‌های رایانه‌ای و مانند آن، از ابرنقاط لیدار در استخراج عوارض شهری و سه‌بعدی‌سازی استفادة گسترده‌ای می‌شود. خوشه‌بندی و طبقه‌بندی نقاط ابری لیدار یکی از گام‌های اصلی برای رسیدن به مدلی سه‌بعدی به‌شمار می‌رود؛ بنابراین، یکی از اهداف این تحقیق را می‌توان ارزیابی کارآیی روش‌های طبقه‌بندی K‌اٌمین همسایگی نزدیک (KNN)، درخت تصمیم (DT)، بیز ساده (Naïve Bayes)، شبکة عصبی مصنوعی (ANN)، ماشین بردار پشتیبان (SVM) و میدان تصادفی مارکوف (MRF) در طبقه‌بندی مجموعه دادة لیدار و تصاویر هوایی در محیط پیچیده شهری برشمرد. بدین‌منظور، داده‌هایی که ISPRS از شهر فایهینگن کشور آلمان فراهم آورده، به‌کار رفته است. سپس همة ویژگی‌های هندسی، مقادیر شدت ثبت‌شده از سوی لیدار، تصاویر هوایی و نیز ویژگی‌های استخراج‌شدة مبتنی‌بر مقادیر ویژه را استخراج و به‌منظور تشخیص پنج کلاس اشیای شهری شامل سطوح نفوذناپذیر، ساختمان، گیاهان کم‌ارتفاع، درخت و اتومبیل به‌کار برده است. برای محاسبة مقادیر ویژه به‌کمک توزیع محلی نقاط، در این مقاله، یک ساختار مکعبی جدید معرفی شده است که در تحقیقات گذشته دیده نشده بود. نتایج نهایی تکنیک‌های طبقه‌بندی به‌کاررفته در این تحقیق با استفاده از نقشه‌های رفرنس ISPRS ارزیابی شدند. نتایج ارزیابی این تحقیق نشان می‌دهد که مدل MRF با دقت کلی 88.08% و ضریب کاپای 0.83 کارآتر از دیگر طبقه‌بندی‌هاست. همچنین، ساختار مکعبی پیشنهادی را می‌توان، به‌خوبی ساختارهای کروی و استوانه‌ای، در استخراج ویژگی‌های مبتنی‌بر مقادیر ویژه به‌کار برد.

کلیدواژه‌ها


عنوان مقاله [English]

Classification of LiDAR Points Cloud Using Markov Random Field and Machine Learning Techniques

نویسندگان [English]

  • F Aghighi 1
  • O.M Ebadati 2
  • H Aghighi 3
1 M.Sc. Student in Knowledge Engineering and Decision Science, Kharazmi University, Tehran
2 Assistant Prof., Dep. of Mathematics and Computer Science, Kharazmi University, Tehran
3 Assistant Prof., Research Center of Remote Sensing and GIS, Shahid Beheshti University, Tehran
چکیده [English]

Light Detection and Ranging (LiDAR) point cloud dataset and 3 dimensional (3-D) models have been extensively used for urban feature extraction, urban management, forestry management, managing urban green space, tourism management, robotics, and video and computer games' production. One of the main steps toward reaching accurate 3-D models is clustering and classification of LiDAR point clouds data. The main purpose of this research is to find out, particular machine learning techniques, which are promising for best learning and classification of LiDAR point cloud data in an urban area. Therefore, the performances of K-nearest neighbor (KNN), Decision Trees (D3), Artificial Neural Networks (ANN), Naive Bayes (NB), Support Vector Machine (SVM), and Markov Random Field (MRF) classifiers were evaluated on the LiDAR and aerial image dataset of Vaihingen, Germany, in the context of the "ISPRS Test Project on Urban Classification and 3D Building Reconstruction." In regard to the literature review, MRF model has not been used to classify LiDAR point cloud data in Iran. In this research, we utilized all the geometrical features, intensity values of LiDAR and aerial images as well as extracted eigenvalues based features to distinguish five urban object classes, including impervious surfaces, buildings, low vegetation, trees and cars. In order to compute eigenvalues using local point distribution, this paper introduces a new cubic structure, which has been not found in previous studies. The final results of 3D classification techniques in this research were 2D maps that evaluated by the benchmark ISPRS tests maps. The evaluation shows that the performance of MRF model with an overall accuracy of 88.08% and the kappa value of 0.83 is higher than other techniques to classify the employed LiDAR point clouds.

کلیدواژه‌ها [English]

  • LiDAR Point Clouds
  • Classification
  • Machine Learning
  • Markov Random Field
  • Urban
  1. حاجب، م.، 1388، استخراج جاده‌ها از داده‌های لیدار، پایان‌نامة کارشناسی ارشد، گروه آموزشی سنجش از دور و GIS دانشگاه شهید بهشتی.
  2. حسن‌زادة شاهراجی، م.، 1390، توسعة یک الگوریتم طبقه‌بندی داده‌های لیدار موج‌ـ پیوسته در مناطق شهری، پایان‌نامة کارشناسی ارشد، دانشکدة مهندسی نقشه‌برداری، ژئودزی و ژئوماتیک دانشگاه صنعتی خواجه نصیرالدین طوسی.
  3. صادقی، ب.، عبادی، ح.، مقصودی، ی.، 1394، تلفیق داده های ابر طیفی و لیدار در طبقه بندی کلاس مبنای پوشش های زمینی در مناطق شهری، اولین کنفرانس ملی مهندسی فناوری اطلاعات مکانی، 9.
  4. صمدزادگان، ف.، محمودی، ف.ط.، 1388، ارائة یک روش چندعاملی به‌منظور استخراج اتوماتیک اشیای سه‌بعدی براساس داده‌های لیدار، همایش ژئوماتیک، تهران، سازمان نقشه‌برداری کشور.
  5. گلشنی، پ.، فلاح، الف.، کلبی، س.، 1393، مقایسة الگوریتم‌های GeoEye-1 برآورد سطح تاج‌پوشش جنگل‌های شهری با استفاده از روش‌های ناپامتری و داده‌های (BRT و (RF، نشریة پژوهش‌های علوم و فناوری چوب و جنگل، جلد 21، شمارة اول.
  6. هژبری، ب.، 1393، بازسازی مدل ساختمان برمبنای تلفیق ابرنقطة لیدار و تصویر هوایی، نشریة علمی‌ـ پژوهشی علوم و فنون نقشه‌برداری، دورة 3 ، شمارة 4، صص. 121-103.
  7. Aghighi, H., Trinder, J., Tarabalka, Y. & Lim, S., 2014, Dynamic Block-Based Parameter Estimation for MRF Classification of High-Resolution Images, Geoscience and Remote Sensing Letters, 11(10), PP. 1687-1691.
  8. Asefi, H., Jolai, F., Rabiee, M., Araghi, M. T., 2014, A hybrid NSGA-II and VNS for solving a bi-objective no-wait flexible flowshop scheduling problem, The Inter-national Journal of Advanced Manufacturing Technology, 75(5-8), PP. 1017-1033
  9. Azadbakht, M., 2016, Improved Urban Scene Classification Using Full-Waveform Lidar, Photogrammetric Engineering & Remote Sensing, 82(12), PP. 973-980.
  10. Blake, A., Kohli, P.,Rother, C., 2011, Markov random fields for vision and image processing, Mit Press.
  11. Bishop, C.M., 2006, Pattern Recognition and Machine Learning, Springer.
  12. Calderon, M. & de Brito, A., 2016, ECG Time Series Data Mining for Cardiovascular Disease Risk Assessment, ETSI_Informatica.
  13. Chang, C.C. & Lin, C.J., 2011, LIBSVM: A Library for Support Vector Machines, ACM Transactions on Intelligent Systems and Technology (TIST), 2(3), PP. 27.
  14. Chehata, N., Li, G. & Mallet, C., 2009, Airborne Lidar Feature Selection for Urban Classification Using Random Forests, International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 38, P. 8.
  15. Chen, S., 2011, Markov Models for Image Labeling, Mathematical Problems in Engineering, 44(1).
  16. Cramer, M., 2010, The DGPF-Test on Digital Airborne Camera Evaluation–Overview and Test Design, Photogrammetrie-Fernerkundung-Geoinformation, 2, PP. 73-82.
  17. Dal Poz, A.P., 2009, 3D Lidar Building Roof Refinement Using Photogrammetric Data, International Cartography Conference, (24th ICC).
  18. Deb, K., Thiele, L., Laumanns, M., Zitzler, E., 2005, Scalable test problems for evolutionary multiobjective optimization, Springer.
  19. Foody, G.M., 2004, Thematic Map Comparison, Photogrammetric Engineering & Remote Sensing, 70(5), PP. 627-633.
  20. Friedman, N., Geiger, D., Goldszmidt, M., 1997, Bayesian Network Classifiers, Machine Learning, 29. PP.131-163.
  21. Geman, S., Geman & D., 1984, Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images, Pattern Analysis and Machine Intelligence, IEEE Transactions on (6), PP. 721-741.
  22. Giannakopoulos, I., Tsoumakos, D., Koziris, N., 2017, A Decision Tree Based Approach Towards Adaptive Profiling of Cloud Applications, arXiv preprint arXiv: 1704.02855
  23. Golovinskiy, A., 2009, Shape-Based Recognition of 3D Point Clouds in Urban Environments, Computer Vision, 2009 IEEE 12th International Conference on, IEEE.
  24. Gross, H. & Thoennessen, U., 2006, Extraction of Lines from Laser Point Clouds, Symposium of ISPRS Commission III: Photogrammetric Computer Vision PCV06, International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences.
  25. Guo, L., Chehata, N., Mallet, C. & Boukir, S., 2011, Relevance of Airborne Lidar and Multispectral Image Data for Urban Scene Classification Using Random Forests, ISPRS Journal of Photogrammetry and Remote Sensing, 66(1), PP. 56-66.
  26. Hao, W. & Wang, Y., 2016, Structure-Based Object Detection from Scene Point Clouds, Neurocomputing.
  27. Han, J., Pei, M., Kamber, M., 2011, Data mining: concepts and techniques, Elsevier
  28. Kasetkasem, T., Arora, M.K. & Varshney, P.K., 2005, Super-Resolution Land Cover Mapping Using a Markov Random Field Based Approach, Remote sensing of environment, 96(3), PP. 302-314.
  29. Kim, K. & Shan, J., 2011, Building Roof Modeling from Airborne Laser Scanning Data Based on Level Set Approach, ISPRS Journal of Photogrammetry and Remote Sensing, 66(4), PP. 484-497.
  30. Kumar, M., 2004, Feature selection for classification of hyperspectral remotely sensed data using NSGA-II, Water Resources Seminar CE D.
  31. Lamba, A. & Kumar, D., 2016, Survey on KNN and its Variants, International Journal of Advanced Research in Computer and Communication Engineering, 5(5).
  32. Li, M., 2014, A Review of Remote Sensing Image Classification Techniques: The Role of Spatio-Contextual Information, European Journal of Remote Sensing, 47, pp. 389-411.
  33. Li, S., 1994, Markov Random Field Models in Computer Vision, Computer Vision—ECCV'94, PP. 361-370.
  34. Lu, D. & Weng, Q., 2007, A Survey of Image Classification Methods and Techniques for Improving Classification Performance, International Journal of Remote Sensing, 28(5), PP. 823-870.
  35. Mather, P.M., 2005, Computer Processing of Remotely-Sensed Images: An Introduction, Wiley, 3rd Edition.
  36. Niemeyer, J., Rottensteiner, F. & Soergel, U., 2012, Conditional Random Fields for Lidar Point Cloud Classification in Complex Urban Areas, ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 1(3), PP. 263-268.
  37. Pao, Y.H., 1989, Adaptive Pattern Recognition and Neural Networks, Addison-Wesley Longman Publishing Co., Inc. Boston, USA.
  38. Rottensteiner, F., Sohn, G., Gerke, M., Wegner, JD., Breitkopf, U. & Jung, J., 2014, Results of the ISPRS Benchmark on Urban Object Detection and 3D Building Reconstruction, ISPRS Journal of Photogrammetry and Remote Sensing, 93, PP. 256-271.
  39. Samadzadegan, F., Azizi, A., Hahn, M.T. & Lucas, C., 2005, Automatic 3D Object Recognition and Reconstruction Based on Neuro-Fuzzy Modelling, ISPRS Journal of Photogrammetry and Remote Sensing, 59(5), PP. 255-277.
  40. Satari, M., Azizi, A. & Maas, H.G., 2012, A Multi‐Resolution Hybrid Approach for Building Model Reconstruction from Lidar Data, The Photogrammetric Record, 27(139), PP. 330-359.
  41. Shi, Y., Choi, S., Ni, X., Ganguly, S., Zhang, G., Duong, H. V., Lefsky, M. A., Simarf, M., Saatchi, S. S., Lee, S., Ni-Meister, W., Piao, S., Cao, C., Nemani, R. R., Myneni, R. B., 2013, Allometric Scaling and Resource Limitation Model of Tree Heights: Part 1. Model Optimization and Testing over Continetal USA, Remote Sensing.
  42. Shirowzhan, S. & Trinder, J., 2017, Building Classification from Lidar Data for Spatio-temporal Assessment of 3D Urban Developments, Procedia Engineering, 180, PP. 1453-1461
  43. Solberg, A.H.S., Taxt, T.K. & Jain, A., 1996, A Markov Random Field Model for Classification of Multisource Satellite Imagery, IEEE Transactions on Geoscience and Remote Sensing, 34(1), PP. 100-113.
  44. Spreckels, V., Syrek, L. & Schlienkamp, A., 2010, DGPF-Project: Evaluation of Digital Photogrammetric Camera Systems–Stereoplotting, Photogrammetrie-Fernerkundung-Geoinformation, 2010(2), PP. 117-130.
  45. Srinivas, N., Deb, K., 1994, Muiltiobjective optimization using nondominated sorting in genetic algorithms, Evolutionary computa-tion, 2(3), PP. 221-248.
  46. Starek, M.J., 2016, Light Detection and Ranging (LIDAR), Encyclopedia of Estuaries, PP. 383-384.
  47. Tarabalka, Y., Fauvel, M. & Chanussot, J., 2010, SVM- and MRF-Based Method for Accurate Classification of Hyperspectral Images, IEEE Geoscience and Remote Sensing Letters, 7(4), PP. 736-740.
  48. Vetrivel, A., Gerke, M., Kerle, N. & Vosselman, G., 2015, Identification of Damage in Buildings Based on Gaps in 3D Point Clouds from Very High Resolution Oblique Airborne Images, ISPRS Journal of Photogrammetry and Remote Sensing, 105, PP. 61-78.
  49. Wegner, J.D., 2011, Detection and Height Estimation of Buildings from SAR and Optical Images Using Conditional Random Fields, Univ., Fachrichtung Geodäsie und Geoinformatik.
  50. Weinmann, M., Urban, S., Hinz, S., Jutzi, B., Mallet, C., 2015, Distinctive 2D and 3D features for automated large-scale scene analysis in urban, Computers & Graphics, 49, PP. 47-57.
  51. Zhang, J. & Sohn, G., 2010, A Markov Random Field Model for Individual Tree Detection from Airborne Laser Scanning Data, Proceedings of Photogrammetric Computer Vision (PCV) 2010 PP. 01-03.
  52. Zheng, Y. & Cao, Z., 2011, Classification Method for Aerial LiDAR Data Based on Markov Random Field, Electronics Letters, 47(16), PP. 934-936.
  53. Zitzler, E., Deb, K., Thiele, L., 2000, Comparison of multiobjective evolutionary algorithms:Empirical results, Evolutionary computation, 8(2), PP. 173-195.