基于感知哈希與尺度不變特征變換的快速拼接算法

要小濤, 王正勇, 石 偉, 卿粼波, 何小海

(1.四川大學(xué)電子信息學(xué)院， 成都 610065； 2.中國民航局第二研究所， 成都 610041)

1 引 言

圖像拼接是指將具有互相重合部分的圖像融合為一張更大視域圖像的技術(shù). 近年來, 這項(xiàng)技術(shù)在無人機(jī)勘測、衛(wèi)星遙感、三維重建以及增強(qiáng)現(xiàn)實(shí)等諸多領(lǐng)域發(fā)揮著重大的作用[1-4].圖像拼接技術(shù)一般分成特征點(diǎn)提取、特征點(diǎn)匹配和圖像融合3個(gè)階段. 在特征點(diǎn)匹配這一環(huán)節(jié)影響著圖像拼接的速度并且決定著圖像的拼接是否成功. 而圖像融合決定著最后呈現(xiàn)的拼接效果. 現(xiàn)在使用最多的拼接算法是先通過ORB算法、SIFT算法或者SURF算法提取特征點(diǎn), 然后使用k-d樹算法進(jìn)行特征點(diǎn)匹配, 再求出兩幅圖像的單應(yīng)性矩陣并轉(zhuǎn)換到同一坐標(biāo)系下, 最后采用漸入漸出算法完成融合. 其中ORB使用的是FAST特征點(diǎn)與BRIEF特征描述符, 特征提取速度很快, 但BRIEF描述簡單, 匹配率相對降低[5]; SIFT算法對矩陣變換不敏感, 噪點(diǎn)污染和光照強(qiáng)弱的變化不會(huì)影響其穩(wěn)定性, 但算法耗時(shí)較大[6]; SURF 算法基于SIFT算法的思想, 改變計(jì)算方法減少了特征點(diǎn)提取時(shí)間, 但精度相對降低[7].

為了提升算法匹配的準(zhǔn)確率及效率, 在特征點(diǎn)提取方面, 李玉峰等[8]采用基于區(qū)域分塊的算法, 將圖像按照4等份分成4個(gè)分塊, 選擇兩幅圖像分塊相似度最大的一組作為相似區(qū)域提取特征點(diǎn), 減少特征點(diǎn)數(shù)量, 加快匹配速度, 但是圖像4等份存在所選區(qū)域相似部分不完整, 不具備代表性等問題. 厲丹等[9]采用相位相關(guān)法, 計(jì)算兩幅圖像的互功率譜提取兩幅圖像的位移從而定位相似區(qū)域, 但該方法對有尺度變化或角度變化的圖像效果不佳, 且圖像越大傅里葉變換耗時(shí)越多. 在特征點(diǎn)匹配方面, Bian等[10]在BF算法[11]匹配之后加入網(wǎng)格運(yùn)動(dòng)統(tǒng)計(jì)(GMS)算法剔除錯(cuò)誤的匹配, 提高了匹配精度. Lowry等[12]提出LOGOS算法，利用特征局部尺度信息剔除錯(cuò)誤的匹配, 同樣提高了匹配精度. 在圖像融合方面, Zaragoza等[13]提出局部單應(yīng)性矩陣, 將圖像網(wǎng)格化, 只對重疊部分進(jìn)行處理, 拼接結(jié)果過渡平滑, 但是對特征點(diǎn)匹配的要求較高.

綜上所述, 本文采用感知哈希算法[14], 通過比對匹配圖像與待匹配圖像的HASH指紋, 確定相似區(qū)域. 在特征點(diǎn)選取上為了保證特征點(diǎn)的精度而使用SIFT特征, 在圖像匹配上則直接替換傳統(tǒng)的k-d樹算法[15], 利用SIFT特征點(diǎn)的主方向信息與相似區(qū)域的坐標(biāo)信息, 過濾掉非匹配組, 縮短匹配時(shí)間. 區(qū)別于GMS算法在匹配完后過濾, 本文算法在匹配計(jì)算過程中實(shí)現(xiàn)過濾, 加速匹配過程的同時(shí)還提高了精度. 最后在圖像融合上選擇加權(quán)最佳拼接縫算法[16]消除突變, 完成拼接. 實(shí)驗(yàn)結(jié)果顯示, 本文算法在速度、計(jì)算資源消耗、拼接效果上都明顯優(yōu)于傳統(tǒng)的SIFT算法,并且在上百張巖石微觀圖像拼接的實(shí)際應(yīng)用場景上, 有較好的表現(xiàn).

2 相似區(qū)域提取

