基于單義域鄰接圖的圓弧與圓識別

1、基于單義域鄰接圖的圓弧與圓識別    摘要cad推廣和普及的關(guān)鍵步驟之一，主要解決已有大量圖紙?jiān)倮脝栴}。在工程圖紙掃描圖象識別研究中，圓弧識別是識別算法中的重點(diǎn)和難點(diǎn)。傳統(tǒng)的圓弧識別多是基于線段逼近。本文提出一種基于單義域鄰接圖的圓弧及圓識別算法，可以直接提取圓弧。對二值圖象作水平黑游程編碼，相關(guān)游程基于線寬與拓?fù)涞囊恢滦詷?gòu)成條形域，對其中多義域進(jìn)行分裂得單義域（線段域和圓弧域）。單義域鄰接圖可較好描述圖象的幾何屬性與拓?fù)潢P(guān)系。單義域具有明顯的形狀意義（線段、圓弧、箭頭等），提高了識別的整體性。圓弧及圓的識別先從鄰接圖頂點(diǎn)中抽取圓弧域，作為種子圓弧，然

2、后從此出發(fā)遍歷圖，按照同圓來建立路徑，進(jìn)行整弧和整圓增長，最終獲得圓弧和圓的幾何表達(dá)。實(shí)例表明，本算法可以較好地處理圓弧與線段及圓弧的相交與相切，適應(yīng)性較強(qiáng)、識別率較高。 關(guān)鍵詞 工程圖紙，矢量化，圓弧識別，條形域，單義域鄰接圖。 1 引言 圓弧和圓是工程圖形中的重要圖元，已有多種識別算法，可分為兩種：逼近法和直接法。細(xì)化方法先跟蹤中心骨架象素得到短小線段，再用來逼近圓弧和圓1。正交掃描法（orthogonal zig-zag）是先獲得條，再用中垂線跟蹤（perpendicular bisector tracing）分割圓弧2。文獻(xiàn)3以梯形域來逼近圓弧和圓。這三種方法都是以線段來逼近圓弧和圓，

3、如果線段過短，會造成數(shù)據(jù)冗余；如果線段過長，將難以識別短小圓弧，需要后續(xù)處理。輪廓匹配法可直接獲得圓弧和圓，但，輪廓獲取及其匹配都很復(fù)雜4。文獻(xiàn)5采用圖段與圓進(jìn)行模式匹配，確定圓的種子圖段，然后跟蹤其它圖段，最終獲得圓弧和圓的圖形表示。 本文提出一種新的識別方法，以相關(guān)游程線寬和拓?fù)錇榧s束生成條形域，對其中多義域作分裂獲得單義域：線段域和圓弧域，并建立其鄰接圖，選取弧形域，以此為起始點(diǎn)，基于同圓幾何要求，通過深度優(yōu)先搜索來遍歷圖，完成圓弧和圓識別。下面分為四部分，先介紹條形域構(gòu)建和多義域分裂，然后給出建立單義域鄰接圖方法，并對整弧和整圓增長算法進(jìn)行詳細(xì)論述，最后對多種圓弧與圓的識別結(jié)果作出分析

4、。 2 條形域構(gòu)建和多義域分裂 2.1 游程分類 在同一線寬的二值圖象中，一個(gè)游程唯一屬于單一圖元，所以，對工程圖紙掃描圖象先作圖文分離再作粗細(xì)分離3，然后對同一線寬圖象進(jìn)行處理。本文采用自上而下和從左到右掃描，定義同一行中連通黑象素為一水平黑游程，并以此對圖象進(jìn)行編碼。如果當(dāng)前游程是參考游程的上（或下）一行，且左右至少一端搭接（包括鄰接），則稱兩個(gè)游程相關(guān)，具有父子（或子父）關(guān)系。游程可以根據(jù)其父子游程進(jìn)行分類6，本文針對工程圖紙掃描圖象特點(diǎn)，分為七類（如圖1所示）： （1）孤立游程：沒有父游程和子游程； （2）起始游程：沒有父游程，只有一個(gè)子游程； （3）終止游程：沒有子游程，只有一個(gè)父游

