基于模板邊緣的自適應Harris角點檢測算法

李冰 呂進來 郝曉麗

摘 ?要： 針對傳統Harris算法檢測的角點出現聚簇、偽角點以及閾值人為設定的問題，提出一種基于模板邊緣的自適應Harris算法。首先，利用局部區域的思想檢測出圖像中的潛在角點區域;然后，對潛在角點區域利用改進的自適應閾值Harris算法進行角點提取;最后，提出模板邊緣的思想，構造一個新的圓形模板，通過評估中心點與模板邊緣像素點鄰域的灰度變化情況，對提取的角點進行提純，過濾掉偽角點，得到最終檢測結果。實驗結果表明，該方法在計算效率上比Harris算法提高了32.8%，在實際應用中具有較高的精確度和魯棒性。

關鍵詞： 角點檢測; 自適應Harris算法; 角點提取; 角點提純; 偽角點過濾; 圓形模板構造

中圖分類號： TN911.73?34 ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2019）11?0040?05

Abstract： Since the traditional Harris detection algorithm has the problems of corner point clustering， pseudo corner point and man?made threshold setting， an self?adaptive Harris algorithm based on template edge is proposed in this paper. The algorithm is to detect the potential corner area in the image by using the idea of local area， and then the improved adaptive threshold Harris algorithm is used to extract the corner point in the potential corner area. On the basis of template edge， a new circular template is constructed. The grayscale change of pixel points in the center and template edge area is evaluated to purify the extracted corner points， filter out the pseudo corner points， and obtain the final detection results. The experimental results show that the computational efficiency of the algorithm is improved by 32.8% than the traditional Harris algorithm， and the algorithm has higher accuracy and stronger robustness in practical applications.

Keywords： corner detection; adaptive Harris algorithm; corner point extraction; corner point purification; pseudo corner filtering; circular template construction

0 ?引 ?言

角點檢測是圖像處理的基礎問題，盡管一個角點可能只包含0.5%個像素，但它卻能代表這幅圖像最重要的信息。角點具有計算量少、匹配簡單、不受光照影響以及旋轉、平移、縮放不變性的優點，因此，角點在三維場景重建、目標跟蹤與識別等計算機視覺領域具有廣泛的應用[1?3]。

目前，角點提取技術主要分為兩類：基于圖像邊緣的角點檢測算法和基于灰度變化的角點檢測算法[4]。前者主要是通過分析圖像邊緣曲線的幾何特性來檢測角點。但該方法過于依賴圖像邊緣輪廓，難度較大，計算復雜，且一旦圖像邊緣存在模糊或發生局部變化，可能會導致角點提取失敗[5]。

而基于灰度變化的角點檢測算法是根據圖像像素點的灰度變化情況，計算曲率和梯度來提取角點，其中最具典型的算法為Harris算法。文獻[6]針對Harris算法尺度變化敏感的問題，提出將區域檢測和利用多尺度結合非極大值抑制的改進Harris算法相結合的方法，該方法能有效增強算法的多尺度性，但運算量大，在低對比度圖像中易產生虛假角點。文獻[7]針對Harris算法閾值人為設定的問題，將圖像進行分割，根據子圖的對比度設置閾值，并結合NCC算法和RANSAC算法對角點進行提純。該方法能有效增加圖像匹配點對數。文獻[8]針對Harris算法的檢測性能依賴高斯窗窗長和閾值的不足，提出圓環模板，利用像素點評估中心像素鄰域灰度的變化來濾除虛假角點。該方法具有較好的魯棒性，但閾值設置低會出現大量偽角點，需要一一進行濾除，計算量大，耗時長。

在綜合了前人研究工作各自優勢和不足的基礎上，本文提出一種基于模板邊緣的自適應Harris角點檢測算法。該算法首先利用局部區域的思想[9]，找出圖像局部灰度變化明顯的區域，建立潛在角點區域庫，然后用改進的自適應閾值Harris檢測算法對庫中區域進行角點提取，形成角點集，最后提出了模板邊緣的思想，對角點集進行提純，過濾掉偽角點。該方法不僅運算量小，而且利用像素間的相關信息，提高了檢測精度。實驗分析驗證了本文算法的良好性能。

