基于SIFT的圖像匹配方法改進①

易 飛, 許珊珊

(湘潭大學 信息工程學院, 湘潭 411105)

1 引言

圖像配準是圖像處理中的一種重要的處理技術,一般指將不同時間、不同傳感器(成像設備)或不同條件下(天候、照度、攝像位置和角度等)獲取的兩幅或多幅圖像進行匹配、疊加的過程, 它已經被廣泛地應用于計算機視覺、遙感圖像處理等領域.其中,圖像之間的特征匹配是圖像配準的重要研究內容.

Lowe[1]在1999年提出的SIFT算法是圖像匹配算法中魯棒性比較好的一種算法, 也是目前比較成功的一種算法, 該算法具有良好的平移特性, 并且對光照、尺度變化保持不變性.但是SIFT算法對每個關鍵點形成一個 4×4×8=128維的描述子, 計算量大；同時, 對于邊緣點較少的圖像, 提取的關鍵點較少.因此, 國內外許多學者針對SIFT算法進行了深入的研究, 并提出了許多改進算法[2–15].例如, Bay 等[2]提出了 SURF算法,其通過計算積分圖像和Fast-Hessian矩陣, 大大提高了關鍵點檢測速度, 但它的旋轉不變性比SIFT算法差.YanKe[3]在 2004年提出了PCA-SIFT算法, 其對SIFT特征描述符采用PCA降維, 大幅減少了運算時間, 但角點的檢測精度有所降低, 在實際應用中效果不太理想.林曉帆[4]提出了基于SURF描述子的遙感圖像配準, 在算法匹配效率上得到了極大的改進, 但該算法重點關注遙感圖像的配準.芮挺[5]等提出了基于SIFT描述的Harris角點多源圖像配準, 在匹配效率和精度兩方面都有很好的改進.張少敏[6]提出了融合SIFT特征的熵圖估計醫學圖像非剛性匹配, 實現了具有良好魯棒性的醫學圖像配準.這些都是基于某個領域內對匹配算法的改進, 適用范圍有一定的局限性.還有學者[7–10]提出對數據進行分組處理, 但是沒有對分組進行規則限制, 導致匹配率降低.

本文將SIFT算法的128維數據根據8個梯度方向分成8組, 并根據梯度模值的大小對這8個梯度方向建立索引, 將索引添加入關鍵點的信息結構中.重新定義每個關鍵點的信息, 產生新的有序描述子, 進而提出一種改進的SIFT算法.

2 SIFT 算法簡介

2.1 尺度空間極值檢測

為了進行圖像尺度空間極值檢測, 首先要對圖像建立尺度空間;尺度空間理論目的是模擬圖像數據的多尺度特征.采用高斯卷積核是實現尺度變換, 將一副二維圖像的尺度空間定義為;

其中,G(x,y,δ)是尺度可變高斯函數;

式(1)(2)中δ大小決定圖像的平滑程度,δ值越大圖像分辨率越低,I為圖像,L為尺度空間.為了有效的在尺度空間檢測到穩定的關鍵點, 提出了高斯差分尺度空間.利用不同尺度的高斯差分核與圖像卷積生成,公式如下;

對于任意圖像, 建立其高斯差分尺度空間, 即圖像金字塔, 如圖1所示.

圖1 高斯差分尺度空間

2.2 關鍵點生成

(1)關鍵點檢測;為了尋找尺度空間的極值點, 每一個采樣點要和它所有的相鄰尺度對應的26個點進行比較, 如果它是其中的最大或最小值時, 就認為該點是圖像在該尺度下的一個關鍵點, 圖2所示為尺度空間尋找到極值點.

圖2 關鍵點

在極值比較的過程中, 每一組圖像的首末兩層是無法進行極值比較的, 為了滿足尺度變化的連續性, 在每一組圖像的頂層繼續用高斯模糊生成了3幅圖像.

(2)不合格關鍵點的剔除;利用泰勒二次展開式(公式(4))擬合曲線, 然后通過該點尺度位置2×2的Hessian矩陣(公式(5))計算其主曲率, 來去掉高斯差分尺度空間局部曲率不對稱的關鍵點.

2.3 關鍵點特征信息的建立

