基于二维局部均值分解的图像边缘检测算法*

陈思汉，余建波.上海大学 机电工程与自动化学院，上海 2000722.同济大学 机械与能源工程学院，上海 200092



基于二维局部均值分解的图像边缘检测算法*

陈思汉1，余建波2+
1.上海大学 机电工程与自动化学院，上海 200072
2.同济大学 机械与能源工程学院，上海 200092

CHEN Sihan,YU Jianbo.Edge detection algorithm based on bidimensional local mean decomposition.Journal of Frontiers of Computer Science and Technology,2016,10(6):847-855.

Received 2015-07,Accepted 2015-09.

CNKI网络优先出版:2015-09-16,http://www.cnki.net/kcms/detail/11.5602.TP.20150916.1548.008.htmltion and the final edge image is more consistent with the human visual inspection.

摘要：针对二维局部均值分解（bidimensional local mean decomposition，BLMD）中影响算法速度的两个主要因素：自适应搜索窗口和迭代终止条件，提出了优化方法，并在其基础上提出了一种边缘检测算法。该算法采用Delaunay三角剖分得到局部极值点的理想规则化的三角网格，通过网格划分确定相邻极值点及滑动平均窗口的大小，并提出了一种新的BLMD算法迭代收敛条件，通过对人工合成图像以及自然图像的实验，证实了该优化算法与原算法结果非常接近甚至更优，且大幅度提高了计算速度。对BLMD得到的最高频分量进行直方图均衡，将其结果二值化，通过设定阈值剔除其中不连续的细小边缘，通过形态学将其骨骼化，得到最终提取的边缘。与几种典型边缘检测算子的比较实验表明，新算法可以较好地检测出图像边缘，相对于其他边缘检测算子，对于图像中的纹理等细节边缘有着更佳的检测效果；并且得益于BLMD图像多尺度分析的优势，较好地避免了因光照明暗等低频因素产生的假边缘，提取出的边缘更符合视觉上的主观检测。

关键词：边缘检测；二维局部均值分解；多尺度图像分析；Delaunay三角剖分；骨骼化

ISSN 1673-9418CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(06)-0847-09

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

1　引言

边缘提取对于进行高层次的特征提取、特征描述等有着重大的作用，是图像处理领域重要的基本问题。基于经典算子，如Sobel、Roberts、Prewitt、LoG、Canny等，研究人员提出了很多优化算法[1-7]。文献[1]基于type-2模糊逻辑提出了一种改进的Sobel算子；文献[2]使用8个方向模板增强Prewitt，使用梯度幅值的邻域均值作为最终的梯度幅值，并使用OTSU计算阈值，降低了Prewitt对图像噪声的敏感度；文献[3]采用布谷鸟算法求得邻域阈值和标准差，增强了LoG算子；文献[4]通过使用type-2模糊集自动选择分割阈值，解决了Canny算子处理低照明图像时的不确定性；文献[5]采用OTSU求得Canny算子中的上下阈值，并结合双边滤波器提出了一种边缘保持的Canny算法；文献[6]使用形态学滤波代替高斯滤波，提出了一种针对椒盐噪声图像的Canny算子；文献[7]针对Canny的自适应性，进一步提出了一种自适应的Canny算法，其对噪声有一定的鲁棒性。

近年来，信号的多尺度分析在图像处理领域受到广泛关注，多尺度分析可以提取图像中不同频率尺度下的成分，为后续处理提供特征输入。由于局部均值分解（local mean decomposition，LMD）在很多方面优于经验模态分解（empirical model decomposition，EMD）[8-10]，本文作者[11]在LMD理论基础上提出了二维局部均值分解（bidimensional local mean decomposition，BLMD）。BLMD是完全数据驱动的自适应算法，采用自适应搜索窗口求得极值点的相邻极值点，使用滑动平均代替BEMD中的插值过程，避免了BEMD中的过包络、欠包络等问题，没有严重的端点效应。

虽然BLMD算法速度相比BEMD[12]已显著提高[11]，但其中搜寻相邻极值点的方法以及终止条件使算法仍较为耗时。因此，本文首先对BLMD算法进行优化，利用Delaunay三角剖分[13]的特性，将其用于确定极值点的局部相邻极值点以及平滑窗的大小，并推导出新的终止条件；其次，基于优化算法提出一种新的边缘检测算法，先对图像进行BLMD，对其中最高频分量进行直方图均衡，将其结果二值化，再清除其中不连续的长度小于预设阈值的细小边缘，最后通过形态学将其骨骼化，得到最终的图像边缘。与几种经典边缘检测算子的对比实验表明：（1）利用Delaunay三角剖分的特性求得极值点的局部相邻极值点更加理想化和迅速，结合新的迭代终止条件，大幅度降低了BLMD算法的迭代次数以及时间，增强了算法的鲁棒性，分解结果与原BLMD算法相当甚至更优；（2）本文算法对图像中细小边缘的提取更好，有效避免了因光照等因素产生的假边缘，且更加符合视觉上的主观检测。

