基于改進(jìn)Hough變換的線性目標(biāo)檢測(cè)

張國(guó)英，程益鈺，朱 紅

（中國(guó)礦業(yè)大學(xué) （北京）計(jì)算機(jī)系，北京100083）

0 引 言

在遙感影像處理中，線性目標(biāo)的檢測(cè)和提取具有重要的地位。在一幅遙感影像中，道路、機(jī)場(chǎng)跑道等都是重要的線性地物，因此線性目標(biāo)提取具有重要的意義。針對(duì)如何提取線性目標(biāo)的問(wèn)題，現(xiàn)在已經(jīng)有很多研究，但都有一定的不足。線性目標(biāo)檢測(cè)具有代表性的方法主要是聚類方法，代表方法有：朱昌盛等人運(yùn)用Hough變換，提出基于平行線對(duì)的線性目標(biāo)檢測(cè)［1］。這類方法具有較強(qiáng)的魯棒性，在檢測(cè)直線時(shí)，受噪聲和曲線間斷的影響特別小，其缺點(diǎn)是由于是全搜索，計(jì)算量和存儲(chǔ)量都很大，不利于實(shí)時(shí)處理。另外，潘建平等提出的基于數(shù)學(xué)形態(tài)學(xué)的線性目標(biāo)檢測(cè)方法［2］，許華榮等人的基于最小二乘B樣條曲線的線性目標(biāo)檢測(cè)［3］，王義敏等的基于區(qū)域生長(zhǎng)的線性目標(biāo)檢測(cè)［4］和Yoshihiko的基于神經(jīng)網(wǎng)絡(luò)的線性目標(biāo)檢測(cè)［5］。其優(yōu)點(diǎn)是計(jì)算不復(fù)雜，處理速度快，缺點(diǎn)在于跟蹤邊緣時(shí)不能處理有間斷的直線，邊緣檢測(cè)算法一定程度上制約這類算法的性能。

Hough變換［5－7］是一種用來(lái)在衛(wèi)星影像中提取線性目標(biāo)邊緣特征的簡(jiǎn)便而有效的方法。其原理是把在圖像空間中的直線檢測(cè)轉(zhuǎn)換到參數(shù)空間里對(duì)點(diǎn)的檢測(cè)，通過(guò)在參數(shù)空間里進(jìn)行累加統(tǒng)計(jì)完成檢測(cè)任務(wù)。檢測(cè)直線時(shí)，對(duì)參數(shù)空間的二維數(shù)組累加統(tǒng)計(jì)，得到最大值所對(duì)應(yīng)的第一條直線，然后依次尋找次最大值對(duì)應(yīng)的其他直線，但在這個(gè)過(guò)程中容易重復(fù)檢測(cè)直線。另外，傳統(tǒng)Hough變換算法的處理對(duì)象是整幅圖像數(shù)據(jù)，導(dǎo)致計(jì)算量和存儲(chǔ)量都很大，不利于實(shí)時(shí)處理。Freeman編碼［9，10］是一種描述邊界的方法，用邊界方向作為編碼依據(jù)，一般描述的是邊界點(diǎn)集，只需保存起點(diǎn)和邊界鏈碼，即可描述目標(biāo)的形態(tài)。因此，用Freeman編碼描述每個(gè)區(qū)域目標(biāo)，大大簡(jiǎn)化了目標(biāo)區(qū)域，可以節(jié)省大量?jī)?nèi)存空間，并且同時(shí)保留了目標(biāo)的幾何形態(tài)，在衛(wèi)星影像中得到大量的使用。根據(jù)以上分析，本文以提取平行對(duì)線對(duì)為原型，分析了Hough變換和Freeman鏈碼提取直線的優(yōu)缺點(diǎn)，提出了基于Freeman編碼的改進(jìn)Hough變換檢測(cè)線性目標(biāo)算法。

改進(jìn)后的Hough變換算法，其處理對(duì)象由整幅影像的數(shù)據(jù)改為圖像分割后各區(qū)域的邊界鏈碼數(shù)據(jù)。在尋找圖像中直線的時(shí)候，刪除已找到的直線鏈碼數(shù)據(jù)，繼續(xù)尋找后續(xù)其他直線，從而避免了重復(fù)的直線檢測(cè)。在檢測(cè)平行線對(duì)之前，對(duì)圖像進(jìn)行分割，然后對(duì)分割得到的各個(gè)區(qū)域使用Hough變換，這樣就能找出整個(gè)影像中所有平行線段，從而完成對(duì)所有線性目標(biāo)的檢測(cè)。最后，為了驗(yàn)證檢測(cè)出來(lái)的準(zhǔn)道路是否為實(shí)際道路，設(shè)計(jì)了平行線對(duì)模型算法，來(lái)提高提取的正確率。

