基于雙閾值SSDA模板匹配的遙感圖像道路邊緣檢測研究

闕昊懿， 黃輝先， 徐建閩

(1.湘潭大學(xué)信息工程學(xué)院，湘潭 411105； 2.華南理工大學(xué)土木與交通學(xué)院，廣州 510200)

0 引言

隨著遙感圖像處理技術(shù)的發(fā)展和圖像分辨率的不斷提高[1]，基于高分辨率遙感圖像[2]的道路專題信息提取技術(shù)已廣泛應(yīng)用于城市交通研究領(lǐng)域。而由縱橫交錯的城市道路網(wǎng)構(gòu)成的龐大交通網(wǎng)絡(luò)，也自然而然成為了遙感圖像在城市交通領(lǐng)域的研究熱點之一。目前，從遙感圖像上提取道路邊緣信息的算法主要有邊緣檢測[3-4]、Hough直線提取[5-7]以及模板匹配[6-11]等等。其中，邊緣檢測就是通過對圖像灰度躍變的分析尋找圖像區(qū)域邊緣的技術(shù)。對于數(shù)字圖像，通常使用卷積或是類似卷積的方法來實現(xiàn)對灰度的分析。常用的邊緣檢測算法有梯度法[2]、Roberts梯度法[3]和Sobel算法等[4]。 Hough變換常常被用來對圖像中的直線和圓進(jìn)行識別[7]，但是Hough變換對于間斷點以及不規(guī)則圖形的檢測效果并不理想[8]。

模板匹配技術(shù)一般是基于已知的模板，利用影像的灰度、形態(tài)等特征算法對待識別的圖像進(jìn)行匹配計算，判斷圖像中是否含有該模板的信息和坐標(biāo)。但模板匹配算法計算量過大，匹配速度較低[11]。為此，本文提出了一種基于減小增長誤差的序列模板匹配檢測算法，旨在提高算法檢測精度的同時，減小模板匹配的計算量，提高檢測速度，抑制增長誤差。

1 檢測算法

1.1 模板匹配算法

在圖像識別過程中，模板匹配是將待匹配的圖像與被搜索圖像的全部或部分在空間上對準(zhǔn)，根據(jù)已知模式的圖像在一幅陌生圖像中尋找對應(yīng)該模式子圖像的過程。將模板T(M×N)疊放在被搜索圖像S(W×H)上并平移(M和N分別表示模板縱向和橫向的像素個數(shù))。令模板覆蓋下的圖像區(qū)域為子圖像Sij(i和j是子圖像左上角像素點在圖像上的坐標(biāo))。模板匹配就是通過比較模板T與子圖像Sij的相似性來完成模板匹配的過程。定義模板T與子圖像Sij的差的平方為D(i,j)，則

(1)

將式(1)展開，得到

(2)

式中： 等號右面第1項為子圖像Sij的能量； 第3項為模板T的能量； 第2項表示模板T和子圖像Sij的相關(guān)程度，用相關(guān)系數(shù)Rij表示。將R(i,j)歸一化得

(3)

當(dāng)模板T和子圖像Sij完全一致時，相關(guān)系數(shù)R(i,j)=1。R(i,j)越大，表明T與Sij的相似度越高。

使用典型的模板匹配算法對道路邊緣進(jìn)行檢測時，由于每次都必須遍歷原圖進(jìn)行搜索并對比，因此存在計算量大、速度較慢等缺點。

1.2 SSDA算法

模板匹配算法效率低下的原因是無法將更多的計算時間用在更接近目標(biāo)的區(qū)域范圍內(nèi)，且算法中相關(guān)閾值的選取較為困難。模板過大容易導(dǎo)致錯測，過小則漏檢，嚴(yán)重影響檢測的準(zhǔn)確性； 但如果將模板數(shù)目固定，則在更大的環(huán)境中，模板匹配算法不具備智能性[12]。

為了加快匹配速度，Barnea[13]于1972年提出了序貫相似性檢測算法(sequential similarity detection algorithm,SSDA)。該算法通過人為設(shè)定一個固定閾值，使不匹配位置上的計算及早終止，以減小計算量，達(dá)到提高運算速度的目的。定義模板T與子圖像Sij差的絕對值為D(n)，則

