直線提取的預(yù)處理研究

顧紹通

(江蘇師范大學(xué) 語言科學(xué)學(xué)院，江蘇 徐州 221009；江蘇省語言科學(xué)與神經(jīng)認(rèn)知工程重點(diǎn)實(shí)驗(yàn)室，江蘇 徐州 221009)

直線提取的預(yù)處理研究

顧紹通

(江蘇師范大學(xué) 語言科學(xué)學(xué)院，江蘇 徐州 221009；江蘇省語言科學(xué)與神經(jīng)認(rèn)知工程重點(diǎn)實(shí)驗(yàn)室，江蘇 徐州 221009)

傳統(tǒng)的直線提取算法對(duì)標(biāo)準(zhǔn)的直線比較有效，但對(duì)非典型直線并不適用。現(xiàn)實(shí)應(yīng)用中圖像由于受到噪聲污染，圖像中的直線會(huì)變得模糊不清，一般的直線提取方法無法提取到足夠的直線信息。為了準(zhǔn)確提取出受污染圖像中足夠的直線信息，以車牌和甲骨拓片字形為例，提出了一種結(jié)合分形幾何與霍夫變換來提取非典型直線的方法。該方法采用基于分形幾何的方法對(duì)非典型直線進(jìn)行計(jì)算機(jī)輔助復(fù)原，通過計(jì)算非典型直線邊緣的分形維數(shù)，對(duì)其邊緣進(jìn)行壓縮變換，平滑非典型直線邊緣因污染所造成的凹凸形態(tài)，恢復(fù)非典型直線的原貌，并利用Hough變換提取其中的直線。實(shí)驗(yàn)結(jié)果表明，經(jīng)平滑后的非典型直線中可提取更多的直線信息，分形幾何與霍夫變換的組合是有效的直線提取方法。

分形幾何；分形維數(shù)；霍夫變換；直線提取

1 概 述

直線提取對(duì)于數(shù)字圖像中規(guī)則目標(biāo)的形狀分析、識(shí)別來說是一個(gè)基本且必要的前期信息提取步驟。目前已再現(xiàn)多種直線提取方法，如Duda等提出的基于Hough變換的方法[1]，將圖像中的參數(shù)曲線在參數(shù)空間中凝聚成參數(shù)峰點(diǎn)，得到被檢測(cè)圖像中曲線的參數(shù)。該方法對(duì)于隨機(jī)噪聲具有良好的魯棒性，但對(duì)存儲(chǔ)空間要求較高，并且需要較長的計(jì)算時(shí)間，應(yīng)用受到限制。Burns等提出了相位編組的方法[2]，根據(jù)相位一致原理，通過直線覆蓋區(qū)的像素點(diǎn)的邊緣方向一致性來確定直線，利用了邊緣方向作為低層特征，是一種比較穩(wěn)定的直線提取算法；但是該方法受噪聲影響大，初步得到的直線圖往往存在缺損和偏差，存在丟失弱線、丟失模糊線等問題。為此，可以采用一些直線提取的后處理方法，主要有基于Bayesian框架的方法[3]、動(dòng)態(tài)規(guī)劃方法[4]、最小熵方法[5]。Boldt等提出了層次編組的方法[6]，該方法根據(jù)共線性、鄰近性、對(duì)比度相似性等先驗(yàn)給定的規(guī)則，將短線連成長線，但先驗(yàn)規(guī)則由若干人為設(shè)定的參數(shù)確定，因此該方法操作性欠佳，對(duì)圖像的普適性不強(qiáng)。Jeong-Hun等提出了矢量基元組合的方法[7]，該方法基于圖像像素點(diǎn)的特定關(guān)系獲得矢量基元，通過合并基元得出完整直線，其對(duì)基元斷裂和噪聲敏感，不具有魯棒性和全局性。梅小明等提出了Beamlet變換的方法[8]，通過對(duì)圖像按二進(jìn)、遞歸進(jìn)行劃分，利用灰度信息，積分計(jì)算每一小塊圖像中的Beamlets，結(jié)合梯度信息，通過廣義似然比檢驗(yàn)來檢測(cè)判斷符合條件假設(shè)的Beamlets，從而重建目標(biāo)直線。該算法可以克服圖像中的干擾及噪聲，但是計(jì)算量較大，運(yùn)算速度無法保證。侯彪等提出了脊波(ridgelet)變換的方法[9]，該方法利用脊波框架和剖分方法實(shí)現(xiàn)直線特性的識(shí)別。楊波等提出了數(shù)學(xué)形態(tài)學(xué)的方法[10]。陸軍等提出了基于尺度空間[11]的方法，但是該方法尺度空間直線抽取計(jì)算量較大。文貢堅(jiān)等[12]采用卡爾曼濾波器跟蹤衩檢測(cè)圖像的邊緣點(diǎn)，得到直線支持區(qū)，然后擬合直線支持區(qū)，進(jìn)而獲取直線。戴激光等[13]利用高斯濾波模型進(jìn)行圖像去噪，然后進(jìn)行邊緣檢測(cè),在邊緣影像上進(jìn)行Hough變換，通過端點(diǎn)檢測(cè)的方法獲取直線。

