徐興東，程 立

(1 中南民族大學(xué) 實(shí)驗(yàn)教學(xué)中心, 武漢 430074 ; 2 中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院, 武漢 430074 )

在圖像處理中，通常使用HOUGH變換檢測直線的傾斜角度.HOUGH變換的基本思想是利用平面空間和參數(shù)空間的點(diǎn)-線的對偶性，將平面空間的直線上的點(diǎn)變換到參數(shù)空間，得到直線的表達(dá)式[1,2].使用HOUGH變換檢測直線傾角，具有很強(qiáng)的抗干擾性，能檢測出不連續(xù)的直線和具有彎曲變形的直線的傾角.該種算法實(shí)際上是一種試探的算法，在一定傾角范圍內(nèi)，檢測有沒有一定角度的直線出現(xiàn)，并統(tǒng)計(jì)落在該直線上的點(diǎn)數(shù).很明顯，由于要探測多種可能，HOUGH變換算法計(jì)算量大，特別是在直線可能出現(xiàn)的傾角范圍很大，并且對直線傾角檢測精度要求較高時，必須在很大的范圍內(nèi)進(jìn)行探測，需要更多的計(jì)算時間.同時，對于HOUGH變換來說，還需要比較大的存儲空間來存儲各種探測直線上的點(diǎn)數(shù).

在很多應(yīng)用中，需要能快速檢測出直線的角度.在這里，采取的方法是首先對直線進(jìn)行細(xì)化，然后找到直線的端點(diǎn)，由端點(diǎn)開始沿著直線進(jìn)行遍歷，記下前進(jìn)的方向碼.遍歷完畢后，計(jì)算方向碼的平均值，并進(jìn)行修正，即可檢測出準(zhǔn)確的直線的傾角.

1 方向碼與角度的關(guān)系

在處理中，首先要對直線圖像進(jìn)行細(xì)化，即得到直線的輪廓，通過一些方法很容易得到直線邊緣的輪廓[3].對于連續(xù)的直線，細(xì)化后的骨架也是連續(xù)的.根據(jù)直線上點(diǎn)的8鄰域狀況，很容易找到一條直線的起點(diǎn)[4].在此主要考慮的是黑點(diǎn)(背景為白色)，則一個黑點(diǎn)的8鄰域如圖1所示.其45°以內(nèi)的細(xì)化直線如圖2所示.

圖1 點(diǎn)P的8鄰域Fig.1 Eight neighborhood diagram of point P

圖2 45°以內(nèi)的細(xì)化直線Fig.2 Lines thinned in 45°

其中P為直線上的黑點(diǎn)，0～7為點(diǎn)P的8鄰域，很明顯，如果鄰域0為黑點(diǎn)，則P和0點(diǎn)連線為0°，1為黑點(diǎn)則為45°，稱n為點(diǎn)P的方向碼，可知方向碼n(n=0～7)與角度α關(guān)系為：α=45n.

2 直線的角度檢測

對于細(xì)化后的直線，其端點(diǎn)的8鄰域中只有一個黑點(diǎn)，依此可以找到直線的起點(diǎn).要檢測出整條直線的傾斜角度，可以從某一端點(diǎn)開始進(jìn)行遍歷，在遍歷過程中，記下所有點(diǎn)到下一點(diǎn)的方向碼，然后用方向碼的總和除以總點(diǎn)數(shù)，即可得到直線傾角的大致角度.我們在這里使用該方法以5°為間隔檢測了0～90°的直線，其數(shù)據(jù)如表1所示.

表1 直線的實(shí)際值和檢測值

依照表1，圖3給出了檢測角度和誤差的曲線圖.

圖3 誤差-測量角度曲線圖Fig.3 Error-angle graph

很明顯，誤差和測量角度間的關(guān)系近似于正弦關(guān)系.按照表1的數(shù)據(jù)進(jìn)行正弦曲線的擬合，將測量的角度加上擬合后正弦的相反數(shù)即為補(bǔ)償.圖4為擬合后的曲線.按照擬合的曲線，補(bǔ)償之后的直線測量角度為：