一張圖像相當(dāng)于一個(gè)二維信號, 含有多種不同的頻率. 低頻部分的亮度變化小, 包含了圖像大多數(shù)的信息. 高頻部分的亮度變化強(qiáng)烈, 表現(xiàn)的是圖像的細(xì)節(jié). 相似區(qū)域感興趣部分是圖像的低頻部分, 對其進(jìn)行編碼生成哈希指紋. 感知哈希算法首先將原始圖像進(jìn)行縮放為32*32尺寸并轉(zhuǎn)化為灰度圖, 以減小計(jì)算量, 然后使用離散余弦變換(DCT)將信號轉(zhuǎn)換到頻域, DCT公式[14]如下.

(1)

(2)

(3)

其中,E是一維變換后的系數(shù);F是二維變換后的系數(shù)；f是輸入的信號；u和v是輸入信號每一維點(diǎn)的個(gè)數(shù)；c是系數(shù), 可以將矩陣轉(zhuǎn)換為正交矩陣.

離散余弦變換后將得到一個(gè)32*32的矩陣, 僅需要矩陣中的低頻部分, 即位于左上方8*8大小的矩陣. 計(jì)算該矩陣內(nèi)的均值, 將矩陣中每一個(gè)小于等于均值的點(diǎn)修改為“0”, 大于均值的修改為“1”. 將得到一個(gè)長度為64位的字符串, 即哈希指紋.

相似區(qū)域提取具體流程如下：輸入匹配圖像與待匹配圖像, 將匹配圖像從左到右平均分成4部分, 考慮到效率以及精度取第4部分生成匹配HASH指紋. 將待匹配圖像以圖像寬度的1/128作為步長截取圖像(截取圖像寬度與匹配圖像截取寬度相同), 共獲得96幅截取圖像, 并生成待匹配HASH指紋, 如圖1所示.

圖1 相似區(qū)域提取示意圖Fig.1 Similar area extraction diagram

計(jì)算匹配HASH指紋與待匹配HASH指紋的漢明距離, 漢明距離最小的即為最佳相似截取圖像, 該圖像到原圖像坐標(biāo)原點(diǎn)的距離再加上截取圖像寬度即為兩幅圖像的大致相似區(qū)域, 圖2和圖3為相似區(qū)域提取的結(jié)果.

(a) 待匹配圖像

(b) 提取的相似區(qū)域

(a) 待匹配圖像圖2 圖像一相似區(qū)域提取結(jié)果Fig.2 Image 1 similar area extraction result

(b) 提取的相似區(qū)域圖3 圖像二相似區(qū)域提取結(jié)果Fig.3 Image 2 similar area extraction result

3 特征點(diǎn)提取與匹配

3.1 特征點(diǎn)提取

獲取到圖像的相似區(qū)域后再提取SIFT特征[6].SIFT特征提取步驟如下.

(1) 構(gòu)造尺度空間：一副圖像清晰程度可以用尺度來度量, 尺度越大則圖像越模糊, 所展示的細(xì)節(jié)越少, 在各個(gè)尺度上提取特征點(diǎn), 確保經(jīng)過縮放的圖像特征點(diǎn)的唯一性, 提高特征點(diǎn)的精度.

(2) 關(guān)鍵點(diǎn)搜索與定位：關(guān)鍵點(diǎn)是尺度空間里的局部極大值或極小值. 將每一個(gè)像素點(diǎn)與它所有的相鄰點(diǎn), 以及它的圖像域和尺度域的相鄰點(diǎn)值的大小進(jìn)行比較. 如果該點(diǎn)的值最大或是最小, 即將該點(diǎn)作為一個(gè)關(guān)鍵點(diǎn)候選點(diǎn). 然后以主曲率大小作為判斷依據(jù), 除去在邊緣的關(guān)鍵點(diǎn).

(3) 方向賦值：為了消除旋轉(zhuǎn)變換對特征的影響, 對關(guān)鍵點(diǎn)周圍鄰域內(nèi)的所有像素點(diǎn)求得其梯度的方向. 使用直方圖統(tǒng)計(jì)的方法, 以每柱10°的間隔將360°分為36個(gè)柱面, 統(tǒng)計(jì)像素點(diǎn)梯度的方向在各區(qū)間的分布. 關(guān)鍵點(diǎn)的主方向是最高柱面所代表的方向. 為了提高魯棒性, 并選擇一些關(guān)鍵點(diǎn)的輔方向, 這些方向的峰值大于或等于最高值的80%.

