基于形態(tài)圖表示的三維物體識別算法

1、第23卷第2期2003年2月文章編號:1001-9081(2003)02-0009-04計算機應(yīng)用ComputerApplicationsVol.23,No.2Feb.,2003基于形態(tài)圖表示的三維物體識別算法曾接賢,陳 震,儲 ,黎 明(1.南昌航空工業(yè)學(xué)院土木建筑系,江西南昌330034;2.南昌航空工業(yè)學(xué)院測試技術(shù)與控制研究中心,江西南昌330034)摘 要:基于形態(tài)圖表示的三維物體識別的基本思路是:首先建立待識別物體的模型庫,找出模型集中所有模型物體的形態(tài)圖和特征視圖,并提取出它們的拓?fù)浣Y(jié)構(gòu)信息和幾何信息;其次對物體真實圖像作輪廓提取和邊界跟蹤,得到二維圖像的線架圖,同時提取出它的拓?fù)?/p>

2、結(jié)構(gòu)信息和幾何信息;最后將物體圖像的拓?fù)浣Y(jié)構(gòu)信息和幾何信息與模型庫中模型物體的拓?fù)浣Y(jié)構(gòu)信息和幾何信息匹配,從而達(dá)到識別的目的。文中提出了在生成線圖鏈碼時提取其拓?fù)浣Y(jié)構(gòu)信息和幾何信息的方法,由拓?fù)浣Y(jié)構(gòu)信息和幾何信息構(gòu)造特征矩陣的方法,以及識別過程中特征矩陣的匹配算法。關(guān)鍵詞:形態(tài)圖;特征視圖;鏈碼;特征矩陣;匹配中圖分類號:TP391.41 文獻(xiàn)標(biāo)識碼:A22RecognitionAlgorithmicBasedonAspectGraphfor3DObjectsZENGJie-xian1,CHENZhen2,CHUJun1,LIMing2(1.DepartmentofArchitecturean

3、dCivil,NanchangInstituteofAeronauticalTechnology,JiangxiNanchang330034,China;2.DepartmentofTest&ControlEngineering,NanchangInstituteofAeronauticalTechnology,JiangxiNanchang330034,China)Abstract:Thefundamentprinciplesof3Dobjectsrecognitionbasedontheaspectgraphisasfollows:Firstofall,establishthemo

4、delbaseofobjectstoberecognizedtofindalltheaspectgraphsandfeatureviewsinthemodelcollectionandextracttheirtopologyinformationandgeometryinformation.Second,extracttheedgeoftheobjectimageandboundarytrackingtogetthe2Dlinedrawingandextractthetopologyinformationandgeometryinformationofthem.Atlast,matchthei

5、nformationoftopologyandgeometryoftheobjectimageswiththatofthemodelobjectsinthemodelbasetorecognize.Itispresentedinthiscontextthewaytoextracttopologyinformationandgeometryinformationwhenformingthechaincodesoflinedrawing,thewayofconstructingcharacteristicmatrixbytopologyinformationandgeometryinformati

6、onandthematchingalgorithmicofcharacteristicmatrixintherecognizingprocess.Keywords:aspectgraph;featureview;chaincode;characteristicmatrix;matching1 引言在基于模型的三維物體識別中,一般要通過兩個階段的處理,以完成圖像中3D物體的識別和定位1,即首先通過傳感器獲取的場景輸入數(shù)據(jù)來得到場景的表達(dá);然后將它與數(shù)據(jù)庫中存儲的物體(模型物)表達(dá)相匹配。具體來說,基于模型的三維物體識別系統(tǒng)必須解決如下三個問題:(1)二維圖像的處理與物體描述;(2)三維物體模型表

7、達(dá)(構(gòu)造)方法;(3)從輸入數(shù)據(jù)獲得的物體描述和物體模型描述之間的匹配方法。其中,三維物體模型表達(dá)(構(gòu)造)方法,既決定了二維圖像的處理方法和物體描述;也決定著從輸入數(shù)據(jù)獲得的物體描述和物體模型描述之間的匹配策略。本文提出一種基于形態(tài)圖表達(dá)的三維物體識別算法。形態(tài)圖表達(dá)三維物體是一種以視點為中心的表達(dá)方法,它列舉了一個物體所有可能的/定性0形象,即使用最少的二維投影線圖(特征視圖)表達(dá)一個完整的三維物體,使三維物體識別轉(zhuǎn)化為2D與2D的匹配,這是一個相對比較容易的識別匹配策略。圖4和圖5是采用形態(tài)圖方法所得到的兩個物體模型的部分特征視圖?；谛螒B(tài)圖表達(dá)的三維物體識別的基本思路是:首先建立待識別物