1 Freeman 編碼

Freeman編碼是圖像處理中最基本的目標(biāo)描述手段。用不同斜率的8個(gè)方向基元來(lái)描述輪廓邊界，得到的編碼即為Freeman編碼。對(duì)任一閉合區(qū)域，從某個(gè)起點(diǎn)開(kāi)始，將邊界的走向按Freeman編碼的方式記錄下來(lái)，就形成連續(xù)的方向序列即為邊界編碼。數(shù)字化二值輪廓曲線用八方向Freeman鏈碼表示，可以形成n條鏈，每條鏈指向8個(gè)方向中的一個(gè)，即ai∈｛0，1，2，…，7｝。如圖1所示，其中i為像素索引值，ai表示由像素 （i）指向像素 （i＋1）的鏈碼方向，最終n條鏈的曲線鏈碼表示為

式中：S——邊界的起點(diǎn)像素，n——邊界點(diǎn)的個(gè)數(shù)。當(dāng)邊界閉合時(shí)，會(huì)回到起點(diǎn)，S可省略。

圖1 Freeman 鏈碼的方向取值

如圖2所示的圖像輪廓邊界，使用Freeman編碼表示則為：077666654533212122。

Freeman鏈碼檢測(cè)直線應(yīng)滿足3 個(gè)條件，請(qǐng)參見(jiàn)文獻(xiàn)［8］。Freeman檢測(cè)直線的一般過(guò)程是：對(duì)圖像進(jìn)行去噪、二值化處理后，使用上述的3個(gè)約束條件遍歷直線，來(lái)完成對(duì)直線的初步識(shí)別，后續(xù)通過(guò)直線段的合并操作能較好地檢測(cè)出直線段，不過(guò)該算法對(duì)噪音較敏感。

2 算法流程

圖2 閉合邊界的Freeman編碼

本文算法以平行線特征為依據(jù)，檢測(cè)衛(wèi)星影像中線性目標(biāo)主要按以下幾個(gè)步驟進(jìn)行。首先對(duì)采集到的遙感影像進(jìn)行平滑濾波預(yù)處理消除椒鹽噪聲，然后通過(guò)以灰度一致性為原則，像素生長(zhǎng)法為手段對(duì)圖像進(jìn)行分割，分割后得到的各個(gè)區(qū)域會(huì)具有各自的形態(tài)幾何特征和顏色信息。接下來(lái)使用Freeman鏈碼提取區(qū)域邊界來(lái)描述分割后的各個(gè)局部目標(biāo)，計(jì)算各目標(biāo)的面積、周長(zhǎng)、外接矩形的長(zhǎng)和寬及長(zhǎng)寬比、復(fù)雜度等幾何特征，去除面積較小、長(zhǎng)寬比小，復(fù)雜度偏小的區(qū)域目標(biāo)。最后，對(duì)剩下的區(qū)域的邊界鏈碼進(jìn)行Hough變換得到構(gòu)成線性目標(biāo)平行邊的直線。對(duì)檢測(cè)出來(lái)的準(zhǔn)平行邊，使用平行邊的數(shù)學(xué)模型進(jìn)行鑒別，以確定其是否確實(shí)為平行邊。最后，根據(jù)得到的平行邊來(lái)確定線性目標(biāo)的位置。整個(gè)算法過(guò)程如圖3所示。

圖3 算法流程

2.1 雙邊濾波

本文采用式 （2）所示的雙邊濾波器對(duì)圖像進(jìn)行濾波。雙邊濾波是一種非線性的濾波方法，是結(jié)合圖像的空間鄰近度和像素值相似度的一種折衷處理，同時(shí)考慮空域信息和灰度相似性，達(dá)到保邊去噪的目的，具有簡(jiǎn)單、非迭代、局部的保留邊緣特點(diǎn)，參見(jiàn)文獻(xiàn) ［11］。

雙邊濾波器中，輸出像素的值g（i，j）依賴于鄰域像素的值的加權(quán)組合

