廣義障礙距離變換的多因素變形研究

吳 凱 張曉莉 蔡永寧 齊 俊 王長鵬 杲廣文

(濟南市勘察測繪研究院, 山東 濟南 250013)

0 引言

在現實世界中,兩個目標物之間可以直接通行的情況較少,一般都需要繞過若干障礙物才可到達。障礙距離變換(distance transformation with obstacles,DTO)可以有效地解決此類地理空間問題,即在障礙空間中進行距離變換[1]。所謂障礙空間,指空間中具有各種障礙物(obstacles),此處的障礙物并非單指點或線或多邊形,而是指全形態圖形,它是點、線、面以及它們的組合,障礙本身不計算距離,并且不傳遞距離。空間中有生成元還有若干障礙,生成元傳播的距離波需要繞過障礙進行傳播。胡鵬等[2]利用地圖代數的原理,解決了擁堵路段或施工路段的最短路徑規劃問題；劉建平[3]針對無人駕駛飛機的防撞避障和導航設計問題探討了障礙空間的問題；秦世引等[4]基于障礙物編碼的遺傳算法,研究障礙空間中機器人路徑規劃問題；Coeurjolly等[5]針對占該空間問題,提出了離散域障礙測地線的路徑算法；Willms等[6]利用網格距離傳播技術,解決了障礙空間中機器人導航避障、實時路徑規劃的問題；Torpelund-Bruin[7]利用障礙空間V圖進行了災難應急決策研究。由上述研究可見,距離分析是障礙空間問題解算的主要途徑。

本文從廣義DTO概念入手,利用影響因素的逐級限制,從單點生成元到多點生層元、網絡空間、街區距離等復雜要素遞進式實現了若干廣義障礙距離變換的派生,并通過實驗進行了驗證,最后總結了廣義DTO及其變形在資源的合理配置、選址及路徑選擇等應用中具有的實際價值。

1 廣義DTO

距離變換是將包含實體特征和空間背景兩種像元的二值圖像轉變為距離圖像的變換。在距離圖像中,每一個像素值表示該像素到其最近的一個實體像素的距離,具體體現為每個實體的距離波不斷地往外空間進行擴張,直到與鄰近實體的距離波相遇。當考慮障礙空間問題時,上述距離變換則應擴展為DTO,即在障礙空間中進行距離變換。基于柵格方法的距離變換對點、直線、曲線和多邊形采用通用的數據結構,即將所有的空間對象等價為標準的柵格點集,所以距離變換的生成元可以是單點也可以點、線、面的組合,甚至是不同權值的多生成元；距離變換的空間可以是勻質空間,即在所有柵格上距離的傳播速度相等；也可以使非勻質空間,即在不同的區域距離的傳播速度不同,以上因素可以單獨或者綜合影響DTO的結果,這就是廣義DTO。

在實際應用中影響距離變換的因素有很多。如表1所示,從生成元類型、變換空間的性質兩方面進行分類,給出了廣義DTO影響因素的若干變形。

表1 廣義DTO的影響因素

現實生活中,旅行所耗費的時間不僅僅與距離成正比,還與路況、運輸工具性能有關,從固定點出發,旅行特定時間后所能到達的點則在各個方向上是不同距離的[8]。考慮到阻力影響,計算的距離稱為耗費距離。物質在空間中移動總要花費一些代價,如資金、時間等。阻力越大耗費也越大。相應的通過耗費距離得到的距離表面稱為阻力表面或耗費表面,其屬性值代表耗費或阻力大小。可以根據阻力表面計算最小耗費距離[9-11],以上這些都是廣義DTO在現實世界中的具體應用。

2 廣義DTO的派生方法

最基本的距離變換是點狀生成元在勻質無障礙空間中的距離變換,而無障礙空間只是障礙空間障礙物個數為零的一種特例。現實的地理空間不僅僅有障礙物,生成元也可以是任意形態的,各個生成元的距離傳播速度可以不同,距離變換空間也可能是非勻質空間,所以將一般的DTO擴展到廣義DTO具有很重要的意義[12-14]。

本節以單點無障礙勻質空間的距離變換為基礎,通過變換條件的逐級限制,遞進式派生出若干廣義DTO。廣義DTO的派生過程如圖1所示,在單生成元勻質空間無障礙距離變換的基礎之上加入障礙就得到了單生成元勻質空間的DTO圖；按照加入非均質空間則形成單生成元非勻質空間的DTO圖；若生成元的類型由單點生成元擴展為點、線、面組合的多生成元則可派生出多生成元非均質勻質空間中的DTO。