8、體的模型庫,找出模型集中所有模型物體的形態(tài)圖和特征視圖,提取出它們的拓?fù)浣Y(jié)構(gòu)信息和幾何信息,并且存儲于特征矩陣;其次將攝像機拍攝到的二維實時圖像作輪廓提取和邊界跟蹤得到二維圖像的線圖,同樣,也提取出它們的拓?fù)浣Y(jié)構(gòu)信息和幾何信息,并且存儲于特征矩陣;最后將圖像物體的特征矩陣與模型庫中模型物體的特征矩陣匹配,從而達(dá)到識別的目的。整個識別過程如圖1所示。本文主要研究二維線圖在生成鏈碼時,提取其拓?fù)浣Y(jié)構(gòu)信息和幾何結(jié)構(gòu)信息的方法,特征矩陣構(gòu)造方法,以及特征矩陣匹配方法。5收稿日期:2002-11-12(修改稿)基金項目:國家自然科學(xué)基金資助項目(項目批準(zhǔn)號:60275037);江西省測試技術(shù)與控制研究中

9、心開放基金資助項目作者簡介:曾接賢(1958-)副教授,碩士,主要研究方向:工程圖學(xué)、計算機圖形學(xué)、計算機視覺; 陳震(1969-),講師,博士研究生,主要研究方向:計算機視覺、圖形圖像處理、人工智能、模式識別; 儲-(1967-),講師,博士研究生,主要研究方向:工程圖學(xué)、計算機視覺、圖像處理; 黎明(1965-),教授,博士,:遺傳算法.10 計算機應(yīng)用2003年圖1 基于形態(tài)圖方法的三維物體識別過程線圖的鏈碼表示法點的坐標(biāo),以及用來確定圍繞邊界路徑走向的編碼序列。由鏈碼的特點可見,鏈碼比較適合用于表達(dá)二維線圖。模型物體的形態(tài)圖與特征視圖是二維線圖,物體圖像經(jīng)過輪廓提取和邊界跟蹤得到的也是

10、二維線圖,因此,它們可以表示成鏈碼7,并以鏈碼文件記錄線圖的信息。3 拓?fù)浣Y(jié)構(gòu)信息和幾何信息的提取圖2 鏈碼方向代碼鏈碼是從物體邊界上任意選取的某個點(x,y)的坐標(biāo)開始的,這個起始點有8個鄰接點,其中至少有一個是邊界點。邊界鏈碼規(guī)定了從當(dāng)前邊界點到下一個邊界點必須采用的方向。由于有8種可能的方向,因此可以將它們從0到7編號。圖2顯示了一種8個方向的編碼方案。因此鏈碼包含了起始線圖主要包含兩個方面的信息,一是拓?fù)浣Y(jié)構(gòu)信息,它反映線圖的形貌和結(jié)構(gòu),這方面的信息有:頂點個數(shù)、線段(邊)數(shù)、閉環(huán)數(shù)以及它們之間的連接關(guān)系。二是幾何信息,它反映線圖中各線段的幾何性質(zhì),如是直線段還是曲線段。而鏈碼文件則記

11、錄了線圖中各線段的鏈碼,每條線段的鏈碼是一串?dāng)?shù)字,它記錄了起始點坐標(biāo)和線段的走向。圖3是線圖及其頂點和線段的編號,它的鏈碼如表1。表1線圖的鏈碼3.1 拓?fù)浣Y(jié)構(gòu)信息的提取在對整個線圖進行鏈碼編碼時,作如下約定:(1)以整個線圖x,y坐標(biāo)值最小的頂點為起始點;(2)當(dāng)某個象素點的鄰域有一個以上(不包括追入該點的象素)象素時,則該點為結(jié)點,用矩陣Ann來記錄結(jié)點信息,Ann叫結(jié)點特征矩陣。其中n表示線圖的結(jié)點數(shù),矩陣的行、列號為線圖結(jié)點序號,每一行的元素值表示該結(jié)點與其余結(jié)點的關(guān)系,即有線段相連的結(jié)點取值為1,無線段相連的結(jié)點取值為0;(3)用矩陣Bmm記錄有關(guān)線段的信息,Bmm叫線段特征矩陣,其

