基于弹簧质点模型边缘检测算法的改进

戚晓伟

摘要：本文基于物理学中弹簧力学的理论提出了一种改进的弹簧质点模型边缘检测算法。为解决现有弹簧质点模型边缘检测算法检测的边缘较粗问题，本文在该模型计算像素点合力的公式中增加一个合力因子，结合数学形态学中腐蚀膨胀的原理来改进弹簧质点模型边缘检测算法，以便能得到单像素宽度的边缘。实验结果表明，该算法的检测效果更加理想。

关键词：边缘检测;弹簧质点模型;数学形态学;细化边缘

中图分类号：TP391.41;TP751文献标识码：A

Theimproved algorithm based on Massspring model edge detection

Qi Xiaowei

Jiangsu College of TourismJiangsuYangzhou225217

Abstract：This paper puts forward an improved springmass model edge detection algorithm based on the physics of the spring mechanics theory.In order to solve the problem that the edges are thicker which is detected by the existing massspring model edge detection algorithm，based on the model this paper add a force factor to calculate the force.In the meanwhile the paper combines with mathematical morphology in the principle of erosion and dilation to improve massspring model edge detection algorithm so as to get the edge of single pixel width.The experimental results show that this algorithm can get more ideal results.

Key words：edge detection;Massspring model;mathematical morphology;edge thinning

图像的边缘信息往往能够告诉我们图像的特征信息，因而图像的边缘检测一直是人们值得研究和关注的课题。传统的边缘检测算子，多数都是基于微分的算子，算法尽管简单，编程方便，然而对噪声的极其敏感，限制了在实际当中的应用[1]。随着科学技术的不断进步，出现了新的边缘检测算法，Sun等人在2007年结合物理学知识提出了基于万有引力的边缘检测算法[2]，这种算法新颖独特，开拓了边缘检测研究的新视野，在此启发下，文献[3]提出了弹簧质点模型边缘检测算法，但该算法检测到的边缘较粗。本文在分析了弹簧质点模型算法的缺点后，在计算像素合力时增加一个合力因子（邻域灰度均值与中心像素灰度之和），并利用数学形态学中腐蚀膨胀的原理对该算法进行改善，得到了单像素边缘的检测算法。

1 弹簧质点模型边缘检测算法原理

就物理角度看，弹簧质点模型是一个经典的力学模型，它一直广泛地应用于织物变形及图像配准的研究中[4]。弹簧质点模型边缘检测算法也是利用这个物理模型，将邻域内中心像素所受到的合力通过门限值作为判定是否是边缘点的依据，取得了较好的边缘检测效果。

在一个弹簧质点模型中，假设两质点之间存在的是一根无质量的弹簧。使弹簧变形的主要有拉伸力FS、剪切力FC和弯曲力FB三类弹性力，那么所受内力可以表示为：

Fin=FS+FC+FB（1）

为了尽量简化过程，每个像素所受的力只考虑拉伸力FS。

原始图像X，（x，y）处的像素灰度值为X（x，y）。我们把图像中的各像素点看成弹簧模型中的质点，记一个像素受到另一个像素拉力的大小和方向可以用一个矢量FM，N来表示，则根据力学胡克定律，FM，N可表示为：

FM，N=kMN（‖XN-XM‖-l0MN）·XN-XM‖XN-XM‖

=kMN1-l0MN‖XN-XM‖·（XN-XM）（2）

其中，l0MN表示该模型在开始状态时两个质点M与N之间的自由长度，即弹簧的初始长度，kMN表示质点间的弹簧系数，‖XN-XM‖表示两个质点M、N的欧氏距离，XM和XN表示两质点的像素灰度值[5]。

在图像的3×3邻域内，对于图像中的每个像素点，通过来自其周围像素点的弹簧拉力的合力大小判定它是否是边缘上的点。中心像素点假设为（i，j），邻域内其他像素点记为（k，l）。则算法步骤为：

（1）分别计算周围像素点对中心像素点的弹簧拉力。

对于中心像素点（i，j），若（k，l）处于它的水平位置，则（i，j）在水平和垂直方向上的受力为：

F1x（i，j;k，l）=k1-l‖Xk，l-Xi，j‖·（X（k，l）-X（i，j））

F1y（i，j;k，l）=0（3）

同理，若（k，l）处于它的垂直位置，则（i，j）在水平和垂直方向上的受力為：

