تعيين توصيفگرهاي بهينه در خوشه‌بندي داده‌هاي ليدار با استفاده از الگوريتم ژنتيك

Optimal Feature Selection in Clustering of LiDAR Data Using GA Algorithm

در سال­های اخیر، تكنولوژی لیدار به عنوان یك تكنولوژی كارآمد در كسب اطلاعات سه­بعدی از زمین شناخته شده و هر روز بیش از پیش مورد توجه مهندسین و متخصصان مهندسی ژئوماتیك قرار می­گیرد. استخراج عوارض از داده­های لیدار به عنوان یكی از مسائل مهم در پردازش این اطلاعات به  شمار می­آید. یكی از راه­های استخراج اتوماتیك عوارض از این داده­ها استفاده از الگوریتم­های خوشه­بندی می‍باشد. تعیین روش بهینه خوشه­بندی، تعداد خوشه بهینه و همچنین توصیفگرهای بهینه از جمله مسائل مهم در خوشه­بندی این داده­ها می­باشند كه تاكنون یك جواب ثابت و جهانی برای آنها ارائه نشده است. هدف از این تحقیق، تعیین توصیفگرهای بهینه در خوشه­بندی داده­های لیدار می­باشد. برای این منظور، از یك نمونه داده لیدار 147 توصیفگر بافتی استخراج شده و با مینیمم كردن معیار NCE با كمك الگوریتم ژنتیك، كه به عنوان یكی از الگوریتم­های قوی در حل مسائل بهینه­سازی مطرح می­باشد، توصیفگرهای بهینه استخراج شدند. نتایج بدست آمده كارآیی الگوریتم ژنتیك در بهینه­سازی و نیز بهینه بودن توصیفگرهای انتخاب­شده را نشان می­دهند.

LiDAR has been recently known as a powerful technology for 3D information acquisition from objects, and researchers are working on developing reliable techniques such as clustering for automatic object extraction from LiDAR data. Finding optimal clustering method, number of clusters and descriptors are the most challenging problems in clustering of LiDAR data. In this research, a GA based solution is presented for finding optimal descriptors of in LiDAR data clustering. A vast number of features were considered in two categories of single operator and composite descriptors. Single operator features are extracted from first and last pulses of intensity and range data (FR, LR, FI and LI) in which, each operator are executed on this four data to extract four operator features. Besides, two other features of NDIR and NDII are also extracted from the resulted features. Here, ten groups of single operator features were extracted: Raw data (6 features), Scene Ratio(12 features), fractal (12 features), Gabor (12 features), Haralick (24 features), Moments (24 features), SemiVariogram (12 features), Normal Vector (36 features) and Roughness (6 features). Composite features are extracted using a combination of the operators in the first category which nine features were generated. Finally, 171 features are extracted from LiDAR data. To simplify the computations, in the first level, unsuitable features are deleted from the list based on manual observation. Minimizing the NCE measure in clustering of LiDAR data using k-means algorithm, optimal descriptors in the remained list are assessed through Genetic Algorithm.  To evaluate the proposed method a sample area from the city of Stuttgart, Germany, were used. From the 171 extracted features 100 unsuitable features were deleted manually and the optimization process were executed on 71 features. In the sample area three clusters of Buildings, Trees and Land were considered for clustering. After executing GA process 5 features were selected as optimal features. Obtained results proved the ability of the GA algorithm as an optimization tool as well as the optimality of the selected descriptors in clustering.