賀永興，歐新良，2

(1.湖南工業(yè)大學計算機與通信學院，湖南 株洲 412008;2.長沙大學計算機科學與技術系，湖南 長沙 410003)

昆蟲點云配準方法綜述*

賀永興1，歐新良1，2

(1.湖南工業(yè)大學計算機與通信學院，湖南 株洲 412008;2.長沙大學計算機科學與技術系，湖南 長沙 410003)

綜述了點云數(shù)據(jù)的配準方法和相關算法，并對這些配準算法的基本思想加以分析比較，分析了昆蟲外形點云的特點及應用領域，對昆蟲點云配準技術的發(fā)展動態(tài)作了介紹，并對未來研究作了展望.

昆蟲點云;配準;ICP算法

仿生學是研究模擬生物系統(tǒng)或使人造技術系統(tǒng)具有類似于生物系統(tǒng)功能的科學.由于昆蟲具有驚人的環(huán)境適應能力，分布極廣，并且結構和功能各異，所以昆蟲是仿生學研究的主要生物來源.對昆蟲外形的仿生學研究具有重要的現(xiàn)實意義，比如對臭蜣螂唇基外形的三維建模有助于切土減能的研究，對蜻蜓翅膀外形的三維建模將有助于直升飛機機翼的研制.其次，昆蟲千姿百態(tài)的外表和令人驚奇的動作，是三維動畫制作的素材寶庫.還有，仿生建筑也需要昆蟲外形的三維數(shù)據(jù)模型，昆蟲的體型和外表往往能夠激發(fā)建筑設計師的靈感.

我們要通過建立昆蟲外形的模型來研究其外形對生存模式的作用和影響，首先就要利用三維激光掃描設備采集昆蟲表面的點云，其次對數(shù)據(jù)進行預處理，預處理的過程包括點云的配準、去噪、精簡、劃分、光順等，其中，點云配準是預處理過程中最重要的一步.

1 點云數(shù)據(jù)配準的定義

為了對被測物體進行三維重建，我們首先需要獲得三維物體表面的真實數(shù)據(jù).但是，由于受到測量設備和環(huán)境等因素的限制和影響，使得每次測量得到的點云數(shù)據(jù)只是實體表面的一部分，并且可能出現(xiàn)平移錯位和旋轉錯位，所以我們若要獲得物體表面完整的測量數(shù)據(jù)，就必須對物體進行多次不同角度、不同位置的測量，并將從各個視角得到的點集合并到一個統(tǒng)一的坐標系下，形成一個完整的數(shù)據(jù)點云，然后才可以方便地進行可視化等操作，這就是點云數(shù)據(jù)的配準.

點云數(shù)據(jù)配準在數(shù)學上的描述為∶設用{pi|pi∈R3，i=1，2，…，N} 表示第一個點集，用 {qi|qi∈R3，i=1，2，…，M}表示第二個點集，找出兩個點集的空間變換，使兩個點集中的相同點進行匹配，兩個點集的對齊變換是應用最小二乘法使下列目標函數(shù)為最小∶min.其中pi'表示在{qi}中找到與{pi}匹配的對應點，使兩者離差平方和為最小.

2 點云數(shù)據(jù)配準的方法

點云數(shù)據(jù)配準有手動配準、依賴儀器的配準和自動配準.值得注意的是，由于各種因素的影響，采用三維激光掃描獲取得到的點云數(shù)據(jù)，無法避免地在真實數(shù)據(jù)點中混有不合理的噪聲點，其結果將直接影響計算精度，因此在進行數(shù)據(jù)點集配準之前，需要進行必要的噪聲點處理和數(shù)據(jù)壓縮處理.關于數(shù)據(jù)的噪聲點處理和數(shù)據(jù)壓縮處理，可參看文獻［1，2］，這里就不再展開討論.下面就各種點云數(shù)據(jù)配準方法進行簡要的介紹和分析.

2.1 手動配準方法

目前，對點云數(shù)據(jù)配準的手動方法主要是在測量階段對數(shù)據(jù)進行標記，也就是說在被測物體上貼標簽，標簽一般應貼在相對較平坦的區(qū)域或者標定平板上，然后用掃描儀對模型進行旋轉掃描，根據(jù)前后兩個視角觀察的三個或三個以上不共線的公共標簽來對數(shù)據(jù)進行配準，從而得到一組特殊的點云，相鄰點云之間只存在角度差異.因此，配準時只存在一個配準參數(shù)，這種配準方法比較高效，即使不用迭代法也能取得很好的配準效果，但缺點是物體底部和下部的數(shù)據(jù)點是無法采集的，并且需要相應的硬件支持.

2.2 依賴儀器的配準方法

