球面元胞自动机框架的比较与选择

1、第26卷第5期2010年9月地理与地理信息科学Geography and Geo- Infor mation ScienceVol. 26 No.5September 2010球面元胞自动机框架的比较与选择肖志峰，翟晓芳（武汉大学测绘遥感信息工程国家重点实验室，湖北武汉430079）摘要：在球面构建基本的元胞自动机框架是球面元胞自动机研究的基础。该 文从球面空间特性岀发,分析比较了四边形、三角形和六边形网格的不同几何特性和元胞运动机制,提出了基于六边形 网格的元胞 自动机框 架模型，描述了其基本定义、运动机制和坐标系统，并构建了球面六 边形元胞自动机原型系统进行模拟实验,结果表明,该元 胞自动

2、机框架能有效支持球面元胞自动机的深入研究。关键词：球面;元胞自动机；六边形中图分类号:P208 文献标识码：A文章编号:1672- 0504（2010） 05- 0007- 04第26卷第5期2010年9月地理与地理信息科学Geography and Geo- Infor mation ScienceVol. 26 No.5September 2010第26卷第5期2010年9月地理与地理信息科学Geography and Geo- Infor mation ScienceVol. 26 No.5September 2010元胞自动机是离散动力学系统1,2,元胞自动机研究常集中在元胞自动机的演

3、化规则上。随着生态 系统模拟、气候模拟、环境模拟等研 究的发展3,在 球面或椭球面上研究元胞自动机的演化日益成为热 点。球面空间是一个各向异性的复杂的流形 ，它属 于非欧空间，在球面空间上无法完全建立与平面空 间的一一对应关系，不能完全照搬平面空间上的相 关研究成果4。因此，球面元胞自动机研究在元胞 网格选择、运动机制、编码规则及多尺度分析等方面 与平面空间的元胞自动机都存在差异，必须从球面元胞网格的空间特性和球面空间拓扑特性出发，发展适用于球面的元胞自动机框架。1球面元胞网格的选取元胞自动机研究的基础在于元胞网格的选取，不同的元胞网格有不同的空间特性，绝大多数元胞自动机网格都是四边形，由于球

4、面空间是黎曼空间， 四边形网格在球面空间无法实现完全覆盖。元胞网 格在参考空间的位置、大小和面积均能不同程度影 响元胞自动机演化的效果，因此，以球面为参考空间 的元胞自动机网格的选取也有别于平面空间。本文 提出了球面元胞网格选择的5点要求：1）元胞网格的分布方式相同，大小和形状相同，地位平等，空间 分布规则整齐5;2）各个元胞网格在每个时刻的状 态变化是独立的行为，相互没有任何影响；3）元胞网 格应完全覆盖全球，无重叠和遗漏；4）元胞网格具有 相同的面积和形状；5）每个元胞网格只有一个网格 介严 参考点。球面元胞自动机网格与离散全球网格系统（DGGs） 6,7存在很大的类比性。DGGs是一种新

5、型的地理空间网 格结构，它由规 则的多边 形构成，目 前存在三种规则多边形进行空间覆盖而无任何缝 隙,即三角形、四边形和六边形（图1）,其他多边形 进行空间覆盖则会产生邻近像素不等距、覆盖缝隙或重叠。图1三角形、四边形、六边形球面网格Fig. 1 Spherical grids of triangle, square and hexagon四边形网格是构建平面网格的常用单元形状，在球面上以等角的经纬度网格最为流行，等角经纬度网格有大量优点，它基于二维笛卡尔坐标系统 ，已 被广泛应用。经纬度网格系统目前已经成为众多空 间数据管理、处理软件的基础。四边形网格边界并 不一致，每个四边形网格单元有四个

6、共享边的邻近 网格,其中心距离与网格中心等距。同时，每个网格有四个共享顶点的邻近网格，但这些网格的中心点距离大于共享边网格的中心点距离，显示出各向异性的特点。因此，每种邻近网格对中心网格的贡献 程度也不同，而大多数基于四边形的元胞自动机研 究认为边邻近网格和角邻近网格对中心网格的贡献 一致。经纬度网格系统存在的另一个重要缺陷就是当 网格从赤道地区向高纬度地区移动时，其形状和面积变形均显著增大。在南极和北极点，网格变成三收稿日期:2010- 05- 17; 修订日期：2010- 06- 11基金项目：国家重大基础研究项目（61399）作者简介：肖志峰（1977-）,男，博士，讲师，主要研究空间信

