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

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

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

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

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

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

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

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

1 ?Harris角點(diǎn)檢測(cè)算法

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

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

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

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

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

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

2.1 ?潛在角點(diǎn)區(qū)域檢測(cè)

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

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

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

2.2 ?模板邊緣思想

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

圖1 ?圓形模板邊緣

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

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

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

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

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

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

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

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

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

2.4 ?算法流程

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

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

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

圖2 ?模板邊緣檢測(cè)示例圖

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

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

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

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

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

Step4：初角點(diǎn)提純。具體操作如下：

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

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

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

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

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

3 ?實(shí)驗(yàn)結(jié)果與分析

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

圖3 ?本文算法流程圖

圖4 ?各算法角點(diǎn)檢測(cè)結(jié)果對(duì)比

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

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

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

圖5 ?實(shí)際場(chǎng)景圖像角點(diǎn)檢測(cè)結(jié)果對(duì)比

表1 ?4幅圖像的角點(diǎn)檢測(cè)所用時(shí)間結(jié)果比較

4 ?結(jié) ?語(yǔ)

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

參考文獻(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角點(diǎn)檢測(cè)的優(yōu)化算法[J].計(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)閾值的角點(diǎn)檢測(cè)算法[J].中國(guó)圖象圖形學(xué)報(bào)，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ū)域檢測(cè)的多尺度Harris角點(diǎn)檢測(cè)算法[J].哈爾濱工程大學(xué)學(xué)報(bào)，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] 張見(jiàn)雙，張紅民，羅永濤.一種改進(jìn)的Harris角點(diǎn)檢測(cè)的圖像配準(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] 鄧淇元，曲長(zhǎng)文，江源.基于圓環(huán)模板的改進(jìn)Harris角點(diǎn)檢測(cè)算法[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] 梁艷.角點(diǎn)檢測(cè)理論及算法研究[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.