2　BLMD

本文作者提出的BLMD算法[11]是一种完全依靠数据驱动的自适应的图像多尺度分析方法，其实质是从频率的角度出发，从原始图像中分离出纯调频和包络信号，并将两者相乘得到一个乘积函数（product function，PF）分量，迭代至一个复杂图像分解为若干个不同频率尺度PF的线性组合。对任意图像I(k,l)，其具体过程如下：

（1）求取图像中的所有局部极大值和局部极小值，并依据作者提出的自适应搜索窗口，确定每一个局部极值点的一定邻域范围内的若干相邻极值点，自适应搜索窗口原理如图1所示，并由式（1）、（2）计算局部均值mi和包络估计ai：

式（1）、（2）中，ni和ni+1是一对相邻的局部极大值点和局部极小值点。

Fig.1　Schematic of adaptive search window图1　自适应搜索窗口示意图

（2）对mi和ai进行滑动平均处理，得到局部均值函数m11和包络估计函数a11，平滑模板如：其中N为平滑窗口大小。

（3）将m11从原始信号I中分离出来，得到：

（4）对h11解调，即除以包络估计函数a11，得到：

迭代终止条件为:

实际数据中一般存在一定的误差，因此设定一个Δ，当1-Δ

（5）将迭代过程中产生的所有包络估计函数相乘得到包络信号：

（6）将包络信号与迭代最终的纯调频信号相乘，得到第一个PF分量：

（7）将PF分量从原始信号I中分离，对剩余部分重复步骤（1）～（6），即：

至此，图像便分解为几个PF分量和一个残余量：

3　优化BLMD算法

BLMD算法已经较为快速[11]，但其中部分过程仍比较耗时：（1）局部相邻极值点的求取，也即自适应搜索窗口的搜索过程；（2）求取PF分量的迭代过程。

分析图1，若将极值点相连，可得到三角网格。受此启发，本文引用三角剖分代替原自适应搜索窗口算法。离散点的三角剖分，尤其是Delaunay三角剖分，对于数值分析、有限元分析以及图形学来说是非常重要的一项预处理技术。Delaunay三角剖分主要应用于计算几何领域，具有最大化最小角、最接近于规则化理想化三角网格的特点。利用此特性，本文将Delaunay引入BLMD算法中，用于求取极值点的局部相邻极值点。

首先，通过对求得的所有极值点进行Delaunay三角剖分，得到所有极值点的理想规则化的三角网格；然后，判断三角网格中的每一对极值点是否为相同属性极值点，若是，则该对极值点之间存在鞍点，不能用于计算mi和ai，若不是，则根据它们的位置关系，由式（1）和式（2）计算出mi和ai。极值点的Delaunay三角剖分如图2所示。

Fig.2　Delaunay triangulation of local extrema图2　极值点的Delaunay三角剖分

采用本优化方法具有以下优势：（1）基于Delaunay三角剖分，具有自适应性，对于给定的任何离散点，都可以得到规则理想化的三角网格；（2）基于Delaunay的优化改进可用于本文优化方法，因此相对原BLMD算法中的自适应搜索窗口，速度有明显优势；（3）根据三角网格可以快速求得极值点之间的最小和最大距离，在确定式（3）中滑动窗口N取值时，耗时更少。

BLMD算法中的迭代终止条件是使分解得到的PF为纯调频调幅函数，即ai趋近于1；由于BLMD算法是LMD在二维的扩展，数据由一维至二维的转变使得ai由线到面，从而收敛迭代的次数相对一维信号增多，且随输入图像分辨率的增大，收敛更加耗时，影响了BLMD算法的时效性。因此，为了进一步提高BLMD算法的速度，分析推导式（7）。将式（4）、（6）带入式（7），可得:

本文优化的BLMD算法流程如下:

输入:图像Ik×l。

（1）分解图像I中的第j个分量PFj，分解PFj-1后的剩余图像为Ij-1,i=0为单次分解迭代次数：

①i=i+1，8-邻域法求Ij-1(即si-1)局部极值点，利用Delaunay三角剖分得到理想化三角划分网格，确定极值点的局部相邻极值点，并计算出极值点间的最小距离作为滑动窗口N的取值；

