沈莞薔，王宏凱

Bézier曲線的多項式重新參數(shù)化檢測

沈莞薔，王宏凱

(江南大學理學院，江蘇 無錫 214122)

研究了一種用于精確檢測一條Bézier曲線的次數(shù)是否可以通過多項式重新參數(shù)化降低的算法。該算法對任意一條Bézier曲線，將重新參數(shù)化前后的基函數(shù)的關系用方程組的形式表達，但不需要解方程，而是通過系數(shù)表示的金字塔算法直接計算，可以精確求出用于重新參數(shù)化的多項式和降低次數(shù)后的Bézier曲線的控制頂點，并且該重新參數(shù)化的多項式在相差一個線性變換的前提下是唯一的。通過實例應用，該算法運算速度較之前的算法快。

Bézier曲線；多項式；重新參數(shù)化；基函數(shù)；金字塔算法

Bézier曲線憑借優(yōu)良的造型性質，在幾何設計中有著重要應用[1-2]。由于在參數(shù)曲線中，參數(shù)選擇的多樣性，有些參數(shù)化會使得一些Bézier曲線出現(xiàn)不適當?shù)那闆r[3]，一旦使用了合適的參數(shù)化，Bézier曲線可以精確轉換為低次的Bézier曲線，相比高次Bézier曲線，低次Bézier曲線具有數(shù)據(jù)量少[4]、計算更快[5]、更好的系統(tǒng)兼容性[6-7]、對多邊形曲線的控制性更強[8-9]等優(yōu)點。

已有文獻在不改變曲線參數(shù)化的情況下，對Bézier曲線降次，如文獻[10]通過選取合適的函數(shù)，在不受拐角插值約束的條件下，實現(xiàn)了形狀參數(shù)可調(diào)的SG-Bézier曲線的降次；文獻[11]提出一種基于約束對偶Bernstein多項式，是計算降次Bézier曲線控制頂點的方法；文獻[12]用L2范數(shù)連續(xù)分段多項式曲線求解有理Bézier曲線逼近問題；文獻[13]利用Bézier曲線本身的升次性質，結合廣義逆矩陣的最小二乘理論，給出了一種新的降次逼近方法；文獻[14]利用3次PH曲線來逼近代數(shù)曲線；文獻[15]基于端點約束的Bézier曲線降次方法，為了保證曲線的平滑程度，在常規(guī)目標函數(shù)的基礎上，提出了附加平滑項的Bézier曲線生成方法；文獻[16]闡述了以高階導消失為B樣條曲線自身退化的條件，利用約束優(yōu)化逼近原曲線。

事實上，一條多項式曲線有許多種參數(shù)形式，有些高次的曲線通過重新參數(shù)化可精確的以低次的形式表示，文獻[3]將原高次曲線的參數(shù)化稱為不適當?shù)摹＿@種改變參數(shù)化降階的相關工作主要有：文獻[17]和文獻[3]使用類似求最大公約式的輾轉相除法，檢測多項式曲線參數(shù)化是否適當；文獻[18]使用分段線性參數(shù)，對Bézier曲線進行降次，取得了更好的逼近效果；文獻[19]給出了2條Bézier曲線完全重合的條件。

針對Bézier曲線參數(shù)化是不適當[3]的情況，本文給出了一種算法，即檢測Bézier曲線的參數(shù)化是否是不適當?shù)?，如果是，將給出重新參數(shù)化后的Bézier曲線的控制頂點和相應的重新參數(shù)化多項式；同時與文獻[3]的算法相比，并經(jīng)實例應用對比表明，本文算法有更快的運算速度。

1 理論分析

如果()是DRPR曲線，那么()的LD的Bézier曲線可記為

與文獻[3]相同，本文將Bernstein基轉化為冪基的形式?；D換有2個目的：①為了排除在Bernstein基下最高次項系數(shù)為0的自身退化的情況；②在冪基形式，利用高次基(包括低次基作為子集)以及同次基中函數(shù)的次數(shù)差異性，在后續(xù)構造金字塔時，避免進行反求方程。

檢驗式(4)是否為DRPR，有

其中，=[01···]。由式(4)和式(6)，以及的線性無關性，得到

1.1 重新參數(shù)化多項式

重新參數(shù)化多項式()具有如下性質。

