基于二維局部均值分解的圖像邊緣檢測算法*

陳思漢，余建波.上海大學 機電工程與自動化學院，上海 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(上海市教育委員會科研創新項目).