基于元胞自动机的栅格路径距离变换方法.doc

基于元胞自动机的栅格路径距离变换方法0. 引言距离是空间度量的基础，并且是地理空间上定义的各种量度诸如密度、坡度、坡向等计算的出发点，同时也是各种地理分析如缓冲区分析，Voronoi分析，DEM分析，网络分析的基础。栅格距离变换主要来采用形态数学。元胞自动机是基于时间、空间都离散的动力学系统, 是复杂性科学的一个重要研究领域。本文利用元胞自动机基于局部规则的并行动态计算特性，构造出一个并行距离变换的元胞自动机算法模型。1. 元胞自动机元胞自动机( Cellular Automata，CA) ,也称细胞自动机、点格自动机等, 是一种时间和空间都离散、物理参量只取有限数值集的动力学系统。 散布在规则格网( LatticeGrid) 中的每一元胞( Cell) 取有限的离散状态, 遵循同样的作用规则, 依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。不同于一般的动力学模型, 元胞自动机不是由严格定义的物理方程或函数确定, 而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。元胞自动机(Cellular Automata, CA)具有强大的空间运算能力,常用于自组织系统演变过程的研究。它是一种时间、空间、状态都离散,空间相互作用和时间因果关系都为局部的网格动力学模型,具有模拟复杂系统时空演化过程的能力。与传统的基于方程式的地理学模型相比,元胞自动机模型具有较好的时空动态性,可以模拟非线性复杂系统的突现、混沌、进化等特征,是模拟生态、环境、自然灾害等多种高度复杂的地理现象的有力工具。元胞自动机中的元胞可以通过改变状态与它们的邻居沟通，它们可以包含复杂的有限状态机解释其输入。有限状态机通常是足够简单使得他们可以在可编程的硬件如FPGA实现，这就使得它们能够非常迅速地进行评估。此外，因为元胞自动机的操作只涉及局部的邻居，因此算法可以很容易地实现并行计算。2. 元胞自动机模型在地理研究中的应用元胞自动机在地理学中的应用最早可追溯到20世纪60年代, Hagerstrand在他的空间扩散模型的研究中首先采用了类似于元胞自动机的思想。到20世纪80年代后期,元胞自动机在地理学上的应用得到了空前发展,成为地理研究和空间分析的热点课题。Batty和Xie在这方面做了大量的工作。他们从生物学的CA中得到启发,提出了早期的城市CA,用来模拟城市的演化。White和Engenlen利用元胞自动机模型对全球变化对Caribbean岛土地利用构成变化的影响进行了研究。IchiroEmbutsu, Michael F。Goodchild等人利用元胞自动机模型成功地模拟了城市热岛效应(UrbanHeat Island)。瑞士的B。Chopard等人利用元胞自动机模型进行了交通流的模拟,并对日内瓦市的交通网的运行情况进行了分析和模拟。国内元胞自动机应用研究起步较晚,受国际研究的推动,20世纪90年代末地理学界才开始类似的尝试研究,主要集中在基于元胞自动机的LUCC和城市增长模拟;此外,国内很多学者对元胞自动机在交通、景观生态、火灾、流行病、水土流失、泥石流、火山岩溶流等式其他地学领域的进行了研究。3. 元胞自动机的一般特征（1） 空间离散性。（2） 时间离散性。（3） 有限状态离散。（4） 同步计算（并行性）。（5） 时空局部性。（6） 时空动态性。（7） 高维数。从元胞自动机的一般特征可以看出，其完全贴合地图代数中算法的特点，因此其在地图代数中的应用潜力是巨大的。4. 算法模型思路元胞自动机一般描述为一个三元组G= (S,N,R),其中G为系统的状态（global states）；S为元胞状态（cellular states）; N为邻近关系（neighbourhood）;R为演化规则（evolution rules）。在本文中，元胞状态分为空状态、扩展状态与源状态。 空状态标记不变换的区域, 扩展状态标记已经变换的区域, 源状态标记还没有变换的区域。空状态区域标记为0，源状态标记为MAXINT（32767），扩展状态标记为0与MAXINT之间。邻近关系采用Moore邻域，如图1。图1 Moore邻居演化规则为dRti,j=mindRt-1i-1,j-1+2, dRt-1i,j-1+1,dRt-1i+1,j-1+2,dRt-1i-1,j+1,dRt-1i,j，dRt-1i+1,j+1，dRt-1i-1,j+1+2,dRt-1i,j+1+1，dRt-1i+1,j+1+2其中dRti,j表示t时态i,j 位置的距离。图2表示了源状态元胞经过一个周期变换后生成的结果。 (a)原始图像 (b)变换1一个周期的图像图2 一个周期后生成的外距离（其中灰色表示空状态、粉色表示扩展状态、白色表示源状态）对于空状态和扩展状态，由于其状态一旦确定，就不会再改变，因此，可以减少很多的计算量。同时，如果其Moore邻域都为源状态，也不用计算。具体算法为：设地图M是x*y 的二维栅格地图, 空间中共有n个栅格, 即n= x* y, 则状态集S= 0, 1, n- 1, n。 初始时检测地图中要素所在栅格赋值为0，其它栅格赋值为源状态（MAXINT），启动元胞自动机，依据演化规则进行推演,直至图像的所有栅格都处于空状态或者扩展状态为止。5. 实验环境与结论采用Visual C+ 6.0平台，图像为手动绘制的一个300300的256色栅格图像如图3。图4为采用元胞自动机运行100次后结果。可以看出,实验结果符合实验目的。 图3 原始图像 图4 CA运算100次后的结果在实验中，发现具有处理具有复杂内容的图像相比简单图像处理速度更快，但实验中由于并没有采用多线程技术以及并行计算技术，导致CA运算效率明显低于栅格距离变换的普通算法，在以后的研究中应该进一步加以改进。参考文献：1 李霖,应申,朱海红.地理计算原理与方法M ,测绘出版社,20082 Matthew A. Lee, Lori Mann Bruce, APPLYING CELLULAR AUTOMATA TO HYPERSPECTRAL