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

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

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

1 引 言

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

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

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

2 相似區域提取

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

(1)

(2)

(3)

其中,E是一維變換后的系數;F是二維變換后的系數；f是輸入的信號；u和v是輸入信號每一維點的個數；c是系數, 可以將矩陣轉換為正交矩陣.

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

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

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

計算匹配HASH指紋與待匹配HASH指紋的漢明距離, 漢明距離最小的即為最佳相似截取圖像, 該圖像到原圖像坐標原點的距離再加上截取圖像寬度即為兩幅圖像的大致相似區域, 圖2和圖3為相似區域提取的結果.

(a) 待匹配圖像

(b) 提取的相似區域

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

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

3 特征點提取與匹配

3.1 特征點提取

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

(1) 構造尺度空間：一副圖像清晰程度可以用尺度來度量, 尺度越大則圖像越模糊, 所展示的細節越少, 在各個尺度上提取特征點, 確保經過縮放的圖像特征點的唯一性, 提高特征點的精度.

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

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

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

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

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

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

圖4中的算法步驟如下：

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

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

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

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

(4)

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

(5)

Earc=|Siarc-Sjarc|-8

(6)

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

(7)

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

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

(8)

(9)

(10)

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

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

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

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

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

表1 實驗數據對比

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

4 圖像融合

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

(11)

其中,x,y是匹配圖像的橫縱坐標，x′,y′是待匹配圖像的橫縱坐標. 根據上一節求出的匹配結果, 求出矩陣 , 通過單應性矩陣將兩幅圖像轉換到同一坐標系下.

傳統的漸入漸出融合算法, 在圖像之間的重疊部分加入權值, 在重合部分過渡的時候, 權值從0至1, 消除重疊區域的突變達到融合的效果. 但是如果重疊部分有運動狀態的物體, 會產生鬼影等現象, 拼接效果不佳. 因此本文使用加權最佳拼接縫圖像融合算法[16], 通過動態規劃的方式找到兩幅圖像的最佳拼接縫, 消除鬼影, 然后在最佳拼接縫處使用加權融合, 最終完成拼接.

兩幅圖像在拼接縫上的像素點色彩差異最小以及結構最相似, 這條拼接縫即為最佳拼接縫[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是兩幅圖像結構上的差異值;Ecolor是兩幅圖像像素的色彩差異值.

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

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

(a) 待拼接圖像

(b) 最佳拼接縫

(c) 傳統算法拼接結果及細節

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

(a) 待拼接圖像

(b) 最佳拼接縫

(c) 傳統算法拼接結果及細節

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

5 實驗數據分析及工程應用

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

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

表2 實驗數據對比

從表2數據中可以看到, 傳統算法從大量的特征點中獲取到有限的正確匹配數, 耗時長且匹配準確率低, 大量的錯誤匹配影響后續計算單應性矩陣. GMS算法與LOGOS算法匹配準確率很高, 但是由于GMS提取的特征點結構簡單, 使得檢測到過多的特征點, 并且GMS算法需要先使用BF算法暴力匹配, 導致匹配用時過長. 而LOGOS算法需要先訓練BOW字典集, 更加耗時. 而本文算法先是提取了相似區域, 在相似區域上提取特征點, 減少特征點的總數目與特征點匹配時間. 并在匹配算法上進一步地剔除不相關特征點, 從有限的特征點數量上獲得大量的正確匹配數, 匹配正確率接近GMS算法與LOGOS算法, 并且在特征提取和特征匹配上耗時最短, 雖然最后的加權最佳拼接縫的融合時間較長, 但是總時間相對更短, 并實現了更好的拼接效果. 綜合效率、精度以及效果, 本文的算法更具優越性.

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

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

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

6 結 論

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