Harris角點(diǎn)檢測(cè)的優(yōu)化算法①

洪改艷, 芮廷先, 俞偉廣, 何士產(chǎn), 王天召(上海財(cái)經(jīng)大學(xué) 浙江學(xué)院經(jīng)濟(jì)與信息管理系, 金華 000)(上海財(cái)經(jīng)大學(xué) 信息管理與工程學(xué)院, 上海 00000)(解放軍705部隊(duì), 金華 000)

Harris角點(diǎn)檢測(cè)的優(yōu)化算法①

洪改艷1, 芮廷先2, 俞偉廣1, 何士產(chǎn)1, 王天召31(上海財(cái)經(jīng)大學(xué) 浙江學(xué)院經(jīng)濟(jì)與信息管理系, 金華 321000)2(上海財(cái)經(jīng)大學(xué) 信息管理與工程學(xué)院, 上海 200000)3(解放軍73051部隊(duì), 金華 321000)

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

Harris角點(diǎn); 角點(diǎn)預(yù)選; 自適應(yīng)閾值; USAN

角點(diǎn)被普遍認(rèn)為是二維圖像亮度變化劇烈或者圖像邊緣曲線上曲率極大值的點(diǎn)[1]. 角點(diǎn)檢測(cè)在圖像匹配、光流計(jì)算、運(yùn)動(dòng)估計(jì)、形狀分析、相機(jī)標(biāo)定和3D重建、視覺的定位和測(cè)量等方面都有重要的應(yīng)用.

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

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

1 Harris算法檢測(cè)原理及步驟

1.1 Harris算法基本原理

Harris算法以Moravec算法為基礎(chǔ), Moravec算法的基本原理是: 取以目標(biāo)像素點(diǎn)為中心的一個(gè)小窗口,并將窗口沿上下左右4個(gè)方向移動(dòng), 計(jì)算這4個(gè)方向上窗口內(nèi)的灰度變化, 并以4個(gè)灰度變化值中的最小值作為該目標(biāo)像素點(diǎn)的角點(diǎn)相應(yīng)函數(shù), 若該值大于設(shè)定閾值, 則為角點(diǎn).

Harris算法則計(jì)算窗口沿任何方向移動(dòng)后的灰度變化, 并用解析形式表達(dá). 設(shè)以像素點(diǎn)≤為中心的小窗口在X方向上移動(dòng)u, Y方向上移動(dòng)v, Harris算法給出了灰度變化度量的解析表達(dá)式:

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

1.2 Harris算法步驟

根據(jù)Harris算法的基本原理, 可以將Harris算法步驟分為以下五個(gè)步驟:

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

Step2 對(duì)圖像進(jìn)行高斯濾波, 得到新的M;

Step3 計(jì)算原圖像上對(duì)應(yīng)每個(gè)像素點(diǎn)的CRF值;

Step4 選取局部極值點(diǎn). 在Harris算法中, 特征點(diǎn)被認(rèn)為是局部范圍內(nèi)的極大CRF值所對(duì)應(yīng)的像點(diǎn);

Step5 設(shè)定閾值, 選取角點(diǎn).

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

為了提高Harris算法檢測(cè)角點(diǎn)的效率和精度, 改進(jìn)Harris算法主要在以下四個(gè)方面:

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

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

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

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

2.1 GSAP處理得到候選點(diǎn)

設(shè)中心點(diǎn)像素的灰度值與周圍一像素點(diǎn)灰度值差的絕對(duì)值為Δ, 設(shè)閾值為t, 如果tΔ≤, 則認(rèn)為中心點(diǎn)與該點(diǎn)周圍一點(diǎn)相似, 同理判斷中心點(diǎn)與周圍其它點(diǎn)是否相似. 統(tǒng)計(jì)中心點(diǎn)與周圍8個(gè)點(diǎn)中相似點(diǎn)的個(gè)數(shù), 記為（）,C i j:

根據(jù)以上討論可知, 0≤C（ i, j）≤8, 下面對(duì)C（ i, j）進(jìn)行討論分析, 如果能夠找出一個(gè)實(shí)例判定該點(diǎn)可能為角點(diǎn), 那么該點(diǎn)就作為候選點(diǎn)進(jìn)行角點(diǎn)檢測(cè).

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

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

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

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

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

綜上所述, 當(dāng)1≤C（ i, j）≤6時(shí), 將中心像素點(diǎn)作為角點(diǎn)的候選點(diǎn).

2.2 角點(diǎn)檢測(cè)預(yù)處理

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

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

2.3 自適應(yīng)閾值

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

求取每個(gè)預(yù)處理后的角點(diǎn)的響應(yīng)函數(shù)值CRF, 找出最大的CRF值, 隨后定義閾值T為最大CRF值的p倍決定的, 即:

其中, C為總的預(yù)處理后的候選點(diǎn)總數(shù)目. 則:

從統(tǒng)計(jì)的觀點(diǎn)出發(fā),, 選取一系列圖像包括各種場(chǎng)景進(jìn)行實(shí)驗(yàn),, 不斷調(diào)整設(shè)定的p值, 比較結(jié)果, 發(fā)現(xiàn)p取經(jīng)驗(yàn)值[0.005, 0.015] 時(shí), 基本上所有角點(diǎn)都可以被檢驗(yàn)出來, 而且產(chǎn)生的偽角點(diǎn)較少.

2.4 利用USAN去除偽角點(diǎn)

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

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

圖2 7x7圓形模板及利用USAN的角點(diǎn)判別

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

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

圖3 實(shí)驗(yàn)結(jié)果

表1 實(shí)驗(yàn)數(shù)據(jù)結(jié)果比較

通過實(shí)驗(yàn), 原始的Harris檢測(cè)算法在檢測(cè)時(shí)產(chǎn)生較多的偽角點(diǎn), 并且程序運(yùn)行的時(shí)間比較長. 而改進(jìn)后的Harris檢測(cè)算法因?yàn)閷?duì)圖像點(diǎn)進(jìn)行了預(yù)選擇和預(yù)處理, 大大降低了程序運(yùn)行的時(shí)間, 從0.765s減少為0.297s, 將近原始算法的30%; 保證檢測(cè)出正確的角點(diǎn)的同時(shí), 檢測(cè)時(shí)產(chǎn)生的偽角點(diǎn)數(shù)目也大大降低, 從16個(gè)降低到了5個(gè), 不足原始算法的30%.

為了驗(yàn)證改進(jìn)的Harris檢測(cè)算法對(duì)噪聲的魯棒性,對(duì)圖像增加了椒鹽噪聲, 椒鹽噪聲通常由圖像傳感器、傳輸信道、解碼處理、圖像切割等產(chǎn)生的黑白相間的亮暗點(diǎn)噪聲, 實(shí)驗(yàn)中椒鹽噪聲的參數(shù)d=0.01, 實(shí)驗(yàn)結(jié)果如圖4所示.

圖4 加入椒鹽噪聲(d=0.01)后的實(shí)驗(yàn)結(jié)果

通過實(shí)驗(yàn)結(jié)果可以看出, Harris算法對(duì)噪聲比較敏感, 但是改進(jìn)后的Harris算法相對(duì)于原始Harris算法具有一定的魯棒性.

4 結(jié)語

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

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;收到修改稿時(shí)間:2016-08-08

10.15888/j.cnki.csa.005718