5、程； （4）單一游程：只有一個(gè)父游程和一個(gè)子游程； （5）分叉游程：有多個(gè)子游程，至多一個(gè)父游程； （6）匯合游程：有多個(gè)父游程，至多一個(gè)子游程；    （7）交叉游程：有多個(gè)父游程和多個(gè)子游程。 2.2 構(gòu)建條形域 相關(guān)游程基于寬度和拓?fù)涞囊恢滦越M合為條形域，具體條件如下： （1）游程相關(guān)； （2）首游程不是分叉游程和交叉游程，末游程不是匯合游程和交叉游程； （3）游程寬度沒有較大變化； （4）孤立游程和交叉游程單獨(dú)構(gòu)成條形域。 條件（1）保證條形域的連通性，（2）確保交叉域、匯合域和分叉域的準(zhǔn)確建立，（3）是條形域?qū)挾纫恢滦缘囊螅?）處理特殊情況

6、。 下面給出條形域構(gòu)建算法： （1）移游程到新建條形域中，設(shè)為當(dāng)前游程，如果是孤立游程、分叉游程或交叉游程，則轉(zhuǎn)到（4）; （2）取當(dāng)前游程的子游程，如果與當(dāng)前條形域游程平均寬度相差較大，則轉(zhuǎn)到（4），否則，設(shè)為當(dāng)前游程; （3）如果當(dāng)前游程是單一游程，則加入條形域，并返回（2）；如果是分叉游程或終止游程，則加入條形域； （4）完成條形域構(gòu)建。 2.3 分裂多義域 從幾何意義上講，根據(jù)上述方法構(gòu)建的條形域包括兩種情況，一是表達(dá)單一幾何實(shí)體，如：線段、圓弧和箭頭等；二是線段與圓弧組合，如折線等。所以，將條形域分為單義域和多義域。一般來講，多義域可看作由線段和圓弧連接而成。因此，對多義域進(jìn)行分裂，

7、提取線段域和圓弧域。 在這里，多義域是開環(huán)的，且單調(diào)，相對一般曲線擬合要簡單些，本文采用首尾相連最大距離法來分裂7。對多義域，先用一條直線連接首尾游程中點(diǎn)，計(jì)算多義域游程中點(diǎn)與直線的最大距離差，并以此點(diǎn)為一分裂點(diǎn)，然后判定所分裂的兩段是否為單義域，如仍為多義域則繼續(xù)分裂，一直進(jìn)行到都是單義域?yàn)橹?，這是一個(gè)遞歸的過程。下面給出分裂步驟： （1）輸入條形域，如為單義域，則轉(zhuǎn)到（5）; （2）對多義域以最大距離法分為兩段：域1和域2，輸出分裂點(diǎn)； （3）如果域1（域2）為多義域，則返回（2）； （4）對分裂點(diǎn)以其y坐標(biāo)作從小到大排序； （5）根據(jù)分裂點(diǎn)，輸出單義域。 3單義域鄰接圖的建立及其拓?fù)浞诸?/p>

8、 3.1 建立單義域鄰接圖 多義域分裂后，圖象描述單元變?yōu)閱瘟x域。但，單義域描述只是表達(dá)幾何信息，而單義域之間還有連接關(guān)系，表達(dá)拓?fù)湫畔?。如果?dāng)前單義域末游程與參考單義域首游程（或當(dāng)前單義域首游程與參考單義域末游程）相關(guān)，則稱兩個(gè)單義域相關(guān)，具有父子（或子父）關(guān)系。采用域鄰接圖（如梯形域和圖段等）可以較好地表達(dá)圖象的幾何與拓?fù)湫畔ⅲ疚牟捎脝瘟x域鄰接圖描述圖象，下面給出建立步驟： （1）加單義域到鄰接圖的頂點(diǎn)表中； （2）取頂點(diǎn)i，i從1到n，n為圖的頂點(diǎn)總數(shù)， 取頂點(diǎn)j，j從1到n，     如果頂點(diǎn)j是頂點(diǎn)i的父域，則加頂點(diǎn)j到頂點(diǎn)i的父鄰接表，且加