以上的直線提取算法都是針對(duì)典型的直線，對(duì)于那些具有鋸齒邊緣，但是從整體上看呈現(xiàn)直線特征的非典型直線則無能為力。比如交通監(jiān)控視頻中提取到的車輛牌照，由于受到燈光、分辨率等因素的影響，車輛牌照會(huì)出現(xiàn)鋸齒狀邊緣，但是從整體上仍然能夠分清圖像的大致邊緣。受到污染的圖像給提取直線帶來了不利影響。另外，在如金文、甲骨文中，也需要對(duì)字形中的直線筆劃加以提取。甲骨文是契刻在龜和獸骨上的文字，其書寫材料甲骨已在地下埋藏上千年的時(shí)間，由于受到污損和發(fā)掘毀壞，導(dǎo)致甲骨損壞嚴(yán)重，拓片上有許多噪聲點(diǎn)，字形的邊緣已經(jīng)非常模糊，呈現(xiàn)出非常明顯的鋸齒形態(tài)，但從整體上來看，直筆仍然具有明顯的直線特征。由于字形邊緣已經(jīng)變得非常模糊，提取其中的直線效果很不理想。由于受到污染，非典型直線邊緣呈現(xiàn)出連綿起伏的鋸齒形狀。對(duì)于這類微觀上呈現(xiàn)鋸齒邊緣整體上呈現(xiàn)直線特征的圖像來說，傳統(tǒng)的直線提取方法已經(jīng)無能為力，如何提取這類非典型直線也是一個(gè)需要加以關(guān)注的問題。

針對(duì)非典型直線的特點(diǎn)，采用基于分形幾何的方法對(duì)非典型直線進(jìn)行計(jì)算機(jī)輔助復(fù)原，計(jì)算圖像邊緣的分形維數(shù)，對(duì)其邊緣進(jìn)行壓縮和變換，使得因污染所造成的凹凸形態(tài)得到平滑處理，恢復(fù)非典型直線的原貌，并利用Hough變換提取其中的直線。

2 基于分形幾何的非典型直線分形變換

2.1分形幾何理論

分形是關(guān)于自相似性的一般概念,由Mandelbrot[14]提出，用于描述具有相似結(jié)構(gòu)的幾何形狀。假設(shè)有n維歐氏空間中的有界集合A,如果A能夠表示為其自身Nr個(gè)互不覆蓋的子集的并時(shí),則稱A是自相似的。此時(shí),A的分形維數(shù)D定義為：

(1)

其中,r為所有坐標(biāo)方向上的尺度因子；Nr為有界集合A的互不覆蓋的子集個(gè)數(shù)。

對(duì)于二維圖像,可以視作三維空間中的表面(x,y,f(x,y)),f(x,y)為圖像(x,y)位置處的灰度值,這樣，圖像灰度的變化就反映在該表面的粗糙程度上,通過使用不同的尺度去度量該表面f(x,y),所得到的維數(shù)就是該圖像的分形維數(shù)。估計(jì)分形維數(shù)[7]的方法有很多，其中差分盒維數(shù)法因計(jì)算簡單、性能較好而應(yīng)用廣泛。

