用于圖像匹配的改進Harris特征點檢測算法

扈立超，史再峰，龐 科，劉江明，曹清潔，2

（1.天津大學電子信息工程學院，天津 300072；2.天津師范大學數學科學學院，天津 300387）

用于圖像匹配的改進Harris特征點檢測算法

扈立超1，史再峰1，龐 科1，劉江明1，曹清潔1，2

（1.天津大學電子信息工程學院，天津 300072；2.天津師范大學數學科學學院，天津 300387）

原始Harris特征點檢測算法采用高斯濾波進行平滑處理，增強了其魯棒性，但是也提高了該算法的復雜度，導致其不能應用到許多圖像匹配系統中，還存在對T型和斜T型特征點定位不準確的問題。為此，提出一種新的特征點檢測算法。使用加速分割測試特征的特征點檢測原理排除大量的非特征點，利用鄰域像素比較法消除部分強干擾點，采用改進的高效非極大值抑制算法獲得結果特征點。實驗結果表明，該算法具有較好的匹配精度和較快的檢測速度，檢測時間僅為原始Harris算法的13.9%，適用于實時圖像匹配系統。

機器視覺；圖像匹配；特征點檢測；Harris算法；非極大值抑制

DO I：10.3969/j.issn.1000-3428.2015.10.040

1 概述

圖像匹配是機器視覺與模式識別領域中的一個重要問題，其目的是為2幅不同圖像中的相似目標物建立對應關系，它是眾多視覺任務中的關鍵技術，包括圖像識別、圖像配準、三維重建和目標跟蹤等［1］。隨著一些較好特征提取算子的出現，基于特征點檢測的配準算法應用更加廣泛，對于位置變化、灰度變化以及圖像變形等具有較好的魯棒性，且計算量小、速度較快，是目前研究最多和應用最廣的匹配算法［2］。 其中，基于灰度的特征點檢測算法［3-5］直接對圖像中像素點的灰度值進行處理，避免了基于輪廓的特征點檢測算法［6-8］在提取輪廓時存在的誤差，因此，在實際研究中得到了更多關注。

基于灰度的特征點檢測算法通過使用圖像的一階或二階導數來進行特征點提取。文獻［3］計算各像素點在4個主要方向上的相鄰像素灰度差的平方和，選取最小值作為特征點響應函數，在一定范圍內具有最大特征點響應函數的像素點為特征點。在文獻［3］特征點檢測算法的基礎上，文獻［4］提出了著名的

Harris特征點檢測算法，其廣泛應用于許多計算機視覺任務。它通過引入高斯濾波函數來提高算法的穩定性和魯棒性，但也正因如此該算法的復雜度被提高。由于在計算特征點響應函數時，該算法使用了差分方向導數計算方式，其與理想方向導數間存在誤差從而在非極大值抑制階段排除了真正特征點。

針對上述Harris特征點檢測算法面臨的2個主要問題，本文使用加速分割測試特征（Features from Accelerated Segment Test，FAST）的特征點檢測［5］原理排除大量的非特征點，采用鄰域像素比較法［9］排除強干擾點，使用改進的高效非極大值抑制算法進一步降低算法復雜度。

2 Harris特征點檢測算法

2.1 Harris特征點檢測算法原理

Harris特征點檢測算法是以文獻［3］算法為基礎提出的，是一種基于信號的點特征提取算子。其原理是將待處理的圖像窗口向任意方向做微小的移動，則灰度變化量可定義為：

其中，E（u，ν）為圖像窗口內的灰度變化量；I（χ，y）為圖像灰度函數，［I（χ+u，y+ν）-I（χ，y）］為圖像灰度的梯度值；w（χ，y）為窗口函數，通常為高斯函數。

將式（1）在點（χ，y）處進行泰勒級數展開，并略去無窮小項為：

其中，矩陣M是2×2的實對稱矩陣，通常稱為自相關矩陣，可表示為：

其中，Iχ和Iy分別表示圖像在水平和垂直方向上的梯度。某一點的圖像灰度自相關函數的極值曲率可由自相關矩陣的特征值近似表示，如果自相關矩陣的2個特征值都很大，說明該點的圖像灰度自相關函數的2個正交方向上的極值曲率比較大，此處為一個特征點。

在實際應用算法中，自相關矩陣的特征值分解可由計算如下的特征點響應函數替代：

其中，det（M）=A×B-C2為矩陣M的行列式；trace（M）=A+B為矩陣M的跡；k是一個經驗值，取值范圍在0.04～0.06之間。當R為局部最大值并且大于一個給定閾值時的位置就是特征點。

2.2 Harris特征點檢測算法分析

