改進(jìn)的SUSAN角點檢測算法

張映權(quán),王瓊?cè)A,李大海,張文濤

摘 要:SUSAN角點檢測算法以抗噪聲性能強(qiáng),運算速度快而被廣泛運用于特征點的提取。傳統(tǒng)的SUSAN算法的灰度差閾值固定,不能有效去除偽角點,并且在大尺寸模板檢測下耗時多。針對這些問題,從模板尺寸對檢測結(jié)果的影響出發(fā),討論不同尺寸模板的檢測效果,從而提出一種變換模板提取特征點的方法。采用一種自動選取閾值的方法實現(xiàn)了閾值的自動選取,使用能量分布法和像素投影法去除了偽角點。結(jié)果顯示,該方法縮短了檢測時間,并且提高了檢測準(zhǔn)確度。

關(guān)鍵詞:特征提取;SUSAN算法;能量分布;像素投影

中圖分類號:TP391文獻(xiàn)標(biāo)識碼:A

文章編號:1004-373X(2009)20-042-03

Improved SUSAN Corner Detection Algorithm

ZHANG Yingquan,WANG Qionghua,LI Dahai,ZHANG Wentao

(School of Electronics and Information Engineering,Key Laboratory of Fundamental Synthetic Vision Graphics and Imagefor National Defense,Sichuan University,Chengdu,610065,China)

Abstract:SUSAN corner detection algorithm is widely used in feature extraction for its good performance in noise resistance and fast calculation.The traditional SUSAN algorithm has a fixed brightness difference threshold and can′t eliminate the fake corner well.The traditional algorithm is time-consuming when large-size mask is used.Aiming at those problems,the relationship between mask size and detection results is discussed,and an algorithm using alternate mask is proposed.A method that can select the threshold automatically is adopted.The energy distribution and pixel projection methods are used to eliminate the fake corners.The experimental results show that this improved algorithm reduces the detection time and improves the detection accuracy.

Keywords:feature extraction;SUSAN algorithm;energy distribution;pixel projection

0 引 言

在計算機(jī)視覺和圖像處理中角點還沒有明確的數(shù)學(xué)定義,存在多種數(shù)學(xué)描述方法。一般的角點定義為圖像中灰度的劇烈變化點或是曲線曲率的極大值點[1,2]。角點包含了大量圖像信息,但卻減小了計算量[3,4],因而被廣泛運用于圖像識別、目標(biāo)匹配、圖像融合以及三維重建之中[5,6]。SUSAN (Smallest Univalue Segment Assimilating Nucleus)算法[7,8]是由Smith等人提出的一種底層圖像處理方法。此算法簡單,定位精度高,運算速度快,其不需要梯度運算的特點,使該算法有很好的抗噪聲性能[9,10]。但SUSAN算法也存在一些不足,例如,當(dāng)模板增大時,其運算量顯著增加,同時它不能很好地去除偽角點。基于以上兩點,這里提出一種變換模板的方法,解決在大模板下耗時的缺點;然后使用能量分布和像素投影的方法去除偽角點。

1 SUSAN算法及改進(jìn)算法

1.1 傳統(tǒng)SUSAN算法的基本原理

圖1是傳統(tǒng)SUSAN算法的原理圖,a,b,c,d是圓形模板所在的四個位置,模板中心點稱為“核”,在模板內(nèi)把所有與核值相同或相似的像素所構(gòu)成的區(qū)域叫作核值相似區(qū)(USAN)。當(dāng)模板位于平坦區(qū)域a時,USAN面積最大;當(dāng)模板位于角點b時,USAN面積最小;當(dāng)模板位于邊緣c時,USAN面積為模板總面積50%;當(dāng)模板位于d時,USAN面積大于總面積的50%,由此可根據(jù)USAN面積大小來判斷角點位置。

c(r,r0)=1, |Ii-I0|≤tp

0, |Ii-I0|>tp(1)

檢測時,模板在圖上移動,在每個位置,用式(1)比較模板內(nèi)各像素與核值的灰度。式(1)中:r0是模板核的位置;r是模板內(nèi)其他點的位置;I0是模板核的灰度值;Ii是模板內(nèi)其他像素的灰度值;tp是灰度閾值;c(r,r0)是灰度比較的結(jié)果。

t0=1N∑Ni=0abs(Ii-I0)(2)

圖1 傳統(tǒng)SUSAN算法原理圖

