直線提取的預處理研究

顧紹通

(江蘇師范大學 語言科學學院，江蘇 徐州 221009；江蘇省語言科學與神經認知工程重點實驗室，江蘇 徐州 221009)

直線提取的預處理研究

顧紹通

(江蘇師范大學 語言科學學院，江蘇 徐州 221009；江蘇省語言科學與神經認知工程重點實驗室，江蘇 徐州 221009)

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

分形幾何；分形維數；霍夫變換；直線提取

1 概 述

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

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

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

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

2.1分形幾何理論

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

(1)

其中,r為所有坐標方向上的尺度因子；Nr為有界集合A的互不覆蓋的子集個數。

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

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

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

(2)

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

(3)

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

2.2非典型直線的分形特征

車輛牌照是交通視頻監控系統中的重要信息，如何準確提取和識別車輛牌照中的直線對于提取車輛牌照中的數字至關重要。由于受到光線、分辨率等因素的影響，使得獲取的車輛牌照圖像中存在噪聲，造成車輛牌照圖像邊緣產生彎曲和鋸齒形態，如圖1所示。

圖1 車牌圖像

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

出土文獻中的字形由于受到腐蝕，字形中的直線筆劃已經失去原貌，呈現鋸齒形態。例如，甲骨拓片字形是以出土甲骨為原型而得到的字形，因為甲骨已在地下埋藏了上千年的時間，受到了腐蝕和發掘損壞，甲骨拓片上產生很多噪聲點，字形的邊緣已經非常模糊，呈現出非常明顯的鋸齒形態，如圖2所示。

圖2 甲骨拓片上的字形

從圖2可以看出，甲骨字形邊緣已經出現鋸齒形態，已不具備甲骨文字形的原貌。

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

2.3分形變換

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

(4)

其中，r表示伸縮比，當r小于1時為壓縮變換，r大于1時為伸長變換。

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

特征點的提取如下所示：

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

(5)

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

考慮到用戶的不同需求，設計了交互功能，用戶可設置不同的角度閾值。當向量夾角θ

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

(6)

變換操作如圖3所示。

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

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

算法步驟如下：

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

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

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

3 Hough變換的直線提取方法

該方法的優點在于抗干擾能力強。原理如下：

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

(2)在參數空間ρ、θ建立累加數組N(ρ,θ)，數組N中元素初始值為零。對于圖像中以1表示的點(x,y)，讓θ遍歷θ軸上所有可能的值，并計算對應的ρ值。根據ρ和θ的值對數組進行累加(N(ρ,θ)=N(ρ,θ)+1)；

(3)對N(ρ,θ)進行局部峰值檢測，得到ρ和θ。

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

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

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

(2)以折線段的首尾兩個端點的連線建立X軸，過其中一點垂直于端點連線建立Y軸，建立平面直角坐標系，對輪廓上的弧線段進行加權壓縮變換；

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

4 實驗及分析

在Windows環境下，在2.20 GHz CPU的計算機上，使用Visual C++6.0集成開發環境和C語言實現了上述算法。圖4、圖5顯示了分形變換前后提取的直線信息。

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

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

從圖中可以看出，對未經分形變換的圖像提取的直線，由于圖像邊緣彎曲比較明顯，即邊緣的分形維數高，因而提取的直線信息較少。而對經分形變換后的圖像提取的直線信息較多。從實驗結果可得，非典型直線經過分形變換后，邊緣已被平滑，提取出了更多的直線信息。

5 結束語

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

[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].計算機科學,2007,34(12):230-232.

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

[10] 楊 波,汪同慶,呂永平,等.利用動態結構元素提取直線[J].計算機輔助設計與圖形學學報，2003，15(4)：421-424.

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

[12] 文貢堅,王潤生.一種穩健的直線提取算法[J].軟件學報,2001,12(11):1660-1666.

[13] 戴激光,宋偉東,李建軍.一種有效的直線提取算法[J].測繪通報,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">網絡出版時間

時間：2017-07-05

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

顧紹通(1978-)，男，碩士，講師，研究方向為中文信息處理。

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