肖志峰,翟曉芳

(武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室,湖北武漢 430079）

球面元胞自動(dòng)機(jī)框架的比較與選擇

肖志峰,翟曉芳

(武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室,湖北武漢 430079）

在球面構(gòu)建基本的元胞自動(dòng)機(jī)框架是球面元胞自動(dòng)機(jī)研究的基礎(chǔ)。該文從球面空間特性出發(fā),分析比較了四邊形、三角形和六邊形網(wǎng)格的不同幾何特性和元胞運(yùn)動(dòng)機(jī)制,提出了基于六邊形網(wǎng)格的元胞自動(dòng)機(jī)框架模型,描述了其基本定義、運(yùn)動(dòng)機(jī)制和坐標(biāo)系統(tǒng),并構(gòu)建了球面六邊形元胞自動(dòng)機(jī)原型系統(tǒng)進(jìn)行模擬實(shí)驗(yàn),結(jié)果表明,該元胞自動(dòng)機(jī)框架能有效支持球面元胞自動(dòng)機(jī)的深入研究。

球面;元胞自動(dòng)機(jī);六邊形

元胞自動(dòng)機(jī)是離散動(dòng)力學(xué)系統(tǒng)[1,2],元胞自動(dòng)機(jī)研究常集中在元胞自動(dòng)機(jī)的演化規(guī)則上。隨著生態(tài)系統(tǒng)模擬、氣候模擬、環(huán)境模擬等研究的發(fā)展[3],在球面或橢球面上研究元胞自動(dòng)機(jī)的演化日益成為熱點(diǎn)。球面空間是一個(gè)各向異性的復(fù)雜的流形,它屬于非歐空間,在球面空間上無(wú)法完全建立與平面空間的一一對(duì)應(yīng)關(guān)系,不能完全照搬平面空間上的相關(guān)研究成果[4]。因此,球面元胞自動(dòng)機(jī)研究在元胞網(wǎng)格選擇、運(yùn)動(dòng)機(jī)制、編碼規(guī)則及多尺度分析等方面與平面空間的元胞自動(dòng)機(jī)都存在差異,必須從球面元胞網(wǎng)格的空間特性和球面空間拓?fù)涮匦猿霭l(fā),發(fā)展適用于球面的元胞自動(dòng)機(jī)框架。

1 球面元胞網(wǎng)格的選取

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

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

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

四邊形網(wǎng)格是構(gòu)建平面網(wǎng)格的常用單元形狀,在球面上以等角的經(jīng)緯度網(wǎng)格最為流行,等角經(jīng)緯度網(wǎng)格有大量?jī)?yōu)點(diǎn),它基于二維笛卡爾坐標(biāo)系統(tǒng),已被廣泛應(yīng)用。經(jīng)緯度網(wǎng)格系統(tǒng)目前已經(jīng)成為眾多空間數(shù)據(jù)管理、處理軟件的基礎(chǔ)。四邊形網(wǎng)格邊界并不一致,每個(gè)四邊形網(wǎng)格單元有四個(gè)共享邊的鄰近網(wǎng)格,其中心距離與網(wǎng)格中心等距。同時(shí),每個(gè)網(wǎng)格有四個(gè)共享頂點(diǎn)的鄰近網(wǎng)格,但這些網(wǎng)格的中心點(diǎn)距離大于共享邊網(wǎng)格的中心點(diǎn)距離,顯示出各向異性的特點(diǎn)。因此,每種鄰近網(wǎng)格對(duì)中心網(wǎng)格的貢獻(xiàn)程度也不同,而大多數(shù)基于四邊形的元胞自動(dòng)機(jī)研究認(rèn)為邊鄰近網(wǎng)格和角鄰近網(wǎng)格對(duì)中心網(wǎng)格的貢獻(xiàn)一致。

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

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

圖2 三角形網(wǎng)格Fig.2 Grids of triangles

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

2 球面元胞網(wǎng)格的鄰域比較

元胞自動(dòng)機(jī)模型中的元胞個(gè)體通常不可移動(dòng),元胞自動(dòng)機(jī)在整體上的運(yùn)動(dòng)通過(guò)元胞個(gè)體的狀態(tài)變化實(shí)現(xiàn)。狀態(tài)的變化除受轉(zhuǎn)換規(guī)則影響外,還受元胞所在鄰域的影響,而不同的元胞網(wǎng)格對(duì)鄰域的影響機(jī)制也不完全一致。根據(jù)元胞網(wǎng)格的鄰近位置不同區(qū)分為兩類領(lǐng)域:直角鄰域和對(duì)角鄰域。直角鄰域共享一條邊,對(duì)角鄰域共享一個(gè)角,對(duì)角點(diǎn)通常被作為元胞運(yùn)動(dòng)的障礙點(diǎn),所以對(duì)角鄰域?qū)υ臓顟B(tài)無(wú)影響。在不同的應(yīng)用中,對(duì)元胞的鄰域要求也不一樣,馮-諾依曼(Von.Neumann）鄰域和摩爾(Moore）鄰域是最主要的領(lǐng)域規(guī)則,馮-諾依曼鄰域?yàn)楣蚕磉叺闹苯青徲?摩爾鄰域則既包括直角鄰域也包括對(duì)角鄰域,并認(rèn)為對(duì)角鄰域和直角鄰域?qū)υ挠绊懴喈?dāng)。

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

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

