快速特征提取與感知哈希結合的圖像配準算法

宋　博，姜萬里，孫　濤，熊正強，芮華建

SONG Bo1,JIANG Wanli2,SUN Tao1,XIONG Zhengqiang1,RUI Huajian1

1.武漢大學 電子信息學院，武漢 430072

2.陸軍軍官學院，合肥 230031

1.School of Electronics and Information,Wuhan University,Wuhan 430072,China

2.Army OfficerAcademy of PLA,Hefei 230031,China

1　引言

圖像特征點配準廣泛應用于三維重建、醫學制導、圖像拼接等領域中，是計算機視覺領域中基礎而又重要的課題[1-3]。圖像特征點是指能夠有效表達圖像本質的點，而圖像特征點匹配是指在圖像中找出有效的匹配點對，進而實現圖像配準。圖像配準是圖像處理領域中的一項關鍵技術，一直以來很多學者在此方面做了大量的工作，研究的焦點多集中在匹配的準確率和實時性等方面。

基于特征的圖像配準方法是利用圖像的特征信息實現配準。例如Harris算法，分別在模板圖像和待配準圖像上，提取Harris角點信息，然后利用相關系數關系，在待匹配圖像中搜索出相關性最大的位置，但是這種方法不具有尺度和旋轉不變性[4]。2004年，Lowe提出的SIFT（Scale Invariant Feature Transform）算法，通過引入高斯拉普拉斯算子實現了特征點的尺度旋轉不變性，進一步實現了圖像的自動配準，但是因為算法要遍歷整幅圖像求解，相應地也增加了運算工作量，不能達到實時性的要求[5]。2006年，Bay等[6]在SIFT算法基礎上，提出了SURF（Speeded Up Robust Features）算法，該方法利用Haar小波，計算特征點的主方向，提高了圖像配準的速度，但是仍然不能達到實時性的要求。對于紋理信息豐富的圖像，Rosten等[7-8]研究了實時性更強的FAST特征檢測算法，但是該算法不具備縮放旋轉不變性。文獻[9]對具有代表性的特征準點算法進行了分析，證明了SURF算法是綜合性能最好的算法。2015年，Yang等[10]利用限制SURF算法提高了圖像的匹配速度。Lin等[11]在2015年提出利用全局相似變換進行圖像配準，提高了圖像配準精度，但是在前期特征提取部分仍采用SIFT算法全局處理，沒有針對性地改善特征提取過程中計算量較大的問題，實時性不足。雒培磊等[12]基于深度學習的方法對遙感影像進行拼接，雖然通過十字點集的方法提前剔除誤匹配點，降低了圖像拼接總時間，但是配準過程的時間消耗相比SIFT卻略有增加。此外，文獻[13-14]采用GPU、多核并行計算等硬件加速的方法實現配準，但是該類方法對硬件要求較高，存在一定的經濟成本。

針對特征點匹配中在耗時和精度方面的缺陷，本文對算法進行改進，提出了一種快速圖像配準方法。先采用高斯拉普拉斯算子構建邊緣稀疏矩陣，之后采用耗時較少的改進后的FAST算法進行特征點的提取，為了提高算法性能，對圖像進行高斯拉普拉斯加權從而結合梯度信息求解。此外，采用感知哈希算法對匹配對提純，在此基礎上通過RANSAC算法得到單應性矩陣最優參數后，又依據仿射不變性建立約束條件對單應形矩陣進行校驗。實驗表明，本文提出的配準方法具有良好的性能。

2　圖像快速配準算法

2.1　特征點快速檢測提取

2.1.1構建邊緣稀疏矩陣

傳統的特征檢測是對整幅圖像進行遍歷計算，計算量是m×n（m是圖像的高度，n是圖像的寬度），會產生大量的特征信息，從而影響圖像/視頻幀的匹配時間。圖像的邊緣包含了圖像的大部分信息，通過高斯拉普拉斯算子（Laplacian of Gaussian，LoG）檢測出圖像的邊緣區域，然后在邊緣區域上進行特征點檢測能夠極大程度上增加檢測特征點的穩定性，同時可以大大降低計算量。另一方面，圖像特征的質量，影響著圖像的匹配準確率，好的特征點應該具有好的魯棒性。特征點一般位于一階導數極大值點，轉換為二階導數，也就是位于二階導數為零的點。一般直接求一階導數的極大值比較復雜，而通過求解二階導數為零的點，可以減少計算量，節省耗時。

