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

邢坤 何紅艷 岳春宇 周楠

（北京空間機電研究所，北京100094）

0 引言

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

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

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

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

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

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

1 基于類直線提取的改進Hough變換

1.1 初步提取類直線

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

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

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

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

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

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

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

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

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

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

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

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

1.2 改進Hough變換投票過程

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

若

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

成立，則認為該計數(shù)器對應(yīng)累加器中的點為實際存在的直線，投票完成。

1.3 線段融合

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

2 實驗分析

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

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

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

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

表1 機場目標(biāo)直線提取運算時間比較Tab. 1 Runtime of airport line segments extraction

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

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

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

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

表3 不同 1T取值的算法運行時間Tab. 3 Runtime with different1T

3 結(jié)束語

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

References)

[1]楊萍, 姜志國, 劉濱濤. 一種遙感圖像建筑物檢測新方法[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]陳世平. 景物和成像條件對遙感圖像品質(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ù)存儲權(quán)值矩陣的多尺度 Hough變換直線提取算法[J]. 測繪學(xué)報, 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]文貢堅, 王潤生. 一種穩(wěn)健的直線提取算法[J]. 軟件學(xué)報, 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)