9、頂點(diǎn)j到頂點(diǎn)i的鄰接表； 如果頂點(diǎn)j是頂點(diǎn)i的子域，則加頂點(diǎn)j到頂點(diǎn)i的子鄰接表，且加頂點(diǎn)j到頂點(diǎn)i的鄰接表； 。    圖2給出圓的圖表示，頂點(diǎn)1的父鄰接表為空，子鄰接表包含頂點(diǎn)2和3；頂點(diǎn)2的父鄰接表包含頂點(diǎn)1，子鄰接表包含頂點(diǎn)4；頂點(diǎn)3的父鄰接表包含頂點(diǎn)1，子鄰接表包含頂點(diǎn)4；頂點(diǎn)4的父鄰接表包含頂點(diǎn)2和3，子鄰接表為空。 3.2 單義域拓?fù)浞诸?從單義域鄰接圖中很容易就可獲得某一頂點(diǎn)的鄰接點(diǎn)情況，單義域（頂點(diǎn)）根據(jù)其父子域（鄰接點(diǎn)）可以分為七種拓?fù)漕愋停ㄈ鐖D3所示）： （1）孤立域：沒有父域和子域； （2）起始域：沒有父域，只有一個(gè)子域； （3）

10、終止域：沒有子域，只有一個(gè)父域； （4）單一域：只有一個(gè)父域和一個(gè)子域； （5）分叉域：有多個(gè)子域，至多一個(gè)父域； （6）匯合域：有多個(gè)父域，至多一個(gè)子域；    （7）交叉域，有多個(gè)父域和多個(gè)子域。 在圖3.a中，孤立域1表示一個(gè)圖元，即一條線段。在圖3.b中，交叉域7連接起始域2和終止域3，組成一條線段，還表示該線段與另一線段相交于此?？梢钥闯?，單義域不僅為單一完整圖元的獲得提供幾何數(shù)據(jù)，而且也為圖元之間的拓?fù)潢P(guān)系提供線索，單義域鄰接圖比較完整地了表達(dá)圖象的幾何數(shù)據(jù)與拓?fù)潢P(guān)系。  4 圓弧識別 4.1 確定種子圓弧 本文采用假設(shè)驗(yàn)證法從單義

