點云數據精簡與配準研究

龐正雅 周志峰 錢莉

摘 要：由于激光雷達等掃描設備得到的點云存在數據量大、數據中摻雜噪聲較多等一系列問題，提出一種基于特征點保持的點云精簡與配準方法。首先利用K-means算法對所有點云數據聚類，濾除掉噪聲點云，再進行精簡化處理;隨后在精簡的基礎上用KD-tree對數據進行最近鄰搜索以加快對應點查找速度，從而為配準節省一定的時間;最后根據歐氏距離選擇合適的初值減少匹配誤差。實驗結果表明，精簡后的點云數據保持了基本特征，一定程度上減少了配準時間和誤差。

關鍵詞：K-means聚類;kd-tree;點云精簡;點云配準

DOI：10. 11907/rjdk. 182261

中圖分類號：TP301

文獻標識碼：A文章編號：1672-7800（2019）006-0025-04

Abstract： Because of ?the point cloud obtained by scanning equipment such as laser radar has a series of problems， such as large data volume and high doping noise in data， a point cloud simplification and registration method based on feature point preservation is proposed. Firstly， K-means algorithm is used to cluster all point cloud data， filter out noise point cloud， and then simplify the processing.Then， on the basis of simplification， KD-tree is used to search the nearest neighbor of data to speed up the search speed of corresponding points， so as to save some time for registration. Finally， the matching error is reduced by selecting the appropriate initial value according to Euclidean distance.The experimental results show that the simplified point cloud data maintain basic characteristics and reduce the registration time and error to some extent.

Key Words： K-means clustering;KD-tree;point cloud simplification;point cloud registration

0 引言

無人駕駛汽車是人工智能的重要應用，激光雷達技術對無人駕駛安全技術起著關鍵作用。由于激光雷達等掃描設備得到的點云存在數據量大、數據中摻雜噪聲較多等一系列問題，因而在獲取點云時無法從一個角度獲取完整的點云數據。實際應用中通常通過多角度采集點云數據，然后將多個視角下的數據整理到同一個坐標系下通過配準技術獲得完整的點云。因此，如何對數據密度大且噪聲多的數據實現去噪、精簡、提高匹配精度和減少匹配時間是研究重點。

Hao Song[1]提出最小化輸入和簡化數據集之間的幾何偏差，本質上是將輸入數據集劃分為固定數量的點集群，每個點集群中選取一個點作為點集群代表，然后將這些代表的集合視為簡化的數據集，并根據每個集群的輸入數據集對結果的幾何偏差進行評估，但是當點數越來越小時這種方法可能失效。文獻[2]首先采用表面法向估計方法處理數據中幾何奇異性點云，然后基于改進的主成分分析法將點云去噪問題約束為非線性最小二乘法問題，從而實現點云去噪。Benhabiles等 [3]提出了一種基于聚類和由粗到細方法結合的快速點云簡化算法，可簡化尖角點密度高、平坦點密度低的點云。在點云的配準算法中，應用最廣泛的是1992年提出的ICP算法[4]。但是傳統的ICP算法存在明顯缺陷，對運算初值的選擇非常嚴格，并且需要遍歷模型上所有的點，不僅配準消耗時間長，并且很難得到全局最優解[5]。文獻[6]、[7]基于一種新的低重疊率多視點集配準方法，通過對點對的曲面分類、曲率和鄰域曲率的匹配，選擇重疊區域并利用重疊區域中的點搜索最優配準參數。

國內對點云數據的精簡與配準研究比國外晚，成果相對較少。文獻[8]利用K-means聚類算法在空間域內聚集相似點，利用最大法向量偏差作為聚類散度的度量，將聚類點集劃分為特征域中的一系列子簇。但由于采用的是最大法向量，所以當噪聲較為嚴重時該方法存在誤差。文獻[9]、[10]基于法線角和信息熵理論推導出點的重要性，刪除其中最不重要的點并逐步更新法向量和重要值，直到達到用戶指定的還原比率。文獻[11]利用體素內部和外部的斥力約束，基于一種迭代重采樣方法將重采樣點投射到所有可能的表面。該方法基于幾何處理，無法判斷是否存在孔洞，也無法確定孔洞是否由于遮擋或掃描問題造成。文獻[12]是基于熵準則遺傳算法的點云粗配準算法，即使只有少部分的點云數據重合或含有噪聲點云數據，配準效果也不錯。文獻[13]提出了基于點云特征的ICP算法，利用待測點云的曲率、面法線、點云密度等幾何特征，尋找兩點云的相關性，將幾何特征引入誤差函數中，實現兩點云的精確配準。文獻[14]、[15]在ICP算法基礎上提出一種迭代最近線算法，利用兩點云之間的連線作為配準依據，但是無法保證線段之間的對應關系。

綜上所述，為有效提高點云數據處理效率，本文利用K-means聚類算法對點云數據聚類，濾除掉噪聲點云，再進行精簡化處理。在精簡的基礎上用KD-tree對數據最近鄰進行搜索，加快對應點查找速度，從而為配準節省一定的時間，最后根據歐氏距離選擇合適的初值減少匹配誤差。經過驗證，本文算法穩定，在大規模的點云數據精簡后點云數據仍保持基本特征，且精簡后的數據配準效果較理想。