②由式（1）、式（2）以及三角划分网络提供的对应关系，计算mi、ai，并根据式（3）对其平滑；

③计算si；

④由式（13）判断终止条件，若不满足，则对si重复步骤①～④，直到满足收敛条件。

（2）由式（9）、式（10）计算PFj。

（3）从Ij-1中减去PFj得到剩余部分rn(即Ij)，重复步骤1、步骤2，直到残余量的极值点数少于2或达到预设的PF数量。

为证实上述优化方法有效且相比原方法更快速，本文采用BLMD算法[11]和优化BLMD算法，分别对人工合成图像[11]（图3（a））和自然图像（图4）进行对比实验。人工合成图像的实验结果如图3所示，通过计算分解各分量与对应的原始组成分量的噪声比（signal noise ratio，SNR）、峰值信号噪声比（peak signal noise ratio，PSNR）、均方差（mean squared error，MSE）和结构相似性理论（structural similarity index measurement，SSIM）[14]指标来证明本文方法的有效性，结果如表1，其中加粗为较优结果。

Fig.3　BLMD and optimized BLMD on synthetic image图3　BLMD与优化BLMD分解人工合成图像对比

Fig.4 BLMD and optimized BLMD on real images图4BLMD与优化BLMD分解自然图像

Table 1　Indicators of synthetic image decomposed by two BLMDs表1　人工合成图像的两种BLMD结果的各指标对比

图3（a）为人工合成图像，分别由图（b）～图（c）3个不同频率的成分组成，图（e）～图（f）为原BLMD算法分解结果，图（h）～（j）为本文优化BLMD算法分解结果，分析对比图3可知，本文提出的优化方法可行有效，分解结果与原结果非常接近。

对自然图像进行两种BLMD分解，比较分析每个PF分量迭代次数以及算法总体运行时间，结果如表2所示。

Table 2　Indicators of real images decomposed by two BLMDs表2　自然图像的两种BLMD结果的各指标对比

分析表1可知，本文方法可行有效，分解结果与原BLMD算法相近，甚至指标上略优于原BLMD。进一步分析表2可知，本文方法大幅度降低了PF分量的迭代次数以及算法的总耗时，总耗时分别为原BLMD算法的4.4%（合成图像）、2.7%（Cameraman）、2.4%（Brain）。

4　基于优化BLMD的图像边缘检测算法

图像经过BLMD可以分解为不同频率尺度的成分，是对图像信号的频率尺度划分。其中，最高频分量表征着图像中的最高频成分，即图像较锐利的边缘轮廓、噪声；最低频成分则表现了图像整体的明暗分布、光照等；虽然中间频率分量也包含着图像的边缘，但大多数是缓慢变化的边缘，并不是图像所突出的主体内容。最高频分量抽取出了图像中不同光照下的边缘信息，剔除了光照等低频信息，将其作为边缘检测的输入，既能提取出更多的边缘，又能避免假边缘的产生。

本文提出的边缘提取算法流程图如图5所示。首先通过BLMD算法得到不同PF分量；接着，对PF1进行直方图均衡，进一步背离边缘与背景；对均衡结果二值化，移除连通区域像素点数量少于ei的细小边缘；最后通过形态学算子thinning或skeleton得到单像素边缘的二值化图像，即是最终提取出的图像边缘。

5　实验与结果分析

本文采用3幅典型图像验证提出的边缘提取算法，分别为Cameraman、Lena和Barbara，并选取Sobel、Roberts、Prewitt、LoG和Canny算子与本文边缘提取算法进行对比，这些算子中涉及到的阈值均为Matlab中自动选取的最优化阈值。

首先对Cameraman进行BLMD分解，得到高频PF1分量，如图6（b）所示；接着对PF1进行直方图均衡操作，再二值化（阈值取0.85）得到原始的图像边缘，如图6（c）所示；然后取ei=10，通过判断图像中各连通区域的像素数量，剔除像素数量小于ei的散点和小范围的连通区域，如图6（d）所示；最后对清理过的二值化图像进行形态学算子skeleton操作，得到最终细化的图像边缘。图6（f）～（j）为Sobel、Roberts、Prewitt、LoG和Canny算子的边缘检测效果。通过对比图6（e）～（j）可知，本文边缘提取算法较理想地提取出了图像中的边缘，其他算子在最优阈值下，本文算法以及LoG和Canny算子兼顾了主体边缘和细节边缘，而Sobel、Roberts和Prewitt算子对细节边缘的提取欠佳。

Fig.5　Flowchart of proposed edge detection algorithm图5　本文提出的图像边缘提取算法流程图

