改進(jìn)的SUSAN角點(diǎn)檢測(cè)算法

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

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

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

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

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

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

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

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

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

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

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

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

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

式(1)中的灰度閾值tp決定了所能檢測(cè)到的最低對(duì)比度以及去除噪聲的能力,這里采用一種迭代的方法實(shí)現(xiàn)自動(dòng)選取閾值。如式(2)所示,首先計(jì)算模板內(nèi)各點(diǎn)與核的差值,再取這些差值的平均值t0作為迭代的初始值,其中N是模板內(nèi)的像素個(gè)數(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)各點(diǎn)與核的灰度差;cmax是這些差值中的最大值;n(d)是模板內(nèi)與核值的灰度差為d的點(diǎn)個(gè)數(shù)。

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

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

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

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

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

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

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

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

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

因?yàn)榻屈c(diǎn)的USAN分布應(yīng)相對(duì)集中,即它只應(yīng)集中分布于模板四個(gè)角中的一個(gè)角,而不可能較均勻地散布在模板內(nèi),如圖3所示。

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

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

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

圖4 能量分布法去除偽角點(diǎn)檢測(cè)圖

圖5 像素投影法原理圖

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

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

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

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

表1 不同尺寸模板檢測(cè)對(duì)照

模板角點(diǎn)個(gè)數(shù)角點(diǎn)誤差個(gè)數(shù)耗時(shí) /s

3×33322760.119

5×5129730.693

9×980246.201

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

2 結(jié) 語

提出一種改進(jìn)的SUSAN角點(diǎn)檢測(cè)算法,充分利用不同尺寸模板的優(yōu)點(diǎn),使檢測(cè)速度和準(zhǔn)確度都得到很大程度的提高,最后運(yùn)用能量分布和像素投影的方法很好地去除了偽角點(diǎn)。結(jié)果顯示,該方法可以快速準(zhǔn)確地提取出圖像的特征點(diǎ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角點(diǎn)檢測(cè)算法[J].計(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ù)合的角點(diǎn)提取方法[J].中國圖像圖形學(xué)報(bào)(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ì)化的角點(diǎn)檢測(cè)方法[J].計(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.