基于感知Hash和極線約束的改進AKAZE算法

王宏志, 張金棟, 胡黃水, 謝沛松

(長春工業大學 計算機科學與工程學院, 長春 130012)

基于特征的圖像匹配是圖像匹配的主流方法之一, 目前已有許多經典算法. SIFT(scale invariant feature transform)算法[1]使用高斯核函數, 使特征點具有尺度不變性, 但計算量較大； SURF(speedup robust features)算法[2]是SIFT算法的加速版本, 使用Hesse矩陣用于尺度空間的構造； ORB算法通過FAST(feature from accelerated segment test)算法提取特征點, 通過BRIEF(binary robust independent elementary features)計算得到描述子[3], 提高了運算效率, 但特征點匹配準確率較低； KAZE算法是基于非線性的特征提取與匹配算法[4], 使用加性算子分裂算法(additive operator splitting, AOS)進行非線性擴散濾波, 使KAZE算法在模糊圖像的同時還能保留邊緣細節； AKAZE(accelerated-KAZE)算法[5]使用快速顯示擴散(fast explicit diffusion, FED)算法代替KAZE中的AOS算法構造非線性尺度空間, 提升了計算效率, 并使用二進制描述符M-LDB(modified-local difference binary)描述特征點. 針對傳統算法目前已提出了許多改進方法， 例如： 用貪婪搜索算法[6]或遺傳算法[7]優化性能； 用改進下采樣方法保留更多有區分性的點對[8]； 用四叉樹劃分圖像輔助特征點的檢測[9]； 用光譜維度進行圖像空間性質的測量[10]； 用基于全局運動建模的雙邊函數算法進行特征點匹配[11]； 用自適應閾值[12]或自適應直方圖均衡化的方法[13]提高特征點匹配準確率.

原始AKAZE算法雖然具有較好的魯棒性, 但當圖像發生變化時特征點匹配準確率較低. 為解決上述問題, 梁煥青等[14]使用顏色不變量的灰度級增加了圖像的彩色信息, 但需要根據經驗值確定灰度變換的參數； 李闖等[15]使用AKAZE檢測特征點, 并使用RANSAC(random sample consensus)算法剔除誤匹配點, 實現了對喀斯特地貌無人機影像的快速匹配; Liu等[16]將AKAZE特征與改進的SIFT描述子相結合, 提高了算法的匹配精度; 李丹等[17]提出了一種基于網格運動約束的遙感圖像配準方法, 能快速且魯棒性較強的進行特征點匹配； 陳海鵬等[18]使用基于密度的聚類算法去除錯誤匹配, 并通過仿射變換整幅圖像對篡改區域進行定位； 邢長征等[19]提出了基于AKAZE的掩碼描述符匹配算法, 使其可應用于對魯棒性和匹配速度要求較高的匹配場景； 沈學利等[20]使用三元組LATCH(learned arrangements of three patch codes)描述符替代M-LDB描述符, 提高了特征點匹配的速度； Anuja等[21]使用AKAZE和FAST技術提取關鍵點, 在FAST關鍵點提取過程中, 采用自動對比度閾值進行非最大值抑制.

本文提出一種改進的AKAZE算法, 將特征點匹配分為兩個階段. 粗匹配階段在使用快速近似最近鄰算法篩選出匹配點對的基礎上, 引入最近鄰特征點和次近鄰特征點的概念, 利用兩者的距離比值進行特征點的篩選, 并使用感知Hash算法計算出特征點Hash值增加特征點的獨特性, 將其用于粗匹配階段特征點對的篩選, 同時使用感知Hash算法計算出兩張圖片的Hash值差異, 將其用于精匹配階段閾值的選取； 精匹配階段在使用RANSAC算法的基礎上利用極線約束原理進一步篩選特征點對.

1 AKAZE算法

1.1 構造非線性尺度空間

AKAZE算法將非線性擴散濾波器用于尺度空間的構造, 非線性擴散濾波可用非線性偏微分方程表示, 表達式為

(1)

其中L為圖像的亮度, div為散度,為梯度,c為傳導函數,x和y為坐標,t為尺度參數.傳導函數c可表示為

c(x,y,t)=g(Lσ(x,y,t)),

(2)

其中g為傳導核函數,Lσ為圖像經過高斯平滑后的梯度圖像.傳導核函數g可表示為

