第41卷第6期 2007年6月
上海交通大学学报
JOU RN AL O F SH AN G HA I JIA OT O N G U N IV ERSIT Y
Vol. 41No. 6 Jun. 2007
文章编号:1006-2467(2007) 06-0911-05
通用亚像素边缘检测算法
盛遵冰, 崔贤玉, 高国安
(哈尔滨工业大学机电工程学院, 哈尔滨150001)
摘 要:研究了针对不同边缘类型进行同步亚像素级检测的问题. 通过详细分析3种基本边缘类型(阶跃型边缘、脉冲型边缘、屋脊型边缘) 的特点, 提出了一种基于形体质心思想的通用算法, 并对
其进行了严格证明. 该算法能同时对这3种基本类型边缘进行亚像素级检测与定位, 且不存在原理性误差. 对算法进行离散化处理, 给出了便于计算机实现的离散算法. 通过实验验证了此算法的有效性, 并分析了误差产生的原因.
关键词:亚像素边缘检测; 算法; 图形质心中图分类号:TN 911. 73 文献标识码:A
A Universal Algorithm for Subpixel Edge Detection
SH EN G Zun -bing , CUI X ian -y u, GA O Guo -an
(Schoo l of M echatr onics Eng. , H ar bin Inst. of Technolog y, H arbin 150001, China)
Abstract:T he pr oblem for detecting all types of edge w ith a sam e m ethod at subpix el lev el w as r esearched. A novelty universal algorithm for subpix el edg e detectio n based on figure centr oid w as propo sed by analy -zing the character istics of three basic types of edge(step edg e, pulse edge, ro of edge). It can pr ocess all ty pes of edg e at one time. T he algo rithm w as demo nstrated, and it w as illuminated no erro r theoretically. Afterw ard discrete fo rm of the algor ithm w as deduced fo r calculating on computer. Finally , validity of the algorithm w as testified by prelim inary ex periments in noise and no noise situation, and the reason of mak -ing error w as analyzed.
Key words:subpixel edge detection; alg orithm ; figure centroid
随着机器视觉技术在检测和测量中广泛深入的应用, 人们期望能从现有图像信息中获取物体更为
精确的尺寸和位置信息. 为此, 针对不同应用人们提出了许多亚像素级边缘检测算法. 基于矩保持的亚像素边缘检测算法是T abatabai 等[1]于1984年提出的一种具有代表性的算法, 它的基本思想是保持理想图像和实际图像的多阶矩相等, 以此来计算边缘的亚像素级位置. 由于需要计算多阶矩, 涉及到多次方运算, 运算量较大, 并且对噪声的抑制能力较
收稿日期:2006-07-16
弱. 另外, 各种基于拟合思想的亚像素边缘检测算法, 由于需要拟合多项式, 求解矩阵方程, 计算量
也相对较大, 且对不同边缘类型不具有通用性. 其他的算法, 如基于变换域(如小波变换) 的亚像素边缘检测算法[5]、基于Zernike 矩的亚像素边缘检测算法[6]等, 也存在着这些问题. 现有算法的缺点之一是不能对同一幅图像中的不同边缘类型进行有效检测, 即这些算法不具有良好的通用性.
本文提出一种基于形体质心思想的通用算法.
[2-4]
作者简介:盛遵冰(1977-) , 男, 山东鱼台人, 博士生, 从事基于机器视觉的精密检测测量技术的研究, E -mail:shengzb@hit. edu. cn.
高国安(联系人) , 男, 教授, 博士生导师, 电话(T el. ) :0451-86416778; E -mail:guoan @hit. edu. cn.
912
上 海 交 通 大 学 学 报
第41卷
对阶跃型边缘、脉冲型边缘、屋脊型边缘3种基本类型边缘的特点进行详细分析后发现, 这3种基本边缘类型的一阶导数是关于边缘点的对称函数, 它们的绝对值则是一个关于边缘点的偶对称函数. 而从图形的角度考虑, 此对称点恰是图形的质心. 因此亚像素级边缘检测问题就可以转化为求解图形质心问题.
又
证明 因为f (x ) =u s (x ) *g(x ) , 所以
f c (x ) =u c s (x ) *g (x ) u c s (x ) =(B -A ) D (x -x 0)
故
f c (x ) =(B -A ) g(x -x 0)
其中, D (x ) 为单位脉冲函数.
(1) 证明f c (x ) 是关于点(x 0, 0) 的偶对称函数, f c (x 0+x ) -f c (x 0-x ) =(B -A ) g(x ) -(B -A ) g(-x )
由g(-x ) =g(x ) , 得f c (x 0+x ) -f c (x 0-x ) =0, 即f c (x ) 是关于点(x 0, 0) 的偶对称函数.
(2) 引入变量X , 令x =X +x 0, 则
1 算法的理论基础及证明
理论上, 一般认为图像是原始理想信息在点扩散函数的卷积作用下形成的. 在不考虑噪声影响的
情况下, 其一维数学模型简单表示为
f (x ) =u(x ) *g(x )
其中:u(x ) 为原始理想信号; f (x ) 为一维图像信息; g(x ) 为点扩散函数, 一般近似为高斯函数,
g(x ) =
2
ex p -22R 2PR
Q
+]-]
x |f c (x ) |dx =
Q
+]-]
(X +x 0) |f c (X +x 0) |d X =
+]-]
若u(x ) 分别取为理想阶跃边缘u s (x ) 、理想脉
冲边缘u p (x ) 、理想屋脊边缘u r (x ) , 则经点扩散函数作用后, 尖锐的理想边缘被平滑成模糊边缘. 点扩
散函数的平滑作用将不可微函数(理想信号) 变成了一个可微函数. 上述3个可微函数的一阶导数图形(见图1) 是关于某点对称的. 此对称点即为所寻求的边缘点x 0.
因为g(x ) 为偶函数, 所以
Q |g(X ) |d X +
|B -A |
Q X |g (X ) |d X
|B -A |x 0
+]-]
Q
故
+]-]+]-]
+]-]
X |g(X ) |d X =0
x |f c (x ) |d x =
Q |f c (x ) |d x
x |B -A ||g(X ) |d X
=
|B -A |
|g(x ) |d x
+]-]
+]-]
x 0
证毕
图1 3种基本类型边缘的微分图形
Fig. 1 T he differentials of three basic types of edg e
定理2 设u p (x ) 为理想脉冲边缘函数, 即
A
u p (x ) =
B A
x
x 0-$p [x
x \x 0+$p
(2)
为了说明算法的有效性, 首先从理论上给出证明. 为此, 先证明以下3个定理.
定理1 设u s (x ) 为理想阶跃边缘函数, 即
u s (x ) =
A x
(1)
p 为脉冲宽度. 设g(x ) 为偶函数, 若记f (x ) 式中, 2$
=u p (x ) *g(x ) , 则:
(1) f c (x ) 是关于点(x 0, 0) 的偶对称函数; (2) x 0
x |f c (x ) |d x =. Q |f c (x ) |d x
-]+]-]+]
式中, A 、B 为常数. 设g(x ) 为偶函数, 若记f (x ) =u s (x ) *g(x ) , 则:
(1) f c (x ) 是关于点(x 0, 0) 的偶对称函数; x |f c (x ) |d x
(2) x =. |f c (x ) |d x
-]+]]+]
证明 由u c p (x ) =(B -A ) [D (x -x 0+$p ) -D (x -x 0-$p ) ]得:
f c (x ) =u c p (x ) *g(x ) =(B -A ) @ [0+p g(x x 0-p ) ]
第6期
盛遵冰, 等:通用亚像素边缘检测算法
913
x-$r x
(1) 证明f c (x ) 是关于点(x 0, 0) 的奇对称函数,
f c (x 0+x ) +f c (x 0-x ) =
(B -A ) [g (x +$p ) -g(x -$p ) ]+ (B -A ) [g (-x +$) -g(-x -$) ]又
p
p
Q Q
-x+$r -x -x-$-x
r
Q g (B ) d B =-Q
g (B ) d B =-x
g (B ) d B g (B ) d B
x+$
r
将上式代入式(4) , 得
f c (x 0+x ) +f c (x 0-x ) =0
故f c (x ) 是关于点(x 0, 0) 的奇对称函数.
(2) 引入变量X , 令x =X +x 0, 则
g (-x +$p ) =g (x -$p )
g (-x -$p ) =g (x +$p )
故
f c (x 0+x ) +f c (x 0-x ) =0
即f c (x ) 是关于点(x 0, 0) 的奇对称函数.
(2) 引入变量X , 令x =X +x 0, 则
Q
+]-]
x |f c (x ) |d x =
Q
+]-]
x |f c (x ) |d x =x 0
Q
+]-]
|f c (X ) |d X +
Q Q
+]-]+]-]
+]-]
+]-]
X |f c (X +x 0) |d X
由结论(1) 知, f c (x ) 是关于点(x 0, 0) 的奇对称函数, 故|f c (X +x 0) |是X 关于原点(0, 0) 偶对称函数. 因为函数X |f c (X +x 0) |是变量X 关于原点(0, 0) 的奇对称函数, 所以
Q (X +x ) |f c (X +x ) |d X =Q X |f c (X +x ) |d X +x
Q |f c (X +x ) |d X
+]-]+]-]
+]-]0
由结论(1) 可知, |f c (X +x 0) |是以X 为变量关于原点对称的偶函数, 故有
X |f c (X +x 0) |d X =0
+]-]0
x |f c (x ) |d x =x |f c (X ) |d X =Q |f c (x ) |d x Q |f c (x ) |d x
+]-]
Q
x 0证毕
又因为
+]-]
X |f c (X +x 0) |d X =0
Q
所以
+]-]
+]-]
x |f c (x ) |d x =x 0x 0) |d X =x 0
Q
+]-]
|f c (X +
定理3 设u r (x ) 为理想屋脊边缘函数, 即u r (x ) =A
k(x -x 0+$r ) +A -k (x -x 0-$r ) +A A
x
r [x
Q
+]-]
|f c (X ) |d X
x 0[x
(3)
式中:2$r 为边缘宽度; k 为斜率. g(x ) 为偶函数且g(x ) \0. 令f (x ) =u r (x ) *g(x ) , 则:
(1) f c (x ) 是关于点(x 0, 0) 的奇对称函数; (2) x 0=
至此结论(2) 获证.
x |f c (x ) |d x =x |f c (X ) |d X =Q |f c (x ) |d x Q |f c (x ) |d x
+]-]0
+]-]
+]-]
x 0
证毕
由于点扩散函数近似为高斯函数, 满足定理中g(x ) 应为偶函数的要求, 故上述结论可用于在图像中提取边缘的亚像素级位置. 而且在3个定理中, 结论(2) 的表达形式是一致的. 这一点保证了以结论(2) 3.
x 0=
x |f c (x ) |d x . Q |f c (x ) |d x
+]-]+]-]
证明 参照定理1的证明过程, 可得:f c (x ) =k
+]-]
x|f c (x ) |d x
|f c (x ) |d x
+]-]
中,
Q
x-x 0+$r x-x
g (B ) d B +k
Q
x-$x
x-x 0-$r x-x
g(B ) d B
积分区域为整个实数域, 采用数值运算时是无法实现的. 但注意到, 求取x 0的信息取自f (x ) 的一阶导
数. 在无噪声干扰的情况下, 只有在边缘过渡区内|f c (x ) |值才较大, 在远离边缘过渡区|f c (x ) |迅速衰减至非常小的值, 几乎近于零. 故在实际计算时, 只需取某一个边缘过渡区间即可.
其中, B 为哑变量.
(1) 证明f c (x ) 是关于点(x 0, 0) 的奇对称函数,
f c (x 0+x ) +f c (x 0-x ) =
Q k Q
k
x
x+$
r
g (B ) d B +k
r
-x+$-x
Q g (B ) d B +g (B ) d B +k
Q g (B ) d B
r
-x-$-x
r
(4)
2 算法的离散化
, )
914
上 海 交 通 大 学 学 报
第41卷
论(2) 进行离散化处理.
设f i 为f (x ) 在x i 处的采样值, x i 处的微分值利用此处的前向差分和后向差分的均值代替, 记为
i i i+1i-1
f c i ==22
其中:$f i =f i +1-f i ; f i =f i -f i -1. 则
续处理有关, 故在本实验中, 为简化后续处理, 突出算法对边缘点的亚像素级定位能力, 长方形物体均是垂直放置. 为验证此算法对不同边缘的通用性, 每幅图像中均包含不同类型的边缘.
实验1 在无噪声的情况下, 检验算法的定位能力. 具体实验步骤如下.
(5)
|f i+1-f i-1|
(1) 生成一个大小为1280@1280像素的图像, 它包括一个实心矩形(含阶跃边缘) 和一个线框矩阵(含脉冲边缘) , 即图像中同时含有阶跃边缘和脉冲边缘, 取背景灰度值为128, 取前景灰度值为230. 并记录2个矩形的长宽值, 作为理论真值.
(2) 使用二维高斯函数作为点扩散函数与之作卷积运算, 其结果可近似为一个从图像采集系统获取的图像. 其中, 二维高斯函数为
22exp -g(x , y ) =2
2R 2P R
(3) 以8为采样周期对图形进行采样, 得到的大小为160@160像素的图像, 如图2(a) 所示.
(4) 使用本文提出的算法对图2(a) 所示的图形进行边缘检测, 并测量矩形的长、宽值, 记录测量结
果. 检测结果图像如图2(b) 所示.
按照上述实验步骤分别对5幅不含噪图像进行测量, 结果如表
1所示.
由表1可见, 此算法对阶跃型边缘更为有效, 这主要是因为在相同采样率的情况下, 阶跃边缘参与运算的点相对较多. 另外当脉冲型边缘较宽时, 有可能检测出双边缘. 这时需有其他辅助信息以帮助判
x 0U
i =1
E x
i=1
n
i
|f c i |
=
E
i=1
E x
i=1
n
i
|f i+1-f i-1|
|f c i |
E
此算法的具体过程如下:
(1) 计算差分矩阵. 使用行差分模板[-1, 0, 1]
与图像矩阵做卷积运算, 然后将其结果取绝对值, 得到矩阵D 1. 使用列差分模板[-1, 0, 1]T 与图像矩阵做卷积运算, 然后将其结果取绝对值, 得到矩阵D 2.
(2) 根据图像矩阵的统计特性选取差分阈值T. 一般取T =K R , R 为噪声信号的标准差, K 为系数, 在无噪声的情况下K =0.
(3) 选取计算区间. 对矩阵D 、D 中的元素小于T 者, 置0. 矩阵D 1、D 2的非零连续区间即为边
1
2
缘过渡区间.
(4) 利用离散算法式(5) 计算边缘点值.
对离散算法式(5) , 进行一次边缘点计算取n +2个采样值(f 0, f 1, , , f n +1) , 则计算量为n +1次乘除运算和4n -2次加法(减法) 运算. 计算量相对其他算法要小得多.
灰度图像实质是一个二维矩阵, 其单行或单列均可视为一维数组, 故上述算法可以比较容易地推广到二维情况下.
3 实验及结果分析
为验证算法的有效性, 设计2个实验来验证此算法对无噪和含噪图像的亚像素级定位能力. 实验设计为测量多个长方形物体的长和宽. 由于物体的放置角度与边缘点的检测无关, 而只与边缘点的后
图2 图像及边缘检测结果
Fig. 2 T he imag e and result o f edg e detectio n
表1 不同边缘类型长宽真值与测量值对照表
Tab. 1 The true value and measure value about step edge and pulse edge
长@宽真实值/像素
实验编号
阶跃边缘
1234873. 000@530. 000666. 000@424. 000774. 000@456. 000552. 000@385. 000脉冲边缘869. 000@438. 000696. 000@424. 000670. 000@349. 000218. 000@372. 000阶跃边缘873. 000@529. 998665. 999@424. 000773. 999@456. 000552. 000@385. 007脉冲边缘868. 808@438. 037696. 000@424. 000669. 902@348. 431217. 963@371. 849
长@宽测量值/像素
第6期
盛遵冰, 等:通用亚像素边缘检测算法
915
断是脉冲型边缘, 还是阶跃边缘.
由表1还可见, 同样在无噪声影响的情况下, 有的检测结果几乎就是真值, 而有的结果相差太大. 其原因是当理论边缘点恰好被采样, 或恰好位于2个采样点的中间时, 在边缘点的邻域内, 其微分图形的纵剖图(如图1所示) 是关于理论边缘点完全对称的. 故此时检测结果是精确的.
实验2 在加入不同强度的噪声下, 检验算法的定位能力.
为检测此算法对含噪图像的检测效果, 以一幅图像为基准加入不同功率的高斯白噪声, 然后使用此算法检测. 具体实验步骤和实验1类似. 为避免线框矩形边缘不被噪声淹没, 信噪比(SNR) 分别取值为50, 60, 70, 80, 90dB. 其检测结果如表2所示.
表2 不同信噪比下的检测结果
Tab. 2 The results of edge detection with dif ferent SNR
长@宽/像素
SNR/dB 5060708090
阶跃边缘873. 029@529. 964873. 007@529. 982872. 999@529. 997872. 999@529. 999973. 001@529. 999
脉冲边缘868. 459@437. 406868. 711@437. 989868. 810@438. 015869. 268@438. 077869. 281@438. 071
情况下的检测能力. 即使在有较强噪声干扰的情况下, 此算法对同一幅图像中的不同边缘类型也能很好地完成亚像素级定位. 此算法的另一优点是不需预先进行像素级边缘检测, 即可直接进行亚像素级边缘检测. 参考文献:
[1] T abat abai A J, M itchell O , Ro ber t. Edg e locatio n to
subpixel values in digit al imag ery [J]. IEEE Transac -tions on Pattern Analysis and M achine Intelligence , 1984, PA M I -6(2) :188-201.
[2] 刘力双, 张 铫, 卢慧卿, 等. 图像的快速亚像素边缘
检测方法[J].光电子#激光, 2005, 16(8) :993-996. LIU L-i shuang , ZH A NG Y ao, LU H u-i qing , et al. A fast subpixel edge det ection metho d for images [J ].Journal of Optoelectronics #Laser, 2005, 16(8) :993-996.
[3] T ruchet et F , La lig ant O. Subpix le edg e detection for
dimensional co nt ro l by art ificial visio n[J]. Journal of Electronic Imaging , 2001, 10(1) :234-239.
[4] 于新瑞, 汪国宝, 王石刚, 等. 基于边缘导向的直边图
亚像素定位方法[J]. 上海交通大学学报, 2005, 39(8) :866-869.
YU Xin -r ui, WA N G Guo -bao, W A NG Sh-i g ang , et al . A n edge -directed subpix el localizatio n method o f st raig ht edg e imag e[J].Journal of Shanghai Jiaotong Unviersity , 2005, 39(8) :866-869.
[5] 丁兴号, 邓善熙. 基于小波变换的屋脊边缘亚像素检
测[J]. 哈尔滨工业大学学报, 2004, 36(11) :1480-1482.
DIN G Xing -hao, DEN G Shan -x i. Sub -pixel ro of edg e detectio n based o n wavelet tr ansfo rm [J]. Journal of Harbin Institute of Technology, 2004, 36(11) :1480-1482.
[6] Qu Y ing -dong, Cui Cheng -song, Chen San -ben, et al .
A fast subpixel edg e detectio n metho d using So be-l Zernike moments o per ator [J].Image and Vision C om -puting , 2005, 23(1) :11-17.
由表2可见, 算法对阶跃边缘的检测能力要远远好于脉冲边缘和屋脊边缘. 这主要是由于后两者
本身有效点较少, 在噪声较强时, 容易被淹没.
另外, 由于此图的背景灰度值为128, 前景灰度值为230. 信号本身的功率较大, 在同样信噪比的情况下, 噪声的功率也较大, 即噪声的幅值较大. 若通过灰度变换, 加宽图像的灰度范围, 即减低背景灰度值, 同时提高前景灰度值, 可以在图像的信噪比较低的情况下, 也能很好地完成检测定位.
4 结 语
本文证明了此通用亚像素级边缘检测算法不存在原理性误差. 通过实验验证了算法在无噪和有噪
上海交通大学学报
国家期刊奖百种重点期刊 中国高校精品科技期刊
欢迎投稿
欢迎订阅
第41卷第6期 2007年6月
上海交通大学学报
JOU RN AL O F SH AN G HA I JIA OT O N G U N IV ERSIT Y
Vol. 41No. 6 Jun. 2007
文章编号:1006-2467(2007) 06-0911-05
通用亚像素边缘检测算法
盛遵冰, 崔贤玉, 高国安
(哈尔滨工业大学机电工程学院, 哈尔滨150001)
摘 要:研究了针对不同边缘类型进行同步亚像素级检测的问题. 通过详细分析3种基本边缘类型(阶跃型边缘、脉冲型边缘、屋脊型边缘) 的特点, 提出了一种基于形体质心思想的通用算法, 并对
其进行了严格证明. 该算法能同时对这3种基本类型边缘进行亚像素级检测与定位, 且不存在原理性误差. 对算法进行离散化处理, 给出了便于计算机实现的离散算法. 通过实验验证了此算法的有效性, 并分析了误差产生的原因.
关键词:亚像素边缘检测; 算法; 图形质心中图分类号:TN 911. 73 文献标识码:A
A Universal Algorithm for Subpixel Edge Detection
SH EN G Zun -bing , CUI X ian -y u, GA O Guo -an
(Schoo l of M echatr onics Eng. , H ar bin Inst. of Technolog y, H arbin 150001, China)
Abstract:T he pr oblem for detecting all types of edge w ith a sam e m ethod at subpix el lev el w as r esearched. A novelty universal algorithm for subpix el edg e detectio n based on figure centr oid w as propo sed by analy -zing the character istics of three basic types of edge(step edg e, pulse edge, ro of edge). It can pr ocess all ty pes of edg e at one time. T he algo rithm w as demo nstrated, and it w as illuminated no erro r theoretically. Afterw ard discrete fo rm of the algor ithm w as deduced fo r calculating on computer. Finally , validity of the algorithm w as testified by prelim inary ex periments in noise and no noise situation, and the reason of mak -ing error w as analyzed.
Key words:subpixel edge detection; alg orithm ; figure centroid
随着机器视觉技术在检测和测量中广泛深入的应用, 人们期望能从现有图像信息中获取物体更为
精确的尺寸和位置信息. 为此, 针对不同应用人们提出了许多亚像素级边缘检测算法. 基于矩保持的亚像素边缘检测算法是T abatabai 等[1]于1984年提出的一种具有代表性的算法, 它的基本思想是保持理想图像和实际图像的多阶矩相等, 以此来计算边缘的亚像素级位置. 由于需要计算多阶矩, 涉及到多次方运算, 运算量较大, 并且对噪声的抑制能力较
收稿日期:2006-07-16
弱. 另外, 各种基于拟合思想的亚像素边缘检测算法, 由于需要拟合多项式, 求解矩阵方程, 计算量
也相对较大, 且对不同边缘类型不具有通用性. 其他的算法, 如基于变换域(如小波变换) 的亚像素边缘检测算法[5]、基于Zernike 矩的亚像素边缘检测算法[6]等, 也存在着这些问题. 现有算法的缺点之一是不能对同一幅图像中的不同边缘类型进行有效检测, 即这些算法不具有良好的通用性.
本文提出一种基于形体质心思想的通用算法.
[2-4]
作者简介:盛遵冰(1977-) , 男, 山东鱼台人, 博士生, 从事基于机器视觉的精密检测测量技术的研究, E -mail:shengzb@hit. edu. cn.
高国安(联系人) , 男, 教授, 博士生导师, 电话(T el. ) :0451-86416778; E -mail:guoan @hit. edu. cn.
912
上 海 交 通 大 学 学 报
第41卷
对阶跃型边缘、脉冲型边缘、屋脊型边缘3种基本类型边缘的特点进行详细分析后发现, 这3种基本边缘类型的一阶导数是关于边缘点的对称函数, 它们的绝对值则是一个关于边缘点的偶对称函数. 而从图形的角度考虑, 此对称点恰是图形的质心. 因此亚像素级边缘检测问题就可以转化为求解图形质心问题.
又
证明 因为f (x ) =u s (x ) *g(x ) , 所以
f c (x ) =u c s (x ) *g (x ) u c s (x ) =(B -A ) D (x -x 0)
故
f c (x ) =(B -A ) g(x -x 0)
其中, D (x ) 为单位脉冲函数.
(1) 证明f c (x ) 是关于点(x 0, 0) 的偶对称函数, f c (x 0+x ) -f c (x 0-x ) =(B -A ) g(x ) -(B -A ) g(-x )
由g(-x ) =g(x ) , 得f c (x 0+x ) -f c (x 0-x ) =0, 即f c (x ) 是关于点(x 0, 0) 的偶对称函数.
(2) 引入变量X , 令x =X +x 0, 则
1 算法的理论基础及证明
理论上, 一般认为图像是原始理想信息在点扩散函数的卷积作用下形成的. 在不考虑噪声影响的
情况下, 其一维数学模型简单表示为
f (x ) =u(x ) *g(x )
其中:u(x ) 为原始理想信号; f (x ) 为一维图像信息; g(x ) 为点扩散函数, 一般近似为高斯函数,
g(x ) =
2
ex p -22R 2PR
Q
+]-]
x |f c (x ) |dx =
Q
+]-]
(X +x 0) |f c (X +x 0) |d X =
+]-]
若u(x ) 分别取为理想阶跃边缘u s (x ) 、理想脉
冲边缘u p (x ) 、理想屋脊边缘u r (x ) , 则经点扩散函数作用后, 尖锐的理想边缘被平滑成模糊边缘. 点扩
散函数的平滑作用将不可微函数(理想信号) 变成了一个可微函数. 上述3个可微函数的一阶导数图形(见图1) 是关于某点对称的. 此对称点即为所寻求的边缘点x 0.
因为g(x ) 为偶函数, 所以
Q |g(X ) |d X +
|B -A |
Q X |g (X ) |d X
|B -A |x 0
+]-]
Q
故
+]-]+]-]
+]-]
X |g(X ) |d X =0
x |f c (x ) |d x =
Q |f c (x ) |d x
x |B -A ||g(X ) |d X
=
|B -A |
|g(x ) |d x
+]-]
+]-]
x 0
证毕
图1 3种基本类型边缘的微分图形
Fig. 1 T he differentials of three basic types of edg e
定理2 设u p (x ) 为理想脉冲边缘函数, 即
A
u p (x ) =
B A
x
x 0-$p [x
x \x 0+$p
(2)
为了说明算法的有效性, 首先从理论上给出证明. 为此, 先证明以下3个定理.
定理1 设u s (x ) 为理想阶跃边缘函数, 即
u s (x ) =
A x
(1)
p 为脉冲宽度. 设g(x ) 为偶函数, 若记f (x ) 式中, 2$
=u p (x ) *g(x ) , 则:
(1) f c (x ) 是关于点(x 0, 0) 的偶对称函数; (2) x 0
x |f c (x ) |d x =. Q |f c (x ) |d x
-]+]-]+]
式中, A 、B 为常数. 设g(x ) 为偶函数, 若记f (x ) =u s (x ) *g(x ) , 则:
(1) f c (x ) 是关于点(x 0, 0) 的偶对称函数; x |f c (x ) |d x
(2) x =. |f c (x ) |d x
-]+]]+]
证明 由u c p (x ) =(B -A ) [D (x -x 0+$p ) -D (x -x 0-$p ) ]得:
f c (x ) =u c p (x ) *g(x ) =(B -A ) @ [0+p g(x x 0-p ) ]
第6期
盛遵冰, 等:通用亚像素边缘检测算法
913
x-$r x
(1) 证明f c (x ) 是关于点(x 0, 0) 的奇对称函数,
f c (x 0+x ) +f c (x 0-x ) =
(B -A ) [g (x +$p ) -g(x -$p ) ]+ (B -A ) [g (-x +$) -g(-x -$) ]又
p
p
Q Q
-x+$r -x -x-$-x
r
Q g (B ) d B =-Q
g (B ) d B =-x
g (B ) d B g (B ) d B
x+$
r
将上式代入式(4) , 得
f c (x 0+x ) +f c (x 0-x ) =0
故f c (x ) 是关于点(x 0, 0) 的奇对称函数.
(2) 引入变量X , 令x =X +x 0, 则
g (-x +$p ) =g (x -$p )
g (-x -$p ) =g (x +$p )
故
f c (x 0+x ) +f c (x 0-x ) =0
即f c (x ) 是关于点(x 0, 0) 的奇对称函数.
(2) 引入变量X , 令x =X +x 0, 则
Q
+]-]
x |f c (x ) |d x =
Q
+]-]
x |f c (x ) |d x =x 0
Q
+]-]
|f c (X ) |d X +
Q Q
+]-]+]-]
+]-]
+]-]
X |f c (X +x 0) |d X
由结论(1) 知, f c (x ) 是关于点(x 0, 0) 的奇对称函数, 故|f c (X +x 0) |是X 关于原点(0, 0) 偶对称函数. 因为函数X |f c (X +x 0) |是变量X 关于原点(0, 0) 的奇对称函数, 所以
Q (X +x ) |f c (X +x ) |d X =Q X |f c (X +x ) |d X +x
Q |f c (X +x ) |d X
+]-]+]-]
+]-]0
由结论(1) 可知, |f c (X +x 0) |是以X 为变量关于原点对称的偶函数, 故有
X |f c (X +x 0) |d X =0
+]-]0
x |f c (x ) |d x =x |f c (X ) |d X =Q |f c (x ) |d x Q |f c (x ) |d x
+]-]
Q
x 0证毕
又因为
+]-]
X |f c (X +x 0) |d X =0
Q
所以
+]-]
+]-]
x |f c (x ) |d x =x 0x 0) |d X =x 0
Q
+]-]
|f c (X +
定理3 设u r (x ) 为理想屋脊边缘函数, 即u r (x ) =A
k(x -x 0+$r ) +A -k (x -x 0-$r ) +A A
x
r [x
Q
+]-]
|f c (X ) |d X
x 0[x
(3)
式中:2$r 为边缘宽度; k 为斜率. g(x ) 为偶函数且g(x ) \0. 令f (x ) =u r (x ) *g(x ) , 则:
(1) f c (x ) 是关于点(x 0, 0) 的奇对称函数; (2) x 0=
至此结论(2) 获证.
x |f c (x ) |d x =x |f c (X ) |d X =Q |f c (x ) |d x Q |f c (x ) |d x
+]-]0
+]-]
+]-]
x 0
证毕
由于点扩散函数近似为高斯函数, 满足定理中g(x ) 应为偶函数的要求, 故上述结论可用于在图像中提取边缘的亚像素级位置. 而且在3个定理中, 结论(2) 的表达形式是一致的. 这一点保证了以结论(2) 3.
x 0=
x |f c (x ) |d x . Q |f c (x ) |d x
+]-]+]-]
证明 参照定理1的证明过程, 可得:f c (x ) =k
+]-]
x|f c (x ) |d x
|f c (x ) |d x
+]-]
中,
Q
x-x 0+$r x-x
g (B ) d B +k
Q
x-$x
x-x 0-$r x-x
g(B ) d B
积分区域为整个实数域, 采用数值运算时是无法实现的. 但注意到, 求取x 0的信息取自f (x ) 的一阶导
数. 在无噪声干扰的情况下, 只有在边缘过渡区内|f c (x ) |值才较大, 在远离边缘过渡区|f c (x ) |迅速衰减至非常小的值, 几乎近于零. 故在实际计算时, 只需取某一个边缘过渡区间即可.
其中, B 为哑变量.
(1) 证明f c (x ) 是关于点(x 0, 0) 的奇对称函数,
f c (x 0+x ) +f c (x 0-x ) =
Q k Q
k
x
x+$
r
g (B ) d B +k
r
-x+$-x
Q g (B ) d B +g (B ) d B +k
Q g (B ) d B
r
-x-$-x
r
(4)
2 算法的离散化
, )
914
上 海 交 通 大 学 学 报
第41卷
论(2) 进行离散化处理.
设f i 为f (x ) 在x i 处的采样值, x i 处的微分值利用此处的前向差分和后向差分的均值代替, 记为
i i i+1i-1
f c i ==22
其中:$f i =f i +1-f i ; f i =f i -f i -1. 则
续处理有关, 故在本实验中, 为简化后续处理, 突出算法对边缘点的亚像素级定位能力, 长方形物体均是垂直放置. 为验证此算法对不同边缘的通用性, 每幅图像中均包含不同类型的边缘.
实验1 在无噪声的情况下, 检验算法的定位能力. 具体实验步骤如下.
(5)
|f i+1-f i-1|
(1) 生成一个大小为1280@1280像素的图像, 它包括一个实心矩形(含阶跃边缘) 和一个线框矩阵(含脉冲边缘) , 即图像中同时含有阶跃边缘和脉冲边缘, 取背景灰度值为128, 取前景灰度值为230. 并记录2个矩形的长宽值, 作为理论真值.
(2) 使用二维高斯函数作为点扩散函数与之作卷积运算, 其结果可近似为一个从图像采集系统获取的图像. 其中, 二维高斯函数为
22exp -g(x , y ) =2
2R 2P R
(3) 以8为采样周期对图形进行采样, 得到的大小为160@160像素的图像, 如图2(a) 所示.
(4) 使用本文提出的算法对图2(a) 所示的图形进行边缘检测, 并测量矩形的长、宽值, 记录测量结
果. 检测结果图像如图2(b) 所示.
按照上述实验步骤分别对5幅不含噪图像进行测量, 结果如表
1所示.
由表1可见, 此算法对阶跃型边缘更为有效, 这主要是因为在相同采样率的情况下, 阶跃边缘参与运算的点相对较多. 另外当脉冲型边缘较宽时, 有可能检测出双边缘. 这时需有其他辅助信息以帮助判
x 0U
i =1
E x
i=1
n
i
|f c i |
=
E
i=1
E x
i=1
n
i
|f i+1-f i-1|
|f c i |
E
此算法的具体过程如下:
(1) 计算差分矩阵. 使用行差分模板[-1, 0, 1]
与图像矩阵做卷积运算, 然后将其结果取绝对值, 得到矩阵D 1. 使用列差分模板[-1, 0, 1]T 与图像矩阵做卷积运算, 然后将其结果取绝对值, 得到矩阵D 2.
(2) 根据图像矩阵的统计特性选取差分阈值T. 一般取T =K R , R 为噪声信号的标准差, K 为系数, 在无噪声的情况下K =0.
(3) 选取计算区间. 对矩阵D 、D 中的元素小于T 者, 置0. 矩阵D 1、D 2的非零连续区间即为边
1
2
缘过渡区间.
(4) 利用离散算法式(5) 计算边缘点值.
对离散算法式(5) , 进行一次边缘点计算取n +2个采样值(f 0, f 1, , , f n +1) , 则计算量为n +1次乘除运算和4n -2次加法(减法) 运算. 计算量相对其他算法要小得多.
灰度图像实质是一个二维矩阵, 其单行或单列均可视为一维数组, 故上述算法可以比较容易地推广到二维情况下.
3 实验及结果分析
为验证算法的有效性, 设计2个实验来验证此算法对无噪和含噪图像的亚像素级定位能力. 实验设计为测量多个长方形物体的长和宽. 由于物体的放置角度与边缘点的检测无关, 而只与边缘点的后
图2 图像及边缘检测结果
Fig. 2 T he imag e and result o f edg e detectio n
表1 不同边缘类型长宽真值与测量值对照表
Tab. 1 The true value and measure value about step edge and pulse edge
长@宽真实值/像素
实验编号
阶跃边缘
1234873. 000@530. 000666. 000@424. 000774. 000@456. 000552. 000@385. 000脉冲边缘869. 000@438. 000696. 000@424. 000670. 000@349. 000218. 000@372. 000阶跃边缘873. 000@529. 998665. 999@424. 000773. 999@456. 000552. 000@385. 007脉冲边缘868. 808@438. 037696. 000@424. 000669. 902@348. 431217. 963@371. 849
长@宽测量值/像素
第6期
盛遵冰, 等:通用亚像素边缘检测算法
915
断是脉冲型边缘, 还是阶跃边缘.
由表1还可见, 同样在无噪声影响的情况下, 有的检测结果几乎就是真值, 而有的结果相差太大. 其原因是当理论边缘点恰好被采样, 或恰好位于2个采样点的中间时, 在边缘点的邻域内, 其微分图形的纵剖图(如图1所示) 是关于理论边缘点完全对称的. 故此时检测结果是精确的.
实验2 在加入不同强度的噪声下, 检验算法的定位能力.
为检测此算法对含噪图像的检测效果, 以一幅图像为基准加入不同功率的高斯白噪声, 然后使用此算法检测. 具体实验步骤和实验1类似. 为避免线框矩形边缘不被噪声淹没, 信噪比(SNR) 分别取值为50, 60, 70, 80, 90dB. 其检测结果如表2所示.
表2 不同信噪比下的检测结果
Tab. 2 The results of edge detection with dif ferent SNR
长@宽/像素
SNR/dB 5060708090
阶跃边缘873. 029@529. 964873. 007@529. 982872. 999@529. 997872. 999@529. 999973. 001@529. 999
脉冲边缘868. 459@437. 406868. 711@437. 989868. 810@438. 015869. 268@438. 077869. 281@438. 071
情况下的检测能力. 即使在有较强噪声干扰的情况下, 此算法对同一幅图像中的不同边缘类型也能很好地完成亚像素级定位. 此算法的另一优点是不需预先进行像素级边缘检测, 即可直接进行亚像素级边缘检测. 参考文献:
[1] T abat abai A J, M itchell O , Ro ber t. Edg e locatio n to
subpixel values in digit al imag ery [J]. IEEE Transac -tions on Pattern Analysis and M achine Intelligence , 1984, PA M I -6(2) :188-201.
[2] 刘力双, 张 铫, 卢慧卿, 等. 图像的快速亚像素边缘
检测方法[J].光电子#激光, 2005, 16(8) :993-996. LIU L-i shuang , ZH A NG Y ao, LU H u-i qing , et al. A fast subpixel edge det ection metho d for images [J ].Journal of Optoelectronics #Laser, 2005, 16(8) :993-996.
[3] T ruchet et F , La lig ant O. Subpix le edg e detection for
dimensional co nt ro l by art ificial visio n[J]. Journal of Electronic Imaging , 2001, 10(1) :234-239.
[4] 于新瑞, 汪国宝, 王石刚, 等. 基于边缘导向的直边图
亚像素定位方法[J]. 上海交通大学学报, 2005, 39(8) :866-869.
YU Xin -r ui, WA N G Guo -bao, W A NG Sh-i g ang , et al . A n edge -directed subpix el localizatio n method o f st raig ht edg e imag e[J].Journal of Shanghai Jiaotong Unviersity , 2005, 39(8) :866-869.
[5] 丁兴号, 邓善熙. 基于小波变换的屋脊边缘亚像素检
测[J]. 哈尔滨工业大学学报, 2004, 36(11) :1480-1482.
DIN G Xing -hao, DEN G Shan -x i. Sub -pixel ro of edg e detectio n based o n wavelet tr ansfo rm [J]. Journal of Harbin Institute of Technology, 2004, 36(11) :1480-1482.
[6] Qu Y ing -dong, Cui Cheng -song, Chen San -ben, et al .
A fast subpixel edg e detectio n metho d using So be-l Zernike moments o per ator [J].Image and Vision C om -puting , 2005, 23(1) :11-17.
由表2可见, 算法对阶跃边缘的检测能力要远远好于脉冲边缘和屋脊边缘. 这主要是由于后两者
本身有效点较少, 在噪声较强时, 容易被淹没.
另外, 由于此图的背景灰度值为128, 前景灰度值为230. 信号本身的功率较大, 在同样信噪比的情况下, 噪声的功率也较大, 即噪声的幅值较大. 若通过灰度变换, 加宽图像的灰度范围, 即减低背景灰度值, 同时提高前景灰度值, 可以在图像的信噪比较低的情况下, 也能很好地完成检测定位.
4 结 语
本文证明了此通用亚像素级边缘检测算法不存在原理性误差. 通过实验验证了算法在无噪和有噪
上海交通大学学报
国家期刊奖百种重点期刊 中国高校精品科技期刊
欢迎投稿
欢迎订阅