1 ?Harris角點檢測算法

Harris角點檢測算法主要運用微分運算和自相關矩陣檢測圖像的角點[10]。定義圖像[I]，在圖像上任意像素點[（x，y）]處，模板[w（x，y）=exp（x2+y2）σ2] 形成的窗口在[x]方向和[y]方向分別移動[（u，v）]后產生的灰度變化[E（u，v）]為：

式中：[λ1]和[λ2]為矩陣[Q]的特征向量;[k]為經驗常數，取值范圍為[0.04～0.06]。在本文實驗中，[k=0.04]。當圖像中每一個像素點對應的[CRF]值在局部區域內為極大值并大于設定的閾值時，則該點即為需要提取的角點。

Harris算法能夠有效提取圖像的特征，具有計算量小、穩健性強的優點。但在實際應用中也發現了一些不足：

1） 閾值人為選擇，可能會影響角點檢測的數量。閾值大會造成大量角點信息的丟失，反之，則會提取出偽角點。

2） 提取角點不精準，會出現聚簇角點和偽角點。本文在繼承Harris算法的基礎上，對這兩點不足進行改進。

2 ?基于模板邊緣的自適應Harris算法

2.1 ?潛在角點區域檢測

由于角點檢測算法對每一個像素點會進行多次重復運算，而實際上一幅圖像中只有10%～20%屬于可能的角點區域。為了避免多重運算，先對圖像進行潛在角點區域提?。和ㄟ^運用[3×3]大小的兩個相鄰區域的灰度值之均值和的差值大小來比較，判別該區域是否有角點存在，具體判別公式如下：

式中：[（x0，y0）]與[（x1，y1）]表示模板的中心點;[P（x0，y0）=19x0，y0為中心I（x，y）]，[P（x1，y1）=19x1，y1為中心I（x，y）]分別表示一個模板的像素灰度值之均值和;[T1]為給定的閾值，為了避免人為設定閾值對實驗結果的影響，采用可變閾值[T1=12min（P（x0，y0），P（x1，y1））]。

若兩個區域的灰度變化之差[Δp]大于閾值[T1]，就認為該區域可能存在角點，設定為潛在角點區域;反之，則為平坦區域。

2.2 ?模板邊緣思想

目前采用的模板通常是圓或矩陣，并對模板中心與模板下覆蓋的所有像素點進行比較。但模板覆蓋過多冗余的信息，導致計算量增加。本文提出的模板邊緣思想是借鑒SUSAN算法思想[11]提出的，如圖1所示。

圖1 ?圓形模板邊緣

令[M]表示模板，模板中的像素用[m∈M]表示，中心點的像素為[m0]，模板邊緣的像素點分別用[m1，m2，…，m20]表示。在圖像內移動模板，用[V]表示模板邊緣像素灰度方差，則：

2.3 ?基于模板邊緣的自適應Harris算法

本文先利用局部區域思想對圖像潛在角點區域進行粗略的篩選，然后只需對潛在角點區域庫使用改進的自適應閾值的Harris角點檢測算法進行角點檢測，而平坦區域直接跳過，在一定程度上提高了算法效率。

在利用Harris算法對潛在角點區域庫進行角點提取時，為了避免漏檢情況，采用的高斯窗口設置為[[9，3]]。閾值是根據每個潛在角點區域灰度值的變化來確定的，先對式（3）的CRF進行非極大值抑制，保留大于動態閾值[t]與式（4）中的可變閾值[T1]且為局部極大值的點，作為角點。公式如下：

式中：[t]動態變化，其變化范圍主要依據潛在角點區域像素點的局部最大值來確定。

實驗表明，本文[t]的最佳變化范圍為0.009～0.02。這里與可變閾值[T1]進行比較，主要是為了將區域中特征變化不明確的角點篩選掉，減少計算量。提取初角點后，利用模板邊緣的思想對其進行篩選，過濾掉偽角點和聚簇角點。方法如下：

