龐正雅 周志峰 錢莉

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

關(guān)鍵詞：K-means聚類;kd-tree;點(diǎn)云精簡(jiǎn);點(diǎn)云配準(zhǔn)

DOI：10. 11907/rjdk. 182261

中圖分類號(hào)：TP301

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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 引言

無(wú)人駕駛汽車是人工智能的重要應(yīng)用，激光雷達(dá)技術(shù)對(duì)無(wú)人駕駛安全技術(shù)起著關(guān)鍵作用。由于激光雷達(dá)等掃描設(shè)備得到的點(diǎn)云存在數(shù)據(jù)量大、數(shù)據(jù)中摻雜噪聲較多等一系列問題，因而在獲取點(diǎn)云時(shí)無(wú)法從一個(gè)角度獲取完整的點(diǎn)云數(shù)據(jù)。實(shí)際應(yīng)用中通常通過(guò)多角度采集點(diǎn)云數(shù)據(jù)，然后將多個(gè)視角下的數(shù)據(jù)整理到同一個(gè)坐標(biāo)系下通過(guò)配準(zhǔn)技術(shù)獲得完整的點(diǎn)云。因此，如何對(duì)數(shù)據(jù)密度大且噪聲多的數(shù)據(jù)實(shí)現(xiàn)去噪、精簡(jiǎn)、提高匹配精度和減少匹配時(shí)間是研究重點(diǎn)。

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

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

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

1 點(diǎn)云去噪與精簡(jiǎn)

1.1 K-means聚類算法

1.2 點(diǎn)云去噪

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

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

1.3 點(diǎn)云精簡(jiǎn)

隨著市場(chǎng)上激光雷達(dá)掃描系統(tǒng)掃描速度和精度的迅猛發(fā)展，快速獲取目標(biāo)物體的高精度海量點(diǎn)云已不是問題。但是如果直接對(duì)海量數(shù)據(jù)進(jìn)行點(diǎn)云重建，會(huì)因?yàn)閿?shù)據(jù)量密集而影響處理效率，嚴(yán)重阻礙特征信息的提取。為加快配準(zhǔn)、曲面重建、形狀識(shí)別等算法速度，必須在盡量保留點(diǎn)云數(shù)據(jù)特征信息的前提下，濾除大量冗余數(shù)據(jù)以減少點(diǎn)云數(shù)據(jù)量[17]。

本文使用體素化網(wǎng)格方法對(duì)點(diǎn)云進(jìn)行精簡(jiǎn)化處理。首先對(duì)聚類去噪后的點(diǎn)云數(shù)據(jù)創(chuàng)建一個(gè)三維立方體集合，其體積按照具體情況設(shè)定;然后用三維立方體的重心近似表示立方體范圍內(nèi)的其它點(diǎn)，這樣該三維立方體內(nèi)所有點(diǎn)均可通過(guò)一個(gè)重心點(diǎn)最終表示。對(duì)所有三維立方體都進(jìn)行處理后則可得到過(guò)濾后的點(diǎn)云。

2 點(diǎn)云配準(zhǔn)技術(shù)

激光雷達(dá)采集點(diǎn)云數(shù)據(jù)過(guò)程中，由于采集環(huán)境光照不均勻、掃描物體的角度、被測(cè)物體被遮擋等因素，無(wú)法從一個(gè)角度得到完整的點(diǎn)云數(shù)據(jù)，因此實(shí)際應(yīng)用中通常是多次、多角度采集點(diǎn)云數(shù)據(jù)，然后將多個(gè)視角下的數(shù)據(jù)根據(jù)變換矩陣整理到同一個(gè)坐標(biāo)系下，通過(guò)配準(zhǔn)技術(shù)獲得完整的點(diǎn)云[18]。

點(diǎn)云配準(zhǔn)方法包括兩兩配準(zhǔn)、對(duì)應(yīng)估計(jì)、迭代最近點(diǎn)算法、采樣一致性初始配準(zhǔn)算法等，經(jīng)常使用的是迭代最近點(diǎn)算法。迭代最近點(diǎn)算法是基于最小二乘法的最優(yōu)配準(zhǔn)算法[19]，主要是將兩個(gè)不同坐標(biāo)系下的點(diǎn)云經(jīng)最小二乘法提供的變換矩陣，旋轉(zhuǎn)、平移后得到二者重疊部分。雖然傳統(tǒng)的迭代最近點(diǎn)算法配準(zhǔn)時(shí)精度可達(dá)到一定要求，但效率較低。

ICP處理流程如下：①減少初始點(diǎn)云數(shù)據(jù)數(shù)量;②確定初始對(duì)應(yīng)點(diǎn)集;③去除錯(cuò)誤對(duì)應(yīng)點(diǎn)對(duì);④坐標(biāo)變換求解。這4個(gè)步驟中求最近點(diǎn)集耗費(fèi)的時(shí)間較多[20]。本文首先在目標(biāo)點(diǎn)云中尋找若干特征點(diǎn)，采用kd-tree對(duì)數(shù)據(jù)最近鄰搜索以加快對(duì)應(yīng)點(diǎn)查找速度，從而為配準(zhǔn)節(jié)省一定的時(shí)間;然后根據(jù)歐氏距離選擇合適的初值減少匹配誤差。

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

坐標(biāo)系旋轉(zhuǎn)變換原理如圖3所示。設(shè)目標(biāo)點(diǎn)集[Xt]里某一點(diǎn)在[XOY]坐標(biāo)系下的坐標(biāo)為[（x，y）]，直角坐標(biāo)系旋轉(zhuǎn)[θ]角度后在[XOY]坐標(biāo)系下的坐標(biāo)為[（x1，y1）]，通過(guò)點(diǎn)[（x，y）]和旋轉(zhuǎn)角度可得到[x1]、[y1]的值。