(4)

式中Tp和Sp分別為模板T與子圖像Sij的第p個像素值。定義閾值△k，在模板T與搜索子圖Sij的相似度測試D(n)的搜索過程中，如果到達(dá)其中某一像素點時，對應(yīng)的D(n)超過了預(yù)設(shè)閾值△k，則表示此處配準(zhǔn)不成功，記錄當(dāng)前的匹配次數(shù)n，結(jié)束該搜索子圖并開始下一次配準(zhǔn)。當(dāng)滿足結(jié)束判斷條件的值較小時，說明系統(tǒng)能夠迅速判別出此次配準(zhǔn)失敗，因而可以節(jié)約大量的計算時間。這種算法的性能在很大程度上取決于閾值△k的設(shè)定。當(dāng)△k較小時，D(n)可能很快超過此閾值而終止當(dāng)前匹配，雖然降低了計算量，但是會增加過早結(jié)束搜索的可能性，導(dǎo)致配準(zhǔn)圖像未能檢測到，降低了配準(zhǔn)精確性； 而閾值△k較大時，雖然精確性得到了保證，但處理速度大大降低。

1.3 雙閾值SSDA算法

為提高模板匹配算法對目標(biāo)區(qū)域的檢測效率，以及解決閾值選取困難的問題，本文提出了雙閾值判斷算法。該算法將明顯不在匹配范圍的數(shù)據(jù)丟棄，避免重復(fù)檢測，提高了算法效率； 將匹配度較高的數(shù)據(jù)直接保存為匹配目標(biāo)； 在匹配度高與低的中間范圍，進(jìn)行減小增長誤差的全樣本序貫時序性模板匹配判斷，進(jìn)一步提高了算法的檢測精度。

首先，定義一個子圖與模板的絕對誤差，即

(5)

式中：k為模板序號，0△k1，拋棄當(dāng)前εk(i,j)； ②當(dāng)εk(i,j)≤△k2時，作為匹配目標(biāo)進(jìn)行保存，并記錄為新樣本； ③當(dāng)△k2<εk(i,j)≤△k1，記錄當(dāng)前εk(i,j)的坐標(biāo)值(i,j)及εk(i,j)值，并建立一個數(shù)組a(i,j,q)進(jìn)行保存。

針對上述3種不同的結(jié)果，可以對應(yīng)采用3種方式進(jìn)行處理。配準(zhǔn)值高于△k2的，則記錄為匹配目標(biāo)保存； 配準(zhǔn)值較低，則不處理； 配準(zhǔn)值處于△k1和△k2之間，則記錄當(dāng)前模板，并進(jìn)行二次判斷。這種處理方式大大提高了處理效率，將匹配范圍減小到更接近于目標(biāo)的檢測范圍內(nèi)，在提高了檢測精度的同時，減少了不必要的非目標(biāo)范圍的檢測計算，從而提高了算法的檢測效率。

對于結(jié)果③出現(xiàn)的在2個閾值間的子圖，其圖像介于相似度高和相似度低之間。為了提高該區(qū)域的檢測精度，本文將采用基于減小增長誤差的雙閾值序列模板匹配算法對這一范圍內(nèi)的子圖進(jìn)行檢測。

在SSDA算法帶來運算速度提升的過程中，由于樣本數(shù)目的不斷增加，相應(yīng)檢測的誤差也會不斷增長，因此，本文根據(jù)統(tǒng)計增長誤差的方法，提出了一個抑制增長誤差的算子，保證了檢測的準(zhǔn)確性。

首先，定義總誤差為每個樣本誤差之和，即

(6)

定義算子

(7)

由式(7)可以看出，f(p)是一個單調(diào)遞增函數(shù)。當(dāng)p=1時，f(p)=0； 當(dāng)樣本數(shù)不斷增加時，f(p)將隨著p的增加而不斷增長。

將該算子加入誤差計算，并記錄累加次數(shù)q，得到最終的誤差計算公式，即

(8)

式中εresult是總誤差與匹配算子f(p)的差值。由于總誤差是由每個樣本誤差之和累加的，當(dāng)樣本數(shù)增加時，總誤差也在不斷增加。匹配算子f(p)的提出，可以減小因樣本數(shù)增加而帶來的誤差總量的增加，從而提高了算法的檢測率。