差分盒維數(shù)法的原理是:將m×n的圖像劃分成s×s的很多子塊(s是1～m/2之間的整數(shù))。假設(shè)r=s/m,圖像為三維空間中的平面(x,y,f(x,y)),其中(x,y)表示點(diǎn)的平面位置,第三維表示像素點(diǎn)的灰度值f(x,y)。平面劃分成眾多s×s的子網(wǎng)格,每個(gè)網(wǎng)格上分布一列s×s×s的小盒子。假設(shè)圖像第(i,j)個(gè)網(wǎng)格內(nèi)灰度的最低值和最高值分別落在第k個(gè)和第l個(gè)盒內(nèi),那么Nr在第(i,j)個(gè)網(wǎng)格內(nèi)的分布為：

nr(i,j)=l-k+1

(2)

其中，nr(i,j)為覆蓋第(i,j)網(wǎng)格中的圖像所需的盒子數(shù),則覆蓋整個(gè)圖像所需的盒子數(shù)Nr為：

(3)

對(duì)于不同的r,可得不同的Nr，運(yùn)用最小二乘法可擬合出lgNr～lg(1/r)的斜率,從而得到對(duì)應(yīng)的分形維數(shù)D。

2.2非典型直線的分形特征

車輛牌照是交通視頻監(jiān)控系統(tǒng)中的重要信息，如何準(zhǔn)確提取和識(shí)別車輛牌照中的直線對(duì)于提取車輛牌照中的數(shù)字至關(guān)重要。由于受到光線、分辨率等因素的影響，使得獲取的車輛牌照?qǐng)D像中存在噪聲，造成車輛牌照?qǐng)D像邊緣產(chǎn)生彎曲和鋸齒形態(tài)，如圖1所示。

圖1 車牌圖像

從圖1可以看出，圖像中的車輛牌照比較模糊，已無法準(zhǔn)確分辨出車輛牌照的邊緣，本來是直線的牌照邊緣已變得模糊，呈現(xiàn)鋸齒形態(tài)的分形特征。

出土文獻(xiàn)中的字形由于受到腐蝕，字形中的直線筆劃已經(jīng)失去原貌，呈現(xiàn)鋸齒形態(tài)。例如，甲骨拓片字形是以出土甲骨為原型而得到的字形，因?yàn)榧坠且言诘叵侣癫亓松锨甑臅r(shí)間，受到了腐蝕和發(fā)掘損壞，甲骨拓片上產(chǎn)生很多噪聲點(diǎn)，字形的邊緣已經(jīng)非常模糊，呈現(xiàn)出非常明顯的鋸齒形態(tài)，如圖2所示。

圖2 甲骨拓片上的字形

從圖2可以看出，甲骨字形邊緣已經(jīng)出現(xiàn)鋸齒形態(tài)，已不具備甲骨文字形的原貌。

圖1、2中直線邊緣呈現(xiàn)鋸齒形狀，這些鋸齒形狀邊緣具有自相似性，具備分形的特征，因而可以采用分形幾何加以刻畫和描寫。

2.3分形變換

非典型直線的邊緣可以通過分形壓縮變換進(jìn)行平滑，從而改善非典型直線圖像邊緣的鋸齒形狀。在平面幾何中，伸縮變換可以表示為：

(4)

其中，r表示伸縮比，當(dāng)r小于1時(shí)為壓縮變換，r大于1時(shí)為伸長變換。

非典型直線的邊緣形式多種多樣，可分作不同的弧線段。對(duì)于不同的弧線段分別進(jìn)行變換處理。通過對(duì)各個(gè)折線段進(jìn)行壓縮變換，可以對(duì)非典型直線的邊緣進(jìn)行平滑。對(duì)弧線段進(jìn)行壓縮變換，首先要找到弧線段的位置。非典型直線邊緣彎曲角度比較劇烈的地方，稱為特征點(diǎn)，通過特征點(diǎn)可以計(jì)算弧線段的端點(diǎn)，從而找到每一個(gè)弧線段的位置。

特征點(diǎn)的提取如下所示：

θ=arc cos(V1·V2/|V1||V2|)

