遙感圖像中基于Hough變換的直線提取算法

邢坤 何紅艷 岳春宇 周楠

（北京空間機(jī)電研究所，北京100094）

0 引言

在遙感圖像中，人工目標(biāo)往往具有比較規(guī)則的直線特征，對(duì)目標(biāo)的識(shí)別和定位起到關(guān)鍵作用[1]，但是景物與成像條件的限制會(huì)加大提取直線特征的難度[2]?，F(xiàn)有的直線提取方法主要分為兩類：一是基于圖像域的直線提取方法。該方法的主要思想是直接在圖像空間中對(duì)圖像的梯度或灰度等信息進(jìn)行處理，分割成很多短的近似位于同一直線上的離散直線段（discrete line segments，DLS），然后通過一定的規(guī)則將這些DLS進(jìn)行合并，相位編組法[3]和啟發(fā)式連接法[4]都是基于該思想。此類方法的特點(diǎn)是局部性好，能夠保持良好的邊緣特性，但對(duì)噪聲敏感，易產(chǎn)生斷裂的直線，很難保證結(jié)果的全局最優(yōu)。二是基于變換域的直線提取方法，是在圖像的變換域空間中對(duì)圖像進(jìn)行間接處理，如 Hough變換[5-6]和 Radon變換[7]，其特點(diǎn)是全局性好，能夠處理由于噪聲或其它原因?qū)е聢D像邊界部分丟失的情況，但其參數(shù)的離散化導(dǎo)致結(jié)果不精確，分布效應(yīng)容易產(chǎn)生虛假直線；此外難以確定直線的端點(diǎn)和長(zhǎng)度，算法比較耗時(shí)。文獻(xiàn)[8-12]對(duì)上述兩類方法進(jìn)行了一定改進(jìn)，但缺陷依然存在。

本文提出一種新的算法，在保持Hough變換全局性好的基礎(chǔ)上加以改進(jìn)，結(jié)合圖像域處理的優(yōu)點(diǎn)，提取直線特征。改進(jìn)方案的特點(diǎn)如下：

1）對(duì)邊緣圖像采用八方向鏈碼法編碼，根據(jù)新設(shè)計(jì)的算法快速提取類直線，既完整檢測(cè)到了Hough變換所使用的直線上的特征點(diǎn)，又降低了計(jì)算量；

2）算法對(duì)圖像空間的每條類直線分別進(jìn)行 Hough變換，改進(jìn)投票過程的映射方式，尋找類直線中最多特征點(diǎn)所在的那條直線，只取一個(gè)投票峰值，既減小了計(jì)算復(fù)雜度和空間復(fù)雜度，又去掉了虛假峰值的影響；

3）對(duì)累加器中的特征點(diǎn)進(jìn)行動(dòng)態(tài)融合和分組，確定線段的端點(diǎn)，不用像許多算法那樣從參數(shù)空間反變換回圖像空間確定線段的端點(diǎn)；

4）根據(jù)變換得到的直線參數(shù)以及端點(diǎn)坐標(biāo)，判定直線之間的位置關(guān)系，為下一步的目標(biāo)識(shí)別做好準(zhǔn)備。

1 基于類直線提取的改進(jìn)Hough變換

1.1 初步提取類直線

對(duì)二值圖像直接進(jìn)行Hough變換，不同直線的邊緣點(diǎn)會(huì)互相干擾，影響準(zhǔn)確性，另外遙感圖像的大信息量也影響Hough變換的運(yùn)算速度。本文在Hough變換之前初步提取一些曲線，既約束了Hough變換所使用的直線上的特征點(diǎn)，改進(jìn)了直接進(jìn)行Hough變換時(shí)不同直線的特征點(diǎn)互相干擾的缺點(diǎn)，又降低了計(jì)算量。這些曲線保留有直線的信息，可以擬合為一條直線，所以本文定義為類直線。一些經(jīng)典的直線跟蹤算法如Freeman鏈碼和啟發(fā)式鏈接，從純理論角度講，這些跟蹤算法是準(zhǔn)確的和嚴(yán)格的，但是實(shí)際應(yīng)用起來總是有差距。比如，數(shù)字圖像中機(jī)場(chǎng)跑道邊緣上的點(diǎn)由于像元的關(guān)系不是嚴(yán)格地沿直線分布，另外邊緣圖像中存在許多拐點(diǎn)，這些拐點(diǎn)并不是單像素分布，進(jìn)而影響了直線的跟蹤。文獻(xiàn)[13]設(shè)計(jì)了一種卡爾曼濾波的基于方向預(yù)測(cè)的跟蹤算法提取直線，但比較復(fù)雜，計(jì)算效率差，生成許多無意義直線段，不適于結(jié)合Hough變換使用。

