谢佩军　计时鸣

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系统的各种转运规则自动实现轮廓提取，充分利用了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)。谢佩军，副教授，主研领域：计算机控制与自动化，计算机视觉与图像处理。计时鸣，教授。