改进的SUSAN角点检测算法

张映权,王琼华,李大海,张文涛

摘 要:SUSAN角点检测算法以抗噪声性能强,运算速度快而被广泛运用于特征点的提取。传统的SUSAN算法的灰度差阈值固定,不能有效去除伪角点,并且在大尺寸模板检测下耗时多。针对这些问题,从模板尺寸对检测结果的影响出发,讨论不同尺寸模板的检测效果,从而提出一种变换模板提取特征点的方法。采用一种自动选取阈值的方法实现了阈值的自动选取,使用能量分布法和像素投影法去除了伪角点。结果显示,该方法缩短了检测时间,并且提高了检测准确度。

关键词:特征提取;SUSAN算法;能量分布;像素投影

中图分类号:TP391文献标识码: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 引 言

在计算机视觉和图像处理中角点还没有明确的数学定义,存在多种数学描述方法。一般的角点定义为图像中灰度的剧烈变化点或是曲线曲率的极大值点[1,2]。角点包含了大量图像信息,但却减小了计算量[3,4],因而被广泛运用于图像识别、目标匹配、图像融合以及三维重建之中[5,6]。SUSAN (Smallest Univalue Segment Assimilating Nucleus)算法[7,8]是由Smith等人提出的一种底层图像处理方法。此算法简单,定位精度高,运算速度快,其不需要梯度运算的特点,使该算法有很好的抗噪声性能[9,10]。但SUSAN算法也存在一些不足,例如,当模板增大时,其运算量显著增加,同时它不能很好地去除伪角点。基于以上两点,这里提出一种变换模板的方法,解决在大模板下耗时的缺点;然后使用能量分布和像素投影的方法去除伪角点。

1 SUSAN算法及改进算法

1.1 传统SUSAN算法的基本原理

图1是传统SUSAN算法的原理图,a,b,c,d是圆形模板所在的四个位置,模板中心点称为“核”,在模板内把所有与核值相同或相似的像素所构成的区域叫作核值相似区(USAN)。当模板位于平坦区域a时,USAN面积最大;当模板位于角点b时,USAN面积最小;当模板位于边缘c时,USAN面积为模板总面积50%;当模板位于d时,USAN面积大于总面积的50%,由此可根据USAN面积大小来判断角点位置。

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

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

检测时,模板在图上移动,在每个位置,用式(1)比较模板内各像素与核值的灰度。式(1)中:r0是模板核的位置;r是模板内其他点的位置;I0是模板核的灰度值;Ii是模板内其他像素的灰度值;tp是灰度阈值;c(r,r0)是灰度比较的结果。

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

图1 传统SUSAN算法原理图

式(1)中的灰度阈值tp决定了所能检测到的最低对比度以及去除噪声的能力,这里采用一种迭代的方法实现自动选取阈值。如式(2)所示,首先计算模板内各点与核的差值,再取这些差值的平均值t0作为迭代的初始值,其中N是模板内的像素个数。

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

按式(3)进行迭代。式(3)中,ti是迭代初值;ti+1是迭代值;d是模板内各点与核的灰度差;cmax是这些差值中的最大值;n(d)是模板内与核值的灰度差为d的点个数。

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

USAN的面积由式(4)给出,Farea(r0)是USAN的面积大小。通过判断Farea(r0)的值,便可判断此点是否是角点。

SUSAN检测算法中模板大小是固定的。实验表明,模板尺寸与检测结果密切相关。图2是不同尺寸方形模板检测结果对比,图2中加入了部分随机噪声。从图2可看出,模板越小,检测灵敏度越高;耗时越短,误检率越高;相反,大尺寸模板的检测准确度高,误检率低,但耗时更长。因此有必要寻找检测准确度高且耗时短的检测方法。

1.2 改进的SUSAN角点检测算法

变换模板检测方法结合了小模板检测灵敏度高,耗时短和大模板检测准确度高,误检率低的优势,从而可以满足上面的要求。变换模板方法的检测过程如下:首先用3×3的模板进行初检测,并记录下此时检测到的角点位置,然后再用9×9的模板对刚才记录下的初测角点位置进行精检测。这些初测角点只有在9×9模板下满足角点条件的才会被判定为特征点,这样就可以减少9×9模板检测的像素个数,减少了计算量, 从而缩减了检测时间。然而,实际中由于噪声的存在,经常会检测出伪角点,这需要去除。

