楊 軍，張 瑤，黃 亮

1.蘭州交通大學(xué) 電子與信息工程學(xué)院，蘭州 730070

2.蘭州交通大學(xué) 自動(dòng)化與電氣工程學(xué)院，蘭州 730070

1 引言

配準(zhǔn)技術(shù)是當(dāng)今數(shù)字化檢測(cè)領(lǐng)域的一項(xiàng)關(guān)鍵技術(shù)，最早出現(xiàn)于醫(yī)療診斷和圖像處理領(lǐng)域[1]，目前已廣泛應(yīng)用于逆向工程[2]、虛擬現(xiàn)實(shí)[3]、機(jī)器人[4]和柔性裝配[5]等領(lǐng)域。

模型配準(zhǔn)是指通過(guò)在源模型和目標(biāo)模型之間構(gòu)造一個(gè)三維空間變換，使源模型在此變換作用下能夠最大限度地和目標(biāo)模型重合。目前主要有三類(lèi)方法：第一類(lèi)是基于標(biāo)記的配準(zhǔn)方法，通過(guò)確定兩模型中對(duì)應(yīng)的特征點(diǎn)，并由對(duì)應(yīng)特征點(diǎn)計(jì)算目標(biāo)模型和源模型之間的空間變換。該方法主要應(yīng)用于醫(yī)學(xué)領(lǐng)域。第二類(lèi)是基于表面的配準(zhǔn)方法，在模型表面上定義并計(jì)算突出的特征，根據(jù)模型表面的共同特征在重疊區(qū)域內(nèi)搜索兩個(gè)表面之間的唯一匹配模式。該方法通常應(yīng)用于工業(yè)領(lǐng)域的模型配準(zhǔn)。第三類(lèi)是基于體素相似性的配準(zhǔn)方法，不需要對(duì)像素做預(yù)處理（去噪或者分割），直接作用于圖像，但該方法計(jì)算量太大，很少用于三維模型配準(zhǔn)。模型配準(zhǔn)一般分為兩步：初始配準(zhǔn)和精確配準(zhǔn)。初始配準(zhǔn)是通過(guò)縮小兩模型旋轉(zhuǎn)和位移誤差將兩模型大致調(diào)整到同一位置，為迭代最近點(diǎn)（iterative closest point，ICP）配準(zhǔn)提供最優(yōu)初始值；精確配準(zhǔn)則是利用初始匹配值不斷地執(zhí)行迭代變換，并使迭代收斂到全局最優(yōu)的配準(zhǔn)結(jié)果。

