一種面向三維重建的改進SIFT圖像匹配算法

◆王梓任 楊友良 馬翠紅

（華北理工大學電氣工程學院 河北 063210）

隨著虛擬現實和三維建模技術在國內的迅速發展，相比之前需要設備的性能可能也會變得更高。而快速獲取和處理目標場景數據，建立較高精度的三維模型也成為現今的研究熱點。現如今主流的三維信息獲得方式有三種：第一種，使用精密儀器的三維數據獲取，比如說，激光雷達掃描，這種方式雖然高效，直接，精度也高，但是成本比較高。第二種，使用Kinect掃描來獲取數據，這種方式便捷，有效，局限在于范圍有限。第三種，是利用圖像的來收集三維信息的方式。這種方式便捷，經濟，有真實感。這幾種方法中基于圖像的三維數據獲取是最具發展前景和應用價值的，并且方便圖像的處理，也擁有更廣泛的視角。同時圖像匹配方法通常應用在圖像處理方面，其主要是針對不同視角、不一樣的方式獲得的圖像，通過匹配算法，找出圖像之間紋理、特征、結構等的相似性和一致性，進而找出相似圖像。其中特征匹配成為圖像領域中的熱點問題，高精度的特征匹配能夠更好得到三維建模所需要的條件。這樣我們就有必要應用更好的更加低廉的實時處理算法。

1 小波變換和Harris相結合算法

目前，有許多特征點檢測和算法提取方法?，F階段主流算法有采用角點提取的Harris算法與點提取的SIFT算法、FAST算法、SURF算法、ORB算法。Harris角點檢測算法基于灰度圖像，并設計局部檢測窗口，使窗口在所有方向上略微移動[1]。當檢測中能量變化大于閾值，那么其中心像素會被選取為角點[2]。該算法簡單而穩定，它不受照明，旋轉和噪聲的影響，但是當圖像比例改變時，特征點會發生顯著變化。FAST算法是加速算法。SURF是SIFT算法的加速版本，ORB是FAST和描述符的組合。所有加速算法都有少量特征點，卻因為點變少，導致精度變差，加大了誤差。首先對參考圖像和場景圖像進行離散小波變換，提取兩幅圖像的低頻部分，然后利用Harris角點檢測來檢測其低頻部分的感興趣點，確定場景的匹配候選區域。

2 小波變換和哈里斯角點檢測

2.1 小波變換

我們可以學習每次通過小波分解分解低頻f0的二維小波分析分解成因此，通過db小波變換，每部分圖像的大小將減小到之前圖片的1/4大小。為了獲得有效且準確的匹配圖像，最初圖像的大小應滿足式（1）：

其中L是分解的最大次數，圖像大小是N×N。

1.2 harris角點檢測

harris角點檢測算法是由 C.Harris和 M.Stephens 在H.Moravec 工作時受啟發于 1988 年提出的。此方法是對Moravec 算法的擴充與完善。為了相對減少噪聲的影響我們采取高斯函數，這是因為一階方向差分對噪聲敏感。如果R超過某個閾值，則將該點作為角點。再采用Harris 算法提取圖像特征點時。基本能夠劃分成下面幾個階段：

首先分別計算像素點在x和y方向上的梯度Ix和Iy，再計算每個像素點對應的梯度乘積 即[3]得到自相關矩陣M1，如式(2)所示。

利用高斯核函數G=(x,y,σ)進行高斯濾波，于是有新的自相關矩陣M2。

利用角點響應函數R求解初始圖片里一一對應的像素點響應值，即R值。其中角點響應函數R=Det(M2)-k?Tr(M2)，Det(M2)=λ1λ2，Tr(M2)=λ1+λ2，其中λ1,λ2為自相關矩陣M2的特征值，k為經驗值。若是某點的角點響應值R超過預先選好的閾值大小，那么這個點就被選定為特征點[4]。選取局部的極值點：根據給定的閾值，采用非極大值抑制的方法對不符合條件的極值進行置零處理，以確定最終的特征點。

2.3 SIFT特征點檢測

1999年，Lowe首次提出關于尺度不變特征變換（SIFT）局部特征。該算法對于旋轉，仿射變換和視點變化方面比其他方法更 具有魯棒性和高效性。SIFT算法在灰度圖像特征檢測中顯示了相當不錯的性能。SIFT算法的過程可以簡述如下。

階段1：SIFT在高斯（DoG）標度空間的差異中檢測局部極值。輸入圖像f(x,y)與具有不同尺度kσ的高斯濾波器G(x,y,kσ)卷積以獲得尺度空間L(x,y,kσ)，k= 1,2...,?。隨后，可以通過獲得DoG標度空間：

