基于Snake模型的建筑物群移位算法改進(jìn)研究

楊莉

(湖北省國土測(cè)繪院，湖北武漢430010)

摘要：在對(duì)Snake模型研究的基礎(chǔ)上，結(jié)合建筑物群在移位中的特點(diǎn)，從2個(gè)方面對(duì)Snake模型進(jìn)行改進(jìn)：首先，在Snake模型中加強(qiáng)對(duì)齊排列建筑物群這一重要空間特征的識(shí)別，以便保持對(duì)齊排列建筑物群在移位前后不變；其次，針對(duì)傳統(tǒng)Snake模型有時(shí)無法解決兩個(gè)建筑物空間沖突的缺點(diǎn)，對(duì)街區(qū)中的建筑物群實(shí)行分層次移位，先將有沖突的兩個(gè)建筑物作為整體，與剩余其它建筑物利用Snake模型一起移位，然后再根據(jù)文中提出的建筑物間相互沖突的4種受力模型，進(jìn)行建筑物間空間沖突的移位。最后利用改進(jìn)的Snake模型進(jìn)行移位實(shí)驗(yàn)和分析。

關(guān)鍵詞：Snake模型；建筑物群；空間關(guān)系；受力模型

中圖分類號(hào)：P208

收稿日期：2014-05-15

作者簡(jiǎn)介：楊莉(1988-)，女，工程師，碩士.

ResearchontheimprovedapproachforbuildingclusterdisplacementbasedonSnakemodel

YANGLi

(LandsurveyingandMappingInstituteofHubeiProvince，Wuhan430010，China)

Abstract：Based on the research of snake model，it presents two improvements on snake model applied to the building cluster displacement.Firstly，in order to protect the important spatial relationship，buildings alignment，a method that strengthens the identification of alignment is proposed to maintain the spatial relationships in the displacement.Secondly，against the weakness of snake model that can not solve the conflicts between buildings，hierarchical displacement of buildings cluster is implemented to improve the computer method of conflict force between buildings，and fourth force models are proposed to displace buildings in conflict with other buildings.Finally，the improvement snake model is used in displacement experiment and the result is analyzed.

Keywords：Snakemodel；buildingcluster；spacerelationship；forcemodel

各種專題地理信息系統(tǒng)的建設(shè)越來越受到重視[1]，作為產(chǎn)生基礎(chǔ)地理信息的地圖綜合也有著重要的研究意義。在地圖綜合中，由于比例尺縮小，地圖要素符號(hào)的相對(duì)擴(kuò)大，造成地圖要素之間產(chǎn)生空間沖突。為了保持地圖的清晰性，必須處理這些沖突。在處理空間沖突的地圖綜合算子中，移位算子是解決沖突，保持要素之間空間關(guān)系的主要方法。建筑物群的空間沖突解決則是地圖綜合中移位研究的一個(gè)重要方面。

目前，國內(nèi)外眾多學(xué)者已對(duì)建筑物群的移位算法進(jìn)行了研究[2-11]。其中Snake模型是典型的解決沖突的方法，最初應(yīng)用于線要素移位[12]。然而，Snake模型在建筑物群移位中有些許不足，如無法較好的識(shí)別和保持呈對(duì)齊排列的建筑物群的空間關(guān)系；無法較好解決Snake內(nèi)部自身的空間沖突，即建筑物之間的沖突。本文在Snake算法研究的基礎(chǔ)上，對(duì)其進(jìn)行改進(jìn)，最后利用改進(jìn)的Snake模型進(jìn)行建筑物群的移位，取得較好的效果。

1Snake模型簡(jiǎn)介

Snake模型是能量最小化方法，將要素的幾何特征變化作為內(nèi)部能量，外部空間沖突作為外部能量，通過微分方程求解得到總能量最小時(shí)的矩陣方程，K·D=F，再利用有限元方法對(duì)矩陣方程求解，得到移位后的形狀和位置[12]。其中，K為剛度矩陣，F(xiàn)為單元的受力矩陣，D為在受力矩陣F的作用下，線段首末端點(diǎn)的移位量和一階導(dǎo)數(shù)變化。Snake模型將力分為x和y兩個(gè)方向分別來求解，分別求得x，y方向的移位量，最后把x和y方向的移位量進(jìn)行合成得到每個(gè)點(diǎn)的真實(shí)移位量。

