一種基于特征集和輪廓線的3d曲線形狀復(fù)原方法

一種基于特征集和輪廓線的3d曲線形狀復(fù)原方法

物體場(chǎng)的匹配是機(jī)械視覺(jué)研究的一個(gè)重要課題。這個(gè)問(wèn)題包括兩個(gè)方面的問(wèn)題。利用該表達(dá)，物體的輪廓的表達(dá)與基于該表達(dá)的物體的輪廓的匹配是一致的。由于這一問(wèn)題的復(fù)雜性和應(yīng)用的廣泛性,許多學(xué)者做了大量的研究:文獻(xiàn)在研究三維物體識(shí)別時(shí),提出了一種用物體特征曲線識(shí)別的方法,物體特征曲線用B-樣條表示和進(jìn)行匹配,特征集為曲率和撓率;文獻(xiàn)在研究二維物體的識(shí)別時(shí),提出了用二維物體的輪廓線進(jìn)行,輪廓線用B-樣條表示和匹配;文獻(xiàn)用邊的特征研究3D物體的識(shí)別;文獻(xiàn)提出了基于高斯曲率的曲面點(diǎn)分類算法進(jìn)行曲面匹配;文獻(xiàn)提出用一般曲線進(jìn)行3D物體識(shí)別。在本文中假定考慮的物體碎片是沒(méi)有厚度的,因此可以將其表示成三維歐幾里德空間中的曲面片,這樣確定兩個(gè)曲面是否相拼接,就通過(guò)檢測(cè)他們的輪廓線中是否有匹配的曲線段,也就是檢測(cè)是否有共享的碎裂線。因此,可以將碎片的拼接重構(gòu)問(wèn)題轉(zhuǎn)化為曲線匹配問(wèn)題。三維物體輪廓線的表示方法有很多,例如,傅立葉描述、鏈碼、多項(xiàng)式逼近、矩方法、參數(shù)代數(shù)曲線、中軸變換、曲率不變、隱多項(xiàng)式函數(shù)、邊界多項(xiàng)式、B-樣條等。B-樣條方法是最有效的方法,因?yàn)樗辛己玫男再|(zhì)如惟一性有界性連續(xù)性局部控制性仿射變換不變性等。B-樣條方法在計(jì)算機(jī)輔助設(shè)計(jì)領(lǐng)域應(yīng)用廣泛,但在模式識(shí)別領(lǐng)域很少應(yīng)用。本文用B-樣條表示物體的形狀,研究基于這一表示的物體形狀的匹配和運(yùn)動(dòng)計(jì)算,并給出在物體形狀復(fù)原中的應(yīng)用。1點(diǎn)點(diǎn)數(shù)據(jù)點(diǎn)設(shè)給定m個(gè)數(shù)據(jù)點(diǎn),目標(biāo)是構(gòu)造B-樣條曲線擬合到這些數(shù)據(jù)點(diǎn)。常用的方法有插值和逼近,由于逼近方法需要較少的參數(shù),且對(duì)噪聲具有彈性,因此本文采用B-樣條曲線在滿足一定誤差的條件下逼近到數(shù)據(jù)點(diǎn)。1.1率等不變量,不同分辨率的曲線本文在匹配中用到光滑空間曲線的弧長(zhǎng)、曲率、撓率等不變量,而曲率和撓率本質(zhì)上是曲線的二階和三階導(dǎo)數(shù)。因此,考慮到基于撓率匹配的穩(wěn)定性,從而選擇B-樣條曲線的階數(shù)為5階(次數(shù)為4)。1.2線性二乘擬合用B樣條逼近數(shù)據(jù)點(diǎn)時(shí),控制頂點(diǎn)越少,曲線越光滑;控制頂點(diǎn)越多,曲線越接近原始數(shù)據(jù)點(diǎn),光滑性就越差。我們希望在滿足精度要求的條件下,用盡量少的控制頂點(diǎn)因此樣條曲線逼近的方法是迭代進(jìn)行的。其步驟如下:(1)開(kāi)始用足夠少的控制頂點(diǎn);(2)用全局逼近方法到數(shù)據(jù)點(diǎn);(3)檢查逼近精度;(4)如果精度小于給定的值,結(jié)束。否則,返回(1)并用更多控制頂點(diǎn)進(jìn)行逼近。迭代進(jìn)行的核心工作是在滿足精度要求的條件下,給出控制頂點(diǎn)數(shù)目n。下面用線性二乘技術(shù)進(jìn)行逼近以確定控制頂點(diǎn)數(shù)目。設(shè)p(=5)≥1,n≥p和數(shù)據(jù)點(diǎn)為Q0,…,Qm(m>n)是給定的,構(gòu)造p階的非有理B樣條曲線滿足條件Q0=C(0),Qm=C(1)。(1){uk}是預(yù)先計(jì)算的參數(shù)值。強(qiáng)調(diào)曲線不全部通過(guò)數(shù)據(jù)點(diǎn)Qk,且C(uk)不是最接近Qk的點(diǎn)。f是n-1個(gè)變量P1,P2,…,Pn-1的實(shí)值函數(shù)?，F(xiàn)在應(yīng)用最小二乘法進(jìn)行逼近,為了使得f最小,令f關(guān)于n-1個(gè)變量P1,P2,…,Pn-1的導(dǎo)數(shù)為零。第l個(gè)導(dǎo)數(shù)為上式是一個(gè)f關(guān)于n-1個(gè)變量P1,P2,…,Pn-1的線性方程組。為了求解上述方程組,需要確定節(jié)點(diǎn)向量U={u0,…,ur}和參數(shù){uk}的值。{uk}用弦長(zhǎng)參數(shù)化方法確定節(jié)點(diǎn)的設(shè)置應(yīng)該表現(xiàn)參數(shù)的性質(zhì)。需要的節(jié)點(diǎn)數(shù)為:n+p+2,其中n-p個(gè)內(nèi)節(jié)點(diǎn),n-p+1個(gè)節(jié)點(diǎn)區(qū)間。令上式方程的節(jié)點(diǎn)設(shè)置方法除端點(diǎn)以外,每一個(gè)節(jié)點(diǎn)生成的區(qū)間至少包含了一個(gè)參數(shù)uk,且保證了方程組的系數(shù)矩陣是正定的,可用高斯消元法求解。1.3初始點(diǎn)選擇應(yīng)用曲線逼近到數(shù)據(jù)點(diǎn)的目標(biāo)函數(shù)為為了計(jì)算Qk到C(u)的最短距離,即點(diǎn)Qk向曲線C(u)作正投影,用牛頓迭代法解決這一問(wèn)題。記通過(guò)參數(shù)ui得到的第i次牛頓迭代式為目標(biāo)檢測(cè)按以下步驟進(jìn)行:1)點(diǎn)在曲線上的檢測(cè)C(ui)-Qk≤ε1,ε1為距離閾值;2)角度檢測(cè),ε2為測(cè)量角度閾值,如果上式中有一個(gè)條件不滿足,新的參數(shù)值ui+1通過(guò)迭代公式得到,并檢查以下兩步;3)保證參數(shù)值位于[a,b]區(qū)間內(nèi)如果曲線是閉的,當(dāng)ui+1<a,ui+1=b-(aui+1),當(dāng)ui+1>b,ui+1=a+(ui+1-b),如果曲線是開(kāi)的,當(dāng)ui+1<a,ui+1=a,當(dāng)ui+1>b,ui+1=b;4)新的參數(shù)值不改變一些特殊點(diǎn)的性質(zhì),如曲線的端點(diǎn)如果上式中1),2)滿足或者4)滿足,則迭代結(jié)束,對(duì)應(yīng)于Qk點(diǎn)的正投影點(diǎn)的參數(shù)就求得。利用牛頓迭代法進(jìn)行迭代的過(guò)程中需要用到初始點(diǎn),初始點(diǎn)的選擇影響到迭代的收斂速度。我們選擇初始參數(shù)為uk。1.4曲線上的投影點(diǎn)對(duì)比由于空間曲線用參數(shù)方程表示不是惟一的,不同的參數(shù)化就得到不同的參數(shù)方程。因此,為了使后續(xù)匹配能方便地進(jìn)行,需要進(jìn)行重新參數(shù)化。上述構(gòu)造的逼近曲線,有些數(shù)據(jù)點(diǎn)在曲線上,有些不在曲線上,通過(guò)上述正投影,我們就求得了每一個(gè)數(shù)據(jù)點(diǎn)在曲線上的投影點(diǎn),位于曲線上的投影點(diǎn)之間的弧長(zhǎng)的累加就是曲線的長(zhǎng)度,并且對(duì)于兩條曲線上的投影點(diǎn)按照相對(duì)弧長(zhǎng)相等的原則進(jìn)行重新排序。具體如下:設(shè)C(s)表示以弧長(zhǎng)s為參數(shù)的逼近到{Qk},k=1,2…,m,的B-樣條曲線,Qk在曲線上投影點(diǎn)之的距離,記為l1,…,lm-1,總弧長(zhǎng)為,l0=則參數(shù)重新選取為2d空間滑動(dòng)曲線的理想特征由微分幾何可知,弧長(zhǎng)、曲率、撓率是空間光滑曲線剛體運(yùn)動(dòng)的不變量,既具有局部性,又具有穩(wěn)定性,還可以通過(guò)這些量重構(gòu)曲線。因此,曲率和撓率是表示曲線的理想特征。假設(shè)我們得到的3D空間的光滑曲線為:C(s)=(x(s),y(s),z(s)),其中s為弧長(zhǎng)。則其曲率和撓率計(jì)算如下顯然,對(duì)于給定的封閉的3D空間光滑曲線,就可以用上式求得曲線上任意一點(diǎn)的曲率和撓率。3參數(shù)特征集及排序?qū)τ诮o定的數(shù)據(jù)點(diǎn)經(jīng)過(guò)前面的預(yù)處理,我們就得到了逼近這些數(shù)據(jù)點(diǎn)的兩個(gè)樣條曲線記為C1(s1),C2(s2),其中s1,s2為弧長(zhǎng)參數(shù)。n+1個(gè)控制頂點(diǎn)分別為:P01,P11,…,Pn1;P02,P12,…,Pn2。由于基于輪廓線的形狀匹配只能應(yīng)用局部特征,根據(jù)特征我們選擇了曲線上的曲率和撓率,來(lái)研究基于這一特征的兩條曲線的匹配問(wèn)題。設(shè)在曲線C1(s1)上取m個(gè)采樣點(diǎn),計(jì)算每一點(diǎn)處的曲率和撓率,得到這條曲線的特征集,{(κi1,iτ1)},i=1,2,…,m。在曲線C2(s2)上取對(duì)應(yīng)的m個(gè)采樣點(diǎn),計(jì)算每一點(diǎn)處的曲率和撓率,得到這條曲線的特征集,{(κi2,iτ2)},i=1,2,…,m。由于將參數(shù)選為弧長(zhǎng)并進(jìn)行了規(guī)范化,因此,只要將參數(shù)區(qū)間m等分,代入各自的曲線表達(dá)式就得到相應(yīng)的采樣點(diǎn)。本文給出的算法如下:對(duì)于給定的兩個(gè)特征集,將按曲率的大小以升序的次序構(gòu)成兩個(gè)有序表(自然可以按照撓率的大小進(jìn)行排序)。假設(shè)排序后的兩個(gè)有序表如下設(shè)κ1il和κ2jk,l,k=1,…,m,絕對(duì)值之差在閾值的范圍內(nèi),這時(shí)檢查對(duì)應(yīng)的第二個(gè)分量,如果絕對(duì)值之差仍在閾值的范圍內(nèi),則該點(diǎn)匹配成功,否則認(rèn)為不匹配。在匹配成功的情況下,自然下一個(gè)κ1il+1只可能與κ2jk+1及以后的一定范圍內(nèi)的某個(gè)點(diǎn)才可能匹配成功。這樣就限制了匹配時(shí)搜索的范圍,如果誤差閾值取為δ=min{mlin(κ1il+1-κ1il),mkin(κ2jk+1-κ2jk)},l,k=1,2,…,m,對(duì)于ΓC1和ΓC2中的各個(gè)曲率的比較的范圍是一個(gè)常數(shù)。因此,避免了在匹配時(shí)盲目的比較,提高了匹配的速度。4模型相互位置的基本概念通過(guò)使用以上方法,在獲取物體模型的基礎(chǔ)上,提取其邊界點(diǎn),然后采用5階4次B-樣條曲線在滿足一定誤差的條件下逼近到數(shù)據(jù)點(diǎn),物體模型、提取到的邊界點(diǎn)以及逼近的曲線:其中,圖1(a)為物體模型,圖1(b)為提取的邊界點(diǎn),圖1(c)為逼近曲線。下一組給出了兩碎片的輪廓曲線、曲線匹配后的結(jié)果及匹配后對(duì)應(yīng)的兩個(gè)模型之間的相互位置關(guān)系。圖2(a)為兩個(gè)破碎物體的輪廓曲線,圖2(b)為輪廓曲線匹配結(jié)果(較粗的重合部分為匹配成功的曲線段),圖2(c)為對(duì)應(yīng)的模型匹配結(jié)果。5特征點(diǎn)的提取和匹配數(shù)字曲線的B-樣條表示不僅給出了輪廓線的一種簡(jiǎn)單的描述方法,也為輪廓線的匹配提供了數(shù)學(xué)模型,這一表