英语原文共 17 页，剩余内容已隐藏，支付完成后下载完整资料

---

线性二维、零边界、九邻域细胞自动机的理论和应用

摘要:本文涉及二维、九邻域、零边界、统一以及混合线性规则的细胞自动机在图像处理中的理论及应用。这些规则根据受影响细胞的周边细胞的数量分为九组。已经发现所有统一规则根据它们所属的组复制给定图像的多个副本，其中混合规则还表征为给定图像的放大，缩小，加粗和稀疏的现象。此外，使用混合CA规则开发了一种称为扫描算法的新的搜索算法，其被发现适用于模拟许多跨学科研究领域，例如生物体向单点目的地迁移，单吸引器和多吸引器细胞自动机理论，模式分类和聚类问题，图像压缩，加密和解密问题，密度分类问题等等。

关键词：细胞自动机,，布尔函数，线性规则， 问题矩阵， 图像处理

1引论

细胞自动机（CA）已成为一个非常有用的概念。它使自然界中许多事件的理解更加容易。尽管约翰·冯·诺伊曼[4]提出这一概念已有50年，但只有在过去二十年里，各个领域的研究人员才开始对这一概念产生兴趣。半导体技术正在向亚微米时代迈进，系统设计人员尝试将软件领域的复杂功能嵌入硅片上的硬件块。 在这样做的同时，在复杂性的可行限制之内，设计人员被迫寻找简单，模块化，可级联和可重复使用的构建块来实现各种复杂功能。 在这种情况下，细胞自动机（CA）是满足上述所有目标的正确选择。 此外，越来越多的对更快计算的需求需要采用并行处理架构。 各种作者已经证明[1,2]，围绕细胞自动机机器（CAM）构建的并行处理架构非常适合于各种应用。

Wolfram等人[5]在多项式代数的帮助下研究了一维CA。 Pries等人[8]研究了基于类似类型的多项式代数展示组属性的一维CA。后来，Das等人[9]在矩阵代数的帮助下扩展了一维CA的表征。 Packard等人[10]报道了一些关于二维五邻域CA的实证研究。 Chowdhury等人[11]把一维CA的矩阵代数理论扩展到二维CA。然而，重点放在特殊类的加性二维CA，被称为限制垂直邻域（RVN）CA。在这类二维CA中，垂直邻域被限制在上方或下方，但不能同是上方和下方。 [3,6]中报道了一些特定的统一和混合二维CA线性规则的特征和应用。 Olu Lafe [12]使用细胞自动机变换（CAT）进行数据压缩和加密。后来Ikenaga等[7]研究了使用高度平行的二维CA寄存器进行实时形态处理。 C. D. Thomas在他的论文[13]中研究了用于图像处理的细胞自动机的演变。 Maji等人[14]研究了使用矩阵理论和特征多项式的用于模式分类的加法一维细胞自动机规则的理论和应用。

使用矩阵本文提供了一些额外的二维CA线性规则理论，并且涉及到上面讨论过的不同作者报告的一些应用。这需要引入二维九邻域CA以及影响单元依赖关系的规则。第二节中，这种规则在问题矩阵上应用被证明是形成图像处理的基础。第3节，介绍了512个线性布尔函数，其矩阵构造，结构和它们的属性在均匀以及混合CA中的研究。在第4节中，讨论了这些线性规则对给定图像的影响。特别地，这些规则用于图像转换，例如平移，将一幅图像复制为多幅图像，放大和缩小，图像增厚和变薄。虽然可以在任何任意图像上执行平移和复制，但是对于其他变换则需要结构化图像。任意图像的多个副本，如此可用，可以在现实生活中找到无数的应用。在第5节中，使用混合CA规则开发了称为扫描器算法的新算法，其被发现适用于许多重要的跨学科研究领域。 在本文中，转换，地图和规则可互换使用。

2二维CA的数学模型

在二维九邻域CA中，特定单元的下一状态受其自身的当前状态和其最近邻域中的八个单元（也称为Moore邻域）的影响，如图1所示。这样的影响由各种规则考虑。为了简单起见，在本节中，我们仅考虑线性规则，即仅可以通过异或运算实现的规则。这里采用的具体规则约定如下：

64	128	256
32	1	2
16	8	4

图-1

中心框表示当前单元（即正在考虑的单元），并且所有其他框表示该单元的八个最近邻。每个框内的数字表示当前小区对该特定邻居的影响的规则编号。规则1表征中心小区对自身的依赖性，而仅对其顶层邻居的依赖由规则128表征，等等。 这九个规则被称为基本规则。在小区具有对两个或更多个相邻小区的依赖性的情况下，规则编号将是相关小区的编号的算术和。例如，二维规则171（128 32 8 2 1）指向5个邻居，分别是上下左右和其自身。包括无依赖性邻居的规则总共有512种组合。（）