本文在應(yīng)用Snake算法進(jìn)行建筑物移位時(shí)，同文獻(xiàn)[12]中一樣，將街區(qū)中的建筑物群用重心表示，用最小生成樹連接所有建筑物的重心，然后進(jìn)行整體移位，保持建筑物群的空間關(guān)系。

2Snake模型改進(jìn)

2.1　對(duì)齊排列建筑物群識(shí)別的改進(jìn)

地圖綜合中，成對(duì)齊分布的建筑物群很容易被人眼識(shí)別，需要在制圖綜合中加以保護(hù)，保證移位前后建筑物群的空間排列關(guān)系不變。文獻(xiàn)[12]中曾提出一種判別建筑物群成對(duì)齊分布的方法，但是存在較容易判別失誤及建筑物的方向計(jì)算有局限性的缺點(diǎn)。本文利用格式塔中的一些原則進(jìn)行改進(jìn)。

格式塔原理最開始應(yīng)用于心理學(xué)，它主要指人們?cè)谝曈X判斷和識(shí)別的時(shí)候，會(huì)不自覺的受到一些規(guī)則和約束的影響，它包括接近性原則、相似性原則、連續(xù)性原則和完整性原則等。而對(duì)齊排列建筑物群也遵循著格式塔的規(guī)律，在其內(nèi)部每個(gè)建筑物大體相似，且相互間距離接近。因此，本文利用格式塔原理中的接近性原則和相似性原則來識(shí)別呈對(duì)齊排列的建筑物群。在算法中，接近性原則用兩個(gè)建筑物間的歐式距離d表示，相似性原則用兩個(gè)建筑物間的面積大小差異Ws和方向差異Wd表示；然后將Wd和Ws分別作為權(quán)值加載到距離d上，獲取兩個(gè)建筑物間的親近度f，

(1)

其中，f越小，建筑物間關(guān)系越親密；f越大，建筑物間關(guān)系越疏遠(yuǎn)，若幾個(gè)建筑物間比較親密，且親近度f差不多大，則認(rèn)為它們屬于同一個(gè)對(duì)齊排列的建筑物群。

通過實(shí)驗(yàn)，確定Wd對(duì)應(yīng)的角度變化為[0，90o]，設(shè)Wd權(quán)值變化為從1到2，角度差值越大，權(quán)值Wd越大。單個(gè)建筑物的角度計(jì)算如圖1所示，做多邊形的最小面積外接矩形(對(duì)凹多邊形而言，要先做凸殼，再做最小面積外接矩形)，再計(jì)算該外接矩形的長軸方向(長軸是指連接矩形各邊中點(diǎn)的連線中，最長的那條線，以長軸與平面坐標(biāo)系中x軸方向的夾角(0~90o)作為建筑物的方向角度)作為角度大小。

圖1　建筑物的方向

用Ws表示兩個(gè)建筑物間的面積大小差異權(quán)值，用兩個(gè)建筑物的面積比表示(面積小的多邊形比面積大的多邊形)。同理，參數(shù)Ws的范圍也是根據(jù)實(shí)驗(yàn)后確定的。面積比的范圍為[0,1]，設(shè)Ws的權(quán)值范圍為[0,2]，面積比越小，權(quán)值越大，兩個(gè)建筑物的面積差異越懸殊。強(qiáng)制在面積比小于0.25時(shí)，權(quán)值Ws為2。

根據(jù)式(1)，得到結(jié)果，如圖2和表1所示。從表1中發(fā)現(xiàn)線段17的親近度特別小，因?yàn)榫€段17連接的兩個(gè)建筑物在圖上存在空間沖突，因此它們之間的實(shí)際距離較其它要小很多(同時(shí)，若探測(cè)到建筑物之間存在壓蓋沖突，即它們之間實(shí)際距離為0，則在程序?qū)崿F(xiàn)時(shí)，強(qiáng)行設(shè)定它們間的距離為0.001m)。因此，將線段17連接的兩個(gè)建筑物先提取出來。同時(shí)，在剩余的親近度中，線段8,9,10的親近度是最小的，且相互之間比較相近，可以識(shí)別出它們連接的建筑物屬于對(duì)齊排列的建筑物群。

圖2　每條連接邊的權(quán)重值