(4) 特征點(diǎn)描述子：以關(guān)鍵點(diǎn)為中心, 將坐標(biāo)軸旋轉(zhuǎn)一定角度, 與主方向平行. 在關(guān)鍵點(diǎn)的周圍鄰域內(nèi), 計(jì)算它們的局部梯度, 用向量的形式表示, 并進(jìn)行歸一化, 最終生成一個(gè)128維的特征向量. 特征點(diǎn)描述子具有很好的獨(dú)立性, 歸一化除去了亮度變化造成的誤差. 旋轉(zhuǎn)到主方向保證了特征點(diǎn)對旋轉(zhuǎn)變換抗性.

3.2 基于SIFT特征點(diǎn)主方向與位置信息的匹配算法

傳統(tǒng)的k-d樹算法只使用到了SIFT特征點(diǎn)的特征描述子, 沒有充分利用特征點(diǎn)的主方向、位置坐標(biāo)信息, 使得存在很多的誤匹配, 且浪費(fèi)了大量的時(shí)間. 因此本文提出基于SIFT特征點(diǎn)主方向與位置信息的匹配算法. 算法的核心思想是根據(jù)已匹配特征點(diǎn)的結(jié)果縮小匹配范圍，減少不必要的匹配計(jì)算. 流程如圖4所示.

圖4 算法流程圖Fig.4 Flowchart of algorithm

圖4中的算法步驟如下：

(1) 輸入匹配圖像相似區(qū)域的匹配特征點(diǎn)集SIFT1和待匹配圖像相似區(qū)域的待匹配特征點(diǎn)集SIFT2. 特征點(diǎn)集中的每一個(gè)特征點(diǎn)都包含主方向信息arc, 坐標(biāo)信息x、y以及特征描述子信息.

(2) 初始化參數(shù)HS為圖像的高度, 參數(shù)WS為原始圖像的1/4截取部分寬度. 這兩個(gè)參數(shù)作為兩個(gè)特征點(diǎn)是否可能關(guān)聯(lián)的判斷依據(jù).HS代表兩幅圖像在y軸方向的偏移,WS代表兩幅圖像在x軸方向的偏移. 這兩個(gè)參數(shù)會(huì)在后續(xù)過程中收斂穩(wěn)定.

(3) 計(jì)算特征點(diǎn)之間的主方向信息與位置信息的誤差，公式如下.

Ex=||xi-xj|-WS|-30

(4)

Ey=||yi-yj|-HS|-20

(5)

Earc=|Siarc-Sjarc|-8

(6)

其中，Ex是x軸方向的誤差;Ey是y軸方向的誤差;Earc是主方向角度誤差.Sarc是特征點(diǎn)的主方向. “8”、“20” 和“30”為經(jīng)驗(yàn)值, 代表允許誤差, 值越小匹配速度越快, 但相應(yīng)的會(huì)損失匹配的精度. 當(dāng)Ex,Ey和Earc中某一項(xiàng)的值大于0則說明兩個(gè)特征點(diǎn)匹配的概率極小, 舍棄并進(jìn)行下一個(gè)關(guān)鍵點(diǎn)的判斷. 在滿足條件的待匹配特征點(diǎn)中計(jì)算與匹配特征點(diǎn)歐式距離, 公式如下.

(7)

其中,mi,ni是特征點(diǎn)描述子的向量；D(m,n)是特征點(diǎn)描述子向量之間的的歐式距離.D(m,n)越小匹配度越高, 記距離最小的一對匹配點(diǎn)的距離為D1, 距離次小的一對匹配點(diǎn)的距離為D2, 若D1小于0.8倍的D2，則最小距離的一對匹配點(diǎn)即為匹配對.

(5) 每找到3個(gè)匹配對以后, 根據(jù)各匹配對權(quán)重和M, 更新HS與WS. 權(quán)重與D大小成反比.公式如下.

(8)

(9)

(10)

為了驗(yàn)證本文匹配算法本身的優(yōu)越性, 選擇在相同特征點(diǎn)數(shù)量下(保證匹配前初始條件的一致性, 為了顯示效果設(shè)置為1 000個(gè)特征點(diǎn)), 對比k-d樹算法[15]、GMS算法[10]、LOGOS算法[12]與本文匹配算法. 實(shí)驗(yàn)結(jié)果如圖5、圖6和表1所示.

(a) k-d樹算法 (b) GMS算法

(c) LOGOS算法 (d)本文算法

(a) k-d樹算法 (b) GMS算法圖5 圖像一匹配結(jié)果對比Fig.5 Image 1 match result comparison

(c) LOGOS算法 (d) 本文算法圖6 圖像二匹配結(jié)果對比Fig.6 Image 2 match result comparison

表1 實(shí)驗(yàn)數(shù)據(jù)對比

