基于加權K-means聚類與路網(wǎng)無向圖的地圖分割算法

肖尚華，胡燦林

（四川大學計算機學院，成都 610065）

0 引言

依托高速增長的交通大數(shù)據(jù)體量與運算能力，智能交通與智慧城市已成為人工智能浪潮的一個重要組成部分。其應用包括OD推算，通勤時間預測及城市區(qū)域分割等多個方面。其中區(qū)域分割可通過將城市地圖劃分，達到簡化并抽象城市交通網(wǎng)絡的作用，并可作為其他某些應用的基礎。

目前地圖數(shù)據(jù)主要以向量化的路網(wǎng)無向圖的方式對城市地圖信息進行存儲，其代表如GeoJson格式、Shapefiles文件等。以GeoJson文件為例，城市的地理信息主要以帶屬性的線段集合方式存儲。每個線段由有序的經(jīng)緯度坐標軸組成。每個經(jīng)緯度線段集合可具有多個屬性值，可攜帶該折線的類型（如高速公路、河流、鐵路），名稱等信息。而傳統(tǒng)的地圖分割算法均以像素化而非向量化的地圖數(shù)據(jù)為基礎。

傳統(tǒng)的基于圖像地圖的分割中，普遍通過對像素點進行聚類進行實現(xiàn)[1-2]。數(shù)字圖像的像素點由0到255的灰度值進行表示，其像素點灰度值的差異可通過多種范數(shù)進行衡量。不同的聚類方法，如均值漂移（Mean Shift）或譜聚類（Spectrum Clustering），可通過這些范數(shù)衡量相鄰像素點之間的差異，從而對圖像的每個像素點聚進行聚類。通過聚類后將圖像不同的區(qū)域劃分為不同的類，從而分割出圖像中的不同物體，前后景。但由于基于向量表達的城市地圖數(shù)據(jù)僅將有意義的地理信息以離散向量進行存儲，其直觀上并沒有覆蓋全部地理空間，故無法使用傳統(tǒng)方法對其進行分割。為解決此問題，本文提出一種基于通過對路網(wǎng)無向圖進行德勞內三角化，對地圖數(shù)據(jù)進行加權K-means聚類的地圖分割算法。并通過代碼實現(xiàn)及可視化驗證了該算法的有效性。

1 相關工作

本文主要依賴的現(xiàn)有工作為德勞內三角化[3]（De?launay Triangulation）以及K-means聚類[4]（K-means Clustering）。對于給定的離散點集合，德勞內三角化可將該點集轉換為一個連通圖，使得該圖由三個一組且相互不相交的三角形回路組成。在得到三角的過程中，德勞內三角通過最大化每個三角內的最小內角來避免過于狹窄的三角形，故其可以看做是一種最優(yōu)化問題。K-means是數(shù)據(jù)科學、圖像等領域應用最為廣泛的算法之一。對于給定的離散點集合及范數(shù)，其將與聚類中心最接近的點加入聚類中心所屬的集合，并迭代的更新聚類中心直到收斂。故其可以非監(jiān)督地方式將離散數(shù)據(jù)進行自動分類。

2 算法實現(xiàn)

2.1 地圖數(shù)據(jù)的德勞內三角化

為了將向量化的地圖數(shù)據(jù)轉化為可覆蓋整個城市二維平面的數(shù)據(jù)，首先將其德勞內三角化。以成都市錦江區(qū)為例，假設傳入的地理信息為道路、河流等線段類數(shù)據(jù)及錦江區(qū)邊界的多邊形數(shù)據(jù)。其數(shù)據(jù)通過以下形式存儲：

坐標列表：

[[104.0454671,30.4769304],[104.0453439,30.476933],……[104.0430272,30.4769812],[104.0368152,30.4769258]]

屬性鍵值對："highway":"secondary";"name":"錦江路一段"……"oneway":"yes"

要得到鋪滿且不重疊的錦江區(qū)的德勞內三角，首先需要將位于錦江區(qū)內的坐標點過濾出。對錦江區(qū)邊界構建多邊形路徑后，通過W.Randolph Franklin提出的PNPoly算法對所有地理信息點判斷其是否屬于該多邊形路徑。得到所有屬于該區(qū)域的點后將所有同一條線路內兩個相鄰的點構成的線段依據(jù)其所屬道路的屬性賦予相應的權重，存儲為權重字典。具體方法將在后文敘述。得到范圍內的點后，將范圍內的點加入邊界點列表，形成一個完整的點集合。對該集合進行德勞內三角化，得到一個鋪滿且無重疊的三角集合，三角集合在地圖上形成一個凸多邊形。其中每個三角形以三個頂點的經(jīng)緯度進行表示。

形成初步的三角集合后，需要將位于邊界外的三角過濾。每個三角形設置一個標志位：對每條邊，若該邊的中點在邊界內或該邊屬于邊界集合，則標志位加1。若該三角形最終標志位不為3，則將該三角形刪除。過濾后則可形成可用于聚類與分割的最終的三角形集合。最終三角形集合效果如圖1所示。

圖1 德勞內三角化后的成都市錦江區(qū)地圖

由圖可見錦江區(qū)被切割為了互不重疊且鋪滿的三角形。

2.2 確定三角的中心

得到三角形集合后，為進行聚類，需要給每個三角形分配一個聚類時的代表中心?？紤]到集合中存在大量的狹長三角形，而為實現(xiàn)更好的效果應該讓長邊相鄰的三角形有限于短邊相鄰的三角形進行融合，故采用三角形中最長垂線的中點最為聚類時的代表中心。采用最長垂線中點為中心的效果與采用定點均值為中心的差異如圖2所示?？梢钥吹揭宰铋L垂線中點為中心時，狹長三角形顯著地傾向于與長邊相鄰的距離更近。而以定點均值為中心時，這種傾向并不顯著。