目前，依賴儀器的配準方法主要是采用激光掃描儀和自動旋轉臺相互配合的測量方法［3］，利用旋轉臺控制被測物體繞旋轉臺中心軸線按規(guī)定的旋轉角度旋轉，工作臺每旋轉一個位置，激光掃描儀則從不同視角采集一次被測物體的點云數(shù)據(jù)，從而可實現(xiàn)多視角點云自動旋轉對齊，對齊精度取決于旋轉臺中心軸線與旋轉角度的精確度.還有一種可行的方法是固定測量物體，通過關節(jié)臂式掃描系統(tǒng)機械手臂的空間運動來記錄測量頭的空間位置變換.

2.3 自動配準方法

自動配準方法是通過一定的算法或者統(tǒng)計學規(guī)律，利用計算機消除兩片點云之間的誤差和錯位，從而達到把兩片點云自動配準的效果，通常意義上的點云配準技術即是自動配準技術.點云數(shù)據(jù)配準的實質是把在不同的坐標系中測量得到的數(shù)據(jù)點云進行坐標變換，以得到統(tǒng)一坐標系下的整體數(shù)據(jù)模型.問題的關鍵是如何求得坐標變換參數(shù)R(旋轉矩陣)和參數(shù)T(平移向量)，使得兩視角下測得的三維數(shù)據(jù)經(jīng)坐標變換后的距離最小.

目前采用的自動配準技術包括初始配準(粗配準)和精確配準兩步.第一步∶初始配準，它的意義在于縮小點云間平移誤差和旋轉誤差，給精確配準提供良好的初值，以此提高配準效率和趨勢.第二步∶精確配準，它使點云之間的配準誤差達到最小.在點云數(shù)據(jù)初始配準和精確配準過程中，運用最廣泛的算法大致可分為三類∶迭代配準算法、基于曲面的配準算法和基于幾何特征的配準算法，下面對這三類算法加以分析和比較.

2.3.1 迭代配準算法

迭代配準算法，即最近點迭代(Iterative ClosestPoint，ICP)算法［4］，1992 年，由Besl和Mckay等提出.ICP 算法主要用于解決基于自由形態(tài)曲面的配準問題，它是當前點云數(shù)據(jù)配準過程中應用最廣泛的算法.該算法以四元數(shù)配準算法為基礎，首先利用牛頓迭代或者搜索方法尋找兩組點云對應的最近點對，然后采用歐氏距離作為目標函數(shù)進行迭代，從而得到三維的剛體變換.迭代算法雖然精確度很高，但存在很多局限∶首先是ICP算法對兩組點云相對的初始位置要求比較高，點云之間初始位置不能相差太大，并且要求兩個匹配點集中的一個點集是另外一個點集的子集;其次是ICP算法在求解鄰近點對集的過程中采用的是全局搜索，所以配準過程會因為迭代次數(shù)太多而導致時間復雜性增加.當位置條件不滿足，或相差太大時，我們將無法確定收斂方向，進而影響ICP算法的收斂結果，甚至還有可能陷入局部最優(yōu)解，使得配準變得不可靠甚至是錯誤的.所以，在迭代過程中確立正確的對應點集，是避免迭代陷入局部極值的關鍵，它直接決定了算法的收斂速度與最終的配準精度［5］.鑒于ICP算法在確立對應關系時一般需進行大量耗時的搜索工作，國內外學者亦提出一些加速算法(如使用k－d tree)來提高ICP算法的效率.

2.3.2 基于曲面的配準算法

在無法預知點云數(shù)據(jù)間的相互關系時，迭代算法的有效性得到了質疑，這時基于曲面描述的配準算法［6］就顯示了其優(yōu)越性.Chen 和 Medioni［7］兩位學者在 Besl和 Mckay 的經(jīng)典ICP算法的基礎上進行了改進，運用兩個測點曲面在法矢方向的距離來代替某一點到其最近點的距離，并將其作為匹配的目標評價函數(shù)，但是要求解一個非線性最小二乘問題，所以速度較慢.這種方法的好處是一開始就可以使迭代誤差很快地減小，也就是快速地收斂，但是因為它用切平面來代替真正的曲面，也就是忽略了目標函數(shù)中的二次項信息，導致有時候迭代不收斂，尤其當目標物體表面曲率變化明顯時.事實上，這種方法是一種Gauss－Newton法，它不保證收斂，但是一旦收斂，其速度會比較快，是二次收斂.

2.3.3 基于幾何特征的配準算法