三角形元胞網(wǎng)格的馮-諾依曼鄰域?yàn)橐粋€(gè)元胞的上、左、右(圖 4a）或下、左、右(圖 4b）的相鄰三個(gè)元胞。摩爾鄰域(圖4c）是指一個(gè)三角形元胞的所有直角和對(duì)角鄰域。從圖中可以看出,三角形元胞的某些對(duì)角鄰域已經(jīng)遠(yuǎn)離中心元胞,難以受到中心元胞的影響,缺少實(shí)際意義。

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

六邊形網(wǎng)格的鄰域規(guī)則最為簡(jiǎn)單,其只有6個(gè)鄰居,每個(gè)鄰近網(wǎng)格都擁有一個(gè)公共邊和兩個(gè)公共頂點(diǎn)(圖5）,即不用考慮復(fù)雜的鄰接情況,且各方向的運(yùn)動(dòng)機(jī)制完全一致[3]。這種簡(jiǎn)化的設(shè)計(jì)導(dǎo)致六邊形網(wǎng)格擁有更加簡(jiǎn)易和高效的算法,并且由于六邊形網(wǎng)格鄰域可以定義更多流向,與現(xiàn)實(shí)情況更加接近。

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

3 基于六邊形網(wǎng)格的球面元胞自動(dòng)機(jī)框架

3.1 基本定義

3.2 元胞網(wǎng)格坐標(biāo)系統(tǒng)

球面空間眾多的元胞網(wǎng)格需要置于統(tǒng)一的坐標(biāo)系統(tǒng)才能進(jìn)行各種演化運(yùn)算。六邊形網(wǎng)格與四邊形網(wǎng)格不同,六邊形網(wǎng)格的點(diǎn)不能對(duì)齊相互垂直的兩個(gè)方向,同時(shí)球面空間的拓?fù)潢P(guān)系也不同于平面空間的拓?fù)潢P(guān)系,因此不能直接使用傳統(tǒng)的笛卡爾坐標(biāo)系統(tǒng)表示六邊形網(wǎng)格點(diǎn)位。

從元胞自動(dòng)機(jī)演化的簡(jiǎn)化性考慮,可使用與笛卡兒坐標(biāo)系統(tǒng)類似的二軸坐標(biāo)系統(tǒng),稱為二軸傾斜坐標(biāo)系統(tǒng)或h2坐標(biāo)系統(tǒng),它是使用與六邊形對(duì)稱軸方向相一致的一對(duì)傾斜軸,一個(gè)六邊形網(wǎng)格可使用一對(duì)整數(shù)坐標(biāo)值來(lái)表示。傾斜坐標(biāo)系統(tǒng)有幾種不同的變體(圖6）,其坐標(biāo)軸分別相距120°或60°。

圖6 六邊形網(wǎng)格的二軸傾斜坐標(biāo)系統(tǒng)Fig.6 2-Axis slope coordinate system of hexagon grids

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

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

4 球面元胞自動(dòng)機(jī)框架實(shí)驗(yàn)

為了驗(yàn)證基于球面的元胞自動(dòng)機(jī)框架,本文使用三維可視化引擎Wo rldW ind構(gòu)建球面元胞自動(dòng)機(jī)原型,主要用來(lái)驗(yàn)證球面元胞自動(dòng)機(jī)的網(wǎng)格剖分、網(wǎng)格編碼與元胞運(yùn)行機(jī)制。球面元胞自動(dòng)機(jī)原型采用JOGL作為三維渲染引擎,在java版WorldWind的基礎(chǔ)上進(jìn)行開發(fā),實(shí)現(xiàn)了全球和局部的六邊形元胞自動(dòng)機(jī)網(wǎng)格生成與基本擴(kuò)展機(jī)制。

雖然球面元胞自動(dòng)機(jī)框架主要在全球范圍內(nèi)應(yīng)用,但局部區(qū)域內(nèi)的元胞自動(dòng)機(jī)模擬也可以使用球面元胞自動(dòng)機(jī)框架,圖8是湖北省的元胞自動(dòng)機(jī)網(wǎng)格模擬,圖9是2002年武漢市土地利用圖的元胞自動(dòng)機(jī)網(wǎng)格圖。

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

5 結(jié)語(yǔ)

隨著研究區(qū)域擴(kuò)展到全球范圍,基于四邊形網(wǎng)格的元胞自動(dòng)機(jī)研究出現(xiàn)了一些不適應(yīng)的情況,由于球面空間的特殊性,在球面上構(gòu)建元胞自動(dòng)機(jī)更需考慮元胞網(wǎng)格面積變形、鄰接關(guān)系等方面,本文提出的球面元胞自動(dòng)機(jī)框架采用六邊形作為元胞網(wǎng)格的基本形狀,在面積一致性和拓?fù)溧徑右恢滦缘确矫婢鶅?yōu)于四邊形和三角形網(wǎng)格,由于六邊形的演化規(guī)則與四邊形有較大差異,因此在演化算法上仍需

進(jìn)行更多研究。

[1] 黎夏,葉嘉安.地理模擬系統(tǒng):元胞自動(dòng)機(jī)與多智能體[M].北京:科學(xué)出版社,2007.

[2] 周成虎,孫戰(zhàn)利,謝一春.地理元胞自動(dòng)機(jī)研究[M].北京:科學(xué)出版社,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

國(guó)家重大基礎(chǔ)研究項(xiàng)目(61399）

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