對于圓形模板邊緣[M]，將模板中的每個像素點[mk]與中心點的像素[m0]進行灰度比較，若大于[V]，設為1;反之設為0。具體公式為：

模板在圖像上進行移動，當移動到平坦區域，模板上為1的點為0個;當移動到邊緣，如圖2情況1所示，模板上為1的點為11個;當移動到角點，如圖2情況2所示，模板上為1的點小于11個。構造最終的角點響應函數為：

式中[N=k=120N（mk）] 。若[C]為1，則判斷模板中心點[m0]為最終角點;反之，則舍去。

2.4 ?算法流程

本文從提取角點的精確度和計算效率的角度出發，提出基于模板邊緣的自適應Harris角點檢測算法，算法步驟如下：

Step1：輸入圖像，進行灰度處理。

Step2：提取潛在角點區域：通過運用[3×3]大小的兩個相鄰區域的灰度值之均值和的差值大小來比較，最終根據式（4）判斷該區域是否有角點存在，若存在，命名為潛在角點區域，形成潛在角點區域庫。

圖2 ?模板邊緣檢測示例圖

Step3：對潛在角點區域庫利用改進的自適應Harris算法進行角點提取，形成角點集：

1） 利用模板[w（x，y）]生成高斯窗口[9，3]，在圖像上移動產生灰度變化[E（u，v）]。

2） 根據式（2）對[E（u，v）]進行變化，并得到矩陣[Q]。計算矩陣的特征向量[λ1]和[λ2]。

3） 根據式（3）的角點響應函數[CRF]進行角點判別，[k]取常值0.04。

4） 根據式（6）對[CRF]進行非極大值抑制，保留大于動態閾值[t]、可變閾值[T1]且為局部極大值的點，作為初角點。

Step4：初角點提純。具體操作如下：

1） 利用模板[M]在圖像上移動，當中心點的像素[m0]移至Step3提取的初角點時，根據式（5）計算中心點與模板邊緣像素灰度方差[V]。

2） 根據式（7）對方差[V]進行判別，更新[N（mk）]。

3） 根據式（8）的角點響應函數[C]判斷模板中心點[m0]是否符合條件。若滿足，則此初角點為最優角點，保留此初角點;若不滿足，則將此初角點舍去。

判斷完一個初角點之后，繼續移動模板[M]至下一個初角點繼續進行Step4，直到所有的初角點全部判別完畢，結束本算法。

本文算法的流程圖如圖3所示。

3 ?實驗結果與分析

為了充分驗證本文算法的有效性及優越性，首先選取了[256×256]的兩幅邊緣像素灰度變化明顯的圖像進行驗證，并將實驗結果與Harris算法、SUSAN算法、文獻[8]的實驗結果進行對比。圖4為各算法檢測結果。

圖3 ?本文算法流程圖

圖4 ?各算法角點檢測結果對比

通過觀察圖4可以看出，Harris算法和SUSAN算法提取的角點數目較多，但存在很多偽角點和聚簇角點。文獻[8]的實驗結果明顯解決了偽角點和聚簇角點的不足，但漏檢角點相對較多，且計算時間比本文算法長。本文算法表現出較好的檢測性能，且時間上優于其他三種算法。

為了進一步驗證本文算法的優越性，又采用2幅[280×280]的實際場景圖像進行仿真實驗。分別為攝影師圖像和一個俯視圖圖像，這2幅圖像中既有灰度變化較大的部分，也有曲率變化不太明顯的角點和低對比度的角點。各算法檢測結果如圖5所示?？梢钥闯?，在實際場景中，Harris算法和SUSAN算法提取出的角點存在大量的虛假角點和聚簇角點;文獻[8]算法檢測結果表現較好;本文算法檢測的角點數量雖然較少，但是準確率高，極少存在虛假角點，且提取出的角點在整幅圖像中特征屬性明顯，具有實用價值。