性質 1.如果()是曲線式(4)的重新參數(shù)化多項式，則()的任意線性變換，如()+(,?,且≠0)，也是式(4)的重新參數(shù)化多項式。

證明：由題意知

其中

證畢

證明將在1.3節(jié)給出。

1.2 基表示矩陣

其中，①是考慮多項式S()的次數(shù)得到的，=0,1,···,；②是顯然的；③是S≠0的結果；④可以由①通過數(shù)學歸納法證明得到。

性質 4. 在曲線式(4)為DRPR的情況下，如果次重新參數(shù)化多項式()確定，那么矩陣是唯一的。

1.3 方程的解

根據(jù)性質3的①，式(7)中的方程組為

在式(9)中，初始的行，每行有個方程，最后一行有1個方程，由該方程組可以依次解出,–1,···,1,0。

根據(jù)性質1，不失一般性，令()中0=0，S=1。有a=0 (0≤<≤)，且a,ik=1 (0≤≤)，根據(jù)性質3的②，若式(4)為DRPR，則有

滿足式(9)的第一行的第一個方程和最后一行的方程。

命題1. 如果式(4)為DRPR，那么向量–1,···,–k+1均為的倍數(shù)，其中為重新參數(shù)化多項式的次數(shù)。

該命題給出了一種求的方法，由于在初始的Bernstein基形式(1)中，單點和直線段的情況均很容易判斷，所以=的情況可以單獨考慮。另外，=1的情況不會降低式(4)的次數(shù)。所以，只考慮的非平凡約數(shù)。當式(4)中的給定時，有如下性質。

性質5.如果式(4)是DRPR，那么任意可用于重新參數(shù)化的多項式的次數(shù)，均要滿足：

①是的一個非平凡約數(shù)；

②≤，其中是滿足–1,–2,···,–l+1都是的倍數(shù)這個條件的最大值。

此外，希望找到式(4)的MD曲線，即取最大值，在下一節(jié)的算法中，的取值從大到小列出。同時，如果不存在滿足條件的，則式(4)為非DRPR。

為了解出S,=1,2,···,–1，仍然考慮式(9)的第一行方程，對于的每一個候選值，–1,–2,···,–l+1均為的倍數(shù)，并且≠0，記向量中首個不為0的分量為，對應的分量為，其中,,，根據(jù)式(9)的第一行方程可得

性質3的②與④表明，通過金字塔算法可計算a，其算法路徑為

即

同樣的，當=–2,–3,···,1，存在

其中，c,n–k+j為(S+1t+1+S+2t+2+···+St)展開式中t–k+j前的系數(shù)。因此，c,n–k+j的值可以通過a用同樣的金字塔算法得出，所以有

其中

并且00=1，根據(jù)上述計算可看出：S,=–2,–3,···,1可通過S+1, S+2,···,S得到。所以性質2的證明如下：

證明：若式(4)為DRPR，由于性質1，如果0和S都是固定的，那么，S,=–2,–3,···,1均是唯一的，因此，性質2成立。

證畢

計算其余，當=–1,–2,···,1，根據(jù)式(9)的第一列方程，依次有

另外，得到后，式(9)的第+1–行中就沒有未知數(shù)了。然后檢查方程是否成立，排除非DRPR的情況。

目前曲線式(4)有2種情況：

(1) 非DRPR；

(2) DRPR，可求得式(4)的MD曲線的控制頂點矩陣，以及重新參數(shù)化多項式()。

最后，用一個簡單方法控制重新參數(shù)化多項式()的值域，使得該值域為[0,1]，記，分別為()在[0,1]的最大值和最小值，則

并且

其中，為式(8)中的矩陣，且=1/(–)，=–/(–)。

2 算 法

本文算法需首先考慮單點和直線段的特殊情況。

2.1 特殊情況

在Bernstein基形式(1)下直接考慮特殊情況。

并且

2.2 算法實現(xiàn)

算法：檢測Bézier曲線是否為DRPR。

(1) 若為單點，可根據(jù)輸入的控制頂點個數(shù)進行判斷。

(2) 若是共線，可根據(jù)輸入的控制頂點個數(shù)進行判斷。

步驟4. 對于的每一個候選值：

(2) 根據(jù)式(11)，依次得到a,j,=–1,–2,···,–+1的值。

(3) 根據(jù)式(12)，得到S–1的值，根據(jù)式(13)，依次計算得到S–2, S–3,···,1的值。