11、域中提取圓弧域，主要思路是，先假設(shè)候選域?yàn)閳A弧域，采用最小二乘法來計(jì)算其幾何定義數(shù)據(jù)（圓心和半徑）8，并計(jì)算平均徑向誤差和最大徑向誤差，如果小于閾值，則判定為圓弧域，作為種子圓弧，以指導(dǎo)圓弧和圓的識別。 在確保計(jì)算精度的前提下，為提高速度，平均抽取五個(gè)游程的中點(diǎn)，如果單義域游程數(shù)小于五，則全部選取?；趶较蛘`差最小，對樣點(diǎn)采用最小二乘法擬合，下面給出計(jì)算公式： 設(shè)給定樣點(diǎn)為，所求圓心為，半徑為，平均徑向誤差為，最大徑向誤差為，則     ， ， ， ， 。 4.2 識別圓弧與圓 在單義域鄰接圖中，從頂點(diǎn)中選取圓弧域，作為種子圓弧，以此為起始點(diǎn)，遍歷得其鄰

12、接域（或鄰接域的鄰接域），如果屬于同一圓，則種子圓弧生長，并繼續(xù)遍歷，否則終止，即可得一弧，如果首末閉合，則得一圓。圓弧及圓的識別算法如下所述： （1）從單義域鄰接圖的頂點(diǎn)集中提取弧形域，作為種子圓弧，設(shè)為當(dāng)前域； （2）如果當(dāng)前域無鄰接域，則轉(zhuǎn)到（4）； （3）取當(dāng)前域的鄰接域i，i從1到n，n為鄰接域總數(shù)     如果鄰接域i與種子圓弧同圓，則種子圓弧生長，并設(shè)鄰接域i為當(dāng)前域，同時(shí)返回（2）；    取鄰接域i的鄰接域j，j從1到m，m為鄰接域i的鄰接域總數(shù) 如果鄰接域j與種子圓弧同圓，則種子圓弧生長，并設(shè)鄰

13、接域j為當(dāng)前域，同時(shí)返回（2）； （4）如果該路徑為回路，則得一圓，否則得一圓弧，計(jì)算其幾何數(shù)據(jù)，獲得矢量表達(dá)。 本算法不僅能夠識別單獨(dú)的圓弧和圓，而且還兼顧圓?。▓A）與線段、圓?。▓A）的相交和相切等情況。在圖4中，原始圖象（a）經(jīng)過圖文分離和粗細(xì)分離，包含圓和多種圓弧，（b）對圖象多義域進(jìn)行分裂，（c）為圖象的單義域表達(dá)，（d）為矢量化圖形。由結(jié)果可以看出，該法識別能力很強(qiáng)，能處理多種圓弧和圓。    5 結(jié)束語 本文介紹了一種基于單義域鄰接圖的圓弧與圓識別算法，與以前方法相比，無需線段逼近和模式匹配，可以直接提取圓弧，對短小圓弧也有較高識別率，對圓弧

14、（圓）與線段、圓?。▓A）的相交和相切等也同樣適用，該方法已被應(yīng)用于我們開發(fā)的工程圖紙掃描圖象識別與理解系統(tǒng)之中，效果較好。但，仍需進(jìn)一步完善，研究各種復(fù)雜情況，以提高識別范圍。單義域鄰接圖的描述模型也可用于線段完整識別及字符識別等方面。 參考文獻(xiàn) 1 vijay nagasamy and noshir a. langrana. engineering drawing processing and vectorization system. computer vision, graphics, and image processing, 1990，49：379-397 2 dov dori, m

15、ember ieee. vector-based arc segmentation in the machine drawing understanding system environment. ieee transactions on pattern and machine intelligence, 1995，17(11)：1057-1068 3 周輝. 掃描工程圖紙識別輸入處理與聯(lián)機(jī)手繪圖形輸入技術(shù)的研究. 大連理工大學(xué)博士論文，1998，3 4 c.-c. han and k.-c. fan. skeleton generation of engineering drawings v

16、ia contour matching. pattern recognition ,1994，27(2): 261-275 5 李偉青，彭群生. 一種基于模式的圓的識別算法. 軟件學(xué)報(bào)，1999，10(2)：129-132 6 s. di zenzo, l. cinque, and s. levialdi. run-based algorithms for binary image analysis and processing. ieee transactions on pattern analysis and machine intelligence, 1996，18(1)：83-89 7

17、 鄭南寧著. 計(jì)算機(jī)視覺與模式識別. 北京：國防工業(yè)出版社，1998，3：160-168 8 吳仲科，焦海星等. 一種線段和圓弧的逼近方法及其在工程圖紙矢量化中的應(yīng)用. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，1998，10(4)：328-332 an algorithm for recognizing circular arcs and circles using primitive region adjacency graph abstract the scanning input and recognition of engineering drawings is a key step in cad

18、, and is to reuse lots of engineering drawings. in study on recognition of scanned image of engineering drawings, the recognition for circular arcs is an important and difficult problem. recent algorithms of recognizing arcs are mainly about approximation with lines. this paper presents an algorithm

19、 for recognizing arcs and circles using primitive regions adjacent graph. the method can directly extract arc. the binary image is encoded with black horizontal runlength. a stripe region consists of correlative runlengths with the same width and topology. the stripe regions then can be segmented as some primitive regions (line and arc). the graph is used to describe geometric