洪改艷, 芮廷先, 俞偉廣, 何士產, 王天召(上海財經大學 浙江學院經濟與信息管理系, 金華 000)(上海財經大學 信息管理與工程學院, 上海 00000)(解放軍705部隊, 金華 000)

Harris角點檢測的優(yōu)化算法①

洪改艷1, 芮廷先2, 俞偉廣1, 何士產1, 王天召31(上海財經大學 浙江學院經濟與信息管理系, 金華 321000)2(上海財經大學 信息管理與工程學院, 上海 200000)3(解放軍73051部隊, 金華 321000)

針對Harris角點檢測算法中提取出較多的偽角點和計算量大的問題, 提出了一種基于Harris角點檢測的改進算法. 為抑制Harris角點檢測中的偽角點數目并且提高算法的效率, 首先加入預篩選得到候選角點, 在計算水平和垂直方向梯度時, 對于梯度較小的像素點進行預處理, 在進行非極大值抑制時采用自適應閾值, 提高算法自適應性, 最后利用USAN對角點進行進一步選擇. 實驗結果表明, 改進的Harris角點檢測算法不僅提高了檢測精度和效率, 而且對噪聲具有一定的魯棒性.

Harris角點; 角點預選; 自適應閾值; USAN

角點被普遍認為是二維圖像亮度變化劇烈或者圖像邊緣曲線上曲率極大值的點[1]. 角點檢測在圖像匹配、光流計算、運動估計、形狀分析、相機標定和3D重建、視覺的定位和測量等方面都有重要的應用.

目前, 角點檢測技術可以分為兩類: 第一類是基于圖像邊緣信息[2], 如基于邊界曲率的角點檢測, 基于邊界鏈碼的角點檢測, 基于小波變換模極大的角點檢測; 第二類是基于圖像灰度信息[3], 如Moravec算法[4], Harris算法[3], SUSAN算法[1], MIC算法[5]等. 在第一類角點檢測中, 角點對邊緣線依賴比較大, 邊緣線提取時如果發(fā)生中斷, 則會對角點的提取結果造成很大的影響. 第二類角點檢測主要缺點是定位精度比較差, 同時還有可能漏掉一些實際的角點, 產生一些偽角點, 對噪聲比較敏感. 第二類角點檢測中, 應用比較多的是Harris算法[6]和SUSAN算法, 但是存在計算量大和精度不高的問題.

本文在對Harris角點檢測原理進行詳細分析的基礎上, 針對Harris角點檢測算法在檢測精度和效率這兩個方面的不足, 提出了一種改進Harris算法. 改進的Harris算法在進行Harris算法之前, 首先對圖像點進行預選, 選出合適的點作為候選點, 在Harris算法中對水平、垂直方向梯度進行了改進, 采用自適應閾值提取Harris角點, 最后利用USAN[1]進一步剔除偽角點. 通過實驗對改進算法的精度和效率進行了驗證.

1 Harris算法檢測原理及步驟

1.1 Harris算法基本原理

Harris算法以Moravec算法為基礎, Moravec算法的基本原理是: 取以目標像素點為中心的一個小窗口,并將窗口沿上下左右4個方向移動, 計算這4個方向上窗口內的灰度變化, 并以4個灰度變化值中的最小值作為該目標像素點的角點相應函數, 若該值大于設定閾值, 則為角點.

Harris算法則計算窗口沿任何方向移動后的灰度變化, 并用解析形式表達. 設以像素點≤為中心的小窗口在X方向上移動u, Y方向上移動v, Harris算法給出了灰度變化度量的解析表達式:

其中, det(M)表示矩陣M的行列式, trace(M)表示矩陣的跡, k一般取為0.04. 當目標像素點的CRF值大于給定的閾值時, 則該目標像素點為角點.

1.2 Harris算法步驟

根據Harris算法的基本原理, 可以將Harris算法步驟分為以下五個步驟:

Step1計算圖像像素在X和Y方向上的梯度, 以及兩者的乘積, 得到矩陣M;

Step2 對圖像進行高斯濾波, 得到新的M;

Step3 計算原圖像上對應每個像素點的CRF值;

Step4 選取局部極值點. 在Harris算法中, 特征點被認為是局部范圍內的極大CRF值所對應的像點;

Step5 設定閾值, 選取角點.

2 優(yōu)化的Harris算法

為了提高Harris算法檢測角點的效率和精度, 改進Harris算法主要在以下四個方面:

