史 媛，曹 國(guó)

(南京理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，南京 210094)

0 引言

道路作為重要的人造地物，是現(xiàn)代交通體系的主體，具有重要的地理、政治、經(jīng)濟(jì)意義，也是地圖和地理信息系統(tǒng)中主要的記錄和標(biāo)識(shí)對(duì)象。上世紀(jì)70年代中期，由于數(shù)字化地理交通信息技術(shù)發(fā)展的需要，圖像道路提取技術(shù)隨之出現(xiàn)并逐步發(fā)展。一方面，多譜高分辨率的遙感衛(wèi)星、成像雷達(dá)、無人駕駛飛機(jī)的出現(xiàn)，使得對(duì)地觀測(cè)手段更加完備，地理圖像數(shù)據(jù)日益豐富；另一方面，地圖繪制、地理信息系統(tǒng)更新、城市觀測(cè)和規(guī)劃等諸多應(yīng)用需求的出現(xiàn)和不斷增長(zhǎng)，促使道路提取技術(shù)不斷發(fā)展。

目前，國(guó)內(nèi)外諸多研究人員對(duì)高分辨率遙感影像的道路檢測(cè)做了很多研究[1-3]。從自動(dòng)化程度上來分，目前的高分辨率遙感影像道路提取主要分為自動(dòng)化和半自動(dòng)化提取。由于道路上車輛、橋梁以及道路周圍建筑物和樹木等干擾因素的影響，完全的自動(dòng)化道路提取存在較大的難度，為了確保道路提取的準(zhǔn)確性，在道路提取的前、中、后期或多或少需要人工的干預(yù)，這就是目前運(yùn)用較多的半自動(dòng)化道路提取。其中主動(dòng)輪廓模型和模板匹配方法被認(rèn)為是在眾多的半自動(dòng)道路方法當(dāng)中相對(duì)來說較有效的方法[4]。利用主動(dòng)輪廓模型進(jìn)行目標(biāo)提取的過程就是將影像的各種特征(其中包括影像強(qiáng)度和梯度)及連續(xù)性與平滑性約束在一個(gè)能量函數(shù)中表示出來，通過求能量函數(shù)的最小值來達(dá)到提取目標(biāo)的目的[5]。但是在實(shí)際應(yīng)用中，很難定義適當(dāng)?shù)哪芰亢瘮?shù)，并且道路在不同的圖像上所具有的特征也不相同，可針對(duì)不同的特征需要定義不同的能量函數(shù)。與主動(dòng)輪廓模型相比，模板匹配方法有著更廣泛的應(yīng)用。

模板匹配是數(shù)字圖像處理的重要組成部分之一。它是一種把不同傳感器或同一傳感器在不同時(shí)間、不同成像條件下對(duì)同一景物獲取的兩幅或多幅圖像在空間上對(duì)準(zhǔn),或根據(jù)已知模式到另一幅圖中尋找相應(yīng)模式的處理方法。簡(jiǎn)單而言，模板就是一幅已知的小圖像，模板匹配就是在一幅大圖像中搜尋目標(biāo)，已知該圖中有要找的目標(biāo)，且該目標(biāo)同模板有相同的尺寸、方向和特征，通過一定的算法可以在圖中找到目標(biāo)，確定其坐標(biāo)位置。

目前大多數(shù)的匹配算法主要處理不存在旋轉(zhuǎn)情況的匹配對(duì)象。Mikhail H Atallah和宋毅等人分別對(duì)MAD(乘加累積運(yùn)算)、NCC(圖像相關(guān)性算法)和SSDA(序列相似性檢測(cè)算法)等經(jīng)典模板匹配算法進(jìn)行改進(jìn)，以提高匹配速度[6-7]；姜?jiǎng)P等人將多個(gè)算法進(jìn)行融合，以提高匹配速度和準(zhǔn)確度[8]。但是以上算法都是針對(duì)圖像不旋轉(zhuǎn)情況下的匹配，在實(shí)際應(yīng)用中圖像都會(huì)存在不同程度的旋轉(zhuǎn)偏差，這樣就大大影響了匹配精度。遍歷的旋轉(zhuǎn)搜索法是較早的針對(duì)旋轉(zhuǎn)圖像匹配的研究，該方法的思想是每旋轉(zhuǎn)一個(gè)角度計(jì)算其相關(guān)性，或者是先估計(jì)一個(gè)旋轉(zhuǎn)角度，在這個(gè)估計(jì)角度范圍內(nèi)進(jìn)行遍歷搜索，此算法的時(shí)間效率非常低。文中用到的環(huán)投影模板匹配算法是計(jì)算同心環(huán)上各像素點(diǎn)和的均值，并將各環(huán)上像素和的均值組成一個(gè)向量作為模板，根據(jù)相應(yīng)的匹配和搜索策略搜索道路點(diǎn)，具有旋轉(zhuǎn)不變的特性，對(duì)于檢測(cè)曲率較大的道路和有噪聲的道路有較好的效果，同時(shí)算法在時(shí)間效率上也有優(yōu)勢(shì)。