可以看到, k-d樹算法存在大量的誤匹配, 算法的時(shí)間對特征的維度敏感且存在回溯搜索的過程, 所以耗時(shí)稍長. GMS算法與LOGOS算法則過濾掉大量的誤匹配, 結(jié)果更加精準(zhǔn), 但是GMS算法依賴于暴力匹配之后的結(jié)果, LOGOS算法需要進(jìn)行特征聚類計(jì)算, 更加耗時(shí). 而本文匹配算法直接在匹配過程中實(shí)現(xiàn)過濾, 減少了計(jì)算量與算法耗時(shí). 速度提升數(shù)倍. 使用迭代方式更新判斷的條件, 提高了算法的穩(wěn)定性, 使得匹配準(zhǔn)確率較k-d樹算法有顯著提升, 雖然不如GMS算法與LOGOS算法精確, 但是獲得了更多的正確匹配對, 綜合結(jié)果更優(yōu).

4 圖像融合

使用RANSAC算法可以得到圖像之間的單應(yīng)性矩陣, 消除拍攝模式不同而造成旋轉(zhuǎn)變換、位移變換以及投影變換的影響[17]. 單應(yīng)性矩陣模型如下.

(11)

其中,x,y是匹配圖像的橫縱坐標(biāo)，x′,y′是待匹配圖像的橫縱坐標(biāo). 根據(jù)上一節(jié)求出的匹配結(jié)果, 求出矩陣 , 通過單應(yīng)性矩陣將兩幅圖像轉(zhuǎn)換到同一坐標(biāo)系下.

傳統(tǒng)的漸入漸出融合算法, 在圖像之間的重疊部分加入權(quán)值, 在重合部分過渡的時(shí)候, 權(quán)值從0至1, 消除重疊區(qū)域的突變達(dá)到融合的效果. 但是如果重疊部分有運(yùn)動(dòng)狀態(tài)的物體, 會(huì)產(chǎn)生鬼影等現(xiàn)象, 拼接效果不佳. 因此本文使用加權(quán)最佳拼接縫圖像融合算法[16], 通過動(dòng)態(tài)規(guī)劃的方式找到兩幅圖像的最佳拼接縫, 消除鬼影, 然后在最佳拼接縫處使用加權(quán)融合, 最終完成拼接.

兩幅圖像在拼接縫上的像素點(diǎn)色彩差異最小以及結(jié)構(gòu)最相似, 這條拼接縫即為最佳拼接縫[18]. 公式如下.

Egeometry(x,y)=|Sx*I|+|Sy*I|

(12)

Ecolor(x,y)=|I1-I2|

(13)

(14)

E(x,y)=Ecolor(x,y)2+Egeometry(x,y)

(15)

其中,Sx與Sy是sobel梯度算子;I是圖像;Egeometry是兩幅圖像結(jié)構(gòu)上的差異值;Ecolor是兩幅圖像像素的色彩差異值.

然后以重疊部分第一行作為拼接縫的起點(diǎn), 按照上述條件, 建立多條拼接縫, 找出誤差最小的一條即為最佳拼接縫. 最后在最佳拼接縫處使用漸入漸出加權(quán)融合, 消除突變. 部分實(shí)驗(yàn)結(jié)果如圖7和圖8所示.

可以看到, 傳統(tǒng)的漸入漸出加權(quán)算法在細(xì)節(jié)上表現(xiàn)不佳, 對RANSAC算法求得的單應(yīng)性矩陣精度要求很高, 稍有偏差就會(huì)出現(xiàn)鬼影現(xiàn)象, 如圖8(c)所示. 使用最佳拼接縫方法有效地避免了在整個(gè)重疊區(qū)域進(jìn)行加權(quán)運(yùn)算, 消除了鬼影. 但在拼接縫處, 由于匹配圖像與待匹配圖像之間亮度差異等原因, 造成拼接縫處左右亮度不均, 過渡生硬, 如圖7(b)所示. 所以在拼接縫處使用加權(quán)運(yùn)算, 消除拼接縫處的突變, 完成自然過渡.

(a) 待拼接圖像

(b) 最佳拼接縫

(c) 傳統(tǒng)算法拼接結(jié)果及細(xì)節(jié)

(d) 加權(quán)最佳拼接縫拼接結(jié)果及細(xì)節(jié)圖7 圖像一拼接結(jié)果對比Fig.7 Image 1 stitching result comparison

(a) 待拼接圖像

(b) 最佳拼接縫

(c) 傳統(tǒng)算法拼接結(jié)果及細(xì)節(jié)

(d) 加權(quán)最佳拼接縫拼接結(jié)果及細(xì)節(jié)圖8 圖像二拼接結(jié)果對比Fig.8 Image 2 stitching result comparison