(4) 根據(jù)性質3中的②和④，計算出其余的a,=1,2,···,–1,=,+1,···,，當=時，=,+1,···, (–1)。

(5) 當=–1,=–2, ···,1時，

①根據(jù)式(15)，計算。

(6) DRPR=T，根據(jù)式(3)得到()，跳出當前循環(huán)。

3 實 例

實驗環(huán)境見表1，每個實例中，用紅色空心圈表示輸入的Bézier曲線()的控制頂點，用藍色虛線表示對應的控制多邊形，用藍色粗實線表示曲線()，用綠色方塊表示Bézier曲線()的控制頂點，用粉色虛線表示對應的控制多邊形，用粉色細實線表示曲線()。

表1 實驗環(huán)境

例1．輸入Bézier曲線的控制頂點

經(jīng)算法得DRPR=，重新參數(shù)化多項式

其中，MD的Bézier曲線的控制頂點為：，如圖1所示。

圖2 平面4次非DRPR曲線

例3. 輸入Bézier曲線的控制頂點：

經(jīng)算法得DRPR=。重新參數(shù)化多項式

其中，MD的Bézier曲線的控制頂點為：，如圖3所示。

例4. 輸入Bézier曲線的控制頂點：

經(jīng)算法得DRPR=T，重新參數(shù)化多項式為

曲線()在Bernstein基下控制頂點為：

圖4 平面6次DRPR曲線

Fig. 4 DRPR planar curve of degree 6

最后將本文算法與文獻[3]的算法進行比較。文獻[3]的算法，輸入和輸出是冪基下的多項式曲線的頂點，所以本文對比的時間是從曲線轉換為冪基形式之后(即步驟2)開始計時，到程序輸出重新參數(shù)化多項式()和冪基形式下頂點(即步驟5)結束計時。時間對比見表2。

表2 算法運行時間對比(s)

4 結束語

本文給出的算法可以用來判斷任意一條Bézier曲線是否為DRPR，若是DRPR，可以精確求出該曲線的MD的Bézier曲線的控制頂點，以及相應的重新參數(shù)化多項式。

本文的算法用于精確判斷曲線是否為DRPR的情況，但是，大部分的Bézier曲線均是非DRPR的。在后續(xù)的工作中，將研究給定Bézier曲線的近似DRPR逼近算法，即通過控制頂點微小擾動，使得非DRPR曲線變?yōu)镈RPR曲線。

[1] 王國瑾, 汪國昭, 鄭建民. 計算機輔助幾何設計[M]. 北京: 高等教育出版社, 2001: 249-250. WANG G J, WANG G Z, ZHENG J M. Computer aided geometric design[M]. Beijing: Higher Education Press, 2001: 249-250 (in Chinese).

[2] 郭大勇, 成佳頤. 基于二項式系數(shù)設計矩陣的Bézier 曲線擴展[J]. 圖學學報, 2014, 35(4): 511-517.GUO D Y, CHENG J Y. Extension of Bézier curve based on the design of matrix using binomial coefficient[J]. Journal of Graphics, 2014, 35(4): 511-517 (in Chinese).

[3] SEDERBERG T W. Degenerate parametric curves[J]. Computer Aided Geometric Design, 1984, 1(4): 301-307.

[4] 胡倩倩, 王國瑾. 球域Bézier曲面的精確邊界及其多項式逼近[J]. 浙江大學學報: 工學版, 2008, 42(11): 1906-1909. HU Q Q, WANG G J. Exact boundary of ball Bézier surface and its approximation by polynomial form[J]. Journal of Zhejiang University: Engineering, 2008, 42(11): 1906-1909 (in Chinese).

[5] QIAO Z F, HU M, TAN Z H, et al. An accurate and fast method for computing offsets of high degree rational Bézier/NURBS curves with user-definable tolerance[J]. Journal of Computer Languages, 2019, 52: 1-9.

[6] RABABAH A, IBRAHIM S. Gometric degree reduction of Bézier curves[C]//International Conference on Mathematics and Computing. Heidelberg: Springer, 2018: 87-95.

[7] 胡倩倩. 曲線曲面的兩類幾何逼近與兩類代數(shù)表示[D]. 杭州: 浙江大學, 2008. HU Q Q, Two kinds of geometric approximations and algebraic representations of curves and surfaces[D]. Hangzhou: Zhejiang University, 2008 (in Chinese).