1 環(huán)形投影算法

1991年，Tang等人首次提出了環(huán)形投影轉(zhuǎn)換(TRP)算法[9]，在TRP中，形狀變換技術(shù)被用于定位圖像的中心點(diǎn)和規(guī)范化大小，環(huán)投影用于處理方向問題。隨后Choi和Tsai也對(duì)該算法做了相關(guān)研究[10-11]。Choi等人提出了兩階段模板匹配算法。在第一階段，定義了一個(gè)叫做圖像環(huán)形投影向量和的特征，該特征具有運(yùn)算量小的特點(diǎn)，用該特征來選擇待匹配圖像。在第二階段，用Zernike矩陣對(duì)待匹配圖像進(jìn)行旋轉(zhuǎn)不變模板匹配。Tsai等人針對(duì)旋轉(zhuǎn)不變模板匹配提出了小波分解法。在匹配過程中，他們用具有較高小波系數(shù)的像素來計(jì)算待匹配圖像間的歸一化關(guān)系，此過程中所用圖像為低分辨率圖像。為了使匹配具有旋轉(zhuǎn)不變性，他們用環(huán)投影轉(zhuǎn)換法(TRP)。此方法極大地減輕了傳統(tǒng)的像素與像素匹配中的計(jì)算負(fù)擔(dān)。

1.1 環(huán)投影向量定義

環(huán)投影向量是由不同半徑的同心圓圓周上像素和組成的，如圖1所示，其中某個(gè)半徑為r的圓周的環(huán)投影P(r)值為:

(1)

圖1 環(huán)投影值

那么環(huán)投影向量P由同心圓上各圓周上像素和組成：

P={P(1),P(2),P(3)…P(n)}

(2)

為了使圓周上各像素點(diǎn)的值均勻分布，更好地表現(xiàn)環(huán)投影向量的旋轉(zhuǎn)不變性的優(yōu)點(diǎn)，將公式(1)中半徑為r圓周的環(huán)投影值P(r)改進(jìn)為：

(3)

其中，C=2πr，即C就是半徑為r的圓的周長(zhǎng)。 此時(shí)，環(huán)投影值P(r)表示半徑為r的圓周上像素和的均值。

1.2 用于道路檢測(cè)中的環(huán)投影向量

將TRP運(yùn)用到道路檢測(cè)中，對(duì)環(huán)投影算法做了如下改進(jìn)：

(4)

其中,△x=△r×k×cos(i×△θ)，△y=△r×k×sin(i×△θ)；f(x,y)是圖像中點(diǎn)(x,y)處的像素值；△r=R/nR是半徑為R的模板的樣本間隔，△=2π/Ck是第k個(gè)圓環(huán)的角度間隔，CK=λk,λ=2R/nR，R是最大半徑，nR是圓環(huán)個(gè)數(shù)。文中將連續(xù)的函數(shù)離散化，使其更適用于圖像匹配的計(jì)算，提高了計(jì)算效率[12]。

環(huán)形投影算法能夠有效地將二維圖像轉(zhuǎn)化到一個(gè)一維向量中，提高了計(jì)算效率，并且具有旋轉(zhuǎn)不變性和收縮不變性等優(yōu)點(diǎn)。環(huán)投影向量有一個(gè)重要的性質(zhì)就是旋轉(zhuǎn)不變性，見圖2、3、4和5。由公式(3)可以看出，對(duì)于一個(gè)圓周來講，不論其如何旋轉(zhuǎn)，它的像素和的均值都是不變的。