(3)

其中參數λ用于控制擴散程度.對于偏微分方程的求解, AKAZE并未使用KAZE算法中的AOS算法, 而使用了FED算法確保算法的實時性, 并以此構造出O組非線性尺度空間, 其中每組有S層.用FED算法求解式(1)得到圖像的非線性尺度空間表達式為

Li+1=(I+τA(Li))Li,i=0,1,…,n-1,

(4)

其中I為單位矩陣,τ為時間步長,A(Li)為圖像Li在維度i的傳導矩陣,n為顯式擴散步數.

1.2 檢測特征點

AKAZE算法首先對每層尺度空間中的像素點進行Hesse矩陣計算, 然后將該像素點的響應值與同層以及上下相鄰層的3×3區域內26個像素點進行比較, 若該像素點在與這26個像素點的比較中均為最大, 則該點即為特征點.Hesse矩陣的計算公式為

(5)

其中σ為尺度參數,Lxx和Lyy分別為二階橫向微分和二階縱向微分,Lxy為二階交叉微分.

1.3 確定特征點主方向

AKAZE算法以特征點為中心, 以尺度參數的6倍為半徑確定圓形區域, 將特征點鄰域的一階微分值Lx和Ly進行高斯賦權運算, 并以角度為60°的扇形窗口旋轉, 計算該窗口內的向量和, 向量和最大的方向即為特征點的主方向.

1.4 計算特征描述符

AKAZE算法使用M-LDB描述符. M-LDB描述符主要針對LDB(local difference binary)描述符進行了旋轉與縮放性能的改進, 該描述符未使用所有的劃分網格像素, 而是通過網格像素采樣完成尺度自適應, 這樣離散采樣獲得的描述符是由0和1構成的二值描述符, 可提高算法的實時性能.

1.5 特征點匹配

AKAZE算法中特征點的描述符為二值描述符, 因此一般通過計算特征點描述符間的Hamming距離判斷特征點之間的匹配程度進行特征點的匹配. 而在實際使用中常會在上述特征點匹配完成后使用隨機抽樣一致算法等消除誤匹配點, 從而進一步完成特征點的匹配.

2 改進的AKAZE算法

2.1 基于最近鄰次近鄰比值和感知Hash特征點的粗匹配

2.1.1 最近鄰次近鄰比值

AKAZE算法通過計算描述符的Hamming距離進行特征點的暴力匹配易導致大量誤匹配, 本文將特征點的匹配分為粗匹配和精匹配兩個階段對AKAZE算法進行改進. 粗匹配階段中, 在使用快速近似最近鄰算法篩選出匹配點對的基礎上, 通過最近鄰次近鄰的比值進行匹配點對的篩選, 并使用感知Hash算法計算特征點的Hash值增加特征點的獨特性, 進一步剔除錯誤的匹配點對.

最近鄰次近鄰比值是指使用快速近似最近鄰算法在待匹配圖像中找出與基準圖像特征點Hamming距離最近和次近的兩個特征點, 并將分別計算出的最近距離與次近距離的比值與設定的閾值比較, 如果比值結果大于設定的閾值, 則將該特征點對剔除, 本文閾值設定為0.75.

2.1.2 感知Hash

感知Hash算法(perceptual Hash algorithm)可對圖像生成一個“指紋”, 通過比較兩張圖像之間的指紋對圖像的相似度進行判斷. 感知Hash算法步驟如下.

1) 縮小尺寸: 將圖片縮小到8×8大小, 共64個像素, 其目的是快速去除圖像高頻和細節, 只保留圖像基礎的結構.

2) 色彩簡化: 將縮小后的圖片轉化為灰度圖像.

3) 計算離散余弦變換(DCT): 離散余弦變換就是將圖片分解頻率聚集和梯形狀, 表示為

(6)

其中F(u,v)為DCT變換后的系數矩陣,f(i,j)為原始信號,c(u)和c(v)為補償系數,N為原始信號的個數,u和v是系數矩陣F(u,v)的坐標.

4) 計算Hash值: 計算步驟3)中64個值的平均值, 并將每個值與平均值進行比較, 如果小于平均值則該值為0, 大于等于平均值則該值為1, 從而獲得由0和1組成的64位Hash值, 即該圖像的指紋.