本文采用LoG算子來計算局部特征，它是一種二階導數算子，具有各向同性的邊緣檢測算子，能對任何方向的線條進行銳化，且不具有方向性，這是高斯拉普拉斯算子最大的優點。對于函數 f(x,y)，在點(x,y)處的拉普拉斯算子如公式（1）所示：

在實際圖像邊緣檢測中，采用如式（2）所示高斯拉普拉斯算子模板M計算梯度值，模板的中心系數為正數，其余的系數為負，所有模板的系數之和為零。

通過高斯拉普拉斯算子求得圖像的梯度信息之后，邊緣圖像中仍然存在著一些梯度值較小的像素點以及因噪聲等因素存在的梯度值較大的像素點。這些信息對于特征點的提取會造成干擾，同時導致提取到的特征點數量過多，影響效率。因此，實際中需要設置適當的梯度閾值進行過濾，提取邊緣稀疏矩陣。

如圖1顯示了實際過程梯度閾值的設置流程。首先，根據潛在邊緣點的梯度分布直方圖得到梯度幅值的遞增排列，初始值選取遞增方向達到總數80%的邊緣點對應的梯度值為高閾值TGmax，低閾值TGmin為高閾值的一半。然后，根據邊緣點像素個數占總像素比例對稀疏度進行判斷，本文中設置判斷參考范圍為3%～10%。若未滿足要求，則根據浮動閾值ΔT進行微調。實驗中，大多數情況下使用初始閾值便可達到稀疏度要求，甚至有些情況直接得到的邊緣矩陣已經滿足稀疏度條件。

圖1　梯度閾值設置示意圖

通過邊緣稀疏矩陣提取對應的像素信息，剔除了部分弱邊緣的像素點，減少了噪聲的干擾，同時保留了大部分邊緣信息。對于紋理較平坦的圖像，因稀疏度判斷并不會丟失主要信息；對于紋理豐富的圖像，剔除了部分邊緣，從而減少計算量，盡管存在部分特征點的丟失，但圖像配準過程中理論上只需要四對準確的匹配點對，就可以獲得準確的單應性矩陣，在實驗過程中，保留的邊緣信息中存在足夠的準確的匹配點對。

2.1.2優化的FAST特征點檢測

FAST是一種角點檢測方法，該方法最早是由Edward Rosten和Tom Drummond提出的，該方法最明顯的優點是它高效的計算速度。

如圖2所示，FAST特征點檢測的方法是在以P像素為中心的圓周上按順時針方向從1到16的順序對圓周像素點進行編號。根據式（3）所示，如果在圓周上有N個連續的像素的亮度都比圓心像素的亮度lp加上閾值th還要亮，或者比圓心像素的亮度lp減去閾值th還要暗，則圓心像素被稱為候選特征點[15]。

圖2　FAST特征點檢測示意圖

目前使用FAST算法可以通過先檢測非特征點的像素點來提高檢測速度，但是FAST特征點檢測算法只考慮了中心像素與圓周上的像素的關系，這導致該方法僅對圓周邊緣區域進行特征點檢測，并沒有結合圓周內部像素點的信息，導致檢測的特征點較少以及誤檢測現象發生。在已通過LoG算子求得梯度信息之后，如式（4）所示，考慮將需要檢測的圓心像素I0(x,y)的鄰域（圓周內部像素）的梯度信息加權融合至圓心像素以在保持FAST算法穩定性的基礎上增加檢測特征點的數目。