為了有效地解決不存在明確對應關系的點云配準問題，提出了一種基于點云幾何特征的配準算法.因為曲率能夠表示測點的局部鄰域形狀變化，具有平移、旋轉和縮放不變性，所以可以作為曲面特征識別的重要依據(jù).該算法首先以點云的曲率為聯(lián)系特征，搜索配準點云的匹配對集合;然后利用鄰域特征對各匹配對進行相似性度量，提取有效配準點對，并引入剛體變換中向量幾何性質剔除其錯配對，生成點云初變換;最后采用ICP算法對點云初配結果進行優(yōu)化，實現(xiàn)點云精確配準.

朱延娟等［8］根據(jù)測點及其鄰域點估算每個點的曲面法矢來計算各個測點的曲率，由每個測點的曲率來識別兩組點云數(shù)據(jù)中可以匹配的點對集合，進而進行精確配準，雖然保證了算法的配準精度，但執(zhí)行中需要進行大量的搜索查找，并且存在多個相似點對，容易增加算法的復雜度.

事實上，基于曲面描述的配準算法和基于幾何特征的配準算法可以看作是同一種方法，即基于特征的配準算法，這種方法配準效率較高，并且對于如局部重疊的點云數(shù)據(jù)，適用性較好.

3 昆蟲點云數(shù)據(jù)的配準方法分析

3.1 昆蟲外形點云特點

昆蟲外形點云的特點，主要包括昆蟲形狀特征、體型規(guī)格、點云規(guī)模等.通常情況下，不同的昆蟲可能有完全不同的外形結構，比如有無角突、齒突、脊梁、毛刺、褶皺、鞘翅等，我們可以根據(jù)實際的應用來有針對性地研究其外形結構.昆蟲的體型尺寸一般不會超過數(shù)厘米，小到0.02厘米，因此對它們的三維掃描有一定困難，目前最好的三維激光掃描儀測量精度達到0.01毫米，最好的三維激光掃描顯微鏡測距精度達到0.01微米，因此昆蟲外形點云處理有特殊性，要有一個放大的過程，以便于人眼觀察.但是放大后，有一個細節(jié)失真的問題要解決.若研究對象是體型較大的昆蟲，尺寸在0.1厘米到10厘米范圍內，比如螞蟻、臭蜣螂、蜻蜓等，圖形顯示本身可以放大幾倍到幾十倍或幾百倍之間，雖然細節(jié)失真的問題仍然存在，但對整體點云數(shù)據(jù)的配準影響不大.

3.2 昆蟲點云數(shù)據(jù)的配準

對采集得到的昆蟲點云數(shù)據(jù)進行配準，我們通常采用基于幾何特征的配準方法，由于曲率能夠表示測點的局部鄰域形狀變化，具有平移、旋轉和縮放不變性，所以可以作為昆蟲曲面特征識別的重要依據(jù).

通常情況下，昆蟲外形結構特征異常復雜，昆蟲外表面曲率變化劇烈，需要進行多角度多次掃描以減少掃描盲區(qū)和死角，以此來獲得更多數(shù)據(jù)信息.有關昆蟲點云曲率的估算也必須要適應這種情況，一般的曲率估算誤差較大，而昆蟲外形顯示需要放大，這導致曲率的估算誤差也可能放大.為了在重建顯示過程中保持昆蟲外表形狀的幾何特征不變，則需要找到更好的曲率估算方法.目前所有點云曲率估算方法的誤差都受到點云密度的較大影響，即∶點云密度越大，估算越準確，反之不然.而昆蟲點云由于昆蟲體型的原因，不可能過高地追求點云密度，因為這會導致對掃描儀精度要求的提高.當前主流掃描儀的精度也是有限的，所以我們只能在曲率估算方法上尋求突破.當今，點云曲率估算方法已經(jīng)較為成熟，再要提高估算精度似乎有較大的困難，但是由于昆蟲外形點云的特殊性，不增加曲率估算精確度，就無法刻畫昆蟲外形的結構特征.所以，如何在已有點云數(shù)據(jù)的基礎上提高曲率估算精度是擺在眾多科研學者面前的一道難題.

有國內學者提出一種從經(jīng)典的曲率估算公式入手，采用幾何的途徑提高曲率估算精度的方法，目前的估算方法都是近似的辦法，這說明有改進的空間.自由曲面上的微分算子，都是逼近運算的極限值，理論上是可以得到精確解的，但是在具體計算時又是取其逼近值(數(shù)值解)，受自由曲面高斯曲率計算公式［9］的啟發(fā)，離散高斯曲率估算公式所依托的多面體在空間與原型上可以進一步逼近，因此在二者之間進行三維空間插值逼近是有可能的.之前點云配準時所使用的擬合曲面法是基于已有的離散點，在其某個鄰域內建立擬合曲面，計算其高斯曲率和其它微分量，而它的精度主要受點云密度和鄰域半徑的影響，并且計算量比較大.不同于擬合曲面法，若首先建立空間插值模型，在相同已知相鄰點數(shù)的情況下，置入插值點，設置調節(jié)參數(shù)，通過實驗來獲取其逼近精度與調節(jié)參數(shù)的關系，從而尋找最優(yōu)閾值，那么，高斯曲率估算的精度將大大提高.

