CIMS論文的天地

 

 

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

注意:本論文已在《中國圖像圖形學報》(2000.5(1):70~74)雜志發表,
使用者請注明論文出處

張習文 歐宗瑛
(大連理工大學機械系CAD&CG研究所 大連 116024)

 

摘要CAD推廣和普及的關鍵步驟之一,主要解決已有大量圖紙再利用問題。在工程圖紙掃描圖象識別研究中,圓弧識別是識別算法中的重點和難點。傳統的圓弧識別多是基于線段逼近。本文提出一種基于單義域鄰接圖的圓弧及圓識別算法,可以直接提取圓弧。對二值圖象作水平黑游程編碼,相關游程基于線寬與拓撲的一致性構成條形域,對其中多義域進行分裂得單義域(線段域和圓弧域)。單義域鄰接圖可較好描述圖象的幾何屬性與拓撲關系。單義域具有明顯的形狀意義(線段、圓弧、箭頭等),提高了識別的整體性。圓弧及圓的識別先從鄰接圖頂點中抽取圓弧域,作為種子圓弧,然后從此出發遍歷圖,按照同圓來建立路徑,進行整弧和整圓增長,最終獲得圓弧和圓的幾何表達。實例表明,本算法可以較好地處理圓弧與線段及圓弧的相交與相切,適應性較強、識別率較高。
關鍵詞 工程圖紙,矢量化,圓弧識別,條形域,單義域鄰接圖。

1 引言

圓弧和圓是工程圖形中的重要圖元,已有多種識別算法,可分為兩種:逼近法和直接法。細化方法先跟蹤中心骨架象素得到短小線段,再用來逼近圓弧和圓[1]。正交掃描法(orthogonal zig-zag)是先獲得條,再用中垂線跟蹤(perpendicular bisector tracing)分割圓弧[2]。文獻[3]以梯形域來逼近圓弧和圓。這三種方法都是以線段來逼近圓弧和圓,如果線段過短,會造成數據冗余;如果線段過長,將難以識別短小圓弧,需要后續處理。輪廓匹配法可直接獲得圓弧和圓,但,輪廓獲取及其匹配都很復雜[4]。文獻[5]采用圖段與圓進行模式匹配,確定圓的種子圖段,然后跟蹤其它圖段,最終獲得圓弧和圓的圖形表示。

本文提出一種新的識別方法,以相關游程線寬和拓撲為約束生成條形域,對其中多義域作分裂獲得單義域:線段域和圓弧域,并建立其鄰接圖,選取弧形域,以此為起始點,基于同圓幾何要求,通過深度優先搜索來遍歷圖,完成圓弧和圓識別。下面分為四部分,先介紹條形域構建和多義域分裂,然后給出建立單義域鄰接圖方法,并對整弧和整圓增長算法進行詳細論述,最后對多種圓弧與圓的識別結果作出分析。

2 條形域構建和多義域分裂

2.1 游程分類

在同一線寬的二值圖象中,一個游程唯一屬于單一圖元,所以,對工程圖紙掃描圖象先作圖文分離再作粗細分離[3],然后對同一線寬圖象進行處理。本文采用自上而下和從左到右掃描,定義同一行中連通黑象素為一水平黑游程,并以此對圖象進行編碼。如果當前游程是參考游程的上(或下)一行,且左右至少一端搭接(包括鄰接),則稱兩個游程相關,具有父子(或子父)關系。游程可以根據其父子游程進行分類[6],本文針對工程圖紙掃描圖象特點,分為七類(如圖1所示):

1)孤立游程:沒有父游程和子游程;

2)起始游程:沒有父游程,只有一個子游程;

3)終止游程:沒有子游程,只有一個父游程;

4)單一游程:只有一個父游程和一個子游程;

5)分叉游程:有多個子游程,至多一個父游程;

6)匯合游程:有多個父游程,至多一個子游程;

wpe2.jpg (9811 字節)

7)交叉游程:有多個父游程和多個子游程。

2.2 構建條形域

相關游程基于寬度和拓撲的一致性組合為條形域,具體條件如下:

1)游程相關;

2)首游程不是分叉游程和交叉游程,末游程不是匯合游程和交叉游程;

3)游程寬度沒有較大變化;

4)孤立游程和交叉游程單獨構成條形域。

條件(1)保證條形域的連通性,(2)確保交叉域、匯合域和分叉域的準確建立,(3)是條形域寬度一致性的要求,(4)處理特殊情況。

下面給出條形域構建算法:

1)移游程到新建條形域中,設為當前游程,如果是孤立游程、分叉游程或交叉游程,則轉到(4;

2)取當前游程的子游程,如果與當前條形域游程平均寬度相差較大,則轉到(4),否則,設為當前游程;

