一種改進(jìn)的拉普拉斯邊緣算法和啟發(fā)式搜索的道路提取方法

胥 亞，馮伍法，盧茂芬，劉衷瑞

（1.信息工程大學(xué)測繪學(xué)院，河南 鄭州 450052；2.73603部隊，江蘇 南京 210049）

1 引言

道路提取是目前地理信息提取的熱點，與之相關(guān)的研究也多不勝數(shù)。隨著空間遙感技術(shù)的發(fā)展，我們獲取了大量的遙感影像。從這些遙感影像上快速、高效地提取地理信息一直是遙感數(shù)據(jù)處理及GIS數(shù)據(jù)獲取的目標(biāo)，而道路信息是這些目標(biāo)的重要組成部分。隨著傳感器技術(shù)的不斷進(jìn)步，我們獲取的圖像分辨率也越來越高。從以前的數(shù)十米級圖像到現(xiàn)在的分米甚至厘米級分辨率的圖像，結(jié)合高精度的GPS定位技術(shù)，實現(xiàn)道路的精確定位和識別已成為了可能。低分辨率遙感圖像道路提取取得了很好的進(jìn)展，已有許多相對成熟的算法可將影像上的道路邊緣以及中心線提取出來。

一般而言，道路都具有兩條比較明顯的邊緣，邊緣內(nèi)部輻射信息比較均勻。道路的這些信息以及道路的周圍信息構(gòu)成了道路的基本特征。道路特征是我們提取道路目標(biāo)的基礎(chǔ)。概括起來，道路特征主要包括以下幾個方面：

（1）形狀特征。在高分辨率影像上，道路一般是彎曲的長條，且其長度遠(yuǎn)遠(yuǎn)大于其寬度，寬度變化受到噪聲的影響，變化比較小，即路面寬度基本一致，曲率有一定的限制；

（2）拓?fù)涮卣鳌Ｐ纬陕肪W(wǎng)的主要道路是相互連通的，不會突然中斷，路段的兩端一般與另一道路段交叉，或者是延伸至圖像的邊緣；

（3）輻射特征。從視覺方面來看，道路有兩條比較明顯的邊緣，而且內(nèi)部灰度與其相鄰像元灰度反差比較大；此外，高分辨率圖像上道路中央的道路中心線呈白色，過往汽車過多也會對灰度信息造成影響；

（4）環(huán)境特征。環(huán)境特征指的是與道路相關(guān)的影像特征，如道路旁的建筑物和行樹等。

針對以上道路特征，許多學(xué)者提出了比較可靠實用的道路模型，結(jié)合一些經(jīng)典的算法，取得了較好的道路提取結(jié)果。根據(jù)道路灰度幾何特征建立了道路模型，該模型從所選的道路段中提取特征來定義多個分配函數(shù)，利用合成法則進(jìn)行合成，形成道路段，最后將合成法則獲取的道路段進(jìn)行合并，從而實現(xiàn)道路提?。?］。利用高分辨率遙感影像城市直線道路特性，在圖像分割獲得道路網(wǎng)輪廓的基礎(chǔ)上，采用Hough變換法，檢測道路所在直線，判斷該直線是否為道路［2］。確定為道路線以后，再將所得道路段進(jìn)行修剪、連接形成道路網(wǎng)，實現(xiàn)道路提取。本文首先利用改進(jìn)后的拉普拉斯核提取了包含完整道路信息的中間結(jié)果，在此結(jié)果上采用啟發(fā)式搜索法，將道路目標(biāo)提取出來，去除了非道路信息。

2 拉普拉斯邊緣檢測

拉普拉斯算子是對二維函數(shù)進(jìn)行運(yùn)算的二階導(dǎo)數(shù)算子。它定義為：

通常在數(shù)字化方式下可用圖1中所示的兩個卷積核之一來實現(xiàn)。

圖1 拉普拉斯卷積核

如果一個沒有噪聲圖像具有比較陡峭的邊緣，就可用拉普拉斯算子將它提取出來。由于拉普拉斯算子是一個二階導(dǎo)數(shù)算子，它對噪聲比較敏感，所以一般先進(jìn)行平滑濾波，再進(jìn)行二階微分。而常用的平滑濾波函數(shù)為高斯低通濾波函數(shù)。由卷積的結(jié)合律可將拉普拉斯算子和高斯脈沖響應(yīng)結(jié)合，形成一個單一的高斯拉普拉斯核。

這種由高斯平滑函數(shù)和拉普拉斯微分合并得到的算子稱為高斯-拉普拉斯 （LOG,Laplacian Of Gaussian）算子，這種邊緣檢測方法也稱為Marr邊緣檢測方法。

本文要利用LOG算子邊緣探測的結(jié)果進(jìn)行啟發(fā)式搜索，道路邊緣探測結(jié)果需要保留一定寬度，最理想的情況是提取后的結(jié)果正好保留了道路的寬度信息，這樣我們提取的道路結(jié)果就與從原圖像上提取道路目標(biāo)的結(jié)果一致。經(jīng)過試驗，將拉普拉斯卷積核改進(jìn)為如圖2所示7×7的窗口形式，探測結(jié)果能夠完整保留道路的基本信息，可為下一步搜索道路提供較好的中間結(jié)果。

圖2 本文改進(jìn)的拉普拉斯核

3 啟發(fā)式搜索法