圖2 原圖像

圖3 旋轉(zhuǎn)后圖像

圖4 原圖環(huán)投影向量

圖5 旋轉(zhuǎn)后環(huán)投影向量

2 環(huán)投影向量法在道路提取中的應(yīng)用

2.1 改進(jìn)的環(huán)投影向量

在公式(4)中，Ck的值起到很關(guān)鍵的作用，它決定了每個(gè)圓周上取得的像素點(diǎn)個(gè)數(shù)，Ck值太大，會(huì)增大計(jì)算量，降低檢測(cè)效率；Ck值太小，就不能很好地覆蓋像素點(diǎn)，降低檢測(cè)的準(zhǔn)確度。由公式(4)可知，CK=λk，λ=2R/nR，所以Ck=k×2R/nR，可知Ck的值是由k、R、nR共同決定的，當(dāng)R和nR已定時(shí)，Ck值就由k決定了，而k=1,2…R，當(dāng)k很小時(shí)，Ck就會(huì)很小，即所取得的像素點(diǎn)減少，這使得離圓心近的圓周所取的像素點(diǎn)少，如圖6a所示，而離圓心近的圓周離道路中心線越近對(duì)整個(gè)環(huán)投影向量影響越大，這就降低了匹配的精度。為了克服精度和效率的雙重困難，本文提出了兩種新的Ck值的計(jì)算方法。

第一種改進(jìn)的Ck值的計(jì)算方法是將Ck值確定為某個(gè)不變的值，因?yàn)殡x圓心近的圓周上的像素對(duì)環(huán)投影向量的影響較大，所以確定Ck時(shí)需優(yōu)先考慮這些圓周的情況。所以，

(5)

該計(jì)算方法既考慮到對(duì)環(huán)投影向量影響大的環(huán)投影值，又提高了計(jì)算效率。本文用該方法通過人工選擇計(jì)算環(huán)投影向量的值，如圖6b所示。

第二種改進(jìn)的Ck值的計(jì)算方法是充分利用了同心圓上各個(gè)圓周上的像素點(diǎn)，盡量把每個(gè)圓周上的每個(gè)像素都包含在內(nèi)，提高了匹配的精準(zhǔn)度，見圖6c。

(6)

環(huán)投影匹配法主要用于圓周上特征值的比較，很少涉及到圖像中心點(diǎn)的特征問題，當(dāng)把這個(gè)方法用于檢測(cè)道路的中心線時(shí)，同心圓的圓心就在道路中心線上，此時(shí)圖像中心點(diǎn)的特征就顯得很重要了。為了提高道路檢測(cè)的準(zhǔn)確度，把中心點(diǎn)特征也加入到環(huán)投影向量中，此時(shí)公式(2)中環(huán)投影向量變?yōu)閚+1維，改進(jìn)為：

P={P(1),P(2),P(3)…P(n),P(n+1)}(7)

其中，P(n+1)是圖像中心點(diǎn)的特征值，即像素值。

(a) 原環(huán)投影值分布

(b) 改進(jìn)一環(huán)投影值分布

(c) 改進(jìn)二環(huán)投影值分布

2.2 特征向量加權(quán)

用環(huán)投影匹配法進(jìn)行道路檢測(cè)，顧名思義同心圓主要覆蓋在道路區(qū)域，圓心就是道路中心點(diǎn)，那么道路主要特征就集中在中心，基于這點(diǎn)對(duì)上述的環(huán)投影向量進(jìn)行加權(quán)[13]。離中心點(diǎn)近的權(quán)值要大些，離中心點(diǎn)遠(yuǎn)的權(quán)值越小。受文獻(xiàn)[13]的啟發(fā)，權(quán)值函數(shù)的定義如下:

(8)

其中，R為最外面圓周的半徑，r為第r個(gè)同心圓的半徑，z為閾值，一般的z取值為R/3。這樣環(huán)投影向量就變?yōu)椋?/p>

p'=W(r)×P

(9)

2.3 相似度的計(jì)算

