快速多项式拟合亚像素边缘检测算法的研究_陈静

第32卷第1期应用光学V o l. 32N o. 1

　　　　　　　　　　　　　　　　　　　　　　　　　　　

2011年1月Jo urnal of A pplied Optics Jan. 2011文章编号:1002-2082(2011) 01-0091-05

快速多项式拟合亚像素边缘检测算法的研究

陈　静, 尚雅层, 田军委

(西安工业大学机电工程学院, 陕西西安710032)

摘　要:传统的亚像素边缘检测都是先粗定位, 再进行亚像素细分, 因而运行时间较长。采用了一种基于多项式拟合的快速亚像素边缘检测算法。该算法根据图像的灰度分布, 运用三次多项式拟合图像的边缘实现亚像素定位, 从而达到较高的定位精度。采用在边缘附近取点, 进行亚像素边缘检测, 减少了运行时间。仿真实验给出的实验结果证明了该算法的有效性。关键词:图像处理; 亚像素; 边缘检测; 多项式拟合

中图分类号:T P 391. 41　　　　　　文献标志码:A

Fast polynomial fits sub -pixel edge detection algorithms

CHEN Jing , SHANG Ya-ceng , T IAN Jun-w ei

(Department o f M echanical Eng ineering , X i ’an T echno lo gical U niv ersit y , Xi ’an 710032, China )

Abstract :Since traditional edge detectio n alg orithm s have the disadvantag es of low precision and efficiency in measuring the edge, a sub-pixel edge detectio n alg orithm based o n the polynom ial fitting s is pro posed. According to the g rey lev el distr ibutio n of the picture, this alg orithm uses cubic po lynomial to fit the edges to r ealize sub -pix el lo calization . Traditional sub -pix el edg e detection algo rithms detect coarse po sition at fir st , and then car ry o ut the sub -divide , therefo re the r unning tim e is relativ ely long. This metho d first fetches so me po ints near the edge, and then carries out the sub-pixel edg e detection algo rithm , so the running time is reduced. Finally,

the ex perimental results show that the pro po sed algorithm is v ery reliable and efficient . Key words :image processing ; sub-pix el; edg e detection; polynom ial fitting

引言

在图像中, 边缘、线和点携带着区域的许多信息, 理想的边缘检测需要精确地检测出图像中的边缘点, 存在的边缘点不应该被漏掉, 不存在的边缘点不应该被错检出来。图像测量时, 大量的信息都是由轮廓边缘提供的, 因此边缘提取与检测在图像处理中占有很重要的地位, 其检测算法的优劣直接影响到整个检测系统的性能。

边缘检测的实质是通过一些算法来提取图像中灰度不连续的边缘像素。早期传统的边缘检测方法不少[1-3], 常用的有Sobel , Ro bert , Prew itt , 拉普

拉斯算子等等, 这些算子又各有优缺点。Roberts

算子虽然简单直观, 对具有陡峭的低噪声图像的响应最好, 但是边缘检测图里有伪边缘; Sobel 算子和Prewitt 算子能检测更多的边缘, 但也存在伪边缘且检测出来的边缘线比较粗, 并放大了噪声; 拉普拉斯算子虽然可以检测出比较多的边缘, 在很大程度上消除了伪边缘的存在, 定位精度比较高, 但是受噪声的影响比较大, 且会丢失一些边缘。传统边缘检测算法的定位精度只能达到像素的整数级, 已经不能够满足实际的需要了, 在此基础上就有不少人提出了亚像素边缘检测

[4-7]

, 它们也是各有优

收稿日期:2010-05-06; 　修回日期:2010-05-28

项目基金:西安工业大学校长基金(XA G DXJJ 0904)

收稿日期:陈静(1986-) , 女, 江苏扬州人, 西安工业大学硕士研究生, 主要从事数字图像处理及计算机数控技术研究。E -:

・92・

应用光学　2011, 32(1) 　陈　静, 等:快速多项式拟合亚像素边缘检测算法的研究

缺点, 本文则是采用三次多项式拟合法来达到亚像素定位。

型中的未知参数; 若为矩保持法, 则根据矩的求解方法来解;

4) 求解

根据各自的特点来求解亚像素边缘位置坐标。上述即为现有亚像素边缘检测算法的一般步骤。现有亚像素边缘检测算法大都是采用传统的边缘检测算子进行粗定位, 而传统边缘检测算子在程序中使用指针进行处理, 会花费大量的时间, 从而使得程序的运行时间较长, 降低了边缘检测的效率。

1. 3　常用亚像素边缘检测算法的优缺点

上述3种类型的亚像素边缘检测各有优缺点, 如表1所示。