α′ =Σn/N，

(1)

α=α′ + 4.20sin(4πα′/180)，

(2)

式中n為直線上所有點(diǎn)相對于上一點(diǎn)的方向碼，N為總點(diǎn)數(shù)，α為修正后的檢測角度.

圖4 擬合后的誤差-測量角度曲線圖Fig.4 Error-angle fitting graph

3 補(bǔ)償?shù)睦碚撘罁?jù)

在此討論0～45°的范圍，其余范圍同理.在0～45°的范圍內(nèi)的直線，細(xì)化后，輪廓上的點(diǎn)至下一點(diǎn)(從左至右，從下到上)的方向碼只有兩種情況，即0和1，如圖2所示.設(shè)所有方向碼為0的點(diǎn)(正右方)總數(shù)為n0，所有方向碼為1的黑點(diǎn)(右上角)的總數(shù)為n1，且直線上點(diǎn)的總數(shù)為N(不計(jì)起點(diǎn))，則有N=n0+n1；按照方向碼均值求的角度為：

α′ = (45×n1+0×n0)/N= (45×n1)/N，

(3)

按照反正切求的角度應(yīng)為：

α=atan(n1/N)×180/π ，

(4)

則其誤差為：

err= 45×n1/N-atan(n1/N)×180/π.

(5)

由圖2知，補(bǔ)償?shù)恼乙?guī)律函數(shù)在測量角度為0～90°即為一個整周期，故補(bǔ)償函數(shù)的幅值表達(dá)式為：

(6)

對此表達(dá)式，使用Matlab從總點(diǎn)數(shù)N=10到N=10000，n1從0到N(即角度從0～45°)進(jìn)行計(jì)算，可求出A介于4.1873和4.2207之間，變化很小，取最大值和最小值的均值4.2040，作為補(bǔ)償函數(shù)的幅值，即可得到誤差很小的直線傾斜角度.將此補(bǔ)償幅值作為公式(2)中的參數(shù)，并以此作為最終的直線傾角檢測角度，在設(shè)計(jì)的VC檢測程序中進(jìn)行檢測，能獲得非常精確的直線傾角.

4 異常處理

在直線的細(xì)化中，可能出現(xiàn)異常的情況，考慮連續(xù)的3個黑點(diǎn)，一共有4種情況，如圖5所示.其中(a)、(b)中3個點(diǎn)應(yīng)該在一條水平線上，(c)、(d)中的3個點(diǎn)應(yīng)該在一條豎直線上.

圖5 細(xì)化后的異常情況Fig.5 Abnormal conditions diagram after thinning process

對于圖5(a)、圖5(b)，遍歷直線的方向有從左到右和從右到左兩種方式.當(dāng)采取從左至右遍歷時，圖5(a)的方向碼為1和7，圖5(b)為7和1，其和為8，而實(shí)際應(yīng)該為0和0，顯然有較大誤差.若采用從右至左的方向，則圖5(a)、圖5(b)的方向碼分別為3，5和5，3，其和與實(shí)際值4，4之和是相同的.而對于圖5(c)、圖5(d)無論是采用從上至下還是從下至上的方向進(jìn)行處理，方向碼之和和正常情況都是相等的.很明顯，對于圖5(a)、圖5(b)兩圖，當(dāng)采用從左至右的方向遍歷時，由于按圖(1)圖像中任一點(diǎn)P右端3個鄰域點(diǎn)的方向碼分別為1，0，7，而點(diǎn)P的上側(cè)、左側(cè)和下側(cè)相鄰的3鄰域中，中間點(diǎn)均為兩邊點(diǎn)的平均值，所以不用進(jìn)行處理.綜上所述，當(dāng)出現(xiàn)圖5中圖5(a)和圖5(b)兩種情況時，需進(jìn)行特別的處理，將其變?yōu)閷?shí)際的方向碼.

