唐亞平+陳蘇婷

摘要：針對Harris角點檢測過程中存在定位粗糙、檢測精度不高以及檢測效率慢等原因，該文在Harris算法的基礎上，結合Harris算子和Forstner算子提出一種改進的亞像素角點提取算法。該算法采用一種逐層檢測策略，首先利用Harris算法進行角點粗略定位，首先對角點做一個初始選擇，利用圖像領域灰度相似度得到大部分角點的粗定位值，大大降低了算法的運算量，然后通過計算自相關矩陣的兩個特征值，利用特征值和閾值比較篩選得到全部角點的粗定位值，避免了CRF（corner reference function角點響應函數(shù)）的計算，最后利用Forstner算子對粗定位后的角點進行亞像素級精確定位。實驗證明，該算法不僅保證Harris算法的靈活性和Forstner算子的亞像素級精度，而且速度快，并且抗噪聲性能較強。

關鍵詞：Harris；Forstner；CRF；亞像素 效率；精度

中圖分類號： TU198+.3 文獻標識碼：A 文章編號：1009-3044（2014）19-4552-04

An Improved Subpixel Corner Extraction Algorithm

TANG Ya-ping， CHEN Su-ting

（Jiangsu Key Laboratory of Meteorological Observation and Information Processing， Nanjing University of Information Science &Technology， Nanjing 210044， China）

Abstract： In view of the rough positioning、inaccurate detecting and the slow efficiency in the Harris corner detection，According to this，an improved Harris algorithm is presented in this paper， on the basis of the combining with Harris algorithm and Forstner operator . The algorithm adopts a layered detection strategy， firstly using Harris algorithm for corner rough localization， considering the slow detecting， before calculating the CRF we made an initial choice to avoid large amount of multiplication， after geting the coarse position of angular point， we then calculate Forstner operator for accurate positioning. Experiments show that the algorithm not only guarantees the flexibility of Harris algorithm and the subpixel accuracy of Forstner operator ，but also improve the speed and have strong anti-noise performance. The algorithm overcomes the problem on the detection speed and precision in the Harris algorithm.

Key words： Harris； Forstner； CRF； subpixel； accuracy； detection efficiency

圖像特征點的提取是計算機視覺領域中非常重要的一步，其中，圖像角點是最常見的一類特征之一，它具有旋轉不變性、不隨光照變化等優(yōu)點，因此角點特征被廣泛應用于物體跟蹤、三維建模、攝影測量自動化以及遙感圖像匹配等領域。

本文通過分析Harris角點檢測過程中的一些弊端，如在對角點進行選擇定位的過程中采用了大量乘法運算，運算量大，大大降低了算法檢測的效率，同時Harris算法只能檢測到像素級水平的坐標，對于精度要求高，需要準確定位像素坐標的場合不能夠滿足精度要求，該文在Harris算法基礎上提出了一種改進的亞像素角點檢測算法，該算法通過Harris算法和Forstner算子相結合，首先用Harris算法進行粗定位，在定位過程中對角點做一個初始選擇，避免了大量的乘法運算，得到角點的粗定位值后，最后利用Forstner算子對角點進行亞像素級的精確定位。

1 Harris角點檢測的原理

1988年，Chris Harris和Mike Stephens提出了Harris角點檢測算法，該算法突破了Moravec算子在角點檢測領域的局限性，Harris算法通過微分算子來計算像素點在任意方向的灰度變化，并計算出目標像素點的CRF（角點響應函數(shù)值），當CRF小于某個很小的值時，則認為檢測點在區(qū)域內部，即灰度基本上無變化的區(qū)域，當CRF大于給定的閾值時，認為此點就是是角點，CRF小于零時，認為此點屬于邊緣上某點。

2 改進的Harris亞像素角點檢測算法

2.1 Harris算法角點初定位

該算法首先利用Harris算法進行角點初定位，并在原算法基礎上加以改進，主要是在計算CRF之前對所有像素點做一個初步篩選，因為這一部分主要都是加法運算，不涉及乘法操作，因此效率較原算法大大提高。endprint