(1) 在偽角點附近, 各點的灰度變化不太大, 甚至沒有變化. 針對這種情況, 提出了鄰近像素灰度相似度(Graylevel Similarity of Adjacent Pixels, GSAP)概念, GSAP是指以圖像像素點為中心與其鄰域8個點的像素灰度值進行比較;

(2) 由于角點的局部區(qū)域灰度變化比較大, 可以忽略梯度較小的點, 不作檢測運算, 只對梯度幅值比較大的像素點進行計算;

(3) Harris角點檢測算法的缺點在于提取角點的時候所用的閾值是固定的, 所以角點提取的效果完全依賴于閾值的設定. 采用自適應閾值, 提高提取角點的自適應能力;

(4) 通過改進算法提取出的角點, 可能會在真正的角點附近小的鄰域內出現偽角點. 為了剔除這些偽角點, 采用USAN去除這些偽角點, 進一步提高角點提取的精度.

2.1 GSAP處理得到候選點

設中心點像素的灰度值與周圍一像素點灰度值差的絕對值為Δ, 設閾值為t, 如果tΔ≤, 則認為中心點與該點周圍一點相似, 同理判斷中心點與周圍其它點是否相似. 統計中心點與周圍8個點中相似點的個數, 記為（）,C i j:

根據以上討論可知, 0≤C（ i, j）≤8, 下面對C（ i, j）進行討論分析, 如果能夠找出一個實例判定該點可能為角點, 那么該點就作為候選點進行角點檢測.

(1) C（ i, j）=0, 表示中心點周圍沒有與之相似的像素點, 所以該像素點為孤立像素點或者是噪聲點,不能作為候選點;

(2) C（ i, j）=7, 可表示為圖1的兩種情況, 其它情況都可以通過這兩幅圖像變換得到. (a)可能的角點應該是目標像素點的正上方的那個像素點, (b)可能的角點應該是目標像素點左上方的那個像素點, 所以這種情況下, 中心像素點不應該作為候選點;

(3) C（ i, j）=8, 表示中心點鄰域的8個點都是與之相似的點, 不能作為候選點;

(4) 1≤C（ i, j）≤6, 這是情況比較復雜, 如圖1(c)(d)(e)(f)(g)(h)所示, 此時中心像素點應該作為候選點進行角點檢測.

圖1 1≤C（ i, j）≤7的幾種情況

綜上所述, 當1≤C（ i, j）≤6時, 將中心像素點作為角點的候選點.

2.2 角點檢測預處理

由于角點的局部區(qū)域圖像灰度變化比較大, 可以忽略水平和垂直方向上梯度比較小的點, 不進行角點檢測的運算, 只對梯度幅值比較大的像素點進行Harris計算, 這些像素點反映了圖像角點的主要信息.在角點檢測運算中, 對于點（x, y）, 計算其在水平方向的梯度Ix和垂直方向的梯度Iy, 利用如下公式進行判斷, 只有滿足條件的點才可以做后面的檢測算法,否則就忽略該點.

其中, M和N為圖像的高和寬, 這樣就避免了在整個圖像的每個像素點上計算Harris算子, 減少了計算量,同時也可以保證得到大部分的角點.

2.3 自適應閾值

在對一幅圖像進行角點提取的時候, 使用的閾值是固定的, 可能會取得好的效果. 但是對其它圖像未必使用, 考慮到算法的通用性, 提高檢測精度, 有必要對閾值的自適應能力提出要求, 需要算法本身有能力計算出合適的閾值. 閾值是在提取角點時才會使用,因此考慮由角點響應函數值CRF來確定.

求取每個預處理后的角點的響應函數值CRF, 找出最大的CRF值, 隨后定義閾值T為最大CRF值的p倍決定的, 即:

其中, C為總的預處理后的候選點總數目. 則:

從統計的觀點出發(fā),, 選取一系列圖像包括各種場景進行實驗,, 不斷調整設定的p值, 比較結果, 發(fā)現p取經驗值[0.005, 0.015] 時, 基本上所有角點都可以被檢驗出來, 而且產生的偽角點較少.

2.4 利用USAN去除偽角點

通過改進算法提取出的角點, 可能會在真正的角點附近小的鄰域內出現偽角點. 為了剔除這些偽角點,采用USAN去除這些偽角點, 進一步提高角點提取的精度.

通過T=p· CRFmax提取出來的角點為corner( i, j), 利用圓形模板對corner( i, j)進行過濾.如果以角點（i, j）為模板核的USAN面積大于模板面積的一半, 則認為（i, j）是偽角點, 從而將點（i, j）從corner( i, j)中剔除. 過濾完所有的corner( i, j)后, 余下的點就是最終得到的角點. 文中采用的模板為7x7的圓形模板, 如圖2所示.