將每次誤差值不斷累加，當(dāng)εresult≥△k3時，計算中止，并記錄當(dāng)前累加次數(shù)q1～qp。記錄q1～qp分布概率函數(shù)，并結(jié)合圖形取得一個接近結(jié)果的分布值t，當(dāng)qi>t時，記錄為匹配目標(biāo)，當(dāng)qi≤t時，將結(jié)果拋棄。算法流程如圖1所示。

圖1 算法流程

2 方法實驗

該算法適用于在較多相似目標(biāo)中尋找匹配度較高的目標(biāo)。因此，本實驗選擇的圖像結(jié)構(gòu)較為簡單。2幅圖像均通過Google Earth得到。

首先，對圖像進(jìn)行灰度化，得到灰度圖； 然后采用中值濾波消除圖像中的干擾點，用均質(zhì)灰度檢測方法獲取邊緣的大致分布。均質(zhì)灰度檢測的方法是在圖像上取一個5像素×5像素的區(qū)域，計算其均值、標(biāo)準(zhǔn)差及均值差分絕對值，若均值差分絕對值較小，且標(biāo)準(zhǔn)差也較小，則視該像素區(qū)為同一類別對象，并將像素區(qū)矩陣元素的灰度取均值。若均值差分絕對值較大，則視為邊緣區(qū)域。通過在圖像上進(jìn)行循環(huán)計算，就能檢測出圖像相同介質(zhì)分布，并去除一些較小的噪點，得出大致的邊緣分布情況。

獲取均質(zhì)灰度分布圖像后，利用閾值分割方法得到二值化圖像。對圖像進(jìn)行分析，利用輪廓檢測方法將圖像中路面車輛信息以及部分干擾去除，即可得到預(yù)處理后的圖像。

采集圖像規(guī)則道路邊緣子圖像為正模板，形變較大的且不規(guī)則部分邊緣子圖像為負(fù)模板，正、負(fù)樣本初始數(shù)目各為15。使用本文匹配算法仿真得出道路邊緣，并與其他算法得出的道路邊緣結(jié)果進(jìn)行對比(圖2，3)。

(a) 原圖像(b) 預(yù)處理后結(jié)果(c) Sobel算子檢測結(jié)果

(d) Hough概率檢測結(jié)果(e) 梯度算子檢測結(jié)果(f) 本文方法檢測結(jié)果

(a) 原圖像(b) 預(yù)處理后結(jié)果(c) 梯度算子檢測結(jié)果

(d) Sobel算子檢測結(jié)果(e) Hough概率檢測結(jié)果(f) 本文方法檢測結(jié)果

由圖2可知，Sobel算子的邊緣檢測方法雖然能得出道路邊緣，但是邊緣不連續(xù)，且沒有消除雜點信息(圖2(c))； Hough概率檢測方法(紅線部分為監(jiān)測結(jié)果)雖然能準(zhǔn)確地提取出大部分邊緣信息，但對干擾信息較多或邊緣形變較大部分的提取，效果依然不理想(圖2(d))； 梯度算子檢測結(jié)果遺漏了過多的邊緣信息(圖2(e))。本文采用雙閾值模板匹配方法提取出了較為完整的邊緣信息，且對于干擾及細(xì)節(jié)部分的濾除效果令人滿意(圖2(f))。

對于帶有大量干擾以及細(xì)節(jié)信息的圖像(圖3)，采用梯度算子和Sobel算子的檢測結(jié)果仍然包含大量干擾信息，得不出完整的道路邊緣(圖3(c)(d))。Hough概率檢測(紅線部分)能提取出大部分道路邊緣信息，但對陰影部分的道路邊緣不能識別，且提取結(jié)果不完整(圖3(e))，對干擾點較多部分，Hough概率也無法檢測出準(zhǔn)確的結(jié)果。本文方法不但能提取出正確的邊緣信息，同時也消除了原圖中道路邊緣上因亮度不均導(dǎo)致的干擾信息，提取的邊緣信息完整準(zhǔn)確(圖3(f))。

3 結(jié)論