(1)確定關鍵點主方向;關鍵點鄰域像素的梯度方向分布特性為每個關鍵點指定方向參數, 使算子具備旋轉不變性.利用梯度直方圖統計鄰域像素的梯度方向, 梯度直方圖的范圍是0～360度, 其中每45度一個柱, 總共 8個柱, 或者每 10度一個柱, 總共 36個柱, 計算時一般采用8個柱的方式.公式(6)和公式(7)為幅值和梯度方向計算方法.

(2)直方圖中的峰值就是主方向, 其他達到最大值80%的可作為輔助方向.這時, 每個關鍵點有三個特征信息;位置、所處尺度、方向.

(3)建立描述子;確立好主方向后, 將坐標軸旋轉為關鍵點的方向, 以確保圖像旋轉不變性.以關鍵點為中心取 4×4的像素點區域, 如圖 3所示.Lowe[1]建議描述子使用在關鍵點尺度空間內4×4的像素點區域中計算的8個方向的梯度信息, 共4×4×8=128維向量表征.

圖3 關鍵點的 4×4像素點區域

3 算法的改進

通過以上對SIFT算法的理解與分析, 本文將從兩個方面進行改進.

(1)關鍵點特征信息的改造;原算法每個關鍵點包含三個特征信息;位置、所處尺度、方向.由于梯度模值越大, 即箭頭越長, 所表示該方向所占關鍵點方向比重越大.因此, 本文根據梯度模值即箭頭長度大小, 由大到小建立索引(如圖4所示), 若大小相同, 則按照逆時針方向順序設置.加入索引后, 并不改變該關鍵點的主方向.加入索引后, 方便在進行匹配時的檢索處理,提高運行效率.因此, 本文每個關鍵點包含四個特征信息;位置、所處尺度、方向、索引.

圖4 關鍵點梯度方向的索引

(2)關鍵點描述子的分解;原SIFT算法表征描述子的是128維向量.根據關鍵點梯度方向的8個索引方向, 可將原描述子的128維向量分成8組16維的向量.每組數據可以單獨計算, 也可以并行處理, 提高效率.這樣, 得到關鍵點的8組16維向量的描述子.

4 算法的實現

原SIFT算法在圖像關鍵點進行匹配時, 基準圖像中關鍵點描述子表示為向量;Si= (si1,si2,···,si128), 待匹配圖像中關鍵點描述子表示為向量;Ri=(ri1,ri2√,···,ri128), 任 意 兩 描 述 子 相 似 性 度 量 用來計算.而本文算法的基準圖像中關鍵點描述子用8組不同的向量Ti=(ti1,ti2,···,ti16)來表示, 待匹配圖像中關鍵點描述子也用8組不同的Hi=(hi1,hi2√,···,hi16)來表示, 描述子相似性度量可以用進行計算,計算復雜度明顯降低.

圖5 原 SIFT算法的匹配方式

從原SIFT算法的匹配方式(圖5)和本文算法的匹配方式(圖6)可以看出, 原算法采用的是全匹配方式, 對兩個SIFT特征向量采用1NN的匹配方式, 這樣在關鍵點較多情況下, 會大大增加運行負擔.而在加入索引后, 根據索引不同, 只需要計算其索引相同的16維數據, 這樣大大提高了運行效率.實驗表明, 在關鍵點達到2000時, 匹配速度提高了大約57.1%左右.

在圖像匹配過程中, 本文算法在原SIFT算法的基礎上進行了刪除匹配成功的關鍵點處理, 這樣可以減少循環匹配次數.

當兩幅圖像進行圖像匹配時, 其處理步驟如下;

1) 建立尺度空間, 得到極值點, 根據 Hessian 矩陣得到圖像的關鍵點;

2) 根據關鍵點鄰域梯度方向, 利用梯度直方圖, 得到關鍵點的梯度方向;

3) 根據關鍵點的梯度方向建立索引, 構建關鍵點的四個特征信息;位置、所處尺度、方向、索引;

4) 根據索引號, 建立關鍵點的8組16維向量的描述子;

5) 根據關鍵點的描述子進行匹配.

圖6 本文算法的匹配方式

5 實驗結果及分析

本文實驗平臺為 64位 Windows 8 操作系統, 酷睿 i5-4210U 處理器, 4G內存, 采用 VS2010+OPENCV 2.4.9的編譯環境, 保證實驗環境一致.

5.1 不同關鍵點數量測試

