一種基于膜計(jì)算的梯度邊緣檢測算法

謝佩軍　計(jì)時(shí)鳴

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

2(浙江工業(yè)大學(xué)　浙江 杭州 310014)

?

一種基于膜計(jì)算的梯度邊緣檢測算法

謝佩軍1計(jì)時(shí)鳴2

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

2(浙江工業(yè)大學(xué)浙江 杭州 310014)

摘要針對傳統(tǒng)邊緣檢測算法的不足，提出一種以組織型P系統(tǒng)為框架的梯度邊緣檢測算法。采用一個兩層膜結(jié)構(gòu)，即表層膜與基本膜，使用轉(zhuǎn)運(yùn)規(guī)則實(shí)現(xiàn)各基本膜間的對象交換與共享。該算法逼近強(qiáng)度函數(shù)的梯度方向，基于梯度進(jìn)行邊緣的檢測，并通過經(jīng)典邊緣檢測算子的對比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明所提出的邊緣檢測方法具有較好的有效性。

關(guān)鍵詞膜計(jì)算組織型P系統(tǒng)邊緣檢測梯度

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引言

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

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

本文主要研究膜計(jì)算的相關(guān)特性和機(jī)制，將其用于圖像處理過程中的邊緣檢測，以擴(kuò)展膜計(jì)算的應(yīng)用范圍和開發(fā)新的圖像處理方法?；赑系統(tǒng)的相關(guān)特性，并應(yīng)用于圖像邊緣檢測。提出了一種P系統(tǒng)計(jì)算模型下的基于梯度的圖像邊緣檢測算法，該算法通過P系統(tǒng)的各種轉(zhuǎn)運(yùn)規(guī)則自動實(shí)現(xiàn)輪廓提取，充分利用了P系統(tǒng)的并行計(jì)算能力。

1組織型P系統(tǒng)

一般地，一個度為n的組織型P系統(tǒng)可表示為如下結(jié)構(gòu)[12]：

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

其中，Γ是字母表，其元素被稱為對象；Σ是輸入字母表；μ是由n個膜組成的膜結(jié)構(gòu)；wi(1≤i≤n)表示μ中的區(qū)域i所包含的對象多重集；R是有限的規(guī)則集，其中的Ri對應(yīng)于μ中膜i的規(guī)則；iΠ是系統(tǒng)的輸入?yún)^(qū)域；io是系統(tǒng)的輸出區(qū)域。

組織型P系統(tǒng)的規(guī)則集主要包括兩類規(guī)則：進(jìn)化規(guī)則和轉(zhuǎn)運(yùn)規(guī)則[13]。運(yùn)用進(jìn)化規(guī)則能夠進(jìn)化膜中對象產(chǎn)生新的對象多重集；運(yùn)用轉(zhuǎn)運(yùn)規(guī)則能夠?qū)崿F(xiàn)各基本膜之間對象的交換與共享。

2基于P系統(tǒng)的邊緣檢測算法

2.1膜結(jié)構(gòu)

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

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

2.2算法流程

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

2.3P系統(tǒng)計(jì)算過程

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

1) 初始化階段

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

圖1　像素aij4對鄰域像素構(gòu)成的方向

2) 逼近梯度階段

(1) 構(gòu)造方向?qū)τ?基本膜(i，j))像素aij，構(gòu)造其4對鄰域像素構(gòu)成基本膜(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) 選取方向?qū)ι鲜?對領(lǐng)域像素值分別作差分運(yùn)算，并取其絕對值，保留絕對值最大的像素對，選取該像素對表示的方向。

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

圖2　3×3鄰域像素

3) 輸出階段

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

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

3實(shí)驗(yàn)結(jié)果與分析

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

3.1邊緣檢測的定性分析

實(shí)驗(yàn)平臺硬件配置CPU Intel i5-2450m，2.5 GHz，64位操作系統(tǒng)，顯卡AMD Radeon HD 6470m。本文針對100幅不同特點(diǎn)、不同數(shù)據(jù)量的醫(yī)學(xué)MRI圖像進(jìn)行實(shí)驗(yàn)，分析比較三種算子的處理時(shí)間與檢測效果，得到3種算子的處理時(shí)間與圖像數(shù)據(jù)量關(guān)系曲線，如圖3所示。

圖3　處理時(shí)間與圖像數(shù)據(jù)量關(guān)系曲線

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

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

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

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

圖4　Heart_1檢測效果

圖5　Heart_2檢測效果

圖6　Brain檢測效果

圖7　Chest檢測效果

3.2邊緣檢測的定量分析

本文采用一種基于邊緣連接程度的評價(jià)方法，比較分析上述三種邊緣檢測算法。按4-連通成分?jǐn)?shù)B、8-連通成分?jǐn)?shù)C及其比值C/B三個指標(biāo)對邊緣檢測效果進(jìn)行定量評價(jià)。4-連通成分是指若某像素的4-領(lǐng)域內(nèi)存在與之連通的像素，則稱為一個4-連通成分，同理可得8-連通成分。C/B比值反映了邊緣的連接程度，邊緣線形的連接程度可反映出邊緣的錯檢、漏檢?？捎蓴?shù)學(xué)歸納法證得C/B值越小時(shí)，邊緣線形連接度越好，因而能夠證明邊緣的提取效果越好[14]。

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

表2　邊緣圖統(tǒng)計(jì)數(shù)據(jù)

4結(jié)語

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

參考文獻(xiàn)

[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].計(jì)算機(jī)工程,2008(9):202-204.

中圖分類號TP391.41

文獻(xiàn)標(biāo)識碼A

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

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