1992年，Besl和Mckay提出了ICP算法[6]，由于其操作簡(jiǎn)單和良好的配準(zhǔn)效果而廣泛應(yīng)用于各種領(lǐng)域的配準(zhǔn)問(wèn)題，然而ICP算法對(duì)于初始值的敏感性極高且運(yùn)行效率低。針對(duì)經(jīng)典ICP算法的缺點(diǎn)，中外許多學(xué)者對(duì)尋找和選取對(duì)應(yīng)點(diǎn)對(duì)設(shè)計(jì)了各種算法，以保證能夠得到最優(yōu)的初始匹配點(diǎn)對(duì)，提高ICP算法的速度和精確度。文獻(xiàn)[7]結(jié)合點(diǎn)集增強(qiáng)技術(shù)與經(jīng)典ICP算法，將一些新的采樣點(diǎn)加入到已有的點(diǎn)集中并作為標(biāo)記點(diǎn)，用于解決由多傳感器掃描獲取的三維點(diǎn)云數(shù)據(jù)的坐標(biāo)融合問(wèn)題，提高了配準(zhǔn)的準(zhǔn)確度和魯棒性，然而該算法太依賴(lài)新加入的標(biāo)記點(diǎn)，而標(biāo)記點(diǎn)對(duì)應(yīng)位置準(zhǔn)確與否直接影響配準(zhǔn)結(jié)果。文獻(xiàn)[8]利用模型表面曲率變化和法線(xiàn)矢量之間的夾角來(lái)約束對(duì)應(yīng)點(diǎn)對(duì)，這種方法雖然提高了配準(zhǔn)效率和準(zhǔn)確度，但仍然需要用戶(hù)給定初始配準(zhǔn)點(diǎn)。文獻(xiàn)[9]除了用模型表面一點(diǎn)和其鄰近點(diǎn)組成的切平面與此點(diǎn)處法向量的夾角閾值約束對(duì)應(yīng)點(diǎn)對(duì)外，還加入了點(diǎn)云數(shù)據(jù)的對(duì)應(yīng)點(diǎn)對(duì)間的歐氏距離閾值來(lái)選取最合適的對(duì)應(yīng)點(diǎn)對(duì)，這種方法對(duì)于小型零件檢測(cè)效果很好，但當(dāng)點(diǎn)云數(shù)據(jù)規(guī)模超過(guò)8 000點(diǎn)之后，其精確度不如經(jīng)典ICP算法。文獻(xiàn)[10]認(rèn)為錯(cuò)誤的對(duì)應(yīng)點(diǎn)對(duì)對(duì)配準(zhǔn)結(jié)果影響較大，于是將圖像信息融合到改進(jìn)的ICP算法中，用SIFT特征點(diǎn)減少錯(cuò)誤對(duì)應(yīng)點(diǎn)對(duì)，提高了配準(zhǔn)的準(zhǔn)確度和效率，但此方法除了必須的點(diǎn)云外還需要模型在真實(shí)環(huán)境中的二維圖像信息。文獻(xiàn)[11]提出了基于點(diǎn)云邊界特征點(diǎn)的改進(jìn)ICP算法。首先，對(duì)點(diǎn)云最小包圍盒進(jìn)行三維空間劃分，運(yùn)用邊界種子網(wǎng)格識(shí)別及生長(zhǎng)算法，從點(diǎn)云邊界提取特征點(diǎn)，運(yùn)用奇異值矩陣分解法求出點(diǎn)云的變換矩陣，得到初始配準(zhǔn)結(jié)果。其次，對(duì)點(diǎn)云對(duì)應(yīng)點(diǎn)賦予權(quán)重，剔除權(quán)重大于閾值的點(diǎn)，通過(guò)對(duì)目標(biāo)函數(shù)引入M-估計(jì)，剔除異常點(diǎn)。最后，在初始配準(zhǔn)的基礎(chǔ)上，運(yùn)用改進(jìn)的ICP方法精確配準(zhǔn)。算法效率提高了，但準(zhǔn)確度并不是很高。

常用的初始配準(zhǔn)方法有重心重合法[12]、標(biāo)簽法[13]、提取特征法[14-15]。重心重合法計(jì)算出兩模型的重心坐標(biāo)，然后將重心重合，這種方法只能縮小平移錯(cuò)位而無(wú)法縮小旋轉(zhuǎn)錯(cuò)位；標(biāo)簽法在測(cè)量時(shí)人為地貼上一些特征點(diǎn)，然后利用這些特征點(diǎn)進(jìn)行定位，根據(jù)這些對(duì)應(yīng)的特征點(diǎn)將兩模型大致調(diào)整到同一位置，這種方式仍然是依賴(lài)于測(cè)量和儀器的；提取特征法，如提取平面特征、輪廓曲線(xiàn)等，通過(guò)將模型表面特征相同部分重合以達(dá)到初始配準(zhǔn)的目的，但這種方式要求點(diǎn)云有比較明顯的突出特征。

本文針對(duì)ICP算法對(duì)于初始值的敏感性以及整體與部分模型的配準(zhǔn)精確度兩方面進(jìn)行了改進(jìn)。首先，采用主成分分析法（principal component analysis，PCA）對(duì)模型進(jìn)行初始配準(zhǔn)，使用三維縮放變換將兩模型調(diào)整為同等大小。然后，用KD-tree進(jìn)行最近點(diǎn)搜索提高搜索速度。由于本文主要針對(duì)整體與部分模型間的配準(zhǔn)，對(duì)配準(zhǔn)精度要求更高，故利用自適應(yīng)最優(yōu)閾值優(yōu)化ICP算法，提高模型配準(zhǔn)的準(zhǔn)確度。最后，為了防止在上下或前后顛倒的情況下進(jìn)行三維模型重合度檢測(cè)，做最后的反轉(zhuǎn)調(diào)整。

2 模型的初始配準(zhǔn)