本文根據(jù)鏈碼的思想設(shè)計(jì)了一種算法快速提取類直線。鏈碼法的基本思想是分析相鄰點(diǎn)的方向關(guān)系。對(duì)每個(gè)圖像點(diǎn)，相鄰點(diǎn)用接續(xù)方向來代表方向編碼，定義八方向鏈碼如圖1所示。從上一個(gè)點(diǎn)移到下一個(gè)點(diǎn)，一定對(duì)應(yīng)8個(gè)基元之一，這是因?yàn)槊總€(gè)像素的8個(gè)相鄰像素的方向及距離，恰恰與鏈碼的8個(gè)基元的方向及長(zhǎng)度一致。這樣，位于坐標(biāo)系內(nèi)的曲線便可以由一個(gè)數(shù)字序列來表示。設(shè)掃描邊緣圖像的順序是從下往上，則本文定義遍歷一條類直線必須進(jìn)行三個(gè)方向的移動(dòng)，即0、1、2方向，或者1、2、3方向，或者2、3、4方向。

圖1 八方向鏈碼Fig.1 8-direction chain coding

定義 Lm表示檢測(cè)的第 m (m ≥ 1) 條類直線，表示第m條類直線點(diǎn)組成的空間， Lm(num)表示第m條類直線的像素個(gè)數(shù)，定義 T1為提取類直線中的長(zhǎng)度閾值，它規(guī)定了類直線提取的最少像素?cái)?shù)目，本文設(shè)計(jì)的掃描類直線的步驟如下：

1）記錄圖像中的每個(gè)邊緣點(diǎn)相對(duì)于相鄰邊緣點(diǎn)的鏈碼方向（由于邊緣并不完全是單像素連接，一些點(diǎn)可能包括多個(gè)方向）；

2）抽取步驟1）中鏈碼方向含有0、1、2的邊緣點(diǎn)組成一幅新的邊緣圖像，掃描新圖像中的邊緣點(diǎn)，把互相連通的像素進(jìn)行聚類標(biāo)記，每個(gè)標(biāo)號(hào)相同的聚類構(gòu)成一條類直線，記錄像素坐標(biāo)，存入，判斷 Lm(num)，把閾值小于 T1的類直線記錄刪掉；

3）抽取步驟1）中鏈碼方向含有1、2、3的邊緣點(diǎn)組成一幅新的邊緣圖像，掃描新圖像中的邊緣點(diǎn)，把互相連通的像素進(jìn)行聚類標(biāo)記，記錄類直線的步驟同2）；

4）抽取步驟1）中鏈碼方向含有2、3、4的邊緣點(diǎn)組成一幅新的邊緣圖像，掃描新圖像中的邊緣點(diǎn)，把互相連通的像素進(jìn)行聚類標(biāo)記，記錄類直線的步驟同2），但記錄像素坐標(biāo)的順序從下往上、從右往左；

5）根據(jù)各步驟提取的類直線形成類直線圖像。

上述步驟中的連通像素聚類常用的方法有掃描法和區(qū)域生長(zhǎng)法，其中掃描法又分一次掃描法和兩次掃描法。一次掃描法是在傳統(tǒng)的兩次掃描法基礎(chǔ)上予以改進(jìn)，將遞歸思想和重復(fù)掃描方式結(jié)合起來，通過一次掃描完成連通區(qū)域標(biāo)記；兩次掃描法的思想是對(duì)圖像按一定的順序兩次逐行逐列逐像素的掃描，第一次掃描時(shí)，將臨時(shí)標(biāo)記存儲(chǔ)在一個(gè)與圖像一樣大小的二維數(shù)組中并形成等價(jià)關(guān)系對(duì)，第二次掃描時(shí)，通過一定的搜索和處理方式對(duì)等價(jià)關(guān)系對(duì)進(jìn)行處理。兩次掃描法因?yàn)樗俣葍?yōu)勢(shì)成為現(xiàn)在研究的熱點(diǎn)，并且也證明是速度最快的標(biāo)記方法。

