王程冬，程筱勝，崔海華，戴 寧

（南京航空航天大學(xué)機電學(xué)院，江蘇南京 210016）

0 引言

目前，光學(xué)三維掃描儀已被廣泛應(yīng)用于逆向工程、三維動畫、文物保護(hù)和虛擬現(xiàn)實等領(lǐng)域。掃描系統(tǒng)無需復(fù)雜的安裝和操作即可快速獲得復(fù)雜形體表面的三維采樣點坐標(biāo)。在不同視角下測量得到的多片點云都存在于各自獨立的坐標(biāo)系中，點云數(shù)據(jù)需要進(jìn)行配準(zhǔn)和融合，產(chǎn)生適合被標(biāo)準(zhǔn)三維建模和渲染程序所使用的三維曲面表達(dá)?？梢酝ㄟ^采用經(jīng)過精確標(biāo)定的機械裝置來記錄相機和物體間的相對位置關(guān)系［1］，但是，預(yù)先標(biāo)定的方案并不總是可行?，F(xiàn)在比較流行的方法是在被測物表面合理布置標(biāo)記點［2］，通過標(biāo)志點的匹配實現(xiàn)多片點云的配準(zhǔn)，然而，在有些情況下不具備粘貼標(biāo)志點的條件。

本文提出一種無需借助額外機械裝置和不貼標(biāo)志點的方法來實現(xiàn)多片點云的配準(zhǔn)，該方法的基本要求就是相鄰兩次測量得到的點云數(shù)據(jù)有足夠的重合度，每片點云是局部坐標(biāo)系中物體表面三維采樣點的集合，待解決的問題就是如何尋找一個坐標(biāo)變換使得多片點云統(tǒng)一到一個坐標(biāo)系中。這樣的一個變換屬于剛體變換，求解變換的常用方法是ICP算法［3］，但I(xiàn)CP算法存在2個主要問題:初始變換的選取和對應(yīng)點的確定。如果所給初值不當(dāng)，算法就會形成局部最小化，造成迭代不能收斂到正確的結(jié)果;對應(yīng)點的確定方法影響到迭代方法的收斂速度，而保證對應(yīng)點的有效性則決定最后所得變換參數(shù)的精確程度。本文在采用SIFT算法獲得圖像對應(yīng)特征點的基礎(chǔ)上，通過映射關(guān)系獲得三維對應(yīng)特征點，即可求解初始變換，而在對應(yīng)點的確定問題上，采用基于特征點的改進(jìn)ICP算法，最終實現(xiàn)點云的精確配準(zhǔn)。

1 SIFT算法原理

SIFT（scale invariant feature transform）算法［4］是 Lowe D G在總結(jié)了現(xiàn)有的基于不變量技術(shù)的特征檢測方法的基礎(chǔ)上，提出的一種基于尺度空間的圖像局部特征描述算法。SIFT特征描述只是圖像的局部特征，該特征對旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性。

1.1 檢測尺度空間特征點

一幅圖像在不同尺度下的尺度空間定義為圖像I（x，y）與高斯核G（x，y，σ）的卷積

式中L為圖像的尺度空間，（x，y）為圖像的像素坐標(biāo)，σ為尺度坐標(biāo)。為有效檢測出尺度空間中的穩(wěn)定特征點，引入高斯差分函數(shù)D（x，y，σ）

其中，k是一個常量。為尋找尺度空間的極值點，每個像素點需要和與它同尺度的8個相鄰點，以及上下相鄰尺度對應(yīng)的9×2個點共26個點相比較，如果該像素點的DoG算子值在這26個鄰域中為極值，則將該點定義為特征點。

1.2 特征點精確定位

通過計算擬合曲面的極值來確定特征點的精確位置和尺度，同時去除低對比度的特征點和不穩(wěn)定的邊緣響應(yīng)點，以增強匹配穩(wěn)定性，提高抗噪聲能力。

利用尺度空間函數(shù)D（X）的泰勒二次展開式進(jìn)行最小二乘擬合