这些规则以下面的方式被分组成九个组。N = 1,2 ... 9的组N指当前单元在9邻域中的依赖于几个。类似地，可以获得属于其他组的规则。 可以注意到，存在于规则的二进制序列中的1的数目与其组编号相同。

2.1 统一和混合CA

上一节中提到的线性规则的应用可以在问题矩阵上实现，其中每个元素是0或1。可以提及的是，除了对问题矩阵的每个元素应用相同的规则，还可以允许在不同的元素上同时应用不同的规则。前者表征统一CA，后者表征混合CA.

例2.2. (统一CA)

在图2中，规则170（2 8 32 128）被统一地应用于具有空边界条件（边界外邻域单元看作状态0）的问题矩阵（3times;4）的每个单元。

[图-2：显示正在考虑的单元格，将通过添加其4个正交相邻单元格的状态来改变其状态。 0 1 1 1 = 1。 类似地，规则170被应用于所有其他细胞。]

例2.3. (混合CA)

这里是在空边界条件中的混合CA的示例，其中在上述问题矩阵中的3个不同行（分别为第一，第二和第三行）中应用3个规则（规则2，规则3和规则4）。

图-3

可以在优雅的数学模型的帮助下分析二维CA行为，其中我们使用两个基本矩阵来获得单元的行和列依赖性。使二维二进制信息矩阵表示为，其表示利用特定规则配置的二维CA的当前状态。任何单元的下一状态将通过与规则相关联的其相关邻居的状态的异或运算来获得。与不同规则相关联的全局变换可以通过以下两个基本矩阵变得有效，在本文的其余部分中称为和：

图-4

2.2 二维CA特征

为了方便分析，我们将每个规则转换为由表示的变换矩阵。我们想要看看用变换矩阵，对当前CA状态X（维度（mtimes;n）的二进制矩阵）操作生成的下一个CA状态X#39;（ mtimes;n）。 公约如下[1]，[8]：

引理2.1：任何规则R的等价一维映射矩阵可以表示为三对角二进制矩阵如下：

[图-5：其中D、L、U是n*n的矩阵，其形式为下列几种之一：[0]，[I]，[]，[]，[I ]，[I ] S]和[I S]，其中S是和的和]

规则矩阵(mn*mn)用于乘由二维矩阵（m*n）生成的1维列矩阵（mn*1）来实现CA的变换。[1][2][8]

3规则矩阵及其属性

3.1 512个线性布尔函数

令L是512线性布尔规则的集合。我们可以在布尔线性规则集中定义操作，规则mn = k。L是交换群，其中每个成员是其自身的逆元。任何成员L可以唯一地表示为基本线性规则的和，如以下示例所示。

定理3.1：由于每个数字都有唯一的二进制表示，所以表达式是唯一的。

3.2 统一规则及其特征

3.2.1 统一CA的规则矩阵结构

如果问题域是（mtimes;n）的二进制矩阵，则规则矩阵为（mntimes;mn）维。令M i表示规则i的规则矩阵，其中i = 0,1,2,3 ... 511。 因此，M1 =规则1的规则矩阵，M2 =规则2的规则矩阵等等。

下面的两个定理用示例指出了在所有512个线性规则矩阵中找到的模式。

定理-3.2：当布尔规则由规则矩阵表示时，对应于基本布尔规则的矩阵被发现以下面的方式彼此相关。

并且可以借助于两个操作来从这5个基本规则矩阵中生成其他规则矩阵，一个用转置T表示，另一个用模2加法表示。

观察引理2.1中使用的不同类型的矩阵，我们构造了两个二进制序列和如下：

其中，n为给定问题矩阵中的列数。

定理3.3：5种基本矩阵具有如下的特定结构。

M1 =主对角线包含所有#39;1#39;，所有其他元素为#39;0#39;。

M2 =超对角元素以类似的顺序排列，所有其他元素为#39;0#39;。

M4 =（n 1）个对角元素以类似S1的顺序排列，并且所有其他元素为#39;0#39;。

M8 =第n个对角线包含所有的#39;1#39;，所有其他元素为#39;0#39;。

M16 =（n-1）个对角元素以类似于S2的顺序排列，并且所有其他元素为#39;0#39;。

上述两个观察，定理2和定理3帮助我们生成所有511线性规则矩阵，这种构造方法比在前面的文献[1]和[2]中提到的要简单得多。

推论3.2.1：除M1外，其他4个基本矩阵{M2，M4，M8，M16}是对角线元素都为0的下三角矩阵，因此通过定理3.2，四个基本矩阵{M32，M64，M128，M256} 是对角线都为0的上三角矩阵

3.2.2非奇异规则矩阵

