基于Snake模型的建筑物群移位算法改進研究

基于Snake模型的建筑物群移位算法改進研究

楊莉

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

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

關鍵詞：Snake模型；建筑物群；空間關系；受力模型

中圖分類號：P208

收稿日期：2014-05-15

作者簡介：楊莉(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

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

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

1Snake模型簡介

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

本文在應用Snake算法進行建筑物移位時，同文獻[12]中一樣，將街區中的建筑物群用重心表示，用最小生成樹連接所有建筑物的重心，然后進行整體移位，保持建筑物群的空間關系。

2Snake模型改進

2.1　對齊排列建筑物群識別的改進

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

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

(1)

其中，f越小，建筑物間關系越親密；f越大，建筑物間關系越疏遠，若幾個建筑物間比較親密，且親近度f差不多大，則認為它們屬于同一個對齊排列的建筑物群。

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

圖1　建筑物的方向

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

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

圖2　每條連接邊的權重值

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

2.2　建筑物之間受力模型的改進

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

圖4　建筑物內部沖突移位后仍然存在

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

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

(2)

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

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

(3)

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

(4)

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

(5)

第二種壓蓋沖突的建筑物經過上面移位后，符號之間已移開，沒有了壓蓋，但相互間距離太小，仍然存在第一種鄰近沖突，但它們之間的受力模型已變為圖5(a)的類型。因此，還需要再利用第一種受力模型中的方法對建筑物進行后續移位，方可最終解決空間沖突。

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

3實驗與分析

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

4結束語

通過實驗可以看到，在建筑物群移位算子中應用改進后的Snake算法，總體上可以滿足制圖綜合的需要，但也存在問題需要進一步的解決。一是在移位區域不充裕時如何移位，既要滿足建筑物與道路沖突的解決，也不能與其它建筑物之間產生沖突，這可能需要建筑物適當的變形；二是Snake算法本身參數的不好確定，Snake算法的兩個形狀參數α，β在不同比例尺、不同受力大小下的值都不一樣，現在需要人為確定，并沒有一個統一的模型設定準確的值。

參考文獻：

[1]周炤，肖強，趙國成，等.基礎地理空間數據持續更新模式分析[J].測繪工程，2014,23(1)：12-16.

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

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

[4]費立凡，河津.解決街道與建筑物圖形沖突的移位模型研究[J].武漢大學學報:信息科學版，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]艾廷華.基于場論分析的建筑物群的移位[J].測繪學報，2004,33(1)：89-94.

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

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

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

[責任編輯：李銘娜]