在運(yùn)用ICP算法對(duì)模型進(jìn)行精確配準(zhǔn)之前，兩模型的點(diǎn)集有可能在不同的坐標(biāo)系下，也有可能處于同一坐標(biāo)系的任意位置，那么點(diǎn)集的迭代初始值就不能滿(mǎn)足精確配準(zhǔn)的要求，因此需要通過(guò)搜索最近點(diǎn)，或者使用三維幾何特征來(lái)計(jì)算兩組點(diǎn)集的匹配條件。然而，算法的復(fù)雜度和計(jì)算量會(huì)劇增，影響執(zhí)行效率。因此，在精確配準(zhǔn)前先進(jìn)行兩模型點(diǎn)集間的初始配準(zhǔn)，為精確配準(zhǔn)提供初始值以提高最終的配準(zhǔn)精確度和效率。

文中使用了一種全局配準(zhǔn)方法。由于兩模型點(diǎn)集的主軸形狀相似度很高，可以通過(guò)計(jì)算兩組點(diǎn)集的主軸以得到點(diǎn)集之間的剛體變換矩陣，此方法稱(chēng)為主成分分析法。給定一組點(diǎn)集P={P1,P2,…,Pn},計(jì)算其均值和協(xié)方差矩陣cov,對(duì)矩陣cov進(jìn)行特征向量分解，得到的正交特征向量作為點(diǎn)集P的三坐標(biāo)軸X、Y、Z,以均值為坐標(biāo)系原點(diǎn)，建立這組點(diǎn)集的坐標(biāo)系?？梢杂猛瑯拥姆绞教幚碓茨Ｐ秃湍繕?biāo)模型的點(diǎn)集，并將兩模型的坐標(biāo)系進(jìn)行位置調(diào)整，以滿(mǎn)足初始配準(zhǔn)的要求。

然而，本文并沒(méi)有將兩模型新的坐標(biāo)系調(diào)整至同一位置，而是先將兩模型進(jìn)行三維縮放調(diào)整為同等大小。

給定包含n個(gè)采樣點(diǎn)的源模型S={s1,s2,…,sn}和包含m個(gè)采樣點(diǎn)的目標(biāo)模型T={t1,t2,…,tm},用矩陣（1）和（2）分別表示源模型和目標(biāo)模型點(diǎn)云數(shù)據(jù)的坐標(biāo)。其中，下標(biāo)s和t分別表示源模型和目標(biāo)模型。

分別計(jì)算源模型和目標(biāo)模型的點(diǎn)集在X、Y、Z坐標(biāo)軸上的平均值分別表示點(diǎn)在X軸、Y軸、Z軸上的坐標(biāo)。

分別計(jì)算源模型和目標(biāo)模型所有點(diǎn)坐標(biāo)值xi、yi、zi和相應(yīng)均值之間的差值，如式（5）和（6）所示。

用Bs和Bt分別表示經(jīng)過(guò)PCA分析后形成的新坐標(biāo)系下源模型和目標(biāo)模型各點(diǎn)的新的坐標(biāo)矩陣。

分別計(jì)算源模型和目標(biāo)模型每一列的最大值和最 小 值 max(Bs)、 min(Bs)、 max(Bt)、 min(Bt),并 計(jì) 算最大值和最小值之間的差值Ds、Dt。

構(gòu)造新的矩陣D,其中元素d是矩陣Ds和Dt對(duì)應(yīng)元素相除得到的一行三列矩陣，d(1,1)、d(1,2)、d(1,3)分別表示矩陣d的第一行一列、一行二列和一行三列元素。

D即為源模型到目標(biāo)模型的縮放矩陣，因此模型的縮放調(diào)整由下式完成：

再將源模型依次繞X軸、Y軸、Z軸、XOY面、XOZ面、YOZ面反轉(zhuǎn)并求出每次反轉(zhuǎn)后的誤差，選取誤差最小的反轉(zhuǎn)方式來(lái)調(diào)整源模型的方向。這樣做既節(jié)省時(shí)間又不影響結(jié)果。

3 模型的精確配準(zhǔn)

初始配準(zhǔn)只是將源模型和目標(biāo)模型縮放至同等大小，并調(diào)整至方向基本一致，其精度太低，遠(yuǎn)不能達(dá)到完全配準(zhǔn)的要求。為了提高配準(zhǔn)精度，還需在初始配準(zhǔn)的基礎(chǔ)上進(jìn)行精確配準(zhǔn)。本文采用ICP算法進(jìn)行精確配準(zhǔn)，其關(guān)鍵是對(duì)應(yīng)點(diǎn)集配準(zhǔn)（corresponding point set registration）。