啟發(fā)式搜索法是利用圖像中目標(biāo)所包含的啟發(fā)信息來引導(dǎo)搜索，這些啟發(fā)信息參數(shù)可根據(jù)具體的道路模型來確定。有了這些信息就可以達(dá)到減少搜索范圍，降低問題復(fù)雜性的目的。其原理為：給定了初始的種子點以后，根據(jù)啟發(fā)信息建立相應(yīng)的代價函數(shù)，通過求解代價函數(shù)的最小值，搜索對應(yīng)最小代價的通道來找到道路邊界。一般地，對于道路搜索而言，如果不利用它的一些基本特性知識，算法對初始點的擴(kuò)展就帶有一定的盲目性，也就是說尋找最小代價通路所需的計算量很大。因而，根據(jù)道路的基本特征確定相關(guān)的啟發(fā)性信息來引導(dǎo)搜索，可大大減少計算量，提高搜索效率。啟發(fā)性知識越多，代價函數(shù)越完善，擴(kuò)展的節(jié)點數(shù)就越小，計算量就越小，從而搜索效率就越高。

搜索道路的邊緣，建立代價函數(shù)主要利用道路的形狀特征和輻射特征。即道路邊緣的灰度值相差較大，內(nèi)部灰度值比較一致，道路邊緣比較光滑，曲率有一定限制。首先考慮曲率因素，在建立代價函數(shù)時可沿著道路邊緣方向以及夾角不大于于的方向進(jìn)行搜索。建立約束性條件如下式：

圖3

定義該段道路的代價函數(shù)為：

從該式可以看出，在輻射灰度值相同的情況下，處于水平或豎直方向上的像元具有較小的代價值。

令E（n）表示從起始結(jié)點s出發(fā)經(jīng)過當(dāng)前結(jié)點n到達(dá)目標(biāo)結(jié)點t的最小代價通路的代價值，將該代價分解為兩個代價之和，即從起始結(jié)點s到當(dāng)前結(jié)點n的最小代價通路的估計代價P（n）以及從當(dāng)前結(jié)點n到目標(biāo)結(jié)點t的通路的估計代價Q(n)，即：

這里P(n)為目前從結(jié)點s到結(jié)點n的最小代價通路，它的值通過（3-3）式定義的代價函數(shù)進(jìn)行計算，則搜索算法由以下步驟組成：

（1）將初始結(jié)點s標(biāo)記為OPEN，令P(s)=0。

（2）如果沒有找到結(jié)點被標(biāo)記為OPEN，算法失敗退出；否則繼續(xù)。

（3）以s點為中心，向其周邊8個像元方向展開搜索。

（4）以搜索方向上的8個像元為中心，取3×3的窗口鄰域，分別計算這8個像元的代價值P(n)，取代價值最小的像元方向為搜索方向。

（5）沿搜索方向?qū)ふ业缆伏c，并將具有最小值搜索點的鄰域內(nèi)所有像元都確定為道路點，同事累積計算P(n)的值。

（6）當(dāng)P(n)的累積值超過一定的閾值時，判斷到達(dá)道路盡頭，算法終止。

上述算法的主要優(yōu)點是借助道路模型的啟發(fā)性知識（包括形狀、角度以及灰度信息）加快了搜索速度。通過人工給定某個道路的種子點，通過搜索最小代價通路實現(xiàn)快速地跟蹤我們所要提取的道路段。

4 實驗分析

依據(jù)本文的算法，選擇了ADS40相機(jī)拍攝的某地區(qū)全色影像，由于原始影像較大，因而從原始影像上裁剪了兩部分用于實驗。這兩部分圖像分辨率分別為597×409，407×353。 實驗結(jié)果如下圖所示：

圖4（a） 原始影像（1）

圖5（a） 原始影像（2）

圖4（b） 拉普拉斯提取結(jié)果

圖5（b） 拉普拉斯提取結(jié)果

圖4（c） 啟發(fā)式搜索后結(jié)果

圖5（c） 啟發(fā)式搜索后結(jié)果

5 實驗結(jié)論

該方法能夠較好地從圖像中提取道路目標(biāo)。在一些比較復(fù)雜的情況下，例如居民區(qū)以及耕地的邊緣與道路邊緣有所混淆（圖4（a））的情況下，提取結(jié)果在局部范圍內(nèi)效果一般。但是一些不連續(xù)的點狀噪聲能夠被算法剔除，而連續(xù)的線狀道路則沒有受到影響，提取的總體情況良好。居民地與道路目標(biāo)重合地區(qū)是目標(biāo)提取的難點所在，也是今后的重點研究方向。而在干擾信息較少的區(qū)域，如山區(qū)地帶（如圖5（a）所示），拉普拉斯算法處理后的圖像保留了較好的道路結(jié)果的同時也包含了大量的斑狀噪點信息，經(jīng)過啟發(fā)式搜索，這些噪點信息大部分都被剔除，獲得了比較好的提取效果。

［1］王莉莉，郝愛民，何兵等.基于D-S證據(jù)理論的城市航拍道路提取方法［J］.軟件學(xué)報，2005，（9）.

［2］呂健剛，韋春桃.基于Hough變換的高分辨率遙感影像城市直線道路提?。跩］.遙感應(yīng)用，2009，（3）.

［3］胡進(jìn)剛，張曉東，沈欣等.一種面向?qū)ο蟮母叻直媛视跋竦缆诽崛》椒ǎ跩］.遙感技術(shù)與應(yīng)用，2006，（3）.

［4］余長慧，孟令奎，秦昆.基于標(biāo)點隨機(jī)過程的遙感影像道路提?。跩］.武漢大學(xué)學(xué)報，2006，（1）.

［5］王士同.基于傳播概念的啟發(fā)式圖搜索法PRA［J］.計算機(jī)學(xué)報，1991.