這里我們提出圖像區(qū)域像素相似度的概念，圖像區(qū)域像素相似度是指檢測窗口中心點的灰度值與其周圍n 個鄰域內所有其他像素點灰度值的相似度，用它們的灰度差來描述這種相似度，如果灰度差小于某個值，則認為該點與中心點相似，反之則與中心點不相似。

我們使用的是3*3的檢測模板窗口，對于中心像素點Image （i，j）計算其周圍8 個鄰域內像素點的相似度。并且統(tǒng)計中心像素點和該范圍內像素點灰度值差的絕對值（記為Δ），若該值小于我們設定的閾值，就認為目標像素點與該像素點相似。

[nlike（i，j）=sum（R（i+x，j+y）） ] （1）

[（-1≤x≤1，-1≤y≤1，x≠0，y≠0）]其中：[1≤Δ（i+x，j+y）≤t]

當[Δ（i+x，j+y）>t]時[R（i+x，j+y）=0]。

從定義中可以看出：[0≤nlike≤8]?，F(xiàn)在討論 [nlike（i，j）]值的含義 。

1） nlike （i ， j） = 8，表示 8 個鄰域范圍內都是和它相似的像素點排除此類點作為角點可能性

2） nlike （i ， j） = 0，表示 8 個鄰域范圍內都是和它不相似的像素點，也可以排除。

3） nlike （i ， j） = 7，分為以下兩種情況，圖 2（a） 中，角點可能位于中心像素點正上方的那個像素點，圖2（b） 中，角點可能位于中心像素點右上方的那個像素點，這種情況也應該排除。

（a） （b）

圖2

4） nlike （i，j） =1，也有兩種情況。由上可知中心像素點也應該排除作為角點可能性。

5） 2 ≤ nlike（i，j） ≤ 6，暫時無法判定，作為我們的角點候選點集。

對上述不能通過圖像領域像素相似度進行定位的角點，我們通過原Harris算法計算這些角點的自相關矩陣的特征值，如果兩個特征值都很小，則說明這個區(qū)域是一個平坦區(qū)域；如果兩個特征值一大一小，則是一條直線；如果兩個值都很大，則這個點就是角點?；蛘咄ㄟ^計算CRF來進行判斷。

[R=C（x，y）=det（M）-ktr2（M）] （2）

其中C只與自相關矩陣的特征值M有關，若C大數(shù)值整數(shù)，則為角點，若C為大數(shù)值負數(shù)，則為邊緣上的點，若C為小數(shù)值整數(shù)，則為平坦區(qū)域中的點。在算法當中，我們對CRF進行閾值處理，判斷CRF>threshold，并提取局部最大值點就是我們所需要的角點。

2.2 角點的亞像素級精確定位

考慮到Harris算法角點檢測過程中存在定位不精確的問題，而Forstner算子本身就擁有較高的定位精度但是卻受灰度對比度變化的影響較大，該文通過將Harris算法與Forstner算子結合起來，利用Forstner算子的定位功能對經(jīng)過Harris算法粗定位后的角點進行亞像素級坐標的精確定位。

2.2.1 最佳窗口的確定

以每一個候選角點為中心，取一個3*3的窗口N進行計算窗口興趣值q和w，若興趣值大于給定閾值，并且為局部最大值，則將該窗口作為我們的最佳窗口。其中閾值由上一步Harris算法粗定位過程中根據(jù)圖像灰度確定的閾值T所決定。

1）首先計算每個粗定位角點（c，r）的Roberts梯度：

[gc=?g?c=gi+1，j+1-gi，jgr=?g?r=gi，j+1-gi+1，j] （3）

圖3 Roberts梯度

2） 計算3*3窗口中的灰度協(xié)方差矩陣Q

[Q=N-1=gc2gcgrgrgcgr2-1] （4）

其中：

[∑gc2=i=c-kc+k-1i=r-kr+k-1（gi+1，j+1-gi，j）2∑gr2=i=c-kc+k-1i=r-kr+k-1（gi，j+1-gi+1，j）2gcgr=i=c-kc+k-1i=r-kr+k-1（gi+1，j+1-gi，j）（gi，j+1-gi+1，j）K=INT（1/2）] （5）

3） 計算興趣值q和w

