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

吳 凱 張曉莉 蔡永寧 齊 俊 王長(zhǎng)鵬 杲廣文

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

0 引言

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

本文從廣義DTO概念入手,利用影響因素的逐級(jí)限制,從單點(diǎn)生成元到多點(diǎn)生層元、網(wǎng)絡(luò)空間、街區(qū)距離等復(fù)雜要素遞進(jìn)式實(shí)現(xiàn)了若干廣義障礙距離變換的派生,并通過(guò)實(shí)驗(yàn)進(jìn)行了驗(yàn)證,最后總結(jié)了廣義DTO及其變形在資源的合理配置、選址及路徑選擇等應(yīng)用中具有的實(shí)際價(jià)值。

1 廣義DTO

距離變換是將包含實(shí)體特征和空間背景兩種像元的二值圖像轉(zhuǎn)變?yōu)榫嚯x圖像的變換。在距離圖像中,每一個(gè)像素值表示該像素到其最近的一個(gè)實(shí)體像素的距離,具體體現(xiàn)為每個(gè)實(shí)體的距離波不斷地往外空間進(jìn)行擴(kuò)張,直到與鄰近實(shí)體的距離波相遇。當(dāng)考慮障礙空間問(wèn)題時(shí),上述距離變換則應(yīng)擴(kuò)展為DTO,即在障礙空間中進(jìn)行距離變換。基于柵格方法的距離變換對(duì)點(diǎn)、直線、曲線和多邊形采用通用的數(shù)據(jù)結(jié)構(gòu),即將所有的空間對(duì)象等價(jià)為標(biāo)準(zhǔn)的柵格點(diǎn)集,所以距離變換的生成元可以是單點(diǎn)也可以點(diǎn)、線、面的組合,甚至是不同權(quán)值的多生成元；距離變換的空間可以是勻質(zhì)空間,即在所有柵格上距離的傳播速度相等；也可以使非勻質(zhì)空間,即在不同的區(qū)域距離的傳播速度不同,以上因素可以單獨(dú)或者綜合影響DTO的結(jié)果,這就是廣義DTO。

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

表1 廣義DTO的影響因素

現(xiàn)實(shí)生活中,旅行所耗費(fèi)的時(shí)間不僅僅與距離成正比,還與路況、運(yùn)輸工具性能有關(guān),從固定點(diǎn)出發(fā),旅行特定時(shí)間后所能到達(dá)的點(diǎn)則在各個(gè)方向上是不同距離的[8]?？紤]到阻力影響,計(jì)算的距離稱為耗費(fèi)距離。物質(zhì)在空間中移動(dòng)總要花費(fèi)一些代價(jià),如資金、時(shí)間等。阻力越大耗費(fèi)也越大。相應(yīng)的通過(guò)耗費(fèi)距離得到的距離表面稱為阻力表面或耗費(fèi)表面,其屬性值代表耗費(fèi)或阻力大小?？梢愿鶕?jù)阻力表面計(jì)算最小耗費(fèi)距離[9-11],以上這些都是廣義DTO在現(xiàn)實(shí)世界中的具體應(yīng)用。

2 廣義DTO的派生方法

最基本的距離變換是點(diǎn)狀生成元在勻質(zhì)無(wú)障礙空間中的距離變換,而無(wú)障礙空間只是障礙空間障礙物個(gè)數(shù)為零的一種特例?，F(xiàn)實(shí)的地理空間不僅僅有障礙物,生成元也可以是任意形態(tài)的,各個(gè)生成元的距離傳播速度可以不同,距離變換空間也可能是非勻質(zhì)空間,所以將一般的DTO擴(kuò)展到廣義DTO具有很重要的意義[12-14]。