12、中m表示線圖的線段數(shù),矩陣的行、列號為線圖的線段序號,每一行的元素值表示該線段與其余線段的關(guān)系,即與該線段相連圖3 線圖及其編號2003年曾接賢等:基于形態(tài)圖表示的三維物體識別算法 11的線段取值為1,與該線段不相連的線段取值為0;(4)對于孤立的封閉環(huán),若是多邊形環(huán),仍以該多邊形環(huán)x,y坐標(biāo)值最小的頂點為起始點;若是封閉曲線組成的環(huán)(如圖3中圓柱孔的端面圓),則插入兩個結(jié)點,即取x坐標(biāo)值最小和最大的兩個象素點為插入的兩個結(jié)點;并將它們也記入矩陣。插入結(jié)點后所生成的線段也記入矩陣Bmm。圖3的結(jié)點特征矩陣和線段特征矩陣為:010010011001000000000000000111000000

13、0010011001000000001110000000000000001001100100110000000001000000000000100110011100000010000000010110100011010000000001110111100000000000000000000000000000000000000000000000001(2)0110010001A=00000010100000001001100100000000000000001000100110010000000000000000000010011001010000110000000001001100000000

14、00000000000000000000111212100100000000(1)B=001010000011010000000000000000116163.2 幾何信息的提取4.2 物體圖像信息的存儲結(jié)構(gòu)線圖的幾何信息主要有:組成線圖各線段的類型和度量攝像機拍攝到的物體圖像經(jīng)輪廓提取和邊界跟蹤,在處尺度,基于形態(tài)圖方法的三維物體識別不考慮線圖的度量尺度問題,這里主要考慮線段的彎曲程度。根據(jù)線段鏈碼的特點,鏈碼中連續(xù)相同的數(shù)字,表明線段的方向沒有發(fā)生變化,故只保留一個。這樣就可將線段鏈碼作一簡化,并稱其為線段的特征鏈碼,如表1。線段的特征鏈碼記錄了線段彎曲程度的信息,識別時可作為一個匹配量。

15、線段的特征鏈碼用矩陣Cmp來記錄,m表示線段數(shù),p表示鏈碼的長度。矩陣中每一行的數(shù)字表示線段的特征鏈碼,用-1作為鏈碼終止標(biāo)志符。該矩陣可用變長度的二維數(shù)組存儲。理成鏈碼的同時,也可得到它的結(jié)點特征矩陣WA、線段特征矩陣WB和線段的特征鏈碼征矩陣WC。該三矩陣均可用數(shù)組來存儲。4.3 匹配為簡化匹配過程,提高匹配效率,采用層次分類法(Hierarchicalclassificationmethod9)進行匹配。匹配時把最簡單的信息放在最上層,最復(fù)雜的信息放在最下層。具體匹配過程如下:Step1:尋找結(jié)點數(shù)相同的特征視圖,設(shè)WA的階數(shù)是n(物體圖像的結(jié)點數(shù)),在MAij中尋找出與n值相同的元素,

16、并記錄下該元素所在的行i和列j號,存入G=(i,j),ContinueStep2。若在MAij中尋找不到與n相同的元素,則不能識別該物體,結(jié)束。Step2:設(shè)WB的階數(shù)是m(物體圖像的線段數(shù)),根據(jù)Step1得到的i和j,在MBij找出i行j列的元素與m進行比較,若相同,ContinueStep3。否則返回Step1。Step3:根據(jù)Step1得到的i和j,找出結(jié)點特征矩陣Aij與WA進行比較。若相同,ContinueStep4,否則返回Step1。Aij與WA的比較,采用按行比較,即依次取出WA的行向量與Aij中的每個行向量進行比較。若取出WA的行向量與Aij中的某一行向量相同,則記錄下該行

17、號,再取WA中的下一行向量與Aij中除去已比較相同的其它行向量進行比較,直至WA中的每個行向量都比較完畢,并在Aij中找到了相同的行向量,則WA與Aij相同,否則只要WA中有一個行向量在Aij找不到相同的,則WA與Aij不同。Step4:根據(jù)Step1得到的i和j,找出線段特征矩陣Bij與WB進行比較。若相同,ContinueStep5,否則返回Step1。WB與Bij的比較與Step3中的Aij與WA的比較相同。Step5:根據(jù)Step1得到的i和j,找出線段特征鏈碼特征Cij與WC若相同,調(diào)出i4 匹配算法4.1 模型庫中有關(guān)信息的存儲結(jié)構(gòu)用形態(tài)圖方法找出每個模型物體的一組特征視圖(子集)

