改進SIFT算法的圖像雙向配準技術

劉清清，李士心，孫夏麗，王 坤

（天津職業技術師范大學大學電子工程學院，天津 300222）

近年來，圖像配準技術被廣泛應用于醫學圖像分析、遙感圖像處理、計算機視覺、集成電路圖像拼接等領域，隨著對圖像配準研究的不斷深入，多領域的應用場景對圖像配準技術的需求也越來越高。目前，實現圖像配準技術的算法主要分為基于灰度信息、變換域和特征匹配。其中，基于特征的圖像配準根據選取特征屬性的不同可細分為若干方法，如基于線特征的Hough變換、基于輪廓特征的Log算子、Sobel邊緣提取算子、Canny邊緣檢測算子等，以及目前應用最為廣泛的基于特征點配準的SIFT算法等[1]。本文主要針對基于尺度不變特征變換（scale-invariant feature transform，SIFT）算法的k-d樹配準算法進行分析并改進。SIFT是一種具有尺度不變性的局部特征描述子，可以檢測并描述輸入圖像中的極值點[2]，該特征點對待配準圖像的旋轉、尺度、亮度等因素保持不變性，因此該算法適用于多種場景[3]。但是，由于一個特征點具有多維描述子，且特征描述子的數量與圖像配準的速度成正比，故傳統的k-d樹單向匹配算法易出現錯誤匹配，同時也無法滿足實際應用的實時性。因此，本文在SIFT描述子匹配階段，采用準歐氏距離代替歐氏距離，匹配效率顯著提高。

1 基于SIFT算法的圖像配準

1.1 特征點檢測

1.1.1 構建尺度空間

SIFT算法在構建尺度空間時采取高斯核函數進行濾波來模擬各個尺度下的特征情況，使待配準圖像保留更多的信息以便后續進行特征的提取與匹配[4]。通過將待配準圖像與具有可變核的高斯濾波進行卷積，從而得到圖像的高斯金字塔Log。高斯卷積核是唯一可以實現尺度變換的線性變換核，尺度空間圖像即為初始圖像與不同尺度參數σ進行卷積運算所產生的圖像，圖像I（x，y）的尺度空間L（x，y，σ）表達式為

式中：G（x，y，σ）為二維高斯函數；I（x，y）為原始圖像中某點的像素值；σ為尺度因子，σ值越大，代表初始圖像被平滑得越多，對應的圖像尺度越大[5]。

1.1.2 構建高斯金字塔

為了在尺度空間有效檢測到穩定的關鍵點，SIFT算法使用了高斯差分尺度空間算子DOG（difference of Gaussian），DOG算子定義為不同尺度的高斯差分核與圖像卷積，其是歸一化高斯拉普拉斯算子Log的近似[6]，表示為

高斯差分金字塔的生成如圖1所示。圖像的金字塔模型是指將原始圖像不斷降階采樣，得到一系列大小不一的圖像，由大到小、從下到上構成的塔狀模型。初始圖像為金字塔的第一層，每組中相鄰上下兩層圖像相減，下一層的圖像是由上一層圖像降采樣而得。

圖1 高斯差分金字塔的生成

1.1.3 DOG局部極值點檢測

SIFT算法中的特征點是由高斯差分尺度空間中的局部極值點組成，在建立高斯差分金字塔尺度空間后，將每個像素點與其同一尺度以及上下相鄰尺度的26個像素點作比較，局部極值點檢測如圖2所示。

圖2 局部極值點檢測

若某檢測點比其圖像域與尺度域的相鄰點大或小，該點即為該尺度上的局部極值點[7]。對于每組圖像的首尾兩層需人為使用高斯模糊生成2幅圖像，以尋找首尾兩層的極值點，滿足尺度變化的連續性。

1.1.4 消除不合格關鍵點

DOG算子會產生較強的邊緣響應，為了提高圖像配準的穩定性和準確性，通過對檢測出的極值點進行差分處理，擬合3位二次函數確定特征點的位置和尺度，消除低對比度和不穩定的邊緣響應點。

利用DOG函數在尺度空間的Taylor展開式對尺度空間DOG函數進行曲線擬合，其擬合函數表示為

式中：X=（x，y，σ）T。

對Taylor展開式求導，并令其導數為0，得到極值點的偏移量為

通過控制偏移量，可以消除低對比度的極值點。

