易 飛, 許珊珊

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

1 引言

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

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

本文將SIFT算法的128維數(shù)據(jù)根據(jù)8個(gè)梯度方向分成8組, 并根據(jù)梯度模值的大小對(duì)這8個(gè)梯度方向建立索引, 將索引添加入關(guān)鍵點(diǎn)的信息結(jié)構(gòu)中.重新定義每個(gè)關(guān)鍵點(diǎn)的信息, 產(chǎn)生新的有序描述子, 進(jìn)而提出一種改進(jìn)的SIFT算法.

2 SIFT 算法簡(jiǎn)介

2.1 尺度空間極值檢測(cè)

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

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

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

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

圖1 高斯差分尺度空間

2.2 關(guān)鍵點(diǎn)生成

(1)關(guān)鍵點(diǎn)檢測(cè);為了尋找尺度空間的極值點(diǎn), 每一個(gè)采樣點(diǎn)要和它所有的相鄰尺度對(duì)應(yīng)的26個(gè)點(diǎn)進(jìn)行比較, 如果它是其中的最大或最小值時(shí), 就認(rèn)為該點(diǎn)是圖像在該尺度下的一個(gè)關(guān)鍵點(diǎn), 圖2所示為尺度空間尋找到極值點(diǎn).

圖2 關(guān)鍵點(diǎn)

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

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

2.3 關(guān)鍵點(diǎn)特征信息的建立

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

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

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

圖3 關(guān)鍵點(diǎn)的 4×4像素點(diǎn)區(qū)域

3 算法的改進(jìn)

通過以上對(duì)SIFT算法的理解與分析, 本文將從兩個(gè)方面進(jìn)行改進(jìn).

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

圖4 關(guān)鍵點(diǎn)梯度方向的索引

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

4 算法的實(shí)現(xiàn)

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

圖5 原 SIFT算法的匹配方式

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

在圖像匹配過程中, 本文算法在原SIFT算法的基礎(chǔ)上進(jìn)行了刪除匹配成功的關(guān)鍵點(diǎn)處理, 這樣可以減少循環(huán)匹配次數(shù).

當(dāng)兩幅圖像進(jìn)行圖像匹配時(shí), 其處理步驟如下;

1) 建立尺度空間, 得到極值點(diǎn), 根據(jù) Hessian 矩陣得到圖像的關(guān)鍵點(diǎn);

2) 根據(jù)關(guān)鍵點(diǎn)鄰域梯度方向, 利用梯度直方圖, 得到關(guān)鍵點(diǎn)的梯度方向;

3) 根據(jù)關(guān)鍵點(diǎn)的梯度方向建立索引, 構(gòu)建關(guān)鍵點(diǎn)的四個(gè)特征信息;位置、所處尺度、方向、索引;

4) 根據(jù)索引號(hào), 建立關(guān)鍵點(diǎn)的8組16維向量的描述子;

5) 根據(jù)關(guān)鍵點(diǎn)的描述子進(jìn)行匹配.

圖6 本文算法的匹配方式

5 實(shí)驗(yàn)結(jié)果及分析

本文實(shí)驗(yàn)平臺(tái)為 64位 Windows 8 操作系統(tǒng), 酷睿 i5-4210U 處理器, 4G內(nèi)存, 采用 VS2010+OPENCV 2.4.9的編譯環(huán)境, 保證實(shí)驗(yàn)環(huán)境一致.

5.1 不同關(guān)鍵點(diǎn)數(shù)量測(cè)試

本組實(shí)驗(yàn)為圖片不做變動(dòng), 但是圖像關(guān)鍵點(diǎn)不一致, 將匹配點(diǎn)數(shù)設(shè)置為100進(jìn)行測(cè)試, 計(jì)算原SIFT算法和本文的改進(jìn)SIFT算法圖像匹配所需運(yùn)行時(shí)間, 實(shí)驗(yàn)結(jié)果如圖7至圖9和表1所示.圖7(a)表示為原算法運(yùn)行時(shí)間, (b)表示為改進(jìn)后關(guān)鍵點(diǎn)數(shù)在600左右時(shí)算法的運(yùn)行時(shí)間;圖8(a)表示為原算法運(yùn)行時(shí)間,(b)表示為改進(jìn)后關(guān)鍵點(diǎn)數(shù)在1700左右時(shí)算法的運(yùn)行時(shí)間;圖9(a)表示為原算法運(yùn)行時(shí)間, (b)表示為改進(jìn)后關(guān)鍵點(diǎn)數(shù)在2100左右時(shí)算法的運(yùn)行時(shí)間.