圖1 廣義DTO派生流程

3 實驗分析

在上節中介紹了廣義DTO的派生原理,即利用條件的逐級限制,遞進式實現。本節就利用此方法設計廣義DTO生成實驗。本實驗中的生成元包括點、線、面即任意形態生成元；變換空間包括障礙空間、無障礙空間、勻質空間、非勻質空間。

以生成元的性質進行分組實驗,分為兩組,單點生成元和點線面組合生成元。每組實驗再根據變換空間的類型進行具體的劃分,實驗中圖幅范圍和比例尺全部相同。

3.1 單點生成元的廣義DTO

本小節以單點無障礙勻質空間的距離變換為基礎,通過添加障礙以及傳播空間的均質變化,遞進式派生出若干單點廣義DTO,實驗過程如下:

單點作為生成元的距離變換,即無障礙、勻質空間的距離變換,它的變換結果是以生成元為圓心的規則圓形,如圖2所示,在圖2(a)中A為點生成元。在圖2(b)中,A為點生成元,B為線狀障礙,C為面狀障礙,距離波繞過障礙進行傳播,對比圖2(a)可以看出同樣的圖幅范圍,由于障礙物的存在,距離值發生了改變,距離最大值由圖2(a)中的782 m變成了2(b)中的855 m。

單點作為生成元在非勻質空間中的距離變換,在圖2(c)中,A為點生成元,距離變換空間由虛線劃分為1、2、3、4、5五個區域,各區域的阻力值分別為1、2、3、4、5,即距離波在區域2、3、4、5中的傳播速度是區域1中傳播速度的1/2、1/3、1/4、1/5倍,區域1中距離傳播的速度和圖2(a)、圖2(b)兩個圖中的傳播速度相等。在圖2(c)中也可以看出,等距線在區域1中最為稀疏,在區域5中最為密集,說明距離波在區域1中傳播最快,在區域5中傳播最慢。對比圖2(a)可以看出勻質空間和非勻質空間由于阻力的影響使得距離波的傳播出現各向同性和各向異性的特征。

單點作為生成元在非勻質障礙空間中的距離變換,在圖2(d)中,A為點生成元,B為線狀障礙,C為面狀障礙。變換空間和圖2(c)中一樣由虛線劃分為1、2、3、4、5五個區域。對比圖2(c)可以看出,受障礙的影響,距離值發生了改變,距離最大值由圖2(c)中的2 884 m變成了圖2(d)中的2 927 m。

(a)勻質空間 (b)勻質障礙空間

單點生成元的廣義DTO是本文研究的基礎,通過設計實驗,確定了障礙空間和均質空間對其距離變換的影響,為后續實驗的設計、分析奠定了基礎。

3.2 多生成元的廣義DTO

本小節以點、線、面全形態作為生成元,進一步拓展了生成元對象,遞進式派生出若干點、線、面等多生成元的廣義DTO,實驗過程如下:

(1)點、線、面全形態生成元距離變換。廣義DTO中生成元和障礙物都應該是全形態圖形,即點、線、面以及它們的組合,如圖3所示。在圖3(a)中,A、B、C分別為點狀、面狀、現狀生成元。點、線、面全形態生成元DTO。在圖3(b)中,A、B、C分別為點狀、面狀、線狀生成元,a為面狀障礙,b為線狀障礙。距離波的傳播繞開障礙物,障礙物本身不具有距離值并且不傳播距離。對比圖3(a)中的距離值,由于障礙物的影響,距離值有所改變,圖3(a)中的距離最大值為644 m,圖3(b)中的距離最大值為789 m。

(2)點、線、面全形態生成元非勻質空間距離變換。在圖3(c)中,A、B、C分別為點狀、面狀、線狀生成元。同圖3(c)一樣,變換空間由虛線劃分為1、2、3、4、5五個區域,各區域的阻力值分別為1、2、3、4、5,等距線在區域1中最為稀疏,即距離傳播速度最快；等距線在區域5中最為密集,即距離傳播速度最慢。由于各區域的阻力大小不同,距離傳播特定時間后在各個方向上的距離值不同,形成各向異性的距離表面。