(5)

其中，θ(θ≤π)為字形輪廓上的點(diǎn)Pi與相鄰點(diǎn)Pi-1、Pi+1形成的向量V1、V2間的夾角。

考慮到用戶的不同需求，設(shè)計(jì)了交互功能，用戶可設(shè)置不同的角度閾值。當(dāng)向量夾角θ

以弧線段的首尾兩個(gè)端點(diǎn)的連線建立X軸，過其中一點(diǎn)垂直于端點(diǎn)連線建立Y軸，建立平面直角坐標(biāo)系。對(duì)弧線段進(jìn)行變換時(shí)，為了既平滑對(duì)非典型直線的邊緣，又保持非典型直線的基本走向和基本形狀，可以對(duì)特征點(diǎn)及相鄰特征點(diǎn)的坐標(biāo)進(jìn)行加權(quán)處理，表示如下：

(6)

變換操作如圖3所示。

圖3 非典型直線變換處理示意圖

在變換過程中，可設(shè)定分形維數(shù)的閾值，若變換后的圖像分形維數(shù)小于此閾值，則變換處理結(jié)束。

算法步驟如下：

Step1:采用freeman鏈碼跟蹤圖像f(x,y)的輪廓;

Step2:在y方向上對(duì)f(x,y)進(jìn)行壓縮變換，得到圖像f'(x,y);

Step3:計(jì)算f'(x,y)的分形維數(shù)D，如果D

3 Hough變換的直線提取方法

該方法的優(yōu)點(diǎn)在于抗干擾能力強(qiáng)。原理如下：

(1)對(duì)原始圖像進(jìn)行二值化處理；

(2)在參數(shù)空間ρ、θ建立累加數(shù)組N(ρ,θ)，數(shù)組N中元素初始值為零。對(duì)于圖像中以1表示的點(diǎn)(x,y)，讓?duì)缺闅vθ軸上所有可能的值，并計(jì)算對(duì)應(yīng)的ρ值。根據(jù)ρ和θ的值對(duì)數(shù)組進(jìn)行累加(N(ρ,θ)=N(ρ,θ)+1)；

(3)對(duì)N(ρ,θ)進(jìn)行局部峰值檢測(cè)，得到ρ和θ。

Hough變換對(duì)圖像中的噪聲不敏感，能夠較好地處理局部遮擋、覆蓋等情況。

提取非典型直線的步驟如下：

(1)提取非典型直線的特征點(diǎn)和端點(diǎn)，找到折線段；

(2)以折線段的首尾兩個(gè)端點(diǎn)的連線建立X軸，過其中一點(diǎn)垂直于端點(diǎn)連線建立Y軸，建立平面直角坐標(biāo)系，對(duì)輪廓上的弧線段進(jìn)行加權(quán)壓縮變換；

(3)利用Hough變換提取直線。

4 實(shí)驗(yàn)及分析

在Windows環(huán)境下，在2.20 GHz CPU的計(jì)算機(jī)上，使用Visual C++6.0集成開發(fā)環(huán)境和C語言實(shí)現(xiàn)了上述算法。圖4、圖5顯示了分形變換前后提取的直線信息。

圖4 分形變換前后提取的直線段(1)

圖5 分形變換前后提取的直線段(2)

從圖中可以看出，對(duì)未經(jīng)分形變換的圖像提取的直線，由于圖像邊緣彎曲比較明顯，即邊緣的分形維數(shù)高，因而提取的直線信息較少。而對(duì)經(jīng)分形變換后的圖像提取的直線信息較多。從實(shí)驗(yàn)結(jié)果可得，非典型直線經(jīng)過分形變換后，邊緣已被平滑，提取出了更多的直線信息。

5 結(jié)束語

為了盡可能多地提取受污染圖像中的直線信息，提出了結(jié)合分形幾何與霍夫變換來提取非典型直線的方法。采用基于分形幾何的方法對(duì)非典型直線進(jìn)行計(jì)算機(jī)輔助復(fù)原。通過計(jì)算圖像邊緣的分形維數(shù)，進(jìn)行加權(quán)的壓縮變換處理，使得鋸齒狀邊緣得到平滑，恢復(fù)非典型直線的原貌，然后利用Hough變換提取直線。實(shí)驗(yàn)結(jié)果表明，平滑后的非典型直線圖像中提取到了更多的直線信息。由此可見，該方法對(duì)于那些具有鋸齒邊緣且從整體上看呈現(xiàn)直線特征的非典型直線具有明顯的提取效果。

