鄭曉璐，潘廣貞，楊 劍，楊小青

（中北大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，山西 太原030051）

0 引 言

為了得到被測(cè)物體的完整數(shù)據(jù)模型，需要對(duì)多次測(cè)量的數(shù)據(jù)進(jìn)行一個(gè)合適的坐標(biāo)變換，將不同視角的點(diǎn)云數(shù)據(jù)變換到統(tǒng)一的坐標(biāo)系內(nèi)進(jìn)行可視化操作，這就是點(diǎn)云的配準(zhǔn)［1－4］。

Besl等提出了一種基于自由形態(tài)曲面的高層次配準(zhǔn)方法［5］，即 為 經(jīng) 典 的 迭 代 最 近 點(diǎn) （iterative closest point，ICP）算法。首先根據(jù)一定的準(zhǔn)則確立對(duì)應(yīng)點(diǎn)集P與Q，其中對(duì)應(yīng)點(diǎn)對(duì)的個(gè)數(shù)為n。然后通過(guò)最小二乘法迭代計(jì)算最優(yōu)的坐標(biāo)變換，即旋轉(zhuǎn)矩陣和平移矢量t，使得誤差函數(shù)最??；隨后DAI提出了一種使用曲率特征點(diǎn)和K－D 樹(shù)尋找最近點(diǎn)的方法［6］。然而該些算法對(duì)點(diǎn)云沒(méi)有進(jìn)行預(yù)處理。之后國(guó)內(nèi)外的許多學(xué)者對(duì)ICP進(jìn)行了不同程度的研究和改進(jìn)。隨著三維掃描設(shè)備精度的提高，數(shù)據(jù)規(guī)模和配準(zhǔn)精度也在提高，經(jīng)典的ICP算法不能滿足實(shí)時(shí)性的需求，因此本文在對(duì)各種ICP算法進(jìn)行研究后，提出了一種基于Hausdorff距離處理點(diǎn)云的ICP 算法。在獲得大量點(diǎn)云數(shù)據(jù)后，以數(shù)據(jù)點(diǎn)主曲率和Hausdorff距離［7］為依據(jù)，利用正態(tài)分布圖將點(diǎn)云分為關(guān)鍵點(diǎn)和非關(guān)鍵點(diǎn)，關(guān)鍵點(diǎn)充分保留了點(diǎn)云的幾何特征，用來(lái)進(jìn)行配準(zhǔn)，而非關(guān)鍵點(diǎn)作為幾何特征不明顯的點(diǎn)，為提高算法效率不予以配準(zhǔn)。采用K－D 樹(shù)［8］加速查找，利用最小二乘迭代計(jì)算最優(yōu)的坐標(biāo)變換，完成點(diǎn)云的配準(zhǔn)。數(shù)據(jù)規(guī)模巨大的點(diǎn)云配準(zhǔn)精度問(wèn)題由此得到解決。

1 點(diǎn)云預(yù)處理

1.1 曲率計(jì)算

點(diǎn)云的曲率［9］是描述點(diǎn)云曲面幾何特征的主要數(shù)學(xué)手段，曲率是在連續(xù)且二階可導(dǎo)的曲面上定義的，沒(méi)有拓?fù)浣Y(jié)構(gòu)，因此離散的三維點(diǎn)云不能直接計(jì)算曲率。在局部坐標(biāo)系內(nèi)擬合一張連續(xù)曲面來(lái)計(jì)算各點(diǎn)的曲率，常用到的曲率分別有高斯曲率、平均曲率和主曲率。

設(shè)（d）＝du：dv 為曲面S：r＝r（u：v）在P 點(diǎn)處的主方向，沿主方向的主曲率為Kn，則Kn滿足

即Kn是二次方程的根，也就是方程K2n－2 HKn＋K ＝0的根

則曲面S 的高斯曲率為

則曲面S 的平均曲率為

則主曲率

1.2 關(guān)鍵點(diǎn)選取

Hausdorff距離［10］是研究分形空間的一個(gè)重要的基本概念，是描述兩組點(diǎn)集之間相似程度的一種度量，它是兩個(gè)點(diǎn)集之間距離的一種定義形式：假設(shè)有兩組集合A ＝｛a1，a2，…ap｝，B ＝｛b1，b2，…bq｝，則A，B 兩點(diǎn)集之間Hausdorff距離定義為

其中，d（A，B）和d（B，A）分別表示集合A 到集合B 和集合B 到集合A 的單向Hausdorff距離，分別定義如下

其中， · 表示某種距離范數(shù)。