7、息网格与高性能空间信息服务。E- mail: xiaozf gmail. com1994-2011 China Acaacmic Journal LJccLronic rUbliSning HduScl All righU reervecL nllp:?7wwwxnki. 11，角形（在其他地区为矩形）。这对于具有同质性和齐 性的元胞空间难以接受。很多学者提出了不同的改第9页地理与地理信息科学第26卷进方法,如减少单元的数量、增加纬度，使之获得了一致的单元格大小，或采用纬线或经线方向单元格 边界的相似变换使网格近似等面积。但这些成果在 获得等面积的同时，都使单元格形状越来越不规则 且单元格接边

8、更复杂。三角形网格避免了四边形网格在赤道和两极出 现的较大面积差异，以基于三角形网格的 QTM系统 为例，其最大与最小网格的面积比约为1 8；同时三角形网格拥有较少的邻居数目，它与正方形网格都是 不一致邻近，每个单元有3个边邻居和9个节点邻居; 其次，三角形网格覆盖单元不具有一致的定向，如图2,一些三角形朝上，一些三角形朝下，难以符合元胞 的齐性规则，对这种特殊情况需要额外考虑8。元胞运动的障碍点，所以对角邻域对元胞的状态无影 响。在不同的应用中，对元胞的邻域要求也不一样，冯-诺依曼（Von. Neumann）邻域和摩尔（Moore）邻域 是最主要的领域规则，冯-诺依曼邻域为共享边的直 角邻域

9、，摩尔邻域则既包括直角邻域也包括对角邻 域,并认为对角邻域和直角邻域对元胞的影响相当。四边形元胞网格的冯-诺依曼邻域（图3a）为一 个元胞的上、下、左、右相邻四个元胞。这里，邻域半 径r为1,相当于图像处理中的四邻域、四方向。摩尔邻域（图3b）是指一个元胞的上、 下、左、右、左上、 右上、右下、左下相邻的八个元胞。邻域半径r同样为1,相当于图像处理中的八邻域、 八方向。（3）再一诺依曼靠域（S）用尔轉域图2三角形网格Fig. 2 Grids of triangles六边形网格是空间最紧凑的网格9,其拥有最大的角分辨率。与三角形和正方形网格不同，六边形具有一致邻近的特性：每个六边形单元有六个共

10、享边的邻近单元，其邻近单元的中心点与中心网格 的中心点距离相等。每个六边形网格没有共有一个 顶点的邻近单元，这一特性使六边形在离散空间仿 真中受到更多重视，六边形网格的六个离散速度矢 量足够用来模拟连续的、各向同性的流动量。在球面空间中，六边形不能完全覆盖整个球面，使用六边形进行球面空间划分时，在所有柏拉图多面体的顶点 处都会出现一个非六边形的多边形，这种多边形的个 数与多面体的顶点数相关，与网格的分辨率无关，在 采用二十面体的六边形网格中，共有12个五边形。由于五边形的数量是固定的，相对元胞网格的总数量 非常少。同时还可采用一定的处理模型来削弱五边 形网格对空间结构和元胞演化的影响，因此五边

11、形的 存在不会影响球面元胞自动机的模拟效果10。图3四边形元胞的邻域Fig. 3 Neighborhood of square CA三角形元胞网格的冯-诺依曼邻域为一个元胞 的上、左、右（图4a）或下、左、右（图4b）的相邻三个 元胞。摩尔邻域（图4c）是指一个三角形元胞的所有 直角和对角邻域。从图中可以看出，三角形元胞的某些对角邻域已经远离中心元胞，难以受到中心元胞的影响，缺少实际意义。U） I型褂L谥依曼第域（I,）曲卜诺依囉部域陀肚鄧域图4三角形元胞的邻域Fig. 4 Neighborhood of triangle CA六边形网格的邻域规则最为简单，其只有6个邻 居,每个邻近网格都拥有