對(duì)應(yīng)點(diǎn)集配準(zhǔn)算法的目的是利用最小二乘法計(jì)算模型間最優(yōu)的坐標(biāo)變換矩陣。對(duì)兩個(gè)點(diǎn)集，可以采用單位四元數(shù)法[1]得到它們之間的變換矩陣。

用S和T分別表示源模型和目標(biāo)模型的點(diǎn)云數(shù)據(jù)，它們應(yīng)滿(mǎn)足以下條件：

（1）T中有m個(gè)點(diǎn)和S中有n個(gè)點(diǎn)，且m=n;

（2）對(duì)于T中的任意點(diǎn)ti都對(duì)應(yīng)于S中具有相同下標(biāo)的si,即ti=(sisi、ti分別表示源模型和目標(biāo)模型上的點(diǎn)）。

設(shè)旋轉(zhuǎn)變換向量為單位四元數(shù)qrotat=[q0q1q2q3]T,其中q0≥0,并且,則可以得到3×3旋轉(zhuǎn)變換矩陣R(qrotat)。設(shè)平移變換向量為qtrans=[q4q5q6]T,則求解對(duì)應(yīng)點(diǎn)集間的最佳坐標(biāo)變換向量問(wèn)題可轉(zhuǎn)化為求解qrotat和qtrans使得函數(shù)f(qtrans,qrotat)最小化的問(wèn)題：

算法流程如下：

步驟1給定源模型和目標(biāo)模型的對(duì)應(yīng)點(diǎn)集S和T,計(jì)算目標(biāo)模型點(diǎn)集T的重心μT和源模型點(diǎn)集S的重心μS:

步驟2由點(diǎn)集T和S構(gòu)造協(xié)方差矩陣：

步驟3由協(xié)方差矩陣構(gòu)造4×4對(duì)稱(chēng)矩陣：

其中，I3是 3×3單位矩陣；tr(ΣT,S)是矩陣 ΣT,S的跡，Δ=[A23A31A12]T,Ai,j是ΣT,S的反對(duì)稱(chēng)矩陣,Ai,j=(ΣT,S-ΣTT,S)i,j。

步驟4計(jì)算Q(ΣT,S)的特征值和特征向量，其最大特征值對(duì)應(yīng)的特征向量即為最佳旋轉(zhuǎn)向量qrotat=[q0q1q2q3]T,最佳旋轉(zhuǎn)矩陣R(qrotat)為：

步驟5計(jì)算最佳平移向量為：

步驟6利用已得到的平移向量和旋轉(zhuǎn)向量，計(jì)算dl=f(qtrans,qrotat),即迭代后的最小誤差。

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

ICP算法是目前應(yīng)用最普遍的配準(zhǔn)方法，其配準(zhǔn)效果良好，但是算法本身計(jì)算效率不高。而KD-tree[12,16]是一種分割k維數(shù)據(jù)空間的數(shù)據(jù)結(jié)構(gòu)，主要應(yīng)用于多維空間關(guān)鍵數(shù)據(jù)的搜索（如本文中的最近鄰搜索），并對(duì)搜索空間進(jìn)行層次劃分，具有搜索速度快的優(yōu)點(diǎn)，故本文采用KD-tree搜索最近點(diǎn)來(lái)提高搜索效率。此外，整體與部分模型間的配準(zhǔn)對(duì)于配準(zhǔn)精度的要求更高，故本文采用自適應(yīng)的最優(yōu)閾值來(lái)優(yōu)化迭代結(jié)果，提高了經(jīng)典ICP算法的配準(zhǔn)精度。

在兩模型初始配準(zhǔn)之后，不直接執(zhí)行ICP算法，而是給定不同的閾值K，計(jì)算不同閾值時(shí)對(duì)兩模型執(zhí)行ICP算法所對(duì)應(yīng)的配準(zhǔn)誤差，記錄最小誤差所對(duì)應(yīng)的閾值并記為Kbest,用Kbest作為閾值，重新執(zhí)行迭代最近點(diǎn)算法，直至算法收斂。

在執(zhí)行ICP算法之后有可能會(huì)出現(xiàn)模型上下或者前后顛倒的現(xiàn)象，這是由于算法在執(zhí)行過(guò)程中，可能會(huì)出現(xiàn)由于初始配準(zhǔn)的不夠準(zhǔn)確導(dǎo)致執(zhí)行ICP算法時(shí)不能找到正確的對(duì)應(yīng)點(diǎn)對(duì)，故目前通常的做法是在初始配準(zhǔn)后用最小包圍盒的方法進(jìn)行校正。但在實(shí)驗(yàn)中發(fā)現(xiàn)即使在初始配準(zhǔn)后用最小包圍盒進(jìn)行矯正，最終還是可能會(huì)出現(xiàn)這種狀況。

因此，本文算法在執(zhí)行完ICP配準(zhǔn)后，增加了三維目標(biāo)重合度檢測(cè)算法，根據(jù)兩模型重合度再進(jìn)行最后的反轉(zhuǎn)調(diào)整，這里也要用到最小包圍盒。根據(jù)包圍盒立方體的三條邊與三個(gè)坐標(biāo)軸間的位置關(guān)系，包圍盒分為沿坐標(biāo)軸的軸向包圍盒AABB（axisaligned bounding box）和有向包圍盒OBB（oriented bounding box）[17]兩種，如圖1所示。本文選用OBB包圍盒。

Fig.1 Axis-aligned bounding box(left)and oriented bounding box(right)圖1 AABB包圍盒（左）和OBB包圍盒（右）

設(shè)Vs為源模型點(diǎn)云包圍盒體積，Vt為目標(biāo)模型點(diǎn)云包圍盒體積，Vi為源模型點(diǎn)云和目標(biāo)點(diǎn)云包圍盒相交得到的包圍盒的體積，則包圍盒重合系數(shù)為：

如果τ＞thr,thr為設(shè)定閾值，則兩點(diǎn)云模型大致重合。否則兩模型不重合，那么反轉(zhuǎn)坐標(biāo)系的X軸或Y軸，將X軸和Y軸是否反轉(zhuǎn)的4種情況全部測(cè)試完，并且沒(méi)有任何一個(gè)τ大于thr,則說(shuō)明兩模型間差異較大，不能配準(zhǔn)。

算法流程如圖2所示，具體步驟說(shuō)明如下。

步驟1輸入源模型和目標(biāo)模型的點(diǎn)云數(shù)據(jù)。

步驟2經(jīng)過(guò)縮放，使兩模型大小相同，再用矩陣C調(diào)整模型的方向。

步驟3用KD-tree來(lái)搜索目標(biāo)模型最鄰近點(diǎn)為對(duì)應(yīng)點(diǎn)對(duì)，計(jì)算源模型上一點(diǎn)到目標(biāo)模型上對(duì)應(yīng)點(diǎn)之間距離的平均值aver和標(biāo)準(zhǔn)差sde。

步驟4設(shè)變量k,且1≤k≤3。k從1開(kāi)始每隔0.05取一個(gè)值，得到不同的閾值K=k×aver+sde,對(duì)對(duì)應(yīng)點(diǎn)對(duì)進(jìn)行篩選，對(duì)應(yīng)點(diǎn)對(duì)間的距離小于閾值的保留，否則剔除。計(jì)算得到不同閾值K執(zhí)行ICP算法后對(duì)應(yīng)的配準(zhǔn)誤差，記錄最小誤差對(duì)應(yīng)的閾值為Kbest。

步驟5以Kbest為閾值執(zhí)行ICP算法，并計(jì)算每次執(zhí)行ICP算法后的配準(zhǔn)誤差。

步驟6判斷誤差是否收斂，若收斂，則兩模型完成配準(zhǔn)。若不收斂，判斷迭代次數(shù)是否超出預(yù)設(shè)值，如超出，則強(qiáng)制結(jié)束迭代，兩模型無(wú)法完全配準(zhǔn)；如迭代次數(shù)沒(méi)有超出預(yù)設(shè)值，返回步驟4。

Fig.2 Flow chart of improved ICP algorithm圖2 算法流程圖

步驟7ICP算法結(jié)束后，執(zhí)行三維目標(biāo)重合度檢測(cè)算法，分析兩個(gè)目標(biāo)的重合度情況，根據(jù)重合度再進(jìn)行最后的旋轉(zhuǎn)調(diào)整。

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

在基于極點(diǎn)譜植入的初始化過(guò)程中，由于優(yōu)化策略采用了貪婪優(yōu)化算法，從而建立了較好的初始對(duì)應(yīng)關(guān)系。對(duì)已建立的初始對(duì)應(yīng)關(guān)系再通過(guò)貪婪優(yōu)化算法進(jìn)行優(yōu)化，就可得到最終的稀疏對(duì)應(yīng)關(guān)系。

本文算法采用Matlab編程實(shí)現(xiàn)，實(shí)驗(yàn)中迭代次數(shù)預(yù)設(shè)最大值為300，針對(duì)部分模型（與源模型相比，目標(biāo)模型缺少了某一部件）與完整模型進(jìn)行實(shí)驗(yàn)，并將本文算法的誤差與經(jīng)典ICP算法進(jìn)行對(duì)比。

圖3是缺少兩只小臂且沒(méi)有穿衣服的人體模型（綠色）與完整模型（黃色）在只執(zhí)行初始配準(zhǔn)算法后的結(jié)果，可以看出配準(zhǔn)精確度很差，沒(méi)有對(duì)齊。同樣的模型，圖4所示實(shí)驗(yàn)表示只用精確配準(zhǔn)的結(jié)果，配準(zhǔn)效果依然不好。由此可見(jiàn)，如果沒(méi)有初始配準(zhǔn)為ICP算法計(jì)算出一個(gè)最優(yōu)的初始值，則配準(zhǔn)效果較差，這是由于ICP算法對(duì)初始值的敏感性所致。圖5所示為本文算法的配準(zhǔn)結(jié)果和迭代誤差圖，基本完全配準(zhǔn)，最終配準(zhǔn)誤差為4.217×10-5。圖6為缺少一條腿的馬模型（綠色）和完整馬模型（黃色）使用本文算法的配準(zhǔn)結(jié)果和迭代誤差。可以看出，在迭代過(guò)程的初期誤差曲線(xiàn)有曲折，當(dāng)?shù)螖?shù)超過(guò)20次時(shí)，算法收斂，基本達(dá)到完全配準(zhǔn)。最終配準(zhǔn)誤差為11.981×10-5。圖7所示為缺少兩只胳膊的人模型（綠色）與完整模型（黃色）的配準(zhǔn)結(jié)果，此組模型中源模型（綠色）與目標(biāo)模型（黃色）在小腿部分不完全相同，從配準(zhǔn)結(jié)果看小腿部分綠色多而其他部分黃色多，在迭代過(guò)程中不斷地前后調(diào)整導(dǎo)致誤差不停波動(dòng)，最終配準(zhǔn)誤差為14.139×10-5。圖8為缺少一只胳膊且穿衣服的人體模型（綠色）與完整模型（黃色）使用本文算法的配準(zhǔn)結(jié)果。與前三組模型相比，此模型的點(diǎn)云規(guī)模較大，且表面紋理復(fù)雜（因?yàn)橐路陌欛蓿?。可以看出，配?zhǔn)效果良好，但是在模型的腳腿部由于有衣服浮動(dòng)的影響，兩模型有差別，在迭代過(guò)程中不斷地調(diào)整，最終配準(zhǔn)誤差在24.975×10-5附近波動(dòng)收斂。當(dāng)兩模型姿態(tài)完全相同時(shí)，本文算法會(huì)完全配準(zhǔn)，但當(dāng)兩模型姿態(tài)有所區(qū)別時(shí)，本文算法會(huì)在不同的部分不斷調(diào)整迭代直到達(dá)到預(yù)設(shè)迭代值。

