基于模板邊緣的自適應(yīng)Harris角點檢測算法

李冰 呂進(jìn)來 郝曉麗

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

關(guān)鍵詞： 角點檢測; 自適應(yīng)Harris算法; 角點提取; 角點提純; 偽角點過濾; 圓形模板構(gòu)造

中圖分類號： TN911.73?34 ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼： 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 ?引 ?言

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

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

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

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

1 ?Harris角點檢測算法

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

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

Harris算法能夠有效提取圖像的特征，具有計算量小、穩(wěn)健性強(qiáng)的優(yōu)點。但在實際應(yīng)用中也發(fā)現(xiàn)了一些不足：

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

2） 提取角點不精準(zhǔn)，會出現(xiàn)聚簇角點和偽角點。本文在繼承Harris算法的基礎(chǔ)上，對這兩點不足進(jìn)行改進(jìn)。

2 ?基于模板邊緣的自適應(yīng)Harris算法

2.1 ?潛在角點區(qū)域檢測

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

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

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

2.2 ?模板邊緣思想

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

圖1 ?圓形模板邊緣

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

2.3 ?基于模板邊緣的自適應(yīng)Harris算法

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

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

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

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

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

模板在圖像上進(jìn)行移動，當(dāng)移動到平坦區(qū)域，模板上為1的點為0個;當(dāng)移動到邊緣，如圖2情況1所示，模板上為1的點為11個;當(dāng)移動到角點，如圖2情況2所示，模板上為1的點小于11個。構(gòu)造最終的角點響應(yīng)函數(shù)為：

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

2.4 ?算法流程

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

Step1：輸入圖像，進(jìn)行灰度處理。

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

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

Step3：對潛在角點區(qū)域庫利用改進(jìn)的自適應(yīng)Harris算法進(jìn)行角點提取，形成角點集：

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

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

3） 根據(jù)式（3）的角點響應(yīng)函數(shù)[CRF]進(jìn)行角點判別，[k]取常值0.04。

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

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

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

2） 根據(jù)式（7）對方差[V]進(jìn)行判別，更新[N（mk）]。

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

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

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

3 ?實驗結(jié)果與分析

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

圖3 ?本文算法流程圖

圖4 ?各算法角點檢測結(jié)果對比

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

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

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

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

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

4 ?結(jié) ?語

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

參考文獻(xiàn)

[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角點檢測的優(yōu)化算法[J].計算機(jī)系統(tǒng)應(yīng)用，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] 趙亞利，章為川，李云紅.圖像邊緣輪廓自適應(yīng)閾值的角點檢測算法[J].中國圖象圖形學(xué)報，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] 吳鵬，徐洪玲，李雯雯.基于區(qū)域檢測的多尺度Harris角點檢測算法[J].哈爾濱工程大學(xué)學(xué)報，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] 張見雙，張紅民，羅永濤.一種改進(jìn)的Harris角點檢測的圖像配準(zhǔn)方法[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] 鄧淇元，曲長文，江源.基于圓環(huán)模板的改進(jìn)Harris角點檢測算法[J].系統(tǒng)工程與電子技術(shù)，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].武漢：華中科技大學(xué)，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.