12、一个公共边和两个公共顶点 （图5）,即不用考虑复杂的邻接情况，且各方向的运动 机制完全一致3。这种简化的设计导致六边形网格 拥有更加简易和高效的算法，并且由于六边形网格邻域可以定义更多流向，与现实情况更加接近。2球面元胞网格的邻域比较元胞自动机模型中的元胞个体通常不可移动，元胞自动机在整体上的运动通过元胞个体的状态变 化实现。状态的变化除受转换规则影响外，还受元胞所在邻域的影响，而不同的元胞网格对邻域的影响 机制也不完全一致。根据元胞网格的邻近位置不同 区分为两类领域：直角邻域和对角邻域。直角邻域共 享一条边,对角邻域共享一个角，对角点通常被作为© 1I I C riiTia Aca

13、dcrnic Journal ElccironiC rub图5六边形元胞的邻域Fig. 5 Neighborhood of hexagon CA3基于六边形网格的球面元胞自动机框架3. 1基本定义通过对传统的元胞自动机网格定义进行扩展第5期肖志峰等：球面元胞自动机 框架的比较与选择第9页定义基于球面的六边形元胞自动机网格规则：1）状态：1/0两种状态。2）初始状态：所有的元胞在初 始时刻的状态。3）转换规则：是元胞自动机最核心 的部分，元胞自动机的整个模拟过程完全受转换规 则控制。由于需要尽可能简单的转换规则来模拟演 变机制，并且把重点集中到网格邻域的影响，所以可将相同的转换规则扩展到球面。4

14、）邻域：六边形网格的6个共享边邻域对中心元胞影响的权重一致，6即六边形邻域函数影响为:ij =小（urban（ ij ） /6。5）边界:在平面空间中，元胞在四边形网格的边 缘或拐角与在网格中心有不同数量的邻域，边界元胞的存在显然影响系统的动态性，因为大多数元胞 自动机演化是单独定义在有限的平面区域上 ，边界 元胞通常给予特殊对待；而球面是封闭无边界的表 面，单一分辨率的球面网格没有边界元胞，不需要特殊对待。3.2元胞网格坐标系统球面空间众多的元胞网格需要置于统一的坐标 系统才能进行各种演化运算。六边形网格与四边形 网格不同，六边形网格的点不能对齐相互垂直的两 个方向，同时球面空间的拓扑关系也

15、不同于平面空 间的拓扑关系，因此不能直接使用传统的笛卡尔坐 标系统表示六边形网格点位。从元胞自动机演化的简化性考虑，可使用与笛卡儿坐标系统类似的二轴坐标系统，称为二轴倾斜坐标系统或h2坐标系统，它是使用与六边形对称轴 方向相一致的一对倾斜轴，一个六边形网格可使用二轴倾斜坐标系统具有明显的特性：1）完整性:能够表示二维空间中的任何六边形网格；2）唯一性:任何不同的坐标对只对应唯一的网格；3）可转换性:能够简单地与笛卡尔坐标系进行相互转换；4）高效性:方便而有效。由于二轴倾斜坐标系统并不能完 整覆盖整个球面，一般将球面剖分为多个子域，在每 个子域构建局部的二轴倾斜坐标系统。 Sahr在二十 面体网

16、格中将整个球面划分为 10个子域11,每个子 域由9个或10个初始六边形构成，通过进一步划分 可以得到更高分辨率的六边形网格。因此，在全球元胞自动机网格中，每个网格的地址由该网格所在 的四边形子域加上该子域内倾斜坐标来表达，如0,2, 1表示在第一个四边形子域内第二行、第一列的网格。对于每个四边形子域，都可以使用一个二轴 倾斜坐标系统来表达（图7）。图7全球二十面体的二轴倾斜坐标子域Fig. 7 Sub area of 2 axis slope coordinate system of icosahedrons in sphere4 球面元胞自动机框架实验一对整数坐标值来表示。倾斜坐标系统有几