表1　3种亚像素定位算法的优缺点

Table 1　Advantages and disadvantages of t hree kinds

of sub -pixel edge detection algorithms

基于插值的亚像素定位算法

优点

重复性好, 计算量小, 计算时间相对较短, 抗噪声能力强

缺点

定位精度低

抗干扰和检测出复杂边缘之间存在一定的矛盾

基于拟合的亚像基于矩保持的亚像素定位算法素定位算法抗干扰性强, 检测出的边缘点位置较准确

亚像素边缘位置不受图像平移或尺寸变化的影响计算时间较长

1　常用亚像素边缘检测算法

1. 1　常用亚像素边缘检测算法的思想

目前国内外研究的亚像素边缘检测理论与技术, 在数学上可以归纳为三种类型:

1) 基于插值的亚像素边缘检测算法

这种方法的原理是对像素点的灰度值或灰度值的导数进行插值, 增加信息, 以实现亚像素边缘检测。

这里可以按插值方式的不同分为一次插值、二次插值和样条插值等。

2) 基于拟合的亚像素边缘检测算法

其基本思想是由于边缘函数在边缘附近是渐变的, 在此情况下用低阶多项式拟合边缘函数在精度上一般是可以接受的。

常见的有拉格朗日多项式拟合与Cheby shev 多项式拟合。

3) 基于矩保持的亚像素边缘检测算法其核心是根据一个物体的矩特性在成像前后保持不变的原理, 将矩方法应用于圆、椭圆和矩形等中心对称目标以及边缘和角点等目标的亚像素定位中。利用像素点的灰度值和包含边缘位置的灰度分布模型计算各种统计量进行亚像素边缘检测, 如灰度矩、空间矩、质心值和局部能量值等。

常见的有灰度矩法、空间矩法、zernike 正交矩法。

1. 2　常用亚像素边缘检测算法的基本步骤

通过分析, 将这三种亚像素边缘检测的步骤可以概括总结为:

1) 粗定位

用传统的边缘检测算子(如Sobel 算子、Ro bert 算子等) 对边缘进行粗定位;

2) 取点

用边缘的二阶导数值为零这一特点, 在边缘点两侧的某一小邻域内取点(一般为3～4个点, 若点过多通常会导致定位不准确) ;

3) 用相应公式代入

若为插值法, 则利用这几个点的梯度值进行插值计算, 求解插值基函数中的未知参数; 若为拟合法

, 2　三次多项式拟合亚像素定位算法

本课题所做的亚像素边缘检测是对刀具的图像进行处理, 没有复杂形状的边缘, 鉴于上述三种算法的优缺点, 本文选用基于拟合的亚像素边缘检测算法。

一般被摄图像是经过摄像系统采集而得到实际图像, 如图1所示, 而摄像系统是有一定频率带宽限制的, 其作用相当于一个低通滤波器, 即相当于被摄图像经过一个低通滤波器后得到实际的图像。由于光学元器件的卷积作用和光学衍射作用以及光学系统的相差, 导致在物空间是巨变的灰度值经过光学成像成为渐变的形式, 如图2所示。

图1　传统图像的采集

Fig . 1　Collection of traditional image

对于M ×N 的图像, 假设理想边缘模型函数为) ) u )

应用光学　2011, 31(1) 　陈　静, 等:快速多项式拟合亚像素边缘检测算法的研究

・93・

像边缘的对比度。

由于摄像系统类似于一个低通滤波器, 可以用点扩展函数等效表示, 点扩展函数为如下多项式:

2

h (x ) =1-(a ) , ûx û≤a , a >0则实际图像的边缘模型为f (x ) =y (x ) *h (x )

(1) (

2)

程度。要使回归直线与全部测量值最接近, 要求二者的偏离程度最小。根据极值条件有

=0, =0, =0, =0, 求出, , , , 再

a b c d 根据=0时点的坐标得出亚像素点的坐标。即

5x

根据极值条件可以解得

a =

i ×j -k ×1b =h -j

X Y -Y ・X X 4-X ・X 3c =-×

X 2-X X 2-X

n n X 3-X ・X 2

　a -×b X 2-X n d =其中:

e =(X 2-n X ) (X 3Y -n Y ・X ) -(X 4-n X ・

X 3) (X Y -・X ) ;

n f =(X 2-n X ) (X 4-n X 2) -(X 3-n X ・X 2)

(X 3-Y ・X 2) ;

n g =(X 2-n X ) (X 5-n X 2・X 3) -(X 4-n X ・

X 3) (X 3-X ・X 2) ;

n h =(X 2-n X ) (X 2Y -n Y ・X 2) -(X 3-n X ・

X 2) (X Y -Y ・X ) ;