本文在兩次掃描法的基礎(chǔ)上針對(duì)帶有鏈碼值的邊緣圖像設(shè)計(jì)標(biāo)記算法，算法只需要一次逐行逐列逐像素掃描，不需要二次掃描處理等價(jià)關(guān)系的點(diǎn)。以上述鏈碼方向含有0、1、2的邊緣點(diǎn)組成的邊緣圖像為例，算法步驟為：對(duì)圖像進(jìn)行從左到右、從下到上逐行逐列逐像素的掃描，假設(shè)掃描當(dāng)前點(diǎn)A點(diǎn)為特征點(diǎn)，對(duì)A點(diǎn)4、5、6方向的點(diǎn)進(jìn)行判斷，若4、5、6方向的點(diǎn)都是非特征點(diǎn)，則A點(diǎn)標(biāo)記為新的一條類直線的起始點(diǎn)，記錄像素坐標(biāo)，存入；若4、5、6方向有特征點(diǎn)，則把A點(diǎn)標(biāo)記為與上述特征點(diǎn)相同類直線上的點(diǎn)，記錄像素坐標(biāo)，存入。因?yàn)閳D像是鏈碼方向含有 0、1、2的邊緣點(diǎn)組成一幅新的邊緣圖像，鄰域連接只可能如圖2所示的8種單元，按從左到右掃描，所以不會(huì)出現(xiàn)4、5、6方向的點(diǎn)標(biāo)記值不一樣的情況，所以不需要二次掃描處理等價(jià)關(guān)系的點(diǎn)。同理，鏈碼方向含有1、2、3的邊緣點(diǎn)組成的邊緣圖像，考慮鄰近點(diǎn)5、6、7方向的點(diǎn)像素值；鏈碼方向含有2、3、4的邊緣點(diǎn)組成的邊緣圖像，考慮鄰近點(diǎn)0、6、7方向的點(diǎn)像素值。

圖2 鄰域連接單元Fig. 2 Neighborhood connection unit

1.2 改進(jìn)Hough變換投票過程

在算法執(zhí)行之前，定義2T為全局閾值，表示圖像坐標(biāo)系下的長(zhǎng)度；3T為累加器閾值，表示累加個(gè)數(shù)；定義δ為局部距離閾值，同樣是圖像坐標(biāo)系下的長(zhǎng)度。對(duì)第m條類直線 Lm(x,y)執(zhí)行改進(jìn)Hough變換的描述如下：

若

4）重復(fù)步驟1）～3），直到所有符合要求的點(diǎn)對(duì)計(jì)算完畢，是計(jì)數(shù)器中的最大值，若

成立，則認(rèn)為該計(jì)數(shù)器對(duì)應(yīng)累加器中的點(diǎn)為實(shí)際存在的直線，投票完成。

1.3 線段融合

1）累加器合并，比較各累加器中的(R,θ)值，滿足式（7）可認(rèn)為和確定的兩條直線為同一條直線，兩個(gè)累加器中元素合并，其中Δθ和ΔR為參數(shù)空間的量化值，一般分別取1。

2 實(shí)驗(yàn)分析

仿真實(shí)驗(yàn)的硬件環(huán)境為3.00GHz Pentium(R)、內(nèi)存2Gbyte的微機(jī)，在Windows XP平臺(tái)上Visual C++編程實(shí)現(xiàn)。

用某機(jī)場(chǎng)遙感圖像測(cè)試改進(jìn)的直線提取算法的過程（如圖3所示）。圖3（a）為原始圖像，大小600×800像素，5m分辨率；圖3（b）為Canny算子提取邊緣結(jié)果；圖3（c）為提取類直線結(jié)果，長(zhǎng)度閾值1T為20；圖3（d）為本文改進(jìn)Hough變換算法提取直線的最終結(jié)果，其中閾值δ為1，2T為10，3T為30。圖3（d）中機(jī)場(chǎng)跑道輪廓的主要直線特征基本上被檢測(cè)出來，邊緣線段損失少，線段細(xì)節(jié)清晰、連續(xù)，同時(shí)也保持了較高的定位精度。圖3（e）是在圖3（d）的基礎(chǔ)上按照KHT[12]的思想改進(jìn)Hough變換，然后加入端點(diǎn)判定提取直線特征的結(jié)果。KHT使用橢圓核函數(shù)和高斯分布優(yōu)化投票過程，但根本上仍然是“一對(duì)多”映射。圖3中可以看出雖然主要的直線特征也被提取出來，但是圖像空間的大量邊緣沒有必要都進(jìn)行Hough變換的投票過程。

圖3 機(jī)場(chǎng)目標(biāo)直線提取Fig.3 Airport line segments extraction