式中：z——中心點(diǎn)（k，l）的大小為 （2N＋1）× （2N＋1）的鄰域，權(quán)重系數(shù)w（i，j，k，l）取決于空間鄰近度因子

和亮度相似度因子

的乘積，即

雙邊濾波器受鄰域半徑N、參數(shù)σs和σr等參數(shù)控制。N 值越大，平滑作用越明顯；σs和σr分別為控制著空間鄰近度因子ws和亮度相似度因子wr的衰減程度的參數(shù)。

2.2 區(qū)域分割

本文采用基于生長(zhǎng)的分割方法，具體步驟如下：初始點(diǎn)集合A 為一個(gè)像素點(diǎn)，灰度平均值A(chǔ)vg 為當(dāng)前集合A 中所有像素點(diǎn)灰度值的平均值；點(diǎn)集合A 中像素點(diǎn)周圍鄰域的像素點(diǎn)作為候選點(diǎn)，如果候選點(diǎn)的灰度值和Avg 之差小于初始設(shè)定的閾值，則將該點(diǎn)加入點(diǎn)集合A 中，并更新Avg 的值。重復(fù)該步驟，直到?jīng)]有新的點(diǎn)加入，此時(shí)集合A 即為具有灰度一致性的區(qū)域。然后用Freeman鏈碼描述這個(gè)區(qū)域。

2.3 去除小目標(biāo)

結(jié)合道路特征，可根據(jù)幾何形狀篩分出道路段目標(biāo)。本文通過(guò)計(jì)算周長(zhǎng)C、面積S、長(zhǎng)寬比R、復(fù)雜度E 等幾何特征進(jìn)行小目標(biāo)的去除［12］。面積S 很小的區(qū)域可直接判定為干擾物體。長(zhǎng)寬比

式中：L——目標(biāo)區(qū)域的長(zhǎng)；W——目標(biāo)區(qū)域的寬；長(zhǎng)寬比R 較小的區(qū)域明顯也是干擾區(qū)域。

定義了復(fù)雜度

式中：C——目標(biāo)區(qū)域的周長(zhǎng)；S——面積；復(fù)雜度E 反應(yīng)了平面內(nèi)物體形狀的復(fù)雜程度。復(fù)雜度E 過(guò)小的區(qū)域也為干擾區(qū)域。根據(jù)這些幾何特征去除圖像中的小目標(biāo)。

2.4 平行線模型

平行線模型包括長(zhǎng)度特征和平行特征。①長(zhǎng)度特征，對(duì)于一條曲線來(lái)說(shuō)，不能簡(jiǎn)單地采用端點(diǎn)之間的距離來(lái)表示其長(zhǎng)度，應(yīng)該為其所包含像素的個(gè)數(shù)。構(gòu)成線性目標(biāo)的邊緣曲線具有一定長(zhǎng)度，定義線性目標(biāo)的長(zhǎng)度特征為

式中：C（L）為曲線L 所包含像素的個(gè)數(shù)，Tlength為線性目標(biāo)邊緣的最短長(zhǎng)度閾值。②平行特征，一般地，平行線的判斷依據(jù)是斜率，由于使用斜率時(shí)誤差較大，在本文中使用的是一種平行線對(duì)模型。對(duì)于兩條光滑的線L 與S，如果他們間的任一點(diǎn)在任意方向上到達(dá)L 與S的距離之和為定值。如果兩條直線L 與S同時(shí)滿足上述兩個(gè)條件，則認(rèn)為它們構(gòu)成一組平行線對(duì)，用L／／S表示。如圖4所示。

圖4 平行線對(duì)模型

圖4中，L和S為一對(duì)直線，現(xiàn)任意取這對(duì)直線內(nèi)部?jī)蓚€(gè)點(diǎn)A0和B0，｜A1A2｜和｜B1B2｜分別是A0和B0在取定的某個(gè)方向上 （圖4中的虛線方向）到直線L 與S的距離之和。若｜A1A2｜＝｜B1B2｜＝常數(shù)，對(duì)于所有的內(nèi)部點(diǎn)均成立，則可判定這兩條線為一組平行線對(duì)。

2.5 標(biāo)繪目標(biāo)

在統(tǒng)計(jì)參數(shù)域中的每一對(duì) θ，（ ）ρ 時(shí)，記錄參與統(tǒng)計(jì)這對(duì) θ，（ ）ρ 的所有點(diǎn)的x 坐標(biāo)，再根據(jù)得到的ρ 和θ，按求出的式 （9）將平行線上的像素點(diǎn) （x，y）用不同的顏色標(biāo)示出來(lái)，從而可以標(biāo)繪出線性目標(biāo)的位置

