三次樣條曲線生成算法研究

1、三次樣條曲線的生成算法本文由天空樂園河南自考網(wǎng)整理分享摘要三次樣條函數(shù)曲線具有的最高多項式插值精度是三次多項式函數(shù)，對其進(jìn)行推廣構(gòu)造的三次參數(shù)樣條曲線應(yīng)至少具有同樣的插值精度。本文討論了構(gòu)造三次參數(shù)樣條曲線中節(jié)點選取問題，相鄰兩節(jié)點之間的跨度規(guī)范化為 1，提出了構(gòu)造 2GC 三次參數(shù)樣條曲線的新方法。文中首先討論了 2GC 三次參數(shù)樣條曲線需滿足的連續(xù)性方程，然后討論了平面有序五點確定一組三次多項式函數(shù)曲線和平面有序六點唯一確定一條三次多項式函數(shù)曲線。 在此基礎(chǔ)上， 提出了為給定數(shù)據(jù)點選取節(jié)點值的新方法。 新方法構(gòu)造的 2GC 三次參數(shù)樣條曲線具有三次多項式函數(shù)的插值精度。 最后以具體數(shù)據(jù)點對

2、新方法和已有的四種節(jié)點選取方法構(gòu)造的插值曲線的精度做了比較。關(guān)鍵詞：三次樣條曲線；曲線擬合；計算機圖形學(xué)自1946年美國數(shù)學(xué)家 I. J. Schoenberg 提出樣條函數(shù)1以來，樣條函數(shù)以其構(gòu)造簡單、易于計算又有很好的力學(xué)背景等特點而被廣泛用于科學(xué)計算、 工程設(shè)計和計算機輔助設(shè)計等領(lǐng)域，成為最重要的曲線和曲面構(gòu)造方法之一。在樣條函數(shù)的應(yīng)用中，三次樣條函數(shù)由于具有極小模性質(zhì)、 最佳逼近性質(zhì)和很強的收斂性2,3,4等而成為最主要的方法應(yīng)用于構(gòu)造插值曲線和曲面。 用樣條函數(shù)方法構(gòu)造三次插值曲線，曲線的連續(xù)性基本可滿足實際應(yīng)用的要求。當(dāng)曲線的端點條件確定之后，曲線的精度和形狀是由曲線需滿足的連續(xù)性

3、方程唯一決定的。在小撓度的情況下，插值曲線的精度和形狀都是非常理想的。對大撓度曲線和任意平面數(shù)據(jù)點，則需推廣三次樣條函數(shù)方法構(gòu)造三次參數(shù)樣條曲線，此時需知道每個數(shù)據(jù)點處的參數(shù)值（節(jié)點值） 。在實際應(yīng)用中，這些參數(shù)值一般是無法預(yù)先給定的，所以構(gòu)造三次參數(shù)樣條曲線的第一步是對給定數(shù)據(jù)點參數(shù)化，即為每個數(shù)據(jù)點指定節(jié)點值。如果指定的節(jié)點值是精確的，給定適當(dāng)?shù)亩它c條件，可使構(gòu)造的插值曲線的代數(shù)精度達(dá)到三次參數(shù)多項式。構(gòu)造三次參數(shù)樣條曲線，當(dāng)曲線的端點條件確定之后，能夠決定曲線插值精度的量只有節(jié)點。因此構(gòu)造三次參數(shù)樣條曲線的關(guān)鍵是如何選擇節(jié)點。目前常用的節(jié)點選取方法有 4種，均勻參數(shù)化法、累加弦長參數(shù)化法