Fig.6　Egde detection experiment on Cameraman with proposed method and other operators图6　本文算法与其他算子对Cameraman边缘提取的对比

Fig.7　Egde detection experiment on Lena with proposed method and other operators图7　本文算法与其他算子对Lena边缘提取的对比

进一步对Lena和Barbara进行相同实验分析，结果分别如图7、图8所示。这两幅图中都包含了大量的细节边缘信息，如头发、织物纹路等，相对于Sobel、Roberts和Prewitt算子，本文算法以及LoG和Canny算子在细小边缘提取上，体现出了相同的优势，并且在Barbara的实验中，本文算法对图像中细节纹理边缘提取最佳，优于所有其他算子。进一步分析比较，LoG有多边缘的产生，Canny虽然对细节边缘提取较好，但其无法较好地区分实体边缘，并且由于光照等因素产生的弱边缘，提取出的边缘较不符合视觉上对原图边缘的感知，如同一个物体的迎光面和背光面（Barbara图中左侧桌布上的纹理），表面明暗交界处（Lena和Barbara的面部五官轮廓）。因本文算法是建立在BLMD算法上，分解出的最高频分量PF1（图6（b）、图7（b）、图8（b））不含光照等低频信息，可以避免光照等对边缘提取的影响，因此在提取图像细小边缘的同时，其结果也能较好地与人眼的主观检测相符。然而对于边缘提取，没有一个统一的合适的评判标准，随着算法使用背景、提取目的的不同，对图像中的边缘需求也不尽相同，因而不能判定某一算法完全优于另一算法。

6　结束语

本文首先详细分析了作者提出的BLMD算法中影响算法速度的因素，并针对这些因素提出了有效的优化方法；将Delaunay三角剖分引入求解相邻极值点，分析推导出了原BLMD中PF分量的计算公式，提出了一种新的迭代收敛条件，并通过对人工合成图像以及自然图像的对比实验，证实了该优化可以大幅度减少BLMD算法的迭代次数和时间，且分解效果与原算法相当，甚至更优。其次，本文在优化的BLMD算法基础上，提出了一种快速的图像边缘提取算法，并与几种典型的边缘提取算子进行对比实验。实验结果表明：首先，本文提出的边缘提取算法可以较好地提取出图像中的边缘；其次，相对于其他边缘提取算子，本文算法对于图像中的纹理等细节边缘有着更佳的提取效果；最后，由于BLMD自适应地将图像分解成了不同频率的尺度成分，使得本文算法可以避免因光照等因素产生的假边缘的干扰，提取出的边缘更加符合人眼视觉上的主观检测。然而本文算法还有待改进，如二值化阈值、连通区域阈值的选取，直方图均衡的优化，以及由于形态学算子细化图像时因边缘不平整而产生的毛刺现象。

Fig.8　Egde detection experiment on Barbara with proposed method and other operators图8　本文算法与其他算子对Barbara边缘提取的对比

References:

[1]Gonzalez C I,Melin P,Castro J R,et al.An improved sobel edge detection method based on generalized type-2 fuzzy logic[J].Soft Computing,2016,20(2):773-784.

[2]Yang Lei,Wu Xiaoyu,Zhao Dewei,et al.An improved Prewitt algorithm for edge detection based on noised image [C]//Proceedings of the 2011 4th International Congress on Image and Signal Processing,Shanghai,China,Oct 15-17, 2011.Piscataway,USA:IEEE,2011:1197-1200.

[3]Mallick A,Roy S,Chaudhuri S S.Optimization of Laplace of Gaussian(LoG)filter for enhanced edge detection:a new approach[C]//Proceedings of the 2014 International Conference on Control,Instrumentation,Energy and Communication,Kolkata,India,Jan 31-Feb 2,2014.Piscataway,USA:IEEE,2014:658-661.

[4]Biswas R,Sil J.An improved Canny edge detection algorithm based on type-2 fuzzy sets[J].Procedia Technology, 2012,4:820-824.

[5]Gao Jie,Liu Ning.An improved adaptive threshold Canny edge detection algorithm[C]//Proceedings of the 2012 International Conference on Computer Science and Electronics Engineering,Hangzhou,China,Mar 23-25,2012.Piscataway,USA:IEEE,2012:164-168.

[6]Deng Caixia,Wang Guibin,Yang Xinrui.Image edge detection algorithm based on improved Canny operator[C]//Proceedings of the 2013 International Conference on Wavelet Analysis and Pattern Recognition,Tianjin,China,Jul 14-17,2013.Piscataway,USA:IEEE,2013:168-172.

