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

劉青平，趙學(xué)勝，王 磊，孫文彬

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

Voronoi圖(簡(jiǎn)稱V圖)是計(jì)算幾何學(xué)中一個(gè)重要的數(shù)據(jù)結(jié)構(gòu)，具有自然鄰近、動(dòng)態(tài)穩(wěn)定等特性，在計(jì)算機(jī)圖形學(xué)、地理信息系統(tǒng)、生態(tài)學(xué)、分子化學(xué)、氣象學(xué)、機(jī)械、醫(yī)學(xué)、藝術(shù)等領(lǐng)域得到了廣泛應(yīng)用[1-6]。其中，V圖結(jié)構(gòu)的高效、準(zhǔn)確生成是其諸多應(yīng)用順利實(shí)現(xiàn)的關(guān)鍵。國(guó)內(nèi)外學(xué)者對(duì)V圖生成算法進(jìn)行了許多研究，其成果主要分為矢量算法和柵格算法兩類。

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

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

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

為此，本文提出了一種基于橫-縱掃描的V圖生成改進(jìn)算法，即根據(jù)傳統(tǒng)算法產(chǎn)生誤差的區(qū)域特征，在一個(gè)正常周期的水平(橫向)掃描后，增加一個(gè)周期豎直(縱向)掃描，實(shí)現(xiàn)柵格V圖的高效、準(zhǔn)確生成，并把誤差控制在一個(gè)格網(wǎng)以內(nèi)，最后進(jìn)行了試驗(yàn)對(duì)比分析。

1 傳統(tǒng)掃描算法原理及缺陷

1.1 傳統(tǒng)掃描算法原理

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

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

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

(1)

1.2 傳統(tǒng)算法缺陷分析

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

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

掃描算法核心是在掃描過(guò)程中通過(guò)每個(gè)格網(wǎng)的與部分種子點(diǎn)之間的距離計(jì)算和比較得到該格網(wǎng)的最近種子點(diǎn)。然而由于傳統(tǒng)算法掃描的不完備，上述錯(cuò)誤的出現(xiàn)主要因?yàn)樵趻呙柽^(guò)程中對(duì)某一格網(wǎng)(如格網(wǎng)M)所進(jìn)行的距離計(jì)算與比較并沒(méi)有包括其最近種子點(diǎn)，致使該格網(wǎng)的歸屬出現(xiàn)錯(cuò)誤。圖3(a)為一隨機(jī)種子點(diǎn)情況下傳統(tǒng)柵格掃描算法得到的V圖，圖3(c)為確定歸屬算法得到的正確的V圖，可以看出它們之間有較大的差異，如圖3(b)黑色區(qū)域所示。

也有學(xué)者在掃描算法結(jié)果的基礎(chǔ)上，進(jìn)行多周期的相同掃描過(guò)程以減少不正確歸屬格網(wǎng)的數(shù)量，但是為得到正確V圖，重復(fù)掃描周期的次數(shù)n是難以控制的。

2 改進(jìn)算法

2.1 歸屬出錯(cuò)單元范圍界定

首先分析種子點(diǎn)經(jīng)一個(gè)周期掃描后錯(cuò)誤歸屬單元的空間分布特征。

如圖4所示，格網(wǎng)A和格網(wǎng)B為種子點(diǎn)。在進(jìn)行正向掃描時(shí)，掃描順序?yàn)閺淖蟮接?、從上到下順序逐行進(jìn)行掃描。因?yàn)樗x模板為3×3模板，所以掃描順序在種子點(diǎn)A左上方格網(wǎng)1之前的格網(wǎng)，都沒(méi)有計(jì)算和比較過(guò)與種子點(diǎn)A之間的距離。與格網(wǎng)1為同一行且掃描順序在格網(wǎng)1之后的格網(wǎng)，都可以從其左側(cè)格網(wǎng)處得到種子點(diǎn)A。種子點(diǎn)A同一行的格網(wǎng)中，最早得到種子點(diǎn)A的是格網(wǎng)2，它是從其右上方格網(wǎng)1處得到的。這樣臨時(shí)歸屬于種子點(diǎn)A的格網(wǎng)就形成了一個(gè)135°的角度，由格網(wǎng)1向左下方延伸。在掃描到達(dá)種子點(diǎn)B附近時(shí)，經(jīng)過(guò)了與種子點(diǎn)A相同過(guò)程。于是在正向掃描結(jié)束時(shí)，就形成了如圖4所示的臨時(shí)種子點(diǎn)歸屬圖，其中淺藍(lán)色格網(wǎng)歸屬于種子點(diǎn)A，淺綠色格網(wǎng)歸屬于種子點(diǎn)B。

單次反向掃描過(guò)程與正向掃描過(guò)程類似。其結(jié)果如圖5所示。

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

2.2 改進(jìn)方法

