王波，陳剛，高信波

(江西理工大學(xué)建筑與測(cè)繪工程學(xué)院，江西贛州 341000)

一種改進(jìn)的Hough變換在建筑物提取中的算法研究

王波?，陳剛，高信波

(江西理工大學(xué)建筑與測(cè)繪工程學(xué)院，江西贛州 341000)

Hough變換作為圖形檢測(cè)提取的經(jīng)典工具，有著其他算法無法比擬的優(yōu)越性，比如對(duì)噪聲不敏感，有著良好的容錯(cuò)性與魯棒性。Hough變換也被應(yīng)用到遙感圖像邊緣提取中。但是傳統(tǒng)的Hough變換計(jì)算量大，占用內(nèi)存空間大。本文提出了一種改進(jìn)的Hough變換算法在建筑物邊緣直線段檢測(cè)中的應(yīng)用，重點(diǎn)對(duì)改進(jìn)的Hough變換算法原理進(jìn)行了分析，改進(jìn)的Hough變換算法可減小計(jì)算量，并通過實(shí)驗(yàn)表明其提取精度較高。

Hough變換；建筑物提?。贿吘墮z測(cè)；直線段提取

1 引 言

利用遙感圖像進(jìn)行信息提取不僅是遙感領(lǐng)域研究的重點(diǎn)和難點(diǎn)，同時(shí)也是圖像理解和計(jì)算機(jī)視覺研究的重點(diǎn)。建筑物作為重要的人工地物，其廣泛應(yīng)用于城市化進(jìn)程的監(jiān)測(cè)、城市規(guī)劃、城市環(huán)境檢測(cè)等諸多方面[1]。

人工建筑物通常表現(xiàn)為直線段的形式，因此對(duì)直線段的提取顯得尤為重要。Hough變換作為直線段檢測(cè)的經(jīng)典工具，最大的優(yōu)點(diǎn)是對(duì)被檢測(cè)圖像的噪聲具有很好的魯棒性和容錯(cuò)性，本文將一種改進(jìn)的Hough變換算法應(yīng)用到建筑物提取中，作為建筑物直線段提取的工具。充分利用Hough變換的參數(shù)空間，先整體后局部，較好地克服傳統(tǒng)Hough變換算法計(jì)算復(fù)雜的缺點(diǎn)，將建筑物直線段的檢測(cè)轉(zhuǎn)變?yōu)镠ough變換檢測(cè)直線段的“投票”過程?；贖ough變換提取建筑物信息的基本思路是，首先進(jìn)行圖像的預(yù)處理，對(duì)建筑物進(jìn)行邊緣特征提取、邊緣細(xì)化、二值化圖像；然后用改進(jìn)的Hough變換進(jìn)行直線段檢測(cè)，從而獲取建筑物邊緣直線段。Hough變換具有很好的魯棒性和容錯(cuò)性，可以消除遙感圖像上噪聲和遮蔽的影像，從而精確地提取出建筑物信息。

2 Hough變換原理及其特點(diǎn)

2.1 Hough變換原理

Hough變換是1962年由美國(guó)的Paul Hough提出的一種圖像檢測(cè)技術(shù)，主要用于檢測(cè)圖像中的直線段、圓、二次曲線以及任意曲線[2]。Hough變換檢測(cè)圖像的過程即是“投票”過程，實(shí)現(xiàn)的是從圖像空間到參數(shù)空間的映射。對(duì)于圖像空間的特征點(diǎn)(xm，ym)，Hough變換將其映射到參數(shù)空間的正弦曲線，另取一個(gè)特征點(diǎn)(xn，yn)與(xm，ym)聯(lián)立方程:

求解(ρ，θ)如圖1所示，ρ在圖像空間中表示原點(diǎn)至直線的垂直距離，θ在圖像空間中表示直線法線與X軸之間的夾角。(ρ，θ)在圖像空間中所表示的是區(qū)域1中的像素點(diǎn)。由此可得，在(△ρ，△θ)取值恰當(dāng)?shù)臈l件下，具有一定寬度的一條直線就可以投到單一的(ρ，θ)中，即是Hough變換中最為理想的情況[3]。

圖1 (ρ，θ)的幾何意義

2.2 Hough變換特點(diǎn)

Hough[4]變換是經(jīng)典的提取直線段的方法，對(duì)噪聲不敏感，有較好的容錯(cuò)性和魯棒性較好是其重要的特點(diǎn)，提取出來的直線段具有平移、旋轉(zhuǎn)和尺度的不變性。它不僅克服了一般提取方法對(duì)噪聲敏感的缺點(diǎn)，而且克服了平移、旋轉(zhuǎn)和尺度的不變性較差的缺點(diǎn)。但是傳統(tǒng)的Hough變換存在著幾個(gè)主要的缺點(diǎn):①參數(shù)空間的細(xì)分問題；②需要的計(jì)算大且占用的內(nèi)存大；③提取出的參數(shù)受到離散間隔的制約；④對(duì)被檢測(cè)的圖像，只能夠指出某一條直線段的存在，并不能完整描述直線段，利用傳統(tǒng)的Hough變換進(jìn)行建筑物邊緣直線段提取會(huì)產(chǎn)生直線段的虛假點(diǎn)和過連接的現(xiàn)象。

