基于改進連通域標(biāo)記的手繪草圖符號分割

劉明明，方貴盛

(1.浙江大學(xué) 機械工程學(xué)院,浙江 杭州 310027；2.浙江水利水電學(xué)院 機械與汽車工程學(xué)院，浙江 杭州 310018)

近年來，隨著智能手機、平板電腦等觸屏設(shè)備的普及，人機交互的方式發(fā)生很大的改變，觸控成為占據(jù)主流的輸入方式.人們可以把頭腦中想象的事物在觸摸屏上手繪出來，形成手繪草圖.手繪草圖通過識別轉(zhuǎn)化為規(guī)范的矢量圖，對后續(xù)處理、修改與保存等具有重要意義.草圖分割是手繪草圖識別的重要環(huán)節(jié)，其好壞直接影響手繪草圖識別的結(jié)果.與普通的圖片相比，設(shè)計人員設(shè)計的草圖一般沒有顏色等信息，大多為二值圖像，并且由于設(shè)計的隨意性與筆劃的不連貫導(dǎo)致草圖單元不完整等問題，使得草圖分割起來更加困難.因此，如何從一系列連續(xù)的筆劃流中準(zhǔn)確地分離出一些具有特定含義的符號，并加以識別，對提高手繪草圖識別效率與質(zhì)量具有重要作用.

圖像分割是將圖像分割成包含相似屬性的不同區(qū)域.為了對圖像分析和解釋有意義，圖像分割出的區(qū)域應(yīng)與描述的對象或者感興趣的特征密切相關(guān).圖像分割是將低層次的灰度或者彩色圖像處理向高層次的圖像描述的第一步，而分割的可靠性則依賴對圖像的精確分析.分割的技術(shù)可分為上下文和非上下文的.上下文的圖像分割技術(shù)利用分組在一起的像素具有相似的灰度級別或者空間位置來分割；而非上下文的分割技術(shù)則是不考慮像素之間的空間關(guān)系.屬于上下文的圖像分割算法有根據(jù)邊緣或者連接狀況來分割的圖像算法[1-3]和根據(jù)區(qū)域相似度來進行分割的圖像算法[4-6]等.這些算法都是依靠像素之間的空間關(guān)系來分割，在區(qū)域分明或者邊界清晰的條件下能夠有很好的分割效果.屬于非上下文的分割算法比較常見的就是根據(jù)閾值來進行分割的算法[7-8]，還有根據(jù)特定理論進行圖像分割的方法[9].

近年來，隨著對圖像分割精度的要求，以往那些基于區(qū)域或者邊緣的分割方法并不能很精確的分割出目標(biāo)區(qū)域.雖然也出現(xiàn)過一些試圖提高分割精確度的算法[10-11]，但是都不能從根本上解決問題，所以基于像素的算法就有著在處理復(fù)雜圖像獨到的優(yōu)勢.傳統(tǒng)的連通域標(biāo)記算法在處理圖像分割過程中運行速度較慢，掃描次數(shù)多，造成了算法效率低下.提高連通域標(biāo)記算法性能可以采用減少圖像的掃描次數(shù)，減少回溯掃描時間，一次掃描盡可能多地提取連通域等信息.基于此，本文提出了一種連通域標(biāo)記的改進算法，通過減少掃描次數(shù)來縮短運行時間，提高算法的性能.由于本文針對的是對電氣草圖的分割，所以要先對草圖進行一些處理，例如去除元器件之間的連接特征，邊緣檢測，膨脹等操作.

1 基于霍夫直線變換檢測電氣圖中元器件的連接特征

1.1 霍夫直線檢測技術(shù)

霍夫(Hough)變換在計算機視覺領(lǐng)域得到了廣泛的應(yīng)用，其主要應(yīng)用于模式識別領(lǐng)域中對二值圖像進行直線檢測[12].霍夫變換主要用于計算特征的全局描述，也可以理解為對每個坐標(biāo)點，計算其對全局一致性的貢獻(xiàn).霍夫直線變換則是將一組離散圖像的點擬合成一條直線，其示意圖(見圖1).

圖1 霍夫直線變換示意圖

平面直角坐標(biāo)系內(nèi)直線的表示形式為:

y=kx+b

(1)

其中，k為斜率，b為截距.

霍夫直線變換就是將原本在笛卡爾坐標(biāo)系下的直線方程轉(zhuǎn)換到極坐標(biāo)霍夫空間下，其極坐標(biāo)的表達(dá)式為：

