球面元胞自動機框架的比較與選擇

肖志峰,翟曉芳

(武漢大學測繪遙感信息工程國家重點實驗室,湖北武漢 430079）

球面元胞自動機框架的比較與選擇

肖志峰,翟曉芳

(武漢大學測繪遙感信息工程國家重點實驗室,湖北武漢 430079）

在球面構建基本的元胞自動機框架是球面元胞自動機研究的基礎。該文從球面空間特性出發,分析比較了四邊形、三角形和六邊形網格的不同幾何特性和元胞運動機制,提出了基于六邊形網格的元胞自動機框架模型,描述了其基本定義、運動機制和坐標系統,并構建了球面六邊形元胞自動機原型系統進行模擬實驗,結果表明,該元胞自動機框架能有效支持球面元胞自動機的深入研究。

球面;元胞自動機;六邊形

元胞自動機是離散動力學系統[1,2],元胞自動機研究常集中在元胞自動機的演化規則上。隨著生態系統模擬、氣候模擬、環境模擬等研究的發展[3],在球面或橢球面上研究元胞自動機的演化日益成為熱點。球面空間是一個各向異性的復雜的流形,它屬于非歐空間,在球面空間上無法完全建立與平面空間的一一對應關系,不能完全照搬平面空間上的相關研究成果[4]。因此,球面元胞自動機研究在元胞網格選擇、運動機制、編碼規則及多尺度分析等方面與平面空間的元胞自動機都存在差異,必須從球面元胞網格的空間特性和球面空間拓撲特性出發,發展適用于球面的元胞自動機框架。

1 球面元胞網格的選取

元胞自動機研究的基礎在于元胞網格的選取,不同的元胞網格有不同的空間特性,絕大多數元胞自動機網格都是四邊形,由于球面空間是黎曼空間,四邊形網格在球面空間無法實現完全覆蓋。元胞網格在參考空間的位置、大小和面積均能不同程度影響元胞自動機演化的效果,因此,以球面為參考空間的元胞自動機網格的選取也有別于平面空間。本文提出了球面元胞網格選擇的5點要求:1）元胞網格的分布方式相同,大小和形狀相同,地位平等,空間分布規則整齊[5];2）各個元胞網格在每個時刻的狀態變化是獨立的行為,相互沒有任何影響;3）元胞網格應完全覆蓋全球,無重疊和遺漏;4）元胞網格具有相同的面積和形狀;5）每個元胞網格只有一個網格參考點。

球面元胞自動機網格與離散全球網格系統(DGGs）[6,7]存在很大的類比性。DGGs是一種新型的地理空間網格結構,它由規則的多邊形構成,目前存在三種規則多邊形進行空間覆蓋而無任何縫隙,即三角形、四邊形和六邊形(圖1）,其他多邊形進行空間覆蓋則會產生鄰近像素不等距、覆蓋縫隙或重疊。

圖1 三角形、四邊形、六邊形球面網格Fig.1 Spherical grids of triangle,square and hexagon

四邊形網格是構建平面網格的常用單元形狀,在球面上以等角的經緯度網格最為流行,等角經緯度網格有大量優點,它基于二維笛卡爾坐標系統,已被廣泛應用。經緯度網格系統目前已經成為眾多空間數據管理、處理軟件的基礎。四邊形網格邊界并不一致,每個四邊形網格單元有四個共享邊的鄰近網格,其中心距離與網格中心等距。同時,每個網格有四個共享頂點的鄰近網格,但這些網格的中心點距離大于共享邊網格的中心點距離,顯示出各向異性的特點。因此,每種鄰近網格對中心網格的貢獻程度也不同,而大多數基于四邊形的元胞自動機研究認為邊鄰近網格和角鄰近網格對中心網格的貢獻一致。

經緯度網格系統存在的另一個重要缺陷就是當網格從赤道地區向高緯度地區移動時,其形狀和面積變形均顯著增大。在南極和北極點,網格變成三角形(在其他地區為矩形）。這對于具有同質性和齊性的元胞空間難以接受。很多學者提出了不同的改進方法,如減少單元的數量、增加緯度,使之獲得了一致的單元格大小,或采用緯線或經線方向單元格邊界的相似變換使網格近似等面積。但這些成果在獲得等面積的同時,都使單元格形狀越來越不規則且單元格接邊更復雜。

三角形網格避免了四邊形網格在赤道和兩極出現的較大面積差異,以基于三角形網格的QTM系統為例,其最大與最小網格的面積比約為1.8[8];同時三角形網格擁有較少的鄰居數目,它與正方形網格都是不一致鄰近,每個單元有3個邊鄰居和9個節點鄰居;其次,三角形網格覆蓋單元不具有一致的定向,如圖2,一些三角形朝上,一些三角形朝下,難以符合元胞的齊性規則,對這種特殊情況需要額外考慮[8]。

圖2 三角形網格Fig.2 Grids of triangles

六邊形網格是空間最緊湊的網格[9],其擁有最大的角分辨率。與三角形和正方形網格不同,六邊形具有一致鄰近的特性:每個六邊形單元有六個共享邊的鄰近單元,其鄰近單元的中心點與中心網格的中心點距離相等。每個六邊形網格沒有共有一個頂點的鄰近單元,這一特性使六邊形在離散空間仿真中受到更多重視,六邊形網格的六個離散速度矢量足夠用來模擬連續的、各向同性的流動量。在球面空間中,六邊形不能完全覆蓋整個球面,使用六邊形進行球面空間劃分時,在所有柏拉圖多面體的頂點處都會出現一個非六邊形的多邊形,這種多邊形的個數與多面體的頂點數相關,與網格的分辨率無關,在采用二十面體的六邊形網格中,共有12個五邊形。由于五邊形的數量是固定的,相對元胞網格的總數量非常少。同時還可采用一定的處理模型來削弱五邊形網格對空間結構和元胞演化的影響,因此五邊形的存在不會影響球面元胞自動機的模擬效果[10]。

2 球面元胞網格的鄰域比較

元胞自動機模型中的元胞個體通常不可移動,元胞自動機在整體上的運動通過元胞個體的狀態變化實現。狀態的變化除受轉換規則影響外,還受元胞所在鄰域的影響,而不同的元胞網格對鄰域的影響機制也不完全一致。根據元胞網格的鄰近位置不同區分為兩類領域:直角鄰域和對角鄰域。直角鄰域共享一條邊,對角鄰域共享一個角,對角點通常被作為元胞運動的障礙點,所以對角鄰域對元胞的狀態無影響。在不同的應用中,對元胞的鄰域要求也不一樣,馮-諾依曼(Von.Neumann）鄰域和摩爾(Moore）鄰域是最主要的領域規則,馮-諾依曼鄰域為共享邊的直角鄰域,摩爾鄰域則既包括直角鄰域也包括對角鄰域,并認為對角鄰域和直角鄰域對元胞的影響相當。

四邊形元胞網格的馮-諾依曼鄰域(圖3a）為一個元胞的上、下、左、右相鄰四個元胞。這里,鄰域半徑r為1,相當于圖像處理中的四鄰域、四方向。摩爾鄰域(圖3b）是指一個元胞的上、下、左、右、左上、右上、右下、左下相鄰的八個元胞。鄰域半徑r同樣為1,相當于圖像處理中的八鄰域、八方向。

圖3 四邊形元胞的鄰域Fig.3 Neighborhood of square CA

三角形元胞網格的馮-諾依曼鄰域為一個元胞的上、左、右(圖 4a）或下、左、右(圖 4b）的相鄰三個元胞。摩爾鄰域(圖4c）是指一個三角形元胞的所有直角和對角鄰域。從圖中可以看出,三角形元胞的某些對角鄰域已經遠離中心元胞,難以受到中心元胞的影響,缺少實際意義。

圖4 三角形元胞的鄰域Fig.4 Neighborhood of triangle CA

六邊形網格的鄰域規則最為簡單,其只有6個鄰居,每個鄰近網格都擁有一個公共邊和兩個公共頂點(圖5）,即不用考慮復雜的鄰接情況,且各方向的運動機制完全一致[3]。這種簡化的設計導致六邊形網格擁有更加簡易和高效的算法,并且由于六邊形網格鄰域可以定義更多流向,與現實情況更加接近。

圖5 六邊形元胞的鄰域Fig.5 Neighborhood of hexagon CA

3 基于六邊形網格的球面元胞自動機框架

3.1 基本定義

3.2 元胞網格坐標系統

球面空間眾多的元胞網格需要置于統一的坐標系統才能進行各種演化運算。六邊形網格與四邊形網格不同,六邊形網格的點不能對齊相互垂直的兩個方向,同時球面空間的拓撲關系也不同于平面空間的拓撲關系,因此不能直接使用傳統的笛卡爾坐標系統表示六邊形網格點位。

從元胞自動機演化的簡化性考慮,可使用與笛卡兒坐標系統類似的二軸坐標系統,稱為二軸傾斜坐標系統或h2坐標系統,它是使用與六邊形對稱軸方向相一致的一對傾斜軸,一個六邊形網格可使用一對整數坐標值來表示。傾斜坐標系統有幾種不同的變體(圖6）,其坐標軸分別相距120°或60°。

圖6 六邊形網格的二軸傾斜坐標系統Fig.6 2-Axis slope coordinate system of hexagon grids

二軸傾斜坐標系統具有明顯的特性:1）完整性:能夠表示二維空間中的任何六邊形網格;2）唯一性:任何不同的坐標對只對應唯一的網格;3）可轉換性:能夠簡單地與笛卡爾坐標系進行相互轉換;4）高效性:方便而有效。由于二軸傾斜坐標系統并不能完整覆蓋整個球面,一般將球面剖分為多個子域,在每個子域構建局部的二軸傾斜坐標系統。Sahr在二十面體網格中將整個球面劃分為10個子域[11],每個子域由9個或10個初始六邊形構成,通過進一步劃分可以得到更高分辨率的六邊形網格。因此,在全球元胞自動機網格中,每個網格的地址由該網格所在的四邊形子域加上該子域內傾斜坐標來表達,如{0,2,1}表示在第一個四邊形子域內第二行、第一列的網格。對于每個四邊形子域,都可以使用一個二軸傾斜坐標系統來表達(圖7）。

圖7 全球二十面體的二軸傾斜坐標子域Fig.7 Sub-area of 2-axis slope coordinate system of icosahedrons in sphere

4 球面元胞自動機框架實驗

為了驗證基于球面的元胞自動機框架,本文使用三維可視化引擎Wo rldW ind構建球面元胞自動機原型,主要用來驗證球面元胞自動機的網格剖分、網格編碼與元胞運行機制。球面元胞自動機原型采用JOGL作為三維渲染引擎,在java版WorldWind的基礎上進行開發,實現了全球和局部的六邊形元胞自動機網格生成與基本擴展機制。

雖然球面元胞自動機框架主要在全球范圍內應用,但局部區域內的元胞自動機模擬也可以使用球面元胞自動機框架,圖8是湖北省的元胞自動機網格模擬,圖9是2002年武漢市土地利用圖的元胞自動機網格圖。

本文對2002年、2005年等多個時間的武漢市土地利用遙感影像圖進行解譯,在構建的球面元胞自動機框架上使用邏輯回歸模型對武漢市土地利用現狀進行演化運算,采用逐點對比和整體比較的方法對模擬結果進行比較。實驗表明,基于六邊形網格的元胞自動機模擬更適宜于不確定方向的擴展,在土地利用現狀的變化趨勢方面更加符合實際情況,能滿足針對全球變化的仿真模擬應用。

5 結語

隨著研究區域擴展到全球范圍,基于四邊形網格的元胞自動機研究出現了一些不適應的情況,由于球面空間的特殊性,在球面上構建元胞自動機更需考慮元胞網格面積變形、鄰接關系等方面,本文提出的球面元胞自動機框架采用六邊形作為元胞網格的基本形狀,在面積一致性和拓撲鄰接一致性等方面均優于四邊形和三角形網格,由于六邊形的演化規則與四邊形有較大差異,因此在演化算法上仍需

進行更多研究。

[1] 黎夏,葉嘉安.地理模擬系統:元胞自動機與多智能體[M].北京:科學出版社,2007.

[2] 周成虎,孫戰利,謝一春.地理元胞自動機研究[M].北京:科學出版社,1999.

[3] ROSS K A,SAHR K.Planar and spherical hierarchical,multiresolution cellular automata[J].Computers,Environment and U rban Systems,2008,32:204-213.

[4] EGENHOFER M J.Spherical topological relations[J].Data Semantics III,2005(LNCS 3534）:25-49.

[5] GOODCH ILD M F.Geographical grid models for environmental monitoring and analysis across the globe[A].Proceedings of GIS/L IS′94 Conference[C].1994.

[6] SAHR K,WH ITED.Geodesic discrete global grid systems[J].Cartography and Geographic Information Science,1998,30(2）:121-134.

[7] GOODCH ILD M,YANG S R.Tessellation of the sphere[R].NCGIS Spatial Analysis on the Sphere——A Review Technical Repo rt,1994.94-97.

[8] DU TTON G.Encoding and handling geospatial data with hierarchical triangular meshes[A].Proceeding of 7th International Symposium on Spatial Data Handling,1996.34-43.

[9] M IDDLETON,LEE,SIVASWAM Y,et al.Hexagonal image p rocessing:A p ractical app roach[R].Sp ringer,2005.16.

[10] HA IX F.Research on the comparison of extension mechanism of cellular automaton based on hexagon grid and rectangular grid[A].p roc.of SPIE vol.7492 74924K-1[C].2009.

[11] SAHR K.Location coding on icosahedral aperture 3 hexagon discrete global grids[J].Computers,Environment and U rban Systems,2008,32(3）:174-187.

Com par ison and Selection of Cellular Automation Framework on Sphere

XIAO Zhi-feng,ZHA IXiao-fang
(LIESMARS,WuhanUniversity,Wuhan430079,China）

With the rapid development of global change research,the evolution simulation of cellular automaton in spherical space has been taken mo re seriously.Constructing the basal cellular automaton framewo rk is the basement of research of spherical cellular automaton.This paper started from the spherical spatial characteristics.And the quadrangle grid′s,triangle grid′s and hexagon grid′s different geometric p roperties and cellular movementmechanism were analyzed and compared,then the cellular automaton framework model based hexagon grid was put fo rward,its basic definition,movement mechanism and reference frame were described,and a spherical hexagon cellular automaton antetype system was built to do simulation experiment.The result showed that this cellular automaton f rame can suppo rt the in-dep th study on spherical cellular automaton effectively.

sphere;Cellular Automation;hexagon

P208

A

1672-0504(2010）05-0007-04

2010-05- 17;

2010-06-11

國家重大基礎研究項目(61399）

肖志峰(1977-）,男,博士,講師,主要研究空間信息網格與高性能空間信息服務。E-mail:xiaozf@gmail.com