張曉娟，李忠科，王先澤，呂培軍，王 勇

（1．第二炮兵工程學院指揮自動化系，陜西西安 710025;2．北京大學口腔醫(yī)學院，北京 100871）

0 引言

隨著激光掃描技術(shù)的發(fā)展，利用激光掃描儀可以在幾秒鐘之內(nèi)直接得到被測物體表面的點云數(shù)據(jù)，在三維物體數(shù)字化過程中，由于受測量設備測量范圍的限制和被測物體外形的復雜性等，三維檢測一次只能得到物體某一部分表面的數(shù)據(jù)，要得到物體完整的形狀信息，需要從不同角度使用多次定位進行測量，而將各個視角得到的點集合并到一個統(tǒng)一的坐標系下，這就是點云數(shù)據(jù)的配準，實際上，配準就是求解在不同視角下三維坐標點之間的轉(zhuǎn)換關(guān)系，它是航空航天、醫(yī)學圖像處理、曲面質(zhì)量檢測和虛擬現(xiàn)實等領(lǐng)域的一項關(guān)鍵技術(shù)，有著廣泛的應用。

1 初始配準

點云數(shù)據(jù)配準前進行預配準，以減少精確配準過程的收斂時間，初始配準可以使兩組點云數(shù)據(jù)盡可能的靠近，從而縮小2個模型之間的差異，提高配準精度。一個好的預配準必須達到兩點:1）預配準的效率要高;2）預配準后的結(jié)果要盡可能和模型接近。這樣才能有效簡化迭代過程并達到預期的目的。

預配準的算法有力矩主軸法、遺傳算法、三點對齊法、基于特征點法等。力矩主抽法對于數(shù)據(jù)的缺失比較敏感，需要的時間很長，在精度要求不高的情況下可以使用。遺傳算法的進化過程比較耗時，配準時間比較長。三點對齊法原理簡單，能夠快速實現(xiàn)預配準，但需要準確確定三基準點的對應關(guān)系?；谔卣鼽c的預配準［7］可以快速完成配準，但是它不能消除配準過程中出現(xiàn)的二義性，所以，特征點的錯誤選擇可能導致配準誤差增大，甚至造成配準失敗。

本文采用一種基于特征點的等曲率預配準方法，首先計算每個點的曲率，曲率信息和點的對應關(guān)系采用哈希表［8］來映射，然后通過對曲率信息進行量化，得到等曲率的特征點，最后利用這些特征點完成預配準，算法如圖1所示。

圖1 點云初始配準Fig 1 Point cloud primary registration

由算法流程圖可以看出:它首先采用點的曲率對點云數(shù)據(jù)進行簡化，將搜索比較過程限制在同曲率點的范圍內(nèi)，有效減少了比較特征點的個數(shù)，大大簡化了原始配準的過程。

2 精細配準

經(jīng)過預配準后，兩組點云數(shù)據(jù)已經(jīng)比較靠近，2個模型之間的差異已經(jīng)縮小了很多，這時候再用迭代方法進行精細配準，就能達到較好的配準結(jié)果。

2．1 ICP概述與算法描述

ICP算法其原意是迭代最近點匹配算法，后來被廣泛理解為迭代對應點（iterative corresponding point）它是相對比較穩(wěn)定和魯棒的算法，具有一些顯著的優(yōu)點，很容易和其他算法結(jié)合，且很容易修改算法的一些步驟解決不同的實際問題。

ICP算法重復進行“確定對應關(guān)系點集并計算最優(yōu)剛體變換”，直到某個表示正確匹配的收斂準則得到滿足，其變換關(guān)系式和收斂準則為

式中 Pi和Qi為2個數(shù)據(jù)點集，R為旋轉(zhuǎn)矩陣，T為平移向量，e達到最小時滿足收斂準則，其實質(zhì)是基于最小二乘法的最優(yōu)匹配方法。

1、葉菜類蔬菜（如大白菜、白菜、菠菜、芹菜等）葉面追肥以尿素為主，噴施濃度0.3%～0.5%，每667m2噴灑75～100kg，全生育期共噴2～3次，也可噴施0.3%米醋溶液，每667m2噴50kg左右。

2．2 鄰近搜索的ICP改進算法

ICP算法雖然具有較好的精度，但由算法描述可知，它采用的是全局搜索，故計算量很大且運算時間很長，針對這一缺點，本文采用鄰近搜索的ICP算法，由于ICP算法最耗費時間的步驟是求解鄰近點對的過程，為了縮短對應點的搜索時間，將搜索范圍限制到局部數(shù)據(jù)，而且經(jīng)過了預配準后，數(shù)據(jù)之間差異縮小了，從而大大減少了計算量和運算時間。求解2個不同視圖中數(shù)據(jù)點之間的變換，即坐標旋轉(zhuǎn)變換R和平移變換T，是點云數(shù)據(jù)配準的本質(zhì)。

2．2．1 鄰近關(guān)系對應準則

鄰近搜索算法假設2個點集P和Q之間有鄰近對應關(guān)系，給出2個鄰近集合p'和q'，這2個集合分別是從P和Q數(shù)據(jù)集合直接定義得來的，假設一個數(shù)據(jù)集合的2個鄰近點在另一個數(shù)據(jù)集里有對應的最近點，鄰近關(guān)系的對應準則是（如圖2）:2個數(shù)據(jù)集合P和Q，qs是ps對應的最近點，C（pi）是pi的鄰近集合，C'（qs）是qs的鄰近集合

若ps∈C（pi），則qi∈C'（qs），即pi在Q中的最近點qi就能在qs的鄰近集合C'（qs）中找到。

2．2．2 鄰近算法描述

