橫-縱掃描的Voronoi圖柵格生成算法

2019-04-11 02:23:30劉青平趙學勝孫文彬

測繪學報 2019年3期

劉青平，趙學勝，王磊，孫文彬

1. 中國礦業大學(北京)地球科學與測繪工程學院,北京 100083； 2. 河南理工大學測繪與國土信息工程學院,河南焦作 454000

Voronoi圖(簡稱V圖)是計算幾何學中一個重要的數據結構，具有自然鄰近、動態穩定等特性，在計算機圖形學、地理信息系統、生態學、分子化學、氣象學、機械、醫學、藝術等領域得到了廣泛應用[1-6]。其中，V圖結構的高效、準確生成是其諸多應用順利實現的關鍵。國內外學者對V圖生成算法進行了許多研究，其成果主要分為矢量算法和柵格算法兩類。

經典矢量算法包括分治算法[7]、插入算法[8]、掃描線算法[9]、投影算法[10]等。矢量算法對生長元有一定的局限性[11]，只能將點和線段(或半線)作為生長元處理，較難生成線集圖[12]，對于面和其他更復雜的空間目標要將其分解為點和線后才能處理，這種分解嚴重地破壞了空間生長目標的完整性。矢量算法不僅算法復雜，而且產生的數據結構復雜，不利于海量數據的處理[13]。

為彌補矢量算法的不足，許多學者提出了基于柵格數據的V圖生成算法。柵格V圖生成算法的關鍵是為每個格網找到距其最近的種子點(或線、面)。依據格網得到種子點歸屬方法的不同，現有柵格V圖生成算法可分為3類。第一類算法，是較為傳統的通過多邊形的擴張和距離變換來得到V圖，如距離變換算法[13-14]、擴張算法[15-16]等。這類算法通過使用柵格距離代替歐氏距離來提升效率，所用模板有棋盤距離、城市距離、八角距離等。這些距離指標只是最優距離度量(歐幾里得距離)的粗略近似。這類算法的誤差很難控制，隨著格網和種子點數量增多而加大。第二類算法是利用四叉樹等數據結構通過區域劃分并判斷區域歸屬的方式來得到V圖，如層次算法[17-18]、細分算法[19]等。此類算法大多較為復雜，不同層次、區域拓撲關系不明朗，且很難動態添加刪除數據。第三類算法是通過計算與比較格網與種子點之間的距離得到V圖，如確定歸屬算法[20-21]、柵格掃描算法[22]等。此類算法使用歐氏距離作為距離基準，大多具有較好的精度指標。除此之外，一些學者也通過并行計算來對上述各類算法的效率進行改進[16,21,23-24]，但是通常情況下，計算機技術并不能提升算法的精度。

綜合精度和效率因素，柵格掃描算法是最優的柵格V圖生成算法之一。此類算法通常利用鄰域模板對所有格網進行向前向后兩次掃描得到V圖。算法既符合計算機離散特征，又優化了歐氏距離算法，在大數據量情況下，較其他第三類柵格V圖生成算法具有效率上的優勢[25]。但是由于柵格距離與歐氏距離的差異，在掃描過程中部分單元的歸屬不可避免地產生一定的誤差[26]。然而，在地圖、軍事、醫學[3-5]等高精度領域的應用中，V圖的誤差可能會造成嚴重的后果。例如，在海洋劃界工作中，V圖是問題的理想解決辦法[6]。不過，在海洋區域的劃界中出現任何位置誤差，就會增加一個國家的海洋空間，而損害另一個國家的海洋空間。這種情況可能對有關國家的經濟、軍事活動和國家關系產生嚴重影響。

為此，本文提出了一種基于橫-縱掃描的V圖生成改進算法，即根據傳統算法產生誤差的區域特征，在一個正常周期的水平(橫向)掃描后，增加一個周期豎直(縱向)掃描，實現柵格V圖的高效、準確生成，并把誤差控制在一個格網以內，最后進行了試驗對比分析。

1 傳統掃描算法原理及缺陷

1.1 傳統掃描算法原理

與矢量空間Voronoi區域是連續的相同，在柵格空間，一般情況下Voronoi區域也是連續的，即一個柵格格網和它的部分鄰近格網屬于相同的Voronoi區域。根據這個特點，利用鄰近格網之間最近種子點的傳遞，格網就可以從它鄰近格網處得到它所屬的Voronoi區域，而不必與所有種子點進行距離比較。