Fig.3 Result of using initial registration separately to align point clouds圖3 僅用初始配準(zhǔn)的結(jié)果

Fig.4 Result of using precise registration separately to align point clouds圖4 僅用精確配準(zhǔn)的結(jié)果

Fig.5 Registration result and iterative error of two human models(complete human model vs partial human model lack of two forearms)圖5 完整與部分（缺少兩只小臂）人體模型的配準(zhǔn)結(jié)果與迭代誤差

Fig.6 Registration result and iterative error of horse models(complete horse model vs partial horse model lack of right foreleg)圖6 完整與部分（缺少一條腿）馬模型的配準(zhǔn)結(jié)果與迭代誤差

Fig.7 Registration result and iterative error of human models(complete human model vs partial human model lack of two arms)圖7 完整與部分（缺少兩只胳膊）人體模型的配準(zhǔn)

Fig.8 Registration result and iterative error of two human models with clothes(complete human model vs partial human model lack of right arm)圖8 穿衣服的完整與部分（缺少右臂）人體模型配準(zhǔn)與迭代誤差

本文算法對(duì)完整模型之間的配準(zhǔn)也非常有效。圖9是4組完整模型的配準(zhǔn)結(jié)果，可以看出，配準(zhǔn)效果良好，骨頭、貓、狗、人體模型的最終配準(zhǔn)誤差分別為10.224×10-5、0.380 42×10-5、2.569 8×10-5、6.842 4×10-5。