本組實驗為圖片不做變動, 但是圖像關鍵點不一致, 將匹配點數設置為100進行測試, 計算原SIFT算法和本文的改進SIFT算法圖像匹配所需運行時間, 實驗結果如圖7至圖9和表1所示.圖7(a)表示為原算法運行時間, (b)表示為改進后關鍵點數在600左右時算法的運行時間;圖8(a)表示為原算法運行時間,(b)表示為改進后關鍵點數在1700左右時算法的運行時間;圖9(a)表示為原算法運行時間, (b)表示為改進后關鍵點數在2100左右時算法的運行時間.

圖7 A 組實驗對比圖

圖8 B 組實驗對比圖

圖9 C 組實驗對比圖

表1 關鍵點不一致時的匹配數據

實驗數據表明, 當關鍵點為600左右時, 改進后算法運算時間大概減少了2秒, 運算速度提高了66.7%,當關鍵點在1500左右時, 算法運行時間提高了2.8秒左右, 運算速度提高了51.9%, 當關鍵點在2000以上時, 算法運行時間提高了4.02秒左右, 運算速度提高了57.1%左右.

5.2 像尺度變換后的配準測試

本組實驗將圖片旋轉之后進行測試.其中A組為原圖向右旋轉10度, 設置匹配點數為100得到的匹配結果.B組為原圖向左旋轉30度, 設置匹配點數為20得到的匹配結果.實驗結果如圖10, 圖11和表2所示.

圖10第一幅圖表示原圖向右旋轉10度, 設置匹配點數為100后, 原算法得到的匹配結果, 第二幅圖表示改進后算法所得到的匹配結果.圖11第一幅圖表示原圖向左旋轉30度, 設置匹配點數為20后原算法得到的匹配結果, 第二幅圖表示改進后算法所得到的匹配結果.本組實驗表明, 改進后的算法依舊對圖像旋轉,拉伸具備良好的魯棒性, 但當匹配數據不大時, 所獲得的時間提升沒有太過明顯.當數據量越來越大時, 算法在運算速度上的優勢才能得到體現.

圖10 A組原算法與改進后算法的對比

圖11 B組原算法與改進后算法的對比

表2 圖像尺度變換后的配準測試數據

5.3 光照、遮蔽測試

本組實驗目的是測試改進算法對于光照變化和遮蔽是否仍然具備魯棒性, 其中A組實驗為光照變換之后, 改進后算法是否依然具備魯棒性, 以及與原算法之間的對比, B組實驗為當有遮蔽物時的測試.實驗結果如圖12至圖15和表3所示.圖12表示為原算法在光照變化情況下的匹配結果;圖13表示為改進后算法在光照變化情況下的匹配結果;圖14表示為原算法在遮蔽情況下的匹配結果;圖15表示為改進后算法在遮蔽情況下的匹配結果.

圖12 A 組原算法光照

圖13 A 組改進后算法光照

圖14 B 組原算法遮蔽

圖15 B 組改進后算法遮蔽

A組實驗表明, 改進后算法對光照變換依然具備較好魯棒性, 同時, 在關鍵點大概在 500左右時, 相較于原算法運行時間提高了大約0.5秒.B組實驗證明了改進后算法對于圖像在有遮蔽情況下, 依然具備良好的魯棒性, 相較于原算法運行時間縮短了大約0.4秒,驗證了改進后算法確實加快了運行速度, 降低了時間復雜度, 表明了采用本文降維的方式能提高算法的效率.

表3 光照、遮蔽測試數據

5.4 加入椒鹽噪聲測試

本文利用opencv在圖像中加入椒鹽噪聲, 來測試改進算法是否具備魯棒性.實驗結果如圖16和表4所示.圖16第一幅圖表示加入噪聲后原算法得到的匹配結果, 第二幅圖表示改進后算法所得到的匹配結果.

圖16 A 組實驗對比圖

表4 加入噪聲測試數據

從表4可以看出, 改進后算法任然對噪聲圖像保持魯棒性, 在配準時間上依然具備競爭力, 配合索引,在效率方面得到了很大的提高.

6 結束語

本文針對圖像配準經典算法-SIFT算法中關鍵點的特征信息進行改造, 并將原描述子的128維數向量據根據8個梯度方向分成8組, 建立分組的描述子向量, 提出了一種改進的 SIFT 算法.數值實驗表明, 本文改進后的算法能夠在保持原算法的光照不變性、旋轉不變性、以及關鍵點的匹配精度的情形下, 有效地提高了算法的效率.