基于單義域鄰接圖的圓弧與圓識(shí)別_第1頁(yè)
基于單義域鄰接圖的圓弧與圓識(shí)別_第2頁(yè)
基于單義域鄰接圖的圓弧與圓識(shí)別_第3頁(yè)
基于單義域鄰接圖的圓弧與圓識(shí)別_第4頁(yè)
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

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

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

4、。 2 條形域構(gòu)建和多義域分裂 2.1 游程分類(lèi) 在同一線寬的二值圖象中,一個(gè)游程唯一屬于單一圖元,所以,對(duì)工程圖紙掃描圖象先作圖文分離再作粗細(xì)分離3,然后對(duì)同一線寬圖象進(jìn)行處理。本文采用自上而下和從左到右掃描,定義同一行中連通黑象素為一水平黑游程,并以此對(duì)圖象進(jìn)行編碼。如果當(dāng)前游程是參考游程的上(或下)一行,且左右至少一端搭接(包括鄰接),則稱兩個(gè)游程相關(guān),具有父子(或子父)關(guān)系。游程可以根據(jù)其父子游程進(jìn)行分類(lèi)6,本文針對(duì)工程圖紙掃描圖象特點(diǎn),分為七類(lèi)(如圖1所示): (1)孤立游程:沒(méi)有父游程和子游程; (2)起始游程:沒(méi)有父游程,只有一個(gè)子游程; (3)終止游程:沒(méi)有子游程,只有一個(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)游程寬度沒(méi)有較大變化; (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í)體,如:線段、圓弧和箭頭等;二是線段與圓弧組合,如折線等。所以,將條形域分為單義域和多義域。一般來(lái)講,多義域可看作由線段和圓弧連接而成。因此,對(duì)多義域進(jìn)行分裂,

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

8、 3.1 建立單義域鄰接圖 多義域分裂后,圖象描述單元變?yōu)閱瘟x域。但,單義域描述只是表達(dá)幾何信息,而單義域之間還有連接關(guān)系,表達(dá)拓?fù)湫畔?。如果?dāng)前單義域末游程與參考單義域首游程(或當(dāng)前單義域首游程與參考單義域末游程)相關(guān),則稱兩個(gè)單義域相關(guān),具有父子(或子父)關(guān)系。采用域鄰接圖(如梯形域和圖段等)可以較好地表達(dá)圖象的幾何與拓?fù)湫畔?,本文采用單義域鄰接圖描述圖象,下面給出建立步驟: (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ù)浞诸?lèi) 從單義域鄰接圖中很容易就可獲得某一頂點(diǎn)的鄰接點(diǎn)情況,單義域(頂點(diǎn))根據(jù)其父子域(鄰接點(diǎn))可以分為七種拓?fù)漕?lèi)型(如圖3所示): (1)孤立域:沒(méi)有父域和子域; (2)起始域:沒(méi)有父域,只有一個(gè)子域; (3)

10、終止域:沒(méi)有子域,只有一個(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 圓弧識(shí)別 4.1 確定種子圓弧 本文采用假設(shè)驗(yàn)證法從單義

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

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

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

14、(圓)與線段、圓弧(圓)的相交和相切等也同樣適用,該方法已被應(yīng)用于我們開(kāi)發(fā)的工程圖紙掃描圖象識(shí)別與理解系統(tǒng)之中,效果較好。但,仍需進(jìn)一步完善,研究各種復(fù)雜情況,以提高識(shí)別范圍。單義域鄰接圖的描述模型也可用于線段完整識(shí)別及字符識(shí)別等方面。 參考文獻(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 周輝. 掃描工程圖紙識(shí)別輸入處理與聯(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 李偉青,彭群生. 一種基于模式的圓的識(shí)別算法. 軟件學(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ī)視覺(jué)與模式識(shí)別. 北京:國(guó)防工業(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 geometrica

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論