5 實(shí)驗(yàn)數(shù)據(jù)分析及工程應(yīng)用

本文算法運(yùn)行在64位win 10操作系統(tǒng), Intel (r) Core (tm)i5-4590 CPU @ 3.30 GHz CPU, 12 G內(nèi)存, 編譯環(huán)境為VS 2015.

為驗(yàn)證本文算法可行性, 對圖2和圖3從提取特征點(diǎn)數(shù)、匹配結(jié)果以及算法時(shí)間上對比算法1(SIFT+k-d樹算法+漸入漸出)、算法2(ORB +GMS[11]算法+漸入漸出)和算法3(SIFT +LOGOS[12]算法+漸入漸出). 實(shí)驗(yàn)結(jié)果如表2所示.

表2 實(shí)驗(yàn)數(shù)據(jù)對比

從表2數(shù)據(jù)中可以看到, 傳統(tǒng)算法從大量的特征點(diǎn)中獲取到有限的正確匹配數(shù), 耗時(shí)長且匹配準(zhǔn)確率低, 大量的錯(cuò)誤匹配影響后續(xù)計(jì)算單應(yīng)性矩陣. GMS算法與LOGOS算法匹配準(zhǔn)確率很高, 但是由于GMS提取的特征點(diǎn)結(jié)構(gòu)簡單, 使得檢測到過多的特征點(diǎn), 并且GMS算法需要先使用BF算法暴力匹配, 導(dǎo)致匹配用時(shí)過長. 而LOGOS算法需要先訓(xùn)練BOW字典集, 更加耗時(shí). 而本文算法先是提取了相似區(qū)域, 在相似區(qū)域上提取特征點(diǎn), 減少特征點(diǎn)的總數(shù)目與特征點(diǎn)匹配時(shí)間. 并在匹配算法上進(jìn)一步地剔除不相關(guān)特征點(diǎn), 從有限的特征點(diǎn)數(shù)量上獲得大量的正確匹配數(shù), 匹配正確率接近GMS算法與LOGOS算法, 并且在特征提取和特征匹配上耗時(shí)最短, 雖然最后的加權(quán)最佳拼接縫的融合時(shí)間較長, 但是總時(shí)間相對更短, 并實(shí)現(xiàn)了更好的拼接效果. 綜合效率、精度以及效果, 本文的算法更具優(yōu)越性.

此外, 在實(shí)際工程應(yīng)用中, 例如多幅巖石微觀薄片圖像的拼接, 由于顯微鏡下的微觀圖像只能展示局部特征, 實(shí)際應(yīng)用中往往需要將多幅微觀圖像拼接為一張完整的圖像來觀察全局的特征, 這涉及到幾十張甚至幾百張圖像的拼接, 以此來驗(yàn)證本文算法. 圖9是單幅巖石微觀薄片圖像, 尺寸為2 448×2 048, 圖10是600張巖石微觀薄片圖像的拼接結(jié)果, 尺寸為44 104×45 504, 共25行24列, 從實(shí)驗(yàn)結(jié)果來看證明了本文算法的有效性. 僅在相似區(qū)域提取有效特征點(diǎn), 可以減少硬件內(nèi)存資源的浪費(fèi), 基于位置與主方向信息的匹配方法可以加快匹配速度, 使得在有限的硬件計(jì)算資源條件下實(shí)現(xiàn)多幅圖像的快速拼接成為可能.

圖9 單幅巖石微觀薄片圖像Fig.9 Single rock micro slice image

圖10 600張巖石微觀薄片圖像的拼接結(jié)果

6 結(jié) 論

由于SIFT算法提取特征點(diǎn)計(jì)算復(fù)雜, k-d樹算法進(jìn)行特征匹配時(shí)回溯次數(shù)過多且存在大量的誤匹配. 針對這一現(xiàn)象本文提出一種基于感知哈希與尺度不變特征變換的快速拼接算法. 感知哈希算法通過HASH指紋對比, 快速識別出兩幅圖像的相似區(qū)域. 匹配算法上利用SIFT特征點(diǎn)主方向與位置信息過濾掉不必要的特征點(diǎn)匹配并實(shí)現(xiàn)粗過濾. 融合算法采用加權(quán)最佳拼接縫算法消除鬼影. 實(shí)驗(yàn)結(jié)果顯示, 本文算法在保證匹配精度的前提下, 耗時(shí)更短, 拼接效果更好, 并且在實(shí)際應(yīng)用場景下得到了驗(yàn)證. 但是匹配算法對于旋轉(zhuǎn)過大的圖像效果會(huì)有降低, 需進(jìn)一步優(yōu)化.