Bezier曲線和BSpline曲線的擬合問題.docx

Bzeier曲線和BSpline曲線的插值擬合問題目錄一、問題重述1二、Bezier曲線的插值和擬合12.1 Bezier曲線的定義12.2 Bezier曲線的性質(zhì)22.3 三次Bezier曲線的插值22.3.1 工程應(yīng)用中常用的三次Bezier插值的算法22.3.2 改進(jìn)的三次Bezier插值的算法32.3.3 兩種Bezier插值的算法比較42.4 Bezier曲線的擬合4三、BSpline曲線的插值和擬合43.1 BSpline曲線的定義43.2 B樣條性質(zhì)53.3 均勻B樣條53.4 三次B樣條插值算法63.4 結(jié)合實(shí)際情況的三次樣條插值算法改進(jìn)73.5 兩種BSpline插值的比較8四、Bezier曲線與BSpline曲線的區(qū)別和聯(lián)系8五、上述算法在實(shí)際血管提取中的應(yīng)用9一、問題重述在圖像中任意點(diǎn)兩個點(diǎn)，軟件能自動提取出以這兩點(diǎn)為端點(diǎn)的一段血管，要求提取到的血管必須經(jīng)過客戶所點(diǎn)的兩點(diǎn)作為提取血管的兩個端點(diǎn)。在OnGetEdge()的函數(shù)里，首先通過自動增長獲取血管兩條邊緣的采樣點(diǎn)數(shù)據(jù)，接下來的問題就是要擬合這些采樣點(diǎn)，生成兩條比較光滑的血管邊緣曲線。得到的擬合（插值）曲線有以下4點(diǎn)要求：1、精確插入客戶所點(diǎn)的起始點(diǎn)終點(diǎn)，作為曲線的兩個端點(diǎn)；2、擬合的曲線具有較好的光滑性3、具有較高的擬合精度和較快的擬合速度4、要求擬合曲線點(diǎn)八連通上述的實(shí)際問題轉(zhuǎn)化為有序離散點(diǎn)的插值擬合問題。所謂插值擬合，就是通過諸如采樣、實(shí)驗(yàn)等方法獲得若干離散的數(shù)據(jù)，根據(jù)這些數(shù)據(jù)，得到一個連續(xù)的函數(shù)（也就是曲線）或者更加密集的離散方程與已知數(shù)據(jù)相吻合。這個過程叫做擬合。插值是曲線必須通過已知點(diǎn)的擬合。常用的插值方法有拉格朗日插值、牛頓插值、埃爾米特插值、樣條函數(shù)插值等。其中，樣條插值可以使用低階多項式樣條實(shí)現(xiàn)較小的插值誤差，這樣就避免了使用高階多項式所出現(xiàn)的龍格現(xiàn)象，所以樣條插值得到了流行。三次B樣條插值不僅運(yùn)行速度較快，而且因?yàn)槠浞侄芜B續(xù)帶來的特有的卓越的性能，有效提高了血管邊緣的平滑程度，鋸齒狀的現(xiàn)象大大減少。本文接下來將主要介紹Bezier曲線和B樣條的插值擬合。二、Bezier曲線的插值和擬合2.1 Bezier曲線的定義【定義1】n次Bezier曲線是由n+1個控制點(diǎn)和以Bernstein多項式為基底共同生成的參數(shù)曲線，其數(shù)學(xué)表達(dá)式為：，其中，為控制點(diǎn)，為Bernstein基。Fig.1是一條三次的Bezier曲線，有四個控制點(diǎn)。工程應(yīng)用上常使用二次或三次Bezier曲線做采樣點(diǎn)的插值擬合以及制圖設(shè)計。Fig.1 三次Bezier曲線2.2 Bezier曲線的性質(zhì)1、插值于兩個端點(diǎn)，即Berize曲線開始于并結(jié)束于。2、Bezier曲線的起始點(diǎn)（結(jié)束點(diǎn)）相切于控制多邊形（控制點(diǎn)以此首位連接所形成的封閉的多邊形）的第一節(jié)（最后一節(jié)），即。3、Bezier曲線是直線的充分必要條件是控制點(diǎn)共線。2.3 三次Bezier曲線的插值插值要求得到的曲線精確的通過采樣點(diǎn)，四個控制點(diǎn)決定一條Bezier曲線，插值M個點(diǎn)(M4)設(shè)計到曲線拼接連續(xù)性的問題，要求達(dá)到切線連續(xù)。2.3.1 工程應(yīng)用中常用的三次Bezier插值的算法三次Bezier曲線的數(shù)學(xué)表達(dá)是為：Fig.2 三次Bezier曲線的結(jié)構(gòu)【算法一】Step 1：已知采樣點(diǎn)，兩端各自增加一個虛擬控制點(diǎn)，分別求出的中點(diǎn)。Step 2：分別求出的中點(diǎn)。Step 3：將沿著的方向移到，對應(yīng)的移到。Step 4：保持點(diǎn)不變收縮線段到，且。記為，為。Step 5：分別以為4個控制點(diǎn)按照（1）式畫出一條三次的Bezier曲線，得到的Bezier曲線插值于每一個采樣點(diǎn)，且分片一次連續(xù)。Fig.3 算法一的示意圖2.3.2 改進(jìn)的三次Bezier插值的算法由于采樣點(diǎn)本身就存在著誤差和噪音等諸多因素的影響，插值于每一個采樣點(diǎn)得到的Bezier曲線不一定能完全反映真實(shí)的數(shù)據(jù)情況。所以不要求精確的插值每一個采樣點(diǎn)。改進(jìn)的算法步驟如下：【算法二】Step 1：已知采樣點(diǎn)，分別求出的中點(diǎn)。Step 2：依次以分別畫出一條三次的Bezier曲線。依次下去，若剩下的點(diǎn)不足四個控制點(diǎn)，則添加相同的虛擬點(diǎn)，直至滿足四個點(diǎn)畫一條Bezier曲線，這樣得到的Bezier曲線精確的插值與兩個端點(diǎn)及部分中間點(diǎn)，且分片一次連續(xù)。Fig.4 算法二的示意圖2.3.3 兩種Bezier插值的算法比較1）兩種算法都精確插值了兩端端點(diǎn)，且都是分片一次連續(xù)的。2）算法一精確插入了每一個采樣點(diǎn)，算法二精確插入了接近一半的采樣點(diǎn)及采樣點(diǎn)的中點(diǎn)。在采樣誤差較大的情況下，算法二對算法一的改進(jìn)也不是很大。3）整體來說，算法二比算法一的計算量要少，更易理解，也更能貼近實(shí)際數(shù)據(jù)。4）在實(shí)際數(shù)據(jù)有很大尖點(diǎn)的情況下，由于算法二不是點(diǎn)點(diǎn)插值，可能擬合不好，不能擬合出尖點(diǎn)的情況，理論上減少分段長度可以避免這種情況。2.4 Bezier曲線的擬合擬合不要求曲線通過每一個采樣點(diǎn)，只要求曲線“很接近”采樣點(diǎn)就行?！昂芙咏钡脑u價標(biāo)準(zhǔn)常為最小平法逼近。擬合的一般步驟：設(shè)采樣點(diǎn)為，擬合的Bezier曲線為Step 1： 將參數(shù)化到0,1區(qū)間上的值，即求，。常采用弦長參數(shù)法Step 2： 對每一段三次的Bezier曲線，有最小，需要求每一段Bezier曲線的控制點(diǎn)。按照這種算法需要反求控制頂點(diǎn)，隨著數(shù)據(jù)采集量的增大，計算量成倍增長，且反求控制點(diǎn)的矩陣若為病態(tài)矩陣，則求解更耗時間，擬合的結(jié)果也不盡人意。三、BSpline曲線的插值和擬合3.1 BSpline曲線的定義【定義2】給定個節(jié)點(diǎn)，分布在區(qū)間，滿足：。一個次B樣條定義為。其中，為控制點(diǎn)，為B樣條基函數(shù)，定義為：當(dāng)節(jié)點(diǎn)等距時，稱B樣條為均勻節(jié)點(diǎn)樣條。Fig.5 B樣條基的遞推定義3.2 B樣條性質(zhì)1、樣條基函數(shù)的次數(shù)與控制頂點(diǎn)數(shù)無關(guān)。2、【定義2】中的BSpline曲線是分段連續(xù)的，每一段都是一條n次的曲線，共有段曲線，且曲線之間是次連續(xù)的。3、控制點(diǎn)的移動對樣條曲線的影響是局部的。3.3 均勻B樣條當(dāng)B樣條是均勻的時候，對于給定的n，每個B樣條基是其他樣條基的平移拷貝而已。對于三次均勻B樣條，由上述定義的B樣條曲線是分段連續(xù)的曲線，每一段的性質(zhì)都是相同的，將B樣條基轉(zhuǎn)化為多項式函數(shù)的基，得到每一段曲線的矩陣表示形式：Fig.6 均勻三次B樣條示意圖3.4 三次B樣條插值算法下面介紹三次B樣條插值的算法?！舅惴ㄈ恳阎椭迭c(diǎn)（采樣點(diǎn)）共n+1個，確定B樣條曲線控制點(diǎn)的個數(shù)有m+1個，記為，則分段B樣條的個數(shù)為m-2條，記為：。Step 1：將弦長參數(shù)化到區(qū)間0,1。記，則有：，記型值點(diǎn)數(shù)組。Step 2：對每一段三次B樣條曲線，記錄該段曲線在型值點(diǎn)數(shù)組中的始末位置，設(shè)為， 。Step 3：將每一段B樣條曲線的型值點(diǎn)弦長參數(shù)化到0,1區(qū)間，記為。Step 4：記系數(shù)矩陣，由以及（2）式，求出系數(shù)矩陣。記： 則 為稀疏矩陣。Step 5：記，由，即可反求出控制點(diǎn)。即。（這里為矩陣的廣義逆，可直接調(diào)用矩陣類的方法）Step 6：根據(jù)每一段的控制頂點(diǎn)，擬合出一條三次的B樣條曲線。即：算法特點(diǎn)：插值于每一個型值點(diǎn)3.4 結(jié)合實(shí)際情況的三次樣條插值算法改進(jìn)算法三中，系數(shù)矩陣A雖然是稀疏的，但是如果矩陣維數(shù)很龐大，求解矩陣的逆將會非常耗時間，造成用戶體驗(yàn)差，又因?yàn)椴蓸狱c(diǎn)的不精確性，所以要求插值于每一個型值點(diǎn)并不是很合理，故提出改進(jìn)的方法，即可直接以型值點(diǎn)（采樣點(diǎn)）作為三次B樣條曲線的控制頂點(diǎn)，避免了反求控制點(diǎn)帶來的龐大的計算量?！舅惴ㄋ摹恳阎椭迭c(diǎn)共n+1個，為了生成的B樣條曲線經(jīng)過兩個端點(diǎn)，還得在兩個端點(diǎn)外分別加入一個虛擬點(diǎn)，記為。這樣分段B樣條的個數(shù)為n條，記為：Step 1： 記Step 2：根據(jù)每一段的控制頂點(diǎn)，擬合出一條三次的B樣條曲線。即：Fig.7 算法四結(jié)果示意圖3.5 兩種BSpline插值的比較1）兩種算法都精確插值了兩端端點(diǎn)，且都是分片二次連續(xù)的。2）算法四比算法三的計算量要少的多，但算法三插值于每一個采樣點(diǎn)，而算法四只插值于兩個端點(diǎn)。3）在采樣誤差大的情況下，算法四優(yōu)于算法三，但如果采樣比較精確，從貼近原始數(shù)據(jù)講，則算法三比算法四好。四、Bezier曲線與BSpline曲線的區(qū)別和聯(lián)系B樣條方法是在保留Bezier方法的優(yōu)點(diǎn)，同時克服其由于整體表示帶來不具有局部性質(zhì)的缺點(diǎn)，及解決在描述復(fù)雜形狀時帶來的連接問題下提出來的。在樣條曲線取重節(jié)點(diǎn)的情況下，BSpline曲線退化成Bezier曲線。他們的區(qū)別主要有以下4點(diǎn)：1、Bezier曲線的基函數(shù)次數(shù)等于控制頂點(diǎn)數(shù)減1。B樣條曲線基函數(shù)次數(shù)與控制頂點(diǎn)數(shù)無關(guān)。2、Bezier曲線的基函數(shù)是Beinstein基函數(shù)，它是個多項式函數(shù)。B樣條曲線的基函數(shù)是多項式樣條。3、Bezier曲線是一種特殊表示形式的參數(shù)多項式曲線。B樣條曲線則是一種特殊表示形式的參數(shù)樣條曲線。4、Bezier曲線缺乏局部性質(zhì)，即修改任意一個控制頂點(diǎn)都會對曲線整體產(chǎn)生影響。B樣條曲線具有性質(zhì)，即修改一個控制頂點(diǎn)只會對幾段曲線產(chǎn)生影響。五、上述算法在實(shí)際血管提取中的應(yīng)用實(shí)際證明，四種算法對原數(shù)據(jù)點(diǎn)的插值（擬合）效果都很好，但由實(shí)際問題提出的四點(diǎn)要求，且實(shí)際采樣點(diǎn)的誤差是肯定存在的，而算法四因其具有計算簡單，光滑性高等特點(diǎn)，要優(yōu)于其他的算法。下圖是在取相同的起始點(diǎn)，終點(diǎn)的情況下，四種算法插值（擬合）的結(jié)果。Fig.8 四種算法擬合血管采樣點(diǎn)的結(jié)果從Fig.8中，可以看出：四種算法都插值于端點(diǎn)。算法一、三更多的插值采樣點(diǎn)，而算法二、四只是貼近于原始采樣點(diǎn)，更符合實(shí)際應(yīng)用。而對