劉明明，方貴盛

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

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

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

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

1 基于霍夫直線(xiàn)變換檢測(cè)電氣圖中元器件的連接特征

1.1 霍夫直線(xiàn)檢測(cè)技術(shù)

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

圖1 霍夫直線(xiàn)變換示意圖

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

y=kx+b

(1)

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

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

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

(2)

其中，r為原點(diǎn)到直線(xiàn)的距離；θ為原點(diǎn)到直線(xiàn)的垂直線(xiàn)的夾角.

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

1.2 去除連接特征

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

第一步：采用高斯濾波器方法進(jìn)行去噪；

第二步：找到圖像的強(qiáng)度梯度；

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

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

第五步：去除不與強(qiáng)邊緣相連接的所有弱邊緣.

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

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

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

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

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

圖2 手繪草圖

圖3 霍夫直線(xiàn)識(shí)別

圖4 去除連接特征圖

圖5 等價(jià)信息表

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

(3)

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

2.2 改進(jìn)的連通域算法

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

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

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

(4)

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

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

圖6 連通域識(shí)別

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

2.3 合并相交區(qū)域

由于圖中部分元器件是一個(gè)整體卻被分割開(kāi)來(lái)，那是因?yàn)閳D形在膨脹的過(guò)程中并沒(méi)有將孔洞補(bǔ)上，從而產(chǎn)生結(jié)果上的不一致，故需要對(duì)分割出來(lái)的結(jié)果進(jìn)行處理.對(duì)矩形框進(jìn)行判別，對(duì)有相交區(qū)域的矩形進(jìn)行合并，其步驟是：

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

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

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

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

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

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

第四步：對(duì)相交的矩形進(jìn)行合并處理.

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

圖8 矩形相交的3種情況

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

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

圖9 手繪草圖

圖10 手繪草圖

圖11 分割結(jié)果圖

圖12 分割結(jié)果圖

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

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

表1 兩種算法的運(yùn)行時(shí)間

4 結(jié) 語(yǔ)

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

[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.