18、,并在轉(zhuǎn)換成鏈碼的同時得到它們的結(jié)點特征矩陣、線段特征矩陣和線段的特征鏈碼矩陣。每個模型的特征矩陣構(gòu)成特征矩陣子集,所有模型的特征矩陣子集構(gòu)成模型庫特征矩陣集。用矩陣MAij表示模型庫中各特征視圖的結(jié)點數(shù),其中i=1,2,n(n為模型庫中的模型個數(shù)),j=1,2,m(m為第i個模型的特征視圖個數(shù)),maij的值為第i個模型第j個特征視圖的結(jié)點數(shù),即結(jié)點特征矩陣的階數(shù)。用矩陣MBij表示模型庫中各特征視圖的線段數(shù),其中i=1,2,n(n為模型庫中的模型個數(shù)),j=1,2,m(m為第i個模型的特征視圖個數(shù)),mbij的值為第i個模型第j個特征視圖的線段數(shù),即線段特征矩陣的階數(shù)。用矩陣MCij表示模

19、型庫中各特征視圖的線段數(shù),其中i=1,2,n(n為模型庫中的模型個數(shù)),j=1,2,m(m為第i個模型的特征視圖個數(shù)),mcij的值為第i個模型第j個特征視圖的線段數(shù),即線段鏈碼特征矩陣的行數(shù)。MAij、MBij、MCij和各特征視圖的特征矩陣Aij、Bijij12 計算機應(yīng)用2003年的模型物體作為對識別物體的解釋,識別結(jié)束。否則返回Step1。Cij與WC進行比較時,仍采用Step3中的Aij與WA的比較方法。但是,由于WC中各線段的編碼順序可能與Cij中的不同。因此,需對WC中的每個行向量與Cij中的所有行向量作兩次比較,即第一次按照WC原行向量與Cij的行向量比較,第二次將WC中的行向

20、量每個元素加4,當(dāng)元素的值>8時,減去8,而得到一新的行向量,這新的行向量就是原線段的反向鏈碼,用這新的行向量與Cij中的行向量再作一次比較。兩次比較,只要有一次相同,則認(rèn)為該兩向量相同。即比較幾個二維數(shù)組,是一個既簡單又高效的方法。匹配穩(wěn)健性還與鏈碼生成時的假設(shè)分辨率有密切關(guān)系,當(dāng)鏈碼生成時的假設(shè)分辨率為$x=$y=5個象素,二維線圖中兩個點或兩條線之間的距離小于等于5個象素時,則不能分離出它們的鏈碼。這有可能造成漏識別或錯識別。當(dāng)然,模型庫特征視圖的鏈碼生成與物體真實圖像的鏈碼生成采用相同的假設(shè)分辨率,可大大減小這種情況。參考文獻(xiàn)1 JainAK,FlynnPJ,ed.3DObjec

21、trecognitionsystemsM.Ams-terdamElsevierSciencePublishersBV,1993.2 李慶,周曼麗,柳健.三維物體識別研究進展J.中國圖象圖形學(xué)報,2000,5A(12):985-993.3 曾接賢,高滿屯,李建軍.常見復(fù)雜物體軸測投影視覺事件及其計算J.工程圖學(xué)學(xué)報,1998,31(1):71-78.4 李建軍,高滿屯,曾接賢.復(fù)雜物體透視形態(tài)圖建立J.西北工業(yè)大學(xué)學(xué)報,1999,17(3):444-448.5 吳立德,林應(yīng)強.基于邊過程的區(qū)域圍線追蹤和圍線的樹結(jié)構(gòu)J.計算機學(xué)報,1996,19(6):457-465.6 FreemanH.ARe

22、viewofRelevantProblemsintheProcessingofLine-DrawingDataA.GrasselliA,ed.AutoomaticInterpreta-tionandClassificationofImagesAcademicPressC.NewYork,1969.7 陳震.基于分辨率下形態(tài)圖計算與識別的研究D.西安:西北工業(yè)大學(xué),2000.4,24-49.8 曾接賢,陳震.特征視圖的鏈碼表示法J.南昌航空工業(yè)學(xué)院學(xué)報.2001,15(3):4-6.5 實驗與結(jié)論5.1 實驗選擇了兩種模型物體,用形態(tài)圖方法分別找出它們的特征視圖3,4。圖4是模型1的部分特征視圖(共計44個),圖5是模型2的部分特征視圖(共計74個)。兩個模型的全部特征視圖組成模型庫。用本文的方法求出全部特征視圖的鏈碼和它們的拓?fù)湫畔⑴c幾何信息。圖4 模型1的部分特征視圖9 WangR,FreemanH.Theuseofch