其中，向量X=（x，y，σ），表示采樣點和特征點之間位置、尺度偏移。令式（3）的一階導(dǎo)數(shù)為0，可得特征點精確位置的偏移向量

將加到原特征點的坐標(biāo)，即得特征點的亞像素精確估計。

1.3 確定特征點主方向

利用特征點鄰域內(nèi)像素的梯度方向分布特性為每個特征點定義主方向，使特征點的描述只具備旋轉(zhuǎn)不變性。在尺度空間中，每個像素的梯度模和方向分別為

創(chuàng)建梯度方向直方圖，直方圖以每10°作為一個柱，共36個柱，將鄰域內(nèi)每個像素點按梯度方向θ歸入適當(dāng)?shù)闹?，以梯度模m作為貢獻(xiàn)權(quán)重。選擇直方圖的主峰值作為特征點主方向，選取量值達(dá)到主峰值80%以上的峰值作為輔方向。這樣一個特征點可能會被指定多個方向，可以增強匹配的魯棒性。

1.4 生成特征點描述子

首先，按特征點主方向旋轉(zhuǎn)坐標(biāo)軸，將以特征點為中心的16×16矩形窗口均勻地分成16個4×4的子區(qū)域。然后，在每個子區(qū)域上計算8個方向上的梯度累加值，形成一個種子點，每個種子點對應(yīng)8個方向信息，則一個特征點就對應(yīng)16×8=128維的向量。將特征向量的長度歸一化，可以去除光照變化的影響。

1.5 特征點匹配

兩幅圖像特征點的描述子生成后，采用特征向量的歐氏距離作為兩幅圖像中特征點相似性判定度量。取一幅圖像中的某個特征點，在另一幅圖像中找出與其歐氏距離最近的前2個特征點，如果最近距離與次近距離的比值小于某個設(shè)定的閾值，則接受這一對匹配點。降低閾值，匹配點數(shù)目會減少，但更加穩(wěn)定。

2 匹配點提純

對于兩幅有部分重疊區(qū)域的圖像，采用SIFT算法得到的匹配點可能存在少部分誤匹配，需要進(jìn)一步予以剔除。另外，在利用三維掃描儀進(jìn)行測量時，由二維像素點可以映射得到三維對應(yīng)點，受測量誤差和噪聲的影響，對應(yīng)的三維點間也存在誤匹配。針對二維和三維的誤匹配問題，本文分別采用一致性提純法和投票提純法予以解決。

2.1 一致性提純法

在忽略成像畸變時，同一場景不同視角的圖像間具有一一對應(yīng)關(guān)系。在齊次坐標(biāo)系下，圖像X（xi，yi，1）T和X'（x'i，y'i，1）T之間滿足透視變換關(guān)系［5］

式（7）表示成向量形式為kXi=HX'i，其中，k為比例系數(shù)，H為自由度為8的變換矩陣。只要有4個對應(yīng)的像素匹配點，就可以計算出兩幅圖像間的變換關(guān)系。如果4對匹配點中存在錯誤的匹配，則計算出的變換矩陣H與實際變換矩陣之間必然會存在很大的差異。

RANSAC（random sample consensus）算法［6］是一種估計數(shù)學(xué)模型參數(shù)的迭代算法，主要思路是通過采樣和驗證的策略，求解大部分樣本（本文中指特征點）都能滿足的數(shù)學(xué)模型的參數(shù)。本文運用RANSAC算法的具體步驟如下:

1）隨機抽取4對匹配點，作為初始的內(nèi)點集合，通過該內(nèi)點集合計算出變換矩陣H。

2）依次判斷內(nèi)點集合外的點，計算Xi與HX'i之間的距離，如果小于設(shè)定的閾值，則將當(dāng)前點加入到內(nèi)點集合中。

3）重復(fù)（1）和（2）N次，選取內(nèi)點個數(shù)最多的那一組作為合格的匹配點集。根據(jù)新的內(nèi)點集合，運用最小二乘法更新變換矩陣H。