3 實(shí)驗(yàn)結(jié)果及分析

本文基于Windows7系統(tǒng)進(jìn)行實(shí)驗(yàn)平臺(tái)搭建，首先在Windows下安裝VMware-workstation并在虛擬機(jī)VMWare上運(yùn)行Ubuntu 14.04，然后在Ubuntu 14.04下安裝一些必要的環(huán)境工具，如CMAKE、QT、VTK、boost庫(kù)等，最后安裝PCL 1.8.1、Microsoft Visual Studio 2013。仿真實(shí)驗(yàn)主要利用C與C++語(yǔ)言，結(jié)合PCL庫(kù)，在虛擬機(jī)環(huán)境下利用Microsoft Visual Studio 2013開發(fā)平臺(tái)進(jìn)行編程開發(fā)實(shí)現(xiàn)。

首先濾除桌子點(diǎn)云數(shù)據(jù)中的噪聲點(diǎn)，如圖4所示。圖4（a）中初始點(diǎn)云共有460 400個(gè)數(shù)據(jù)，圖4（b）中經(jīng)過(guò)去噪后的點(diǎn)云共有451 410個(gè)數(shù)據(jù)，圖4（c）為被去掉的噪聲點(diǎn)云，共8 990 個(gè)數(shù)據(jù)。

然后對(duì)濾除噪聲數(shù)據(jù)的點(diǎn)云進(jìn)行精簡(jiǎn)化處理，在保留點(diǎn)云數(shù)據(jù)特征信息的前提下，對(duì)過(guò)密的點(diǎn)云數(shù)據(jù)進(jìn)行精簡(jiǎn)，去除大量冗余數(shù)據(jù)，如圖5所示。圖5（a）中白色為初始點(diǎn)云共451 410個(gè)數(shù)據(jù)，綠色為經(jīng)過(guò)精簡(jiǎn)后的點(diǎn)云共 ?36 993個(gè)數(shù)據(jù)，雖然只保留了原來(lái)數(shù)據(jù)的1/12，但從圖5（b）中可以看出，點(diǎn)云的邊緣和特征信息得到很好的保留。最后對(duì)精簡(jiǎn)后的數(shù)據(jù)進(jìn)行配準(zhǔn)處理，如圖6所示。圖6中白色點(diǎn)云為原始點(diǎn)云，綠色點(diǎn)云為經(jīng)過(guò)一定轉(zhuǎn)換后的目標(biāo)點(diǎn)云，紅色為配準(zhǔn)后的點(diǎn)云。經(jīng)過(guò)24次迭代后完成配準(zhǔn)，誤差值達(dá)到最?。ㄒ姺舛蕡D）。

本文還對(duì)不同數(shù)據(jù)量的點(diǎn)云進(jìn)行配準(zhǔn)比較。圖7、圖8、圖9分別是對(duì)bunny、horse、dragon數(shù)據(jù)的配準(zhǔn)。表1為以上數(shù)據(jù)的配準(zhǔn)結(jié)果。

4 結(jié)語(yǔ)

本文對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行了聚類、去噪和精簡(jiǎn)化處理，并對(duì)精簡(jiǎn)后的數(shù)據(jù)進(jìn)行配準(zhǔn)。通過(guò)上述實(shí)驗(yàn)結(jié)果可知，基于特征點(diǎn)保持的點(diǎn)云精簡(jiǎn)與配準(zhǔn)方法對(duì)于大規(guī)模的點(diǎn)云數(shù)據(jù)去噪和精簡(jiǎn)效果都很好，且減少了配準(zhǔn)時(shí)間。

本文雖然一定程度上提升了配準(zhǔn)速度和精度，但點(diǎn)云配準(zhǔn)算法本身具有一定的復(fù)雜性，使得在配準(zhǔn)數(shù)據(jù)量龐大的點(diǎn)云時(shí)沒有明顯效率優(yōu)勢(shì)，這是下一步工作改進(jìn)方向。

參考文獻(xiàn)：

[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] 楊現(xiàn)輝，王惠南. ICP算法在3D點(diǎn)云配準(zhǔn)中的應(yīng)用研究[J]. 計(jì)算機(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] 陳杰. 散亂點(diǎn)云配準(zhǔn)技術(shù)優(yōu)化研究[D]. 綿陽(yáng)：西南科技大學(xué)，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] 楊輝華，王克，李靈巧，等. 基于自適應(yīng)布谷鳥搜索算法的K-means聚類算法及其應(yīng)用[J]. 計(jì)算機(jī)應(yīng)用，2016，36（8）：2066-2070.

[17] 李仁忠，楊曼，劉陽(yáng)陽(yáng)，等. 一種散亂點(diǎn)云的均勻精簡(jiǎn)算法[J]. 光學(xué)學(xué)報(bào)，2017，37（7）：97-105.

[18] 孫威，黃惠. 機(jī)器人輔助的三維點(diǎn)云自動(dòng)配準(zhǔn)[J]. 集成技術(shù)，2015，4（6）：37-45.

[19] 邱世聰，羅意. 改進(jìn)ICP算法的點(diǎn)云配準(zhǔn)[J]. 河南科技，2017（7）：40-42.

[20] 戴靜蘭，陳志楊，葉修梓. ICP算法在點(diǎn)云配準(zhǔn)中的應(yīng)用[J]. 中國(guó)圖象圖形學(xué)報(bào)，2007（3）：517-521.

（責(zé)任編輯：杜能鋼）