4、、向心參數(shù)化法5和修正弦長參數(shù)化法6。這些方法雖然在實際中得到了較為廣泛的應(yīng)用，但從逼近的角度看，它們的插值精度較低，其插值多項式的最高精度是線性的。 最近一個確定節(jié)點的方法7具有二次多項式插值精度， 如果用來構(gòu)造三次參數(shù)樣條曲線，這個精度也是較低的。三次樣條函數(shù)曲線具有的最高多項式插值精度是三次多項式函數(shù)，對其進(jìn)行推廣構(gòu)造的三次參數(shù)樣條曲線應(yīng)至少具有同樣的插值精度。從這一目標(biāo)出發(fā)，本文討論了構(gòu)造三次參數(shù)樣條曲線中節(jié)點選取問題，相鄰兩節(jié)點之間的跨度規(guī)范化為 1，提出了構(gòu)造 2GC 三次參數(shù)樣條曲線的新方法。文中首先討論了 2GC 三次參數(shù)樣條曲線需滿足的連續(xù)性方程，然后討論了平面有序五點確定一

5、組三次多項式函數(shù)曲線和平面有序六點唯一確定一條三次多項式函數(shù)曲線。 在此基礎(chǔ)上， 提出了為給定數(shù)據(jù)點選取節(jié)點值的新方法。 新方法構(gòu)造的 2GC 三次參數(shù)樣條曲線具有三次多項式函數(shù)的插值精度。 最后以具體數(shù)據(jù)點對新方法和已有的四種節(jié)點選取方法構(gòu)造的插值曲線的精度做了比較。平面自由曲線不能用一個標(biāo)準(zhǔn)代數(shù)方程精確表示。實際中應(yīng)用很多，如輪船船身放樣。將放樣過程抽象為:平面上給定若干點（型值點），找一個代數(shù)方程，逼近或插值上述型值點。理論上，n個點，可以找到一個n-1次多項式來逼近，但n太大時，多項式次數(shù)太高，計算復(fù)雜，難以控制。工程上，降低次數(shù)，且分段定義。樣條函數(shù)自提出以來，以其構(gòu)造簡單，易于計算

6、，及很好的力學(xué)背景等特點被廣泛用于科學(xué)計算，工程設(shè)計和計算機輔助設(shè)計等領(lǐng)域，從而成為最重要的曲線和曲面構(gòu)造方法之一。三次樣條曲線在使用中存在局限性，且表示方法缺乏幾何不變性。即當(dāng)平面直角坐標(biāo)系中得型值點發(fā)生旋轉(zhuǎn)等幾何變形時，其曲線的形狀也發(fā)生變形，嚴(yán)重時甚至不能保證滿足X1X2X3Xn的條件，對表現(xiàn)曲線的幾何形狀極為不便；在使用autoCAD中spline命令繪制樣條曲線時，可能導(dǎo)致各型值點的橫坐標(biāo)也不能滿足X1X2X3Xn的條件。為了解決這些問題，一些學(xué)者運用向心參數(shù)法在周期性三次樣條曲線擬合控制多邊形時，取得了很小的偏差；基于累加弦長的三次參數(shù)樣條曲線插值在數(shù)控系統(tǒng)中取得了較好的效果，但是

7、以累加弦長為參數(shù)的三次參數(shù)樣條曲線插值和基樣條的函數(shù)插值在各分段曲線兩端曲率的符號相同的情況下都有可能產(chǎn)生這段曲線上的拐點，造成曲線不光顧。因此一些準(zhǔn)測提出檢查多余的拐點，YE J等人修正了Kjellander的方法，并從累加弦長參數(shù)化和光顧函數(shù)兩方面消除了三次參數(shù)樣條的震蕩和回折。在曲線擬合中，插值過程可具體使用線性（liner）插值，三系樣條（spline）插值，立方(cubic)插值等方法，在曲線插值法中最常用的是線性插值法，它是估計2個主干點之間數(shù)值的最簡單，最易實現(xiàn)的方法，但采用線性插值法會有以下缺點：1曲線不能顯示連接主干點間的凸?fàn)罨【€；2從曲線導(dǎo)出遠(yuǎn)期曲線時會形成人為的“尖頭”。