假設(shè)正確匹配的點占總數(shù)的比例為p，則隨機抽取的4對匹配點不全是正確匹配的幾率為1－p4，抽取N次都抽不到4對全是正確匹配點的概率為（1－p4）N，在實踐中只要能夠保證（1－p4）N＜0.05就可以滿足實際應(yīng)用需要。

2.2 投票提純法

由于在不同視角下，三維采樣點之間的相互位置關(guān)系并沒有改變，因而，它們具有空間特征不變性［7］，比如:某2個三維點之間的歐式距離不會因為視角的改變而變化。由于實際測量時不可避免都存在一定的誤差，因此，本文認(rèn)為，如果2個距離的差值小于設(shè)定的閾值，即可認(rèn)為這2個距離值是相等的。

基于這個原則，在全部的匹配點中根據(jù)空間點之間的距離是否相等進(jìn)行投票，保留得票數(shù)超過一定數(shù)量的匹配點，去除得票數(shù)較低的匹配點。設(shè){vk}，{v'k}分別表示三維對應(yīng)點集，k=1，2，…，N，N為匹配個數(shù)，為每對點（vk，v'k）之間的匹配關(guān)系建立累加器CNTk，對投票結(jié)果進(jìn)行統(tǒng)計，用‖vkv'k‖表示兩點間的歐氏距離，投票算法偽代碼如下

當(dāng)累加器的數(shù)值與匹配個數(shù)的比值CNTk/N大于設(shè)定的閾值時，則保留相應(yīng)的匹配點，而其它的匹配點視為誤匹配。

3 點云配準(zhǔn)

點云的配準(zhǔn)過程可以劃分為粗配準(zhǔn)和精確配準(zhǔn)。粗配準(zhǔn)就是在初始坐標(biāo)變換關(guān)系未知的情況下，對任意相對位置下的多片點云進(jìn)行配準(zhǔn)，使得配準(zhǔn)后的點云數(shù)據(jù)具有良好的吻合度。粗配準(zhǔn)可以獲得較好的初始位置關(guān)系，但在實際應(yīng)用中這種初始位置的精度是不能滿足最終拼合要求的，需要進(jìn)行精確配準(zhǔn)以提高精度。粗配準(zhǔn)為精確配準(zhǔn)提供了良好的初始位置，是點云配準(zhǔn)過程的基礎(chǔ)。

3.1 粗配準(zhǔn)

對應(yīng)點集配準(zhǔn)算法的目標(biāo)在于尋找最小二乘逼近的坐標(biāo)變換矩陣，可以采用單位四元數(shù)法［8］得到。若目標(biāo)點集D對應(yīng)于參考點集X，則D中點的個數(shù)ND和X中點的個數(shù)NX相等，即ND=NX。計算變換矩陣的步驟如下:

1）分別求目標(biāo)點集D和參考點集X的重心

2）由點集D和X構(gòu)造協(xié)方差矩陣

3.2 精確配準(zhǔn)

ICP（iterative closest point）算法是目前應(yīng)用最廣的點云精確配準(zhǔn)算法。ICP算法雖然能夠滿足點云配準(zhǔn)在精度上的要求，但算法本身計算效率不高，花費時間較多，特別是對于有實時性要求的三維掃描系統(tǒng)無法直接使用。

本文采用基于特征點的改進(jìn)ICP算法，解決傳統(tǒng)ICP算法計算效率的問題。本文算法首先獲得目標(biāo)點云中經(jīng)過匹配點提純得到的特征點，然后利用kd-tree尋找這些特征點在參考點云中的最近點，通過這些步驟可以顯著減少算法的時間復(fù)雜度。

算法流程說明如下:

1）得到目標(biāo)點云D（含有nD個點）和參考點云X（含有nX個點）;

2）經(jīng)過匹配點提純，獲得D中的N個特征點，得到特征點集S0;

3）初始化:迭代次數(shù)k=0，由粗配準(zhǔn)得q0=［qR，qT］，對特征點集進(jìn)行初始變換S1=q0（S0），為參考點云X建立kd-tree;

4）尋找Sk在X中的最近點S'k，由對應(yīng)點集Sk和S'k計算坐標(biāo)變換向量qk;

5）特征點集坐標(biāo)變換:Sk+1=qk（Sk）;

6）判斷誤差是否收斂，若dk－dk+1＜τ，則收斂，τ＞0為設(shè)定的閾值，否則，轉(zhuǎn)到步驟（4）;

7）目標(biāo)點云坐標(biāo)變換:D'=qk（D）。

4 實驗結(jié)果

通過對牙模的測量來驗證本文算法的有效性。1）由三維掃描儀獲得牙模的局部圖像并重建得到點云數(shù)據(jù);2）再次獲得牙模局部圖像且與前次測量的圖像有部分重疊區(qū)域，采用SIFT算法進(jìn)行特征匹配，由圖1（a）可知，采用SIFT算法得到的圖像間的匹配特征點不夠精確，經(jīng)過一致性提純后，能夠較好地剔除誤匹配點，結(jié)果如圖1（b）所示。3）由像素點和三維點的一一映射關(guān)系獲得三維匹配點，首先對兩片點云進(jìn)行粗配準(zhǔn)，由圖2（a）可知僅用粗配準(zhǔn)會造成配準(zhǔn)精度不夠，不能滿足要求，采用改進(jìn)的ICP算法精確配準(zhǔn)后，可以得到較好的配準(zhǔn)精度，結(jié)果如圖2（b）所示，圖2（c）為兩片點云融合后生成的STL模型。

圖1 圖像特征檢測與匹配Fig 1 Feature detection and matching of image

圖2 兩片點云配準(zhǔn)Fig 2 Registration of two point clouds

由圖3和圖4可知，本文算法對于多片點云配準(zhǔn)也有令人滿意的效果。

圖3 三片點云配準(zhǔn)Fig 3 Registration of three point clouds

圖4 牙模的完整STL模型Fig 4 STL model of the complete dental wax

5 結(jié)論

針對ICP算法初始變換選取的問題，本文提出在采用SIFT算法獲得圖像對應(yīng)特征點的基礎(chǔ)上，通過一一映射關(guān)系獲得三維對應(yīng)特征點，由單位四元數(shù)法獲得點云初始位置關(guān)系。通過實驗驗證，對點云進(jìn)行粗配準(zhǔn)獲得了較好的初始位置關(guān)系，再用改進(jìn)的ICP算法進(jìn)行精確配準(zhǔn)，得到較好的配準(zhǔn)精度和收斂速度。在實際應(yīng)用中，具有較高的使用價值。

［1］龍 璽，鐘約先，李仁舉，等.結(jié)構(gòu)光三維掃描測量的三維拼接技術(shù)［J］.清華大學(xué)學(xué)報:自然科學(xué)版，2002，42（4）:477 －480.

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

［3］Chen Y，Medioni G.Object modeling by registration of multiple range images［C］//Proc of IEEE Conf on Robotics and Automation，Sacramento，Califomia，1991:2724 －2729.

［4］Lowe D G.Distinctive image features from scale-invariant keypoints［J］.International Journal of Computer Vision，2004，60（2）:91－110.

［5］王永明，王貴錦.圖像局部不變特性特征與描述［M］.北京:國防工業(yè)出版社，2010:163－164.

［6］徐正光，田 清，張利欣.圖像拼接方法探討［J］.微計算機信息，2006，22（3）:27 －30.

［7］梁云波，鄧文怡，婁小平，等.基于標(biāo)志點的多視三維數(shù)據(jù)自動拼接方法［J］.北京信息科技大學(xué)學(xué)報，2010，25（1）:30－33.

［8］Eggert D W，Lorusso A，F(xiàn)isher R B.Estimating 3D rigid body transformations:A comparison of four major algorithms［J］.Machine Vision and Applications，1997，9（1）:272 －290.