一種改進的拉普拉斯邊緣算法和啟發式搜索的道路提取方法

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

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

1 引言

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

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

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

（2）拓撲特征。形成路網的主要道路是相互連通的，不會突然中斷，路段的兩端一般與另一道路段交叉，或者是延伸至圖像的邊緣；

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

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

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

2 拉普拉斯邊緣檢測

拉普拉斯算子是對二維函數進行運算的二階導數算子。它定義為：

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

圖1 拉普拉斯卷積核

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

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

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

圖2 本文改進的拉普拉斯核

3 啟發式搜索法

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

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

圖3

定義該段道路的代價函數為：

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

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

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

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

（2）如果沒有找到結點被標記為OPEN，算法失敗退出；否則繼續。

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

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

（5）沿搜索方向尋找道路點，并將具有最小值搜索點的鄰域內所有像元都確定為道路點，同事累積計算P(n)的值。

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

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

4 實驗分析

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

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

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

圖4（b） 拉普拉斯提取結果

圖5（b） 拉普拉斯提取結果

圖4（c） 啟發式搜索后結果

圖5（c） 啟發式搜索后結果

5 實驗結論

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

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

［2］呂健剛，韋春桃.基于Hough變換的高分辨率遙感影像城市直線道路提取［J］.遙感應用，2009，（3）.

［3］胡進剛，張曉東，沈欣等.一種面向對象的高分辨率影像道路提取方法［J］.遙感技術與應用，2006，（3）.

［4］余長慧，孟令奎，秦昆.基于標點隨機過程的遙感影像道路提取［J］.武漢大學學報，2006，（1）.

［5］王士同.基于傳播概念的啟發式圖搜索法PRA［J］.計算機學報，1991.