表1是本文算法和經(jīng)典ICP算法對(duì)不同點(diǎn)云數(shù)目的模型進(jìn)行配準(zhǔn)的誤差對(duì)比。本文算法根據(jù)每個(gè)模型的實(shí)際情況，搜索出最適合的閾值來(lái)篩選出最合適的對(duì)應(yīng)點(diǎn)對(duì)，提高配準(zhǔn)的準(zhǔn)確度。且本文主要針對(duì)整體與部分模型間的配準(zhǔn)，對(duì)配準(zhǔn)精確度要求更高。可以看出，本文算法對(duì)于人和馬模型（整體與部分模型）配準(zhǔn)精確度的提高程度相對(duì)于貓和狗模型（兩個(gè)完整模型）高很多。配準(zhǔn)誤差對(duì)比表明本文算法既能用于源模型是目標(biāo)模型的某些部件這種情況，也適用于兩個(gè)完整模型的配準(zhǔn)，同時(shí)提高了經(jīng)典ICP算法的模型配準(zhǔn)精度。

Fig.9 Registration results of 4 sets of complete models圖9 4組完整模型配準(zhǔn)結(jié)果

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

隨著科技工業(yè)的快速發(fā)展，醫(yī)學(xué)和工業(yè)等領(lǐng)域?qū)Ω鞣N技術(shù)檢測(cè)的精確度要求越來(lái)越高，模型配準(zhǔn)是這些檢測(cè)領(lǐng)域中的基本問(wèn)題。本文提出了加入縮放功能的PCA算法，使用KD-tree搜索鄰近點(diǎn)提高搜索速度，并使用自適應(yīng)最優(yōu)閾值優(yōu)化ICP算法提高其準(zhǔn)確度。此外，還進(jìn)行模型重合度檢測(cè)做最后調(diào)整避免出現(xiàn)模型上下或前后顛倒問(wèn)題。實(shí)驗(yàn)結(jié)果表明本文算法既可以配準(zhǔn)整體與部分模型，也適用于兩個(gè)完整模型間的配準(zhǔn)問(wèn)題，同時(shí)提高了配準(zhǔn)精度和效率。然而，在整體與部分模型的配準(zhǔn)中，目標(biāo)模型經(jīng)常比源模型多一些部件，當(dāng)搜索目標(biāo)模型的所有點(diǎn)以尋找源模型的對(duì)應(yīng)點(diǎn)時(shí)，往往也會(huì)搜索在源模型中沒(méi)有對(duì)應(yīng)點(diǎn)的部件。這屬于無(wú)用遍歷，增加了程序的運(yùn)行時(shí)間，故在程序的運(yùn)行速度方面可以再做進(jìn)一步改善，比如利用三維網(wǎng)格分割技術(shù)，先將目標(biāo)模型中多余的部件去除掉，然后再執(zhí)行本文改進(jìn)的ICP算法來(lái)進(jìn)一步提高速度，這將是下一步的研究方向。