在計算興趣值之前我們首先對各個模板窗口做一個初始選擇，在以某個角點粗定位值為中心的窗口內，分別在x、y方向上計算Sobel梯度算子大小，當它們大于給定閾值時，才對所在窗口計算興趣值q和w。

[Gx=-10+1-20+2-10+1*W and Gx=+1+2+1000-1-2-1*W] （6）

Gx及Gy分別代表經(jīng)橫向及縱向邊緣檢測的圖像，W表示被選窗口，窗口內每個像素的橫向及縱向梯度近似值為[G=Gx2+Gy2]，當G>T時，對其計算興趣值。

接下來對粗角點為中心的每個模板大小窗口計算興趣值q和w，考慮到矩陣的跡作為分母，當矩陣的跡等于0時，無法判斷結果，因此在計算矩陣跡時，加上一個常數(shù)C，避免了矩陣跡為0時無結果的情況。

[q=4Det（N）tr2（N）+Cw=1tr（Q）=Det（N）tr（N）+C] （7）

其中[Det（N）]代表矩陣N的行列式，[tr（N）]為矩陣的跡。

2.2.2 粗定位角點的精確定位

對Harris算法初步定位出來的角點進行精確定位，首先我們假設最佳窗口內任意粗定位角點（c，r）的邊緣直線L的方程為：

[ρ=rcosθ+csinθ] （8）

上式中，[ρ]為原點到直線L的垂直距離；[θ]為梯度角，[tanθ=gc/gr.gc，gr]為該點的Robert梯度。假設角點坐標為[（c0，r0）]，同時設v為點[（c，r）]到直線L的距離，在[（c，r）]處我們給出誤差方程：

[ρ+ν=r0cosθ+c0sinθw（r，c）=Δg2=gr2+gc2] （9）

對上式進行法化，可得下式：

[gr2grgcgrgcgc2.r0c0=gr2rgrgccgrgcrgc2c] （10）

求解上述方程，我們就可以得到角點的亞像素級坐標[（c0，r0）]。

3 實驗結果及分析

通過Matlab實現(xiàn)上面改進后的算法，并與Harris原算法提取后的角點進行比較，通過對多幅圖像的角點提取實驗證明，該算法對角點目標的提取、定位抗噪性能好，運算量小且實現(xiàn)速度快。

3.1 改進算法對角點檢測的時間運行效率實驗及分析

表1為改進前原 Harris 算法和改進后的Harris 算法對6 幅給定圖像進行角點提取時，在核心算法部分（通過計算CRF確認角點）所消耗的平均時間的比較。

表1 原算法與改進算法在核心算法部分平均消耗時間的比較（單位：秒）

[圖像名＼&lena.jpg＼&stuff.jpg＼&fruits.jpg＼&baboon.jpg＼& fish.jpg＼&cat.jpg＼&改進前 ＼&6.566712＼&6.556286＼&6.755664＼&6.681580＼&6.601732＼&6.569117＼&改進后＼&1.170748＼&1.141037＼&1.598029＼&2.172551＼&2.195614＼&1.130464＼&]

3.2 改進算法與原算法在圖像角點定位精度方面的比較

通過對南京信息工程大學的遙感圖像利用原算法和改進算法分別進行角點檢測，進行對比。

（a）原算法 （b）改進算法

圖4

表2 原算法和改進算法在遙感圖像上提取的角點坐標比較（單位：pixel）

[＼& Harris算法角點像素級坐標＼& 改進算法亞像素級坐標＼&1＼&（88，110）＼&（88.1135，110.3272）＼&2＼&（71，107）＼&（71.8135，107.1112）＼&3＼&（197，65）＼&（197.7462，65.9697）＼&4＼&（328，321）＼&（328.7394，321.8376）＼&5＼&（318，235）＼&（318.9163，235.6999）＼&6＼&（212，303）＼&（212.0830，303.1214）＼&7＼&（63，96）＼&（63.3472，96.5439）＼&8＼&（316，343）＼&（316.7932，343.5493）＼&9＼&（329，333）＼&（329.3616，333.7831）＼&10＼&（190，313）＼&（190.1755，313.9654）＼&]

4 結論

