一種基于膜計算的梯度邊緣檢測算法

謝佩軍　計時鳴

1(寧波大紅鷹學院　浙江 寧波 315175)

2(浙江工業大學　浙江 杭州 310014)

?

一種基于膜計算的梯度邊緣檢測算法

謝佩軍1計時鳴2

1(寧波大紅鷹學院浙江 寧波 315175)

2(浙江工業大學浙江 杭州 310014)

摘要針對傳統邊緣檢測算法的不足，提出一種以組織型P系統為框架的梯度邊緣檢測算法。采用一個兩層膜結構，即表層膜與基本膜，使用轉運規則實現各基本膜間的對象交換與共享。該算法逼近強度函數的梯度方向，基于梯度進行邊緣的檢測，并通過經典邊緣檢測算子的對比實驗，實驗結果表明所提出的邊緣檢測方法具有較好的有效性。

關鍵詞膜計算組織型P系統邊緣檢測梯度

A MEMBRANE COMPUTING-BASED GRADIENT EDGE DETECTION ALGORITHM

Xie Peijun1Ji Shiming2

1(Ningbo Dahongying University,Ningbo 315175,Zhejiang,China)2(Zhejiang University of Technology,Hangzhou 310014,Zhejiang,China)

AbstractAiming at the shortcomings of traditional edge detection algorithms, this paper presents a gradient edge detection algorithm using tissue P system as the framework. The system adopts a two-level structure, i.e. the outermost membrane and the elementary membrane. The communication rules are employed to realise the exchange and share of the objects among elementary membranes. This algorithm approaches the gradient direction of intensity function, and detects edges based on gradient. By contrast experiment using classic edge detection operator, the experimental results illustrate that the proposed edge detection method has good effectiveness.

KeywordsMembrane computingTissue P systemEdge detectionGradient

0引言

膜計算是自然計算的分支，是從生物細胞及組織的功能和結構中抽象出來的計算模型。Gheorghe P?un在多年深入研究DNA分子的基礎上，受細胞結構和組織功能的啟發，于1998年提出膜計算的概念，并于2000年正式發表論文提出膜計算思想[1]。由于膜計算是由P?un提出的，因此，膜計算模型通常稱為P系統。目前主要有3種類型的P系統：細胞型P系統、組織型P系統[2]和神經型P系統[3]。P系統是一種分布式、并行計算模型，具備很多特性，如同步性、分隔性、非確定性、可理解性、可描述性、可編程性等。因此，膜計算自提出以來，便受到眾多研究者的廣泛關注，涵蓋數學、計算機科學、人工智能、計算機圖形學、自動控制等諸多學科，成為一個非常活躍的研究領域。

關于膜計算的研究大致分為3類：理論研究、應用研究和P系統的軟硬件研究。理論研究主要研究各類計算模型的建立，并分析其計算能力和計算有效性，計算能力分析P系統是否具有圖靈等價性[4,5]，而計算有效性主要分析其解決NP等問題的可能性[6]；P系統的軟硬件研究主要關注于仿真軟件系統的實現或研發硬件處理器實現相關計算模型[7]；P系統的應用研究主要是利用各種模型求解信息安全、自動控制、數字圖像處理、經濟學等方面的實際問題[8]。P系統在數字圖像處理方面的應用，文獻[9]提出了一種基于組織P系統的數字圖像平滑去噪方法，圖像處理效果較理想。文獻[10]利用細胞型P系統的并行計算實現2D圖像的閾值分割。文獻[11]提出了一種基于數學同構理論的圖像分割算法，但只能分割人造圖像；

本文主要研究膜計算的相關特性和機制，將其用于圖像處理過程中的邊緣檢測，以擴展膜計算的應用范圍和開發新的圖像處理方法?；赑系統的相關特性，并應用于圖像邊緣檢測。提出了一種P系統計算模型下的基于梯度的圖像邊緣檢測算法，該算法通過P系統的各種轉運規則自動實現輪廓提取，充分利用了P系統的并行計算能力。

1組織型P系統

一般地，一個度為n的組織型P系統可表示為如下結構[12]：

∏=(Γ,Σ,μ,w1,…,wn,R,iΠ,io)

其中，Γ是字母表，其元素被稱為對象；Σ是輸入字母表；μ是由n個膜組成的膜結構；wi(1≤i≤n)表示μ中的區域i所包含的對象多重集；R是有限的規則集，其中的Ri對應于μ中膜i的規則；iΠ是系統的輸入區域；io是系統的輸出區域。

組織型P系統的規則集主要包括兩類規則：進化規則和轉運規則[13]。運用進化規則能夠進化膜中對象產生新的對象多重集；運用轉運規則能夠實現各基本膜之間對象的交換與共享。

2基于P系統的邊緣檢測算法

2.1膜結構