17、种不同 的变体（图6）,其坐标轴分别相距 120?或 60?。图6六边形网格的二轴倾斜坐标系统Fig. 62 Axis slope coordinate system of hexagon grids© 1994-2011 China Academic Joumal Elslrcmiic rum机原型，主要用来验证球面元胞自动机的网格剖分、 网格编码与元胞运行机制。球面元胞自动机原型采 用JOGL作为三维渲染引擎，在java版 WorldWind 的基础上进行开发，实现了全球和局部的六边形元 胞自动机网格生成与基本扩展机制。虽然球面元胞自动机框架主要在全球范围内应 用，但局部区域内的

18、元胞自动机模拟也可以使用球 面元胞自动机框架，图8是湖北省的元胞自动机网 格模拟，图9是2002年武汉市土地利用图的元胞自 动机网格图。本文对2002年、2005年等多个时间的武汉市土 地利用遥感影像图进行解译，在构建的球面元胞自 动机框架上使用逻辑回归模型对武汉市土地利用现 状进行演化运算，采用逐点对比和整体比较的方法 对模拟结果进行比较。实验表明，基于六边形网格的元胞自动机模拟更适宜于不确定方向的扩展，在J为了验证基于球面的元胞自动 机框架，本文使 用三维可视化引擎 WorldWind构建球面元胞自动 第10页地理与地理信息科学第26卷土地利用现状的变化趋势方面更加符合实际情况 能满足针对

19、全球变化的仿真模拟应用。图&基于盍边理的湖北省元胞自动机网格F跑.S Huibti CA grids ba»*d on囲9基于六边形的武汉市土地利用图Fig. 9 Wuhnmapnn hexagon5结语随着研究区域扩展到全球 范围，基于四边形网 格的元胞自动机研究出现了一些不适应的情况，由于球面空间的特殊性，在球面上构建元胞自动机更 需考虑元胞网格面积变形、邻接关系等方面，本文提 出的球面元胞自动机框架采用六边形作为元胞网格 的基本形状，在面积一致性和拓扑邻接一致性等方 面均优于四边形和三角形网格，由于六边形的演化规则与四边形有较大差异，因此在演化算法上仍需进行更多研究。参

20、考文献：1 黎夏，叶嘉安.地理模拟系统：元胞自动机与多智能体M.北 京：科学出版社，2007.2 周成虎，孙战利，谢一春.地理元胞自 动机研究M .北京：科学 出版社，1999.3 ROSS K A， SAH R K. Plan ar and spherical hierarchical， multi resolution cellular automata J . Computers, Environm ent and U rban Systems，2008, 32: 204- 213.4 EGENH OFER M J. Spherical top ological relations J.

21、 Data Se mantics III，2005( L NCS 3534) : 25- 49.5 GOODCH ILD M F. Geographical grid m odels for environmental monitorin g and analysis across the globe A . Proceedings of GIS/ LIS#94 Conference C . 1994.6 SAHR K，WHIT ED. Geodesic dis crete global grid systems J. Cartograp hy and Geographic Inform at

22、ion Science，1998，30( 2): 121- 134.7 GOODCH ILD M，YANG SR. Tessellation of the sphere R. NCGIS Spatial Analysis on the Sphere? A Review Technical Report， 1994. 94- 97.8 DUT TON G. En coding and handling geospatial data with hier archical triangular meshesA . Proceeding of 7th In ternational Symposium

23、 on Spatial Data H andling，1996. 34- 43.9 M IDDLET ON，LEE，SIVASWAM Y，et al. Hexagonal image pr ocessing: A practical approach R . Springer，2005. 16.10 HAI X F. Res earch on the comparison of extens ion mechanismof cellular automaton based on h exagon grid and rectangu lar grid A . proc. of SPIE vol.

24、 7492 74924K-1 C . 2009.SAH R K. Location coding on icosahedral aperture 3 hexagon discrete global grids J. Computers， Environment and Urban System s，2008, 32( 3) : 174- 187.第#页地理与地理信息科学第26卷第11页地理与地理信息科学第26卷Comparis on and Select ion of Cellular Automati on Framework on SphereXIA O Zhi- feng，ZHA I Xiao- fang(LI ESM A RS，Wuhan Univer sity，Wuhan 430079，China)Abstract: With the rapid development of global change reseaich，the evolutio n simulation of cellular automat on in spherical space has been t aken more seriously. Constructing the basal cel