[7]Geng Hao,Luo Min,Hu Feng.Improved self-adaptive edge detection method based on Canny[C]//Proceedings of the2013 5th International Conference on Intelligent Human-Machine Systems and Cybernetics,Hangzhou,China,Aug 26-27,2013.Piscataway,USA:IEEE,2013:527-530.

[8]Huang N E,Shen Z,Long S R,et al.The empirical mode decomposition and the Hilbert spectrum for nonlinear and non-stationary time series analysis[J].Proceedings of the Royal Society of London A:Mathematical,Physical and Engineering Sciences,1998,454(1971):903-995.

[9]Smith J S.The local mean decomposition and its application to EEG perception data[J].Journal of the Royal Society Interface,2005,2(5):443-454.

[10]Cheng Junsheng,Zhang Kang,Yang Yu,et al.Comparison between the methods of local mean decomposition and empirical mode decomposition[J].Journal of Vibration and Shock,2009,28(5):13-16.

[11]Chen Sihan,Yu Jianbo.Multiscale image analysis based on bidimensional local mean decomposition[J].Journal of Computer-Aided Design&Computer Graphics,2015,27 (10):1842-1850.

[12]Nunes J C,Bouaoune Y,Delechelle E,et al.Image analysis by bidimensional empirical mode decomposition[J].Image and Vision Computing,2003,21(12):1019-1026.

[13]Delaunay B.Sur la sphère vide.A la mémoire de Georges Voronoï[J].Bulletin de l'Académie des sciences de l'URSS: Classe des Sciences Mathématiques et na,1934(6):793-800.

[14]Wang Zhou,Bovik A C,Sheikh H R,et al.Image quality assessment:from error visibility to structural similarity[J]. IEEE Transactions on Image Processing,2004,13(4):600-612.

附中文参考文献：

[10]程军圣,张亢,杨宇,等.局部均值分解和经验模式分解的对比研究[J].振动与冲击,2009,28(5):13-16.

[11]陈思汉,余建波.基于二维局部均值分解的图像多尺度分析处理[J].计算机辅助设计及图形学学报,2015,27(10): 1842-1850.

CHEN Sihan was born in 1990.He is an M.S.candidate at Shanghai University.His research interests include signal processing,image processing,machine learning,object detection and tracking,etc.

陈思汉（1990—），男，安徽淮南人，上海大学硕士研究生，主要研究领域为信号处理，图像处理，机器学习，物体识别与跟踪等。

YU Jianbo was born in 1978.He received the Ph.D.degree from Shanghai Jiao Tong University in 2009.Now he is a professor at School of Mechanical Engineering,Tongji University.His research interests include intelligent maintenance and machine learning,etc.

余建波（1978—），男，浙江慈溪人，2009年于上海交通大学获得博士学位，现为同济大学机械与能源工程学院教授，主要研究领域为智能维护，机器学习等。

+Corresponding author:E-mail:jianboyu.bob@gmail.com

文献标志码：A

中图分类号：TP751.1

doi:10.3778/j.issn.1673-9418.1507031

Edge DetectionAlgorithm Based on Bidimensional Local Mean Decompositionƽ

CHEN Sihan1,YU Jianbo2+
1.School of Mechanical Engineering andAutomation,Shanghai University,Shanghai 200072,China
2.School of Mechanical Engineering,Tongji University,Shanghai 200092,China

Abstract:For optimizing two crucial time-consuming processes in bidimensional local mean decomposition(BLMD): adaptive window-based search method and terminal criterion,this paper proposes two schemes,and then puts forward a new image edge detection algorithm based on this optimized bidimensional local mean decomposition.Delaunay triangulation is employed to get an ideal triangular mesh,then the local adjacent extrema and the moving average window size can be achieved from the mesh.Also,this paper presents a new convergence condition of iteration.Experiments on the synthetic and real images prove that these optimizations can make BLMD be much faster and have an identical or even better performance.Histogram equalization and binarization are applied to the first PF for achieving raw edge,then the disjoint or unconnected and undesired edges can be removed from binary image by a removal operation controlled by a threshold parameter,finally morphological thinning or skeleton operation is applied to get the final single-pixel width edge image.The proposed method is compared with several standard edge detection techniques,the experimental results show that the proposed method can successfully generate the desired edge map and has a better performance.In addition,benefitting from BLMD,the proposed method can relieve false edges produced by illumina-

Key words:edge detection;bidimensional local mean decomposition;multiscale image analysis;Delaunay triangulation;skeleton

*The National Natural Science Foundation of China under Grant Nos.51375290,71001060(国家自然科学基金);the Research and Innovation Foundation of Shanghai Education Commission under Grant No.13YZ002(上海市教育委员会科研创新项目).