1 點云去噪與精簡

1.1 K-means聚類算法

1.2 點云去噪

在激光雷達采集點云數據過程中，由于設備精度、人為因素、環境因素等影響，最終得到的點云數據有密度不規則、數據中摻雜噪聲較多等一系列問題。點云數據還存在離散點，這是由于外部干擾如視線遮擋、障礙物等因素影響而產生的離被測物點云較遠的點。這些點有兩個特點：①遠離表面點云;②與相鄰點云連接形成的區域不平坦，因此通過計算歐式距離和曲率作為判斷噪聲點的標準。

算法流程：①設聚類后得到的一個點云集合為：[S=][{pi，i=1，2，？n}]，求每個點[pi]的K-1個[pj]鄰近點集;②計算[pi]到其K-1個鄰近點集的歐式距離，求k-1個歐式距離的平均值，記為該點的K鄰近點距離[di];③計算所有[pi]的K鄰近點距離的均值[μ=1Ni=1Ndi]和標準方差[σ=][1Ni=1N（di-μ）2];④通過均值和標準方差共同決定閾值，當點的K鄰近距離比閾值大時則判斷為噪聲點。

1.3 點云精簡

隨著市場上激光雷達掃描系統掃描速度和精度的迅猛發展，快速獲取目標物體的高精度海量點云已不是問題。但是如果直接對海量數據進行點云重建，會因為數據量密集而影響處理效率，嚴重阻礙特征信息的提取。為加快配準、曲面重建、形狀識別等算法速度，必須在盡量保留點云數據特征信息的前提下，濾除大量冗余數據以減少點云數據量[17]。

本文使用體素化網格方法對點云進行精簡化處理。首先對聚類去噪后的點云數據創建一個三維立方體集合，其體積按照具體情況設定;然后用三維立方體的重心近似表示立方體范圍內的其它點，這樣該三維立方體內所有點均可通過一個重心點最終表示。對所有三維立方體都進行處理后則可得到過濾后的點云。

2 點云配準技術

激光雷達采集點云數據過程中，由于采集環境光照不均勻、掃描物體的角度、被測物體被遮擋等因素，無法從一個角度得到完整的點云數據，因此實際應用中通常是多次、多角度采集點云數據，然后將多個視角下的數據根據變換矩陣整理到同一個坐標系下，通過配準技術獲得完整的點云[18]。

點云配準方法包括兩兩配準、對應估計、迭代最近點算法、采樣一致性初始配準算法等，經常使用的是迭代最近點算法。迭代最近點算法是基于最小二乘法的最優配準算法[19]，主要是將兩個不同坐標系下的點云經最小二乘法提供的變換矩陣，旋轉、平移后得到二者重疊部分。雖然傳統的迭代最近點算法配準時精度可達到一定要求，但效率較低。

ICP處理流程如下：①減少初始點云數據數量;②確定初始對應點集;③去除錯誤對應點對;④坐標變換求解。這4個步驟中求最近點集耗費的時間較多[20]。本文首先在目標點云中尋找若干特征點，采用kd-tree對數據最近鄰搜索以加快對應點查找速度，從而為配準節省一定的時間;然后根據歐氏距離選擇合適的初值減少匹配誤差。

算法流程：①減少初始點云數據量，讀取精簡后的目標點集[Xt]和參考點集[Yt]，并對[Yt]建立KD-Tree;②通過點的曲率特征，從目標點集[Xt]隨機選取N個特征點記為[Xt];③計算特征點集[Xt]中的每一點[xi]到[Yt]中每一點[yj]的距離，找出[xi]到[Yt]距離最短的點[yj]作為匹配點對，并計算匹配點對的曲率相似度;④根據最小二乘法計算得到的旋轉和平移矩陣，進行特征點坐標轉換;⑤迭代直到滿足誤差最小為止。

坐標系旋轉變換原理如圖3所示。設目標點集[Xt]里某一點在[XOY]坐標系下的坐標為[（x，y）]，直角坐標系旋轉[θ]角度后在[XOY]坐標系下的坐標為[（x1，y1）]，通過點[（x，y）]和旋轉角度可得到[x1]、[y1]的值。

3 實驗結果及分析

本文基于Windows7系統進行實驗平臺搭建，首先在Windows下安裝VMware-workstation并在虛擬機VMWare上運行Ubuntu 14.04，然后在Ubuntu 14.04下安裝一些必要的環境工具，如CMAKE、QT、VTK、boost庫等，最后安裝PCL 1.8.1、Microsoft Visual Studio 2013。仿真實驗主要利用C與C++語言，結合PCL庫，在虛擬機環境下利用Microsoft Visual Studio 2013開發平臺進行編程開發實現。