通過(guò)計(jì)算點(diǎn)與其鄰域之內(nèi)點(diǎn)之間Hausdorff距離作為依據(jù)，將點(diǎn)集P 分為關(guān)鍵點(diǎn)P′和非關(guān)鍵點(diǎn)P″（P′∪P″＝P且P′∩P″＝Φ）。關(guān)鍵點(diǎn)P′指幾何特征比較明顯，對(duì)點(diǎn)云配準(zhǔn)起至關(guān)重要的點(diǎn)。非關(guān)鍵點(diǎn)P″指幾何特征不明顯，配準(zhǔn)時(shí)可以忽略的點(diǎn)。對(duì)于任意點(diǎn)M 和它的鄰近點(diǎn)N ，其主曲率分別為k1，k2和。點(diǎn)M 和N 之間的曲率差別可以看作是｛k1，k2｝和｛｝之間的差別。我們可以通過(guò)一個(gè)相對(duì)度量H 來(lái)衡量Hausdorff距離

當(dāng)分母接近0時(shí)，誤差較大。于是，我們引進(jìn)臨界值ε。當(dāng) ki＋＜ε 時(shí)， ki＋應(yīng)該轉(zhuǎn)換為，用來(lái)防止誤差較大。

M 點(diǎn)的Hausdorff距離可定義為：HM＝max（H1，H2，H3，…，Hk）。其中：H1，H2，H3，…Hk為點(diǎn)M 與其鄰域內(nèi)k個(gè)鄰近點(diǎn)的Hausdorff距離值。HM可以反映出M 點(diǎn)曲率的變化情況，對(duì)曲率變化大的區(qū)域保留足夠多的特征點(diǎn)，用來(lái)突出模型的曲面特征，而在曲率變化小的區(qū)域保留少量的點(diǎn)，所有保留的點(diǎn)即為關(guān)鍵點(diǎn)。即當(dāng)HM較大時(shí)，M 處的幾何特征比較明顯。我們采用HM值的正態(tài)分布圖來(lái)獲取點(diǎn)云的關(guān)鍵點(diǎn)。因?yàn)檎龖B(tài)分布是自然界中一種常見(jiàn)的分布，存在于自然現(xiàn)象、生產(chǎn)、生活及科學(xué)技術(shù)等領(lǐng)域，我們繪制出點(diǎn)集P 的H 值正態(tài)分布圖，模型大致如圖1所示，橫坐標(biāo)是HM，縱坐標(biāo)是在值為HM的點(diǎn)云個(gè)數(shù)n，在正態(tài)分布圖中找到值H0使得小于H0的點(diǎn) （圖中陰影部分）占點(diǎn)總數(shù)的20%，即為非關(guān)鍵點(diǎn)，剩余80%為關(guān)鍵點(diǎn) （經(jīng)實(shí)驗(yàn)驗(yàn)證，28比例的劃分效果比較理想）。關(guān)鍵點(diǎn)非關(guān)鍵點(diǎn)的劃分使我們對(duì)點(diǎn)集P 進(jìn)行了預(yù)處理，找出了集合特征明顯的特征點(diǎn)。然后對(duì)幾何特征明顯的點(diǎn)進(jìn)行配準(zhǔn)，一方面節(jié)省了時(shí)間，另一方面使配準(zhǔn)更具有針對(duì)性。我們?cè)诮酉聛?lái)的ICP配準(zhǔn)時(shí)利用的就是這些幾何特征明顯的關(guān)鍵點(diǎn)，用來(lái)調(diào)高配準(zhǔn)的精確度。

圖1 點(diǎn)云正態(tài)分布

點(diǎn)集預(yù)處理算法流程說(shuō)明如下：

步驟1 計(jì)算出集合P 中所有點(diǎn)的主曲率，利用式（5）計(jì)算。

步驟2 計(jì)算每個(gè)點(diǎn)及其鄰域點(diǎn)的Hausdorff距離，并取最大值為該點(diǎn)的Hausdorff值，利用式 （8）計(jì)算。

步驟3 將集合P 中所有點(diǎn)的Hausdorff值進(jìn)行統(tǒng)計(jì)，并繪制出HM正態(tài)分布圖。

步驟4 根據(jù)上文介紹的分類方法，利用正態(tài)分布圖H 值的分布情況將點(diǎn)云分為關(guān)鍵點(diǎn)P′和非關(guān)鍵點(diǎn)P″。

步驟5 完成點(diǎn)云的預(yù)處理。

2 改進(jìn)的ICP算法

對(duì)兩個(gè)三維點(diǎn)集P′和Q 進(jìn)行ICP配準(zhǔn)，步驟如下：

步驟1 利用k－d tree尋找P′中每一個(gè)點(diǎn)在Q 點(diǎn)集中對(duì)應(yīng)的最近點(diǎn)。

步驟2 求得上述對(duì)應(yīng)點(diǎn)對(duì)平均距離最小的剛體變換，即旋轉(zhuǎn)變換向量qR和平移變換向量qT以及誤差。