F1x（i，j;k，l）=0

F1y（i，j;k，l）=k1-l‖Xk，l-Xi，j‖·（X（k，l）-X（i，j））（4）

若（k，l）处于它的对角位置，则（i，j）在水平和垂直方向上的受力为：

F2x（i，j;k，l）=k1-l‖Xk，l-Xi，j‖·（X（k，l）-X（i，j））·cosθ

F2y（i，j;k，l）=k1-l‖Xk，l-Xi，j‖·（X（k，l）-X（i，j））·sinθ（5）

其中，θ为45°。

（2）计算中心像素点（i，j）所受合力F在x，y轴方向上的分力。

Fx=∑F1x（i，j;k.l）+∑F2x（i，j;k，l）

Fy=∑F1y（i，j;k.l）+∑F2y（i，j;k，l）（6）

（3）计算中心像素点所受合力F和方向角θ。

F=F2x+F2y，θ=arctanFyFx（7）

（4）设置一个合适的阈值T，如果某像素点所受合力大于这个阈值，可以认为这个像素点为边缘点。

2 改进的弹簧质点模型边缘检测算法

原始的弹簧质点模型的边缘检测算法由于没有使用传统的微分算法检测边缘，虽然在抗噪声性能上有一定的提高，但检测到的边缘也较粗，因此本文从以下两个方面对该算法进行改善。

2.1 合力算法的分析及改善

原始弹簧质点模型边缘检测算法检测出的边缘较粗。以下从二值合成图像分析导致该结果的原因。

在图1中，假设邻域内水平或垂直的两像素点间的欧氏距离设为a，那么对角的两像素点间的距离为2a，为方便计算，这里设定弹簧系数为1.0，弹簧的初始长度为1.0，并且合成的二值图像白色像素点灰度值为1，黑色像素点灰度值为0。那么可以计算：

F1=F4=0（8）

F2x=22（1-12a）（X5-X2）+22（1-12a）（X9-X2）+（1-1a）（X1-X2）-22（1-12a）（X7-X2）-22（1-12a）（X11-X2）-（1-1a）（X3-X2）

=-（2+1-2a）F2y=22（1-12a）（X5-X2）+22（1-12a）（X7-X2）+（1-1a）（X6-X2）-22（1-12a）（X9-X2）-22（1-12a）（X11-X2）-（1-1a）（X10-X2）

=0

从而像素点2所受到的合力：

F2=F22x+F22y=（2+1-2a）（9）

同理，像素点3所受到的合力也为F3=（2+1-2a）。在选定合适阈值后，由于像素点2、3所受到的合力值相同，因此在检测时把这两个像素点都判定为边缘点，显然这是不合理的。从图2中可以看出，像素点2和3所在邻域的整体灰度值是不同的。由此可见，利用物理力学中的胡可定律计算像素点所受到的合力并以此作为判定边缘的根据会引起误判，从而采用弹簧质点模型边缘检测算法所检测到的边缘较粗。为充分利用邻域的整体性质并考虑邻域内的整体灰度情况，本文将像素点所受合力的计算公式改为F=（X-+X（i，j））F2x+F2y，其中X-为邻域内灰度均值。以此合力作为判定像素点（i，j）是否为边缘的依据，实验显示该方法可以得到较细的像素边缘。

2.2 数学形态学细化原理

对于一些复杂的真实图像，只采用上述改进并不能有效进行边缘细化。而数学形态学是一种研究数字图像形态结构特征与快速并行处理的方法，它算法简单、速度快、可并行处理、易于硬件实现[6]。

数学形态学中最基本的运算是腐蚀和膨胀。主要进行集合相关的运算。下面介绍数学形态学的基本概念和运算。

设Ω为二维欧几里得空间，图像A是Ω的一个子集，结构元素B也是Ω的一个子集，b∈Ω是欧氏空间的一个点，定义如下几个概念。

（1）平移：

Ab=a+ba∈A（10）

Ab表示图像A被b平移后的结果，即Ab中所有元素是A中的对应元素平移到以b为原点的坐标系内的结果。

（2）反射：

A～=-aa∈A（11）

A～表示图像A对于图像原点反射的结果。

（3）膨胀（dilation）的运算定义式为：

AB=a+ba∈A，b∈B=∪Ab（12）

（4）腐蚀（erosion）的运算定义式为：