圖2 左圖為以最長垂線中點為中心，右圖為以頂點均值為中心

2.3 三角中心的加權K-means聚類

對三角形進行加權聚類的目的是使聚類的邊界能夠最大程度地集中在地圖數(shù)據(jù)中存在的道路、河流、鐵路等現(xiàn)有線段上，以得到更有依據(jù)的劃分與更好的視覺效果。此處加權K-means的核心思想是，對于分布在二維平面上由歐式距離衡量的待聚類的三角中心點，通過對歐氏距離加權的方式映射到一個新的距離空間上，再在這個空間上對三角中心點進行K-means聚類。故對于三角形的聚類可分為兩步：新的距離空間映射，以及K-means聚類。

對于兩個三角形中心，其連線與這兩個三角形的公共邊具有一定且唯一的交點。故要為每對三角中心點之間的距離分配的權重，可通過2.1中進行德勞內三角化前生成的權重字典獲得。假設所有地圖數(shù)據(jù)中原始的道路、河流線段集合構成一個地理線段集，則對任意公共邊進行如下判斷：若公共邊不屬于地理線段集的，則設權重為1；對于公共邊屬于地理線段集，且線段的屬性為小型道路，如步道、小區(qū)道路，則設權重為1.5；若線段的屬性為大型道路，如高速路、鐵路，則設權重為3。分配權重后，由以下公式：

求得新的距離。其中i，j為三角形下標。

圖3展示了對于一個聚類中心，進行54次迭代并得到一個由道路包圍的區(qū)域的實現(xiàn)效果?？梢钥吹?，從第20次到第30次迭代時，雖然存在公共邊為道路的兩個三角形中心的原始歐氏距離更加接近的情況，但由于三角形中心已經(jīng)被映射到了新的距離空間，故聚類中心仍然優(yōu)先選擇了處于道路同一方的其他三角進行了融合。由此可見，加權K-means可以使地圖分割時更傾向于按照地圖原有的地理信息作為邊界進行分割與區(qū)域生成。

圖3 對三角化后的進行加權K-means聚類的示意圖

紅框中1至4分別為迭代0次，迭代20次，迭代30次，迭代54次的效果圖。

2.4 生成聚類邊界

得到聚類區(qū)域的三角形集合后，需要解析出該類的邊界。即以三角形所有邊組成邊集合，則刪除所有處于區(qū)域內部的邊，并將邊界點有序排列，得到一個封閉多邊形的頂點序列。由于所有區(qū)域的內部邊一定為兩個三角形的公共邊，所以可通過刪除所有重復的邊得到邊界的無序點集。而由于由多個三角形的邊組成的區(qū)域一定為封閉邊界，故每個邊一定在兩端與其他邊具有相同端點。假設要從任意邊出發(fā)，不斷加入新的邊以進行解析，則可通過迭代地尋找該邊集合中與當前邊界序列尾部具有相同端點的邊，最終得到封閉的有序邊界序列。

圖4

3 算法實現(xiàn)及實驗效果

在實驗階段，以基于Python的相關科學計算模塊為基礎實現(xiàn)了算法，其中通過Matplotlib模塊實現(xiàn)了德勞內三角化，并通過Numpy和Scipy模塊簡化了向量運算。最終的輸出為一個多邊形列表，每個多邊形由多個有序的經(jīng)緯度對序列組成。形式如圖4所示。

通過基于JavaScript的開源地圖工具OpenLayers進行可視化后，最終區(qū)域劃分效果如圖5所示。可以看出，對于不同形狀與大小的行政區(qū)域，地圖基本上都基于道路、河流域鐵路等具有實際意義的地理信息被劃分為了不同的區(qū)域。并且在不同的切割數(shù)量上都可以達到較好的效果。

圖5 對成都市下不同行政區(qū)劃分為不同數(shù)量的區(qū)域

左為錦江區(qū)，劃分為5個區(qū)域。中為武侯區(qū)，劃分為25個區(qū)域。右為成華區(qū)，劃分為100個區(qū)域。其中白色高亮區(qū)域為選中樣式。

4 結語

本文針對目前流行的地圖數(shù)據(jù)結構提出了一種自適應地圖分割算法，并進行了代碼實現(xiàn)及其可視化。該算法通過對向量化的地圖數(shù)據(jù)進行德勞內三角化使數(shù)據(jù)能映射到整個地圖邊界所包含的二維空間，并通過加權K-means聚類的方式對三角進行融合，最終得到具有實際地理意義并符合視覺直覺的地圖分割結果。

參考文獻：

[1]吳信才,鄧志勇,謝忠.彩色地圖影像分割方法及其實現(xiàn)[J].上海：計算機工程,2003：29(1):176-177.

[2]郭玲,周獻中.基于模糊最大熵原則的地圖圖像分割[J].成都：計算機應用,2002：22(11):18-19.

[3]Hartigan,J.A.;Wong,M.A.Algorithm AS 136:A K-Means Clustering Algorithm.Journal of the Royal Statistical Society.Series C(App-lied Statistics).1979：28(1):100-108

[4]Cignoni,P，C.Montani，R.Scopigno.DeWall:A Fast Divide and Conquer Delaunay Triangulation Algorithm in Ed.Computer-Aided Design.1998：30(5):333-341