一種基于輪廓線匹配的二維ddp復(fù)原方法_第1頁(yè)
一種基于輪廓線匹配的二維ddp復(fù)原方法_第2頁(yè)
一種基于輪廓線匹配的二維ddp復(fù)原方法_第3頁(yè)
一種基于輪廓線匹配的二維ddp復(fù)原方法_第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)介

一種基于輪廓線匹配的二維ddp復(fù)原方法

在計(jì)算機(jī)視角和模式識(shí)別領(lǐng)域,兩個(gè)物體的比例匹配非常重要。如在一些裝配任務(wù)中,要求機(jī)器人通過(guò)物體的邊緣將其安裝在一起,重疊物體的識(shí)別問(wèn)題,兩個(gè)碎片物體的復(fù)原問(wèn)題等等。由于問(wèn)題的特殊性,物體的輪廓線表示不能用全局參數(shù)進(jìn)行整體描述,即全局特征不能再繼續(xù)使用。例如,重心、面積、總長(zhǎng)度、鏈碼、傅立葉描述符等,只能用輪廓曲線的局部幾何屬性進(jìn)行描述,基于局部幾何屬性的輪廓線一旦給出,識(shí)別和匹配就通過(guò)輪廓線的匹配來(lái)完成。由于這一問(wèn)題的重要性,已進(jìn)行了大量研究。文獻(xiàn)給出了一種嚴(yán)格限制的方法,設(shè)給定兩條曲線,其中一條是另一條的完全子曲線,要求完全匹配且距離平方最小的對(duì)應(yīng)子曲線段,要計(jì)算子曲線的位移和旋轉(zhuǎn)角度。文獻(xiàn)用一系列關(guān)鍵點(diǎn)(拐點(diǎn))來(lái)描述2D物體的形狀,對(duì)于沒有拐點(diǎn)或者曲率不連續(xù)的點(diǎn)不適合。文獻(xiàn)把匹配建立在尋找多邊形邊的相關(guān)性上,這些多邊形是原曲線的逼近。文獻(xiàn)采用了同心圓技術(shù),求交點(diǎn)計(jì)算量大,采樣步長(zhǎng)的選取較難。因此,需要研究簡(jiǎn)單、快速基于匹配的碎片復(fù)原技術(shù)。另外,對(duì)于一個(gè)實(shí)用的碎片物體復(fù)原系統(tǒng)來(lái)說(shuō),也需要一種快速進(jìn)行圖像處理和2D物體形狀復(fù)原算法。本文提出了一種基于局部幾何結(jié)構(gòu)屬性表示的輪廓線方法和基于這一表示的匹配算法,并將這一技術(shù)應(yīng)用在復(fù)原扁平類碎片物體(如字畫碎片)中。對(duì)于二維物體的形狀通過(guò)多邊性逼近,然后選取特征集,在兩個(gè)特征集之間進(jìn)行快速匹配。本文的算法在保證匹配準(zhǔn)確性的同時(shí),大大提高了匹配速度,且碎片物體的復(fù)原效果良好。12基于遺傳算法的范圍范圍模型二維物體的形狀可用輪廓線來(lái)表示,輪廓線可以用多邊形進(jìn)行有效逼近。用多邊形線段來(lái)近似形狀邊緣,是以最小誤差、最小多邊形周長(zhǎng)、最小多邊形內(nèi)部面積或最小多邊形外部面積作為近似準(zhǔn)則。這些誤差度量中最常用的是最大誤差和平方積分誤差。這類方法中最常用的是分裂和合并法,曲線分裂由幾個(gè)線段來(lái)表示,直到誤差達(dá)到可以接受,同時(shí)分裂的線段又可能融合。文獻(xiàn)使用平方和誤差函數(shù)的偏導(dǎo)數(shù)來(lái)引導(dǎo)牛頓法搜索最佳斷點(diǎn),文獻(xiàn)提出了用最大內(nèi)部面積、最小外部面積、面積偏差準(zhǔn)則來(lái)獲取多邊形逼近。文獻(xiàn)擴(kuò)充了文獻(xiàn)的方法,以多邊形的幾何矩和正交矩為模型提出了兩個(gè)構(gòu)造逼近多邊形的算法,目標(biāo)函數(shù)為逼近多邊形和初始輪廓線的矩差最小。文獻(xiàn)提出了基于遺傳算法的多邊形逼近平面數(shù)字曲線方法,逼近多邊形和初始輪廓線間的距離積分方差最小為目標(biāo)函數(shù)。文獻(xiàn)提出了基于遺傳算法的以線段和圓弧為基元的曲線擬和方法,文獻(xiàn)提出了一個(gè)有效的進(jìn)化算法,以多邊形逼近到平面數(shù)字曲線。此外,還有一些方法可以進(jìn)行多邊形逼近,例如連碼、傅立葉變換等。本文對(duì)輸入圖像先進(jìn)行二值化和邊緣抽取,然后對(duì)于獲得的數(shù)字曲線用遺傳算法進(jìn)行多邊形逼近。通過(guò)以上處理,兩個(gè)2D物體碎片就可以用兩個(gè)多邊形來(lái)表示。P1={P1,P2,…,Pn},Q1={Q1,Q2,…,Qm}。為了便于處理,將多邊形頂點(diǎn)按順時(shí)針或逆時(shí)針統(tǒng)一編號(hào)排列。2定義連接點(diǎn)特征集是描述物體形狀的惟一特征,本算法中用到的特征集滿足:①局部性;②位移和旋轉(zhuǎn)變換的不變性;③穩(wěn)定性;④能方便計(jì)算變換矩陣;⑤能快速重構(gòu)物體形狀。從微分幾何可知,對(duì)于光滑曲線的弧長(zhǎng)、曲率、撓率是位移和旋轉(zhuǎn)變換下的不變量,且由曲線惟一性定理知,可以用這3個(gè)不變量重構(gòu)空間曲線,同理,對(duì)于多邊形組成的封閉圖形邊長(zhǎng)、角度是不變量。顯然可以由邊長(zhǎng)和角度重構(gòu)多邊形,即物體的邊界輪廓。因此,在本算法中取多邊性的連接點(diǎn)集為特征集。定義1一個(gè)多邊形定義為一個(gè)點(diǎn)集{Pi}i=0,1,…,n+1,Pi稱為頂點(diǎn),且順序兩點(diǎn)之間線段相連,該線段稱為邊,如果為封閉的,令Pn+1=P0,如圖1所示。定義2連接點(diǎn)定義為頂點(diǎn)和與該頂點(diǎn)相連的兩條邊。如圖2所示。設(shè):li=‖Pi+1-Pi‖,其中‖·‖為向量的模。ni-1=Ρi-1-Ρili-1?ni+1=Ρi+1-Ρilini?1=Pi?1?Pili?1?ni+1=Pi+1?Pili,則記ni-1到ni+1的轉(zhuǎn)角為θi,(i=0,1,…,n),其中θ0為向量Pn-Pn+1與P1-P0的轉(zhuǎn)角,且規(guī)定逆時(shí)針?lè)较驎r(shí)轉(zhuǎn)角為正,順時(shí)針時(shí)為負(fù)。則三元數(shù)組(li-1,θi,li)定義為頂點(diǎn)Pi處的連接點(diǎn),記為Qi。θi,li稱為本質(zhì)參數(shù)。在圖1中閉形式的多邊形定義的連接點(diǎn)為:Q0,Q1,…,Q10,其中Pi與Qi對(duì)應(yīng)。而在圖1中開形式的多邊形定義的連接點(diǎn)為:Q1,Q2,Q3。其中Qi與Pi對(duì)應(yīng),P0與P4點(diǎn)不是連接點(diǎn)。即開形式的多邊形兩端點(diǎn)不是連接點(diǎn)。定義3按照定義2,關(guān)于閉形式的多邊形如圖3特征集定義如下:對(duì)于開形式的多邊形如圖4的特征集定義,只需連接開形式多邊形的首末端點(diǎn),這樣轉(zhuǎn)化開形式的多邊形為閉形式的多邊形,按照閉形式的多邊形的特征集定義。顯然,上述用來(lái)進(jìn)行多邊形匹配的特征集中的特征數(shù)目已達(dá)到了最少且又不失多邊性的幾何和拓?fù)湫再|(zhì)。因此,對(duì)于給定的多邊形由以上定義,惟一確定了特征集,反之,具有相同如上定義的特征集,則確定了相同幾何形狀的多邊形。這些多變形只是位置和朝向不同。即兩個(gè)多邊形之間僅相差一剛體運(yùn)動(dòng),這一運(yùn)動(dòng)由一對(duì)匹配的連接點(diǎn)確定。3圖像匹配算法給定兩個(gè)多邊形C和D,計(jì)算其本質(zhì)參數(shù),則C和D分別用以下特征集表示。ΓC={P1(θ1,l1),P2(θ2,l2),…,Pn(θnln)},ΓD={Q1(φ1,l1),Q2(φ2,l2),…,Qm(φmlm)}。其中:P1,P2,…,Pn;Q1,Q2,…Qm分別為兩個(gè)多邊形的連接點(diǎn)。在理想狀態(tài)下,特征點(diǎn)pi(θi,li)與Qj(φj,lj)匹配成功,就意味著滿足以下兩點(diǎn):①θi=φj?②lglilj=λ(λ①θi=φj?②lglilj=λ(λ為縮放因子)。由于圖像處理方法和噪聲等因素的影響,從圖像中抽取的特征點(diǎn)有一定的誤差。因此,在匹配特征點(diǎn)時(shí),不可能完全相同,應(yīng)當(dāng)在某種誤差閾值范圍內(nèi)就認(rèn)為匹配成功。定義4如圖1所示,如果ΓC和ΓD中的兩個(gè)連接點(diǎn)滿足以下兩個(gè)條件,則稱它們?yōu)橐粋€(gè)匹配點(diǎn)對(duì)(Pi,Qj)。①|(zhì)θi-φj|≤δ,δ為角度誤差閾值;②|lgli-lglj|≤λε,ε為相對(duì)長(zhǎng)度誤差的閾值。根據(jù)定義,ΓC和ΓD中的匹配點(diǎn)對(duì)最多有m×n個(gè),然而其中含有大量的冗長(zhǎng)性。為了適應(yīng)實(shí)用化的要求,縮短多邊形匹配的時(shí)間,本文采用點(diǎn)模式的快速匹配算法。進(jìn)行匹配時(shí),就要比較ΓC,ΓD中連接點(diǎn)Pi與Qj的對(duì)應(yīng)各分量的值,只有對(duì)應(yīng)各分量的值的絕對(duì)值之差在閾值的范圍內(nèi)時(shí),對(duì)應(yīng)的兩個(gè)連接點(diǎn)才能匹配上,因此,對(duì)于Pi與Qj只要有一個(gè)對(duì)應(yīng)分量的值不相等,則匹配失敗。關(guān)于多邊形匹配已有很多算法,本文給出的算法如下:對(duì)于給定的兩個(gè)多邊形的連接點(diǎn)P1,P2,…Pn;Q1,Q2,…,Qm將按角度的大小以升序的次序構(gòu)成兩個(gè)有序表(自然也可以按照連接點(diǎn)對(duì)應(yīng)邊的長(zhǎng)度進(jìn)行排序)。假設(shè)排序后的兩個(gè)有序表如下Γθ={θi1,θin,…,θin};Γφ={φj1,φjn,…,φjm}。設(shè)θi1和φjm絕對(duì)值之差在閾值的范圍內(nèi),這時(shí)檢查對(duì)應(yīng)的第2個(gè)分量,如果絕對(duì)值之差仍在閾值的范圍內(nèi),則該點(diǎn)匹配成功,否則不匹配。在匹配成功的情況下,自然下一個(gè)θil+1只可能與φjk+1及以后的一定范圍內(nèi)的某個(gè)點(diǎn)才可能匹配成功。這樣就限制了匹配時(shí)搜索的范圍,如果角度誤差閾值δ=max{maxl(θil+1-θi1),maxk(φjk+1-φjk)}?l=0,2,?n-1,k=0,2???m-1。對(duì)于Γθ和Γφ中的各個(gè)角度有可能匹配的范圍是一個(gè)常數(shù)。因此,避免了盲目的特征點(diǎn)的比較。4算法的實(shí)現(xiàn)4.1輸入輸入平面碎片物體圖像,進(jìn)行二值化、提取輪廓曲線。用多邊形逼近,得到兩個(gè)特征集ΓC及ΓD。4.2特征集中匹配匹配的連接點(diǎn)對(duì)。step1用定義2中的公式計(jì)算轉(zhuǎn)角和邊長(zhǎng),得到兩個(gè)特征集;step2將特征集中的第一分量角度按升序排序;step3選取第一個(gè)匹配點(diǎn)對(duì);step4在匹配點(diǎn)對(duì)的后面范圍內(nèi)繼續(xù)進(jìn)行匹配;step5輸出連續(xù)的匹配點(diǎn)對(duì);Step6計(jì)算變換矩陣;Step7復(fù)原物體顯示。5實(shí)驗(yàn)2:雙邊協(xié)議下的多模型表面噪聲為了驗(yàn)證上述所給方法的有效性,用模擬數(shù)據(jù)和實(shí)際的圖像數(shù)據(jù)進(jìn)行了試驗(yàn)。下面是兩個(gè)具有代表性的試驗(yàn)和結(jié)果。實(shí)驗(yàn)1對(duì)于上面給出的匹配算法,使用隨機(jī)發(fā)生的圖像數(shù)據(jù)作了模擬測(cè)試。首先隨機(jī)的產(chǎn)生n個(gè)二維點(diǎn),組成一個(gè)封閉的多邊形。然后將這n個(gè)點(diǎn)按照下列公式進(jìn)行旋轉(zhuǎn)和縮放變換,并加進(jìn)一定的噪聲,作為第二個(gè)多邊形。{x′=λ(xcosα-ysinα)+μ?y′=λ(xsinα+ycosα)+μ。其中:λ縮放因子;α為旋轉(zhuǎn)角度;μ為噪聲。試驗(yàn)中的具體參數(shù)為α=90,λ=1,ε=0.1,δ=0.05,μ=0.025。算法輸出對(duì)應(yīng)匹配的連接點(diǎn)對(duì)為(P4,Q0);(P5,Q1);(P6,Q2);(P7,Q3);(P8,Q4);(P9,Q5);(P10Q6);(P0,Q7);(P1,Q8);(P2,Q9);(P3;Q1

溫馨提示

  • 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ù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 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)論