一种基于元胞自动机变换的图像边缘检测方法

1、收稿日期:2007210212作者简介:金军(19702,女,讲师,博士生,从事计算机应用、数字图像处理研究;e 2mail :jsjxxqj 。第26卷第1期2008年2月石河子大学学报(自然科学版Journal of Shihezi University (Natural Science Vol.26No.1Feb.2008文章编号:100727383(20080120113204一种基于元胞自动机变换的图像边缘检测方法金军(四川大学计算机学院,四川成都610065摘要:提出了一种新的基于元胞自动机变换的图像边缘检测方法。应用二维元胞自动机,首先确定合适的二维变换基函数,然后对图像进行元胞

2、自动机变换,将变换系数进行子带编码,再根据基函数的性质,分离出变换系数中的高频部分,最后经过反变换得到图像的边缘信息。此算法简单实用,仿真实验结果较好。关键词:边缘检测;元胞自动机;元胞自动机变换中图分类号:TP391文献标识码:A 边缘是图像对视觉的最主要的特征。边缘检测是图像处理的关键,广泛应用于轮廓、特征的提取、纹理分析等领域,所以在图像识别和分析中,物体边缘的检测和提取技术一直深受学者们的关注。元胞自动机变换提供了一种把已知的现象和元胞自动机演化联系起来的直接方法,本文把元胞自动机模型引入到图像处理中,提出了一种新的基于元胞自动机变换的图像边缘检测方法。1元胞自动机元胞自动机(cell

3、ular automata ,C A 13是描述自然界复杂现象的一种简化数学模型,可以定义为在一个由离散、有限状态的元胞组成的元胞空间上,并按照一定局部规则,在离散的时间维上演化的动力学系统。元胞自动机模型是以20世纪50年代冯诺依曼为模拟生物学中的自我复制而提出的。20世纪80年代W olfram 3对一维C A 模型做了深入全面的研究。但是关于C A 的基本理论从数学上深入研究十分困难,目前还处在通过大量的计算机实验来获得经验性规律和寻求具体应用的阶段,同时也出现了不少相关的应用39。元胞自动机按其元胞空间的维数可分为一维C A 、二维C A 和三维C A 。1个k 个状态的一维C A由1

4、行元胞组成,每个元胞的状态取0到k -1的任意1个整数值,局部规则控制r 邻域内m 个元胞在离散时间里同步演化,我们称之为k 个状态、m 个邻居的元胞自动机;二维C A 不同于一维C A 的是,它是一个均匀的网格,网格形状可以是三角形、正方形和六边形,为便于计算机实现,通常把网格限制为有限大小,运用周期边界来解决格子有限问题,邻域类型通常是Von Neumann 型或M oore 型,如图1所示,黑色元胞为中心元胞,灰色元胞为其邻居。最简单的一维C A 的元胞个数为3,每个元胞的状态值取0或1。设a it 、a i -1t 、a i +1t 分别表示第i 个、i -1个、i +1个元胞在t 时

5、刻的状态,在指定的局部规则下,可以根据t 时刻第i 个元胞的2个邻居的状态计算出t +1时刻第i 个元胞的状态。元胞自动机的演化过程可以表示为:a it +1=F (a i 21t ,a it ,a i +1t ,其中F 是布尔函数定义的局部规则。一个状态数是2,邻居个数是3的自动机,每个邻居有 23=8个可能的构型。按照W olfram 对规则的定义:R =67n =0C n 2n,(1式(1中,R 是0到255之间的1个整数,表示规则,C n 是第n 个构型通过规则作用产生的布尔值。图1二维元胞自动机的邻域类型2元胞自动机变换元胞自动机变换(cellular automata trans

6、form, C AT由Olu Lafe4提出,目前已应用于数据加密、解密和图像压缩10。在元胞空间中选择1个合适的局部规则,将其作用于元胞自动机的状态演化域,从而产生1个“正交”的变换基函数(也称为C A滤波器,可对数据或图像进行元胞自动机变换。基函数由一系列的“结构块”组成,也称为“元素”或“变换基”。C AT能演化出大量不同性质的基函数,有些基函数所表现出的自生功能的性质是其它变换(如小波变换所无法比拟的4,这些基函数可以适应一些特定问题的要求。例如在图像的边缘检测中,我们可以选择这样的基函数A,利用A对图像进行C AT,能得到图像的高频系数。应用C AT来建立模型,方法和传统的变换(傅立

7、叶变换、拉普拉斯变换和小波变换相同。假如数据序列f i表示1个图像,f是定义在物理网格空间上的函数,我们希望寻找定义在C A网格空间网格k上的基函数A和与基函数相关的变换系数C。C AT可表示为如下公式:f i=6kC k A ik,(2C k=6if i B ik。(3在物理网格i上的每一个点都有一个相应的基函数A(跨越整个C A空间。式(2表示从过程f(在物理域到系数C(在C A域的一个映射,这个映射将基函数A作为传递函数。在许多应用中,人们试图得到一些变换系数C,使这些系数具有原函数f不具备的性质,或者能够揭示函数f在物理域中没有被观察到的性质。例如,在数据压缩中,可以通过C A T揭示

8、原始数据的冗余,变换系数C中具有无意义或零的元素的数量,揭示了由C A检测到的冗余的程度。有大量不同性质的基函数存在,C AT的实质是,对于一个特定的问题,总能找到一个合适的C A,它由其动力学系统参数确定。C A按照给定的系统参数进行离散时间演化,演化域被映射成变换基(即“结构块”,即针对特定的问题,总能够得到期望的基函数和变换系数。典型的元胞自动机系统参数见表1。对于N个元胞组成的一维元胞自动机,有无穷多种方法可以将A ik表示成C A状态演化a it(其中, i,t=0,1,2,N-1的函数。对于二值状态C A,Olu Lafe4给出了7类正交基函数,其中T ype2型类非窗口C A基函

9、数为:A ik=2ikki-1。(4表1元胞自动机系统参数K ey Description1在定义好的邻居范围内,元胞相互作用的规则2每个元胞允许的状态范围3每个邻居内的元胞个数4整个网格总共的元胞个数5元胞的初始构型6元胞的边界构型7元胞空间或结构的形状8元胞空间的维度9元胞自动机变换的种类10元胞自动机的基的类型3二维元胞自动机在由N×N个元胞组成的二维元胞空间中,设变换基AA ijkl,其中,i,j,k,l=0,1,N-1,数据序列f ij(i,j=0,1,N-1的C AT可表示为:f ij=6N-1k=06N-1l=0C kl A ijkl,(5其中,i,j=0,1,2,N-

10、1,c kl是变换系数。我们称A ijkl为二维基。有二种产生二维基的方式:由二维C A状态演化得到;由一维C A的基衍生得到二维C A的基:A ijkl=A ik A jl。本文采用第二种方式产生一种类二维基(T ype8型基:A ijkl=L w(ikki+jlljm od L w-(L w-1(6其中,L w2是C A的状态数。当元胞状态取0或1时,L w=2,则T ype8型二维基A ijkl可由T ype2型一维基A ik演化计算得到。目前,对C A T的研究还处于初级阶段,并没有像小波基那样提出具体的命名基函数。本文基于边缘检测的目的,需要找到有利于获取图像高频系数的A ijkl,

11、经过多次实验,选择了C A系统参数(表2。表2产生Type8型A ijkl的CA系统参数元胞自动机的基类型T ype8块的大小8规则号43初始构型01111110边界构型循环(cyclic演化出的64×8×8的基函数为见图2,其中A00kl 表示左上角的块,最上面一行表示0j<8,i=0;最左边一列表示j=0,0i<8。A ij00表示每一个小块的左上角点,白色代表1(加,黑色代表-1(减。411石河子大学学报(自然科学版第26卷 图2 类Type 8型二维基函数对应的变换公式为:C kl =67i =067j =0f ij A jikl /8,(7f ij =

12、67k =067l =0C kl A jikl /8。(84基于元胞自动机变换的边缘检测图像元胞自动机变换的许多特性可以在变换系数中得到体现。对一幅图像进行C A T ,得到的变换系数C 划分成高频部分和低频部分,高频部分反映的是图像的边缘变化与分布,代表图像的边缘信息,因此利用C A T 的高频系数分量可以得到图像的边缘11。假设w 、h 为图像f 的长宽,满足w =2n ,h =2m ,n 、m 都是整数。如果图像的长宽不满足上述条件,则采用填充0的方法补充。a :一级C AT 变换系数b :二级C AT 变换系数图3CAT 变换系数的分解设A 为N ×N 的二维基函数,图像f

13、的长度为L ,首先将f 分割成L/N 个不重叠的分割块:f i =6N -1k =0C kj A (i m odN k,(9其中,i =0,1,2,L -1,j =0,1,2,(L/N -1。再将每个分割块划分成2(m +n /64个子块,子块由8×8个像素组成。对每个子块利用如图2所示的A ijkl 进行C A T 变换 ,将得到的变换系数ckl 进行子带编码,分解成、4个子带:处于k 和l 都是偶数位置上的系数属于子带,处于k 是偶数l 是奇数位置上的系数属于子带,处于k 是奇数l 是偶数位置上的系数属于子带,处于k 和 l 都是奇数位置上的系数属于子带(图3a 。根据二维基的性

14、质,4个子带系数又分为二组:一组为低频系数,另一组为高频系数。低频系数存储了大量的原图像信息,将低频系数分离出来进行IC A T 变换可形成与原始图像近似的低分辨率图像,大小为2(n -12(m -1,可再次对其进行C A T 变换,得到的变换系数再分解成4个子带(图3b ;将高频系数分离出来进行IC A T 变换形成原始图像的边缘图像。5仿真实验对图4a 的256×256的灰度图像按上述方法进行一级C AT ,得到4个子带系数,根据本文所用的A ijkl 的性质,子带的系数是图像的低频系数,子带、的系数是图像的高频系数。分离出图像的低频系数进行IC AT ,形成的原始图像的低分辨率

15、近似图像(图4b 。a :原始图像b :低分辨率近似图像图4原始图像与低频近似图像分离出图像的高频系数进行IC AT ,形成原始图像的边缘图像,并与传统的边缘检测算子得到的边缘图像进行比较(图5。从实验的仿真结果可以看到,C A T 检测到的图像边缘比较细腻,边缘定位比较准确,丢失的边缘信息少,视觉效果也较好,是一种实用的边缘检测方法。a :prewitt 算子边缘图像;b :roberts 算子边缘图像;c :s obel 算子边缘图像;d :log 算子边缘图像;e :本文C AT 边缘图像图5边缘图像511第1期金军:一种基于元胞自动机变换的图像边缘检测方法6小结本文提出了一种新的基于元

16、胞自动机变换的图像边缘检测方法,在未作其它处理的情况下,仅利用C AT变换系数的高频部分来检测图像边缘,取得了初步结果。仿真实验结果显示,C AT的边缘检测结果优于大多数传统的边缘检测算子的检测结果,并且C AT方法所运用的C A模型及运算操作都很简单,避免了大量的计算,是一种实用的图像处理方法,其有效性使其具有良好的应用前景。本文因只单纯的利用了变换系数的高频部分进行边缘检测,所以该方法对噪声较为敏感。我们下一步的工作就是继续对二维C A及C AT进行研究,以期提高本文算法的抗噪性和提取边缘的连续性。参考文献:1谢惠民.复杂性与动力系统M.上海:上海科技教育出版社,1994.2祝玉学.物理系

17、统的元胞自动机模拟M.北京:清华大学出版社,2003.3W olfram S.Theory and Applications of Cellular AutomataM.S ingapore:W orld Scientific Publishing C ompany,1986.4Olu Lafe.Cellular automata trans forms:Theory and applicationsin multimedia compression,encryption,and m odelingM.Bos2 ton D ordrecht London:K luwer Academic Pu

18、blishers,2000. 5李才伟.元胞自动机及复杂系统的时空演化模拟D.武汉:华中理工大学,1997.6叶瑞芳,黄春晖.基于摩尔近邻模型的二维元胞自动机在图像处理中的应用J.现代电子技术,2006,(8:55257.7张传武.细胞自动机及其理论研究进展J.贵州大学学报,2004,21(3:2892293.8A K Das,A G anguly,A Dasgupta,et al,E fficient characteris2ation of cellular puter simulation,Digital comput2 ers and computationJ.IEE Proceedi

19、ngs,1990,137(1:81287.9Amr Badr.An alternative cellular automata cryptogramJ.S tudies in In formatics and C ontrol,2002,11(4:3392347. 10Olu Lafe.Data compression and encryption using cellular au2tomata trans formsJ.Engng Applic Artif Intell,1997,10(6: 5812591.11唐良瑞.基于小波高频分量的边缘检测方法J.北方工业大学学报,2002,14(1:13216.A Method of Edge DetectionB ased on Cellular Automata TransformsJ I N Jun(C ollege of C omputer Science,S ichuan University,Chengdu,S ichuan610065,ChinaAbstract:A new edge detection method based on cellular autom