向量間相似度的計(jì)算一般有兩種方法：距離測(cè)量法和相似性函數(shù)法。距離測(cè)量法中的距離有以下幾種：Minkowsky距離、Euclidean距離、Manhattan距離、Jffreys&Matusita距離、Mahalanobis距離和Camberra距離等。相似性函數(shù)法有:夾角余弦法、相關(guān)系數(shù)法、廣義Dice系數(shù)法、廣義Jaccard系數(shù)法等。因?yàn)镸anhattan距離法簡(jiǎn)單明了，運(yùn)算量較低，并且同等對(duì)待向量中每個(gè)元素的誤差，所以本文采用了Manhattan距離法作為相似度的計(jì)算方法。Manhattan距離為：

(10)

其中,x=(x1,x2,…,xN),y=(y1,y2,…,yN) ,i=1,2…N。

相似度值越小，與模板匹配度越大，越接近道路中心線，取值最小的點(diǎn)就是道路中心點(diǎn)。

3 實(shí)驗(yàn)結(jié)果與分析

基于改進(jìn)的環(huán)投影向量模板匹配法運(yùn)用多幅高分辨率遙感圖像進(jìn)行了道路提取實(shí)驗(yàn),根據(jù)設(shè)置的步長(zhǎng)(一般為模板環(huán)的直徑長(zhǎng)度)，并參考文獻(xiàn)[12]道路跟蹤方法對(duì)道路進(jìn)行跟蹤提取。實(shí)驗(yàn)結(jié)果見圖7、8、9。運(yùn)算平臺(tái)的配置如下：CPU為Intel Xeon E5630 2.50GHz，內(nèi)存2GB，Windows 7系統(tǒng)，Matlab2012b。

實(shí)驗(yàn)一(圖7)中，圖7a是原圖，可以看出圖中道路較為清晰，道路特征明顯，但道路曲率比較大，如圖7a中方框中所示，道路曲率非常大，一些道路檢測(cè)方法在該路況下很可能檢測(cè)失敗，圖7b是環(huán)投影向量模板匹配法檢測(cè)出的道路，圖7c是本文中所用的改進(jìn)的環(huán)投影模板匹配法檢測(cè)出的道路。可以看出，圖7b和7c中的方框能夠較好地檢測(cè)出曲率大的道路。通過本實(shí)驗(yàn)，可以看出對(duì)于圖7a這種類型的道路，原方法和改進(jìn)的環(huán)投影法都能夠精確地檢測(cè)出道路，但改進(jìn)的環(huán)投影模板匹配法在效率上有所提高，本文方法與原方法在精度和效率上的比較結(jié)果如表1所示。

實(shí)驗(yàn)二(圖8)中所選圖比實(shí)驗(yàn)一所選圖路況復(fù)雜，地物信息比較復(fù)雜，道路中的車輛、橋梁等干擾因素也增加了。圖8a為原圖，圖8b為環(huán)投影模板匹配法檢測(cè)結(jié)果，圖中斑點(diǎn)為原環(huán)投影匹配法檢測(cè)出的道路，容易看出在干擾因素影響下道路檢測(cè)偏離了正確的道路方向，見圖8b中的橢圓框，圖8c為改進(jìn)的環(huán)投影模板匹配法的檢測(cè)結(jié)果，可以看出，文中所用方法能夠有效地檢測(cè)出道路信息，并且效率也提高了，如表1所示。

實(shí)驗(yàn)三(圖9)中，圖9a為原圖，圖9b為path opening檢測(cè)結(jié)果[14]，容易看出在道路曲率較大的地方出現(xiàn)了斷裂現(xiàn)象，如橢圓框所示，圖9c為原環(huán)投影模板匹配法的檢測(cè)結(jié)果，受道路周圍因素的影響，且原環(huán)投影值的計(jì)算方法和向量沒有充分考慮中心點(diǎn)的特征，道路檢測(cè)點(diǎn)出現(xiàn)了偏差如圖橢圓框所示，而文中提出的方法克服了上述缺點(diǎn)，不僅考慮中心點(diǎn)周圍圖像特征，而且更重視中心點(diǎn)本身的特征，檢測(cè)效果更好，精度更高，圖9d為本文方法的檢測(cè)結(jié)果，在上述兩種檢測(cè)誤差處都能夠成功檢測(cè)，如圖中橢圓框所示。