3 改進(jìn)的Hough變換直線段提取及其算法

3.1 改進(jìn)的Hough變換直線段提取

針對(duì)上述傳統(tǒng)Hough變換的缺點(diǎn)與局限性，根據(jù)Hough變換的基本原理[5]，Hough變換檢測(cè)直線段的過程即是“投票”過程。圖像空間中的一個(gè)點(diǎn)投影到Hough變換參數(shù)空間上為θr/△θ個(gè)點(diǎn)，θr為Hough變換角度搜索范圍(0<θr<π)，△θ為Hough變換粒度，圖像空間中的一個(gè)點(diǎn)就形成參數(shù)空間中的一條正弦曲線，如圖2、圖3所示。

圖2 圖像空間中直線段上的點(diǎn)

圖3 參數(shù)空間中的正弦曲線

如圖3所示，圖像空間上的一條直線段上的點(diǎn)投影到參數(shù)空間中的正弦曲線，每一個(gè)點(diǎn)對(duì)應(yīng)一條正弦曲線，這些正弦曲線交于一點(diǎn)。因此，在參數(shù)空間中的累加值就產(chǎn)生了局部極大值。這個(gè)極大值就作為利用Hough變換進(jìn)行檢測(cè)圖像時(shí)判斷是否為直線段的重要依據(jù)和標(biāo)準(zhǔn)。

根據(jù)以上所述原理，極大值大致可分為理想狀況和不理想狀況，下面分別就這兩種狀況做討論。

(1)理想狀況，即同一直線段上各點(diǎn)均投影到參數(shù)空間正弦曲線相交于一點(diǎn)。此種狀況下又存在兩種情況。一種為交點(diǎn)是直線段的準(zhǔn)確表述，即最佳逼近；一種為交點(diǎn)非直線段的準(zhǔn)確表述，這種情況下，可以將△ρ的值減小再進(jìn)行局部的Hough變換，直到直線段的最佳逼近為止。

(2)非理想狀況，即同一直線段上各點(diǎn)投影到參數(shù)空間正弦曲線未交于一點(diǎn)。這種情況是Hough變換“投票”過程中存在跨越，大致可分為下面兩種情況:

①單向跨越，即參數(shù)空間中的正弦曲線交于兩點(diǎn)。如圖4(a)所示，這種情況由以下兩種原因引起的。一種是ρ的值定位不準(zhǔn)確，此種情況下將△ρ的值平移后再進(jìn)行局部Hough變換；一種是△ρ的值偏小，此情況下可將其合并為理想狀況下，合并后直線段表達(dá)為式(2):

式(2)中vot1為第一個(gè)正弦交點(diǎn)的投票數(shù)，vot2為第二個(gè)正弦交點(diǎn)的投票數(shù)。顯然，合并后即可根據(jù)上述理想狀況下的兩種情況進(jìn)行處理，進(jìn)而精確地描述直線段。

②雙向跨越，即參數(shù)空間中的正弦曲線交于三點(diǎn)。如圖4(b)所示，同單向跨越，這種情況也由以下兩種原因引起。一種是ρ的值定位不準(zhǔn)確，這種情況可將△ρ的值平移后再進(jìn)行局部Hough變換；一種是△ρ的值偏小，但是它無法像單向跨越那樣直接合并為理想狀況下，這種情況下需要適當(dāng)增大△ρ的值，然后進(jìn)行Hough變換“投票”。增大后△ρ′的取值為式(3):

式(3)中vot1為第一個(gè)正弦交點(diǎn)的投票數(shù)，vot2為第二個(gè)正弦交點(diǎn)的投票數(shù)。隨著△ρ的增大，ρ的值也應(yīng)隨著變化，變化后的ρ′的取值為式(4):

式(4)中vot1為第一個(gè)正弦交點(diǎn)的投票數(shù)，vot2為第二個(gè)正弦交點(diǎn)的投票數(shù)，vot3為第三個(gè)正弦交點(diǎn)的投票數(shù)。經(jīng)過增大△ρ、ρ的值的處理后，就可以轉(zhuǎn)換到理想狀況下Hough變換的“投票”，從而得到精確地直線段描述。

圖4 Hough變換非理想狀況下的兩種情況