8、因此，通常采用樣條法來構(gòu)造曲線，它通過構(gòu)造多項式（1個或1組不同階多項式）來形成1條把所有主干點連接起來的平滑曲線，一般常選擇3次曲線（根據(jù)3次插值樣條函數(shù)所得的曲線）進(jìn)行擬合。3次樣條曲線具有良好的數(shù)學(xué)特征，而且用3次曲線去擬合時，其結(jié)果要比線性插值估計更接近于工程實際情況，但是在工程應(yīng)用中，我們利用三次樣條插值方法，對相同的控制點，只可以得到1條光滑曲線，如果我們想基于相同的控制點，得到多條不同曲線，依靠傳統(tǒng)算法，是無法實現(xiàn)的，這就限制了三次樣條在工程中，特別是印刷領(lǐng)域中得應(yīng)用。在印刷領(lǐng)域，特別市在工藝前端，傳統(tǒng)的方法是利用曲線進(jìn)行分色操作，由于色彩的特殊性，即人眼對色彩的感覺不盡相同。如

9、果只有1條色度曲線，那么工藝人員就無法對色彩效果進(jìn)行有效的對比。因此印刷工藝的特殊性要求能夠根據(jù)相同控制點，得出多條曲線，實現(xiàn)不同的印刷色彩效果，從中選出最佳的色度曲線。在這一點上，傳統(tǒng)的方法是通過修改基本的控制點，生成新的控制曲線實行，本文提出改進(jìn)的3次樣條算法，實現(xiàn)了在相同的控制點上，生成了曲線不同的新曲線。增加了生成曲線的條數(shù)，從而使得印刷前端的工藝操作人員，對控制圖像的色度曲線有更多的選擇。三次參數(shù)樣條曲線的構(gòu)造設(shè)平面上給定了n個數(shù)據(jù)點 目標(biāo)是構(gòu)造一條對n個數(shù)據(jù)點插值的三次參數(shù)樣條曲線 P (t)。設(shè)ti(待定)是與 iP相對應(yīng)的節(jié)點，令則區(qū)間上的三次參數(shù)曲線 Pi(t)可定義如下：其

10、中為0,1區(qū)間上的三次埃爾米特基函數(shù)， 為節(jié)點ti處的切矢。 P t ()應(yīng)滿足的連續(xù)性方程是6,8：其中;令；則(2.2)可寫成如下形式：其中；如果Si給定，則可得到(2.4)中的 Ni,i=1,2,n,由知，對i =1,2, ,n-1,(2.1)可寫成如下形式：其中0s1。 顯然，由(2.6)定義的樣條曲線是 連續(xù)的。方程組(2.4)中有n 2方程，n個未知量,解方程組需增加兩個端點條件，方法如下： (1) 對封閉或周期曲線 所以，(2) 兩端點處的二階導(dǎo)數(shù)為零此時，對(2.4)中的 i =2和n-1 ，相應(yīng)的方程為所求方程中的未知量為(3) 給定端點切向條件M1 和Mn ，其中F1和 F

11、2的值確定將在第四節(jié)中討論。 設(shè)，是給定數(shù)點中連續(xù)五點，與 Pj 相對應(yīng)的節(jié)點是t j(待定)。為討論方便，我們做如下變換。設(shè)不在一條直線上，把坐標(biāo)變換分別施加到 Pi和 ti 。則在ovw坐標(biāo)系中 的坐標(biāo)為相應(yīng)的節(jié)點值分別為 和其中 is 由(2.3)定義。對插值的三次參數(shù)曲線是其中；如果給定數(shù)據(jù)點是一條三次多項式函數(shù)曲線上的點，則 vi(s)和wi(s)中二次項系數(shù)之比等于三次項系數(shù)之比8，即化簡得：其中 滿足由于Q (s)是唯一的，從而有直接驗證知，兩式是等價的，并且可寫成如下形式由( 3.4)知，這時一個關(guān)于 Si 的一元五次方程，用公式法不能求出精確解。可用如下方法求精確解。考慮 P

