改进的SUSAN角点检测算法

1、改进的SUSAN!点检测算法Improved SUSAN Corner Detection AlgorithmZHANG Yingquan,WANG Qionghua,LI Dahai,ZHANG Wentao (School of Electronics and InformationEngineering,Key Laboratory of Fundamental Synthetic Vision Graphics and Imagefor National Defense,Sichuan University,Chengdu,610065,China):SUSAN corner dete

2、ction 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 e liminate the fake corner well.The traditional algorithm is time-consuming when large-size mas

3、k 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 fa

4、ke corners.The experimental results show that this improved algorithm reduces the detection time and improves the detection accuracy.distribution;pixel projection0 引 言在计算机视觉和图像处理中角点还没有明确的数学定义 , 存 在多种数学描述方法。 一般的角点定义为图像中灰度的剧烈变化 点或是曲线曲率的极大值点 1,2 。角点包含了大量图像信息 , 但却减小了计算量 3,4, 因而被广泛运用于图像识别、目标匹 配、图像融合以及三维重

5、建之中 5,6 。 SUSAN (Smallest Univalue Segment Assimilating Nucleus) 算法7,8 是由 Smith 等人提出的一种底层图像处理方法。此算法简单 , 定位精度高 , 运算速度快 , 其不需要梯度运算的特点 , 使该算法有很好的抗噪 声性能9,10。但SUSAN!法也存在一些不足，例如,当模板增大 时, 其运算量显著增加 , 同时它不能很好地去除伪角点。 基于以上 两点,这里提出一种变换模板的方法 ,解决在大模板下耗时的缺 点; 然后使用能量分布和像素投影的方法去除伪角点。1 SUSAN算法及改进算法1.1传统SUSAf算法的基本原理图1

6、是传统SUSAN!法的原理图，a,b,c,d 是圆形模板所在 的四个位置 , 模板中心点称为“核” , 在模板内把所有与核值相 同或相似的像素所构成的区域叫作核值相似区(USAN)。当模板位于平坦区域a时,USAN面积最大；当模板位于角点b时,USAN面积 最小；当模板位于边缘c时,USAN面积为模板总面积50%;当模板位于d时,USAN面积大于总面积的50%,由此可根据USAN面积大 小来判断角点位置。c(r,r0)=1, |li- I0| tp(1)检测时, 模板在图上移动 , 在每个位置 , 用式(1) 比较模板内 各像素与核值的灰度。式(1)中:r0是模板核的位置;r是模板内 其他点的

7、位置 ;l0 是模板核的灰度值 ;li 是模板内其他像素的灰 度值;tp是灰度阈值;c(r,r0) 是灰度比较的结果。t0=1NE Ni=0abs(li -10) (2)图1传统SUSAf算法原理图式(1) 中的灰度阈值 tp 决定了所能检测到的最低对比度以 及去除噪声的能力 , 这里采用一种迭代的方法实现自动选取阈 值。如式 (2) 所示, 首先计算模板内各点与核的差值 , 再取这些差 值的平均值t0作为迭代的初始值，其中N是模板内的像素个数。ti + 1= 12Etid = 0dn(d)刀tid = 0n(d) + 刀 cmax d = ti+1d n(d) 刀 cmaxd = ti+1

8、n(d) (3)按式进行迭代。式中,ti是迭代初值;ti+1是迭代 值;d是模板内各点与核的灰度差;cmax是这些差值中的最大 值;n(d)是模板内与核值的灰度差为d的点个数。Farea(r0)= E Nr=1c(r,r0)(4)USAN勺面积由式 给出,Farea(r0) 是USAN的面积大小。通过判断 Farea(r0) 的值, 便可判断此点是否是角点SUSAN检测算法中模板大小是固定的。实验表明，模板尺寸 与检测结果密切相关。图 2 是不同尺寸方形模板检测结果对比 , 图 2 中加入了部分随机噪声。 从图 2 可看出 , 模板越小 , 检测灵敏 度越高;耗时越短,误检率越高;相反,大尺寸

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

10、出伪角点 , 这需要 去除。图 2 不同尺寸模板检测结果首先分析一下伪角点产生的原因。 图 3是伪角点产生及能量 分布法的原理图 , 图中颜色相同的方块表示其像素灰度相似。从 图中可知,USAN的面积，即浅色方格的个数是20,其中不包括核。 在文中判定是否是角点的条件:USA N的值介于模板总像素个数 （不包括核）的 1/41/2 之间,因此图 3中的核满足角点条件。产生误检的原因是USAN勺像素分布不集中。图3 伪角点产生及能量分布法原理图 从图 3 抽象出如下方法 , 模板内与核值灰度相似的像素组成 模板内的一高能量区，即USAN高能量区；相反,模板内与核值灰 度差大于灰度阈值 tp 的像

11、素 , 则组成模板内的另一个相对的低 能量区。模板内每个与核值灰度相似的像素都对USAN高能量区产生各自的贡献。因为角点的USAN分布应相对集中，即它只应集中分布于模 板四个角中的一个角 , 而不可能较均匀地散布在模板内 , 如图 3 所示。以核所在的行、列为界,将模板分成四个能量区 ,核的左上方 为能量I区，右上方为口区，同理左、右下方分别是区，其 中每个区都包含核所在的行列。 因此可以分别计算出图 3 中四个 能量区的能量大小，也即USAN面积。如果模板的能量集中分布于 某一区域 , 即模板的四个能量区中只有一个高能量区 , 并且这一 高能量区的大小满足文中提到的角点条件 , 那么这就是一

12、个角 点。图 4 是变换模板方法下用能量分布法去除伪角点的检测图。 从图 4看出, 能量分布法能较好地去除伪角点 , 但图 4中由两条直 线相交而成的那些角点却没有被检测到 , 如图 4 中用圆圈标识出 的, 这是因为它们在模板内的分布本来就不集中。结合这类角点 的特性,可采用像素投影法来检测。图5为像素投影法的原理图 , 如图 5中虚线箭头所示 , 模板中 与核值灰度相似的像素在垂直方向向下做投影 , 同时各列相应像 素投影区计数加 1, 最后通过判断各列像素投影区的值就可判断 出该模板中心是否是角点。 在此过程中 ,核不参与投影 , 核所在列 的像素投影区位置最终也不予考虑。综合实际中存在

13、的噪声 , 并 考虑到常见的线型有“十”型和“ X”型两种，若各列投影区均 有值 , 且不大于 2, 就认为该模板中心为角点。图4 能量分布法去除伪角点检测图图5 像素投影法原理图1.3 实验结果及分析图 6 是变换模板方法结合能量分布法与像素投影法提取一幅图像的特征点。图像分辨率是 640X480,图中加有部分随机噪 声, 角点数为 56 个, 包含了各类型角点。图6改进的SUSAf算法检测结果对比图 6和图2可看出,由于能量分布法的使用 ,许多伪角点 都被去除掉。对比图 6 和图 4 可看出 , 由直线相交而成的角点在 图 4 中没有被检测到 , 而在图 6 中 , 因为像素投影法的使用 , 它们 被检测到了。表 1 是检测结果对照表。从表 1 得出的模板越小 , 检测出的伪角点越多 , 但耗时越短 , 大模板则有相反检测效果。 在 结合了大小尺寸模板后 ,就可得到较好的结果。从图 6和表 1可 看出 , 改进算法的准确度最高 , 它提取出所有