在式（5）的基礎上，使用FAST特征點檢測算法對特征點進行提取，當α?LoG?I(x,y)＞0時，則說明該待檢測點是較亮點，通過梯度加權值變小，則增加了該點比圓周上N個連續的像素點都亮的可能性；當α?LoG?I(x,y)＜0時，說明該待檢測點是較暗點，通過梯度的加權，值變小，則增加了該點比圓周上N個連續的像素點都暗的可能性。通過在檢測過程中加入梯度信息，從而調節了FAST特征點判斷的閾值范圍，相當于利用梯度信息對候選特征點進一步篩選，使得對圖像中存在的陰影、噪聲、亮度變化等具有更強的適應能力，可以增加特征點檢測數目，使特征點提取更加穩定。

2.2　誤匹配對剔除

2.2.1感知哈希算法優化匹配對

特征點匹配的好壞直接影響圖像配準的結果，而特征點匹配因閾值、噪聲等原因總會存在誤匹配點。在計算變換參數之前移除誤匹配點，能夠提高配準精度，同時降低計算復雜度。本文提出使用均值感知哈希方法[16]提純匹配點對，該方法以匹配點對為中心，以特征點的主方向為水平方向，提取一定大小的圖像塊計算得到該特征點的哈希指紋，通過匹配點對哈希指紋的對比驗證來判斷該匹配點對是否正確匹配。

均值感知哈希利用圖像的低頻信息計算哈希指紋，相比其他感知哈希算法[17]具有較快的運行速度，通過比較兩幅圖的哈希指紋就可以判斷兩幅圖像是否相似[18]。哈希指紋一般是在8×8圖像大小尺寸下獲得的0、1哈希值組合，通過計算比較相同位置哈希值不同的個數，如果不同的個數為0，則這兩張圖片非常相似，如果這兩張圖片的哈希距離的不同個數小于5，則這兩幅圖像相似，否則認為這兩幅圖像差別很大，不相似。

在獲得匹配對之后，對于準確的匹配點對，其所處圖像區域也是相似的；對于錯誤的匹配點對，其所處圖像區域是有差異的[19]。根據這一特性，結合感知哈希算法對匹配對進行校驗，剔除錯誤的匹配對，具體的算法流程如下。

步驟1選取特征點鄰域尺寸：以特征點的主方向為垂直方向，然后以通過FAST提取的特征點為中心，因為特征點距圓周邊緣的最小尺寸為3，為了更好地保留邊緣特征點，所以選取7×7的正方形作為感知哈希校驗區域。

步驟2簡化色彩：將步驟1中獲得7×7圖像轉換為7×7灰度圖像。

步驟3計算像素灰度平均值：計算步驟2中得到的7×7灰度圖像的49個像素的灰度平均值。

步驟4比較像素灰度值：將步驟2得到的7×7灰度圖像的每個像素與步驟3中得到的7×7灰度圖像的灰度平均值進行比較，大于平均值的記為1，小于平均值的記為0。

步驟5計算哈希值：將步驟4中得到的49個0、1按固定的順序組合起來，這樣就得到了該以特征點為中心的哈希指紋。

步驟6匹配點提純：通過比較步驟5中獲得的哈希指紋，統計49個相同位置的值的不同的個數，如果不同的個數小于5，則認為這對匹配點對是正確匹配的，否則不是正確的匹配點對。

如圖3（a）所示，在SURF描述符下使用FAST算法得到的匹配點對，此時未使用感知哈希驗證，可以看到圖中存在數對誤匹配對。圖3（b）為按照上述誤匹配剔除算法對圖3（a）中匹配點對進行提純，可以看到圖3（a）中原來存在的誤匹配對已全部被剔除。

圖3　圖像匹配點對感知哈希算法驗證前后對比

在對匹配對進行提純之后，使用RANSAC算法來進行迭代尋找最佳的單應性矩陣。因為經過一次提純，剔除了錯誤的匹配對，減少了樣本數據集中的無效數據，使得在匹配點數據集中迭代尋找最優參數矩陣更加高效。

2.2.2單應性矩陣準確性校驗

在視頻圖像匹配中，經過前述步驟并不能判斷圖像是否正確匹配。Lin等[20]曾在2016年利用改進的Seamdriven并且加入了曲線和直線結構保持約束，進一步提高了圖像配準精度。本文根據圖像的仿射變換的特性，提出了相應的約束條件進行校驗，進而去除干擾圖像。

