基于改進AKAZE的特征匹配算法及應用

張潤梅，宦思琪，張 媛，徐靜雯

（安徽建筑大學，合肥 230601）

一般來說，圖像中所顯示的幾何特征、光線特征、空間位置、質地、邊緣信息等，在不同的時間、視角、使用不同傳感器對同一物體進行攝影時，都可能有顯著的區別，如果再考慮各種干擾和噪音的影響，多次拍攝的圖像則會存在或大或小的差異［1］。圖像匹配就是查找并確定多次拍攝的圖像相同和不同的點，以確認相同的位置；如果兩幅圖像相同的點較多，它們之間的相關性相對較高；相反，如果兩幅圖像的相同點較少，則2個圖像之間的相關性相對較低。圖像的相關性影響匹配結果，相關度高的情況下圖像的匹配良好，相反相關度低的情況下，圖像的匹配結果較差［2］。

圖像的匹配主要可以劃分為基于灰度的圖像匹配和基于特征的圖像匹配。基于灰度的匹配是最先在國際上發展并流行起來的圖像匹配技術，這種匹配方法主要是在一幅圖像中選擇一塊圖像中的區域，用該圖像中的區域在另一幅新的圖像中進行移動，尋找另一幅新的圖像中與此查找區域的灰度差別最小的部分，以此基本實現兩幅相似圖像間的灰度匹配，這類的算法一般都需要遍歷多個查找區域進行運算［3］。最先被提出的基于灰度的圖像匹配檢測算法，是1971年由Leese提出的平均絕對差值檢測算法（MAD），通過遍歷計算以尋找2個區域的灰度差而基本實現了兩幅圖像間的配準。1972年由Barnea和Silverman提出了基于圖像序列相似性檢測的算法（SSDA），這個算法通過設定閾值以有效地避免遍歷計算數據尋找的復雜過程，并減少計算過程的量。由于基于灰度的匹配算法不僅計算出了待匹配點，而且把每個待匹配點周圍的模板和待匹配區域也一起仔細地考慮歸納進來，導致這種方法計算量較大且實際運算的時間也較長較慢［4］。基于圖像特征的匹配算法，在進行特征匹配前先要從圖像中獲取點、線、面或區域等的特征［5－6］。Harris和Stephen博士對1977年提出的經典Moravec角點檢測算法進行了改進，提出了在不變性方面表現更好的Harris角點算法［7］。1999年Lowe博士基于尺度空間的研究提出了經典的SIFT檢測算法，并在2004年對該算法進行了重大改進，該特征匹配算法對于圖像中的外界環境變化的檢測具有較強魯棒性。2003年，M.Brown和D.G.Lowe在ICCV上聯合發表了論文，將對SIFT特征關鍵點匹配檢測算法的運用推廣到全景圖的數字圖像拼接處理系統中。為了有效地改善和提高對特征點提取的匹配速度，Bay.H等在2006年對SIFT算法又進行了改進，提出了另一種新的經典匹配算法—SURF特征匹配算法［8－9］。之后，隨著現代計算機科學技術的進步和發展，對特征點匹配算法速度的技術要求越來越高，Ethan Rublee等在2011年發表的論文中提出了ORB匹配算法［10］。近年來，特征點的匹配算法主要分為2個不同的發展方向，一是為了盡可能地提高特征點匹配的精確度和準確度，繼續改進并發展SIFT、PCA-SIFT、ASIFT、LIFT等匹配算法；二是為了有效地提升特征點匹配的速度，如改進SURF、ORB、KAZE、AKAZE等匹配算法［11］。

徽派的建筑主要是選用傳統的磚、木、石3種材料進行建造，梁架結構用料碩大且十分注重裝飾。徽派建筑群的整體結構和走勢主要依賴于自然界山水的變化脈絡。從建筑群的外觀來看，徽派建筑都是由粉墻黛瓦的馬頭墻組合而來，總體在外觀上具有統一的建筑韻律感，而建筑群個體的個性化和設計上的靈活性則主要體現在雕刻的紋理和裝飾上的彩繪。由于徽派建筑群的構件總體上的造型特征區別相對較小，細節上的特征差別繁雜，且其數據量龐大，所以我們需要尋求一種新的特征匹配的方法，在進一步保證特征匹配精確度和準確度的同時也希望能更好地兼顧特征匹配的速度。

1 AKAZE算法