本文使用感知Hash算法增加特征點的獨特性, 相當于對M-LDB描述符增加了一個Hash值的新維度, 可有效減少原始算法中兩個特征點在不同區域, 但根據Hamming距離仍然判斷為匹配點對的情況. 本文以特征點為中心, 截取其8×8的鄰域圖像并計算Hash值, 在最近鄰次近鄰比值的基礎上對匹配點對的Hash值進行計算, 如果小于設定的閾值, 則保留匹配點對, 如果大于設定的閾值, 則將該特征點對剔除. 在對整幅圖片進行對比時, 閾值一般設定為5, 但對于本文所選取的特征點鄰域并不存在縮小圖片尺寸的步驟, 閾值如果仍設定為5會消除掉過多正確的匹配點對, 因此本文將該閾值設定為15.

2.2 基于RANSAC和極線約束的特征點精匹配

RANSAC算法雖然能魯棒地估計模型參數, 但其本質存在著隨機性和假設性, 因此只有一定的概率得到可信的模型. 針對上述問題, 本文在特征點的精匹配階段, 在使用RANSAC算法的基礎上利用極限約束進一步篩選匹配點對.

極線約束原理如圖1所示, 其中C1和C2分別為兩個相機的投影中心, 點P1和P2分別是點P在兩個相機上的投影, 點C1,C2和P組成的平面稱為極平面, 極平面和左右兩張圖像分別產生交線l1和l2, 這兩條線稱為極線, 極線和投影中心產生交點e1和e2, 這兩個點稱為極點. 由圖1可見, 特征點對中右圖的特征點應該在根據左圖特征點計算出的極線上, 因此可通過極線約束原理創建基本矩陣F, 并通過基本矩陣F判斷是否剔除特征點對.基本矩陣F是一個3×3的矩陣, 一般取右下角元素為1, 因此F包含了8個未知量, 本文采用8點法進行求解, 過程如下.

圖1 極線約束原理Fig.1 Principle of epipolar constraint

設點P1和P2的坐標分別為(x1,y1,1)T和(x2,y2,1)T, 可得：

(x2x1,x2y1,x2,y2x1,y2y1,y2,x1,y1,1)f=0,

(7)

其中f為F的元素組成并按優先順序排列的矢量, 表達式為

f=(F11,F12,F13,F21,F22,F23,F31,F32,F33),

(8)

式中Fij表示F的第i行、 第j列元素, 選取8組特征點對, 令x和y的第一個下標表示組數, 第二個下標表示坐標, 可得

(9)

由式(9)可計算出極線方程以及基礎矩陣F.此時可判斷匹配點對是否滿足下式：

(10)

式中p0和p1為匹配點對坐標.若匹配點對滿足式(10)則保留, 不滿足則剔除.在實際應用中, 將正確匹配點對代入式(10)也不會完全為0, 因此本文根據兩張圖像Hash值的Hamming距離進行閾值的設定, 當特征點對代入后的值大于設定的閾值時, 剔除匹配點對.閾值設定為

(11)

式中η為兩張圖像Hash值的Hamming距離.

3 實驗結果與分析

實驗環境為虛擬機環境. 電腦操作系統為Windows 10, CPU為i7-4790四核處理器, 頻率為3.60 GHz, 內存為8 GB, DDR3架構, 頻率為1 600 MHz. 虛擬機操作系統為ubuntu 18.04, 處理器數量設為兩個, 每個處理器有兩個內核, 內存設為4 GB.

為驗證本文改進后算法的有效性, 采用Mikolajcayk標準圖像數據集中的ubc(壓縮)、 bikes(模糊)、 boat(旋轉縮放)、 leuven(光線亮度)4組圖像進行實驗, 對比算法1～算法4分別為AKAZE算法、 KAZE算法、 SIFT算法、 ORB算法. 由于在實際情況下計算出特征點對后會進行誤匹配點對的剔除, 因此本文的對比算法均使用RANSAC算法進行了誤匹配點對的剔除.

在圖像發生壓縮和模糊的情況下各算法的對比結果如圖2和表1所示. 表1中壓縮1～5, 模糊1～5表示數據集中的第一張圖與后續第幾張圖進行實驗.

圖2 圖像發生壓縮和模糊情況下不同算法準確率的折線對比結果Fig.2 Broken line comparison results of accuracy of different algorithms in the case of image compression and blur