(a) 原圖 (b) 環(huán)投影模板匹配法檢測(cè)結(jié)果 (c) 本文方法檢測(cè)結(jié)果

(a) 原圖

(b) 環(huán)投影模板匹配法檢測(cè)結(jié)果

(c) 本文方法檢測(cè)結(jié)果

(a) 原圖 (b) Path opening法檢測(cè)結(jié)果

(c) 環(huán)投影模板匹配法檢測(cè)結(jié)果 (d) 本文方法檢測(cè)結(jié)果

圖9 實(shí)驗(yàn)三檢測(cè)結(jié)果對(duì)比

4 結(jié)束語

針對(duì)高分辨率遙感影像道路寬度大致不變以及道路內(nèi)部灰度較均勻且與周圍環(huán)境相差較大的特征，對(duì)環(huán)投影向量進(jìn)行了改進(jìn)，將同心環(huán)中心點(diǎn)加入投影向量中并對(duì)環(huán)投影向量賦予不同權(quán)值，提高了檢測(cè)道路中心線的準(zhǔn)確度。本文提出的方法也存在一些缺陷，如在道路跟蹤的過程中下一個(gè)點(diǎn)的選取依賴于上一點(diǎn)，一旦道路點(diǎn)的選取偏離正常道路，下面的檢測(cè)就很可能一直偏離而導(dǎo)致檢測(cè)失敗，筆者將在今后的道路跟蹤方面做進(jìn)一步的研究和改進(jìn)。

參考文獻(xiàn)：

[1] Sahar Movaghati, Alireza Moghaddamjoo, Ahad Tavakoli. Road Extraction From Satellite Images Using Particle Filtering and Extended Kalman Filtering[J].IEEE Transactions on geoscience and remote sensing,2010, 48(7):2807-2817.

[2] Karin Hedman, Uwe Stilla, Gianni Lisini,et al.Road Network Extraction in VHR SAR Images of Urban and Suburban Areas by Means of Class-Aided Feature-Level Fusion[J].IEEE transactions on geoscience and remote sensing,2010,48(3):1294-1296.

[3] Li Wei.Road extraction from remote sensing images[J]. Automation Panorama,2009,23(5):20-23.

[4] 楊云,朱長(zhǎng)青,張德.高分辨率遙感影像上道路中心線的半自動(dòng)提取[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2007,19(6): 781-785.

[5] Kass M,Witkin A,Terzopoulos D.Snakes:Active Contour[J].International Journal of Computer Vision, 1988,1(4):321-331.

[6] Mikhail H Atallah.Faster Image Template Matching in the Sum of Absolute value of Differences Measure[J].IEEE Trans on Image Processing,2001,10(4):659-662.

[7] 宋毅，崔平遠(yuǎn)，居鶴華.一種圖像匹配中SSDA和NNC算法的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用,2006(2):42-44.

[8] 姜?jiǎng)P,陳海霞,湯建華.一種快速圖像匹配算法的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2004,40(11):1002-8331.

[9] TANG Y Y,Cheng H D,SUEN C Y.Transformation-ring-projection (TRP) algorithm and its VLSI implementation[J].International Journal of Pattern Recognition and Artificial Intelligence,1991,5(0-2):25-56.

[10] Choi M S, Kim W Y. A novel two stage template matching method for rotation and illumination invariance[J].Pattern recognition,2002,35(1):119-129.

[11] Tsai D M,Chiang C H.Rotation-invariant pattern matching using wavelet decomposition[J].Pattern Recognition Letters,2002,23(1-3):191-201.

[12] Fu G,Zhao H,Li C,et al.Road Detection from Optical Remote Sensing Imagery Using Circular Projection Matching and Tracking Strategy[J].Journal of the Indian Society of Remote Sensing,2013,41(4): 819-831.

[13] 楊德貴,朱孝開,肖順平.基于圓投影和粒子濾波的紅外目標(biāo)跟蹤[J].信號(hào)處理,2009,25(11):1701-1705.

[14] 王雙,曹國(guó).一種基于改進(jìn)path opening的道路提取新方法[J].計(jì)算機(jī)科學(xué),2014,41(2):285-289.