由于DOG對圖像中的邊緣有比較強的響應值，如果極值點在圖形的邊緣上，這些點就是不穩定的點。在邊緣梯度的橫向方向上主曲率值比較大，而沿著邊緣垂直方向則主曲率值較小，主曲率可以通過2×2的Hessain矩陣H求出

式中：Dxx、Dxy、Dyy是由極值點鄰域對應位置的差分得到的。

令H的特征值α和β表示x和y方向的梯度，特征值α較大、β較小，D的主曲率與H的特征值成正比，則

Tr（H）是矩陣H的對角線元素之和，Det（H）是矩陣H的行列式。令α=γβ，則

若上式成立，則保留該極值點，否則剔除該極值點[8]。

1.1.5 關鍵點的方向分配

上述步驟確定了特征點的尺度和位置，保證了SIFT算子的尺度不變性。此外，特征點還具有旋轉不變性，通過利用圖像的局部結構特征計算關鍵點的方向。采集特征點所在DOG金字塔圖像3σ鄰域像素的梯度m（x，y）和方向θ（x，y）分布特征，如

計算出特征點的梯度后，通過直方圖統計鄰域像素的梯度和幅值。直方圖以梯度方向角為橫軸，將0°～360°劃分為若干個區間，以各梯度方向角所對應的幅值累加值為縱軸[9]。直方圖的峰值即為該像素點的主方向，大于主峰值80%的方向為輔方向。

1.2 生成特征點描述子

為保證特征點的獨特性，提高圖像配準的準確率，對于每個特征點用一組向量描述，生成特征點描述子。旋轉坐標軸的方向使坐標軸與特征點方向保持一致，選取以特征點為中心的16×16大小的區域窗口。特征描述子的生成如圖3所示。

圖3 特征描述子的生成

從圖3可知，特征點位于正中間，特征點鄰域所在尺度空間的像素由左側的每一個小方格表示，像素的梯度模值和梯度方向分別由右側的每個箭頭的長度和方向表示。對每個像素進行高斯加權運算，鄰域像素越靠近特征點，梯度方向信息的價值就越大[10]。計算左側每4×4個方格區域中8個方向的梯度方向直方圖，根據梯度方向形成如右側的種子點。每個特征點最終由4×4個種子點組成，每個種子點共包含8個方向的梯度信息。對于每個特征點形成一個4×4×8=128維的描述子，每一維都可以代表相應4×4方格的尺度或方向，即生成了128維的特征向量描述子。

1.3 基于k-d樹的單向配準

SIFT特征點的相似度可以由特征向量的歐氏距離度量，歐氏距離是一個經常引用的距離定義，是指在n維空間中向量的自然長度（即該點到原點的距離）或2個點的真實距離。以待配準圖像中的某個特征點為基準，找到原圖像中與待配準圖像的特征點歐氏距離最鄰近的特征點和次鄰近的特征點，若最近的距離除以次鄰近的距離的值低于設定的閾值時，則即為匹配點[11]。通常以0.8為比例閾值，但實際應用中該閾值由待配準圖像的大小、亮度等因素決定，合理的閾值可以提高配準的準確度。

搜索最鄰近點和次鄰近點通常采用窮舉策略，即根據原圖像中的某一特征點與待配準圖像中的特征點逐一匹配，該策略需要遍歷所有特征描述子，搜索效率不高。本文采用k-d樹對鄰近點進行搜索匹配，先建立k-d樹，對特征描述子數據進行分類整理，從根節點出發，根據索引樹朝鄰近點所在的方向逼近，直至找到包含目標點的的葉子節點，計算葉子節點的歐氏距離，找到最鄰近和次鄰近的特征點進行匹配。

構建k-d樹是一個逐級展開的遞歸過程[12]。首先確定分割域的取值，計算特征描述子的特征向量在每個維度上的數據方差，方差最大的值相對應的維數即為分割域的值；確定節點數據的域值，所有特征描述符向量按照分割域的值排序，中位數即為節點數據；確定左子空間和右子空間，分割平面將整個空間分為2部分，分割域中小于節點數據的特征描述符向量對應的特征點為左子空間，大于節點數據的特征描述符向量對應的特征點則為右子空間。對左、右子空間內的數據分別重新遍歷根節點，即可得到下一級的子節點，同時將空間和數據集再進一步細分，如此反復直到空間中只包含1個數據點。從根節點到葉子節點所遍歷的所有節點構成了葉子節點的索引。