圖7 A 組實(shí)驗(yàn)對(duì)比圖

圖8 B 組實(shí)驗(yàn)對(duì)比圖

圖9 C 組實(shí)驗(yàn)對(duì)比圖

表1 關(guān)鍵點(diǎn)不一致時(shí)的匹配數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)表明, 當(dāng)關(guān)鍵點(diǎn)為600左右時(shí), 改進(jìn)后算法運(yùn)算時(shí)間大概減少了2秒, 運(yùn)算速度提高了66.7%,當(dāng)關(guān)鍵點(diǎn)在1500左右時(shí), 算法運(yùn)行時(shí)間提高了2.8秒左右, 運(yùn)算速度提高了51.9%, 當(dāng)關(guān)鍵點(diǎn)在2000以上時(shí), 算法運(yùn)行時(shí)間提高了4.02秒左右, 運(yùn)算速度提高了57.1%左右.

5.2 像尺度變換后的配準(zhǔn)測(cè)試

本組實(shí)驗(yàn)將圖片旋轉(zhuǎn)之后進(jìn)行測(cè)試.其中A組為原圖向右旋轉(zhuǎn)10度, 設(shè)置匹配點(diǎn)數(shù)為100得到的匹配結(jié)果.B組為原圖向左旋轉(zhuǎn)30度, 設(shè)置匹配點(diǎn)數(shù)為20得到的匹配結(jié)果.實(shí)驗(yàn)結(jié)果如圖10, 圖11和表2所示.

圖10第一幅圖表示原圖向右旋轉(zhuǎn)10度, 設(shè)置匹配點(diǎn)數(shù)為100后, 原算法得到的匹配結(jié)果, 第二幅圖表示改進(jìn)后算法所得到的匹配結(jié)果.圖11第一幅圖表示原圖向左旋轉(zhuǎn)30度, 設(shè)置匹配點(diǎn)數(shù)為20后原算法得到的匹配結(jié)果, 第二幅圖表示改進(jìn)后算法所得到的匹配結(jié)果.本組實(shí)驗(yàn)表明, 改進(jìn)后的算法依舊對(duì)圖像旋轉(zhuǎn),拉伸具備良好的魯棒性, 但當(dāng)匹配數(shù)據(jù)不大時(shí), 所獲得的時(shí)間提升沒有太過明顯.當(dāng)數(shù)據(jù)量越來越大時(shí), 算法在運(yùn)算速度上的優(yōu)勢(shì)才能得到體現(xiàn).

圖10 A組原算法與改進(jìn)后算法的對(duì)比

圖11 B組原算法與改進(jìn)后算法的對(duì)比

表2 圖像尺度變換后的配準(zhǔn)測(cè)試數(shù)據(jù)

5.3 光照、遮蔽測(cè)試

本組實(shí)驗(yàn)?zāi)康氖菧y(cè)試改進(jìn)算法對(duì)于光照變化和遮蔽是否仍然具備魯棒性, 其中A組實(shí)驗(yàn)為光照變換之后, 改進(jìn)后算法是否依然具備魯棒性, 以及與原算法之間的對(duì)比, B組實(shí)驗(yàn)為當(dāng)有遮蔽物時(shí)的測(cè)試.實(shí)驗(yàn)結(jié)果如圖12至圖15和表3所示.圖12表示為原算法在光照變化情況下的匹配結(jié)果;圖13表示為改進(jìn)后算法在光照變化情況下的匹配結(jié)果;圖14表示為原算法在遮蔽情況下的匹配結(jié)果;圖15表示為改進(jìn)后算法在遮蔽情況下的匹配結(jié)果.

圖12 A 組原算法光照

圖13 A 組改進(jìn)后算法光照

圖14 B 組原算法遮蔽

圖15 B 組改進(jìn)后算法遮蔽

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

表3 光照、遮蔽測(cè)試數(shù)據(jù)

5.4 加入椒鹽噪聲測(cè)試

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

圖16 A 組實(shí)驗(yàn)對(duì)比圖

表4 加入噪聲測(cè)試數(shù)據(jù)

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

6 結(jié)束語(yǔ)

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