式(1)中的灰度閾值tp決定了所能檢測到的最低對比度以及去除噪聲的能力,這里采用一種迭代的方法實現(xiàn)自動選取閾值。如式(2)所示,首先計算模板內(nèi)各點與核的差值,再取這些差值的平均值t0作為迭代的初始值,其中N是模板內(nèi)的像素個數(shù)。

ti + 1= 12∑tid = 0[d?n(d)]∑tid = 0n(d) + ∑cmax d = ti+1[d?n(d)]∑cmaxd = ti+1n(d) (3)

按式(3)進(jìn)行迭代。式(3)中,ti是迭代初值;ti+1是迭代值;d是模板內(nèi)各點與核的灰度差;cmax是這些差值中的最大值;n(d)是模板內(nèi)與核值的灰度差為d的點個數(shù)。

Farea(r0)=∑Nr=1c(r,r0)(4)

USAN的面積由式(4)給出,Farea(r0)是USAN的面積大小。通過判斷Farea(r0)的值,便可判斷此點是否是角點。

SUSAN檢測算法中模板大小是固定的。實驗表明,模板尺寸與檢測結(jié)果密切相關(guān)。圖2是不同尺寸方形模板檢測結(jié)果對比,圖2中加入了部分隨機(jī)噪聲。從圖2可看出,模板越小,檢測靈敏度越高;耗時越短,誤檢率越高;相反,大尺寸模板的檢測準(zhǔn)確度高,誤檢率低,但耗時更長。因此有必要尋找檢測準(zhǔn)確度高且耗時短的檢測方法。

1.2 改進(jìn)的SUSAN角點檢測算法

變換模板檢測方法結(jié)合了小模板檢測靈敏度高,耗時短和大模板檢測準(zhǔn)確度高,誤檢率低的優(yōu)勢,從而可以滿足上面的要求。變換模板方法的檢測過程如下:首先用3×3的模板進(jìn)行初檢測,并記錄下此時檢測到的角點位置,然后再用9×9的模板對剛才記錄下的初測角點位置進(jìn)行精檢測。這些初測角點只有在9×9模板下滿足角點條件的才會被判定為特征點,這樣就可以減少9×9模板檢測的像素個數(shù),減少了計算量, 從而縮減了檢測時間。然而,實際中由于噪聲的存在,經(jīng)常會檢測出偽角點,這需要去除。

圖2 不同尺寸模板檢測結(jié)果

首先分析一下偽角點產(chǎn)生的原因。圖3是偽角點產(chǎn)生及能量分布法的原理圖,圖中顏色相同的方塊表示其像素灰度相似。從圖中可知,USAN的面積,即淺色方格的個數(shù)是20,其中不包括核。在文中判定是否是角點的條件:USAN的值介于模板總像素個數(shù)(不包括核)的1/4~1/2之間,因此圖3中的核滿足角點條件。產(chǎn)生誤檢的原因是USAN的像素分布不集中。

圖3 偽角點產(chǎn)生及能量分布法原理圖

從圖3抽象出如下方法,模板內(nèi)與核值灰度相似的像素組成模板內(nèi)的一高能量區(qū),即USAN高能量區(qū);相反,模板內(nèi)與核值灰度差大于灰度閾值tp的像素,則組成模板內(nèi)的另一個相對的低能量區(qū)。模板內(nèi)每個與核值灰度相似的像素都對USAN高能量區(qū)產(chǎn)生各自的貢獻(xiàn)。

因為角點的USAN分布應(yīng)相對集中,即它只應(yīng)集中分布于模板四個角中的一個角,而不可能較均勻地散布在模板內(nèi),如圖3所示。

以核所在的行、列為界,將模板分成四個能量區(qū),核的左上方為能量Ⅰ區(qū),右上方為Ⅱ區(qū),同理左、右下方分別是Ⅲ、Ⅳ區(qū),其中每個區(qū)都包含核所在的行列。因此可以分別計算出圖3中四個能量區(qū)的能量大小,也即USAN面積。如果模板的能量集中分布于某一區(qū)域,即模板的四個能量區(qū)中只有一個高能量區(qū),并且這一高能量區(qū)的大小滿足文中提到的角點條件,那么這就是一個角點。