[8] CHEN Y, CAI Y Y, ZHENG J M, et al. Accurate and efficient approximation of clothoids using Bézier curves for path planning[J]. IEEE Transactions on Robotics, 2017, 33(5): 1242-1247.

[9] HAN X L, GUO X. Optimal parameter values for approximating conic sections by the quartic Bézier curves[J]. Journal of Computational and Applied Mathematics, 2017, 322: 86-95.

[10] HU G, QIAO Y, QIN X Q, et al. Approximate multi-degree reduction of SG-Bézier curves using the grey wolf optimizer algorithm[J]. Symmetry, 2019, 11(10): 1242-1260.

[11] GOSPODARCZYK P, LEWANOWICZ S, WO?NY P. Degree reduction of composite Bézier curves[J]. Applied Mathematics and Computation, 2017, 293: 40-48.

[12] ESLAHCHI M R, KAVOOSI M. The use of Jacobiwavelets for constrained approximation of rational Bézier curves[J]. Computational and Applied Mathematics, 2018, 37(3): 3951-3966.

[13] 陳國棟, 王國瑾. 基于廣義逆矩陣的Bézier曲線降階逼近[J]. 軟件學報, 2001, 12(3): 435-439. CHEN G D, WANG G J. Degree reduction approximation of Bézier curves by generalized inverse matrices[J]. Journal of Software, 2001, 12(3): 435-439 (in Chinese).

[14] 壽華好, 江瑜, 繆永偉. 基于三次PH曲線誤差可控代數(shù)曲線等距線逼近算法[J]. 圖學學報, 2012, 33(2): 30-33. SHOU H H, JIANG Y, MIAO Y W. Error controllable algebraic curve offset approximation based on cubic PH curve[J]. Journal of Graphics, 2012, 33(2): 30-33 (in Chinese).

[15] HAN X L, YANG J. Multi-degree reduction of Bézier curves with distance and energy optimization[J]. Journal of Applied Mathematics and Physics, 2016, 4(1): 8-15.

[16] YONG J H, HU S M, SUN J G, et al. Degree reduction of B-spline curves[J]. Computer Aided Geometric Design, 2001, 18(2): 117-127.

[17] SEDERBERG T W. Improperly parametrized rational curves[J]. Computer Aided Geometric Design, 1986, 3(1): 67-75.

[18] CHEN X D, MA W Y, PAUL J C. Multi-degree reduction of Bézier curves using reparameterization[J]. Computer-Aided Design, 2011, 43(2): 161-169.

[19] CHEN X D, YANG C, MA W Y. Coincidence condition of two Bézier curves of an arbitrary degree[J]. Computers & Graphics, 2016, 54: 121-126.

Polynomial reparameterization detection of Bézier curves

SHEN Wan-qiang, WANG Hong-kai

(School of Science, Jiangnan University, Wuxi Jiangsu 214122, China)

An algorithm is presented to determine whether the degree of Bézier curve can be reduced by polynomial reparameterization. In the algorithm, for any Bézier curve, the relation between the basis functions before and after reparameterization is expressed as a system of equations. Instead of solving the equations,the polynomial for reparameterization and the control points of the lower degree Bézier curve can be calculated directly by apyramid algorithm of coefficient reparameterization.In addition,the polynomial for reparameterization is unique to within a scale factor and a constant. Compared with the previous algorithm by examples, this algorithm possesses shorter computational time.

Bézier curve; polynomial; reparameterization; basis function; pyramid algorithm

TP 391.72

10.11996/JG.j.2095-302X.2020040576

A

2095-302X(2020)04-0576-07

2020-01-19；

2020-03-29

29 March，2020

19 January，2020；

國家自然科學基金項目(61772013)；中央高?；究蒲袠I(yè)務費專項基金項目(JUSRP21816)

National Natural Science Foundation of China (61772013); Fundamental Research Funds for the Central Universities (JUSRP21816)

沈莞薔(1981-)，女，江蘇無錫人，副教授，博士，碩士生導師。主要研究方向為計算機輔助幾何設計、計算機圖形學等。E-mail：wq_shen@163.com

SHEN Wan-qiang (1981-), femal, associate professor, Ph.D. Her main research interest covers computer aided geometric design, computer graphics, etc. E-mail：wq_shen@163.com