本文通過改進Harris角點檢測算法，并通過實驗驗證了改進算法在角點檢測方面的優(yōu)越性，分別就提取時間和提取的準確度與原算法進行了比較。改進算法解決了Harris算法定位不精確，運算量大等情況，還解決了Foestner算子受閾值選擇以及圖像對比度和灰度的影響，通過實驗驗證，改進算法的運算時間約為原算法的17.83%，并且角點的亞像素定位誤差可達到0.1265個像素，可以有效的應用于后期的計算機視覺和三維重建當中。

參考文獻：

[1] 周龍萍.基于改進的Harris算法檢測角點[J].計算機技術與發(fā)展，2013，23（2）：11-14.

[2] 房超，王小鵬，牛云鵬，王超.基于改進Harris算法的角點檢測[J].計算機與數(shù)字工程，2011，39（5）：142-144.

[3] 郭海霞，解凱.基于USAN的改進的角點檢測算法[J].計算機工程， 2007，22（33）：232-234. （下轉第4571頁）

（上接第4555頁）

[4] 張海燕，李元媛，儲晨昀.基于圖像分塊的多尺度 Harris 角點檢測方法[J].計算機應用，2011，31（ 2） ：356-357.

[5] 王崴，唐一平，任娟莉.一種改進的Harris 角點提取算法[J].光學精密工程，2008，16（10）：1995-2001.

[6] Ville O， Janne H. Image registration using blur-invariant phase correlation [J].IEEE Signal Processing Letters，2007， 14（7）： 449-452.

[7] Chen Aihua，Zhu Ming，Wang Yanhua，Xue Chen.Image feature points match algorithm based on orientation angles[J].Journal of Optoelectronics-Laser，2009，20（4）.

[8] Bastanlar Y，Yardimci，Y.Corner validation based on extracted comer properties[J].Computer vision and image understanding，2008，112（3）.

[9] Song wei，Hou Jianjun.A novel zero-bit watermarking algorithm based on Logistic chaotic system and singUlar value decomposition[J]Acta Physica Sinca，2009，58（7）.

[10] Zhao Wanjin，Gong Shengrong，Liu Chunping，Shen Xiangjun.A Daptive Harris Corner Detection Algorithm[J]. Computer Engineering，2008，34 （10）：212-215.

[ρ=rcosθ+csinθ] （8）

上式中，[ρ]為原點到直線L的垂直距離；[θ]為梯度角，[tanθ=gc/gr.gc，gr]為該點的Robert梯度。假設角點坐標為[（c0，r0）]，同時設v為點[（c，r）]到直線L的距離，在[（c，r）]處我們給出誤差方程：

[ρ+ν=r0cosθ+c0sinθw（r，c）=Δg2=gr2+gc2] （9）

對上式進行法化，可得下式：

[gr2grgcgrgcgc2.r0c0=gr2rgrgccgrgcrgc2c] （10）

求解上述方程，我們就可以得到角點的亞像素級坐標[（c0，r0）]。

3 實驗結果及分析

通過Matlab實現(xiàn)上面改進后的算法，并與Harris原算法提取后的角點進行比較，通過對多幅圖像的角點提取實驗證明，該算法對角點目標的提取、定位抗噪性能好，運算量小且實現(xiàn)速度快。

3.1 改進算法對角點檢測的時間運行效率實驗及分析

表1為改進前原 Harris 算法和改進后的Harris 算法對6 幅給定圖像進行角點提取時，在核心算法部分（通過計算CRF確認角點）所消耗的平均時間的比較。

表1 原算法與改進算法在核心算法部分平均消耗時間的比較（單位：秒）

[圖像名＼&lena.jpg＼&stuff.jpg＼&fruits.jpg＼&baboon.jpg＼& fish.jpg＼&cat.jpg＼&改進前 ＼&6.566712＼&6.556286＼&6.755664＼&6.681580＼&6.601732＼&6.569117＼&改進后＼&1.170748＼&1.141037＼&1.598029＼&2.172551＼&2.195614＼&1.130464＼&]

3.2 改進算法與原算法在圖像角點定位精度方面的比較

通過對南京信息工程大學的遙感圖像利用原算法和改進算法分別進行角點檢測，進行對比。