首先濾除桌子點云數據中的噪聲點，如圖4所示。圖4（a）中初始點云共有460 400個數據，圖4（b）中經過去噪后的點云共有451 410個數據，圖4（c）為被去掉的噪聲點云，共8 990 個數據。

然后對濾除噪聲數據的點云進行精簡化處理，在保留點云數據特征信息的前提下，對過密的點云數據進行精簡，去除大量冗余數據，如圖5所示。圖5（a）中白色為初始點云共451 410個數據，綠色為經過精簡后的點云共 ?36 993個數據，雖然只保留了原來數據的1/12，但從圖5（b）中可以看出，點云的邊緣和特征信息得到很好的保留。最后對精簡后的數據進行配準處理，如圖6所示。圖6中白色點云為原始點云，綠色點云為經過一定轉換后的目標點云，紅色為配準后的點云。經過24次迭代后完成配準，誤差值達到最小（見封二彩圖）。

本文還對不同數據量的點云進行配準比較。圖7、圖8、圖9分別是對bunny、horse、dragon數據的配準。表1為以上數據的配準結果。

4 結語

本文對點云數據進行了聚類、去噪和精簡化處理，并對精簡后的數據進行配準。通過上述實驗結果可知，基于特征點保持的點云精簡與配準方法對于大規模的點云數據去噪和精簡效果都很好，且減少了配準時間。

本文雖然一定程度上提升了配準速度和精度，但點云配準算法本身具有一定的復雜性，使得在配準數據量龐大的點云時沒有明顯效率優勢，這是下一步工作改進方向。

參考文獻：

[1] HAO S，HIS Y F. A global clustering approach to point cloud simplification with a specified data reduction ratio[J]. Computer-aided Design，2008，40（3）：281-292.

[2] CASTILLO E，LIANG J，ZHAO H. Point cloud segmentation and denoising via constrained nonlinear least squares normal estimates[M]. Germany：Springer Berlin Heidelberg ，2013.

[3] BENHABILES H， AUBRETON O， BARKI H， et al. Fast simplification with sharp feature preserving for 3D point clouds[J]. International Symposium on Programming and Systems （ISPS），2013（11）： 47-52.

[4] BESL P，MCKAY N D. A method for registration of 3D shapes[C]. IEEE Transactions on Pattern Analysis and Machine Intelligence，1992：239-256.

[5] 楊現輝，王惠南. ICP算法在3D點云配準中的應用研究[J]. 計算機仿真，2010，27（8）：235-238.

[6] LI Q D，GRIFFITHS J G. Iterative closest geometric objects registration[J]. Computers and Mathematics with Applications，2000，40（10）：1171-1188.

[7] GE X M. Non-rigid registration of 3D point clouds under isometric deformation[J]. ?ISPRS Journal of Photogrammetry and Remote Sensing，2016（121）：192-202.

[8] SHI B Q，LIANG J，LIU Q. Adaptive simplification of point cloud using K-means clustering[J]. Computer-aided Design，2011，43（8）：910-922.

[9] HAN H Y，HAN X，SUN F S，et al. Point cloud simplification with preserved edge based on normal vector[J]. Optik - International Journal for Light and Electron Optics，2015，126（19）：2157-2162.

[10] WEI X，HUA X G，CHEN X J. A new progressive simplification method for point cloud using local entropy of normal angle[J]. Journal of the Indian Society of Remote Sensing，2018，46（4）：581-589.

[11] LI M L，SUN C M. Refinement of lidar point clouds using a super voxel based approach[J]. ISPRS Journal of Photogrammetry and Remote Sensing，2018（143）：213-221.

[12] 陳杰. 散亂點云配準技術優化研究[D]. 綿陽：西南科技大學，2018.

[13] HE Y，LIANG B，YANG J，et al. An iterative closest points algorithm for registration of 3D laser scanner point clouds with geometric features[J]. Sensors （Basel， Switzerland），2017，17（8）：1862-1865.

[14] WU Y F，WANG W，LU K Q，et al. A new method for registration of 3D point sets with low overlapping ratios[J]. Procedia CIRP，2015（27）：202-206.

[15] JOAQUIM SALVI，MATABOSCH C，DAVID FOFI，et al. A review of recent range image registration methods with accuracy evaluation[J]. ?Image and Vision Computing，2006，25（5）：578-596.

[16] 楊輝華，王克，李靈巧，等. 基于自適應布谷鳥搜索算法的K-means聚類算法及其應用[J]. 計算機應用，2016，36（8）：2066-2070.

[17] 李仁忠，楊曼，劉陽陽，等. 一種散亂點云的均勻精簡算法[J]. 光學學報，2017，37（7）：97-105.

[18] 孫威，黃惠. 機器人輔助的三維點云自動配準[J]. 集成技術，2015，4（6）：37-45.

[19] 邱世聰，羅意. 改進ICP算法的點云配準[J]. 河南科技，2017（7）：40-42.

[20] 戴靜蘭，陳志楊，葉修梓. ICP算法在點云配準中的應用[J]. 中國圖象圖形學報，2007（3）：517-521.

（責任編輯：杜能鋼）