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

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

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

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

?

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

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

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

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

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

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

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)中抽象出來(lái)的計(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ì)算自提出以來(lái)，便受到眾多研究者的廣泛關(guān)注，涵蓋數(shù)學(xué)、計(jì)算機(jī)科學(xué)、人工智能、計(jì)算機(jī)圖形學(xué)、自動(dòng)控制等諸多學(xué)科，成為一個(gè)非?；钴S的研究領(lǐng)域。

關(guān)于膜計(jì)算的研究大致分為3類：理論研究、應(yīng)用研究和P系統(tǒng)的軟硬件研究。理論研究主要研究各類計(jì)算模型的建立，并分析其計(jì)算能力和計(jì)算有效性，計(jì)算能力分析P系統(tǒng)是否具有圖靈等價(jià)性[4,5]，而計(jì)算有效性主要分析其解決NP等問(wèn)題的可能性[6]；P系統(tǒng)的軟硬件研究主要關(guān)注于仿真軟件系統(tǒng)的實(shí)現(xiàn)或研發(fā)硬件處理器實(shí)現(xiàn)相關(guān)計(jì)算模型[7]；P系統(tǒng)的應(yīng)用研究主要是利用各種模型求解信息安全、自動(dòng)控制、數(shù)字圖像處理、經(jīng)濟(jì)學(xué)等方面的實(shí)際問(wèn)題[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ī)制，將其用于圖像處理過(guò)程中的邊緣檢測(cè)，以擴(kuò)展膜計(jì)算的應(yīng)用范圍和開(kāi)發(fā)新的圖像處理方法。基于P系統(tǒng)的相關(guān)特性，并應(yīng)用于圖像邊緣檢測(cè)。提出了一種P系統(tǒng)計(jì)算模型下的基于梯度的圖像邊緣檢測(cè)算法，該算法通過(guò)P系統(tǒng)的各種轉(zhuǎn)運(yùn)規(guī)則自動(dòng)實(shí)現(xiàn)輪廓提取，充分利用了P系統(tǒng)的并行計(jì)算能力。

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

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

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

其中，Γ是字母表，其元素被稱為對(duì)象；Σ是輸入字母表；μ是由n個(gè)膜組成的膜結(jié)構(gòu)；wi(1≤i≤n)表示μ中的區(qū)域i所包含的對(duì)象多重集；R是有限的規(guī)則集，其中的Ri對(duì)應(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)化膜中對(duì)象產(chǎn)生新的對(duì)象多重集；運(yùn)用轉(zhuǎn)運(yùn)規(guī)則能夠?qū)崿F(xiàn)各基本膜之間對(duì)象的交換與共享。

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

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

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

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

2.2算法流程

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

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

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

1) 初始化階段

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

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

2) 逼近梯度階段

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

(3) 梯度逼近根據(jù)上步選取的方向，對(duì)于每個(gè)像素aij(膜(i，j))，選用3×3鄰域范圍內(nèi)的6個(gè)像素(4種選擇方式，圖2是其中一種)對(duì)強(qiáng)度函數(shù)的梯度方向進(jìn)行逼近。運(yùn)用轉(zhuǎn)運(yùn)規(guī)則2，實(shí)現(xiàn)各個(gè)膜中對(duì)象的進(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)過(guò)上階段，實(shí)現(xiàn)對(duì)強(qiáng)度函數(shù)的梯度方向逼近。最后，需要將各個(gè)基本膜中經(jīng)過(guò)轉(zhuǎn)運(yùn)與進(jìn)化的對(duì)象，通過(guò)轉(zhuǎn)運(yùn)規(guī)則3相應(yīng)地發(fā)送到表層膜膜0，替換膜0中的初始對(duì)象(原始圖像)。此處，轉(zhuǎn)運(yùn)規(guī)則3實(shí)現(xiàn)將各個(gè)基本膜(i,j)中相應(yīng)對(duì)象發(fā)送至表層膜膜0(即輸出膜)，其形式為：((i,j)，u/λ,0)，1≤i≤n,1≤j≤m。

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

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

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

3.1邊緣檢測(cè)的定性分析

實(shí)驗(yàn)平臺(tái)硬件配置CPU Intel i5-2450m，2.5 GHz，64位操作系統(tǒng)，顯卡AMD Radeon HD 6470m。本文針對(duì)100幅不同特點(diǎn)、不同數(shù)據(jù)量的醫(yī)學(xué)MRI圖像進(jìn)行實(shí)驗(yàn)，分析比較三種算子的處理時(shí)間與檢測(cè)效果，得到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í)間差值越來(lái)越大，但Sobel算子與GP算子的處理時(shí)間差值相對(duì)較小，說(shuō)明當(dāng)數(shù)據(jù)量增大時(shí)，GP算子的并行處理能力開(kāi)始體現(xiàn)優(yōu)勢(shì)。

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

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

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

圖4　Heart_1檢測(cè)效果

圖5　Heart_2檢測(cè)效果

圖6　Brain檢測(cè)效果

圖7　Chest檢測(cè)效果

3.2邊緣檢測(cè)的定量分析

本文采用一種基于邊緣連接程度的評(píng)價(jià)方法，比較分析上述三種邊緣檢測(cè)算法。按4-連通成分?jǐn)?shù)B、8-連通成分?jǐn)?shù)C及其比值C/B三個(gè)指標(biāo)對(duì)邊緣檢測(cè)效果進(jìn)行定量評(píng)價(jià)。4-連通成分是指若某像素的4-領(lǐng)域內(nèi)存在與之連通的像素，則稱為一個(gè)4-連通成分，同理可得8-連通成分。C/B比值反映了邊緣的連接程度，邊緣線形的連接程度可反映出邊緣的錯(cuò)檢、漏檢?？捎蓴?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值最大，說(shuō)明其邊緣線形的連接程度最差，邊緣的錯(cuò)檢、漏檢最多；GP算法的C/B最小，說(shuō)明其邊緣線形連接程度最好，邊緣的錯(cuò)檢、漏檢少，邊緣提取效果最佳。

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

4結(jié)語(yǔ)

本文提出的采用P系統(tǒng)模型進(jìn)行基于梯度的邊緣檢測(cè)方法，其核心是一個(gè)具同向/反向轉(zhuǎn)運(yùn)規(guī)則的組織P系統(tǒng)。系統(tǒng)將原始圖像的每個(gè)像素對(duì)應(yīng)一個(gè)基本膜，使用轉(zhuǎn)運(yùn)規(guī)則實(shí)現(xiàn)各基本膜間的對(duì)象交換與共享，并將表層膜作為輸出膜。該算法主要對(duì)強(qiáng)度函數(shù)的梯度方向進(jìn)行逼近，基于梯度進(jìn)行邊緣的檢測(cè)，因此，提取的輪廓具有較好的連續(xù)性。本文從檢測(cè)效果與處理時(shí)間兩個(gè)方面將GP算法與經(jīng)典邊緣檢測(cè)算子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] 陳彥燕,王元慶.常用邊緣檢測(cè)算法的定量比較[J].計(jì)算機(jī)工程,2008(9):202-204.

中圖分類號(hào)TP391.41

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

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

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