SIFT和SURF這兩種算法都是利用一種金字塔式的策略構建高斯尺度空間，常用于對目標的檢測、識別、定位和目標匹配［12］。無論是傳統的SIFT算法還是SURF算法，在尺度空間的構建和設計上都有一個明顯的技術缺陷：高斯模糊不能完全地保留物體邊界的局部信息，在所有的尺度上平滑到相同程度的細節和噪聲水平，這直接影響目標定位的精度和唯一性［13］。

學者針對高斯核函數構造尺度空間的局限性，提出了雙邊濾波和非線性擴散濾波擴散方式。這種利用非線性擴散濾波策略建立的尺度空間可以對物體局部的細節進行局部自適應濾波并有效保持物體和目標的局部邊界，從而在尺度空間中保持更多的細節特征。如，BFSIFT算法采用了雙邊濾波和雙向匹配的方法，提高了SIFT算法在強噪聲SAR圖像中的相應計算性能，但是需要進行更復雜的計算［14］。與SIFT和SURF算法相比，AKAZE算法作者之前在論文中提出的KAZE算法主要采用非線性擴散濾波器，缺點主要在于其計算量大。雖然AOS求解的方程組是穩定且可并行的，但是該算法需要同時求解大規模的線性方程組，并且難以很好地滿足移動端的實時性要求。

與SIFT算法和SURF算法相比，AKAZE算法的計算速度更快，與ORB和BRISK算法相比，其可重復性和魯棒性也有顯著的提高。

1.1 非線性擴散濾波

在之前的傳統算法如SIFT和SURF中，構造尺度空間都使用了高斯濾波，都無法避免一個潛在的問題，高斯濾波不能保留邊緣信息，且會將所有尺度的細節和噪聲平滑到相同的水平。尺度空間包括若干個組且通過降采樣得到下一個組，每個組中包含若干個尺寸相同的層，同一組中的若干層通過逐層非線性擴散來獲得。從構造效果上來看，高斯濾波處理后的圖片會隨著尺度減小逐漸模糊，而非線性濾波后圖片會損失一些細節，但仍然清晰可以辨認，能夠局部自適應進行濾除小細節同時保留目標的邊界使其尺度空間保留更多的特征信息。

非線性擴散濾波描述圖像亮度的變化是通過提升圖像的尺度參數作為熱擴散函數的散度因子來達到控制圖像亮度擴散過程的目的。通常采用偏微分方程進行求解，由于其中涉及微分方程的非線性性質，通過圖像亮度的擴散來構建尺度空間，表達式為：

式中：L為圖像亮度矩陣；div與▽分別代表散度函數與圖像梯度算子。當c（x，y，t）為常數時，則為熱擴散方程，表達式為各向同性擴散；當c（x，y，t）為關于梯度的函數時，表達式為各向異性擴散。擴散方程中引入傳導函數c能夠自適應于圖像的局部結構特性進行擴散，傳導函數的表達式定義為：

式（2）中的▽Lσ為圖像L經過高斯平滑后得到的梯度圖像，式（3）中的參數λ用來控制擴散的程度，決定邊緣區域要進行增強且平坦區域濾波的決策因子。FED結合顯式和半隱式理論的優勢互補，求解的思想動機來自于顯式理論分解box濾波器：能夠很好地近似高斯濾波器且便于應用。KAZE算法中使用AOS算法作為求解方法，但是由于大量線性方程求解過程緩慢，導致算法的實時性得不到保障，所以在AKAZE算法中用FED算法替換了AOS算法，這一步是為了提升計算速度和算法實時性［15－16］。FED算法表達式為：

其中：I為單位矩陣，A（Li）為圖像Li的傳導矩陣；n表示顯性擴散步數；τj為對應步長；τmax為滿足顯性擴散穩定性條件時的最大步長值。在整個FED的循環中，矩陣A（Li）始終保持不變。而當FED循環結束，算法將會重新計算矩陣A（Li）的值。

1.2 M-LDB描述子

