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

闕昊懿， 黃輝先， 徐建閩

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

0 引言

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

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

1 檢測(cè)算法

1.1 模板匹配算法

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

(1)

將式(1)展開，得到

(2)

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

(3)

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

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

1.2 SSDA算法

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

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

(4)

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

1.3 雙閾值SSDA算法

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

首先，定義一個(gè)子圖與模板的絕對(duì)誤差，即

(5)

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

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

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

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

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

(6)

定義算子

(7)

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

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

(8)

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

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

圖1 算法流程

2 方法實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

3 結(jié)論

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

參考文獻(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].國(guó)土資源遙感,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] 朱長(zhǎng)青,王耀革,馬秋禾,等.基于形態(tài)分割的高分辨率遙感影像道路提取[J].測(cè)繪學(xué)報(bào),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圖像道路檢測(cè)及其仿真[J].計(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] 鄧小煉,王長(zhǎng)耀,王汶,等.一種遙感影像地面控制點(diǎn)動(dòng)態(tài)模板匹配算法[J].國(guó)土資源遙感,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.