在找到了出現(xiàn)單元?dú)w屬錯(cuò)誤的區(qū)域后，本文設(shè)計(jì)了一種水平掃描后接豎直掃描的解決方案。豎直掃描保持?jǐn)?shù)據(jù)結(jié)構(gòu)不變，掃描模板仍為3×3模板(如圖1所示)。豎直掃描方向?yàn)樨Q直方向，掃描順序?yàn)橄葟淖笊辖情_始由下至上的逐列向右掃描一次為正向掃描，模板中心格網(wǎng)P從Q1、Q4、Q6和Q2這4個(gè)鄰近格網(wǎng)中得到其最近種子點(diǎn)。再?gòu)挠蚁陆情_始從下至上的逐列向左掃描一次為反向掃描，模板中心格網(wǎng)P從Q8、Q5、Q3和Q2這4個(gè)鄰近格網(wǎng)中得到其最近種子點(diǎn)。正反兩次掃描稱為一個(gè)豎直掃描周期。

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

水平掃描后接豎直掃描的解決方案對(duì)一個(gè)格網(wǎng)進(jìn)行兩個(gè)周期共4次掃描，可以完全覆蓋該種子點(diǎn)周圍所有區(qū)域，如圖8所示。藍(lán)色格網(wǎng)為豎直周期正向掃描覆蓋區(qū)域，綠色格網(wǎng)為豎直周期反向掃描覆蓋區(qū)域，紫色區(qū)域?yàn)樗麄冎睾蠀^(qū)域。左側(cè)的淺綠色區(qū)域(Ⅰ區(qū))和右側(cè)的淺藍(lán)色區(qū)域(Ⅱ區(qū))為水平周期無(wú)法完全覆蓋的區(qū)域，但是可以被豎直周期覆蓋。這樣就保證了種子點(diǎn)周圍所有區(qū)域在經(jīng)過(guò)水平、豎直兩個(gè)周期掃描后都可以得到該種子點(diǎn)。

3 試驗(yàn)與分析

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

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

表1 不同算法生成V圖所用時(shí)間

由表1可以看出，在格網(wǎng)數(shù)和種子點(diǎn)數(shù)較少情況下，確定歸屬算法與掃描算法效率相差不大。但是在數(shù)據(jù)量較大的情況下，掃描算法具有明顯的速度優(yōu)勢(shì)，且隨著格網(wǎng)數(shù)和種子點(diǎn)數(shù)量的增加這種優(yōu)勢(shì)越來(lái)越明顯。而改進(jìn)后掃描算法與原算法效率大體相當(dāng)。

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

(2)

表2 算法的誤差分析

注：表中數(shù)字表示100次隨機(jī)試驗(yàn)中兩種算法得到的格網(wǎng)的最大誤差在各區(qū)間的數(shù)量。

圖2 出現(xiàn)錯(cuò)誤的原因Fig.2 Reason of sweeping errors

圖3 一周期水平掃描后出現(xiàn)的誤差Fig.3 Errors after the horizontal cycle sweeps

圖4 單次正向掃描結(jié)果Fig.4 Result of single positive scan

圖5 單次反向掃描結(jié)果Fig.5 Result of single reverse scan

圖6 正反掃描后一定能得到種子點(diǎn)的區(qū)域Fig.6 The area which can get the seed point after the positive and reverse scanning

圖7 豎直掃描周期單次正反掃描后結(jié)果Fig.7 The result of single positive and reverse scan of vertical scanning cycle

圖8 水平加豎直兩周期掃描后結(jié)果Fig.8 The results of horizontal plus vertical two-period scan

圖9 不同種子點(diǎn)數(shù)生成結(jié)果示意圖Fig.9 The results of different seed points

圖10 各算法效率情況Fig.10 The efficiency of different algorithms

由上表可以看出，原算法大概率會(huì)出現(xiàn)單元?dú)w屬錯(cuò)誤，且誤差隨數(shù)據(jù)量的增加而增加，嚴(yán)重影響了某些需要高精度的應(yīng)用，而改進(jìn)后的算法，以確定歸屬算法生成結(jié)果為基準(zhǔn)，生成的V圖把每個(gè)格網(wǎng)的誤差都控制在了一個(gè)格網(wǎng)以內(nèi)，所以本文提出的算法達(dá)到了與確定歸屬算法相當(dāng)?shù)木取?/p>

4 結(jié) 論

本文在深入分析了傳統(tǒng)掃描算法產(chǎn)生誤差缺陷的原因和區(qū)域特征后，在傳統(tǒng)柵格掃描算法基礎(chǔ)上，提出了一種基于橫-縱掃描的V圖生成改進(jìn)算法，并進(jìn)行了相關(guān)效率和精度試驗(yàn)，結(jié)果表明：

(1) 改進(jìn)后的算法保留了掃描算法效率上的優(yōu)勢(shì)，在大數(shù)據(jù)量情況下速度遠(yuǎn)高于確定歸屬算法，與原掃描算法的效率基本一致。

(2) 改進(jìn)后算法彌補(bǔ)了原算法不完備的掃描缺陷，在高效生成的同時(shí)把誤差限制在一個(gè)格網(wǎng)以內(nèi)，達(dá)到了與確定歸屬算法相當(dāng)?shù)木取?/p>