平面圖像的仿射變換應具有以下特性：共線線段單比不變性、直線的平行性[21]。已知四點 Pi(xi,yi)(i=1,2,3,4)，且其中直線P1P2與直線P3P4平行，那么經過仿射變換后

由直線的平行性可得：

因直線P1P2與直線P3P4平行，故經過仿射變換后理論上也是平行的，但是在實際中總會存在一定誤差，式（6）中β是變換后兩平行線斜率差的閾值。

由共線線段單比不變性可得：

通過式（6）、（7）所示約束條件，對所得單應性矩陣準確性進行校驗，不滿足閾值約束條件的結果被判定為錯誤的配準結果。

3　實驗分析

實驗平臺硬件環境：Intel?Core? i5 2.50 GHz CPU，4 GB RAM；軟件環境：Windows 7旗艦版系統，Microsoft Visual Studio 2010，Visual C++，Open_CV_VERSION 2.4.8。默認采用的梯度閾值TGmin=20，TGmax=40，FAST特征點選取閾值th=30，仿射不變性閾值β=γ=0.2，拉普拉斯加權系數α=0.075，漢明閾值為2倍的最小距離。在實際不同的場景中，提取的特征點數量存在差異，實驗中特征點的提取數量范圍設定為80～120。

（1）仿射不變性校驗

為驗證本文所提仿射不變性約束條件在匹配過程中的有效性，對不同算法在匹配圖像中存在和不存在目標物體（課本）情況下的匹配結果進行對比分析。

如圖4所示，第一行是SIFT算法處理結果，第二行是SURF算法處理結果，第三行是ORB算法處理結果，第四行是本文算法處理結果。第一列是SIFT、SURF、ORB和本文算法分別對含有目標物體（課本）圖像匹配的結果，可以看出都能很好地匹配到目標，SIFT和SURF算法匹配到的特征點較多，但存在的誤匹配對也較多，ORB和本文算法匹配對較少；第二列匹配圖像中不存在目標物體情況下四種算法的匹配結果，可以看到SIFT、SURF、ORB方法均匹配到了大量的匹配點對，本文算法也存在少量的匹配對，但是實際并不存在目標。第三列圖像為四種方法在第二列圖像匹配基礎上標記出的匹配結果，可以看到只有本文算法最終未標記出目標物體匹配結果，這是因為本文算法利用圖像變換的仿射不變性，對匹配結果進行判斷處理后的結果，可以看出，算法能夠在不存在目標時，很好地糾正誤匹配結果。

圖4　匹配圖像中存在和不存在目標物狀態下SIFT、SURF、ORB及本文算法的特征點匹配結果

（2）縮放、旋轉和噪聲匹配性能分析

為檢驗本文算法的縮放、旋轉和噪聲匹配性能，選擇標準Lena圖像（512×512）為參考圖像，以存在縮放旋轉的高斯噪聲Lena圖像為待匹配圖像，其獲取方法為：對標準Lena圖像，加高斯白噪聲，然后對圖像進行橫向4/5，縱向6/5的縮放，然后順時針旋轉35°。將本文算法與SIFT、SURF、ORB算法進行匹配性能比較。實際實驗過程中，避免匹配過程特征點數過多，對圖像進行一次下采樣處理，以便后續計算。另外，SIFT、SURF、ORB算法匹配對提取最優匹配點時采用的漢明距離閾值是2.5倍的最小距離。

圖5為在前述縮放、旋轉和噪聲情況下，幾種算法的特征點匹配結果對比。圖5（a）為SIFT算法匹配結果，41個匹配對中有3對誤匹配，誤匹配率約為7.32%；圖5（b）為SURF算法匹配結果，32個匹配對中，有16對誤匹配，誤匹配率為50%；圖5（c）為ORB算法匹配結果，31個匹配對中，有1個誤匹配對，誤匹配率約為3.23%；圖5（d）為本文算法匹配結果，在32個匹配對中，有4對誤匹配，誤匹配率約為12.5%。從仿真實驗結果來看，在圖像存在噪聲、縮放和旋轉的情況下，ORB、SIFT和本文算法都表現出很強的魯棒性，SURF性能最差。

