基于形狀參數(shù)均勻B樣條的曲線擬合方法研究_趙顏利_圖文

1、第12卷 第11期2007年11月中國圖象圖形學(xué)報Journa l o f I m age and G raphicsV o. l 12, N o . 11N ov . , 2007基于形狀參數(shù)均勻B 樣條的曲線擬合方法研究趙顏利 史文俊 郭成昊 劉鳳玉(南京理工大學(xué)計算機(jī)系, 南京 210094摘 要 分析了帶形狀參數(shù)的均勻B 樣條模型, 將帶形狀參數(shù)的均勻B 樣條曲線應(yīng)用于離散數(shù)據(jù)點的擬合。歸納并給出了形狀參數(shù)的取值策略, 采用迭代線性最近點的方式來優(yōu)化修正數(shù)據(jù)點的參數(shù), 以上方法提高了擬合的精度和速度。通過實驗分析, 證明了該方法的有效性。關(guān)鍵詞 帶形狀參數(shù)的均勻B 樣條 曲線擬合 迭代

2、線性最近點中圖法分類號:TP391 文獻(xiàn)標(biāo)識碼:A 文章編號:1006-8961(2007 11-2093-05Curve F itti ng Based on Unifor m B -spli nes w ith Shape Para m eterZ HAO Y an -l, i SH IW en-j u n, GUO Cheng -hao , LIU Feng -yu(Depart m e n t of C o mputer S cience and Technol ogy, N anji ng Un i versit y o f S cie n ce and Tec hn ology,

3、Nan ji ng 210094Abstrac t T h i s pape r analyses t he uniform B -spli ne modelw ith shape para m eters , and applys the m ode l to the curve fitti ng o f discrete data po i nts . In th i s paper , the va l ue o f the shape para m eter i s stud i ed , and an a l gor it hm based on itera ti ve li nea

4、rclosest po i nts is put for w ard to rectify the param eter va l ues of data po i nts . The ana l ysis o f expe ri m en tal results de m onstrates the va lidity and robustness o f our algorith m.K eywords unifor m B -sp li ne w ith shape pa ra m e ters , curv e fitti ng ,i tera tive li ner c l o se

5、st po i nt曲面擬合中更具有方便性和精確性。同時本文采用1 引 言在圖像處理、工程設(shè)計等應(yīng)用中常常需要用曲線按一定要求逼近一系列實測的有序數(shù)據(jù)點, 即所謂的曲線擬合問題。曲線擬合的精度直接影響到后續(xù)處理效果的優(yōu)劣, 國內(nèi)外不少學(xué)者對此問題進(jìn)行了大量的研究。如Rogers 和Fog 提出了一種迭代修正數(shù)據(jù)點參數(shù)的方法; Pigel 提到了用迭代的方2法來修正B 樣條曲線的參數(shù), 但其沒有給出具體的修正方法; 肖等人提出了迭代最近點的B 樣條曲線擬合方法, 并對其有效性、穩(wěn)定性進(jìn)行了討論。本文將帶形狀參數(shù)的均勻B 樣條模型應(yīng)用于曲線擬合。由帶形狀參數(shù)的均勻B 樣條基組成的樣條曲線可以通過調(diào)

6、整形狀參數(shù)的取值來生成不同形狀的均勻樣條曲線, 具有很大靈活性, 故在曲線、基金項目:國家自然科學(xué)基金項目(60273035 收稿日期:2006-07-11; 改回日期:2006-08-2831了迭代線性最近點的方法, 減少了擬合誤差, 提高了擬合精度。實驗結(jié)果表明本文算法與文獻(xiàn)3算法相比, 計算量小, 擬合速度和精度都有了較大提高。同時當(dāng)形狀參數(shù)取值為零時, 文獻(xiàn)3提出的B 樣條曲線擬合方法成為本文方法的一種特例。2 帶形狀參數(shù)均勻B 樣條基函數(shù)的構(gòu)造及性質(zhì)為得到帶形狀參數(shù)均勻B 樣條基函數(shù)非負(fù)函數(shù)h( , t, t 0, 2滿足條件:(1 h ( , 0 =h ( , 2 =0, t h

7、( , t =h ( , 2-t, t 0, 2;4, 構(gòu)造0, 2(2 h ( , t 是C 連續(xù)(零階點連續(xù) 的分段二次函數(shù);第一作者簡介:趙顏利(1981 , 男。現(xiàn)為南京理工大學(xué)計算機(jī)系博士研究生。主要研究方向為計算機(jī)視覺、計算機(jī)圖形學(xué)與圖像分析E-l j co m(3h ( , t d t =21;由條件1和條件2可以得到:h ( , t =a t +b ta (2-t +b(2-t220 t <11 t <2由條件3得到2a /3+b =1, 若令b =1- , 則a =3 /2。將a 、b 代入上式, 得3 t +(1- t/2S 0, 2(t =3 (2-t /2+

8、(1- (2-t220 t <11 t <2其他圖1 形參4階均勻B 樣條曲線F i g . 1 4order B -spli ne w ith s hape para m eter=0. 75(實線, =0(虛線, =-1. 5(點線其中, -1 <1。令S i, 2(t =S 0, 2(t -i, i =0, 1, 2, , 稱S i, 2(t 為二階形狀參數(shù)均勻B 樣條的基函數(shù)。k 階(k 3 形狀參數(shù)均勻B 樣條的基函數(shù)可由以下公式遞推得到:S 0, k (t =-1圖1中給出的是在相同的控制點下形狀參數(shù)4階均勻B 樣條曲線在不同的形參取值時得到的3條樣條曲線。可以看

9、出在相同的控制點情況下, 帶形狀參數(shù)的B 樣條模型可以通過取不同的形狀參數(shù)值得到不同形狀的曲線而均勻B 樣條模型是固定不變的。說明帶形狀參數(shù)的B 樣條模型比B 樣條模型具有更加好的調(diào)節(jié)曲線形狀的性能, 可以更好逼近不同類型的的曲線。S10, k-1(x d x, i =0, 1, 2,S i, k (t =S 0, k (t -i當(dāng)k 3時, 根據(jù)定義可得到S i , k (t 所具有的性質(zhì)。稱其為k 階帶形狀參數(shù)均勻B 樣條基函數(shù), 為形狀參數(shù), 取值范圍為-1, 1。由以上定義和性質(zhì)可以得出, 當(dāng) =0. 3, i =0時, 4階形參均勻B 樣條基函數(shù)為t /8+(1- t /6- x /

10、8-(1+ t /2+(4- t /2-2t +(8+ /12N 0, 4(t =- x /8+(1+3 t /2-(8+13 t /2+(10+12 t -(88+95 /12 t /8-(11+5 t /6+(2+10 t -8(1+3 t +32(2 +1 /31 t <2432432243430 t <13 最小二乘形狀參數(shù)均勻B 樣條曲線擬合k (k 3 階帶形狀參數(shù)均勻B 樣條曲線的參數(shù)方程為-1 t <00 t <1P (u =向量。d Nii=0n, k i(u (1其中, d i 表示帶形狀參數(shù)B 樣條曲線的控制點坐標(biāo)N i, 3(u 為帶形狀參數(shù)均勻

11、B 樣條基函數(shù)。如果數(shù)據(jù)點集P =pj :j =1, 2, 3, , r 在B 樣條曲線上, 點p j 應(yīng)滿足方程(1, 于是有p j (t j =為了便于對形參均勻B 樣條和均勻B 樣條比較, 將上面基函數(shù)參數(shù)t 的范圍進(jìn)行規(guī)范化, 使得t 0, 1?；喴院蟮玫綆螤顓?shù)的4階均勻B 樣條的調(diào)配函數(shù)為b 0(t =(4- -3 t (1-t /24b 1(t =16+2 -12(2+ t +12(1+ t -3 t /24b 2(t =4- -12t +6(2+ t -12t -3 t /24b 3(t =4-4 +3 t t /2432342343d Ni=0ini, k(t j (2將

12、式(2 寫成矩陣形式有P =ND (3其中, P 是包含r 個數(shù)據(jù)點的r 3矩陣, N 是r n 的B 樣條基函數(shù)系數(shù)矩陣, D 是包含n 個未知控制點的n 3矩陣。進(jìn)一步可以推出高斯正交方程組:N ND =N P, N TTT當(dāng) =0時得到的調(diào)配函數(shù)和3次均勻B 樣條的調(diào)配函數(shù)式是一致的。說明均勻B 樣條基函數(shù)是帶形狀參數(shù)的均勻B 樣條基函數(shù)的一個特例。即形狀參數(shù) =0時, 帶形狀參數(shù)的均勻B 樣條曲陣, 方程存在唯一解。得到最小二乘法擬合帶形參B 樣條曲線的控制點, 求解方程如下:D =(N N N P (4可以證明, 在均方誤差最小意義下式(4 的解是最優(yōu)解, 即解出的控制點d 形成的B

13、 樣條曲線是最佳擬合曲線, 并使得參數(shù)為t j 的B 樣條曲線采樣點集到數(shù)據(jù)點集P 的均方誤差最小。t j 通過對數(shù)據(jù)點均勻參數(shù)化5qT-1T(2 若q 0, 計算數(shù)據(jù)點集在擬合曲線上的對應(yīng)的線性最近點集, 并把對應(yīng)的線性最近點集的參數(shù)作為該數(shù)據(jù)點的參數(shù)t j :j =1, 2, 3, , r 。若q =0, 轉(zhuǎn)到第3步。(3 根據(jù)式(4 計算出新的控制點集合D =d i :j =1, 2, 3, , n ,設(shè)定曲線的形狀參數(shù) , 得到帶形參B 樣條曲線C 。q(4 計算參數(shù)集t j :j =1, 2, 3, , r 對應(yīng)的帶形狀參數(shù)均勻B 樣條曲線上的點X =x j :j =1, 2, 3,

14、 , r ,進(jìn)一步計算數(shù)據(jù)點集P 與曲線對應(yīng)點集qX 的均方差d 。(5 重新返回第2步, 直到迭代的均方差之差 d =d -dqq -1qqqqq的方法得到。對有序的數(shù)據(jù)點列P =pj :j =1, 2, 3, , r ,將其按4個數(shù)據(jù)點為一組進(jìn)行劃分, 每4個數(shù)據(jù)點對應(yīng)于一段分段曲線。在每一段分段曲線內(nèi)對這4個數(shù)據(jù)點進(jìn)行均勻參數(shù)化。后一分段曲線的起點為前一分段曲線的終點, 每一段對應(yīng)的數(shù)據(jù)點列都按照這樣的規(guī)則進(jìn)行參數(shù)化, 由此完成了對整個數(shù)據(jù)點列的均勻參數(shù)化。< , 其中, 為給定的門限值。為比較形狀參數(shù) 在不同情況的數(shù)據(jù)點下對曲線擬合精度的影響, 下面實驗分析給出了形狀參數(shù) 的選擇

15、策略。4 迭代線性最近代點形參均勻B 樣條曲線擬合最小二乘法擬合帶形狀參數(shù)均勻B 樣條曲線保證了擬合曲線上參數(shù)為t j 的點到對應(yīng)數(shù)據(jù)點的均方距離最小, 但是參數(shù)為t j 的點不一定是B 樣條曲線上離對應(yīng)的數(shù)據(jù)點最近的點, 即數(shù)據(jù)點集到擬合B 樣條曲線的均方距離不一定是最小的。為了解決這一個問題, 文獻(xiàn)3中提出了一種基于迭代修正最近數(shù)據(jù)點集參數(shù)的方法。所謂某數(shù)據(jù)點p i 的最近點, 是把該點的參數(shù)t j 鄰域(t i - , t i + 進(jìn)行n 等分(n >1, >0, 每一等分點是一個參數(shù), 對應(yīng)一個曲線點, 把這些曲線點逐個算出和p i 的距離, 最近者就是所謂的最近點。同樣為

16、解決擬合誤差問題, 本文采用迭代修正線性最近數(shù)據(jù)點集參數(shù)的方法。當(dāng)數(shù)據(jù)點集比較密集時, 由于參數(shù)t i - , t i + 對應(yīng)的B 樣條曲線點距離很近, 可以將兩點之間的曲線段近似為直線段。所以在曲線段上求出的最近點, 就轉(zhuǎn)化為在直線段上求p i 的最近點。求得的最近點就是所謂的線性最近點。顯然, 求線性最近點的計算量及速度都優(yōu)于在曲線上求最近點。本文采用的線性迭代最近點的最小二乘法形參均勻B 樣條曲線擬合算法在迭代過程中保持B 樣條模型的形狀參數(shù)不變。具體的算法如下:(1 對取得的邊緣數(shù)據(jù)點集合進(jìn)行參數(shù)化, 得到數(shù)據(jù)點集合P 的參數(shù)集t j :j =1, 2, 3, , r ,其中r q5

17、 實驗結(jié)果采用4階形狀參數(shù)均勻B 樣條和3組實驗數(shù)據(jù)對提出的算法進(jìn)行了曲線擬合實驗, 并將文獻(xiàn)3中算法的結(jié)果和本文算法的結(jié)果進(jìn)行了比較。圖2為平滑和非平滑兩種不同類型數(shù)據(jù)點, 在 取不同值時, 經(jīng)過多次迭代后的曲線擬合效果圖。圖3(a 、(b 為形狀參數(shù)固定時, 不同類型數(shù)據(jù)點曲線擬合隨迭代次數(shù)變化方差分布圖, 圖3(c 為迭代次數(shù)固定時, 數(shù)據(jù)點曲線擬合隨形狀參數(shù)變化方差分布圖。圖2 不同類型數(shù)據(jù)點迭代效果圖F i g. 2Iterati ve fi gures of d ifferent k i nds of data po i n ts (2 相對非平滑的數(shù)據(jù)點進(jìn)行曲線擬合時, 迭代超過

18、一定次數(shù)后, 越大, 曲線擬合的精度越高, 收斂性越好。(3 相對平滑的數(shù)據(jù)點進(jìn)行曲線擬合時, 迭代次數(shù)一定, 越小, 曲線擬合的精度越高, 收斂性越好。由于當(dāng) =0時, 帶形狀參數(shù)均勻B 樣條基函數(shù)與均勻B 樣條基函數(shù)相同, 即兩種樣條函數(shù)擬合效果圖相同。分析圖3方差圖, 可以看出迭代次數(shù)相同時, 形參的選擇可以提高擬合精度, 精度要求固定時, 形參的選擇可以降低迭代開銷。所以通過形參的選擇, 形參均勻B 樣條擬合曲線優(yōu)于均勻B 樣條曲線擬合。為檢驗本文對復(fù)雜曲線的擬合效果, 用一個魚類生物輪廓進(jìn)行了曲線擬合實驗, 采用了300個數(shù)據(jù)采樣點, 擬合效果如圖4所示。圖5為擬合方差隨迭代次數(shù)變化

19、分布圖。其中, =0時, 帶形狀參數(shù)均勻B 樣條函數(shù)等同于均勻B 樣條函數(shù), 圖4(b 為采用文獻(xiàn)3的迭代最近點的方法得出的效果圖。(a 非平滑數(shù)據(jù)迭代次數(shù)變化方差圖(b 平滑數(shù)據(jù)迭代次數(shù)變化方差圖圖4 復(fù)雜海洋生物輪廓曲線擬合圖F i g. 4 Curve fi tti ng fi gures o f contour of halob i o s(c 數(shù)據(jù)點形狀參數(shù)變化方差圖圖3 數(shù)據(jù)擬合形狀參數(shù)變化方差圖F i g . 3 V ar i ogra m o f da ta fitting w i th the changeo f shape para m ete r分析圖3的擬合方差圖, 可

20、以歸納得出對于不同類型的數(shù)據(jù)點, 形狀參數(shù) 的最佳取值策略。(1 曲線擬合的精度隨迭代次數(shù)的增加而 圖5 海洋生物輪廓擬合均方差圖F i g . 5 V a ri og ram o f curve fi tti ng of halobi o s由于動物輪廓曲線相對平滑, 故此 取值應(yīng)滿足策略1、策略3才會得到最佳的效果。圖5的擬合方差圖證實了這一結(jié)果, 隨著迭代次數(shù)的增大, 生物輪廓曲線擬合的精度越來越高。迭代次數(shù)相同時, 擬合的精度隨 的減小而增大。圖4給出了文獻(xiàn)3和本文算法的擬合效果圖, 通過對圖5方差圖的分析, 可以得出通過對形狀參數(shù) 的調(diào)節(jié), 本文的算法會取得更好的效果。本文算法將兩點

21、之間的曲線段近似為直線段, 若兩點間距離越小, 則近似精度越大, 反之若距離大, 則精度越小。即采樣數(shù)據(jù)點越密集, 則曲線擬合精度越高; 采樣數(shù)據(jù)點越稀疏, 則精度就會降低。故此本文改進(jìn)的算法對于密集采樣數(shù)據(jù)點的曲線擬合能達(dá)到最佳效果。因此在實際圖像處理中, 可以通過多采集數(shù)據(jù)點的方法來保證曲線擬合的精度。實驗結(jié)果表明, 最終得到的數(shù)據(jù)點集到形狀參數(shù)均勻B 樣條曲線采樣點集的均方誤差變得最小, 滿足了擬合精度的要求。同時針對不同的曲線模型, 對形狀參數(shù)進(jìn)行調(diào)節(jié), 提高了精度, 加快了擬合速度。本文算法在速度和精度都上優(yōu)于均勻B 樣條曲線的擬合方法。線性最近點形參均勻B 樣條曲線擬合方法, 實際

22、應(yīng)用中可以推廣到k (k 3 階形參均勻B 樣條曲線擬合。為提高擬合精度和降低算法的開銷用到如下方法:(1 重復(fù)迭代線性最近點而非最近點, 使得最終數(shù)據(jù)點集到形參均勻B 樣條采樣點集的均方差最小, 保證了迭代擬合的精度, 降低了計算量。(2 分析歸納了形狀參數(shù)的選擇策略, 不同的數(shù)據(jù)點類型選取不同的形狀參數(shù), 提高了擬合精度和算法的速度。以上措施使得本文算法適用范圍更廣。實驗結(jié)果表明本文算法取得了很好的效果。參考文獻(xiàn)(References1 Rogers D F , Fog N G . Con strai n ed B -spli ne curve and surf ace fittingJ .Compu t er A i ded D es i gn , 1989, 21(10:641648.2 P i gel L . On NURBS:A Su rveyJ.I EEE Transacti ons