（应用数学专业论文）基于元胞自动机变换的图像处理方法.pdf

中文摘要 摘要 元胞自动机变换为我们提供了一个将己知现象和元胞自动机演化联系起来的 直接方法它将物理网格空间上的每个点通过元胞自动机变换基映射到元胞自动 机空间上，通过元胞自动机空间上的变换系数揭示出物理空间中很难观察到的性 质元胞自动机变换最大的优势是能产生大量的不同性质的基函数，这些基函数 可以适应已知问题的各种特性，为图像压缩、数据加密、求解积分方程等方面的 应用提供一个良好的平台 本文先对元胞自动机变换的发展情况和元胞自动机变换的基本方法作了简要 的介绍，在此基础上把元胞自动机变换应用到图像处理中首先，应用元胞自动 机变换来对图像进行分类通过选择适当的正交基，利用元胞自动机变换系数所 反应的能量值，来描述整幅图像的本质属性，从而达到按照物理属性对图像进行 分类的目的其次，我们将元胞自动机变换在噪声类型识别方面进行了尝试，通 过选择适当的正交基，利用元胞自动机变换系数高频子带的能量分布特点，对任 意图像中最常出现的两类噪声高斯噪声和椒盐噪声进行了识别 另外，我们还将元胞自动机变换和目前常用于正交变换编码中的小波变换、 离散余弦变换、沃尔什一哈达玛变换从能量集中率角度对变换的性能进行了比较， 并用这几种变换方法分别对图像进行压缩在相同的压缩比下，比较了压缩后图 像的均方误差 关键词：元胞自动机变换；图像分类；噪声识别；能量集中率 英文摘要 i m a g ep r o c e s s i n gm e t h o d b a s e do nc e l l u l a ra u t o m a t at r a n s f o r i l l a b s t r a c t c e l l u l a ra u t o m a t at r a n s f o r m sp r e s e n tam o r ed i r e c tw a yo fa c h i e v i n gt h el i n k a g e b e t w e e nag i v e np h e n o m e n o na n dt h ee v o l v i n gc af i e l d ，i tm a p se a c hp o i n to nt h e p h y s i c a ls p a c 霉i n t oc e l l u l a ra u t o m a t ad o m a i nu s i n gt h eb a s i sf u n c t i o n so fc a t h e t r a n s f o r mc o e f f i c i e n t si nc af i l e dr e v e a lf e a t u r e sn o to b s e r v e di nt h ep h y s i c a ld o m a i n t h eh u g en u m b e ro ft r a n s f o r mb a s e sa v a i l a b l ea n dv a r i e dn a t u r ei sam a j o rs t r e n g t ho f t h e s ec at r a n s f o r m t h e s ec a nb ea d a p t e dt ot h ep e c u l i a r i t i e so fag i v e np r o b l e ma n d p r o v i d e da l le x c e l l e n tp l a t f o r mf o ri m a g ec o m p r e s s i o n ，d a t ae n c r y p t i o na n ds o l u t i o no f i n t e g r a le q u a t i o n s t h ep a p e rb r i e f l yi n t r o d u c e st h eb a s i ct h e o r ya n dt h ed e v e l o p m e n to fc e l l u l a r a u t o m a t at r a n s f o r ma n dw ea p p l yi ti nt h ei m a g ep r o c e s s i n g f i r s t l y ，w ea p p l i e dt h e c e l l u l a ra u t o m a t at r a n s f o r mt oi m a g ec l a s s i f i c a t i o na n dt h e nt h ed e s c r i p t i o no fi n t r i n s i c c h a r a c t e r i s t i c s ，w h i c hi sa c h i e v e db yu s i n gt h ea p p r o p r i a t eo r t h o g o n a lb a s e sa n de n e r g y v a l u ep r e s e n t e db yt h ec e l l u l a ra u t o m a t at r a n s f o r mc o e f f i c i e n t s ，l e a dt ot h es u c c e s si n i m a g ec l a s s i f i c a t i o nb a s e do nt h ep h y s i c a lf e a t u r eo fi m a g e s e c o n d l y ，w ea t t e m p t e dt o a p p l yt h ec e l l u l a ra u t o m a t at r a n s f o r mt oi d e n t i f y i n gt h et y p eo fi m a g en o i s e u s i n gt h e a p p r o p r i a t eo r t h o g o n a lb a s e sa n de n e r g yd i s t r i b u t i o np r e s e n t e db yt h eh i g hf r e q u e n c y c o m p o n e n t so fc e l l u l a ra u t o m a t at r a n s f o r m ，l e a dt ot h es u c c e s si nd i s c r i m i n a t i n g g a u s s i a na n dt h es a l t p e p p e rn o i s e o t h e r w i s e ，w ec o m p a r e dt h ec a p a b i l i t yo fc e l l u l a ra u t o m a t at r a n s f o r mw i t ht h a to f d i s c r e t ec o s i n et r a n s f o r m ，w a v e l e tt r a n s f o r ma n dw a l s h h a d a m a r dt r a n s f o r mi ne n e r g y c o m p a c t i o ne f f i c i e n c ya s p e c t t h e nc o m p r e s s i n gi m a g ea n dc o m p a r i n gt h er e c o n s t r u c t i o ni m a g e sm s ev a l u eu s e dt h ed i s c r e t ec o s i n et r a n s f o r m ，w a v e l e tt r a n s f o r m ， w a l s h h a d a m a r dt r a n s f o r ma n dc e l l u l a ra u t o m a t at r a n s f o r n l k e yw o r d ：c e l l u l a ra u t o m a t at r a n s f o r m ；i m a g ec l a s s i f i c a t i o n ；n o i s ei d e n t i f i c a t i o n ； e n e r g yc o m p a c t i o ne f f i c i e n c y 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博士硕士学位论文 ：基王丞照自动扭变逸的图傻丝堡友洼：。除论文 中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文 中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公 开发表或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名；年月 同 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于：保密口 不保密口( 请在以上方框内打“”) 论文作者签名： 基丁元胞白动机变换的图象处理方法 引言 元胞自动机( c e l l u l a r a u t o m a t a ，又称细胞自动机，简称c a ) 是一种有自组织行 为的时空离散、状态离散的并行数学模型1 9 4 8 年v o n n e u m a n n 首先提出了元胞 自动机的思想【1 1 ，t 9 5 0 年s t a r t u l a m 和v o n n e u m a n n 共同找到了作为实现复杂系 统的离散模型的媒介元胞空间，1 9 7 0 年英国剑桥大学的数学家j h c o n w a y 编 制了著名的“生命游戏”程序( 该程序通过设定几条简单的演化规则，元胞在网 格中就能产生无法预测的延伸、变形和停止等复杂的演化结果) ，此后有关元胞 自动机的研究引起了人们广泛的关注到了1 9 8 3 年，s w o l f r a m 引入动力系统的 理论和方法，对元胞自动机进行了系统的研究，用熵来描述其演化，并将元胞自 动机按动力学行为分类1 2 2 1 ，掀起了学术界研究元胞自动机的高潮 2 0 世纪9 0 年代，一些工程师丌始致力于研究如何将元胞自动机模型运用到实 际中去特别地，英国工程师o l u l a f e 提出的元胞自动机变换( 简称c a t ) 理论， 为我们提供了一个将已知现象和元胞自动机演化联系起来的直接方法 元胞自动机变换的本质就是寻找具有特定性质的与元胞自动机状态演化有关 的基函数，并且利用这样的基函数作为转换函数，将物理网格空i 日j 上的每个点映 射到元胞自动机空i 、日j 上o l u l a f e 的研究表明，元胞自动机能够产生成千上万的令 人惊奇的讵交基、半证交基、双币交基和非j 下交基其中一些基函数具有与己知 变换( 如：沃尔什变换、小波变换等) 的基相似的性质，还有一些基函数则反映 出了数掘集合或函数的自组织性质利用基函数的这些性质，元胞自动机变换可 以应用到一些领域，进行相应的算法设计例如： ( 1 ) 在数字图像压缩领域：由于元胞自动机可以产生上亿个基函数，因此总能 找到一个元胞自动机变换基，使得在这个基下元胞自动机变换的非零系数尽可能 地少这样，图像经过元胞自动机变换后，不重要系数的数量最大，编码重要系 数所需要的比特数最少，压缩后的数掘具有很高的保真度同时，利用元胞自动 机变换，还可以根掘不同的需要对图像进行对称压缩和不对称压缩 ( 2 ) 在数掘加密领域：大量的元胞自动机变换基可以毫无错误的对数掘进行编 码，为数掘加密提供了一个极好的方法密钥由用来产生元胞自动机变换基的全 引言 部关键值组成用元胞自动机变换系数柬代替原始数掘进行传输和储存要想对 密文进行破译，只能通过加密时使用的全部关键值来完成 ( 3 ) 在计算数学领域：大量的元胞自动机变换基具有正交性和数掘变换的能 力，为解积分方程提供了一个极好的平台积分方程的核被变换到元胞自动机空 i 甘j 在元胞自动机空i 日j 中，得到的矩阵是罩稀疏的、带状的，而且又具有鲁棒性 和可逆性的性质 目前，对元胞自动机变换的讨论还处于仞始阶段，相关的文献并不多，许多 研究工作仍是尝试性的本文对元胞自动机变换在图像处理领域的应用也进行了 尝试性的探讨： 首先，本文尝试着将元胞自动机变换应用于图像分类的研究中通过选择适 当的正交基，利用元胞自动机变换系数所反应的能量值，来描述整幅图像的本质 属性，从而达到按照物理属性对图像进行分类的目的 其次，本文提出了一种基于元胞自动机变换域的图像噪声类型识别的方法这 个方法不需要任何先验知识，就能够对任意图像中最常出现的两类噪声高斯 噪声和椒盐噪声j 挂行识别 最后，本文将元胞自动机变换和常见于图像压缩的几个证交变换从能量集中 率的角度进行了比较由于元胞自动机变换具有数掘压缩能力，其它一些正交变 换，如离散余弦变换、小波变换、沃尔什一哈达玛变换，也具有数据压缩能力， 并均可用于图像压缩，因此，从变换的能量集中率角度可以对它们的性能进行比 较，在相同的压缩比下，比较压缩后图像的均方误差 基于元胞自动机变换的图象处理方法 第1 章元胞自动机变换 1 1 元胞自动机理论 元胞自动机是时间空间都离散的动力学系统散布在规则格网中的每个元胞 取有限的离散状态，依据确定的局部规则同步更新不同予一般的动力学模型， 元胞自动机不是由严格定义的物理方程或函数确定的，而是用一系列模型构造的 规则构成的凡是满足这些规则盼模型都可以看作是元胞自动机模型因此，元 胞自动机是一类模型的总称其特点是时间、空耐、状态都离散，每个变量只取 有限多个状态，且其状态改变的规则在时间和空间土都是局部的 元胞自动机由元胞、元胞的状态空间、邻居及局部规则四部分组成的元胞 是元胞自动机的最基本的组成部多捧分布在离散自争一维、二维或多维欧几里德空 间的格点上而元胞所分布的空间网格集合就是元胞空问对于一维元胞自动机， 元胞空间的划分只有一种如图1 1 所示 图1 1 一维元胞自动机空间 f i g1 1o n e - d l m e m l o n a lc e l l u l a rs p a c e 而高维的元胞自动机，元胞空间的划分可能有多种形式对予常见的二维元 胞自动机，二维元胞空间可按三角、四方或六边形网格排列在大多数情况下用 正方形网格描述，如图1 2 ，少数情况下可以选择三角形或六边形网格形式 理论上元胞空闻在各维上是无限的，但却无法在计算机上实现，因此定义不 同的边界条件，把网格限制在有限的大小内本文采用周期型边界条件来解决格 子有限的问题以上的元胞及元胞空间只表示了系统的静态成分，为将“动态” 引入系统，必须加入演化规则在元胞自动机中，这些规则是定义在空间局部范 围内的，即一个元胞下一时刻的状态决定于本身状态和它的邻居元胞的状态因 而，在指定规则之前，必须定义一定的邻居规则，明确哪些元胞属于该元胞的邻 居 第1 章元胞自动机变换 在一维元胞自动机中，通常以半径来确定邻居距离一个元胞内的所有元胞均被 认为是该元胞的邻居二维元胞自动机的邻居定义较为复杂，但通常有以下几种 形式( 我们以最常用的规则四方网格划分为例) ，如图1 3 ，黑色元胞为中心元胞， 灰色元胞为其邻居，利用中心元胞及其邻居元胞的状态一起来计算中心元胞在下 一时刻的状态 图1 2 元胞自动机四方网格空间 f i g1 2t w o - d i m e n s i o n a ls q u a r e ：l a t t i c ec e l l u l a rs p a c e 图1 3 胞自动机的邻居类型 f i g 1 3c e l l u l a r a u t o m a t a n e i g h b o r h o o d 初等元胞自动机是状态集s 只有两个元素( 0 ，1 ) ，邻居半径，= l ，邻居个 数拧= 3 的一维元胞自动机，是最简单的元胞自动机模型。a 。t ，a 。t ，a 。r 分别 表示在时刻t 第f 个元胞、第卜1 个元胞和第t + 1 个元胞的状态如果我们指定一 个规则f ，在这个规则之下，可以根据，时刻第f 个元胞的状态及两个邻居元胞的 状态计算出f + l 时刻第1 个元胞的状态所有元胞的状态是同时发生变化的，元胞 自动机的演化过程可以下面的形式来表达： 基丁i 元胞白动机变换的幽象处理方法 口，+ ，= r ( a 一，口。口，。) 其中f 是元胞自动机的局部规则出于所有不同的局部规则共有2 8 = 2 5 6 种，所以 在参考文献 2 和e 3 中，s w o l f r a m 根掘其局部规则对初等元胞自动机编号进 行了深入研究他将一维二相邻的元胞按可能出现的状态排序，由于是二相邻的， 再加上本身，共有3 个元胞，8 种可能状态，因此可以对每种状念的演化结果进行 编码，如表1 1 表1 1 元胞白动机演化规则 t a b 1 1c e l l u l a ra l l t o m a t ar u l e 这罩c ， 0 ，1 ，f = 1 ，2 ，3 ，7 由c oc l c 2 c 3 c 4 岛c 6 c 7 构成的二进制数所对应的十 进制数就是这种规则的编码在w o l f r a m 规则的定义中，用整数r 代表规则： 7 r = c 。2 ” ( 1 2 ) n 。0 因此，r 代表0 到2 5 5 之间的一个整数如表1 2 所示的规则1 4 袭1 2 规则1 4 1 a b 1 2r u l e1 4 例如，一个状态集s 只有两个元素( 0 ，1 ) ，邻居半径，= 1 ，邻居个数咒= 3 的初等元胞自动机初始构型为1 1 0 1 0 1 0 0 ，周期边界条件下，从t - - - 0 时刻到t = 7 时刻的演化过程如表1 3 第1 章元胞白动机变换 1 2 元胞自动机变换 元胞自动机变换( 简称c a t ) 提供了一种把元胞自动机理论和数学、物理、 工程等联系起来的工具【4 1 元胞自动机变换的主要优势就是可以得到大量不同性质 的基函数，有些基函数所表现出的再生功能是其他变换( 如小波变换) 所无法比 拟的，它们能够适应一些特定问题的要求例如，在数字图像压缩中，我们可以 选择一些基，它们能使元胞自动机变换的系数中零的个数最少应用元胞自动机 变换来建立模型，方法和传统的变换( 傅立叶变换和拉普拉斯变换) 相同从元 胞自动机的状念演化中可以很容易地获得变换的基函数，计算过程也不像在传统 的气格子模型【5 】中那样需要大量的元胞参与 1 2 1 元胞自动机变换方程 假如一个过程( 如信号、图像等) 用一个数掘序列，来表示，厂是定义在物 理网格空l 、日j 中网格i 上的函数我们希望寻找定义在元胞自动机网格空间( 频率空 问) 中网格k 上的变换系数c 和基函数a ，使得 厂= q a 。 ( 1 3 ) k 变换系数c 的值由逆变换得到： q = ，取 ( 1 4 ) 墓丁元胞自动机变换的幽象处理方法 其中，b 是a 的逆( 1 3 ) 式称为元胞自动机变换 式( 1 3 ) 表示了从过程厂( 在物理域) 到系数c ( 在元胞自动机域) 的一个 映射，这个映射将基函数4 作为传递函数在许多应用中，人们试图得到一些变 换系数c ，使这些系数具有原函数厂不具备的性质，或者能够揭示函数厂在物理域 中没有被观察到的性质例如，在数据压缩中，可以通过变换揭示原始数掘的冗 余变换系数c 中具有无意义或零的元素的数量，揭示了由元胞自动机检测到的冗 余的程度 元胞自动机变换的实现和十个关键值( 见表1 4 ) 密不可分的这些关键值的 选择将决定接下柬变换的性质在许多应用中，一些关键值( 如：3 ，4 ，7 ) 都是 固定不变的，其余的关键值是可变化的元胞自动机变换的精髓就是找到元胞自 动机的规则( 由十个关键值决定的) ，通过这些规则可以得到具有我们所希望性 质的基函数和变换系数元胞自动机变换的主要优势就是能产生大量的性质不同 的基函数 表1 4 元胞白动机大键值表 t a b i 4d e s c r i p t i o no f c ag a t e w a yk e y s d e s c r i p t i o n 在定义盯的邻居范用内，元胞相且作州的规则 每个元胞允许的状态范围 每个邻居内的元胞个数 档个网格的总共的元胞个数 元胞的初始构型 元胞的边界构刑 元胞空间或结构的形 元胞空间的维度 元胞自动机变换的种类 元胞白动机的基的类掣 ：至l一。o。o，o。m 第1 章元胞白动机变换 1 2 2 元胞自动机变换基 元胞自动机变换的基与元胞自动机演化域( 元胞自动机的状态) 有关它的 一些特征包括： ( 1 ) 从元胞自动机状态演化得到基的方法 ( 2 ) 基函数的币交程度( 完全f 交、半正交、双正交、非萨交) ( 3 ) 计算变换系数的方法 最简单的基是由两个状态的元胞自动机演化得到的，其中的项都是整数 - 1 ，1 】 称之为一基有些基中的项是由元胞自动机演化域中即时点的密度得到的，我们 称之为t 9 一基有些基函数中的项是由元胞自动机演化域中多个元胞平均密度得到 的，称之为一b a s e s s 一基( 由上述三种基得到的) 通常是非证交的，对于数据 的自组织变换来说是极好的基 一维元胞自动机空间为产生元胞自动机变换基提供了一个最简单的环境它 的优势如下： 对于邻居个数少，元胞状念数多的元胞自动机，可以产生易于处理的字母 表基这在数掘压缩应用中是很强的优势 可以通过一维基的结合得到高维基函数 一维元胞自动机的理论知识比较完善 在一维元胞自动机空间中，变换基a z a 。 f ，k = o ，1 ，n - 1 考虑一个数掘 序歹0 ，( o ，l ，2 ，- ，n 一1 ) ，贝0 ： 一1 ：= q a m i = o 1 2 , - - - , n - 1 ( 1 5 ) k = 0 在( 1 5 ) 中，唧是变换系数有很多方法可以把a 。表示成= 口。( f = 0 , 1 ，2 ，n 1 ) 的函数，其中就包括我们下面提到的由两个状态的元胞自动机演化得到基的方法 t y p e1 t y p e 2 ： t y p e 3 ： a = 2 a m 一1 a = 2 a 。k d b 一1 a * = u m t n 墓丁元胞白动机变换的图象处理方法 舻击，孙 f 1 l ： ，+ 【，一n t y p e a ： a l k = p l k p h p i k = 2 a - 一1 + p , k 4 m o d l , o j o = 2 a * - 1 m o d l 。，其中l 。2 是一个整数 t y p e6 ： a m = u t “ z * = “ _ + a o - k 吼= l + 吼 在大多数的应用中，我们希望基函数是币交的如果基函数a 。满足： 熟耻恬蓦 6 ， 其中屯( 七= 0 ，l ，一1 ) 是系数，则称a 。是讵交的，于是很容易得到变 换系数： q 一1 u - f , 彳，i ，：0 表1 5 列举了能够产生一维正交t y p e 2 型基的一些元胞自动机的关键值表 1 6 是规则1 4 ，初始构型1 1 0 1 0 1 0 0 ，元胞个数为8 的元胞自动机产生的一维正交 基 一 一 一 中其 掣 矿扩扩 第1 章元胞白动机变换 表1 5 t a b 产生t y p e 2 型元胞白动机的基的芙键值 i 5g a t e w a yv a l u ef o rd u a l - c o e f f i c i e n tb a s e s 表1 6 规则1 4 ，初始构删为1 1 0 1 0 1 0 0 的元胞白动机变换基 t 曲1 6b a s i sf u n c t i o no f r u l e1 4c a 七o234567 - 1 0 - + + + - + + - + - - + - + + + + - - + - + - + + + + - + + 一 + _ + - + - + + + - + - + _ + + - + - + + 斗一，山o2 3 4 5 6 7 基丁元胞白动机变换的图象处理方法 第2 章图像的元胞自动机变换 2 1 二维元胞自动机变换 在由n 个元胞组成的二维元胞空间中，设变换基彳= 一州， ( f ，_ ，女，z = 0 , 1 ，n - 1 ) ，则数掘序列( f ，= o ，i ，2 ，一1 ) 可由元胞自动机变换表 示成： ( f ，= 0 , i ，2 ，n 一1 ) ( 2 1 ) 其中是变换系数我们称a u u 为二维基有两种方式可以产生二维基【6 】： ( 1 ) 由二维空间元胞自动机演化的状态得到基函数这罩，a 。是由o ；口， o ，t = o , 1 ，2 ，一1 ) 得到的 ( 2 ) 由一维元胞自动机的基产生二维元胞自动机的基：彳，删= 爿。a “ 本文采用的基是第二种方式产生的一类特殊的二维基t y p e 8 型基，即 a 耻，= 上。敝， 口“+ 口，口口) m o d l 。 一0 。一1 ) ( 2 2 ) 其中，三。2 是元胞自动机的状态数我们选择一组元胞自动机的关键值用来产 生t y p e 8 型的二维的币交的基关键值见表2 1 ，产生的基函数图像见图2 1 表2 1 产生t y p e 8 型墓的元胞臼动机笑键值 t a b 2 1c ag a t e w a yv a l u e 元胞臼动机荩的类掣 块的人小 规则 初始构刑 边界条什 t y p e 8 8 1 4 1 1 0 1 0 1 0 0 周期刑 盯 屯 = 第2 章幽像的元胞臼动机变换 幽2 1 ：t y p e 8 喇一维基函数其中山w 是块的左上角，最上面 一行表示0 ， 8 ，j = 0 ；晟左边一列表示，= 0 ，0 j 8 ； a m ，表示左上角小块中的左上角的小块，向块代表1 ( 加) ， 黑快代表- - 1 ( 减) f i g 2 1t y p e 8t w o - d i m e n s i o n a l4 0 0 “i sab l o c ka tt h ee x t r e m eu p p e r l e f tc o m e r t h e l e f tc o l u m n i s 20 ，0 j 8 ；a ，0 0i s t h eu p p e r c o m e ro f e a c hb l o c k t h ew h i t er e c t a n g u l a rd o t sr e p r e s e n t1 ( a d d i t i o n ) w h i l et h eb l a c kd o t sa l e 1 ( s u b t r a c t i o n ) 2 2 元胞自动机变换的子带编码 子带编码是元胞自动机变换的一个特性，也是目i j i 许多已有的变换( 如小波 变换) 的特性它将一个信号分解成高频分量和低频分量，为进行数掘序列的多 分辨率分析提供了一个工具例如，给定一个长度l = 2 ”( g 是一个整数) 的一维 数据序列_ ，：我们首先选择这个序列的m 个部分将其变换，得到的系数分为储存， 偶数位詈的系数存放一组，奇数位霄的系数存放一组偶数位冒的组第二次被变 换得到2 ”个系数把2 ”。个系数再次分成偶数位冒的组和奇数位冒的组，奇数位 霄的组加到上一步得到的奇数位霄的组，偶数位晋的组第三次被变换这个过程 基丁元胞白动机变换的幽象处理方法 一直持续到剩余的偶数组和奇数组的长度为2 最后2 个属于奇数组的系数 加到所有奇数位置系数的集合中，最后 2 个偶数位置的系数就是序列经变换后 的低频部分在这个分级过程的最后得到了2 “个系数如果需要恢复原始数掘， 只要将上述过程逆过来：首先将2 个高频系数和u 2 个低频系数按照原来的奇 数位冒和偶数位置交替排列形成个系数将这个系数做第一次逆变换，又得 到个系数经第次逆变换后得到的个系数就是下一次逆变换静的偶数位置 的系数，它和奇数组中的基数系数形成2 n 个系数再将2 n 个系数进行逆变换， 直至原始数掘得到完全恢复 2 3 图像的元胞自动机变换 设给定图像的尺寸为w ， w = 2 ”，h = 2 “ ( 2 3 ) 其中m ，n 都是证整数如果给定图像的尺寸不满足( 2 3 ) ，则通常采用填充0 的方法来处理根据上述假设，原始图像被分成2 ( m + n ) 1 6 4 个子块，每个子块由8 8 = 6 4 个象素组成对每个子块实施元胞自动机变换，变换基采用t y p e 8 型二维 基函数( 如图2 1 ) ，根掘元胞自动机的子带编码，则变换系数c 。，落在四个不同的 子带中在k 和，都是偶数的位置上的系数( i ) 是元胞自动机变换系数的低频部 分，这些系数被分离出来形成一幅新的低分辨率的图像，其尺寸为2 ( n 一1 ) 2 ( m 1 ) ； 其余的系数( i i ：k 是偶数，是奇数；i i i ：k 是奇数，l 是偶数；i v ：k 是奇数， 是奇数) 都是元胞自动机变换系数的高频部分，如图2 2 所示高频部分可以提供 图像的边缘信息，低频部分形成的低分辨率图像，可以进一步经过元胞自动机变 换再分成2 ( m + n - 2 ) 6 4 个子块之后将得到的变换系数再分成4 组，如图2 3 对 于一幅图像，由于它的尺寸是2 的整数次幂，所以逐级变换可以一直进行下去， 直到i 仅仅包括1 6 个元素对于每一个子块： = ( 砉委厶一叫 卢，= ( 砉砉4 卢 c 2 m 第2 章幽像的元胞白动机变换 l - z - 1回 同 同 l 二二j 幽2 2 元胞白动机变换系数分解成4 个子带 g r o u pi 就是低频分苗g r o u pi i ，l i i ，i v 是高频分苗 f i g 2 2d e c o m p o s e sc a tc o e f f i c i e n t si n t of o u rb a n d s g r o u pii se q u i v a l e n tt ot h el o wf r e q u e n c yc o m p o n e n t s g r o u pi i ，i ，i va r et h eh i g hf r e q u e n c yc o m p o n e n t s 囡回 国团 幽2 3 在第2 层分解中，幽2 2 中的g r o u p1 分肇被进步元胞白动机变换分解成另外4 个组 f i g 2 3t h ei m a g ef o r m e db y g r o u p ic o m p o n e n ti nf i g ，2 2i sf u r t h e r c a td e c o m p o s e da n ds o r t e di n t oa n o t h e rg r o u p sa tt h el o w e rr e s o l u t i o n 1 4 基丁元胞白动机交换的幽象处理方法 第3 章基于元胞自动机变换的图像分类方法 目前的图像处理方法，如边缘检测、提取纹理特征、图象增强以及图象分割 等等，大部分是针对特定的目的、孤立使用的特定方法人们在应用这些方法时， 往往忽视特定的约束条件和对图像整体的把握，如用扶度阈值分割一个纹理图像、 用恢复算法恢复一个没有模糊的图像等等造成这种情况的原因是多种多样的， 其中一个重要的原因是缺乏对图像本质属性的认识，不能对图像进行分类处理因 此，在对图像进行任何处理之前，应该根掘图像所具有( 或包含) 的物理属性， 对整幅图像的本质属性予以客观的掐述，对图像进行适当的分类，以便预先了解 图像是否可压缩或可分割，图像是否需要恢复等等【刀 然而，根据不同的处理目的对图像基本属性进行分析研究的并不多文献 8 】、 9 】和【1 0 】在像素层面上对图像进行了分类，但是这些研究并没有进一步就面向 某一图像处理目的，对整幅图像进行分析与研究针对客观描述整幅图像本质属 性的必要性和可能性，文献【7 】和【1 1 】进行了系统的讨论在研究了图像小波高 频系数的基础上，提出了面向图像压缩的图像分类新概念，按图像的边缘度对图 像进行分类，从而利用该分类结果可对图像的压缩结果进行预测 元胞自动机变换提供了一种把己知的现象和元胞自动机演化联系起束的直接 方法，已经被应用于图像与多媒体压缩、数据加密和偏微分方程求解等方面 4 - 6 1 我 们应用元胞自动机变换束对图像进行分类通过选择适当的正交基，利用元胞自 动机变换系数所反应的能量值，来描述整幅图像的本质属性，从而达到按照物理 属性对图像进行分类的目的 3 1 图像的属性 对于一般的图像处理来说，关于图像属性可以有一个统一的观点，即图像属 性分为物理的和几何( 或结构) 的物理属性包括灰度特性( 强度、分御和变化 情况等) 和噪声特性( 类型、强度和分白等) 几何属性包括区域特性( 整体和 分区的狄度分布和纹理特性等) 和边缘特性( 类型、强度和方向等) 在这一分 析的基础上，r a n 等根掘心理学研究指出，图像是由不同知觉意义的三部分组成的， 即平滑区、边缘区和纹理区l 住1 如果狄度变化比较平缓，则属于平滑区：如果灰 第3 章基r 元胞白动机变换的剀像分类方法 度变化比较剧烈，则属于边缘区；边缘区内边缘的密度是区分边缘区和纹理区的 依掘【i i 】 按照这一观点，可将图像按人们的视觉特点进行简单分类，如图3 1 所示其 中( a ) 为纯纹理图，该图只含有纹理区：( b ) 的两幅图只包含边缘区和纹理区； ( c ) 的两幅图包含平滑、边缘、纹理三部分：( d ) 的图像只包含平滑和边缘区， ( e ) 为纯平滑图 图( a ) 纯纹理幽( t e x t u r e 2 t e x t u r e a ) f i g ( a ) p u r et e x t u r ei m a g e 幽( b ) 纹理边缘幽( b r i d g e ，b a b o o n ) f i g ( b ) t e x t u r e e d g ei m a g e 基丁元胞白动机变换的幽象处理方法 幽( c ) 平滑边缘纹理图( 1 e n d , b o a t s ) f i g ( c ) s m o o t h e d g e t e x t u r ei m a g e 圈( d ) 平滑边缘幽( e i g h t ，m o o n ) f i g ( d ) s m o o t h e d g ei m a g e 幽( e ) 纯平滑幽( g r a y l 9 6 ) 幽3 1 平滑区、边缘区、纹理区不同的图像对比 f i g 3 1c o m p a r i s o no f s m o o t hi m a g e ，e d g ei m a g e ，t e x t u r ei m a g e 1 7 第3 章基丁元胞白动机变换的幽像分类方法 3 2 基于元胞自动机变换的图像分类原则 在对图像基本属性进行分析研究中，图像边缘具有重要的意义，因为边缘是 图像最基本的特征，是图像的本质属性图像的边缘不仅反映了图像的狄度统计 信息，还反映了图像的空j 日j 分布信息和结构信息本质上，图3 1 中给出的血种图 像类型( 按照物理属性的分类) ，都是由图像中边缘的分布来决定的图像元胞 自动机变换的许多特性可以在变换系数中得到体现在相同的尺度空问下，主要 的变换系数“聚集”在图像的灰度突变的区域，即边缘区域，而这种“聚集”的 程度恰好与图像区域中边缘分御的密集程度相对应因此，利用元胞自动机变换 这种检测突变的能力，可以检测图像的边缘分却情况 将一幅图像进行元胞自动机变换后，得到的系数分成高频部分和低频部分高 频部分反映的是图像边缘的变化与分布，代表了图像的边缘信息，因此利用元胞 自动机变换的高频部分就可以对图像边缘进行度量 我们选择2 6 幅实验图像( 见附录) ，逐幅进行了一层元胞自动机变换将每 幅图像元胞自动机变换系数的高频部分取平均值( 平均能量) 作为度量指标，进 行统计和分析，得到的结论如表3 1 到表3 4 由表中给出的结果可以看出，利用 图像元胞自动机变换，对于任意给定的图像，我们可以对其按照物理属性进行分 类，分类的原则为：当指标值大于1 4 时，为纯纹理图像；当指标值介于3 和1 4 之间时，为纹理边缘图像或者纹理边缘平滑图像，当指标值介于l 和3 之i 甘j 时， 为边缘平滑图像；当指标值小于1 时，为纯平滑图像 表3 1 高频系数的平均值介丁1 4 和1 9 之间的幽像集 t a b 3 1r a v e r a g eo f h i g hf r e q u e n c yc o e f f i c i e n tb e t w e e n1 4a n d1 9 墓丁：元胞白动机变换的图象处理方法 图像名称 高频系数均值 图像名称 高频系数均值 a l u m g m s 1 6 5 7 5 p o u t 2 5 2 7 7 s a t u m 1 ，6 6 1 7 e ；g h t 2 8 9 6 6 m o o n 1 9 5 9 9 表3 4 幽像类别和高频系数值 t a b 3 4t y p ea n dh i 曲f r e q u e n c yc o e f f i c i e n t so f i m a g e s 1 9 第4 章基丁元胞白动机变换的嵘卢识别方法 第4 章基于元胞自动机变换的噪声识别方法 图像在生成和传输过程中常常会受到各种噪声源的干扰和影响而使图像质量 变差1 1 3 】图像处理的一项重要任务是有效滤除图像噪声又不模糊图像目前的图 像去噪算法在实施前都假设噪声的类型是已知的【j 4 - 1 8 1 ，只有明确了噪声的类型， 爿能根据类型选择方法比如高斯噪声，其零均值的特点需要使用像素的局部平 均抑止噪声；对于脉冲噪声，需要特别的非线性滤波器进行去噪处理然而，在 图像处理过程中图像受到的是何种类型的噪声干扰往往是未知的，如果在这种情 况下盲目地对噪声图像进行去噪处理将达不到任何效果，因此在对图像进行噪声 处理之前，对图像噪声的类型进行识别是必要的这样既避免了图像去噪过程的 盲目性，也可利于去噪算法的自动选择与改进 目前，对图像噪声识别的研究并不多文献 1 1 给出了一种基于小波域的 图像噪声类型识别的方法，它不需要任何先验知识就能够对任意图像中最常出现 的两类噪声高斯噪声和椒盐噪声进行识别，并在此基础上进一步得到高 斯噪声的方差估计和椒赫噪声的密度估计本章借鉴了文献 1 1 中的方法，通 过选择适当的正交基，利用元胞自动机变换系数高频子带的能量分卸特点，对高 斯噪声和椒盐噪声进行识别 4 1 基于元胞自动机变换的噪声识别原则 图像经过元胞自动机变换后，变换系数具有良好的能量集中特性，即图像的 能量主要集中在低频子带，而高频子带系数幅度较小、能量较低，很大程度上是 噪声【l9 】进步研究我们发现：图像经元胞自动机变换后的高频子带的系数能 反映图像受干扰噪声的类型以l e n a 图为例，分别加入标准差为2 0 的高斯噪声和 密度为2 0 的椒撩噪声，这两种噪声图像经元胞自动机变换后高频子带的系数 有以下特点：受高斯噪声干扰图像的高频子带系数中不显著系数( 系数中占有 小部分能量的绝对值较小的系数) 较多，而受椒哉噪声干扰图像的高频子带系 数中不显著系数较少根掘这个特点，可以用系数能量对噪声类型进行识别 基于元胞自动机变换的噪声类型识别包含以下几部分： ( 1 ) 对图像进行元胞自动机变换，得到噪声图像的元胞自动机分解高频系数 基于元胞自动机变换的图象处理方法 ( 2 ) 对该系数的能量集中程度进行度量 ( 3 ) 根据能量集中程度识别图像所受到的是高斯噪声还是椒盐噪声的干扰 4 1 1 系数的能量集中程度 对系数的能量集中程度进行度量之前，首先要将元胞自动机变换系数分为显 著和不显著两大类 设h h 系数矩阵为 d ( f k )( f ，k 一2 0 ，2 1 ，2 “ m t 厅) ) ，按系数幅值( 绝对 值) 的大小可将不显著的系数提出： d r ( f ，k ) 一 d q ，七) ， l d ( 1 ，k ) l o 8 时可断定图像受 到高斯噪声的干扰，能量比e r 0 8 时图像受高斯噪声的干扰，能量比e r o 8 时图像 受椒哉噪声的干扰 表4 1t = o 1 7 5 时含小高斯噪声幽像的e r t a b 4 1 弘0 1 7 5 ，e ro f s m a l lg