Harris特征點檢測是當前比較廣泛使用的一種基于圖像灰度的特征點提取算法，其主要優點在于：（1）其計算用到的是圖像的灰度梯度值，所以，對光照是不敏感的。只是由于閾值的選擇會影響特征點檢測的數量。（2）其使用的是特征點附近的區域灰度二階矩矩陣，而二階矩矩陣可表示成一個橢圓。當橢圓轉動時，特征值并不發生變化，所以，其對旋轉是不敏感的。（3）其對圖像中的每一個像素點都計算特征點響應函數，然后在鄰域范圍內尋找最優值，所以，其提取的特征點均勻且合理。

但是Harris特征點檢測算法也存在著一些缺點，主要表現在：（1）引入高斯濾波函數進行平滑操作，雖然增強了算法的魯棒性，但是由于高斯卷積計算量大，使得算法的復雜度被提高。并且該算法對整個圖像的每個像素點都進行特征點響應函數計算和非極大值抑制操作，使得其檢測效率非常低。（2）其特征點定位有偏差，特別是對 T型和斜 T型特征點定位不準確。文獻［9］對5種類型的特征點進行了實驗，檢測結果表明Harris特征點檢測算法對T型特征點在水平方向有一個像素的偏差，對斜T型特征點在水平和垂直方向均有一個像素的偏差。

3 改進的Harris特征點檢測算法

3.1 檢測效率改進

一幅圖像中的特征點數量往往占不到全部像素點的1%，如果對全部像素點均進行檢測，必然會造成效率的降低。針對該問題，本文首先利用FAST特征點檢測算法原理來排除大量的非特征點。FAST算法以一個半徑為3的Bresenham圓作為測試模板，圓上一共有16個點，中心點為待測像素點，如圖1所示。

圖1 FAST算法圓形模板示意圖

如果此圓上至少有12個連續點的灰度值大于或者小于中心點的灰度值加上或者減去一個閾值，

那么此中心點被認為是一個特征點。

因為12個連續點必然包括像素點1，5，9和13中的3個，所以本文首先檢測像素點1和像素點9。如果它們的灰度值均與中心點的灰度值相似，那么此中心點不是特征點，將其排除，否則繼續檢測像素點5和13。如果這4個像素點中至少有3個點的灰度值大于或者小于中心點的灰度值加上或者減去一個閾值，那么將此中心點記為候選特征點，供算法后續處理。但是，如果在這4個像素點中僅有2個相鄰點的灰度值，遠大于或者遠小于中心點的灰度值，那么此中心點仍然可能是一個特征點，也將其記為候選特征點。通過此步驟能夠排除大量的非特征點，所以，檢測效率被劇烈提升。

3.2 匹配精度改進

對于提高算法的匹配精度，本文采用文獻［9］算法，并在此基礎上做一些改進，以便更適合本文算法。對于目標像素點，考慮其8鄰域范圍內的像素點，計算該范圍內的像素點與目標像素點的灰度差值的絕對值，如果該值小于等于預設的閾值，則認為該像素點與目標像素點相似［9］。最后統計8鄰域范圍內相似點的個數，并根據相似點個數對目標像素點進行分類。文獻［9］的目標像素點是一幅圖像中的所有像素點，而本文的目標像素點只針對候選特征點。設8鄰域內相似點個數為n，則目標像素點的分類情況如下：

（1）n=8，表示鄰域內像素點均與目標像素點相似，所以，該點為一平坦區域內的點，因此，該點要被排除掉。

（2）n=7，可能的特征點為與目標像素點不相似的那個像素點，所以，該點要被排除掉。

（3）2≤n≤6，這種情況無法確定目標像素點性質，將此點進行保留。文獻［9］對n=5的情況做了進一步的討論，其考慮到了目標像素點左右兩側像素點的n值，而本文不再對其進行分析，因為本文為了提升檢測效率，只計算候選特征點的相似點個數，所以目標像素點左右兩側像素點的n值可能并沒有被計算。

（4）n=1，這種情況下的目標像素點可能為特征點，也可能為離散的噪聲點，此時，需要考察24鄰域內與目標像素點相似的個數，如果相似點個數仍然較小或者比例不變，那么可以認為該點為噪聲點，將其排除。

（5）n=0，表示目標像素點鄰域內沒有與之相似的像素點，所以，該點為孤立像素點或者噪聲點，將其排除。

通過此步驟能夠排除強干擾點，從而實現對T型和斜T型特征點的準確定位，并且本文提出的算法仍然具有Harris特征點檢測算法對其他類型特征點定位準確的優點。

3.3 改進的高效非極大值抑制