由于规则矩阵必然是方矩阵，称为可逆CA [14]的非奇异规则矩阵值得密切研究，因为非奇异矩阵必须产生在模式分类，聚类，加密和解密，数据压缩等方面具有可列举应用的循环状态转换图。

规则1是可逆的，因为M1是非奇异的，并且与M1组合的矩阵在其对角元素中包含1，也变成非奇异的。 因此，使用规则1形成的规则也是可逆的。 在512个规则矩阵中，以下31个规则对于任意输入矩阵（mtimes;n）总是可逆的。

3.2 混合CA规则及其特征

3.3.1 混合CA规则矩阵的结构

如在部分2中讨论的混合CA是其中每个细胞具有其自己的本地规则，其可以不同于任何其他细胞的本地规则。可以观察到，与应用于具有阶数（mtimes;n）的项0或1的二进制矩阵的线性布尔规则对应的阶数（mntimes;mn）的规则矩阵的数量为512。但是，具有项0或1的阶（mntimes;mn）的矩阵的总数是。问题出现在哪些规则矩阵对应。为了找到这样的问题的答案，以下面的方式引入混合矩阵的概念。将规则3应用于（2times;2）意味着，这里该规则应用于每个元素，因此，它是如下所示的9个变量的函数。

但是，当将规则3应用于整个矩阵（2times;2）时，实际上我们在矩（4times;4）上运用（在边界中添加两行和两列），因此， 这种情况规则3是一个超过16个变量的函数。

定义3.1（混合矩阵）

与混合CA规则对应的矩阵被称为混合矩阵。

我们知道所有512线性布尔规则的行为及其矩阵构造。 例如规则2的规则矩阵也可以以另一种方式构造，并且这种新技术将帮助我们研究涉及混合CA或非均匀CA的所有可能的混合矩阵的行为。

假设例如规则2被应用于（3times;3）的问题矩阵，则：第一单元通过查看第二单元的状态来改变其状态。 第二个单元通过查看第三个单元格的状态来改变其状态。 第三单元通过查看矩阵中不存在的单元来改变其状态，因此，我们处理零边界条件时，其边界状态为“0”。 第4个细胞通过查看第5个细胞的状态来改变其状态。 第5个细胞通过观察第6个细胞来改变其状态。 第6个单元通过查看矩阵中不存在的单元来改变其状态，因此其状态为“0”。 第七个细胞通过观察第六个细胞来改变其状态。 第8个细胞通过观察第6个细胞来改变其状态。 第9个单元通过查看矩阵中不存在的单元来改变其状态，因此其状态为“0”。 根据规则2的定义，在这里给出，我们可以构建规则2的规则矩阵，其为（9times;9）的阶数。

规则2矩阵的构建：

（9times;9）矩阵的第一行可以从第一个单元的行为构建。 如前面关于规则2的应用所述，第一小区的状态受第二小区的状态的影响。 因此，在规则矩阵的第一行中，只有第2个位置为1，该行中的其他元素为0。

在（9times;9）矩阵的第二行中，只有第3位是1，其他是0。类似地构造其他行，并且整个规则矩阵以图形方式示出。 一般来说，问题矩阵的第i个单元对应于规则矩阵的第i行，第i行中的位置1取决于影响第i个单元格的问题中的单元位置。这里，规则2是一个统一的规则，因为所有的单元行为完全相同的方式（改变发生，由于其右手边的单元格）。 但是上面讨论的构造规则对于混合线性规则是相同的。

反向操作也可以是给定任何任意矩阵（mntimes;mn），应该能够告诉（mtimes;n）的每个单元如何变化。 这里，第i个单元取决于mtimes;n矩阵的那些位置，其中，（mntimes;mn）矩阵的第i行恰好包含值1。

在前面的章节中，我们已经讨论了所有线性规则的数学属性，这些线性规则主要与我们的图像处理工作相关。

4在图像处理中的应用

本文报道的用于图像处理工作的二维CA线性规则为根据我们在第2节中所示的分类，这些规则属于第1组规则。此外，在复制图像的情况，使用来自不同组的二维CA线性规则。

为了在图像处理中应用二维CA线性规则，我们采用大小为（100times;100）的二进制矩阵。 我们将矩阵的每个元素映射到屏幕上的唯一像素，我们以白色0和黑色1为矩阵元素。 这是如何在（100times;100）像素的区域内绘制图像的方式，我们通过用红色对其边界着色来指示。 我们对（100x100）矩阵（在正则和某些情况下是混合形式）应用二维CA线性规则，并且每当使用改变的矩阵应用规则并且重绘新的图像。 通过以合适的方式使（100times;100）矩阵的一些元素为1来获取初始图像。 我们将这个初始图像称为“种子图像”

全文共7536字，剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[144483]，资料为PDF文档或Word文档，PDF文档可免费转换为Word