图2 不同尺寸模板检测结果

首先分析一下伪角点产生的原因。图3是伪角点产生及能量分布法的原理图,图中颜色相同的方块表示其像素灰度相似。从图中可知,USAN的面积,即浅色方格的个数是20,其中不包括核。在文中判定是否是角点的条件:USAN的值介于模板总像素个数(不包括核)的1/4~1/2之间,因此图3中的核满足角点条件。产生误检的原因是USAN的像素分布不集中。

图3 伪角点产生及能量分布法原理图

从图3抽象出如下方法,模板内与核值灰度相似的像素组成模板内的一高能量区,即USAN高能量区;相反,模板内与核值灰度差大于灰度阈值tp的像素,则组成模板内的另一个相对的低能量区。模板内每个与核值灰度相似的像素都对USAN高能量区产生各自的贡献。

因为角点的USAN分布应相对集中,即它只应集中分布于模板四个角中的一个角,而不可能较均匀地散布在模板内,如图3所示。

以核所在的行、列为界,将模板分成四个能量区,核的左上方为能量Ⅰ区,右上方为Ⅱ区,同理左、右下方分别是Ⅲ、Ⅳ区,其中每个区都包含核所在的行列。因此可以分别计算出图3中四个能量区的能量大小,也即USAN面积。如果模板的能量集中分布于某一区域,即模板的四个能量区中只有一个高能量区,并且这一高能量区的大小满足文中提到的角点条件,那么这就是一个角点。

图4是变换模板方法下用能量分布法去除伪角点的检测图。从图4看出,能量分布法能较好地去除伪角点,但图4中由两条直线相交而成的那些角点却没有被检测到,如图4中用圆圈标识出的,这是因为它们在模板内的分布本来就不集中。结合这类角点的特性,可采用像素投影法来检测。

图5为像素投影法的原理图,如图5中虚线箭头所示,模板中与核值灰度相似的像素在垂直方向向下做投影,同时各列相应像素投影区计数加1,最后通过判断各列像素投影区的值就可判断出该模板中心是否是角点。在此过程中,核不参与投影,核所在列的像素投影区位置最终也不予考虑。综合实际中存在的噪声,并考虑到常见的线型有“十”型和“X”型两种,若各列投影区均有值,且不大于2,就认为该模板中心为角点。

图4 能量分布法去除伪角点检测图

图5 像素投影法原理图

1.3 实验结果及分析

图6是变换模板方法结合能量分布法与像素投影法提取一幅图像的特征点。图像分辨率是640×480,图中加有部分随机噪声,角点数为56个,包含了各类型角点。

图6 改进的SUSAN算法检测结果

对比图6和图2可看出,由于能量分布法的使用,许多伪角点都被去除掉。对比图6和图4可看出,由直线相交而成的角点在图4中没有被检测到,而在图6中,因为像素投影法的使用,它们被检测到了。表1是检测结果对照表。从表1得出的模板越小,检测出的伪角点越多,但耗时越短,大模板则有相反检测效果。在结合了大小尺寸模板后,就可得到较好的结果。从图6和表1可看出,改进算法的准确度最高,它提取出所有角点,且耗时最短。

表1 不同尺寸模板检测对照

模板角点个数角点误差个数耗时 /s

3×33322760.119

5×5129730.693

9×980246.201

改进算法模板5600.924

2 结 语

提出一种改进的SUSAN角点检测算法,充分利用不同尺寸模板的优点,使检测速度和准确度都得到很大程度的提高,最后运用能量分布和像素投影的方法很好地去除了伪角点。结果显示,该方法可以快速准确地提取出图像的特征点。

参考文献

[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]杨莉,张弘,李玉山.一种快速自适应RSUSAN角点检测算法[J].计算机科学,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]陆宏伟,于起峰.最小核值相似区低层次图像处理算法的改进及应用[J].应用光学,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]张坤华,王敬儒,张启衡.多特征复合的角点提取方法[J].中国图像图形学报(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]邹琼兵,周东翔,蔡宣平.基于边缘细化的角点检测方法[J].计算机应用与软件,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.