SIFT算法在點云配準中的應用

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

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

0 引言

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

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

1 SIFT算法原理

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

1.1 檢測尺度空間特征點

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

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

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

1.2 特征點精確定位

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

利用尺度空間函數D（X）的泰勒二次展開式進行最小二乘擬合

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

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

1.3 確定特征點主方向

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

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

1.4 生成特征點描述子

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

1.5 特征點匹配

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

2 匹配點提純

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

2.1 一致性提純法

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

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

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

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

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

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

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

2.2 投票提純法

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

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

當累加器的數值與匹配個數的比值CNTk/N大于設定的閾值時，則保留相應的匹配點，而其它的匹配點視為誤匹配。

3 點云配準

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

3.1 粗配準

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

1）分別求目標點集D和參考點集X的重心

2）由點集D和X構造協方差矩陣

3.2 精確配準

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

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

算法流程說明如下:

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

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

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

4）尋找Sk在X中的最近點S'k，由對應點集Sk和S'k計算坐標變換向量qk;

5）特征點集坐標變換:Sk+1=qk（Sk）;

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

7）目標點云坐標變換:D'=qk（D）。

4 實驗結果

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

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

圖2 兩片點云配準Fig 2 Registration of two point clouds

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

圖3 三片點云配準Fig 3 Registration of three point clouds

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

5 結論

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

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

［2］羅先波，鐘約先，李仁舉.三維掃描系統中的數據配準技術［J］.清華大學學報:自然科學版，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］.北京:國防工業出版社，2010:163－164.

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

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

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