圖2 7x7圓形模板及利用USAN的角點判別

3 實驗結果及分析

為了驗證本文改進算法的有效性, 利用經典的“積木”圖片進行仿真驗證. 實驗數據: 256x256像素大小的圖片, 在PC(Intel(R) Core(TM) i3CPU2.93GHz, 1.80G內存)機上利用Matlab進行實驗. 高斯窗口為7x7, t取20, 非極大值抑制窗口為3x3, 圓形模板為7x7, 比例系數p取0.008. 實驗結果如圖3所示.

圖3 實驗結果

表1 實驗數據結果比較

通過實驗, 原始的Harris檢測算法在檢測時產生較多的偽角點, 并且程序運行的時間比較長. 而改進后的Harris檢測算法因為對圖像點進行了預選擇和預處理, 大大降低了程序運行的時間, 從0.765s減少為0.297s, 將近原始算法的30%; 保證檢測出正確的角點的同時, 檢測時產生的偽角點數目也大大降低, 從16個降低到了5個, 不足原始算法的30%.

為了驗證改進的Harris檢測算法對噪聲的魯棒性,對圖像增加了椒鹽噪聲, 椒鹽噪聲通常由圖像傳感器、傳輸信道、解碼處理、圖像切割等產生的黑白相間的亮暗點噪聲, 實驗中椒鹽噪聲的參數d=0.01, 實驗結果如圖4所示.

圖4 加入椒鹽噪聲(d=0.01)后的實驗結果

通過實驗結果可以看出, Harris算法對噪聲比較敏感, 但是改進后的Harris算法相對于原始Harris算法具有一定的魯棒性.

4 結語

針對Harris角點檢測算法的一些缺點, 包括在角點提取中會出現偽角點, 并且在非極大值抑制時設置固定閾值的問題, 提出了基于Harris角點檢測算法的改進算法. 在不影響Harris角點檢測算法計算簡便和穩(wěn)定的前提下, 首先利用GSAP對圖像進行處理得到候選點, 在計算水平和垂直梯度時對候選點進行預處理, 在非極大值抑制時采用自適應閾值, 提高了算法的自適應性, 最后為了進一步剔除偽角點采用USAN對提取的角點進行處理. 實驗結果表明, 優(yōu)化后的Harris角點檢測算法不僅僅減少了提取的偽角點數量和縮短了運算時間, 而且對噪聲具有一定的魯棒性.

1 Smith SM, Brady JM. SUSAN—A new approach to low-level image processing. International Journal of Computer Vision, 1997, 23(1): 45–78.

2 Quddus A, Fahmy MM. An improved waveletbased corner detection technique. Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing. Phoenix, USA. IEEE. 1999. 3213–3216.

3 Harris C, Stephens MJ. A combined corner and edge detector. Proc. of the 4th Alvey Vision Conference. Manchester, England. IEEE. 1988. 147–151.

4 Moravec H. Towards automatic visual obstacle avoidance. Proc. of the 5th International Joint Conference on Artificial Intelligence. Cambridge, MA, USA. William Kaufmann. 1977. 584.

5 Trajkovic M, Hedley M．Fast corner detection． Image and Vision Computing, 1998, 16(2): 75–87．

6 Schmid C, Mohr R, Bauckhage C. Evaluation of Interesting Point Detectors. International Journal of Computer Vision, 2000, 37(2): 151–172.

Improved Algorithm Based on Harris Corner Detection

HONG Gai-Yan1, RUI Ting-Xian2, YU Wei-Guang1, HE Shi-Chan1, WANG Tian-Zhao31(Department of Economics and Information Management, Shanghai University of Finance and Economics Zhejiang College, Jinhua 321000, China)2(School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200000, China)3(No.73051 of PLA, Jinhua 321000, China)

According to the problems of extracting more false corners and large computation problems in harris corner detection, this paper proposes an improved algorithm based on harris corner detection. In order to reduce the number of false corners and improve the algorithm efficiency, a pre-selection strategy is embedded to pick out potential corners before the normal routine. When calculate the horizontal and vertical gradients, the pixels with smaller horizontal and vertical gradients are pre-processed. In order to improve the auto-adaptive of algorithm, an auto-adaptive threshold is adopted, finally using USAN to make further selection. The result shows that the improved algorithm not only can improve the precision and efficiency of corner detection, but also is robust to noise to some extent.

Harris corner; corner pre-selection; auto-adaptive threshold; USAN

2016-07-18;收到修改稿時間:2016-08-08

10.15888/j.cnki.csa.005718