圖4是變換模板方法下用能量分布法去除偽角點的檢測圖。從圖4看出,能量分布法能較好地去除偽角點,但圖4中由兩條直線相交而成的那些角點卻沒有被檢測到,如圖4中用圓圈標(biāo)識出的,這是因為它們在模板內(nèi)的分布本來就不集中。結(jié)合這類角點的特性,可采用像素投影法來檢測。

圖5為像素投影法的原理圖,如圖5中虛線箭頭所示,模板中與核值灰度相似的像素在垂直方向向下做投影,同時各列相應(yīng)像素投影區(qū)計數(shù)加1,最后通過判斷各列像素投影區(qū)的值就可判斷出該模板中心是否是角點。在此過程中,核不參與投影,核所在列的像素投影區(qū)位置最終也不予考慮。綜合實際中存在的噪聲,并考慮到常見的線型有“十”型和“X”型兩種,若各列投影區(qū)均有值,且不大于2,就認(rèn)為該模板中心為角點。

圖4 能量分布法去除偽角點檢測圖

圖5 像素投影法原理圖

1.3 實驗結(jié)果及分析

圖6是變換模板方法結(jié)合能量分布法與像素投影法提取一幅圖像的特征點。圖像分辨率是640×480,圖中加有部分隨機(jī)噪聲,角點數(shù)為56個,包含了各類型角點。

圖6 改進(jìn)的SUSAN算法檢測結(jié)果

對比圖6和圖2可看出,由于能量分布法的使用,許多偽角點都被去除掉。對比圖6和圖4可看出,由直線相交而成的角點在圖4中沒有被檢測到,而在圖6中,因為像素投影法的使用,它們被檢測到了。表1是檢測結(jié)果對照表。從表1得出的模板越小,檢測出的偽角點越多,但耗時越短,大模板則有相反檢測效果。在結(jié)合了大小尺寸模板后,就可得到較好的結(jié)果。從圖6和表1可看出,改進(jìn)算法的準(zhǔn)確度最高,它提取出所有角點,且耗時最短。

表1 不同尺寸模板檢測對照

模板角點個數(shù)角點誤差個數(shù)耗時 /s

3×33322760.119

5×5129730.693

9×980246.201

改進(jìn)算法模板5600.924

2 結(jié) 語

提出一種改進(jìn)的SUSAN角點檢測算法,充分利用不同尺寸模板的優(yōu)點,使檢測速度和準(zhǔn)確度都得到很大程度的提高,最后運用能量分布和像素投影的方法很好地去除了偽角點。結(jié)果顯示,該方法可以快速準(zhǔn)確地提取出圖像的特征點。

參考文獻(xiàn)

[1]Smith S M,Brady M J.SUSAN-A New Approach to Low Level Image Processing[J].International Journal of Compu-ter Vision,1997,23(1):45-48.

[2]楊莉,張弘,李玉山.一種快速自適應(yīng)RSUSAN角點檢測算法[J].計算機(jī)科學(xué),2004,31(5):198-200.

[3]Shen F,Wnag H.Real Time Gray Level Corner Detector[J].Pattern Rectionition Letters,2003,23(8):1-6.

[4]Trajkovic M,Hedley M.Fast Corner Detection[J].Image Vision Comput.,1998,16(2):75-87.

[5]陸宏偉,于起峰.最小核值相似區(qū)低層次圖像處理算法的改進(jìn)及應(yīng)用[J].應(yīng)用光學(xué),2000,21(1):32-36.

[6]Zhou Dongxiang,Liu Yunhui,Cai Xuanping.An Efficient and Robust Corner Detection Algorithm[A].Proceedings of the 5th World Congress on Intelligent Control and Automation[C].Hangzhou,2004:4 020-4 023.

[7]張坤華,王敬儒,張啟衡.多特征復(fù)合的角點提取方法[J].中國圖像圖形學(xué)報(A輯),2004,7(4):319-324.

[8]Weng Muyun,He Mingyi.Image Feature Detection and Matching Based on Susan Method[A].2006 International Conference on Innovative Computing,Information and Control[C].Beijing,2006:322-325.

[9]鄒瓊兵,周東翔,蔡宣平.基于邊緣細(xì)化的角點檢測方法[J].計算機(jī)應(yīng)用與軟件,2006,23(3):110-112.

[10]Gholamali Rezai-Rad,Aghababaie Majid.Comparison of SUSAN and Sobel Edge Detection in MRI Images for Feature Extraction[A].Proceedings of International Confe-rence on Information and Communication Technologies[C].Damascus,2006:1 103-1 107.