5 時間復(fù)雜度分析

本算法相對于HOUGH變換，在時間復(fù)雜度和空間復(fù)雜度上均具有明顯的優(yōu)勢.以圖形上某一條具有N個點(diǎn)的直線為例，若采用HOUGH變換檢測直線角度，需首先預(yù)設(shè)直線傾角范圍，并設(shè)定角度探測步長，也就是檢測精度.假設(shè)角度范圍為[θ1,θ2], 探測步長為Δθ，則采用HOUGH變換時需完成的循環(huán)次數(shù)為：

(7)

而采用本算法，最壞情況下循環(huán)次數(shù)為8N, 平均循環(huán)次數(shù)4N, 即每個點(diǎn)在其8鄰域中找其下一點(diǎn)的方向碼.采用HOUGH變換時，假設(shè)當(dāng)直線傾角范圍為[-45°,45°]，檢測步長為0.5°，則需循環(huán)次數(shù)為180N，很明顯本算法處理的循環(huán)次數(shù)大大低于HOUGH變換.并且采用HOUGH變換時，每次循環(huán)需計(jì)算所探測角度的正弦和余弦，還需實(shí)現(xiàn)兩次乘法和一次加法，而本算法只需在循環(huán)中完成一次加法.可見本算法在時間復(fù)雜度上明顯低于HOUGH變換，并且檢測時處理時間和直線的傾角范圍及檢測精度無關(guān)，只與直線上的點(diǎn)數(shù)成線性關(guān)系.

6 結(jié)果與討論

按照遍歷直線輪廓，求出各點(diǎn)到下一點(diǎn)的方向碼的平均值，并做修正后，可以獲得直線的準(zhǔn)確的傾角.相對于HOUGH變換，本方法計(jì)算量小很多；而相對于求反三角函數(shù)的方法，本方法不需要討論角度的范圍.表2為經(jīng)過修正后的直線的測量角度和實(shí)際角度，可見經(jīng)過補(bǔ)償后，檢測的角度和直線的實(shí)際角度非常接近，誤差很小.而且使用該方法檢測直線的角度，既可以遍歷到直線的另一端點(diǎn)結(jié)束，也可以只遍歷一定的點(diǎn)數(shù)，檢測所需要的時間與直線的傾角范圍無關(guān).當(dāng)然，本算法只能適用于連續(xù)直線的情況，對于斷續(xù)直線，本算法則不適用[5].而且，在使用算法前，首先必須對直線進(jìn)行細(xì)化處理，或者是單像素的直線邊緣，其處理情況和圖2類似，只是不同角度的直線，方向碼不同，所以文中未給出更多的實(shí)驗(yàn)圖例.

表2 直線的實(shí)際角度值和修正后的檢測角度值Tab.2 The real and estimate angle after correction of lines

參 考 文 獻(xiàn)

[1] 肖志濤, 國澄明, 孟翔宇. 基于Hough變換的傾斜文本圖像的檢測[J]. 紅外與激光工程, 2002,31(4): 315-317.

[2] 趙小川,羅慶生,陳少波. 改進(jìn)型圖像中的直線快速檢測[J]. 光學(xué)精密工程, 2010,18(7): 1654-1660 .

[3] 楊 威, 郭 科, 魏義坤.一種有效的基于八鄰域查表的指紋圖像細(xì)化算法[J]. 四川理工學(xué)院學(xué)報,2008, 21(2): 61-63.

[4] 張曉青,王國文,曹海云,等. 基于細(xì)化的手寫漢字的筆段提取方法[J]. 哈爾濱工業(yè)大學(xué)學(xué)報, 1999, 31(5):107-110.

[5] 程 立，王江晴，田 微，等.手寫體女書文字規(guī)范化處理程度研究[J].中南民族大學(xué)學(xué)報：自然科學(xué)版，2012，31(1)：93-96.