步驟3 對(duì)于P′使用上步求得的變換向量得到新的變換點(diǎn)集。

步驟4 當(dāng)新的變換點(diǎn)集與參考點(diǎn)集Q 滿足式 （9）的目標(biāo)函數(shù)時(shí)，停止計(jì)算。否則跳轉(zhuǎn)到步驟2 一直迭代，直到達(dá)到目標(biāo)函數(shù)的要求。

步驟5 完成點(diǎn)云的配準(zhǔn)。

本文采用了基于Hausdorff距離改進(jìn)的ICP 算法，目的在于解決ICP算法的高精度要求。利用曲率能表示鄰域形狀變化的特性，引入Hausdorff距離的點(diǎn)集定義，對(duì)點(diǎn)云進(jìn)行預(yù)處理，使得點(diǎn)云的配準(zhǔn)更具有針對(duì)性。高精確度的優(yōu)勢(shì)使得該算法可應(yīng)用于海量數(shù)據(jù)的逆向工程，本文的算法流程如圖2所示。

圖2 本文算法流程

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

為了驗(yàn)證本文算法的正確性和有效性，以經(jīng)典算法作為對(duì)比，對(duì)三維模型進(jìn)行了仿真實(shí)驗(yàn)。本文實(shí)驗(yàn)的硬件環(huán)境為Intel Xeon 的處理器，6.00G 內(nèi)存的64位的win7操作系統(tǒng)。軟件環(huán)境為PCL 點(diǎn)云庫(kù)、Visual Studio2010、cmake3.0、華碩Xtion Pro Live。實(shí)驗(yàn)數(shù)據(jù)均取自PCL官網(wǎng)提供的pcd格式文件。

3.1 配準(zhǔn)結(jié)果

點(diǎn)云bunny的點(diǎn)數(shù)分別為20480、18566，下面分別給出了經(jīng)典ICP算法和本文ICP 算法的配準(zhǔn)結(jié)果。圖3 （a）為兩片未配準(zhǔn)的點(diǎn)云，淺灰色為源點(diǎn)云，深灰色為目標(biāo)點(diǎn)云。圖3 （b）為經(jīng)典ICP算法的配準(zhǔn)圖。圖3 （c）為本文改進(jìn)的ICP算法的配準(zhǔn)圖。圖4為經(jīng)過(guò)30次迭代計(jì)算后的自由剛體變換。對(duì)比圖3 （b）和圖3 （c），圖3 （c）中 淺灰部分深灰部分距離小于圖3 （b）對(duì)應(yīng)淺灰深灰點(diǎn)云之間的距離，可以得出圖3 （c）的配準(zhǔn)精度得到進(jìn)一步提高。

圖3 bunny實(shí)驗(yàn)配準(zhǔn)

圖4 bunny最優(yōu)剛體變換

點(diǎn)云robot的點(diǎn)數(shù)分別為20991、19352，下面圖分別給出了經(jīng)典ICP算法和本文ICP算法的配準(zhǔn)結(jié)果。圖5 （a）為兩片未配準(zhǔn)的點(diǎn)云，圖5 （b）為經(jīng)典ICP算法的配準(zhǔn)圖。圖5 （c）為本文改進(jìn)的ICP算法的配準(zhǔn)圖。圖6為經(jīng)過(guò)30次迭代計(jì)算后的自由剛體變換。對(duì)比圖5 （b）和圖5 （c），圖5 （c）中淺灰部分深灰部分距離小于圖5 （b）對(duì)應(yīng)淺灰深灰點(diǎn)云之間的距離，可以得出圖5 （c）的配準(zhǔn)精度有了很大的提高。

3.2 結(jié)果分析

圖5 robot實(shí)驗(yàn)配準(zhǔn)

圖6 robot最優(yōu)剛體變換

實(shí)驗(yàn)的配準(zhǔn)精度我們可以用配準(zhǔn)誤差來(lái)衡量。表1列出了經(jīng)典ICP算法和本文改進(jìn)算法的時(shí)間和精度，分別對(duì)bunny、robot、horse、dragon進(jìn)行了實(shí)驗(yàn)。從表數(shù)據(jù)分析來(lái)看，bunny在時(shí)間上由3.842s縮短到了2.957s，配準(zhǔn)精度由0.3929mm 提高到了0.1604 mm。我們可以得出，在配準(zhǔn)時(shí)間幾乎相近的情況下利用基于Hausdorff距離的改進(jìn)算法能有效的找出均勻的關(guān)鍵點(diǎn)，實(shí)驗(yàn)精度有了很大的提高，取得了令人滿意的效果。

表1 點(diǎn)云配準(zhǔn)比較