通過以上綜合分析了Hough變換檢測(cè)直線段的各種情況，最后都可以轉(zhuǎn)變?yōu)槔硐霠顟B(tài)下Hough變換的“投票”過程，充分利用了Hough變換參數(shù)空間，不斷地進(jìn)行合成、分解，尋求最優(yōu)解，從而精確地對(duì)直線段進(jìn)行描述。

3.2 算法步驟及建筑物提取步驟

基于改進(jìn)的Hough變換算法步驟如圖5所示。

圖5 基于改進(jìn)的Hough變換檢測(cè)直線段流程

4 實(shí)驗(yàn)結(jié)果及其算法分析

4.1 實(shí)驗(yàn)結(jié)果

基于Hough變換提取建筑物信息不是單一的過程[6]，利用Hough變換進(jìn)行建筑物邊緣直線段提取之前要進(jìn)行邊緣檢測(cè)[7]，其基本過程如圖6所示。

圖6 基于Hough變換提取建筑物輪廓流程

圖7 實(shí)驗(yàn)圖像

圖8 Hough變換檢測(cè)結(jié)果

圖9 結(jié)果附著在原圖上

4.2 算法分析

在本文提出的Hough變換算法中，采用是單一的峰值進(jìn)行直線段的提取，圖像中直線外的獨(dú)立點(diǎn)會(huì)影響提取結(jié)果。可以利用以下兩種方法消除影響:

(1)進(jìn)行Hough變換前，消除原圖的這些點(diǎn)，比如使用中值濾波；

(2)進(jìn)行Hough變換時(shí)，可以設(shè)定一定的閾值，除去“投票”值小的直線段。

這樣就可以消除Hough變換時(shí)產(chǎn)生的一些虛假直線段，從而降低Hough變換的復(fù)雜度。

此Hough變換算法的計(jì)算量主要集中在粗的全局Hough變換中，后面的局部Hough變換由于ρ、θ的范圍非常小，計(jì)算量可以忽略不計(jì)?？傮w看來，此算法較傳統(tǒng)的Hough變換計(jì)算量小，由圖9可看出，將Hough變換檢測(cè)出的直線段附著在原圖上吻合較好，提取精度較高。

5 結(jié) 語

本文提出了一種改進(jìn)的Hough變換應(yīng)用在建筑物提取中直線段的檢測(cè)，這種Hough變換算法的中心思想是采用單一的峰值、由整體到局部、由粗略到細(xì)部，逐級(jí)進(jìn)行Hough變換，可以較好解決傳統(tǒng)的Hough變換計(jì)算量大的缺點(diǎn)，同時(shí)也可保證了提取的精度。

[1] 趙英時(shí).遙感應(yīng)用分析原理與方法[M].第一版.北京:科學(xué)出版社，2004

[2] 唐氓，李軍，胡占義.隨機(jī)Hough變換與Tabu搜索算法在基元提取中的比較[J].計(jì)算機(jī)學(xué)報(bào)，1999(1)

[3] Ioannou D，Huda W，Laine A F.Circle recognition through a 2D Hough transform and radius histogramming[C].Image and Vison Computer，1999(17):15～26

[4] 楊治明，周齊國(guó).基于霍夫變換理論的圖形識(shí)別[J].重慶工業(yè)高等?？茖W(xué)校學(xué)報(bào)，2002(4)

[5] Daniel Walsh，Adrian E.Raftery.Accurate and efficient curve detection in image:the importance sampling Hough transform [J].2002，35(5):1421～1431

[6] 孟亞賓.高分辨率衛(wèi)星影像建筑物輪廓提取方法研究[D].阜新:遼寧工程技術(shù)大學(xué)，2007

[7] 陶文兵，田巖等.航空?qǐng)D像矩形建筑物自動(dòng)提取方法研究明[J].宇航學(xué)報(bào)，2003，24(4):341～347

One kind of Improvement Hough Transformation in Building Extraction Algorithm Research

WangBo，Chen Gang，Gao XinBo
(Jiangxi University of Architecture and Surveying Institute，Ganzhou 341000，China)

The Hough transformation takes the pattern detection extraction the classical tool，There are other algorithms incomparable superiority，Such as noise，have good fault－tolerance and robustness.Hough transform were applied to the remote sensing image edge extraction.But the Hough transform the traditional calculation，memory space.This paper puts forward a kind of Hough transform algorithm is improved in building straight edge detection，the key to improving the application of the principle of Hough transform algorithm is analyzed，and the improving Hough transform algorithm can reduce the computational complexity，and through the experiments show that the extraction accuracy.

Hough transform；buildings extraction；edge detection；straight extraction

1672－8262(2011)02－112－03

P237，TP301.6

A

2010—08—05

王波(1986—)，男，碩士研究生，專業(yè):大地測(cè)量學(xué)與測(cè)量工程。