4 研究展望

點云數(shù)據(jù)配準技術，尤其是昆蟲點云數(shù)據(jù)配準技術是實現(xiàn)逆向工程和仿生工程的關鍵技術，目前它仍處在發(fā)展階段，有許多問題有待進一步地研究和解決.下述幾個方面仍然是今后研究的熱點和難點，迫切需要引起研究人員的關注∶

(1)雖然ICP算法以其簡便、高效及良好的精度與穩(wěn)定性成為了精確配準領域的基本算法，但是它大多只能適用于一些特殊場合，比如必須要求待配準點云相對初始位置較近或者具有包含關系.除此之外，在其他場合其性能一般無法令人滿意，故提出一種具有普遍適用性并且具有良好可靠性與魯棒性的ICP算法將是今后研究的重點和難點.

(2)其次是ICP算法在求解鄰近點對集的過程中采用的是全局搜索方法，在執(zhí)行中需要進行大量的搜索查找，并且很容易找到相似的對應點對而重復操作，這直接導致配準過程因迭代次數(shù)太多而使時間復雜度大增.所以，需要找到一種快速確立對應點集并過濾錯誤點集的方法，以此來降低時間復雜度，提高配準效率.

(3)對于昆蟲點云數(shù)據(jù)的配準，盡管基于幾何特征的配準方法較為實用，但是由于昆蟲外形結構的特殊性以及三維掃描設備精度的限制，根據(jù)測點及其鄰域點來估算每個點的曲率時，往往存在著較大的估算誤差，所以，一般的曲率求解方法不適合于昆蟲點云.找到適合昆蟲點云數(shù)據(jù)特性的曲率求解方法將是配準成功的關鍵.同時，盡可能地降低曲率估算的誤差也直接關系到最終配準的精度，故如何快速正確求解昆蟲點云數(shù)據(jù)的曲率將是今后研究的重點和難點.

(4)此外，當昆蟲的尺寸小于0.1厘米或者更小時，如何解決昆蟲點云數(shù)據(jù)放大后的細節(jié)失真問題，如何求得相關的點云幾何特征，進而有效地配準點云將是以后研究的重點和難點.

5 結語

本文對點云數(shù)據(jù)的一般配準方法和針對昆蟲點云數(shù)據(jù)的配準方法進行了論述.首先總結分析了點云數(shù)據(jù)配準的主要方法，其次對比較有代表性的配準方法及算法進行了具體的分析和對比，最后闡述了適合昆蟲點云配準的方法和研究現(xiàn)狀.目前，對配準算法的研究仍然集中在算法的速度、精度、穩(wěn)定性、收斂性和可靠性等方面，如何改進算法，如何快速配準昆蟲點云數(shù)據(jù)，將是今后的研究重點.

［1］李劍.基于激光測量的自由曲面數(shù)字制造基礎技術研究［D］.杭州:浙江大學博士學位論文，2001.

［2］吳敏，周來水，王占東，等.測量點云數(shù)據(jù)的多視拼合技術研究［J］.南京航空航天大學學報，2003，(5):552 －557.

［3］ Vàrady T ，Martin R R，Cox J.Reverse engineering of geometric models——an introduction［J］.Computer Aided Design，1997，29(4):255－268.

［4］Besl P J，McKay N D.A method for registration of 3D shapes［J］.IEEE Transactions on Pattern Analysis Machine Intelligence，1992，14(2):239－256.

［5］Gregory C，Sang W，David K.ICP Registration using invariant features［J］.IEEE Transactions on Pattern Analysis Machine Intelligence，2002，24(1):90 －102.

［6］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.

［7］Chen Y，Medioni G.Object modeling by registration of multiple range images［J］.Image and Vision Computing，1992，10(3):145 －155.

［8］朱延娟，周來水，張麗艷.散亂點云數(shù)據(jù)配準算法［J］.計算機輔助設計與圖形學學報，2006，18(4):475－481.

［9］歐新良，陳松喬，方逵.基于高斯映射下自由曲面的形狀分析及邊界計算［J］.小型微型計算機系統(tǒng)，2006，(4):735－740.

(責任編校:晴川)

TP391

A

1008－4681(2011)05－0055－03

2011－04－26

湖南省教育廳科技重點項目(批準號∶09A010).

賀永興(1984－)，男，湖南株洲人，湖南工業(yè)大學計算機與通信學院碩士生.研究方向∶計算機圖形學.