Table 1 Comparison of registration error between traditional ICP algorithm and improved ICP表1 本文算法與傳統(tǒng)ICP算法配準(zhǔn)誤差對(duì)比

[1]Zhang J,Yan C H,Chui C K,et al.Multimodal image registration system for image-guided orthopaedic surgery[J].Machine Vision&Applications,2011,22(5):851-863.

[2]Imbert M,Li Xiaoxing.Automatic registration of 3D point clouds for reverse engineering[J].Journal of Computational&Theoretical Nanoscience,2011,4(6):2431-2432.

[3]Lemeszenski D D A,Nakamura R.A marker-free calibration and registration process for multiple depth maps from structured light sensors and its application in video avatar systems[C]//Proceedings of the 15th Symposium on Virtual and Augmented Reality,Cuiabá-Mato Grosso,May 28-31,2013.Washington:IEEE Computer Society,2013:73-82.

[4]Schneider C,Guerrero J,Nguan C,et al.Intra-operative“pick-up”ultrasound for robot assisted surgery with vessel extraction and registration:a feasibility study[C]//LNCS 6689:Proceedings of the 2nd International Conference on Information Processing in Computer-Assisted Interventions,Berlin,Jun 22,2011.Berlin,Heidelberg:Springer,2011:122-132.

[5]Jacobs A G,Jung B,Ober C K,et al.Control of PS-b-PMMA directed self-assembly registration by laser induced millisecond thermal annealing[C]//Proceeding of the SPIE 9049,Alternative Lithographic Technologies VI,Bellingham,Mar 28,2014.San Jose:SPIE,2014:4177-4180.