AΘB=z∈ΩBzA=∩Ab（13）

图像A被结构元素B膨胀，膨胀后A形状与结构元素B的形状息息相关。同样，图像A被结构元素B腐蚀，腐蚀的结果与结构元素B的选取有关。因此，选取不同的结构元素B做膨胀或腐蚀运算后所得的结果可能截然不同。

在定义腐蚀和膨胀运算的基础上，再定义另外两个常用运算：开运算（opening）和闭运算（clothing）。

①开运算：A对B的开运算的结果定义为：

A°B=（AΘB）B（14）

即A先被B腐蚀，再被B膨胀的结果。

②闭运算：A对B的闭运算定义为：

A·B=（AB）ΘB（15）

即A先被B膨胀，其结果再被B腐蚀。它与开运算正好相反。依据开运算和闭运算的特征，一般可以运用开运算删除图像中的小分支，運用闭运算填补图像中的空穴。

形态学还有一种称为击中击不中的变换，它被广泛应用在保持拓扑结构的形状细化与修剪、形状识别和目标定位等方面。

（5）击中击不中变换：假设B由两个不相交的部分B1和B2组成，即B满足B=B1∪B2且B1∩B2=，则A被B击中定义为：

AB=x（B1）xA，（B2）xAc（16）

细化一般是指用一条曲线代表一个具有一定面积的区域，而击中击不中变换是数学形态学细化算法的关键环节：对给定一系列具有一定形状的结构元素后，顺序循环地删除满足击中变换的像素。

于是，图像A被结构元素B细化的定义为：

AB=A-（AB）=A∩（AB）c（17）

即AB为在A中去掉A被B击中的结果。那么A被结构元素序列细化的定义为：