傳統柵格掃描算法[22]原理是通過一個33的鄰域模板將一個格網的信息傳遞給它的鄰近格網(如圖1所示)。首先，進行正反兩次掃描：掃描開始之前格網P被賦予一個空值，正向掃描按從左到右、從上到下的順序逐行進行，掃描過程中格網P分別計算并比較與Q1、Q2、Q3和Q4這4個鄰近格網(臨時)最近種子點之間的距離，然后將距離最短的種子點作為當前格網P的(臨時)最近種子點，可用公式(1)來表示；反向掃描按從右到左、從下到上的順序逐行進行掃描，通過距離的計算與比較從P的臨時最近種子點及Q5、Q6、Q7和Q8的最近種子點中獲取P的最終最近種子點。一般情況下，Q1到Q8至少有一個與格網P有相同的最近種子點。在正反兩次掃描過程中，格網P通過與其鄰近格網的(臨時)最近種子點的距離計算與比較得到其最近種子點，這一過程稱為格網P得到其正確歸屬種子點。

圖1 3×3鄰域示意圖Fig.1 3 × 3 neighborhood diagram

(1)

1.2 傳統算法缺陷分析

本文將一次正向掃描和一次反向掃描稱作一個水平周期掃描。按上述算法進行了一個周期掃描之后，大多數的格網單元都得到了正確的種子點，但仍有少數格網單元的歸屬信息是錯誤的(如圖2)。

如圖2所示，格網A、B和C為該V圖種子點，其正確結果如圖2(a)所示，格網M、N、P和Q的正確歸屬均為種子點B。但是，一個水平掃描周期后，格網M、N、P和Q沒有得到其正確歸屬，如圖2(d)。這是由于正向掃描為從上到下的逐行掃描，格網M、N、P和Q的掃描順序在種子點B之前，它們歸屬判斷的種子點并不包括種子點B，正向掃描完成后這4個格網暫時歸屬于種子點A，如圖2(b)所示；當反向掃描到格網M時，此時它的鄰近格網5-8歸屬于種子點C，格網1-4歸屬于種子點A，格網M只能從其臨近格網的歸屬(種子點A和C)中進行判斷比較，而不能得到其正確歸屬(種子點B)，如圖2(c)。在整個水平掃描周期過程中，正反兩次與格網M進行距離計算和比較的種子點中都沒有包括其正確的最近種子點(種子點B)，造成了錯誤的出現。

掃描算法核心是在掃描過程中通過每個格網的與部分種子點之間的距離計算和比較得到該格網的最近種子點。然而由于傳統算法掃描的不完備，上述錯誤的出現主要因為在掃描過程中對某一格網(如格網M)所進行的距離計算與比較并沒有包括其最近種子點，致使該格網的歸屬出現錯誤。圖3(a)為一隨機種子點情況下傳統柵格掃描算法得到的V圖，圖3(c)為確定歸屬算法得到的正確的V圖，可以看出它們之間有較大的差異，如圖3(b)黑色區域所示。

也有學者在掃描算法結果的基礎上，進行多周期的相同掃描過程以減少不正確歸屬格網的數量，但是為得到正確V圖，重復掃描周期的次數n是難以控制的。

2 改進算法

2.1 歸屬出錯單元范圍界定

首先分析種子點經一個周期掃描后錯誤歸屬單元的空間分布特征。

如圖4所示，格網A和格網B為種子點。在進行正向掃描時，掃描順序為從左到右、從上到下順序逐行進行掃描。因為所選模板為3×3模板，所以掃描順序在種子點A左上方格網1之前的格網，都沒有計算和比較過與種子點A之間的距離。與格網1為同一行且掃描順序在格網1之后的格網，都可以從其左側格網處得到種子點A。種子點A同一行的格網中，最早得到種子點A的是格網2，它是從其右上方格網1處得到的。這樣臨時歸屬于種子點A的格網就形成了一個135°的角度，由格網1向左下方延伸。在掃描到達種子點B附近時，經過了與種子點A相同過程。于是在正向掃描結束時，就形成了如圖4所示的臨時種子點歸屬圖，其中淺藍色格網歸屬于種子點A，淺綠色格網歸屬于種子點B。