[1] Duda R, Hart P. Use of the Hough transformation to detect lines and curves in the pictures[J].Communications of the ACM,1972,15(1):11-15.

[2] Burns J B, Hanson A R, Riseman E M.Extracting straight lines[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1986,8(4):425-455.

[3] Tupin F,Maitre H,Mangin J F.Detection of linear features in SAR images:application to road network extraction[J].IEEE Transactions on Geoscience & Remote Sensing,1998,36(2):434-453.

[4] Merlet N,Zerubia J.New prospects in line detection by dynamic programming[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1996,18(4):426-431.

[5] Geman D, Jedynak B. An active resting model for tracking roads in satellite images[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1996,18(1):1-14.

[6] Boldt M,Weiss R S.Token-based extraction of straight lines[J].IEEE Transactions on SMC,1989,19(6):1581-1594.

[7] Jang J H,Hong K S.Fast line segment grouping method for finding globally more favorable line segments[J].Pattern Recognition,2002,35(10):2235-2247.

[8] 梅小明,張良培,李平湘.利用Beamlet變換算法提取遙感圖像直線[J].計(jì)算機(jī)科學(xué),2007,34(12):230-232.

[9] 侯 彪,劉 芳,焦李成.基于脊波變換的直線特征檢測(cè)[J].中國科學(xué):E輯,2003,33(1):65-73.

[10] 楊 波,汪同慶,呂永平,等.利用動(dòng)態(tài)結(jié)構(gòu)元素提取直線[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2003，15(4)：421-424.

[11] 陸 軍,王潤生.一種基于尺度空間理論的直線抽取算法[J].中國圖象圖形學(xué)報(bào)，2000,5(8):693-698.

[12] 文貢堅(jiān),王潤生.一種穩(wěn)健的直線提取算法[J].軟件學(xué)報(bào),2001,12(11):1660-1666.

[13] 戴激光,宋偉東,李建軍.一種有效的直線提取算法[J].測(cè)繪通報(bào),2012(11):59-61.

[14] Mandelbrot B B.Fractals:form,chance and dimension[M].San Francisco:W. H. Freeman & Co.,1977.

Investigation on Preprocessing of Line Extraction

GU Shao-tong

(School of Linguistic Science,Jiangsu Normal University,Xuzhou 221009,China；Key Lab of Linguistic Sciences and Neuro-cognition Engineering of Jiangsu Province,Xuzhou 221009,China)

Although traditional line extraction algorithms are effective for standard lines,they are not applicable to atypical lines.The lines in image are blurry since there is noise in many applications,and sufficient information cannot be acquired with the general method of line extraction.To extract sufficient line information in noised image accurately,a method for extracting atypical lines by combining fractal geometry and Hough transform has been proposed,with car plate and Oracle character shape as the examples.It adopts the approach based on fractal geometry to realize computer-assisted restoration for atypical lines.After computation of fractal dimensions of atypical lines edges,compressing and transforming of their edges,the shape of concaves or convexes for atypical lines since noise is smoothed and their original shape are restored,extraction of straight lines by Hough transform.The experimental results show that more information has been extracted from the smoothed atypical lines and that the method of fractal geometry with Hough transform is effective.

fractal geometry;fractal dimension;Hough transform;line extraction

2016-05-13

：2016-08-24 < class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間

時(shí)間：2017-07-05

國家社會(huì)科學(xué)基金(13CYY039);教育部社會(huì)科學(xué)基金(10YJC740032)

顧紹通(1978-)，男，碩士，講師，研究方向?yàn)橹形男畔⑻幚怼?/p>

http://kns.cnki.net/kcms/detail/61.1450.TP.20170705.1649.010.html

TP391

:A

:1673-629X(2017)09-0040-04

10.3969/j.issn.1673-629X.2017.09.009