AB=（（…（（AB`1）B2）…）Bn（18）

其中，B=B1，B2，…，Bn为一个结构元素序列，Bi是Bi-1的旋转。以上细化过程可以描述为：先用B1细化一遍，再用B2对B1的结果进行迭代细化，如此反复，直到Bn。整个过程可以继续重复到没有变化为止。另外，由于细化是有方向性的且需要更为对称地进行，因此本文选择的是八个方向的结构元素序列，如图2。

图2中，B1，B3，B5，B7，B2，B4，B6，B8是用来对称地去掉南、西、北、东、西南、西北、东北、东南八个方向上的点。“o”点方格表示参考中心点;“1”方格表示目标图像上的点;“0”方格表示背景图像上的点;“*”表示既可以是目标上的点，也可以是背景上的点。

因此，式（18）就被定义为：

ABm=（（…（（AB1）B2）…）B8）m（19）

式中，m是进行图像细化收敛时的总循环次数，它的结果由目标图像的大小和边缘粗细决定[7]。

2.3 算法描述

以下是本文给出的改进的弹簧质点模型边缘检测算法过程：

（1）输入原图像，对所有邻域内中心像素点用改进的算法分别计算其所受x軸、y轴方向的分力，并求出其合力大小及方向;

（2）选取一个合适的阈值，对图像中各像素点进行二值化，合力大小大于阈值的像素点判为边缘点，否则为非边缘点;

（3）对所得到的边缘图像运用数学形态学细化边缘;

（4）输出最终边缘图像。

3 实验结果及分析

本文使用合成图像和真实图像进行实验，并且与效果较好的LoG算子、Canny算子以及原弹簧质点模型检测算法进行比较。其中，对合成图像的检测性能用定量的边缘检测品质因子分析各算法的优劣，真实图像则通过视觉效果判断各算法检测效果。

3.1 合成图的检测结果

图3显示了无噪合成图像的各算法边缘检测结果。

（a）原始合成图像

（b）LoG算子（c）Canny算子

（d）原弹簧模型算法（e）本文方法

从上图可以看出，本文方法较于其他方法不仅可以检测到单像素边缘，而且能够准确检测出边缘的位置。

目前尽管没有较统一权威的判别依据来确定不同边缘检测方法的性能，但区分从检测方法中获得的主要信息和辅助性信息帮助我们判定一个边缘检测方法的性能的好坏。这些信息包括边缘像素点的位置、边缘的高度和斜面倾角及其在空间中的方位等。

此外，边缘判定的可靠性因子可以用来刻画实际拟合边缘与理想边缘之间的接近程度。边缘检测过程中，三种类型的误差会造成边缘的错误检测，分别为：（1）边缘点丢失，（2）边缘点定位失效，（3）将噪声波动误认为是边缘点。于是可以用真实边缘检测的概率来描述边缘检测的性能，该概率可以通过对理想边缘检测器和实际边缘检测器检测到的边缘图形进行比较来进行估计。在此基础上，Pratt提出了品质因子来判定边缘检测器的性能。品质因子的定义式为：

R=1IN∑IAi=111+ad2（20）

式中，IN=MAXII，IA，II和IA表示理想和实际边缘图形点的数量。a是一个比例常数，d为实际边缘点到理想边缘点连线的垂直距离。R值越大，表示边缘定位精度越高，边缘检测性能就越好[89]。下表给出了各算法的品质因数。

由上表可以看出，本文对于合成图像的边缘检测效果要优于其他算法。

3.2 真实图像的边缘检测结果

对真实图像进行各算法的边缘检测结果，如图4所示。

（a）原图像（b）加噪图像

（c）LoG原图像检测（d）LoG含噪图像检测

（e）Canny原图像检测（f）Canny含噪图像检测

（g）原方法原图像检测（h）原方法含噪图像检测

（m）本文方法原图像检测（n）本文方法含噪图像检测

在图4中，左列各图是无噪情况下边缘检测的情况，右列是对图像加了一定强度的高斯噪声后各算法边缘检测的结果。在无噪声的情况下，原弹簧质点模型边缘检测算法检测出的边缘很明显较粗;LoG算子和Canny算子图像边缘检测的边缘虽然较精细，但它们均检测出了一些伪边缘，丢失了很多重要的细节信息，从而导致检测图像并不能很好的反映图像本身的特征，也就失去了边缘检测的意义。在加入高斯噪声的图像检测中，由于LoG算子和Canny算子本身具有高斯滤波器平滑噪声的作用，检测后的图像中噪声较少，但由于高斯滤波器过度平滑噪声，很多边缘信息也被平滑掉，检测出来的结果很不真实，失去了很多反映结构特征的边缘信息;原弹簧质点模型检测算法检测出的结果仍然存在检测不精细的缺点，虽然较Canny算法能够提取出图像的边缘信息，可是由于受到噪声的影响，破坏了检测性能。本文方法无论是对原图像还是含噪声图像，检测出的边缘信息清晰，边缘的连续性也较好，很好地反映图像的重要特征，同时也有一定的滤波效果，综合考虑，本文算法相比其他算法有了很大的改善。

4 结语

针对原弹簧质点模型边缘检测算法检测到的边缘较粗的弊端，本文提出了一种改进的弹簧质点模型边缘检测算法，算法中将邻域灰度均值与该邻域中心像素灰度值之和作为因子考虑到所求合力中，检测到的边缘更加精细，再将数学形态学应用到该算法中细化边缘，通过实验表明改进后的算法在边缘检测的性能上有了很大的改善。

参考文献：

[1]Richard EWoods，Steven L.Eddins.数字图像处理[M].电子工业出版社，2008.

[2]SUN Genyun，LIU Qinhuo，LIN Qian.A novel approach for edgedetectionbased on the theory of universal gravity[J].PatternRecognition，2007，40（10）：27662775.

[3]徐遥，张如艳，王世同.一种新的基于改进弹簧质点模型的图像边缘检测算法[J].计算机应用研究，2011，28（4）：15731576.

[4]龚永义，罗笑南，贾维嘉，等.基于改进的弹簧质子模型的医学图像配准[J].计算机学报，2008，31（7）：12241233.

[5]满利红，王士同.应用改进的弹簧质点模型进行图像滤波的算法[J].计算机辅助设计与图形学学报，2009，21（11）：16181623.

[6]何新英，王家忠，孙晨霞，常淑惠，周桂红.基于数学形态学和Canny算子的边缘提取方法[J].计算机应用，2008，28（2）：477479.

[7]崔屹.圖像处理与分析——数学形态学方法及应用[M].北京：科学出版社，2002.1.

[8]I.Abdou.Quantitative Methods of Edge Detection[R].USCIPI Report 830，Image Processing Institute，University of Southern California，Los Angeles，1973.

[9]I.E.AdouW.K.Pratt.Quantitative Design and Evaluation of Enhancement/Thresholding Edge Detectors[J].Proc.IEEE1979：753763.