12、k ，k=i-1,i+3，把變換(3.1)施加到 Pk ，由對稱性得其中由(3.4)定義。聯(lián)立(3.6)和(3.7)可求出精確解 Si 。因此平面六點可唯一定義一條三次多項式函數(shù)曲線。對邊界數(shù)據(jù)點 Pi，當(dāng) 3 = i ，相應(yīng)于(3.7)的方程是聯(lián)立 (3.6) 和 (3.8) 可求出精確解 S3對 P2 , 由 (3.4) 知，相應(yīng)于 P2 的參數(shù)是所以，同理可求出。計算題可用兩種方法計算 Si ：1) 對(3.6)直接用數(shù)值方法求；2) 聯(lián)立(3.6)和(3.7)用公式法求。所求的 Si應(yīng)滿足下列條件：這樣的Si可能多于一個。所以，平面有序五點不能唯一決定一條三次多項式函數(shù)曲線。 確定 S

13、i的方法是所有滿足(3.9)的加權(quán)平均。 下面討論權(quán)函數(shù)的取值。在所有中，只有一個值是所求的?？紤]，如果給定數(shù)據(jù)點是三次多項式函數(shù)上的點，由(3.3)和(3.4)知，中應(yīng)有一個Si,l滿足如果給定數(shù)據(jù)點和 P k不是三次多項式上的點，則, 。在這種情況下，希望值小的Si,l對形成Si的影響大。為此定義Si由下式定義：顯然，如果 Si,j ,滿足Ei,j=0，則Si = Si,j。記(3.6)的右端為F(Si)。計算表明，在大多數(shù)情況下，F(xiàn)(Si)有符合(3.9)的兩個實根或兩個重根，如圖 1所示。在圖1 中，F(xiàn)(Si)雖然有三個實根，但左邊的根不符合條件(3.9)。如果(3.6)中沒有滿足(3

14、.9)的Si，則選取F(Si) 在0,1區(qū)間上的極小值點(F(Si)在0,1區(qū)間上的極值點的值大于零)或極大值點(F(Si)在0,1區(qū)間上的極值點的值小于零)作為Si。例如，對圖 2 所示的情況選取極大值點為Si。如果F(Si) 在0,1區(qū)間上既沒有符合(3.9)的實根， 也沒有符合條件的極小或極大值點，如圖 3 所示，則Si的選取應(yīng)極小化下式的值即，對應(yīng)使(3.3)定義的兩個三次參數(shù)曲線的三次項系數(shù)的差最小。 例子：本節(jié)我們以實例對新方法、累加弦長法、向心法，修正弦長法和二次精度法做比較。用于比較的數(shù)據(jù)點取自一條給定曲線。用五種方法分別對給定數(shù)據(jù)點構(gòu)造三次參數(shù)樣條曲線，以樣條曲線的插值精度對

15、五種方法進(jìn)行比較。定義數(shù)據(jù)點的曲線是其中，三次參數(shù)曲線 F(t) 具有如下性質(zhì)：K = 1,2,3,4時是凸的，K = 5,6,7,8 時有兩個拐點，K = 9時有一個尖點，K = 10 ,11,12 時有一個圈，圖 4 是K = 3,6,9,12 時F (s)在區(qū)間0,1 上的圖形。 用于比較的區(qū)間是0,1。區(qū)間被分成 20 個子區(qū)間定義數(shù)據(jù)點Pi=F(Ti) , i=0,1,2,20 ,Ti由下式定義其中00.25 。的取值使數(shù)據(jù)點相鄰兩弦長滿足五種方法用絕對誤差曲線 E(s) 比較,E(s) 定義如下其中 P(s) 表示五種方法構(gòu)造的三次參數(shù)樣條曲線之一， F(t) 為 (5.1)或(5

16、.3)定義的曲線， P i(s)表示 P(s)在區(qū)間Si,Si+1上的部分，|P(s)-F(t)|表示點P(s)到F(t)的距離。 (5.2)中取 = 0.25 時，五種方法產(chǎn)生的最大絕對誤差見表 1。 表 1 五種方法對(5.1)插值產(chǎn)生的最大誤差E(s)新方法二次精度累加弦長修正弦長向心K=19.07e-6 1.68e-53.91e-44.97e-48.07e-4K=25.08e-6 9.24e-62.23e-52.77e-41.29e-3K=31.73e-7 4.89e-62.42e-55.50e-41.87e-3K=44.73e-5 1.47e-54.50e-59.40e-42.37e