表1顯示了圖3各步驟的運(yùn)行時(shí)間。相對(duì)于傳統(tǒng)的Hough變換本文算法由于加入了提取類直線這一步驟，不僅減少了其它直線上特征點(diǎn)的干擾，而且不需考慮投票峰值的影響，對(duì)于得到線段的端點(diǎn)坐標(biāo)和長(zhǎng)度等參數(shù)非常重要。根據(jù)同一直線上的特征點(diǎn)計(jì)算出的ρ僅在很小的范圍內(nèi)變化，δ的設(shè)置進(jìn)一步減少了噪聲點(diǎn)干擾。許多對(duì)Hough變換的改進(jìn)算法在投票過程中都是“一對(duì)多”映射，需要在整個(gè)參數(shù)空間內(nèi)建立累加器，而本文算法將同一直線上的特征點(diǎn)映射到參數(shù)空間的一個(gè)點(diǎn)，建立有限個(gè)動(dòng)態(tài)累加器，空間復(fù)雜度大大減少。從計(jì)算復(fù)雜度來說，不需要計(jì)算每個(gè)特征點(diǎn)生成參數(shù)空間特征曲線，僅需判斷特征點(diǎn)是否在直線上；另外還有一些細(xì)節(jié)減少算法的計(jì)算復(fù)雜度，如從類直線特征點(diǎn)空間中選取的兩個(gè)特征點(diǎn)相距一定的距離、對(duì)累加器中的特征點(diǎn)進(jìn)行動(dòng)態(tài)融合和分組等，所以在時(shí)間上比 KHT算法具有優(yōu)勢(shì)。

表1 機(jī)場(chǎng)目標(biāo)直線提取運(yùn)算時(shí)間比較Tab. 1 Runtime of airport line segments extraction

改進(jìn)Hough變換提取直線特征算法不僅適用于機(jī)場(chǎng)目標(biāo)，對(duì)其它大型人工目標(biāo)的直線特征同樣使用。圖4顯示了遙感圖像某港口目標(biāo)直線特征提取過程，其中圖4（a）為原始圖像，368×295像素，圖4（b）為Canny算子提取邊緣結(jié)果，圖4（c）為提取類直線結(jié)果，長(zhǎng)度閾值1T為40，圖4（d）為本文算法提取直線的結(jié)果，直線數(shù)目是10，其中閾值δ為1，2T為10，3T為30，可以看出圖中港口輪廓的主要直線特征基本上被檢測(cè)出來。圖4（e）同樣是邊緣檢測(cè)后按照KHT算法提取直線的結(jié)果，由于算法使用高斯核卷積去除參數(shù)空間的虛假峰值，導(dǎo)致相鄰的平行直線也被去除。表2顯示了上述步驟的運(yùn)算時(shí)間，實(shí)驗(yàn)表明本文算法整體上性能優(yōu)于KHT算法。

圖4 港口目標(biāo)直線特征提取Fig.4 Harbor line segments extraction

表2 港口目標(biāo)直線提取運(yùn)算時(shí)間Tab. 2 Runtime of harbor line segments extraction

下面來討論閾值 T1，T2和 T3對(duì)算法結(jié)果的影響。T1直接影響后續(xù)算法的效率和結(jié)果，如果設(shè)置過小，達(dá)不到初步提取類直線的效果，如果設(shè)置過大，則會(huì)造成邊緣丟失。根據(jù)大量實(shí)驗(yàn)，一般將閾值 T1設(shè)置為目標(biāo)長(zhǎng)度的110～15。表3顯示了對(duì)圖3進(jìn)行Canny算子邊緣檢測(cè)后，在保證不影響最后直線特征提取效果的前提下，不同 T1取值對(duì)算法處理時(shí)間的影響?？梢钥闯?T1取值對(duì)初步提取類直線的影響不大，但隨著取值的增大而逐漸減少改進(jìn)Hough變換算法的運(yùn)行時(shí)間，直到初步提取類直線的條數(shù)固定，改進(jìn)Hough變換運(yùn)行時(shí)間穩(wěn)定。 T2是全局距離閾值，根據(jù)實(shí)驗(yàn)一般設(shè)為。是累加器閾值，在數(shù)值上基本等于 T1，也可以使用另一種設(shè)置方式——取整幅圖像中累加器閾值最大的幾條直線。 T2和 T3對(duì)改進(jìn)Hough變換算法運(yùn)行時(shí)間影響不大。