表1 圖像發生壓縮和模糊情況下不同算法準確率的對比結果

由圖2和表1可見, 本文算法在圖像發生壓縮的情況下平均準確率為96.79%, AKAZE,KAZE,SIFT,ORB算法的平均準確率分別為89.8%,77.458%,82.162%,74.368%, 與未改進的AKAZE算法相比, 本文算法平均準確率提高了6.99%; 與最接近的SIFT算法相比, 本文算法平均準確率提高了14.628%. 而在圖像發生模糊的情況下, 本文算法平均準確率為92.242%, AKAZE,KAZE,SIFT,ORB算法的平均準確率分別為78.93%,69.032%,70.934%,48.866%, 與未改進的AKAZE算法相比, 本文算法平均準確率提高了13.312%, 與最接近的SIFT算法相比, 本文算法平均準確率提高了21.308%.

在圖像發生旋轉縮放和光線亮度改變情況下不同算法的對比結果如圖3和表2、 表3所示. 表2和表3中旋轉縮放1～5和光線亮度1～5表示數據集中的第一張圖與后續第幾張圖進行實驗. 由表2和表3可見, 本文算法在圖像發生旋轉縮放的情況下平均準確率為87.31%, AKAZE,KAZE,SIFT,ORB算法的平均準確率分別為72.605%,66.91%,82.167 5%,73.62%, 與未改進的AKAZE算法相比, 本文算法平均準確率提高了14.705%, 與最接近的SIFT算法相比, 本文算法平均準確率提高了5.143%. 而在圖像發生光線亮度改變的情況下, 本文算法平均準確率為97.442%, AKAZE,KAZE,SIFT,ORB算法的平均準確率分別為80.87%,76.034%,89.002%,67.908%, 與未改進的AKAZE算法相比, 本文算法平均準確率提高了16.572%, 與最接近的SIFT算法相比, 本文算法平均準確率提高了8.44%.

圖3 圖像發生旋轉縮放和光線亮度改變情況下不同算法準確率的折線對比結果Fig.3 Broken line comparison results of accuracy of different algorithms when images are rotated and scaled and brightness of light changes

表2 圖像發生旋轉縮放改變情況下不同算法準確率的對比結果

表3 圖像發生光線亮度改變情況下不同算法準確率的對比結果

本文算法、 AKAZE算法、 KAZE算法、 SIFT算法、 ORB算法的特征點匹配平均用時分別為0.279 2,0.272 6,0.910 8,0.562 8,0.103 7 s. 表明由于本文算法在粗匹配階段已經進行過一次匹配點對的篩選, 在圖像發生變化時可先行有效地削減特征點對的數量, 而在精匹配階段本文算法選擇順序執行而不是并行執行極線約束和RANSAC算法, 因此在面對圖像發生變化的圖片匹配時, 在速度上與原始算法相比僅慢2.4%, 并未產生明顯差距.

選取4種圖像變化效果中的模糊和旋轉縮放繪制特征點匹配如圖4所示. 圖4中左側為模糊數據集中第一張圖像與第四張圖像的特征點匹配, 右側為旋轉縮放數據集中第一張圖像與第三張圖像的特征點匹配. 從上到下依次為原始AKAZE算法、 經過RANSAC算法剔除誤匹配點對的AKAZE算法以及本文算法. 由圖4可見, 本文算法可有效匹配各特征點.

圖4 特征點匹配Fig.4 Feature point matching

綜上所述, 本文針對AKAZE算法在圖像發生變化時, 特征點匹配精度較低的問題, 提出了一種基于感知Hash和極線約束的改進AKAZE算法, 并使用Mikolajcayk標準圖像數據集中的ubc(壓縮)、 bikes(模糊)、 boat(旋轉縮放)、 leuven(光線亮度)4組圖像, 與經過RANSAC算法進行誤匹配點對剔除后的AKAZE算法、 KAZE算法、 SIFT算法、 ORB算法進行了對比. 實驗結果表明, 改進后的AKAZE算法在保證算法效率的前提下, 特征點匹配準確率比原算法平均提高了12.9%, 比KAZE算法平均提高了21.09%, 比SIFT算法平均提高了12.38%, 比ORB算法平均提高了27.26%.