從點云數(shù)據(jù)的拓撲關(guān)系看，每個點有8個鄰近點（不包含邊緣點），故鄰近算法可以這樣描述:鄰近關(guān)系C是P圍繞pi一個3×3的區(qū)域，C'是Q中的n×n的區(qū)域，從左至右一行一行的掃描P中的點，這樣可以在pi的8個鄰近候選點搜索檢驗并最終找到ps，一旦ps確定找到，而ps又有已知的最近點qs，就可以在Q中以qs為中心的n×n的區(qū)域內(nèi)進行pi的最近點的搜索，一般任何一個候選點都有已知屬于它自己的最近點。鄰近搜索算法流程如圖3。

圖2 鄰近關(guān)系準則Fig 2 Relation rule of neighborhood

圖3 鄰近搜索算法流程Fig 3 Flow chart of neighborhood search algorithm

下面的偽代碼簡要描述了鄰近搜索算法:

輸入:點云數(shù)據(jù)P和 Q，相對應的鄰近集合C（p）和C'（q）

輸出:P中每個點pi，在Q中都存在它的最近點的近似值qi

采用鄰近搜索法進行二次精細配準的主要步驟:

1）迭代初始化:使用預配準后兩組點云的位置作為新的初始位置，并且將統(tǒng)計的可匹配點對集合作為初始的配準點對集合。經(jīng)過預配準之后的點云數(shù)據(jù)為

2）最近點計算:計算點云數(shù)據(jù)pi∈FP的對應點qi，使‖pi－pj‖→min?；谔卣鼽c的等曲率預配準方法縮小了模型之間的差異，大大降低了這一步的代價，降低了復雜度。

3）優(yōu)化求解:采用最優(yōu)化解析方法計算旋轉(zhuǎn)變換R和平移變換T，使得∑‖Rpi+T－qj‖→min。

4）進行變換:用得到的R和T對FP進行旋轉(zhuǎn)和平移變換。

5）迭代終止判定:如果最小二乘誤差小于一給定的閾值 ε（ε＞0），即滿足dk－dk+1＜ε時，迭代終止。

3 算法實驗

本實驗通過對實際測量的一牙齒模型在多個視角下的數(shù)據(jù)點云進行配準，驗證了該算法的有效性和可靠性。

取ε=0．000 000 2，在實際計算中，若選取的闞值使得匹配失敗，則可適當放松約束閾值重新匹配，圖4（a），（b）為牙齒模型的2個配準視圖，（c）為初次配準后效果圖，（d）為精細配準后效果圖，（e）為用ICP算法的配準效果。從圖中可以看出:二次配準比初次配準更加精確，因為僅用精確配準可能會使配準趨向一個錯誤的方向，導致無法實現(xiàn)良好的配準效果，而先使用預配準而后再使用精細配準不僅能大幅提高配準精度，而且可以保證配準方向的合理性。

圖4 牙齒模型的配準Fig 4 Registration of dental cast

實驗中，本文也對ICP算法和本文算法進行了比較，主要在算法運行時間方面進行比較。經(jīng)過對牙模型4個視角的數(shù)據(jù)點云進行實驗，驗證了該算法也有較好的配準速度，由表1的分析可以看出:與ICP算法相比，本文算法的效率較高，在配準速度上有明顯的優(yōu)勢，而且點云數(shù)據(jù)量越大，配準速度優(yōu)勢越明顯（表1中點云3為點云1和點云2配準后的新點云，同理，點云5是點云3和點云4配準后的新點云）。

表1 點云數(shù)據(jù)的兩種配準算法時間比較Tab 1 Comparison of registration time of two algorithms

4 結(jié)論

因為基于特征點的等曲率配準算法與鄰近搜索的ICP算法是很獨立的算法，但本文采用預配準和精細配準的形式將它們結(jié)合起來，實例證明:該方法提高了配準的精度和速度，克服了ICP算法計算量大且存在可能無法收斂到全局最優(yōu)解的缺陷，具有更高的可靠性和穩(wěn)定性，有較高的實際應用價值。算法對處理的點云數(shù)據(jù)規(guī)模無特別限制。

［1］ Besl P J，McKay N D．A method for registration of 3D shapes［C］∥IEEE Transactions on Pattern Analysis and Machine Intelligence，Washington D C:IEEE Computer Society，1992，14（2）:239－256．

［2］ Menq C H，Yau H T，Lai G Y．Automated precision measurement of surface profile in CAD－directed inspection［J］．IEEE Transaction on Robotics and Automation，2002，8（2）:268 －278．

［3］ Rusinkiewicz S，Levoy M．Efficient variant of the ICP algorithm［C］∥ The Third International Conference on 3D Digital Image and Modeling，Quebec City，Canada，2001:145 －152．

［4］ Mitra N J，Gelfand N，Pottmann H，et al．Registration of point cloud data from a geometric optimization perspective［C］∥Euro Graphics Symposium on Geometry Processing，2004:23 －32．

［5］ Chua C S，Jarvis R．Point signatures:A new representation for 3D object recognition［J］．International Journal of Computer Vision，1997，25（1）:63 －85．

［6］ Ko K H，Maekawa T，Patrikalakis N M．An algorithm for optimal free－form object matching［J］．Computer－Aided Design，2003，35（10）:913－923．

［7］ 羅先波，鐘約先，李仁舉．三維掃描系統(tǒng)中的數(shù)據(jù)配準技術(shù)［J］．清華大學學報:自然科學版，2004，44（8）:1104 －1106．

［8］ Behzad K P，Behrooz K P．An open problem in matching sets of 3D lines［C］∥2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition（CVPR），Kauai，Hawaii，2001:651－656．