2.6 實(shí)驗(yàn)對(duì)比

圖5 實(shí)驗(yàn)結(jié)果對(duì)比

實(shí)驗(yàn)的硬件平臺(tái)：CPU 為Intel Core（TM），主頻2.8 GHz，內(nèi)存4GB。在相同的實(shí)驗(yàn)平臺(tái)下，運(yùn)行耗時(shí)越少表示算法效率越高。實(shí)驗(yàn)結(jié)果對(duì)比如下：①傳統(tǒng)Hough變換在提取平行線對(duì)的第二條直線時(shí)出現(xiàn)了重復(fù)檢測(cè)第一條直線的情況，而改進(jìn)后的算法不會(huì)出現(xiàn)重復(fù)檢測(cè)的情況并且可以準(zhǔn)確檢測(cè)出線性目標(biāo)的兩條平行邊。②在檢測(cè)平行線對(duì)的數(shù)量上，當(dāng)圖像中有多個(gè)線性目標(biāo)時(shí)，本文檢測(cè)算法能檢測(cè)出所有線性目標(biāo)的平行線對(duì)，而傳統(tǒng)Hough變換法只能檢測(cè)出最規(guī)則的那對(duì)平行線。③在檢測(cè)性能上，從表1可以看出，平行線對(duì)檢測(cè)算法優(yōu)于傳統(tǒng)算法，識(shí)別精度有了很大提高。在運(yùn)算耗時(shí)上，由于改進(jìn)算法只需對(duì)邊界鏈碼數(shù)據(jù)進(jìn)行運(yùn)算，大大降低了Hough 變換過(guò)程中的復(fù)雜度，使得本文檢測(cè)算法耗時(shí)更少。

表1 測(cè)試結(jié)果

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

實(shí)驗(yàn)系統(tǒng)采用Visual studio2010平臺(tái)開(kāi)發(fā)，實(shí)驗(yàn)中使用的遙感影像大小為580＊508，圖中的道路、隔離帶和車輛都可以很容易被人眼識(shí)別出來(lái)。使用本文算法識(shí)別道路的過(guò)程，如圖6所示。其中圖6 （a）為原始衛(wèi)星影像，圖6（b）是進(jìn)行中值濾波和圖像分割后得到的結(jié)果，圖6 （c）是使用基于區(qū)域生長(zhǎng)的灰度一致化方法去除小目標(biāo)得到的灰度圖像，圖6 （d）為對(duì)圖6 （c）中的灰度圖像進(jìn)行二值化后得到的結(jié)果，圖6 （e）為對(duì)二值圖像使用形態(tài)學(xué)方法進(jìn)行膨脹、腐蝕和填充后的結(jié)果，圖6 （f）為Hough變換提取出平行線對(duì)后標(biāo)繪出線性目標(biāo)的位置。實(shí)驗(yàn)中，由于原始圖像中有樹(shù)陰遮擋、車輛等因素的干擾，導(dǎo)致分割后的圖像有很多孔洞，所以使用形態(tài)學(xué)方法對(duì)其進(jìn)行填充后才進(jìn)行后續(xù)平行線對(duì)的提取。從結(jié)果看，對(duì)于線條狀的線性道路目標(biāo)能被有效地提取出來(lái)，但對(duì)呈弧線型的彎曲支路，沒(méi)有提取出來(lái)，對(duì)提取這類彎曲的支路部分還需進(jìn)一步研究處理。

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

圖6 實(shí)驗(yàn)處理過(guò)程

在總結(jié)現(xiàn)有線性目標(biāo)檢測(cè)算法的基礎(chǔ)上，本文根據(jù)遙感影像中線性道路具有寬度一定、灰度一致、道路有一定的長(zhǎng)度等特征提出了一種結(jié)合Freeman鏈碼和Hough變換的道路檢測(cè)算法。通過(guò)實(shí)驗(yàn)分析，改進(jìn)后的算法，效率高、計(jì)算結(jié)果更精準(zhǔn)、允許少數(shù)點(diǎn)的擾動(dòng)、內(nèi)存使用上更靈活、適用性強(qiáng)。但是，在檢測(cè)路面噪聲信息較多、局部灰度變化較大的影像中道路時(shí)，其性能會(huì)受到明顯影響。另外，該算法僅適合檢測(cè)直線形道路，在道路寬度忽然改變的情況效果也不是很好，這些都有待改進(jìn)。