x×cos(θ)+y×sin(θ)=r

(2)

其中，r為原點到直線的距離；θ為原點到直線的垂直線的夾角.

在實現(xiàn)的圖像處理領(lǐng)域，圖像的坐標(biāo)(x,y)是已知的，要根據(jù)每個(x,y)坐標(biāo)求出(r,θ)，這種變換稱為直線的霍夫變換.該變換是通過將霍夫參數(shù)空間量化為有限區(qū)間或者使用累加器單元疊加來實現(xiàn).出現(xiàn)直線的依據(jù)就是累加器陣列產(chǎn)生了峰值，也就說明了圖像中存在一組離散點可以擬合近似成一條直線.

1.2 去除連接特征

連接特征的檢測要進行邊緣檢測，這里選擇Canny邊緣檢測算法.Canny邊緣檢測是根據(jù)對信噪比與定位乘積進行測度，得到最優(yōu)化逼近算子.其具體步驟描述為：

第一步：采用高斯濾波器方法進行去噪；

第二步：找到圖像的強度梯度；

第三步：采用非最大值抑制的方法刪除不屬于邊緣部分的像素；

第四步：選擇上下閾值進行分割，確定潛在邊緣；

第五步：去除不與強邊緣相連接的所有弱邊緣.

由于草圖中直線特征并不全是連接特征，因此需要取一些連接特征共同的特點，設(shè)定一些閾值，將連接特征標(biāo)記出來，具體做法為：首先在編程界面上手繪一個簡單的電路草圖樣本(見圖2)；然后選用Canny算法檢測二值圖像的邊緣，并用藍(lán)色的線段標(biāo)記出來(見圖3).設(shè)某一點的像素值為a(x,y)，二值圖像的像素值a(x,y)={0,1}.連接特征的去除，只要將連接特征的像素值設(shè)與背景像素一致即可，即藍(lán)色標(biāo)記區(qū)域a(x,y)=0.去除連接特征后的電氣原理圖結(jié)果(見圖4).

2 連通域分離技術(shù)

現(xiàn)階段常用的圖像分割技術(shù)大多是根據(jù)連通域特性來對簡單的二值圖像進行分割.由于草圖中都是筆劃，采用四連通域不包含所有的情況，故選用八連通域.先對草繪圖像進行二值化處理，然后分析連通域，最后將單一連通域的區(qū)域分割出來.但是傳統(tǒng)的連通域標(biāo)記算法Suzuki標(biāo)記算法耗時比較長，還會產(chǎn)生等價信息失效的問題,需要進行很多次的掃描進行改善，所以本文采用的是連通域標(biāo)記改進算法[13].

2.1 傳統(tǒng)的基于行程的連通域標(biāo)記

傳統(tǒng)的連通域標(biāo)記算法大多采用的是基于行程的標(biāo)記[14].這種算法的思想是逐行掃描圖像，每一行中連續(xù)像素為0組成的一個序列為一個集合，并記下起點和終點以及行號.如果每一行中所有的集合與上一行一個集合有重合區(qū)域，則將上一行的標(biāo)號賦給這個集合；如果它與上一行2個以上的集合有重疊區(qū)域，則給它賦一個相連集合的最小標(biāo)號，并將上一行的這幾個集合寫入等價對，說明它們屬于一類.將等價對轉(zhuǎn)換為等價序列，每一個序列需要給一個相同的標(biāo)號，因為它們都是等價.從1開始，給每個等價序列一個標(biāo)號，遍歷每個集合的標(biāo)記，查找等價序列，給予它們新的標(biāo)記，將每個集合的標(biāo)號填入標(biāo)記圖像中.等價信息表(見圖5).

圖2 手繪草圖

圖3 霍夫直線識別

圖4 去除連接特征圖

圖5 等價信息表

設(shè)置初始標(biāo)號m=1.對每個當(dāng)前像素a(x,y)按下式計算其標(biāo)號b(x,y).

(3)

Ms表示一個像素點的左、左上、上、右上的4個單元組成的區(qū)域.條件1表示a(x,y)為X；條件2表示當(dāng)a(x,y)的Ms鄰域中沒有為X的值，則賦一個新值m，并且m比上一個新值增加1；條件3表示a(x,y)的Ms鄰域中有為X的值，則賦上一行與之相連的最小值m.對于圖中產(chǎn)生的等價對，要通過多次掃描,不停的更新標(biāo)號，直到標(biāo)號不再發(fā)生變化.