特征匹配另一個重要環節是在k-d樹中查找數據，其目的是找到在k-d樹中與特征點距離最近的數據點。從k-d樹的根節點開始搜索，若待查詢節點小于k-d樹節點分割域的值，則優先搜索左子樹分支，反之，則搜索右子樹分支。順著搜索路徑找到葉子節點，該葉子節點對應的特征點為最近鄰特征點的概率最大。沿搜索路徑回溯到其父節點，在該父節點的其他分支反向查找是否有距離特征點更近的數據點和次鄰近點，若無更近的數據點，則該葉子節點為最近鄰特征點；若有更近的數據點，則需繼續搜索其他路徑，直至搜索路徑全部回溯完畢。

2 改進算法與實驗結果

2.1 改進算法

傳統的配準算法是從k-d樹的父節點開始向下搜索至葉子節點，根據原圖像中的特征點搜索待配準圖像中對應的特征點，具有單向匹配性。每個像素點具有多個方向向量，方向不同屬于不同的特征描述子，但實際為同一像素點，匹配時易出現同一點重復匹配的情況，采取雙向匹配即可消除大部分重復的匹配點[13]。

傳統的圖像匹配采用歐氏距離度量特征點的相似性，在二維圖像中歐氏距離定義為

本文采用準歐氏距離進行圖像配準，準歐氏距離定義為

根據定義可以看出，計算準歐氏距離明顯比計算歐氏距離運算簡單，求得的數值普遍偏小，采用準歐氏距離可明顯縮短運算時間，提高了算法的匹配效率[14]。

雙向匹配即在傳統的配準算法基礎上，反向搜索已被匹配的特征點在原圖像中與之匹配的特征點，若正向匹配與反相匹配中2點的準歐氏距離小于設定的閾值，則該2點即為正確的匹配點。

式中：D（xi，yj）、D（yj，xi）分別為原圖像和待配準圖像中一對匹配點的正向和反向的準歐氏距離；r1和r2分別為正向閾值和反向閾值，若滿足上式，則xi和yj為一對正確的匹配點[15]。

2.2 實驗結果與分析

實驗在Widows 10環境下采用Matlab 2017和C編程對本文提出的改進SIFT算法的圖像雙向配準算法進行實現，2組實驗圖片分別通過室外自然光和室內光線下手機拍攝獲取，對2幅不同光照、不同角度的圖片進行特征匹配，通過特征點匹配正確率進行定量分析[16-17]。室外自然光線下和室內光線下基于SIFT特征的圖像配準分別如圖4、圖5所示。

圖4 室外自然光線下基于SIFT特征的圖像配準

圖5 室內光線下基于SIFT特征的圖像配準

在室外光線下，通過平移、對焦等操作采集具有重疊部分的圖片，原圖像共檢測出866個特征點，待配準圖像共檢測出977個特征點。在室內光線下，拍攝時通過平移、旋轉、縮放等操作采集具有重疊部分的圖片，原圖像共檢測出572個特征點，待配準圖像共檢測出724個特征點。室外、室內拍攝的2組圖片分別基于SIFT特征的傳統單向配準結果與改進的SIFT特征的圖像雙向匹配的數據結果如表1所示。

表1 圖像匹配數據（基于歐氏距離的單向配準/基于準歐氏距離的雙向配準）

通過對比不同光線下的2組圖片采用2種方法匹配的數據可以看出，改進后的算法在匹配點對數上分別減少68對、30對，錯誤匹配點數分別為52對、36對，與傳統配準方法相比，匹配正確率約提高6%，但時間卻縮短為原來的69%。故本文提出的改進算法在實際應用中有效提高了圖像配準技術的效率和質量。

3 結語

本文分析了SIFT特征的提取、描述過程，介紹了SIFT特征基于k-d樹單向配準的方法，并提出一種改進的配準算法，采用準歐氏距離代替歐氏距離進行運算，縮短了運算時間，提高了配準的速度，且使用雙向配準的方法進行特征點匹配，有效消除了部分誤匹配點與重復匹配點，提高了圖像配準的準確度。實驗結果表明，本文提出的改進算法在保證特征點匹配性能的前提下，有效提高了圖像配準的速度和正確率，對日后基于SIFT算法的圖像配準技術在各領域的應用研究具有一定的借鑒意義。