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

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