n i =(X 2-n X ) (X 6-n X 3) -(X 4-n X ・X 3)

(X 4-X ・X 3) ;

n j =(X 2-n X ) (X 4-n X 2) -(X 3-n X ・X 2)

(X 3-・X 2) ;

n k =(X 2-n X ) (X 5-n X 2・X 3) -(X 4-n X ・

X 3) (X 3-n X ・X 2) ;

l =(X 2-n X ) (X 5-n X 3・X 2) -(X 3-n X ・

(Y -a ×X 3-b ×X 2-c ×X ) n

2

图2　理想的和实际的边缘Fig . 2　Ideal edge and real edge

上述点扩展函数(1) 式为二次多项式, 由(2) 式可知, 边缘的灰度分布为三次解析曲线, 因此可以用三次多项式来拟合边缘的灰度值, 取其拐点为边缘位置。

在拟合之前, 首先在待求的边缘附近取一个点, 这个点不要求严格的在待求边缘上, 如图3

所示。

图3　三次多项式拟合过程示意图

Fig . 3　Sketch image of the course of the cubic

polynomial f itting

接着在过这个点的某一个方向选取一系列的点, 这些点过待求边缘, 求得这些点的灰度值, 并绘制灰度曲线图。

然后根据灰度分布函数的特征, 利用三次多项式函数对灰度分布作最小二乘拟合, 并根据拟合出的曲线来确定灰度分布边缘点的位置。

假设采用的三次多项式的形式为f (x ) =

d =f (x ) , 全部测量值ax 3+bx 2+cx +d , 并且假设y 与回归直线的偏离平方和记为S , 则

d i ) 2=S =∑(y i -y

i =1n

n

∑[y

i =1

i

3

-(ax 3i +bx i +

cx i +d ) ]2(i =1, 2, …, n )

(3)

・94・

n

应用光学　2011, 32(1) 　陈　静, 等:快速多项式拟合亚像素边缘检测算法的研究

n

n

2i

3

∑x i ; i =16i

记X =

n

∑x i ; X 2=

i =1

n

4i

∑x ; X 3=

i =1

n

5i

合时拟合出的曲线与灰度曲线不能很好地重合, 但这并不能说明这些点的拟合是不准确的, 因为我们是用三次曲线来拟合的, 取这些点时灰度曲线不是三次曲线了, 因而不能很好地拟合。现在需要的是边缘位置点, 也就是图中的直线位置, 其结果还是拟合得很好的, 符合要求。

本文采用精度更高的五次多项式对同一位置进行亚像素边缘检测, 得到的亚像素位置为786. 9335, 将我们实验得出的数据与其进行比较得到的拟合误差, 如表2所示。根据表2中的拟合误差可以看出取8个点时的拟合效果最佳。

表2　拟合出的亚像素位置Table 2　Fitting of sub -pixel position

点的个数5个点

6个点7个点8个点9个点10个点11个点

亚像素位置值787. 2640786. 2423787. 5001786. 9185787. 0811787. 3148787. 4651

拟合误差0. 33050. 69120. 56660. 0750. 14760. 38130. 5316

X 4=

n

∑x ;

i =1

X 5=

n

i i

∑x ;

i =1

X 6=

n

∑x ;

i =12i

Y =

∑y ;

i

i =1n

3i

i

i =1

X Y =

∑x y ;

i =1

X 2Y =

∑x

i =1

y i ; X 3Y =

∑x y 。

从而解得亚像素点坐标为-。3a

3　三次多项式拟合算法的实现

用C#语言在VS2005平台上编写程序实现三次多项式拟合的亚像素边缘检测, 分别取11个点、10个点、9个点、8个点、7个点、6个点、5个点进行拟合, 拟合的结果如图5所示, 其中带黑点的曲线为灰度曲线, 黑点即为检测到的点, 另一条曲线即为拟合后的曲线,

直线为检测后的亚像素位置。

4　实验结果分析

对于一幅2592×1944的图像, 对其边缘点采用三次多项式拟合的亚像素边缘检测算法进行定位, 得到定位时间, 通过多次实验求其平均值, 其运行时间如表3所示。

表3　三次多项式拟合运行时间

Table 3　Running time of cubic polynomial f ittings 运行次数

12345

运行时间/m s 59. 619959. 427759. 759359. 804058. 9525

运行次数

678910

运行时间/ms 60. 219759. 954359. 344459. 274360. 0194

　　将表3中运行10次得到的运行时间求平均值, 得到运行时间为

t =59. 63755m s

同一幅图像, 对其中的边缘点分别采用基于二次插值多项式的亚像素边缘检测、基于LOG 算子

图4　三次多项式拟合曲线图

Fig . 4　Image of the fitting curves by the

cubic polynomial

的亚像素边缘检测以及三次多项式拟合亚像素边缘检测, 其运行时间对比情况如表4所示。由表4可知三种亚像素边缘检测算法中三次多项式拟合亚像素边缘检测算法的运行时间显著缩短, 效率由图4可知, 分别取8、9个点进行拟合时都能,

应用光学　2011, 31(1) 　陈　静, 等:快速多项式拟合亚像素边缘检测算法的研究

表4　三种亚像素算法运行时间对比

Table 4　C ontrast of running time of three kinds of sub -pixel edge detection algorithms

亚像素算法时间/ms

基于二次插值基于L OG 算三次多项式多项式的亚像子的亚像素拟合的亚像素边缘检测边缘检测素边缘检测81. 1562

145. 6379

59. 6376

・95・

比较分析[J ]. 自动化技术与应用, 2009, 28(3) :68-72.

ZHAO Fang , L U A N X iao -ming , SU N Yue. Edg e detection oper ator s in dig ital imag e pr ocessing [J ].

Co mmunicatio n and Infor mation Pr ocessing , 2009, 28(3) :68-72. (in Chinese w ith an English abstract ) [4]　马睿, 曾理, 卢艳平. 改进的基于F acet 模型的亚像素

边缘检测[J ]. 应用基础与工程科学学报, 2009, 17(2) :296-302.

M A Rui, Z EN G L i, L U Yan-ping. Impr ov ed sub-pix el edg e detectio n method based o n Facet model [J ]. Jour nal of Basic Science and Eng ineering , 2009, 17(2) :296-302. (in Chinese with an Eng lish abstract )

[5]　郎晓萍, 刘力双. 图像测量中快速边缘亚像素定位研

究[J ].工具技术, 2009, 43(3) :89-92.

L A N G X iao -ping, LI U Li-shuang. St udy o n fa st edg e sub-pix el det ect ion method fo r measur ement imag e [J ].T echnolog y of t he T o ol , 2009, 43(3) :89-92. (in

Chinese w ith an English abstr act )

[6]　罗钧, 侯艳, 付丽. 一种改进的灰度矩亚像素边缘检测

算法[J].重庆大学学报, 2008, 31(5) :549-586. LU O Jun , Ho u Ya n , F U L i . A n impr ov ed alg or it hm for sub -pix el edg e detectio n using g ray mo ment [J ].Jo urnal of Chongqing U niver sity , 2008, 31(5) :549-586. (in Chinese with an Eng lish abstr act)

[7]　曲迎东, 李荣德, 袁晓光, 等. 两级Z ernike 矩算子的快

速亚像素边缘检测[J].哈尔滨工业大学学报, 2009, 41(5) :178-180.

QU Y ing -dong , L I R ong -de, YU AN Xia o-g uang, et al . F ast sub -pix el edg e detectio n based o n tw o Zernike m oments operat or s w ith differ ent mask sizes [J ].Jour nal o f Har bin Institute o f T echno log y, 2009, 41(5) :178-180. (in Chinese w ith an Eng lish abstr act )

5　结论

为了提高检测效率, 本文并没有采用传统的边缘检测算法进行粗定位, 而是在待测边缘的附近先取一点, 接着在这点的某一方向取几个点, 然后用三次多项式进行拟合从而得到亚像素边缘位置。经过与其他两种亚像素边缘检测算法的运行时间进行比较, 得出本算法的运行时间最短, 效率较高。

通过在研制的刀具检测系统中的试应用, 其检测速度较高, 运行稳定可靠。

参考文献:

[1]　陈彦燕, 王元庆. 常用边缘检测算法的定量比较[J ].

计算机工程, 2008, 34(17) :202-204. CHEN Y an-y an, WA N G Y uan-qing. co mpar ing

o f

co mmonly

used

edge

T he rat ion detect ion

alg or ithms [J ]. Co mputer Engineer ing , 2008, 34(17) :202-204. (in Chinese w ith an Eng lish abstr act) [2]　崔天横, 高晶敏, 刘振慧. 经典边缘检测的快速算法

[J]. 微计算机应用, 2007, 28(6) :575-579.

CU I T ian -heng , GA O Jing -min , L IU Z hen -hui . Fast algo rithm for edg e det ect ion [J ]. M icro co mput er A pplicatio ns, 2007, 28(6) :575-579. (in Chinese w ith an Eng lish abstr act)

[3]　赵芳, 栾晓明, 孙越. 数字图像几种边缘检测算子检测