17、-3K=51.01e-4 3.88e-45.43e-51.36e-32.70e-3K=63.60e-4 6.21e-42.60e-41.68e-32.73e-3K=74.33e-4 1.64e-31.44e-31.61e-32.06e-3K=82.19e-4 3.08e-44.25e-31.07e-31.37e-3K=92.68e-4 9.34e-41.11e-34.57e-41.84e-3K=102.75e-4 4.25e-46.32e-31.93e-32.31e-3K=111.72e-4 3.83e-43.15e-33.82e-33.70e-3K=121.46e-4 3.79e-41.23

18、e-35.17e-35.55e-3下面用一個橢圓定義數(shù)據(jù)點對五種方法構(gòu)造的閉合曲線進(jìn)行比較。橢圓的方程是X = 3cos(2t) (5.3)Y = 2sin(2t)區(qū)間0,1也被分成 20 個小區(qū)間定義數(shù)據(jù)點。 本例中也對用精確節(jié)點值構(gòu)造的三次參數(shù)插值曲線進(jìn)行比較。對應(yīng)于(5.2)中不同的，六種方法產(chǎn)生的最大絕對誤差見表 2。計算知，本例中 = 0時新方法和二次精度法指定的節(jié)點都是精確的。表 2說明，對本例，新方法構(gòu)造的插值曲線的精度比用精確節(jié)點構(gòu)造的插值曲線的精度高。 表 2 五種方法對橢圓插值產(chǎn)生的最大誤差E(s) 精確參數(shù)新方法二次精度累加弦長修正弦長向心 =.0 7.68e-57.68

19、e-57.68e-56.65e-41.87e-43.56e-4 =.05 1.36e-41.16e-42.08e-47.55e-43.46e-34.68e-3 =.10 2.20e-41.68e-43.85e-48.41e-47.48e-31.02e-2 =.15 3.25e-42.26e-46.03e-49.23e-41.24e-21.65e-2 =.20 4.51e-42.88e-48.62e-41.00e-31.83e-22.37e-2 =.25 6.00e-4 3.53e-41.17e-31.07e-32.50e-23.18e-2我們還把區(qū)間0,1分成 30、40 等個小區(qū)間對五種方法

20、進(jìn)行比較，其結(jié)果類似于表 1和表 2。總結(jié)：在平面上唯一確定一條三次多項式函數(shù)曲線需要 6 個有序數(shù)據(jù)點。 如果給定的 6 個有序數(shù)據(jù)點是三次多項式函數(shù)F 上的點，則 6 個數(shù)據(jù)點可精確定義F 。 對平面上給定的n個數(shù)據(jù)點，本文提出了一個對其進(jìn)行參數(shù)化的新方法。用指定節(jié)點構(gòu)造的三次參數(shù)樣條曲線是 2GC 連續(xù)的，其多項式準(zhǔn)確集包括所有三次和小于三次的函數(shù)多項式。實例計算也表明，新方法構(gòu)造的三次參數(shù)樣條曲線對給定數(shù)據(jù)點，尤其是對凸的數(shù)據(jù)點，具有較高的插值精度。 繼續(xù)的工作是：研究是否存在一個對數(shù)據(jù)點參數(shù)化的方法，使構(gòu)造的三次參數(shù)樣條曲線的多項式準(zhǔn)確集包括所有三次和小于三次的參數(shù)多項式。 推廣本文思想構(gòu)造對空間數(shù)據(jù)點插值的 2GC 三次參數(shù)樣條曲線。 在對疊化的編輯模型分析的基礎(chǔ)上，針對有些非疊化區(qū)域由于物體及攝像機運動的影響，也符合疊化編輯模型的特征，利用疊化所特有的連續(xù)一致性對候選收索區(qū)域進(jìn)行確認(rèn)，減少了因物體及攝像機運動所產(chǎn)生的誤檢，提高了算法的查準(zhǔn)率。同時，本算法是在檢測出切變鏡頭邊界的基礎(chǔ)上檢