二進制描述符可以在小圖像變形模式下由于計算的高效化而接近SIFT算法性能，因此它被廣泛用于移動終端、高實時性目標識別、追蹤等相關用途中。Yang Xin在2014年提出的LDB描述符，通過使用領域的區域強度均值信息和水平垂直方向上的圖像梯度信息來增加二值描述的分化性和魯棒性。AKAZE算法進一步提高了LDB描述符的圖像旋轉和縮放性能。通過KAZE算法的特征點旋轉不變性獲得主方向，然后LDB網格進行相應的旋轉。而AKAZE算法中的M-LDB描述符不使用分割網格的像素，而是對網格像素進行尺度自適應［17］。采樣后平均值近似劃分的網格均值效果良好，比例采樣提升了描述符對于尺度變化的魯棒性。M-LDB通過離散點采樣獲得散點的亮度值和水平方向和垂直方向的微分平均值，獲得的運算符是由0和1構成的二值描述符，縮短了計算時間，從而進一步提高算法的實時性能。

2 G-AKAZE算法

2.1 誤匹配點剔除算法

由于運動平滑度的存在所以極不可能在一幅圖像中發生多組隨機對應簇，因此通過簡單地計算特征點鄰域中的匹配數，從而準確區分真假匹配［18］，去除誤匹配點。

如果運動過程是平滑的，相鄰像素和特征點將一起移動。所以假設xi是一對特征匹配的點，2個點各自得到一個匹配統計區域，分別記為a區域和b區域，記統計值為Si。Si服從二項分布：

為了能在保證算法精度的前提下通過統計值的差異更加快速高效地進行誤匹配點剔除，需要將檢測區域擴大。如果檢測區域為圓形可能會造成相鄰區域中間夾縫點的遺漏，所以將統計區域設計為矩形網格，并將統計范圍擴大到周圍相鄰的8個網格，計算以目標特征點所在網格為中心初始網格的共9個網格中的匹配點個數［19］。

計算當xi正確和錯誤時的均值、方差：

圖1 n×n網格圖

為了使特征匹配過程的速度更快，采用一種降低計算復雜度的方法。在原本的特征匹配算法中，每個特征點周圍都需要圈定一個匹配鄰域并計算鄰域中匹配點的統計值，此時算法的計算復雜度為O（N）。如果在進行匹配之初就將圖像分割成網格面，那么只需要同時計算所有網格中匹配點的個數并通過簡單加法直接得出特征點所在3×3的網格中的統計值，算法計算復雜度將是O（1）。在實際應用中，圖像可能會出現旋轉、放縮的情況，那么只需要旋轉、放縮網格即可。圖像相應區域的旋轉方式見圖2。

圖2 圖像相應區域的旋轉方式示意圖

根據經驗和前期實驗數據可以得知判斷閾值：

2.2 改進的G-AKAZE算法

GMS算法采用ORB算法進行特征點檢測與特征點描述，找出與它周圍的大部分點比較都不同的點，再用BRIEF算法計算二進制的描述符。ORB主要應用于場景變化不明顯但需要高速計算的情況下［20］。AKAZE算法與SIFT、SURF相比較，構造尺度空間的方法不同，KAZE與AKAZE是利用非線性方式構造。

為結合2種算法的優勢，嘗試一種新的特征點匹配算法，改進的G-AKAZE算法流程見圖3。

圖3 G-AKAZE算法流程框圖

首先使用非線性方法構造尺度空間，可以自適應地進行濾除小細節保留目標邊緣從而留下更多的特征信息，并用快速顯式擴散數學框架FED來快速求解偏微分方程，從而解決計算量大的問題。下一步用Hessian矩陣檢測出局部極大值得到特征點，在定義域內對2階連續可導多元函數f（x1，x2，…，xn）定義其Hessian矩陣H：

若H是負定矩陣，則臨界點處是局部極大值，即特征點。算法中使用了M-LDB描述子，它采用二進制方法來描述特征點。首先對特征點求一固定大小的窗口，并將該窗口拆分成2×2、3×3和4×4的網格，依次用二值來表示每2個格子之間的關系。M-LDB可以從非線性尺度空間中獲取梯度信息，并且利用特征點檢測步驟中計算出的導數，進一步減少了描述子生成過程中的計算量。在此基礎上，將待匹配圖像進行網格化劃分，并計算每個網格中的特征點數量，再相加得到3×3鄰域網格內的特征點總數，這一步降低了算法復雜度，根據錯誤匹配點極小可能得到其他匹配點的支持這一思想，把與鄰域內的其他特征點匹配相差較遠的剔除，完成去除誤匹配點的過程，最終完成匹配。

3 徽派建筑特征匹配實驗

3.1 實驗數據