如圖6所示，使用所提算法對不同場景下實際拍攝圖像進行實驗驗證結果，圖像中方框標記出為匹配出的目標物體（課本）。第一行為待匹配圖像由大到小情況下的縮放匹配結果；第二行為待匹配圖像在不同旋轉角度情況下的匹配結果；第三行是待匹配圖像不同投影變換下的匹配結果；第四行為待匹配圖像在被部分遮擋情況下的匹配結果；第五行為待匹配圖像在光照條件從暗至亮發生變化情況下的匹配結果。從實驗結果中可以看出本文算法在圖像存在一定縮放、旋轉、投影變換、遮擋和光照變化的情況下，都能夠很好地實現圖像的匹配，具有很好的魯棒性，而且在經過感知哈希與仿射不變性的進一步校驗之后，具有很少的誤判斷。

圖5　本文算法與經典算法Lena圖像特征點匹配結果對比

圖6　不同場景下實拍圖像本文算法特征點匹配結果

（3）運行效率分析

為檢驗算法的運行效率，選擇標準Lena圖像（512×512）進行特征描述仿真實驗，將本文算法結果與SIFT、SURF、ORB算法結果進行對比分析。得到四種算法的特征點提取具體耗時如表1所示，表中時間均為連續處理10次之后的平均值。

由表1中對單個特征點描述所用時間的平均值可知，本文算法速度最快，約是SIFT算法耗時的1/160，約是SURF算法耗時的1/75，約是ORB算法的1/14。從總耗時來看ORB算法耗時最短，主要原因是本文算法為解決FAST算法下某些特征點難以提取的問題，利用高斯拉普拉斯算子加權從而增加了FAST算法檢測的特征點數。

表1　本文算法與經典算法性能比較

如圖7為一段視頻序列圖像中沒有目標、出現目標、目標消失過程中本文方法連續運行耗時曲線。兩條垂直標記線分別表示目標49幀開始出現及97幀目標消失，標記線之間表示在目標出現在視頻期間利用本文算法對目標進行匹配的耗時，其他區間為無目標時處理耗時。在49～97幀出現目標時，單幀處理最大耗時為50 ms，而整個區間變化穩定在30～40 ms，在無目標匹配過程中，單幀處理耗時基本穩定在20～30 ms。在曲線中出現峰值，產生的原因可能有兩個：（1）視頻中出現噪聲，造成圖像稀疏矩陣中非零個數增加，增加了計算量；（2）可能是算法中梯度閾值、FAST特征閾值的更新或高斯拉普拉斯算子的加權系數的更新，增加了計算量。但是總體上看，本文算法的處理速度整體小于50 ms/幀，具有良好的實時性以及魯棒性。

圖7　視頻序列圖像匹配耗時變化曲線

（4）圖像配準結果分析

為驗證本文算法整體性能，對無人機航拍得到的實際序列圖像進行了實驗驗證，其中，無人機航拍序列圖像第60幀和96幀配準結果如圖8所示。在圖8中，暗度較低的部分是第60幀圖像經過降低亮度顯示的結果，亮度較高的是第96幀圖像，這樣處理是為了方便對圖像的配準結果進行分析比較，圖中箭頭標記序號為配準結果比對位置。圖8（a）是利用SIFT算法進行配準的結果，可以看出利用SIFT算法進行配準的結果在1和2處的線性區域具有一定的錯位，在3處房子明顯出現了錯位。圖8（b）是利用SURF算法進行配準的結果，可以看出SURF算法在1處具有較好的配準效果，在2處公路的行車線則出現錯位，在3處出現了明顯的錯位，4處甚至都出現明顯的誤配準。圖8（c）是利用本文算法進行配準的結果，可以看出本文算法最終在3處配準比對位置的配準結果都具有較好的直觀效果，沒有出現因誤匹配導致的變形和錯位現象。實驗結果表明，本文提出的算法在配準精度上要優于SIFT和SURF算法。

圖8　本文算法與SIFT、SURF算法圖像配準結果對比

4　結束語