找到對(duì)齊排列的建筑物群和有沖突的建筑物后，做它們的凸殼，如圖3所示，圖中陰影部分為凸殼。將凸殼與其它剩余建筑物一起，在Snake模型下移位，當(dāng)它們最后移動(dòng)到合理的位置后，記下凸殼的移位量，然后將這個(gè)移位量加到每一個(gè)組成其凸殼的建筑物中，這樣，組成對(duì)齊建筑物群的每一個(gè)建筑物移位量都相同，保證凸殼內(nèi)部之間的空間關(guān)系不變。同時(shí)，對(duì)圖3中的凸殼1而言，凸殼內(nèi)部的建筑物之間是有沖突的，需要在內(nèi)部對(duì)沖突建筑物進(jìn)行調(diào)整。

2.2　建筑物之間受力模型的改進(jìn)

在用傳統(tǒng)Snake模型進(jìn)行建筑物移位時(shí)，建筑物之間沖突的受力計(jì)算與建筑物與道路沖突的受力計(jì)算方法是不同的，建筑物之間是用緩沖區(qū)計(jì)算受力，而建筑物與道路之間是用距離計(jì)算受力[12]。這兩種不同的計(jì)算方式所得數(shù)值在數(shù)量級(jí)上相差很大，當(dāng)同時(shí)存在著兩種沖突時(shí)，有時(shí)不易解決建筑物內(nèi)部的沖突。如圖4(a)所示，建筑物A、B、C通過最小生成樹相連，其中建筑物A與街道有沖突，建筑物B與C之間有沖突。在移位中，由于Fa>Fb，會(huì)促使著建筑物B向C的方向移動(dòng)，造成移位后建筑物B與C仍然沖突的局面，如圖4(b)所示。

圖4　建筑物內(nèi)部沖突移位后仍然存在

為了解決這個(gè)問題，將建筑物群實(shí)行分層次移位。先將相互間有沖突的建筑物整體移位，然后根據(jù)四種沖突模型，分別進(jìn)行調(diào)整，解決建筑物之間的沖突。先設(shè)定要素間的所需最小距離值為0.2mm(即人眼在地圖上可分辨的最小距離)。

建筑物之間的沖突分兩種，一種是符號(hào)之間距離太近，在視覺上出現(xiàn)擁擠而產(chǎn)生的鄰近沖突，如圖5(a)所示。每個(gè)建筑物在地圖上占據(jù)一定大小的空間，面積越大，移動(dòng)時(shí)對(duì)周圍要素的影響越大，基于此，本文在移位時(shí)考慮建筑物的面積因素，面積大小與移位量成反比。隨后分別做兩個(gè)建筑物寬度為0.1mm的緩沖區(qū)，這兩個(gè)緩沖區(qū)相交于點(diǎn)P1，P2，連接P1P2，垂直于P1P2指向B1的方向，同理，V2為建筑物B2的受力方向。

(2)

另一種是建筑物之間互相壓蓋產(chǎn)生的空間沖突，如圖5(b)、5(c)、5(d)所示。壓蓋方式不同，受力分析也不同。依據(jù)符號(hào)壓蓋產(chǎn)生的相交線的中點(diǎn)來判斷不同壓蓋方式。

圖5(b)為相交連線P1P2的中點(diǎn)P在相交多邊形內(nèi)部的情況。沖突解決方案為式(3)。對(duì)建筑物B1而言，找出既在B1邊界也在相交多邊形(圖中陰影部分)邊界上，且距離連線P1P2最遠(yuǎn)的點(diǎn)F1，記距離為dmax1，同理，找出建筑物B2的點(diǎn)F2及距離dmax2。點(diǎn)F1到連線P1P2方向的垂線向量V1為B1的受力方向；點(diǎn)F2到連線P1P2方向的垂線向量V2為B2的受力方向。

(3)

圖5(c)為相交連線P1P2的中點(diǎn)P在相交多邊形邊界上的情況，沖突解決方案為式(4)。找到相交多邊形(圖中陰影部分)邊界上距離連線P1P2最遠(yuǎn)的點(diǎn)，計(jì)算到連線的距離dmax，兩個(gè)建筑物的受力大小分別為F(B1)，F(xiàn)(B2)；垂直于連線P1P2指向B1的方向，同理，V2為建筑物B2的受力方向。

(4)

圖5(d)為符號(hào)相交連線P1P2的中點(diǎn)P在相交多邊形外部的情況，沖突解決方案為式(5)。在相交多邊形(圖中陰影部分)中找到離連線P1P2距離最大的點(diǎn)，作最遠(yuǎn)點(diǎn)到連線的垂線，然后取垂線在相交多邊形中的部分，計(jì)算它的長度，記為dmax，兩個(gè)建筑物的受力大小分別為F(B1)，F(xiàn)(B2)；其方向同上面一樣。