[6]Besl P J,Mckay N D.A method for registration of 3-D shapes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14(2):239-256.

[7]Senin N,Colosimo B M,Pacella M.Point set augmentation through fitting for enhanced ICP registration of point clouds in multisensor coordinate metrology[J].Robotics and Computer-Integrated Manufacturing,2013,29(1):39-52.

[8]Bae K H,Lichti D D.A method for automated registration of unorganized point clouds[J].ISPRS Journal of Photogrammetry and Remote Sensing,2008,63(1):36-54.

[9]Zhong Ying,Zhang Meng.Automatic registration of point clouds based on improved ICP algorithm[J].Control Engineering of China,2014,21(1):37-40.

[10]Zheng Zhongyang,Li Yan,Wang Jun.LiDAR point cloud registration based on improved ICP method and SIFT feature[C]//Proceedings of the 2015 International Conference on Progress in Informatics and Computing,Nanjing,Dec 18-20,2015.Washington:IEEE Computer Society,2015:588-592.

[11]Wang Xin,Zhang Mingming,Yu Xiao,et al.Point cloud data registration using improved iterative closest point method[J].Optics and Precision Engineering,2012,20(9):2068-2077.

[12]Liu Jiang,Zhang Xu,Zhu Jiwen.ICP three-dimensional point cloud registration based onK-D tree optimization[J].Engineering of Surveying and Mapping,2016,25(6):15-18.

[13]Meng Cai,Zhang Jun,Zhou Fugen,et al.New method for geometric calibration and distortion correction of conventional C-arm[J].Computers in Biology&Medicine,2014,52(3):49-56.

[14]He Bingwei,Lin Zeming,Li Y F.An automatic registration algorithm for the scattered point clouds based on the curvature feature[J].Optics&Laser Technology,2013,46(1):53-60.

[15]Lakehal A,Beqqali O E,Zemzami O A.Retrieval of similar shapes under affine transform using affine length paramete-rization[J].Journal of Computer Science,2010,6(10):1226-1232.

[16]Shakhnarovich G,Darrell T,Indyk P.Nearest-neighbors methods in learning and vision:theory and practice[J].Pattern Analysis andApplications,2008,11(2):221-222.

[17]Walizer L E,Peters J F.A bounding box search algorithm for DEM simulation[J].Computer Physics Communications,2011,182(2):281-288.

附中文參考文獻(xiàn)：

[9]鐘瑩,張蒙.基于改進(jìn)ICP算法的點(diǎn)云自動(dòng)配準(zhǔn)技術(shù)[J].控制工程,2014,21(1):37-40.

[11]王欣,張明明,于曉,等.應(yīng)用改進(jìn)迭代最近點(diǎn)方法的點(diǎn)云數(shù)據(jù)配準(zhǔn)[J].光學(xué)精密工程,2012,20(9):2068-2077.

[12]劉江,張旭,朱繼文.一種基于K-D樹(shù)優(yōu)化的ICP三維點(diǎn)云配準(zhǔn)方法[J].測(cè)繪工程,2016,25(6):15-18.