其中D(x,y,σ)是高斯差分圖像，G(x,y,σ)是高斯濾波器，L(x,y,σ)是比例空間的比例表示。在DoG空間中，可以使用搜索局部極值的方法判斷來尺度和方向不變的潛在興趣點。當地的極值是第二階段標記的關鍵點的候選者。

圖1顯示了高斯尺度空間金字塔，高斯金字塔在差異里創建了一個區間。為了觀察并得到G(x,y,σ)的局部最大值和最小值，把所有的采樣點和其圖像中的上面八個鄰居點和下面九個鄰居點相比較。

圖1 高斯尺度空間金字塔在差異里創建一個區間

圖2 高斯差分圖像中的最大值和最小值檢測

階段2：通過選擇符合詳細定義模型要求的局部極值來定位關鍵點。在該模型中，在DoG空間的不同尺度上具有高穩定性的候選點被標記為關鍵點。

階段3：有關局部圖像梯度方向將一種或多種取向分到所有關鍵點位置。所有做法都是對比于所有特征的指定方位，由比例與位置發生變換的圖像數據所處理的，進而給上述變換提供不變性。

階段4：最終生成關鍵點描述符。它使用梯度幅度m(x,y)與方向θ(x,y)作為描述符中的基本元素，它們的定義如下：

原算法的描述子因為維數太高，這導致構建特征描述子以及最后進行匹配都需要很長時間。也因為關鍵點的增加錯誤匹配概率上升，剔除錯誤匹配的耗時增加，很難滿足對時間的要求。由于關鍵點的特征描述子不僅與該點所在的像素有關，也和該點周圍的像素區域有關，它們對描述子的貢獻與距離的大小成正比，因此還要考慮距離的問題，對各個區域與關鍵點的距離進行加權，得到新的特征描述子[5]。圓形區域比正方形區域含有更少的像素點，剔除了邊緣易受干擾的像素點，使得計算梯度描述子的時間有所縮短，相似性加強。

如圖3，在圓形部分劃分8個小區域用公式（3）、（4）計算每個像素的幅值與幅角。圓形分為8個區域即45度為一個區域。每個像素點根據其幅角判斷位置，找到后進行高斯加權并加到相關區域。加權系數為：

圖3 新描述子和梯度方向

(i0,j0),(i,j)分別為所求像素點和中心點在待描述圖像區域中的坐標，σ0為選定的常數[6]，這樣就得到了64維梯度描述子。

3 圖像匹配方法

為加快速度，本文對提取的特征點進行構建二維KD樹。通過 KD 樹搜索鄰近點后利用比值提純法獲取粗匹配。再利用RANSAC剔除錯誤匹配

RANSAC其本身就是依據一組含有非正確數據的樣本數據集。RANSAC是為得到正確且有效的數據的方法，其通過計算解得數據本身的模型參數。它于1981年由 Fischler和Bolles最先提出。RANSAC算法的基本假設是樣本中包含正確數據，也包含異常數據，即數據集中含有噪聲。得到的錯誤數據有一部分原因是因為測量時出現誤差、假設預期相差很多、計算出現錯誤。給出進行解決所需要正確參考數據，在給出數據時RANSAC則需要假設，這樣就是能夠找到計算出最適合給出數據的模型參數的算法。

因為是使用一幅圖像，那么能夠把它定義成剛性的。這樣能夠在pattern image與query image的不同特征點間尋找其中單應性變換。若是發現能夠發現單應性變換，那么就可以運用RANSAC來找到合適的單應性矩陣。這樣就可以剔除一部分錯誤匹配。

4 實驗平臺搭建

本實驗是在Windows 7 系統下以Matlab 2016B作為開發環境，圖3為經典的Lena照片，第二張為稍微旋轉之圖像，圖4—圖6為幾種算法的效果圖。圖7—圖9為另一幅圖片幾種算法的效果圖。表1為幾種算法效果數字比較。

圖3 Lena照片與稍微旋轉片

圖4 SIFT檢測

圖5 SURF檢測

圖6 本文算法

圖7 SIFT檢測

圖8 SURF檢測

圖9 本文算法

表1 幾種算法效果數字比較

改進后的新算法具有相對不錯的魯棒性，跟SIFT相比，新算法因為角點檢測去篩選了邊緣信息小的點，信息密集的點則用了改進的SIFT算法。所以可以有效提高準確率，匹配精度?？梢愿玫耐瓿蔀槿S重建的匹配工作。

5 結論

本文提出的改進算法不僅在低頻部分運用了小波變換與角點檢測，而且新算法也改變了原描述子，以此來降低維度，提高匹配的實時性。之后實驗首先用KD樹做粗匹配，再用RANSAC來找到合適的單應性矩陣。這樣就可以剔除一部分錯誤匹配。新算法匹配正確率有了相對不錯的提高，這樣就能更好地應用在三維重建中去。