非極大值抑制能夠在一定范圍內尋找到一個最大值，同時，把其他值排除掉。在特征點檢測算法中，如果一個像素點的特征點響應函數為局部最大值并且大于一個給定閾值，那么此點被認為是一個特征點。Harris特征點檢測算法計算每一個像素點的特征點響應函數，并以每一個像素點為中心執行非極大值抑制，這必然會造成檢測效率的降低。因為一旦一個局部最大值被搜索到，那么在一定范圍內必然不會出現另一個最大值，這意味著不需要在這個范圍內繼續以其他像素點為中心來執行非極大值抑制。

文獻［10］提出了高效非極大值抑制算法，從而很好地解決了低效率的問題，如圖2所示，非極大值抑制窗口為（2n+1）×（2n+1）。首先，它將圖像劃分為多個（n+1）×（n+1）的塊。其次，在每一個塊中尋找最大值，如圖2中的黑點表示每個塊中的最大值。最后，對于每一個塊中的最大值，其完整鄰域被測試，如圖2中像素點a的虛線窗口。

圖2 高效的非極大值抑制算法

雖然高效非極大值抑制算法能很好地解決原始算法的低效率問題，但是要將其運用到特征點檢測領域必然會呈現出一個缺陷。因為該算法將圖像中的所有區域均進行劃分，并在每塊區域上執行非極大值抑制，而有些區域為平坦區域，特征點是不可能出現在這些平坦區域中，所以該算法不可避免地提高了復雜度。所以，本文在應用該算法之前做了一些改進，以降低其復雜度。

通過3.1節，已經排除掉大量的非特征點，同時得到候選特征點隊列。首先，以一個候選特征點為中心，形成一個（n+1）×（n+1）的區域。其次，在該區域中尋找具有最大響應函數的候選特征點，同時將其他候選特征點從隊列中刪除。再次，對該候選特征點做完整鄰域的測試。最后，按照以上3步遍歷所有剩余的候選特征點。據此，高效非極大值抑制算法應用到特征點檢測領域所遇到的問題便被有效地解決。

4 實驗結果與分析

為了更好地客觀評價本文算法，本文引入特征點檢測常用的2個關鍵評價指標：特征點數量一致性（CCN）和精確度（ACU）。文獻［11］提出定義如式（5）所示的CCN準則和定義如式（6）所示的ACU準則：

其中，No是原始圖像中被檢測到的特征點數量；Nt是變換圖像中被檢測到的特征點數量。特征點檢測算法的穩定性越強，其CCN值越高。

其中，No是原始圖像中被檢測到的特征點數量；Na是被檢測到的特征點中所包含的真正特征點的數量；Ng是真正特征點的數量。特征點檢測算法的定位準確性越強，其ACU值越高。

為了評估本文算法，進行了大量實驗，并與原始Harris特征點檢測算法［4］和FAST-9特征點檢測算法［5］進行了比較。測試圖像及其全部特征點位置如圖3所示，圖中每一個點表示一個特征點。此測試圖像一共有38個特征點。

圖3 測試圖像及其特征點

實驗結果如表1所示。其中，分別包括每一種算法所檢測到的真正特征點數量、所漏報的特征點數量、所誤報的特征點數量、ACU結果和每一種算法的運行時間。由結果可知，本文算法擁有最好的精確度和最快的檢測速度，檢測時間僅為原始Harris算法的13.9%，適用于實時圖像匹配系統。

表1 3種特征點檢測算法的檢測結果

為了評估特征點檢測算法的重復性，本文對圖像施加了縮放變換。算法的重復性越高，在縮放變換下其檢測到的特征點數量越不會發生變化，說明該算法的穩定性越好。通過使用雙三次插值算法來實現圖像的縮放變換，縮放倍數區間為［1.0，2.0］。本文對原始圖像在［1.0，2.0］的區間內以0.2的間隔分別施以縮放變換，使用這3種特征點檢測算法提取縮放圖像中的特征點，根據式（5）分別計算每個縮放圖像的CCN值，并對所有的CCN求出平均值。在［1.0，2.0］縮放倍數區間內提取的特征點數量及其平均CCN值如表2所示。從平均CCN的結果可知，本文算法的重復性最高，在圖像發生縮放變換下，仍能很好地進行匹配。

表2 3種算法在縮放倍數區間內的實驗結果

本文分別使用這3種算法提取2幅待匹配圖像的特征點，然后利用歸一化互相關算法［12］進行2幅圖像特征點的匹配，匹配對數占所提取的特征點比重越大，說明該算法檢測出的特征點越準確，匹配精度越好。匹配結果如圖4所示，相同的數字表示相匹配的特征點。

圖4 特征點匹配結果

實驗結果如表3所示。其中，分別包括每一種算法所檢測到的圖4左圖特征點數量、右圖特征點數量、2幅圖像相匹配的特征點對數量和匹配率。由結果可知，本文算法擁有最好的匹配精度，優于另外2種算法。

表3 3種特征點檢測算法的匹配結果