徽州傳統建筑隨著時間的推移，會出現不同程度的自然損毀和人為磨損，而信息化技術的發展為徽州傳統建筑的永久保存和有效利用提供了重要技術手段。實驗室目前已建成國內唯一的徽州傳統建筑特征元素數據庫，收集了近100種構件的近萬條相關數據；建成了徽州傳統建筑數據庫，收集了黃山地區100余個聚落，近萬幢建筑的相關信息，利用激光三維掃描技術對具有特殊歷史地位的文物建筑進行了精細測繪，并進一步開展了徽州傳統建筑的虛擬可視化研究，提出了基于幾何參數化的徽派建筑快速建模技術，構建了徽派建筑構件庫和規則庫，建成了徽派建筑虛擬營造系統。在此基礎上，使用已有的徽派建筑數據庫，數據內容較為充足。圖4為實驗所用數據圖，來源于標準數據集VGG和徽派建筑構件。

圖4 實驗所用數據圖，來源于標準數據集VGG和徽派建筑構件

3.2 特征匹配實驗結果

為了驗證提出的兩種算法結合改進的GAKAZE算法匹配效果良好且剔除誤匹配點效果良好，將用對照實驗的方法在標準數據集VGG上對AKAZE與ORB進行對比，再在VGG數據集和徽派建筑構件數據集上進行誤匹配剔除的對比實驗。實驗用圖為標準數據集VGG及本實驗室在徽州建筑群拍攝所得，算法運行時間為3次實驗取平均數（保留小數點后四位數）所得。實驗所用系統為Windows10。

1）ORB＋BF與AKAZE＋BF在VGG數據集的匹配結果見圖5～6。其中，A組兩幅圖片為牛津大學校內的一座橋。B組兩幅圖片為牛津大學校內的一個穹頂建筑物。

圖5 ORB＋BF與AKAZE＋BF匹配 結果對比（A組）

圖6 ORB＋BF與AKAZE＋BF匹配 結果對比（B組）

2）ORB＋BF與AKAZE＋BF在徽派建筑構件數據集的匹配結果見圖7。在相同的實驗條件下，AKAZE可以識別出更多的特征點，ORB需要預先測量特征點的個數進行算法初始化，并預置特征點識別點數。

圖7 ORB＋BF與AKAZE＋BF匹配結果對比

3）G-AKAZE與AKAZE、AKAZE＋RANSAC實驗效果見圖8～16。對應的3種算法耗時實驗結果見表1。

表1 3種算法耗時實驗結果 s

圖8 A1組與A2組中AKAZE的匹配結果

圖9 A1組與A2組中AKAZE＋RANSAC的匹配結果

圖10 A1組與A2組中G-AKAZE的匹配結果

圖11 B1組與B2組中AKAZE的匹配結果

圖12 B1組與B2組中AKAZE＋RANSAC的匹配結果

圖13 B1組與B2組中G-AKAZE的匹配結果

圖14 C1組與C2組中AKAZE的匹配結果

圖15 C1組與C2組中AKAZE＋RANSAC的 匹配結果

圖16 C1組與C2組中G-AKAZE的匹配結果

從實驗結果可以看出：G-AKAZE算法的速度明顯快于原始AKAZE和AKAZE＋RANSAC，對比原始AKAZE、G-AKAZE的算法運行耗時平均降低36.86%；對比于用RANSAC對AKAZE進行誤匹配剔除，算法耗時平均降低76.32%。

3種算法匹配對結果見表2。RANSAC在誤匹配點剔除時，造成了大量的誤剔除，匹配點對的平均保留率為4.66%，使得實驗結果不理想，而G-AKAZE在實驗中表現良好，在剔除誤匹配點的同時保留正確的點，平均保留率為19.64%。

表2 3種算法匹配對結果 對

圖17為2種算法的F值。從精確度和召回率兩方面計算F值，結果表明G-AKAZE的實驗結果優于AKAZE＋RANSAC，F值的平均提高率為14.62%。

圖17 2種算法的F值比較

4 總結

針對徽派建筑群的構件造型區別難以辨別，細節特征差別繁雜，且數據量龐大的特征點匹配問題，G-AKAZE算法很好地實現了匹配，通過實驗驗證其相比原始AKAZE和RANSAC可以更好地剔除誤匹配點，算法耗時平均降低76.32%，且加權調和平均值F值提升了14.62%。實驗中發現G-AKAZE的匹配速度以及誤匹配點剔除精度仍然有改進空間，在后續的研究中希望進一步改進，并能將新算法應用于點云數據的匹配中。