為了能定量分析這四種算法提取角點的優劣性和時間效率，表1給出了4幅圖像進行角點檢測所用時間，結合實驗結果和表中數據可以看出，本文算法提取的角點精度相較于其他三種算法高，且所用時間短，計算效率比Harris算法提高了32.8%，比文獻[8]提高了34.2%。

圖5 ?實際場景圖像角點檢測結果對比

表1 ?4幅圖像的角點檢測所用時間結果比較

4 ?結 ?語

針對傳統Harris角點檢測算法出現聚簇、偽角點以及閾值人為設定的問題，本文提出了模板邊緣的思想。運用局部區域的思想檢測出潛在角點區域，利用自適應閾值的Harris算法對潛在角點區域庫進行角點提取，最后用模板邊緣的思想對提取的角點進行提純，過濾偽角點和聚簇角點。仿真結果表明本文算法魯棒性好，結果精確，且計算效率比Harris算法提高了32.8%。未來研究工作將重點對提取的角點進行特征點匹配，以此來增強本文算法的實用性。

參考文獻

[1] MANORANJITHAM R， DEEPA P. Novel interest point detector using bilateral?Harris corner method [C]// 2017 International Conference on Advanced Computing and Communication Systems. Coimbatore： IEEE， 2017： 1?4.

[2] YAO G， CUI J， DENG K， et al. Robust Harris corner matching based on the quasi homography transform and self?adaptive window for wide?baseline stereo images [J]. IEEE transactions on geoscience & remote sensing， 2017， 56（1）： 559?574.

[3] 洪改艷，芮廷先，俞偉廣，等.Harris角點檢測的優化算法[J].計算機系統應用，2017，26（4）：169?172.

HONG Gaiyan， RUI Tingxian， YU Weiguang， et al. Improved algorithm based on Harris corner detection [J]. Computer systems and applications ， 2017， 26（4）： 169?172.

[4] ZHANG W C， SHUI P L. Contour?based corner detection via angle difference of principal directions of anisotropic Gaussian directional Derivatives [J]. Pattern recognition， 2015， 48： 2785?2797.

[5] 趙亞利，章為川，李云紅.圖像邊緣輪廓自適應閾值的角點檢測算法[J].中國圖象圖形學報，2016，21（11）：1502?1514.

ZHAO Yali， ZHANG Weichuan， LI Yunhong. Novel contour?based corner detection with adaptive threshold [J]. Journal of image and graphics， 2016， 21（11）： 1502?1514.

[6] 吳鵬，徐洪玲，李雯雯.基于區域檢測的多尺度Harris角點檢測算法[J].哈爾濱工程大學學報，2016，37（7）：969?973.

WU Peng， XU Hongling， LI Wenwen. Multi?scale Harris corner detection algorithm based on region detection [J]. Journal of Harbin Engineering University， 2016， 37（7）： 969?973.

[7] 張見雙，張紅民，羅永濤.一種改進的Harris角點檢測的圖像配準方法[J].激光與紅外，2017，47（2）：230?233.

ZHANG Jianshuang， ZHANG Hongmin， LUO Yongtao. Image registration method based on improved Harris corner detection algorithm [J]. Lasers & infrared， 2017， 47（2）： 230?233.

[8] 鄧淇元，曲長文，江源.基于圓環模板的改進Harris角點檢測算法[J].系統工程與電子技術，2016，38（4）：949?954.

DENG Qiyuan， QU Changwen， JIANG Yuan， Improved corner detection algorithm based on circle mask via Harris [J]. Systems engineering and electronics， 2016， 38（4）： 949?954.

[9] 梁艷.角點檢測理論及算法研究[D].武漢：華中科技大學，2010.

LIANG Yan， Research on primary corner detection algorithm [D]. Wuhan： Huazhong University of Science and Technology， 2010.

[10] JUN Yan， YAN Piao. Research on the Harris algorithm of feature extraction for moving targets in the video [J]. Applied mechanics and materials， 2015， 741： 378?381.

[11] GAO Chao， ZHU Hongjun， GUO Yongcai. Analysis and improvement of SUSAN algorithm [J]. Signal processing， 2012， 92（10）： 2552?2559.