賀永興，歐新良，2

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

昆蟲點(diǎn)云配準(zhǔn)方法綜述*

賀永興1，歐新良1，2

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

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

昆蟲點(diǎn)云;配準(zhǔn);ICP算法

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

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

1 點(diǎn)云數(shù)據(jù)配準(zhǔn)的定義

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

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

2 點(diǎn)云數(shù)據(jù)配準(zhǔn)的方法

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

2.1 手動配準(zhǔn)方法

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

2.2 依賴儀器的配準(zhǔn)方法

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

2.3 自動配準(zhǔn)方法

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

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

2.3.1 迭代配準(zhǔn)算法

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

2.3.2 基于曲面的配準(zhǔn)算法

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

2.3.3 基于幾何特征的配準(zhǔn)算法

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

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

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

3 昆蟲點(diǎn)云數(shù)據(jù)的配準(zhǔn)方法分析

3.1 昆蟲外形點(diǎn)云特點(diǎn)

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

3.2 昆蟲點(diǎn)云數(shù)據(jù)的配準(zhǔn)

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

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

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

4 研究展望

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

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

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

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

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

5 結(jié)語

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

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

［2］吳敏，周來水，王占東，等.測量點(diǎn)云數(shù)據(jù)的多視拼合技術(shù)研究［J］.南京航空航天大學(xué)學(xué)報，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］朱延娟，周來水，張麗艷.散亂點(diǎn)云數(shù)據(jù)配準(zhǔn)算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報，2006，18(4):475－481.

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

(責(zé)任編校:晴川)

TP391

A

1008－4681(2011)05－0055－03

2011－04－26

湖南省教育廳科技重點(diǎn)項(xiàng)目(批準(zhǔn)號∶09A010).

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