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

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