本節(jié)以單點(diǎn)無(wú)障礙勻質(zhì)空間的距離變換為基礎(chǔ),通過(guò)變換條件的逐級(jí)限制,遞進(jìn)式派生出若干廣義DTO。廣義DTO的派生過(guò)程如圖1所示,在單生成元?jiǎng)蛸|(zhì)空間無(wú)障礙距離變換的基礎(chǔ)之上加入障礙就得到了單生成元?jiǎng)蛸|(zhì)空間的DTO圖；按照加入非均質(zhì)空間則形成單生成元非勻質(zhì)空間的DTO圖；若生成元的類型由單點(diǎn)生成元擴(kuò)展為點(diǎn)、線、面組合的多生成元?jiǎng)t可派生出多生成元非均質(zhì)勻質(zhì)空間中的DTO。

圖1 廣義DTO派生流程

3 實(shí)驗(yàn)分析

在上節(jié)中介紹了廣義DTO的派生原理,即利用條件的逐級(jí)限制,遞進(jìn)式實(shí)現(xiàn)。本節(jié)就利用此方法設(shè)計(jì)廣義DTO生成實(shí)驗(yàn)。本實(shí)驗(yàn)中的生成元包括點(diǎn)、線、面即任意形態(tài)生成元；變換空間包括障礙空間、無(wú)障礙空間、勻質(zhì)空間、非勻質(zhì)空間。

以生成元的性質(zhì)進(jìn)行分組實(shí)驗(yàn),分為兩組,單點(diǎn)生成元和點(diǎn)線面組合生成元。每組實(shí)驗(yàn)再根據(jù)變換空間的類型進(jìn)行具體的劃分,實(shí)驗(yàn)中圖幅范圍和比例尺全部相同。

3.1 單點(diǎn)生成元的廣義DTO

本小節(jié)以單點(diǎn)無(wú)障礙勻質(zhì)空間的距離變換為基礎(chǔ),通過(guò)添加障礙以及傳播空間的均質(zhì)變化,遞進(jìn)式派生出若干單點(diǎn)廣義DTO,實(shí)驗(yàn)過(guò)程如下:

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

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

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

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

單點(diǎn)生成元的廣義DTO是本文研究的基礎(chǔ),通過(guò)設(shè)計(jì)實(shí)驗(yàn),確定了障礙空間和均質(zhì)空間對(duì)其距離變換的影響,為后續(xù)實(shí)驗(yàn)的設(shè)計(jì)、分析奠定了基礎(chǔ)。

3.2 多生成元的廣義DTO

本小節(jié)以點(diǎn)、線、面全形態(tài)作為生成元,進(jìn)一步拓展了生成元對(duì)象,遞進(jìn)式派生出若干點(diǎn)、線、面等多生成元的廣義DTO,實(shí)驗(yàn)過(guò)程如下:

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

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

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

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

本小節(jié)將生成元的類型由單點(diǎn)生成元擴(kuò)展為點(diǎn)、線、面組合的多生成元,并按照同樣的規(guī)則派生出多生成元在不同限制條件下的DTO,進(jìn)一步模擬了現(xiàn)實(shí)空間的復(fù)雜多樣性。

3.3 網(wǎng)絡(luò)空間DTO

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

下面通過(guò)實(shí)驗(yàn)來(lái)描述網(wǎng)絡(luò)空間DTO的原理。圖4為某市的主干道路網(wǎng)。圖4(a)為正常狀態(tài)下的道路網(wǎng),取路網(wǎng)上的兩點(diǎn)分別設(shè)為起點(diǎn)(Start)和終點(diǎn)；以起點(diǎn)(Start)為生成元在道路網(wǎng)空間中進(jìn)行距離變換,結(jié)果如圖4(b)所示；隨著顏色的加深距離值變大，當(dāng)?shù)缆肪W(wǎng)中的某一段禁止通行時(shí),如圖4(d)所示；將此段路設(shè)為障礙,并以起點(diǎn)(Start)為生成元進(jìn)行DTO,結(jié)果如圖4(e)所示；隨著顏色的加深距離值變大,利用工具成本路徑(CostPath)回溯最短路徑,則障礙空間中起點(diǎn)到終點(diǎn)的最短路徑如圖4(f)所示。

(a)無(wú)障礙道路網(wǎng) (b)以起點(diǎn)為生成元的距離變換

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

3.4 街區(qū)距離DTO

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

(1)

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

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

4 結(jié)束語(yǔ)

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