針對經典的特征點算法是從整個圖像進行遍歷來確定特征點的問題，本文提出了一種先建立圖像邊緣稀疏矩陣，在其基礎上利用改進的FAST算法快速提取特征點，再通過SURF描述符為特征點構建描述向量。獲得匹配點對后，利用均值感知哈希算法對匹配點對提純，之后再使用RANSAC算法尋找最優參數矩陣，并結合仿射不變性對單應性矩陣進行校驗，提高圖像配準準確度。實驗結果表明，本文算法具有很好的配準精確性、時效性以及魯棒性。

參考文獻：

[1]Burger W，Burge M J.Digital image processing：An algorithmic introduction using Java[M].Berlin：Springer，2016.

[2]Oliveira F P M，Tavares J M R S.Medical image regis-tration：A review[J].Computer Methods in Biomechanics and Biomedical Engineering，2014，17（2）：73-93.

[3]Adel E，Elmogy M，Elbakry H.Image stitching based on feature extraction techniques：A survey[J].International Journal of Computer Applications，2014，99（6）：1-8.

[4]Harris C.A combined corner and edge detector[C]//Proc of Alvey Vision Conf，1988：147-151.

[5]Lowe D G.Distinctive image features from scale-invariant keypoints[C]//International Journal of Computer Vision，2004，60（2）：91-110.

[6]Bay H，Tuytelaars T，Van Gool L.Surf：Speeded up robust features[C]/Proceedings of European Conference on Computer Vision（ECCV 2006），2006：404-417.

[7]Rosten E，Drummond T.Machine Learning for High-Speed Corner Detection[C]//Proceedings of European Conference on Computer Vision，2006：430-443.

[8]Rosten E，Porter R，Drummond T.Faster and better：A machine learning approach to corner detection[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，2010，32：105-119.

[9]Mikolajczyk K，Schmid C.A performance evaluation of local descriptors[J].IEEE Trans on Pattern Aralysis&Machine Intelligence，2005，27（10）：1615-1630.

[10]Yang K.Missile placement analysis based on improved SURF feature matching algorithm[C]//Proceedings of International Conference on Graphic and Image Processing，2015.

[11]Lin C C，Pankanti S U，Ramamurthy K N，et al.Adaptive as-natural-as-possible image stitching[C]//Proceedings of International Conference on Computer Vision and Pattern Recognition，2015：1155-1163.

[12]雒培磊，李國慶，曾怡.一種改進的基于深度學習的遙感影像拼接方法[J].計算機工程與應用，2017，53（20）：180-186.

[13]Daga P，Chadebecq F，Shakir D C S，et al.Real-time mosaicing of fetoscopic videos using SIFT[C]//Proceedings of SPIE Medical Imaging，2016.

[14]曹國剛，張晴，張培君，等.基于多核并行化差異進化算法的圖像配準方法[J].計算機工程與應用，2017，53（20）：166-172.

[15]安維勝，余讓明，伍玉鈴.基于FAST和SURF的圖像配準算法[J].計算機工程，2015，41（10）：232-235.

[16]Haviana S F C，Kurniadi D.Average hashing for perceptual image similarity in mobile phone application[J].Journal of Telematics and Informatics，2016，4（1）：12-18.

[17]Niu X M，Jiao Y H.Overview of perceptual hashing[J].Acta Electronica Sinica，2008，36（7）：1405-1411.

[18]丁凱孟，朱長青，盧付強.基于自適應格網劃分的遙感影像感知哈希認證算法[J].武漢大學學報：信息科學版，2015，40（6）：716-720.

[19]Jaewook J，Gunho S，Bang K，et al.Matching aerial images to 3D building models using context-based geometric hashing[J].Sensors，2016，16（6）：932.

[20]Lin K，Jiang N，Cheong L F，et al.SEAGULL：Seamguidedlocalalignmentforparallax-tolerantimage stitching[C]//ProceedingsofEuropeanConferenceon Computer Vision（ECCV 2016），2016.

[21]Demir B，Bruzzone L.Hashing-based scalable remote sensing image search and retrieval in large archives[J].IEEE Transactions on Geoscience&Remote Sensing，2016，54（2）：892-904.