本文提出的邊緣檢測算法的基礎是一個組織型P系統。該系統采用的膜結構是一個兩層膜結構，表層膜由0來表示，也是系統的輸出膜。由于輸入數據是一張大小為n×m的原始圖像，原始圖像的每個像素aij對應一個基本膜(i,j)，1≤i≤n,1≤j≤m,且這n×m個基本膜處于相同的層次，因此，該系統的度為n×m+1。當系統滿足停機條件時，表層膜中的對象就是系統的輸出。該膜結構也可表示為：

μ=[0[(1,1)](1,1)[(1,2)](1,2)…[(n,m)](n,m)]0

2.2算法流程

在P系統中，每個膜通常都包含一定數量的對象，且對象是由字符串來表達?？紤]到所討論像素為n×m的圖像，在這個P系統中，表層膜包含的初始對象就是原始圖像，最后的輸出也是通過表層膜得到邊緣檢測完成的圖像。其他n×m個基本膜分別包含一個像素，其初始對象就是原始圖像的各像素。

2.3P系統計算過程

組織P系統的輸入數據是大小為n×m的原始圖像。對該圖像進行編碼，形成對象aij(a∈C，1≤i≤n,1≤j≤m)。該P系統的計算過程分為四個階段：

1) 初始化階段

原始圖像輸入到膜0，系統開始運行。并通過轉運規則將原始圖像的每個像素aij相應地發送至n×m個基本膜，作為基本膜的初始對象。此處，轉運規則1實現將表層膜膜0中相應對象發送至各個基本膜(i,j)，其形式為：(0，u/λ,(i,j))，1≤i≤n,1≤j≤m。如圖1所示。

圖1　像素aij4對鄰域像素構成的方向

2) 逼近梯度階段

(1) 構造方向對于(基本膜(i，j))像素aij，構造其4對鄰域像素構成基本膜(i，j)的四個方向，即東西((i，j-1)與(i，j+1))，南北((i-1，j)與(i+1，j))，東南-西北((i+1，j-1)與(i-1，j+1))，東北-西南((i-1，j-1)與(i+1，j+1))。

(2) 選取方向對上述4對領域像素值分別作差分運算，并取其絕對值，保留絕對值最大的像素對，選取該像素對表示的方向。

(3) 梯度逼近根據上步選取的方向，對于每個像素aij(膜(i，j))，選用3×3鄰域范圍內的6個像素(4種選擇方式，圖2是其中一種)對強度函數的梯度方向進行逼近。運用轉運規則2，實現各個膜中對象的進化。轉運規則2的規則形式為：((i，j),u/v, (k，l)),1≤i,k≤n，1≤j,l≤m,且i=k與j=l不能同時成立。如圖2所示。

圖2　3×3鄰域像素

3) 輸出階段

經過上階段，實現對強度函數的梯度方向逼近。最后，需要將各個基本膜中經過轉運與進化的對象，通過轉運規則3相應地發送到表層膜膜0，替換膜0中的初始對象(原始圖像)。此處，轉運規則3實現將各個基本膜(i,j)中相應對象發送至表層膜膜0(即輸出膜)，其形式為：((i,j)，u/λ,0)，1≤i≤n,1≤j≤m。

通過這種方式，會得到完成邊緣檢測的新圖像，實現對圖像輪廓的提取。

3實驗結果與分析

將本文提出的算法(下文記作GP算法)與經典的邊緣檢測算子Canny檢測算子、Sobel3×3檢測算子的檢測效果與運行時間進行對比分析。Canny檢測算子具有既能濾去噪聲又保持邊緣特性的邊緣檢測最優濾波器，能較理想地檢測圖像輪廓，但處理時間稍長；Sobel3×3算子利用快速卷積函數，能夠快速有效地檢測邊緣，但由于沒有基于圖像灰度進行處理，因此，提取的圖像輪廓有時并不理想。

3.1邊緣檢測的定性分析

實驗平臺硬件配置CPU Intel i5-2450m，2.5 GHz，64位操作系統，顯卡AMD Radeon HD 6470m。本文針對100幅不同特點、不同數據量的醫學MRI圖像進行實驗，分析比較三種算子的處理時間與檢測效果，得到3種算子的處理時間與圖像數據量關系曲線，如圖3所示。

圖3　處理時間與圖像數據量關系曲線

根據圖3曲線可以分析得到，當圖像數據量較小時，幾種算子的處理時間差值不是非常大。隨著數據量逐漸增加，Canny算子處理的邊緣信息量成倍增加，其與Sobel算子、GP算子的處理時間差值越來越大，但Sobel算子與GP算子的處理時間差值相對較小，說明當數據量增大時，GP算子的并行處理能力開始體現優勢。

選取4幅典型圖片，比較3種算子的處理時間，如表1所示。

表1　3種算子對典型圖片的處理比較

