元胞自动机.doc

元胞自动机-1- 元胞自动机(Cellular Automata ,简称 CA) ,是一时间和空间都离散的动力系统。散布在规则格网中的每一元胞取有限的离散状态, 遵循同样的作用规则, 依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。不同于一般的动力学模型, 元胞自动机不是由严格定义的物理方程或函数确定,而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此, 元胞自动机是一类模型的总称, 或者说是一个方法框架。其特点是时间、空间、状态都离散,每个变量只取有限多个状态, 且其状态改变的规则在时间和空间上都是局部的。传统的的识别方法: 视觉标记的识别过程包括输入图像、输出图像标记的包围框和特征点的坐标。这个过程的设计要求是具有较好的精度, 满足实时性要求, 其中实时性要比精度更重要一些。标记的识别中,一般可以利用的信息是标记的边缘信息、几何信息、色度信息。如下图所示。首先将图像转化为二值图像, 然后利用腐蚀、边框提取和 Hough 变换等技术获得标志包围,再经过种子填充和几何限制等手段取得特征点集合。采用 CA 模型的算法: CA 识别算法如图 2 所示,可见算法的效率高低取决于 CA模的设计。 CA 法有以下几个特征: (1) 同质性、齐性,同质性反映在元胞空间内的每个元胞的变化都服从相同的规律,即元胞自动机的规则, 或称为转换函数; 而齐性指的是元胞的分布方式相同, 大小、形状相同, 空间分布规则整齐; (2) 空间离散: 元胞分布在按照一定规则划分的离散的元胞空间上; (3) 时间离散: 系统的演化是按照等间隔时间分步进行的, 时间变量 t 只能取等步长的时刻点,形似整数形式的 t0,t 十 l,t 十2…,而且, t 时刻的状态构形只对其下一时刻, 即 t+1 时刻的状态构形产生影响,而 t+2 时刻的状态构形完全决定于 t+1 的状态构形及定义在上面的砖换函数。元胞自动机的时间变量区别于微分方程中的时间变量 t, 那里 t 通常是个连续值变量; 元胞自动机-2- (4) 状态离散有限: 元胞自动器的状态只能取有限(k) 个离散值(s1,s2,...,sk) 。相对于连续状态的动力系统,它不需要经过粗粒化处理就能转化为符号序列。而在实际应用中,往往需要将有些连续变量进行离散化,如分类,分级,以便于建立元胞自动机模型; (5) 同步计算( 并行性): 各个元胞的在时刻 ti+1 的状态变化是独立的行为, 相互没有任何影响。若将元胞自动机的构形变化看成是对数据或信息的计算或处理, 则元胞自动机的处理是同步进行的,特别适合于并行计算; (6) 时空局部性: 每一个元胞的下一时刻 ti+1 的状态, 取决于其周围半径为 r 的邻域(或者其它形式邻居规则定义下的邻域) 中的元胞的当前时刻 ti 的状态, 即所谓时间、空间的局部性。从信息传输的角度来看,元胞自动机中信息的传递速度是有限的; (7) 维数高:在动力系统中一般将变量的个数成为维数。例如,将区间映射生成的动力系统称为一维动力系统; 将平面映射生成的动力系统称为二维动力系统; 对于偏微分方程描述的动力系统则称为无穷维动力系统。从这个角度来看, 由于任何完备元胞自动机的元胞空间是定义在一维、二维或多维空间上的无限集, 每个元胞的状态便是这个