（a）原算法 （b）改進算法

圖4

表2 原算法和改進算法在遙感圖像上提取的角點坐標比較（單位：pixel）

[＼& Harris算法角點像素級坐標＼& 改進算法亞像素級坐標＼&1＼&（88，110）＼&（88.1135，110.3272）＼&2＼&（71，107）＼&（71.8135，107.1112）＼&3＼&（197，65）＼&（197.7462，65.9697）＼&4＼&（328，321）＼&（328.7394，321.8376）＼&5＼&（318，235）＼&（318.9163，235.6999）＼&6＼&（212，303）＼&（212.0830，303.1214）＼&7＼&（63，96）＼&（63.3472，96.5439）＼&8＼&（316，343）＼&（316.7932，343.5493）＼&9＼&（329，333）＼&（329.3616，333.7831）＼&10＼&（190，313）＼&（190.1755，313.9654）＼&]

4 結論

本文通過改進Harris角點檢測算法，并通過實驗驗證了改進算法在角點檢測方面的優(yōu)越性，分別就提取時間和提取的準確度與原算法進行了比較。改進算法解決了Harris算法定位不精確，運算量大等情況，還解決了Foestner算子受閾值選擇以及圖像對比度和灰度的影響，通過實驗驗證，改進算法的運算時間約為原算法的17.83%，并且角點的亞像素定位誤差可達到0.1265個像素，可以有效的應用于后期的計算機視覺和三維重建當中。

參考文獻：

[1] 周龍萍.基于改進的Harris算法檢測角點[J].計算機技術與發(fā)展，2013，23（2）：11-14.

[2] 房超，王小鵬，牛云鵬，王超.基于改進Harris算法的角點檢測[J].計算機與數(shù)字工程，2011，39（5）：142-144.

[3] 郭海霞，解凱.基于USAN的改進的角點檢測算法[J].計算機工程， 2007，22（33）：232-234. （下轉第4571頁）

（上接第4555頁）

[4] 張海燕，李元媛，儲晨昀.基于圖像分塊的多尺度 Harris 角點檢測方法[J].計算機應用，2011，31（ 2） ：356-357.

[5] 王崴，唐一平，任娟莉.一種改進的Harris 角點提取算法[J].光學精密工程，2008，16（10）：1995-2001.

[6] Ville O， Janne H. Image registration using blur-invariant phase correlation [J].IEEE Signal Processing Letters，2007， 14（7）： 449-452.

[7] Chen Aihua，Zhu Ming，Wang Yanhua，Xue Chen.Image feature points match algorithm based on orientation angles[J].Journal of Optoelectronics-Laser，2009，20（4）.

[8] Bastanlar Y，Yardimci，Y.Corner validation based on extracted comer properties[J].Computer vision and image understanding，2008，112（3）.

[9] Song wei，Hou Jianjun.A novel zero-bit watermarking algorithm based on Logistic chaotic system and singUlar value decomposition[J]Acta Physica Sinca，2009，58（7）.

[10] Zhao Wanjin，Gong Shengrong，Liu Chunping，Shen Xiangjun.A Daptive Harris Corner Detection Algorithm[J]. Computer Engineering，2008，34 （10）：212-215.

[ρ=rcosθ+csinθ] （8）

上式中，[ρ]為原點到直線L的垂直距離；[θ]為梯度角，[tanθ=gc/gr.gc，gr]為該點的Robert梯度。假設角點坐標為[（c0，r0）]，同時設v為點[（c，r）]到直線L的距離，在[（c，r）]處我們給出誤差方程：

[ρ+ν=r0cosθ+c0sinθw（r，c）=Δg2=gr2+gc2] （9）

對上式進行法化，可得下式：

[gr2grgcgrgcgc2.r0c0=gr2rgrgccgrgcrgc2c] （10）

求解上述方程，我們就可以得到角點的亞像素級坐標[（c0，r0）]。

3 實驗結果及分析

通過Matlab實現(xiàn)上面改進后的算法，并與Harris原算法提取后的角點進行比較，通過對多幅圖像的角點提取實驗證明，該算法對角點目標的提取、定位抗噪性能好，運算量小且實現(xiàn)速度快。