(5)

第二種壓蓋沖突的建筑物經(jīng)過上面移位后，符號(hào)之間已移開，沒有了壓蓋，但相互間距離太小，仍然存在第一種鄰近沖突，但它們之間的受力模型已變?yōu)閳D5(a)的類型。因此，還需要再利用第一種受力模型中的方法對(duì)建筑物進(jìn)行后續(xù)移位，方可最終解決空間沖突。

圖5　建筑物之間的四種受力模型

3實(shí)驗(yàn)與分析

圖6是應(yīng)用改進(jìn)的Snake模型對(duì)某地區(qū)建筑物群進(jìn)行移位的示例圖，圖上最小可識(shí)別距離為0.2mm。圖6 (a)是移位前的情況，圖6(b)是移位后的情況。從圖6中可以看到，大部分沖突在移位后解決的比較好，并且建筑物相互間的沖突通過移位后得到了解決，空間拓?fù)潢P(guān)系也保持的很好，街區(qū)內(nèi)的重要的空間拓?fù)潢P(guān)系，如對(duì)齊排列的建筑物，移位后的相互空間關(guān)系也沒有被破壞。

4結(jié)束語

通過實(shí)驗(yàn)可以看到，在建筑物群移位算子中應(yīng)用改進(jìn)后的Snake算法，總體上可以滿足制圖綜合的需要，但也存在問題需要進(jìn)一步的解決。一是在移位區(qū)域不充裕時(shí)如何移位，既要滿足建筑物與道路沖突的解決，也不能與其它建筑物之間產(chǎn)生沖突，這可能需要建筑物適當(dāng)?shù)淖冃?；二是Snake算法本身參數(shù)的不好確定，Snake算法的兩個(gè)形狀參數(shù)α，β在不同比例尺、不同受力大小下的值都不一樣，現(xiàn)在需要人為確定，并沒有一個(gè)統(tǒng)一的模型設(shè)定準(zhǔn)確的值。

參考文獻(xiàn)：

[1]周炤，肖強(qiáng)，趙國成，等.基礎(chǔ)地理空間數(shù)據(jù)持續(xù)更新模式分析[J].測(cè)繪工程，2014,23(1)：12-16.

[2]劉小春，華一新，鄭剛，等.面向服務(wù)的分級(jí)地理空間數(shù)據(jù)中心框架的構(gòu)建[J].測(cè)繪工程，2014,23(1)：57-60.

[3]趙軍喜，孫慶輝，張亞軍.地理空間元數(shù)據(jù)理論體系研究[J].測(cè)繪工程，2014,23(4)：10-13.

[4]費(fèi)立凡，河津.解決街道與建筑物圖形沖突的移位模型研究[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版，2007,32(6)：540-543.

[5]WAREJM，JONESC.B.ConflictReductioninMapGeneralizationUsingIterativeImprovement[J].GeoInformatica,1998,2(4):383-407.

[6]WAREJM，JONESCB.AutomatedMapGeneralizationwithMultipleOperators：ASimulatedAnnealingApproach[J].GeographicalInformationScience，2003,17(8):743-769.

[7]LONERGANME，JONESCB.AnIterativeDisplacementMethodforConflictResolutioninMapGeneralization[J].Algorithmica,2001,30,287-301.

[8]WILSONID，WAREJM，WAREJA.AGeneticAlgorithmApproachtoCartographicMapGeneralization[J].ComputersinIndustry,2003,52,291-304.

[9]艾廷華.基于場(chǎng)論分析的建筑物群的移位[J].測(cè)繪學(xué)報(bào)，2004,33(1)：89-94.

[10]HOJHOLTP.SolvingSpaceConflictsinMapGeneralization：UsingaFiniteElementMethod[J].CartographyandGeographicInformationScience，2000,27(1)：65-73.

[11]吳小芳，杜清運(yùn)，徐智勇.多層次移位原則的道路與建筑物空間沖突處理[J].測(cè)繪學(xué)報(bào)，2010，39(6)，649-654.

[12]BADERM.EnergyMinimizationMethodsforFeatureDisplacementinMapGeneralization[D].Zurich：DepartmentofGeography，UniversityofZurich，2001:138-143.

[責(zé)任編輯：李銘娜]