單次反向掃描過程與正向掃描過程類似。其結果如圖5所示。

在傳統掃描算法中，一個格網需經過正反兩次掃描，如果其在任意一次掃描過程中得到正確種子點，那么便能得到正確歸屬。如圖6所示，藍色部分格網在正向掃描后必定可以得到種子點C，綠色部分格網在反向掃描時必定可以得到種子點C，紫色部分格網是它們的重合部分。白色部分格網想要得到種子點C就需要反向掃描時藍色格網的傳遞，如果傳遞被阻隔的話(例如圖2)，那么部分格網就不能得到其正確歸屬，造成單元歸屬出錯。從上面的分析可以看出：可能出現歸屬錯誤的區域單元(圖6白色單元)位于其正確種子點的左下方(Ⅰ區)與右上方(Ⅱ區)。

2.2 改進方法

在找到了出現單元歸屬錯誤的區域后，本文設計了一種水平掃描后接豎直掃描的解決方案。豎直掃描保持數據結構不變，掃描模板仍為3×3模板(如圖1所示)。豎直掃描方向為豎直方向，掃描順序為先從左上角開始由下至上的逐列向右掃描一次為正向掃描，模板中心格網P從Q1、Q4、Q6和Q2這4個鄰近格網中得到其最近種子點。再從右下角開始從下至上的逐列向左掃描一次為反向掃描，模板中心格網P從Q8、Q5、Q3和Q2這4個鄰近格網中得到其最近種子點。正反兩次掃描稱為一個豎直掃描周期。

與水平掃描周期相同，豎直掃描周期正反掃描同樣具有類似的過程，其結果如圖7所示，其中圖7(a)為單次正向掃描后的結果，圖7(b)為單次反向掃描后的結果。

水平掃描后接豎直掃描的解決方案對一個格網進行兩個周期共4次掃描，可以完全覆蓋該種子點周圍所有區域，如圖8所示。藍色格網為豎直周期正向掃描覆蓋區域，綠色格網為豎直周期反向掃描覆蓋區域，紫色區域為他們重合區域。左側的淺綠色區域(Ⅰ區)和右側的淺藍色區域(Ⅱ區)為水平周期無法完全覆蓋的區域，但是可以被豎直周期覆蓋。這樣就保證了種子點周圍所有區域在經過水平、豎直兩個周期掃描后都可以得到該種子點。

3 試驗與分析

確定歸屬算法是根據V圖定義，計算并比較所有柵格與每一個種子點之間的距離，來確定格網單元的最近種子點。其需要進行大量的距離計算與比較，隨著空間分辨率的增大，要處理的數據量急劇上升，算法效率大大降低，實際操作性較差。但是其算法精度高，相較于正確矢量結果，其誤差在一個格網以內。因此，本文選擇確定歸屬算法作為算法精度評判的基準。

本文算法所用的編程語言為C++，顯示所用的三維圖形接口為Microsoft OpenSceneGraph SDK (17.1)，硬件環境為Intel(R) Core(TM) i5-3337U CPU @1.80 GHz， 2.70 GB內存。并與改正前算法和確定歸屬算法在精度和效率方面進行了對比，如圖9為改正后算法在10、100和1000種子點數量時生成的結果示意圖，表1為確定歸屬算法、原掃描算法和改正后的算法在不同格網數和不同種子點數情況下所花費的時間。

表1 不同算法生成V圖所用時間

由表1可以看出，在格網數和種子點數較少情況下，確定歸屬算法與掃描算法效率相差不大。但是在數據量較大的情況下，掃描算法具有明顯的速度優勢，且隨著格網數和種子點數量的增加這種優勢越來越明顯。而改進后掃描算法與原算法效率大體相當。

圖10為在3000×3000格網數情況下，3種算法所需時間隨種子點數量增加而變化的情況，確定歸屬算法在10 000種子點數量情況下由于所需時間太長而無法在圖中表示。由圖可以看出，確定歸屬算法那所需時間隨種子點數量增加而劇烈增加，而掃描算法時間幾乎不變。改正后的算法在時間上略高于原算法，但遠低于確定歸屬算法。