3.1 改進算法對角點檢測的時間運行效率實驗及分析

表1為改進前原 Harris 算法和改進后的Harris 算法對6 幅給定圖像進行角點提取時，在核心算法部分（通過計算CRF確認角點）所消耗的平均時間的比較。

表1 原算法與改進算法在核心算法部分平均消耗時間的比較（單位：秒）

[圖像名＼&lena.jpg＼&stuff.jpg＼&fruits.jpg＼&baboon.jpg＼& fish.jpg＼&cat.jpg＼&改進前 ＼&6.566712＼&6.556286＼&6.755664＼&6.681580＼&6.601732＼&6.569117＼&改進后＼&1.170748＼&1.141037＼&1.598029＼&2.172551＼&2.195614＼&1.130464＼&]

3.2 改進算法與原算法在圖像角點定位精度方面的比較

通過對南京信息工程大學的遙感圖像利用原算法和改進算法分別進行角點檢測，進行對比。

（a）原算法 （b）改進算法

圖4

表2 原算法和改進算法在遙感圖像上提取的角點坐標比較（單位：pixel）

[＼& Harris算法角點像素級坐標＼& 改進算法亞像素級坐標＼&1＼&（88，110）＼&（88.1135，110.3272）＼&2＼&（71，107）＼&（71.8135，107.1112）＼&3＼&（197，65）＼&（197.7462，65.9697）＼&4＼&（328，321）＼&（328.7394，321.8376）＼&5＼&（318，235）＼&（318.9163，235.6999）＼&6＼&（212，303）＼&（212.0830，303.1214）＼&7＼&（63，96）＼&（63.3472，96.5439）＼&8＼&（316，343）＼&（316.7932，343.5493）＼&9＼&（329，333）＼&（329.3616，333.7831）＼&10＼&（190，313）＼&（190.1755，313.9654）＼&]

4 結論

本文通過改進Harris角點檢測算法，并通過實驗驗證了改進算法在角點檢測方面的優(yōu)越性，分別就提取時間和提取的準確度與原算法進行了比較。改進算法解決了Harris算法定位不精確，運算量大等情況，還解決了Foestner算子受閾值選擇以及圖像對比度和灰度的影響，通過實驗驗證，改進算法的運算時間約為原算法的17.83%，并且角點的亞像素定位誤差可達到0.1265個像素，可以有效的應用于后期的計算機視覺和三維重建當中。

參考文獻：

[1] 周龍萍.基于改進的Harris算法檢測角點[J].計算機技術與發(fā)展，2013，23（2）：11-14.

[2] 房超，王小鵬，牛云鵬，王超.基于改進Harris算法的角點檢測[J].計算機與數(shù)字工程，2011，39（5）：142-144.

[3] 郭海霞，解凱.基于USAN的改進的角點檢測算法[J].計算機工程， 2007，22（33）：232-234. （下轉第4571頁）

（上接第4555頁）

[4] 張海燕，李元媛，儲晨昀.基于圖像分塊的多尺度 Harris 角點檢測方法[J].計算機應用，2011，31（ 2） ：356-357.

[5] 王崴，唐一平，任娟莉.一種改進的Harris 角點提取算法[J].光學精密工程，2008，16（10）：1995-2001.

[6] Ville O， Janne H. Image registration using blur-invariant phase correlation [J].IEEE Signal Processing Letters，2007， 14（7）： 449-452.

[7] Chen Aihua，Zhu Ming，Wang Yanhua，Xue Chen.Image feature points match algorithm based on orientation angles[J].Journal of Optoelectronics-Laser，2009，20（4）.

[8] Bastanlar Y，Yardimci，Y.Corner validation based on extracted comer properties[J].Computer vision and image understanding，2008，112（3）.

[9] Song wei，Hou Jianjun.A novel zero-bit watermarking algorithm based on Logistic chaotic system and singUlar value decomposition[J]Acta Physica Sinca，2009，58（7）.

[10] Zhao Wanjin，Gong Shengrong，Liu Chunping，Shen Xiangjun.A Daptive Harris Corner Detection Algorithm[J]. Computer Engineering，2008，34 （10）：212-215.