由圖7可以看出本文改進(jìn)算法的配準(zhǔn)誤差明顯低于經(jīng)典算法，并且隨著數(shù)據(jù)量的增大配準(zhǔn)誤差越低。改進(jìn)算法配準(zhǔn)在精度上有明顯的優(yōu)勢(shì)，并且隨著數(shù)據(jù)量的增大配準(zhǔn)精度的優(yōu)勢(shì)越明顯。因此該配準(zhǔn)算法可以應(yīng)用在對(duì)配準(zhǔn)精度要求較高，點(diǎn)云凹凸性較明顯的物體上。

4 結(jié)束語(yǔ)

圖7 改進(jìn)算法與經(jīng)典算法的配準(zhǔn)誤差比較

本文在研究了各種ICP 算法后，針對(duì)點(diǎn)云數(shù)據(jù)量大、對(duì)配準(zhǔn)精度要求較高的情況，提出了一種基于Hausdorff距離改進(jìn)的算法。采用三維點(diǎn)云擬合曲面的主曲率和點(diǎn)鄰域內(nèi)Hausdorff距離相結(jié)合的方法，利用正態(tài)分布圖選擇出點(diǎn)云幾何特征明顯的關(guān)鍵點(diǎn)。然后采用K－D 樹(shù)加速查找，通過(guò)最小二乘迭代進(jìn)行點(diǎn)云ICP 配準(zhǔn)。實(shí)驗(yàn)結(jié)果表明，本文提出的算法提高了點(diǎn)云配準(zhǔn)的精確度。在實(shí)際應(yīng)用中，本算法適合對(duì)配準(zhǔn)精度要求較高，點(diǎn)云凹凸性比較明顯的物體配準(zhǔn)上。

［1］DUN WZ，HUN G，HONG LX，et al.The research of optical 3D measuring precision influencing factor in reverse engineering ［J］.Applied Mechanics and Materials，2010，33：157－162.

［2］Hacene A，Mekki A.Bio－CAD reverse engineering of freeform surfaces by planar contours［J］.Computer－Aided Design＆Applications，2011，8 （1）：37－42.

［3］XU Gang，WANG Chunyan.Based on vitural reality modeling language medical volume data reconstruction ［J］.Automation and Instrumentation，2012 （4）：38－40 （in Chinese）. ［徐剛，王春燕.基于虛擬現(xiàn)實(shí)建模語(yǔ)言的醫(yī)學(xué)體數(shù)據(jù)三維重建研究［J］.自動(dòng)化與儀器儀表，2012 （4）：38－40.］

［4］Karen RS，Alexandra SC.Reliability of photogrammetry in the evaluation of postural aspect of individuals with structural scoliosis［J］.Journal of Bodywork and Movement Therapies，2011，16 （2）：210－216.

［5］LI Shifei，WANG Ping，SHEN Zhenkang.A survey of iterative closest point algorithm ［J］.Signal Processing，2009，25（10）：1582－1588 （in Chinese）.［李世飛，王平，沈振康.迭代最近點(diǎn)算法研究進(jìn)展 ［J］.信號(hào)處理，2009，25 （10）：1582－1588.］

［6］YANG Xianhui，WANG Huinan.Application research of ICP algorithm in 3Dpoint cloud alignment［J］.Computer Simulation，2010，27 （8）：235－288 （in Chinese）. ［楊現(xiàn)輝，王惠南.ICP算法在3D點(diǎn)云配準(zhǔn)中的應(yīng)用研究 ［J］.計(jì)算機(jī)仿真，2010，27 （8）：235－288.］

［7］ZHU Yu，KANG Baosheng，LI Hong’an，et al.An improved method to streamline point cloud ［J］.Computer Application，2012，32 （2）：521－524 （in Chinese）. ［朱煜，康寶生，李洪安，等.一種改進(jìn)的點(diǎn)云精簡(jiǎn)方法 ［J］.計(jì)算機(jī)應(yīng)用，2012，32 （2）：521－524.］

［8］YU Xiaogao，YU Xiaopeng.Based on angular similarity K－nearest neighbor search algorithm ［J］.Application Research of Computers，2009，26 （9）：239－256 （in Chinese）. ［余小高，余小鵬.一種基于角相似性的K－最近鄰搜索算法 ［J］.計(jì)算機(jī)應(yīng)用研究，2009，26 （9）：239－256.］

［9］Bu Yanlong，Peng Shuangchun，Wangnan，et al.Constriction of mutual information based matching－suitable features for SAR image aided navigation ［C］／／International Conference on Environmental Science and Information Application Technology，2009.

［10］BAI Yanbing.Free－form surfaces Haudorff diatance approximation calculation to freedom of curves and surfaces［D］.Beijing：Tsinghua University，2011 （in Chinese）.［白彥冰.自由曲面到自由曲線曲面的Hausdorff距離近似值的計(jì)算 ［D］.北京：清華大學(xué)，2011.］