5 結束語

本文提出一種改進的Harris特征點檢測算法。通過使用FAST特征點檢測原理排除大量的非特征點，對高效非極大值抑制算法進行改進，降低原始算法的復雜度，通過使用鄰域像素比較法排除一些強干擾點，實現對 T型和斜 T型特征點的準確定位。實驗結果表明，該算法的特征點定位精度和縮放不變性要優于其他算法，并且擁有較快的檢測速度和最高的特征點匹配率。今后考慮將Harris特征點檢測精度由像素級提高到亞像素級，從而進一步完善算法的檢測性能。

［1］ 吳振國，楊紅喬.一種具有仿射不變性的圖像匹配算法［J］.計算機工程，2013，39（8）：215-218.

［2］ 曾 巒，王元欽，譚久彬.改進的SIFT特征提取和匹配算法［J］.光學 精密工程，2011，19（6）：1391-1397.

［3］ Moravec H P.Towards Automatic Visual Obstacle Avoidance［C］//Proceedings of the 5th International Joint Conference on Artificial Intelligence.Cambridge，USA：M IT Press，1977：584-590.

［4］ Harris C，Stephens M.A Combined Corner and Edge Detector［C］//Proceedings of the 4th Alvey Vision Conference.Manchester，UK：［s.n.］，1988：147-151.

［5］ Rosten E，Porter R，Drummond T.Faster and Better：A Machine Learning Approach to Corner Detection［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（1）：105-119.

［6］ Mokhtarian F，Suomela R.Robust Image Corner Detection Through Curvature Scale Space［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1998，20（12）：1376-1381.

［7］ He Xiaochen.Corner Detector Based on Global and Local Curvature Properties［J］.Optical Engineering，2008，47（5）.

［8］ Awrangjeb M，Lu Guojun.Robust Image Corner Detection Based on the Chord-to-point Distance Accumulation Technique［J］.IEEE Transactions on Multimedia，2008，10（6）：1059-1072.

［9］ 王 崴，唐一平.一種改進的Harris特征點提取算法［J］.光學 精密工程，2008，16（10）：1995-2001.

［10］ Neubeck A，Gool L V.Efficient Non-maxim um Suppression［C］//Proceedings of the 18th International Conference on Pattern Recognition.Washington D.C.，USA：IEEE Press，2006：850-855.

［11］ Mokhtarian F，Mohanna F.Performance Evaluation of Corner Detectors Using Consistency and Accuracy Measures［J］.Computer Vision and Image Understanding，2006，102（1）：81-94.

［12］ Tsai Duming，Lin Chienta.Fast Normalized Cross Correlation for Defect Detection［J］.Pattern Recognition Letters，2003，24（15）：2625-2631.

編輯 劉冰

Improved Harris Feature Point Detection Algorithm for Image Matching

HU Lichao1，SHI Zaifeng1，PANG Ke1，LIU Jiangming1，CAO Qingjie1，2
（1.School of Electronic and Information Engineering，Tianjin University，Tianjin 300072，China；2.School of Mathematical Sciences，Tianjin Normal University，Tianjin 300387，China）

By using Gaussian filtering for smooth processing，the original Harris feature point detection algorithm enhances its robustness.But it also increases the complexity of the algorithm which can not be applied to many image matching systems.Its positioning accuracy of T-type and diagonal T-type feature points is low.In order to solve the above problems，a new feature point detection algorithm is proposed.Amounts of non-feature points are excluded by using the principle of Features from Accelerated Segment Test（FAST）feature point detection.Some strong interference points are ruled out by using neighborhood pixels comparison method.The resulting feature points are obtained by using the improved efficient non-maximum suppression algorithm.Experimental results demonstrate that the improved algorithm has better matching accuracy and higher detection speed，its detection time is only approximately 13.9%that of the original Harris algorithm and it is quite suitable for real-time image matching system s.

machine vision；image matching；feature point detection；Harris algorithm；non-maximum suppression

扈立超，史再峰，龐 科，等.用于圖像匹配的改進 Harris特征點檢測算法［J］.計算機工程，2015，41（10）：216-220.

英文引用格式：Hu Lichao，Shi Zaifeng，Pang Ke，et al.Improved Harris Feature Point Detection Algorithm for Image Matching［J］.Computer Engineering，2015，41（10）：216-220.

1000-3428（2015）10-0216-05

A

TP391

國家“863”計劃基金資助項目（2012AA012705）；國家國際科技合作專項基金資助項目（2012DFB10170）。

扈立超（1988-），男，碩士研究生，主研方向：數字圖像處理；史再峰，講師；龐 科，博士研究生；劉江明，碩士研究生；曹清潔，博士研究生。

2014-11-03

2014-11-27E-mail：hulichao@tju.edu.cn