本文從道路邊緣的影像特征出發(fā)，提出了使用雙閾值的序貫相似性檢測算法(SSDA)的模板匹配方法提取道路邊緣信息，同時，根據(jù)SSDA存在的總誤差隨著樣本數(shù)增加而不斷增大的問題，定義了一個減小增長誤差的算子。從理論和實驗的結(jié)果可以看出，該方法有以下3個優(yōu)點： ①設(shè)計過程中考慮了閾值選取的復(fù)雜性，提出了采用雙閾值多結(jié)果的處理方法，增加了模板匹配閾值選擇的彈性空間； ②在對道路邊緣信息提取過程中，能修復(fù)預(yù)處理時難以消除的干擾信息，完整顯示道路的邊緣； ③提取方法有一定的機(jī)器學(xué)習(xí)能力，帶有一定的智能性。本算法適用于一般直線道路的邊緣信息提取，對噪聲不敏感，具備很好的檢測效果。

參考文獻(xiàn)(References)：

[1] 孫家柄.遙感原理與應(yīng)用[M].武漢:武漢大學(xué)出版社,2003:79-111.

Sun J B.Principles and Applications of Remote Sensing[M].Wuhan:Wuhan University Press,2003:79-111.

[2] 李石華,王金亮,畢艷,等.遙感圖像分類方法研究綜述[J].國土資源遙感,2005,17(2):1-6.

Li S H,Wang J L,Bi Y,et al.A Review of methods for classification of remote sensing images[J].Remote Sensing for Land and Resources,2005,17(2):1-6.

[3] 朱長青,王耀革,馬秋禾,等.基于形態(tài)分割的高分辨率遙感影像道路提取[J].測繪學(xué)報,2004,33(4):347-351.

Zhu C Q,Wang Y G,Ma Q H,et al.Road extraction from high-resolution remotely sensed image based on morphological segmentation[J].Acta Geodaetica et Cartographica Sinica,2004,33(4):347-351.

[4] Kaplan N H,Erer I,Kent S.Edge detection in remote sensing images via lattice filters based subband decomposition[C]//Proceedings of the 4th International Conference on Recent Advances in Space Technologies.IEEE,2009:437-440.

[5] Cai Y Q,Tong X H,Shu R.Multi-scale segmentation of remote sensing image based on watershed transformation[C]//IEEE Joint Urban Remote Sensing Event.Shanghai,2009:1-6.

[6] 梅珍,林偉.SAR圖像道路檢測及其仿真[J].計算機(jī)仿真,2010,27(5):201-203,251.

Mei Z,Lin W.SAR image road detection and simulation[J].Computer Simulation,2010,27(5):201-203,251.

[7] 鄧小煉,王長耀,王汶,等.一種遙感影像地面控制點動態(tài)模板匹配算法[J].國土資源遙感,2005,17(2):7-11.

Deng X L,Wang C Y,Wang W,et al.An efficient remote sensing image ground control point matching algorithm based on dynamic template[J].Remote Sensing for Land and Resources,2005,17(2):7-11.

[8] Yu X Q,Chen X,Jiang M.Motion detection in moving background using a novel algorithm based on image features guiding self-adaptive Sequential Similarity Detection Algorithm[J].Optik-International Journal for Light and Electron Optics,2012,123(22):2031-2037.

[9] Du P J,Liu S C,Xia J S,et al.Information fusion techniques for change detection from multi-temporal remote sensing images[J].Information Fusion,2013,14(1):19-27.

[10]Lopez-Molina C,De Baets B,Bustince H,et al.Multiscale edge detection based on Gaussian smoothing and edge tracking[J].Knowledge-Based Systems,2013,44:101-111.

[11]Fazan A J,Poz A P D.Rectilinear building roof contour extraction based on snakes and dynamic programming[J].International Journal of Applied Earth Observation and Geoinformation,2013,25:1-10.

[12]Yang G W,Xu F C.Research and analysis of image edge detection algorithm based on the matlab[J].Procedia Engineering,2011,15:1313-1318.

[13]Barnea E I,Silverman H F A.A class of algorithms for fast digital image registration[J].IEEE Transactions on Computers,1972,C-21(2):179-186.