［1］ZHU Changsheng，ZHOU Wei，GUAN Jian.Main roads ex－traction from SAR imagery based on parallel pairs detection［J］.Journal of Image and Graphics，2011，16 （10）：1908－1917 （in Chinese）.［朱昌盛，周偉，關(guān)鍵.基于平行線對(duì)檢測(cè)的SAR 圖像主干道提取算法 ［J］.中國(guó)圖象圖形學(xué)報(bào)，2011，16 （10）：1908－1917.］

［2］PAN Jianping，WU Mingquan.Road detection based on morphology ［J］.Computer Engineering and Applications，2008，44（11）：232－233 （in Chinese）.［潘建平，鄔明權(quán).基于數(shù)學(xué)形態(tài)學(xué)的道路提取 ［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44 （11）：232－233.］

［3］XU Huarong，WANG Xiaodong，F(xiàn)ANG Qiu.Structure road detection algorithm based on B－spline curve model［J］.Acta Automatica Sinica，2011，37 （3）：270－275 （in Chinese）.［許華榮，王曉棟，方遒.基于B樣條曲線模型的結(jié)構(gòu)化道路檢測(cè)算法 ［J］.自動(dòng)化學(xué)報(bào)，2011，37 （3）：270－275.］

［4］WANG Yiming，Qin Yongyuan.Target detection in SAR images based on region growing ［J］.Journal of Computer Applications，2009，29 （1）：45－46 （in Chinese）.［王義敏，秦永元.基于區(qū)域生長(zhǎng)的SAR 圖像目標(biāo)檢測(cè)方法研究 ［J］.計(jì)算機(jī)應(yīng)用，2009，29 （1）：45－46.］

［5］WANG Ping，DONG Yude，LUO Zheshuai.Freeman encodingbased line－segments recognition ［J］.Computer Engineering，2005，31 （10）：171－173 （in Chinese）.［王平，董玉德，羅喆帥.基于Freeman 鏈碼的直線識(shí)別方法 ［J］.計(jì)算機(jī)工程，2005，31 （10）：171－173.］

［6］Yoshihiko Mochizuki，Akihiko Torii，Atsushi Imiya.N－Point hough transform for line detection ［J］.J Vis Commun Image R，2009，20 （4）：242－253.

［7］KANG Wenjing，DING Xuemei，CUI Jiwen.Fast straight－line extraction algorithm based on improved hough transform ［J］.Opto－Electronic Engineering，2007，34 （3）：105－108.

［8］Mokhtarzdae M，Valadan Zoej M J.Road detection from high resolution satellite images using artificial neural networks［J］.International Journal of Applied Earth Observation and Geoinformation，2007，9 （1）：32－40.

［9］Vaddi R S，Boggavarapu L N P，Vankayalapati H D.Contour detection using Freeman chain code and approximation methods for the real－time object detection ［J］.Asian Journal of Computer Science and Information Technology，2011，1 （1）：15－17.

［10］LU Guangquan，XU Hongguo，LI Yibing.Line segment detection based on chain code detection ［J］.Computer Engineering，2006，32 （14）：1－3 （in Chinese）.［魯光泉，許洪國(guó)，李一兵.基于鏈碼檢測(cè)的直線段檢測(cè)方法 ［J］.計(jì)算機(jī)工程，2006，32 （14）：1－3.］

［11］ZHANG Zhiqiang，WANG Wanyu.A modified bilateral filtering algorithm ［J］.Journal of Image and Graphics，2009，14 （3）：443－447（in Chinese）.［張志強(qiáng)，王萬(wàn)玉.一種改進(jìn)的雙邊濾波算法［J］.中國(guó)圖象圖形學(xué)報(bào)，2009，14 （3）：443－447.］

［12］LEI Xiaoqi，WANG Weixing，LAI Jun.A method of road extraction from high－resolution remote sensing images based on shape features［J］.Acta Geodaetica et Cartographica Sinica，2009，38 （5）：457－465 （in Chinese）.［雷小奇，王 衛(wèi)星，賴均.一種基于形狀特征進(jìn)行高分辨率遙感影像道路提取方法［J］.測(cè)繪學(xué)報(bào)，2009，38 （5）：457－465.］