3)如果當前游程是單一游程,則加入條形域,并返回(2);如果是分叉游程或終止游程,則加入條形域;

4)完成條形域構建。

2.3 分裂多義域

從幾何意義上講,根據上述方法構建的條形域包括兩種情況,一是表達單一幾何實體,如:線段、圓弧和箭頭等;二是線段與圓弧組合,如折線等。所以,將條形域分為單義域和多義域。一般來講,多義域可看作由線段和圓弧連接而成。因此,對多義域進行分裂,提取線段域和圓弧域。

在這里,多義域是開環的,且單調,相對一般曲線擬合要簡單些,本文采用首尾相連最大距離法來分裂[7]。對多義域,先用一條直線連接首尾游程中點,計算多義域游程中點與直線的最大距離差,并以此點為一分裂點,然后判定所分裂的兩段是否為單義域,如仍為多義域則繼續分裂,一直進行到都是單義域為止,這是一個遞歸的過程。下面給出分裂步驟:

1)輸入條形域,如為單義域,則轉到(5;

2)對多義域以最大距離法分為兩段:域1和域2,輸出分裂點;

3)如果域1(域2)為多義域,則返回(2);

4)對分裂點以其y坐標作從小到大排序;

5)根據分裂點,輸出單義域。

3單義域鄰接圖的建立及其拓撲分類

3.1 建立單義域鄰接圖

多義域分裂后,圖象描述單元變為單義域。但,單義域描述只是表達幾何信息,而單義域之間還有連接關系,表達拓撲信息。如果當前單義域末游程與參考單義域首游程(或當前單義域首游程與參考單義域末游程)相關,則稱兩個單義域相關,具有父子(或子父)關系。采用域鄰接圖(如梯形域和圖段等)可以較好地表達圖象的幾何與拓撲信息,本文采用單義域鄰接圖描述圖象,下面給出建立步驟:

1)加單義域到鄰接圖的頂點表中;

2)取頂點ii1nn為圖的頂點總數,

{

取頂點jj1n

{

如果頂點j是頂點i的父域,則加頂點j到頂點i的父鄰接表,且加頂點j到頂點i的鄰接表;

如果頂點j是頂點i的子域,則加頂點j到頂點i的子鄰接表,且加頂點j到頂點i的鄰接表;

}

}。

wpe3.jpg (24187 字節)

2給出圓的圖表示,頂點1的父鄰接表為空,子鄰接表包含頂點23;頂點2的父鄰接表包含頂點1,子鄰接表包含頂點4;頂點3的父鄰接表包含頂點1,子鄰接表包含頂點4;頂點4的父鄰接表包含頂點23,子鄰接表為空。

3.2 單義域拓撲分類

從單義域鄰接圖中很容易就可獲得某一頂點的鄰接點情況,單義域(頂點)根據其父子域(鄰接點)可以分為七種拓撲類型(如圖3所示):

1)孤立域:沒有父域和子域;

2)起始域:沒有父域,只有一個子域;

3)終止域:沒有子域,只有一個父域;

4)單一域:只有一個父域和一個子域;

5)分叉域:有多個子域,至多一個父域;

6)匯合域:有多個父域,至多一個子域;

wpe4.jpg (9032 字節)

7)交叉域,有多個父域和多個子域。

在圖3.a中,孤立域1表示一個圖元,即一條線段。在圖3.b中,交叉域7連接起始域2和終止域3,組成一條線段,還表示該線段與另一線段相交于此。可以看出,單義域不僅為單一完整圖元的獲得提供幾何數據,而且也為圖元之間的拓撲關系提供線索,單義域鄰接圖比較完整地了表達圖象的幾何數據與拓撲關系。

4 圓弧識別

4.1 確定種子圓弧

本文采用假設驗證法從單義域中提取圓弧域,主要思路是,先假設候選域為圓弧域,采用最小二乘法來計算其幾何定義數據(圓心和半徑)[8],并計算平均徑向誤差和最大徑向誤差,如果小于閾值,則判定為圓弧域,作為種子圓弧,以指導圓弧和圓的識別。

在確保計算精度的前提下,為提高速度,平均抽取五個游程的中點,如果單義域游程數小于五,則全部選取。基于徑向誤差最小,對樣點采用最小二乘法擬合,下面給出計算公式:

設給定樣點為,所求圓心為,半徑為,平均徑向誤差為,最大徑向誤差為,則

 

4.2 識別圓弧與圓

在單義域鄰接圖中,從頂點中選取圓弧域,作為種子圓弧,以此為起始點,遍歷得其鄰接域(或鄰接域的鄰接域),如果屬于同一圓,則種子圓弧生長,并繼續遍歷,否則終止,即可得一弧,如果首末閉合,則得一圓。圓弧及圓的識別算法如下所述:

1)從單義域鄰接圖的頂點集中提取弧形域,作為種子圓弧,設為當前域;

2)如果當前域無鄰接域,則轉到(4);

3)取當前域的鄰接域ii1nn為鄰接域總數

{

如果鄰接域i與種子圓弧同圓,則種子圓弧生長,并設鄰接域i為當前域,同時返回(2);

取鄰接域i的鄰接域jj1mm為鄰接域i的鄰接域總數

{

如果鄰接域j與種子圓弧同圓,則種子圓弧生長,并設鄰接域j為當前域,同時返回(2);

}

}

4)如果該路徑為回路,則得一圓,否則得一圓弧,計算其幾何數據,獲得矢量表達。

本算法不僅能夠識別單獨的圓弧和圓,而且還兼顧圓弧(圓)與線段、圓弧(圓)的相交和相切等情況。在圖4中,原始圖象(a)經過圖文分離和粗細分離,包含圓和多種圓弧,(b)對圖象多義域進行分裂,(c)為圖象的單義域表達,(d)為矢量化圖形。由結果可以看出,該法識別能力很強,能處理多種圓弧和圓。

wpe5.jpg (22281 字節)

5 結束語

本文介紹了一種基于單義域鄰接圖的圓弧與圓識別算法,與以前方法相比,無需線段逼近和模式匹配,可以直接提取圓弧,對短小圓弧也有較高識別率,對圓弧(圓)與線段、圓弧(圓)的相交和相切等也同樣適用,該方法已被應用于我們開發的工程圖紙掃描圖象識別與理解系統之中,效果較好。但,仍需進一步完善,研究各種復雜情況,以提高識別范圍。單義域鄰接圖的描述模型也可用于線段完整識別及字符識別等方面。

 

參考文獻

[1] Vijay Nagasamy and Noshir A. Langrana. Engineering Drawing Processing and Vectorization System. Computer Vision, Graphics, and Image Processing, 199049379-397

[2] Dov Dori, Member 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] 周輝. 掃描工程圖紙識別輸入處理與聯機手繪圖形輸入技術的研究. 大連理工大學博士論文,19983

[4] C.-C. Han and K.-C. Fan. Skeleton Generation of Engineering Drawings via Contour Matching. Pattern Recognition ,1994,27(2): 261-275

[5] 李偉青,彭群生. 一種基于模式的圓的識別算法. 軟件學報,199910(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, 199618(1)83-89

[7] 鄭南寧著. 計算機視覺與模式識別. 北京:國防工業出版社,1998,3:160-168

[8] 吳仲科,焦海星等. 一種線段和圓弧的逼近方法及其在工程圖紙矢量化中的應用. 計算機輔助設計與圖形學學報,1998,10(4):328-332

 

An Algorithm for Recognizing Circular Arcs and Circles Using Primitive Region Adjacency Graph

Zhang Xiwen ,Ou Zongying
(CAD&CG Institute, Dalian University of Technology, Dalian 116024)

Abstract The scanning input and recognition of engineering drawings is a key step in CAD, 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 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 geometrical property and topological constraint. The primitive region supplies shape information (line, arc, arrow etc) improving integrality of recognition. After extraction of the arc region from regions, the seed for an arc is obtained. By traversals for the graph, the seed arc grows by constrains for the same circle. Some applications to recognize arcs and circles are finally provided, which show that the algorithm is effective and robust, can solve well intersection and tangency of between a arc and a line or a arc.
Key words engineering drawings, vectorization, recognition for circular arc, stripe region, Primitive Region Adjacency Graph

作者簡介:

張習文,1971年生,博士生,研究方向為模式識別和圖紙理解。

歐宗瑛,1936年生,教授,博士生導師,主要從事智能CAD、圖象理解、人工智能、分形和小波等研究。

 

 


作者點評:

 

 

歡迎您參加討論,發表您對此論文及其研究領域的看法!
(請在發言時在標題中使用所點評的論文的題目或研究方向,這樣方便大家瀏覽!)

返回首頁 | CIMS論文 | 并行工程 | 虛擬制造 | 敏捷制造 | 其他論文 | 項目開發 | 學術資源 | 站內全文搜索 | 免費論文網站大全 |

line.gif (4535 字節)

為了更好的為大家服務,歡迎您參加本站的投票調查

>>>>參加更多投票調查請點擊!

本站永久域名:http://www.sqvswk.live歡迎訪問

注意:本站內容未經書面允許不得轉載

All rights reserved, all contents copyright 2000-2019
本站自2000年3月總網頁訪問量為
pk10开奖记录直播