基于分塊矩陣求導的Bézier曲線降階方法

李建東，楊 艷

(呂梁學院 數學系，山西呂梁 033000)

基于分塊矩陣求導的Bézier曲線降階方法

李建東，楊 艷

(呂梁學院 數學系，山西呂梁 033000)

Bézier曲線的降階逼近有著實際應用價值，但是逼近程度會受端點約束條件的影響。提出了基于分塊矩陣求導的降階逼近方法。該方法能產生降多階，且滿足端點約束條件的顯式表達式。最后將中點分割法與分塊矩陣求導的降階方法結合并應用到數值實驗中，驗證了該算法的優越性。

Bézier曲線;降階;分塊矩陣求導;中點分割

Bézier曲線的降階有著重要的實際應用價值。例如在CAD系統間進行數據交換時，由于不同的CAD系統對多項式的次數限制不同，因此需要將多項式的次數調整相同，也就是對曲線的階進行統一。而統一的方法一般有2種:升階和降階。雖然Bézier曲線有升階性質，可以得到精確的結論，但是卻使系統變得復雜，導致可靠性降低。相反，降階方法不僅可以提高計算效率以及系統的穩定性和可靠性，而且對于數據壓縮也有重要的作用。

對于Bézier曲線降階的研究，目前已有較成熟的技術。早在1972年Forrset給出Bézier曲線的定義后，就提出了Bézier曲線的降階算法。本文在對有關降階逼近主要方法深入分析的基礎上，針對Bézier曲線滿足端點任意階連續性的降多階逼近進行了研究。

定義1［2］設pi∈Rd，d=2，3;i=0，1，2，…，n，Bn

i(t)為n次Bernstein基函數。若對n次Bézier曲線，

則稱這種降階為在該范數下帶(r，s)次端點插值條件的Bézier曲線降n－m階逼近。

1 基于分塊矩陣求導的Bézier曲線降階方法

本節討論的降階方法中，用式(5)定義距離。

1.3 基于中點分割的分段逼近

以上幾種情況中誤差均由式(7)計算得到。如果誤差結果比控制值大，可以將曲線分為兩段，直到誤差小于控制值。

依據Bézier曲線割角的產生辦法可得出:對曲線的分段降階逼近，實質上是由分割成的兩段子曲線分別做次數相同的降階，再拼到一起的。此處要求分割點也達到要求的端點連續性。依據擾動約束方法［5］的理論分析，降階的誤差與由原曲線本身所決定的控制因子‖Δnp0‖有關，同時論證了隨著分割的進行，該因子會減小。由此保證了分割會使逼近誤差降低［9］。

算法如下:

步驟1 輸入誤差限e、最多分割次數k與原曲線的控制頂點。

步驟2 再用分塊矩陣求導的方法，按照式(11)計算出初步逼近曲線的控制頂點，并計算誤差。如果誤差大于e，且分段次數小于k，則執行步驟3，否則執行步驟4。

步驟3 由Bézier曲線的de Casteljau算法計算原曲線中點分割點，同時計算得到2條子曲線的控制頂點，對2組控制頂點分別執行步驟2。

步驟4 輸出各子曲線的控制頂點，并繪制與原曲線的比較圖像。

2 數值實驗

實例 以平面上16個點(0，0)，(1.5，－2)，(4.5，－1)，(9，0)，(4.5，1.5)，(2.5，3)，(0，5)，(－4，8.5)，(3，9.5)，(4.4，10.5)，(6，12)，(8，11)，(9，10)，(9.5，5)，(7，6)與(5，7)為控制頂點的15次Bézier曲線用分塊矩陣求導方法降到m階并且保端點(r，s)階連續。圖1和2中，虛線為原Bézier曲線，實線為降階后的曲線，d為誤差。圖2為中點分割后的曲線逼近(其中*號為分割點)，圖像看起來重合。當保端點(0，0)階連續時，中心分一次，誤差由0.016 3降為10－4級;保端點(2，2)階連續時，中心分了2次，誤差由2.025 4降到10－5級，并且中間的2段誤差均達到10－8級。

圖1 分塊矩陣求導方法分別降了1階和9階不保端點插值的逼近曲線

圖2 中點分割后再用矩陣分塊求導的保端點不同連續階的逼近曲線

3 結束語

提出了基于分塊矩陣求導的方法，該方法的優點在于將原曲線分為3部分，但沒有各自獨立，解決了端點約束與降多階的矛盾，并且可以得到顯式的表達式。同時結合了中心分割的分段逼近，使之能夠達到任意精度。

本文僅討論了事后誤差，沒有找到誤差上限，不能進行事先誤差估計。如果有先驗誤差，就可以避免盲目降階，從而可以先對原曲線進行分割，再對子曲線求先驗誤差，直到小于事先給定的控制值，再實行降階。

［1］ 王仁宏，李崇君，朱春鋼.計算幾何教程［M］.北京:科學出版社，2008.

［2］ 郭清偉，朱工勤.Bézier曲線降多階逼近的一種方法［J］.應用數學與計算數學學報，2003，17(2):49－54.

［3］ 劉慶生.Bézier曲線可降階條件及其降階逼近［J］.同濟大學學報，2001，29(4):470－473.

［4］ Lu L Z，Wang G Z.Application of ChebyshevⅡ－Bernstein basis transformations to degree reduction of Bézier curves［J］.Journal of Computational and Applied Mathematics，2008，221(1):52－65.

［5］ Hu S，Sun J，Jin T，et al.Approximate Degree Reduction of Bézier Curves［J］.Tsinghua Science and Technology，1998，3(2): 997－1000.

［6］ 陳國棟，王國瑾.基于廣義逆矩陣的Bézier曲線降階逼近［J］.軟件學報，2001，12(3):435－439.

［7］ 滿家巨，胡事民，雍俊海，等.Bézier曲線的降階逼近［J］.清華大學學報:自然科學版，2000，40(7):117－120.

［8］ 陸利正，胡倩倩，王國昭.Bézier曲線降階的迭代算法［J］.計算機輔助設計與圖形學學報，2009，21(12):1689－1693.

［9］ 曾輝.基于中心分割的Bézier曲線降階［D］.大連:大連理工大學，2008.

(責任編輯 何杰玲)

Method for Degree Reduction of Bézier Curve Based on Partitioned Matrix Derivation

LI Jian－dong，YANG Yan
(School of Mathematics，Lyuliang University，Lyuliang 033000，China)

The approximation of degree reduction to Bézier curve has its practical application value but is limited by constrained condition of endpoints.It comes up a new method for degree reduction approximation based on partitioned matrix derivation.This new method can produce explicit formulation with multi－degree reduction and satisfies constrained condition of endpoints.Finally combining mid－point segmentation with partitioned matrix’s derivation and putting them into numerical experiment show the advantages of this algorithm.

Bézier curve;degree reduction;partitioned matrix derivation;midpoint subdivision

O174

A

1674－8425(2014)07－0142－05

10.3969/j.issn.1674－8425(z).2014.07.028

2014－03－25

呂梁學院科研項目(JYYB201304)

李建東(1978—)，男，山西方山人，碩士，講師，主要從事微分方程及其應用研究。

李建東，楊艷.基于分塊矩陣求導的Bézier曲線降階方法［J］.重慶理工大學學報:自然科學版，2014(7): 142－146.

format:LI Jian－dong，YANG Yan.Method for Degree Reduction of Bézier Curve Based on Partitioned Matrix Derivation［J］.Journal of Chongqing University of Technology:Natural Science，2014(7):142－146.