2.2 改進的連通域算法

傳統(tǒng)的連通域標(biāo)記算法之所以比較耗時，是因為更新像素標(biāo)號的時候要經(jīng)過多次掃描來更新圖像.如果可以在掃描一次圖像，記錄像素標(biāo)號的同時，能夠依據(jù)上一行掃描的像素標(biāo)號從后向前傳播，并及時修改標(biāo)號，這樣就可以在一次掃描完圖像，像素的標(biāo)號也可以更新完畢，所以這里提出了一種改進的連通域標(biāo)記算法.算法的思想是增加一步等價表T的標(biāo)號的遍歷，不用對整張圖再掃描，比較節(jié)省時間.對T中的標(biāo)號，選擇一個根節(jié)點，記錄該根節(jié)點的序號為α，在相同標(biāo)號的T[α]分支上的鄰域上，第一個大于T[α]的T[γ]標(biāo)號記為T[α]，直到此分支結(jié)束，開始找到下一分支，再重復(fù)以上步驟.算法實現(xiàn)過程：

(1)設(shè)置一個用來記錄標(biāo)號的連接表為T，掃描圖像遇到的第一個像素標(biāo)號m=1.

(2)掃描圖像的每一行，由式(3)計算出當(dāng)前行中每個像素的標(biāo)號g(x,y)，并按式(4)及時更新上一行的像素標(biāo)號，這可以通過修改表T中的臨時標(biāo)號來完成.

(4)

(3)當(dāng)掃描完圖像，會產(chǎn)生這些節(jié)點的標(biāo)號偏大，并且原始根節(jié)點的標(biāo)號也不是最小標(biāo)號，所以在這樣一個類似于樹形結(jié)構(gòu)的標(biāo)號表T中，需要增加一次對T的所有節(jié)點的臨時標(biāo)號更新，這里可使用樹的深度優(yōu)先遍歷，可快速地更新所有在T中的標(biāo)號至最小.

先將同一連通域的區(qū)域標(biāo)注出來，用*號標(biāo)記出來，圖中共有24個部件，分析出來標(biāo)記出31個*號，表明識別出來31個連通域(見圖6).然后限定一個矩形，將這些區(qū)域用矩形標(biāo)記出來，方便分割，找到連通域中像素點的最左、最右、最上、最下的位置，并以此做個矩形的區(qū)域，將連通域標(biāo)記出來(見圖7).

圖6 連通域識別

圖7 連通域標(biāo)記

2.3 合并相交區(qū)域

由于圖中部分元器件是一個整體卻被分割開來，那是因為圖形在膨脹的過程中并沒有將孔洞補上，從而產(chǎn)生結(jié)果上的不一致，故需要對分割出來的結(jié)果進行處理.對矩形框進行判別，對有相交區(qū)域的矩形進行合并，其步驟是：

(1)設(shè)計一個算法，確定兩個矩形是否相交.

(2)如果兩個矩形相交，設(shè)計一個算法，求出合并的最小矩形區(qū)域.

一般矩形相交有3種情況(見圖8).其區(qū)域合并算法描述為：

第一步：輸入兩個矩形的左上角坐標(biāo)(xa1,ya1)(xb1,yb1)和右下角坐標(biāo)(xa2,ya2)(xb2,yb2).

第二步：判斷max(xa1,xb1)<=min(xa2,xb2)和max(ya1,yb1)<=min(ya2,yb2)是否都成立.

第三步：如果第二步成立，則相交；反之不相交.

第四步：對相交的矩形進行合并處理.

根據(jù)上述算法進行區(qū)域合并以后，還需要將這些識別出來的一片片區(qū)域分割出來，達(dá)到每片區(qū)域都是一個單獨的元器件的效果.

圖8 矩形相交的3種情況

3 實驗結(jié)果及分析

本文在Visual Studio 2013環(huán)境上(Intel CORE i7 CPU 5500U 2.40GHz CPU,4GB Memory, Windows 7)，利用C++語言編程對所提出的算法進行了驗證與測試.測試圖選擇了手繪的兩幅電氣草圖(見圖9和圖11)，最終分割結(jié)果(見圖10和圖12).在將分割出的區(qū)域還原到原草圖結(jié)果中，得到的結(jié)果(見圖12).最終的實驗結(jié)果表明，原草圖中所有的元器件的個數(shù)與分割出來的結(jié)果相一致，所以本文采用的分割方法可以有效地將每個元器件分割開來，而且具有良好的魯棒性.