表3 不同 1T取值的算法運(yùn)行時(shí)間Tab. 3 Runtime with different1T

3 結(jié)束語(yǔ)

針對(duì)大型目標(biāo)的直線特征提取問題，本文提出了一種基于類直線提取的改進(jìn)Hough變換算法。首先從圖像中提取類直線，保持邊緣特性的同時(shí)也檢測(cè)到了Hough變換所需要的特征點(diǎn)；然后對(duì)每條初步提取的類直線分別進(jìn)行Hough變換，改進(jìn)投票過程，設(shè)置一維參數(shù)空間進(jìn)行映射，從類直線中尋找最多特征點(diǎn)對(duì)應(yīng)的那條直線，只取一個(gè)峰值，減少峰值擴(kuò)散和虛假峰值的影響，動(dòng)態(tài)確定線段的端點(diǎn)。理論分析和實(shí)驗(yàn)表明，本文提出的方法簡(jiǎn)單高效，可為遙感影像的識(shí)別、配準(zhǔn)和導(dǎo)航等提供良好的預(yù)處理手段。

References)

[1]楊萍, 姜志國(guó), 劉濱濤. 一種遙感圖像建筑物檢測(cè)新方法[J]. 航天返回與遙感, 2013, 34(5): 70-77.YANG Ping, JIANG Zhiguo, LIU Bintao. A New Approach to Building Detection in Remote Sensing Images[J]. Spacecraft Recovery and Remote Sensing, 2013, 34(5): 70-77. (in Chinese)

[2]陳世平. 景物和成像條件對(duì)遙感圖像品質(zhì)的影響[J]. 航天返回與遙感, 2010, 31(1): 1-6.CHEN Shiping. The Effects on Remote Sensing Image Quality from Scenes and Imaging Conditions[J]. Spacecraft Recoveryand Remote Sensing, 2010, 31(1): 1-6. (in Chinese)

[3]Burns J, Hanson A, Riseman E. Extracting Straight Lines[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 1986, 8(4): 425-455.

[4]Venkateswar V, Chellappa R. Extraction of Straight Lines in Aerial Images[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(11): 1111-1114.

[5]徐勝華, 朱慶, 劉紀(jì)平, 等. 基于預(yù)存儲(chǔ)權(quán)值矩陣的多尺度 Hough變換直線提取算法[J]. 測(cè)繪學(xué)報(bào), 2008, 37(1):83-88.XU Shenghua, ZHU Qing, LIU Jiping, etal. Straight Line Extraction via Multi-scale Hough Transform Based on Pre-storage Weight Matrix[J]. 2008, 37(1): 83-88. (in Chinese)

[6]Kalviainen H, Hirvonen P, Xu L, etal. Probabilistic and Non-probabilistic Hough Transforms: Overview and Comparisions[J]. Image and Vision Computing, 1995, 13(4): 239-252.

[7]Li J, Pan Q, Zhang H, etal. Image Recognition Using Radon Transform[C]. The IEEE 6th International Conference on Intelligent Transportation Systerms IV: Image Analysis, Shanghai, China, IEEE Computer Society, 2003, 4: 741-744.

[8]Rowe N C, Grewe L L. Change Detection for Linear Features in Aerial Photographs Using Edge-finding[J]. IEEE Transaction on Geoscience and Remote Sensing, 2001, 39(7): 1608-1612.

[9]Wu F, Schweitzer H. Fast Selection of Linear Features in Image Data[C]. Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE Computer Society Washington, DC, USA, 2005, 3: 49-54.

[10]Bonci A, Leo T, Longhi S. A Bayesian Approach to the Hough Transform for Line Detection[J]. IEEE Transaction on Systems, Man and Cybernetics, 2005, 35(6): 945-955.

[11]Bandera A, Perez-lorenzo J M, Bandera J P, etal. Mean Shift Based Clustering of Hough Domain for Fast Line Segment Detection [J]. Pattern Recognition Letters, 2006, 27(6): 578-586.

[12]Fernandes L, Oliveira M. Real-time Line Detection through an Improved Hough Transform Voting Scheme[J]. Pattern Recognition, 2008, 41(1): 299-314.

[13]文貢堅(jiān), 王潤(rùn)生. 一種穩(wěn)健的直線提取算法[J]. 軟件學(xué)報(bào), 2001, 12(11):1660-1666.WEN Gongjian, WANG Runsheng. A Robust Approach to Extracting Straight Lines[J]. Journal of Software, 2001, 12(11):1660-1666.(in Chinese)