(3)點、線、面全形態生成元非勻質空間DTO。在圖3(d)中,A、B、C分別為點狀、面狀、線狀生成元,a為面狀障礙,b為線狀障礙,變換空間和同圖3(c)一樣由曲線劃分為1、2、3、4、5五個區域,對比圖3(c)中的距離值可看出,由于障礙物的影響,距離波需要繞開障礙物進行傳播,障礙影響區域的距離值發生變化。

(a)勻質空間 (b)勻質障礙空間

本小節將生成元的類型由單點生成元擴展為點、線、面組合的多生成元,并按照同樣的規則派生出多生成元在不同限制條件下的DTO,進一步模擬了現實空間的復雜多樣性。

3.3 網絡空間DTO

網絡空間是指距離的傳播只能在網絡上進行。例如，車輛在城市道路網上行駛,若某一道路因施工等原因而禁止通行,則車輛在路網中的行駛時需繞開此段路。同樣的原理,距離在網絡中傳播時,若在某處遇到障礙,則需尋找其他的線路進行傳播[15]。網絡空間中進行距離變換時,首先要將網絡之外的空間設置為障礙,這樣,距離的傳播只能在網絡中進行。網絡空間中的DTO則是在網絡上存在障礙物時,距離的傳播需要繞過網絡上的障礙物,尋找新的路徑進行傳播。

下面通過實驗來描述網絡空間DTO的原理。圖4為某市的主干道路網。圖4(a)為正常狀態下的道路網,取路網上的兩點分別設為起點(Start)和終點；以起點(Start)為生成元在道路網空間中進行距離變換,結果如圖4(b)所示；隨著顏色的加深距離值變大，當道路網中的某一段禁止通行時,如圖4(d)所示；將此段路設為障礙,并以起點(Start)為生成元進行DTO,結果如圖4(e)所示；隨著顏色的加深距離值變大,利用工具成本路徑(CostPath)回溯最短路徑,則障礙空間中起點到終點的最短路徑如圖4(f)所示。

(a)無障礙道路網 (b)以起點為生成元的距離變換

網絡空間中的DTO在現實生活中具有廣泛的應用,像道路網避障路徑、地下管網的布局等網絡空間問題都可以得到很好的解決。另外,基于網絡空間中的DTO而得到網絡空間中的障礙V圖,可以方便地劃分出障礙空間中公共設施(例如,醫院、醫療救助設施、公交站等)的服務范圍,從而方便快捷地服務于人們的日常生活。

3.4 街區距離DTO

同網絡空間類似,街區距離(即曼哈頓距離)是指平面上兩點x方向距離加上y方向距離,如式(1)所示,這類距離非常適合于城市的矩形街區結構,因而稱作街區距離[15]。街區距離在導航和城市路網規劃中也有著非常廣泛的應用。

(1)

本小節將DTO與街區距離進行融合,探討了街區距離的DTO變換,具體的實驗如下:根據街區距離的定義可得街區距離變換的原理如圖5所示,在圖5(a)中,生成元P其上下左右4鄰域的距離值為1,對角線所對的四個像元的值由4鄰域向外傳播,所以值為2,以此類推。如圖5(b)所示,和歐氏距離變換產生的距離波為同心圓不同,街區距離變換的距離波為同心正方形;當空間中存在障礙物,距離變換以街區距離尺度進行,則為街區距離DTO。如圖5(c)所示,以中間點為生成元,四個黑色矩形為障礙,得到的街區距離DTO。從圖中可以看出，距離波以同心正方形的形態向外傳播。當遇到障礙時,則繞過障礙進行傳播。

(a)原理圖 (b)街區距離變換圖

4 結束語

本文首先探討了廣義障礙距離變換概念,給出了廣義DTO的派生方法及具體流程,并以單點生成元、多生成元、網絡空間、街區距離等廣義DTO影響因素及變形為分析對象進行了實驗驗證,獲得了廣義DTO影響因素及變形的適用性。實驗結果表明:單點生成元的廣義DTO是基礎,確定了障礙空間和均質空間對變形的影響；多生成元的廣義DOT實驗則在將生成元進行拓展模擬了現時空間的多樣性；網絡空間DTO實驗和街區距離DTO實驗則表明了廣義DTO變形的適用性在資源的合理配置、選址及路徑選擇等應用中具有一定實際價值。