圖9 手繪草圖

圖10 手繪草圖

圖11 分割結(jié)果圖

圖12 分割結(jié)果圖

為了測試本文算法在時間上的優(yōu)化，對Suzuki標(biāo)記算法與本文改進的算法在連通域識別上的時間進行了比較，所有數(shù)據(jù)都是測試100次之后在時間上的均值.測試圖像是來自南加州大學(xué)的標(biāo)準(zhǔn)圖像數(shù)據(jù)Miscellaneous database,Textures Database, Aerial Database的圖像，并且選取的圖像都是512×512、連通域最多的圖形，其測試結(jié)果(見表1).

可以看到本文算法在相同圖像下，時間上相較于傳統(tǒng)的連通域標(biāo)識算法縮短了約56%，并且可以很好地識別所有的連通域，可以看出減少掃描次數(shù)可以很好地降低時間復(fù)雜度，從而簡化了算法的執(zhí)行過程.

表1 兩種算法的運行時間

4 結(jié) 語

針對草圖的研究大多都集中在對單個草圖符號的識別，很少從整體上對草圖圖像進行規(guī)劃和整理.為了提高草圖識別精確度，草圖中符號分割具有重要意義.本文提出了一種可以連通域標(biāo)識的改進算法，可以實現(xiàn)手繪電氣原理圖電氣元器件符號的分割.傳統(tǒng)算法是通過不斷掃描圖像，直到等價信息表不再發(fā)生變化為止，耗時較大.本文提出的算法只要添加一次對等價信息表的掃描就可以將最小標(biāo)號傳遞，能夠同樣實現(xiàn)連通域的識別，而且通過減少掃描圖像的次數(shù)，縮減了算法運行的時間.實驗結(jié)果表明，該方法能夠?qū)⒉堇L圖中電氣元器件符號進行有效地分割，并且在時間上也比傳統(tǒng)的連通域標(biāo)識算法縮短了約56%，從而提高算法運行的效率.

[1] CASELLES V,KIMMEL R,SAPIRO G. Geodesic active contours [J].International Journal of Computer Vision,1997,22(1):61-79.

[2] CASELLES V,CATTE F,COLL T,etal. A geometric model for active contours in image processing [J].Numerische Mathematik,1993,66(1):1-31.

[3] KICHENASSAMY S, KUMAR A, OLVER P,etal.Gradient flows and geometric active contour models [C]//IEEE International Conference on Computer Vision.Piscataway:IEEE,1995:810-815.

[4] ZHANG K,SONG H,ZHANG L. Active contours driven by local image fitting energy [J].PatternRecognition,2010,43(4):1199-1206.

[5] WANG Y,XIANG S,PAN C,etal. Level set evolution with locally linear classification for image segmentation [J]. Pattern Recognition, 2013,46(6):3361-3364.

[6] WANG L,LI C,SUN Q,etal. Active contours driven by local and global intensity fitting energy with application to brain MR image segmentation[J].Computerized Medical Imaging and Graphics,2009,33(7):520-531.

[7] KAPUR J N, SAHOO P K, WONG A K C. A new method for gray-level picture threshold using the entropy of the histogram[J]. Computer Vision, Graphics, and Image Processing, 1985, 29(3): 273-285.

[8] TSU N. A threshold selection method from gray level histogram [J].Automatica, 1975, 11(285-296): 23-27.

[9] FELZENSZWALB P,HUTTENLOCHER D. Efficient graph-based image segmentation[J]. International Journal of Computer Vision,2004,59(2):167-181.

[10] FOWLKES C.Spectral Grouping using the Nystrom method[J].IEEE Trans on PAMI,2004,26(2):214-255.

[11] HERNANDEZ-BELMONTE U H,AYALA-RAMIREZ V,SANCHEZ-YANEZ R E.A comparative review of two-pass connected component labeling algorithms[J].Advances in Soft Computing,2011,7095(12):452-462.

[12] GUIL N,VILLALBA J,ZAPATA E L.A fast hough transform for segment detection[J]. IEEE Transactions on Image Processing,1995,4(11):1541-1548

[13] SONKA M, HLAVV, BOYLE R. Image Processing analysis and machine vision,[2nd ed.][J].Journal of Electronic Imaging, 2008,xix(82):685-686.

[14] SUZUKI K,HORIBA I,SUGIE N.Linear-time connected component labeling based on sequential local operations[J]. Computer Vision and Image Understanding,2003,89(1):1-23.