從圖4-圖7的圖像檢測效果來看，Canny算子檢測出的圖像邊緣信息最豐富，能夠完整地檢測出輪廓，但存在不少假邊緣，容易產生干擾；Sobel算子能檢測出比較明顯的邊緣，提取的邊緣信息比較少，且邊緣存在不連續現象；本文提出的GP算子的檢測效果明顯優于Sobel算子，能夠較清晰、完整地檢測提取邊緣，且假邊緣極少，說明該算法具有較好的可行性與較理想的檢測效果，尤其是對于灰度變化劇烈的圖像，GP算子的檢測效果比傳統算法均要好。

圖4　Heart_1檢測效果

圖5　Heart_2檢測效果

圖6　Brain檢測效果

圖7　Chest檢測效果

3.2邊緣檢測的定量分析

本文采用一種基于邊緣連接程度的評價方法，比較分析上述三種邊緣檢測算法。按4-連通成分數B、8-連通成分數C及其比值C/B三個指標對邊緣檢測效果進行定量評價。4-連通成分是指若某像素的4-領域內存在與之連通的像素，則稱為一個4-連通成分，同理可得8-連通成分。C/B比值反映了邊緣的連接程度，邊緣線形的連接程度可反映出邊緣的錯檢、漏檢。可由數學歸納法證得C/B值越小時，邊緣線形連接度越好，因而能夠證明邊緣的提取效果越好[14]。

根據上述原理，選取圖Brain與圖Chest進行實驗，可以得到如表2所示的邊緣圖統計數據。統計數據顯示3種算法中Sobel算子的C/B值最大，說明其邊緣線形的連接程度最差，邊緣的錯檢、漏檢最多；GP算法的C/B最小，說明其邊緣線形連接程度最好，邊緣的錯檢、漏檢少，邊緣提取效果最佳。

表2　邊緣圖統計數據

4結語

本文提出的采用P系統模型進行基于梯度的邊緣檢測方法，其核心是一個具同向/反向轉運規則的組織P系統。系統將原始圖像的每個像素對應一個基本膜，使用轉運規則實現各基本膜間的對象交換與共享，并將表層膜作為輸出膜。該算法主要對強度函數的梯度方向進行逼近，基于梯度進行邊緣的檢測，因此，提取的輪廓具有較好的連續性。本文從檢測效果與處理時間兩個方面將GP算法與經典邊緣檢測算子Canny算子、Sobel算子進行比較，GP算法表現出較好的有效性和并行處理能力。

參考文獻

[1] P?un G.Computing with Membranes[J].Journal of Computer and System Sciences,2000,61(1):108-143.

[2] Freund R,P?un G,Perez-Jimenez M J.Tissue P systems with channel states[J].Theoretical Computer Science,2005,330(1):101-116.

[3] P?un A,P?un G.Small universal spiking neural P systems[J].Biosystems,2007,90(1):48-60.

[4] Dassow J,Paun G.On the power of membrane computing[J].Journal of Universal Computer Science,2004,5(2):33-49.

[5] Freund R,P?un A.Membrane systems with symport/antiport rules universality result[J].New Generation Computing,2004,22(4):331-347.

[6] Paun G.P systems with active membranes:attacking NP complete problem[J].Journal of Automata and Combinatorics,2001,6(1):75-90.

[7] Cabarle F,Adorna,Martfnez-del.Amor M A Simulating Spiking Neural P Systems Without Delays Using GPUs[J].International Journal of Natural Computing Research,2011,2(2):19-31.

[8] Ciobanu G,P?un G,MjPerez-jimenez.Applications of membrane computing[M].Berlin:Springer-Verlag,2005.

[9] Pena Cantillana F,Diaz-Pernil D,Christinal H A,et al.Implementation on CUDA of the Smoothing Problem with Tissue-Like P Systems[J].International Journal of Natural Computing Research,2011,2(3):25-34.

[10] Christinal H A,Diaz-Pernil D,Jurado P R.Using Membrane Computing for Obtaining homology groups of Binary 2D Digital Images[J].Lecture Notes in Computer Science,2009,585(2):383-396.

[11] Díaz-Pemil D,Gutiérrez-Naranjo M A,Real P.A New Way to Obtain Homology Groups in Binary 2D Images using Membrane Computing[C]//XII Encuentro de Algebra Computacionaly Aplicaciones EACA 2010.Santiago de Compostela,Spain:Universidadede Santiago de Compostela Publicacións,2010:107-112.

[12] Martin-Vide C,P?un G,Pazos J,et al.Tissue P systems[J].Theoretical Computer Science,2003,296(2):295-326.

[13] P?un G.Membrane Computing An Introduction[M].Berlin:Springer-Verlag Berlin and Heidelberg GmbH & Co.K,2002:111-112.

[14] 陳彥燕,王元慶.常用邊緣檢測算法的定量比較[J].計算機工程,2008(9):202-204.

中圖分類號TP391.41

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.039

收稿日期：2014-06-30。國家自然科學基金項目(61325019)；浙江省教育廳科研課題(Y200907175)。謝佩軍，副教授，主研領域：計算機控制與自動化，計算機視覺與圖像處理。計時鳴，教授。