软件学报
JOURNAL OF SOFTWARE
1999年 第19卷 第3期  Vol.19 No.3 1999



三阶Bzier曲线的三类节点缩减算子
曹锋 张克君
摘　要　研究曲线拟合和编辑中的分段Bzier曲线的简化问题.定义了3类Bzier曲线的节点缩减算子以及基于其上的算法.实现了分段曲线的最简Bézier表示,并给出严格的数学证明.上述方法已被应用到所开发的软件中.
关键词　Bzier曲线,曲线延展,节点,缩减算子,最简Bézier表示.
中图法分类号　TP391
Three Kinds of Node-reduce Operator on 3rd Order Bzier Curve
CAO Feng ZHANG Ke-jun
(National Key Laboratory of Text Processing Institute of Computer Science and TechnologyBeijing University Beijing 100871)
Abstract　 The simplification of Bzier curves in fitting and editing is discussed, three kinds of node-reduce operators are defined, and the algorithms based on them are given in this paper. The simplest Bzier expression can be gotten through the algorithms, and a strict proof is given. These algorithms have been already used in the developing software.
Key words　Bzier curve, extension of curves, node, node-reduce operator, simplest Bézier expression.
　　随着计算机辅助图形设计的迅速发展,人们经常需要将大量的图像数据转化为图形数据,以便于修改与操作.字模图像经扫描后转成TrueType字形,广告设计中草稿的图形化处理等就是应用的实例.图形化处理中最关键的技术就是曲线追踪与最佳拟合.就面向出版方面的应用来说,由于目前国际出版界的标准PostScript支持三次Bézier曲线,经常需要利用三次Bézier曲线来拟合所获得的图像数据,因此,怎样用尽量少的点尽量精确地拟合就成了核心问题.在一般的图形设计与编辑中,也大多利用三次Bézier曲线来表示,如果所用的Bézier曲线有太多的控制点,将会有极大的不便.本文给出了3类Bézier曲线节点缩减算子,高效地实现了Bézier曲线的简化.在方正底纹辅助设计系统中,我们应用了这些技术,取得了比国外同类软件更好的效果.
1 一些概念与记号
　　我们将要研究的是平面上的三次Bézier曲线段(对于更高次的Bézier曲线,可将其转化为三次Bézier曲线段［1］).关于Bézier曲线的一般性质可参阅文献［2,3］.它可以用4个点加以表示.我们以p0,p1,p2,p3来标记,其中p0为起始点,p3为终止点,p1,p2为控制点,p0,p3又称为节点.它的参数方程为
C(t)=(1-t)3.p0+3(1-t)2.t.p1+3(1-t).t2.p2+t3.p3 (0≤t≤1)，
从而集合B1=｛b=(p0,p1,p2,p3)｜p0,p1,p2,p3∈R2｝表示了平面上所有的三次Bézier曲线段.
　　为了方便论述,在本文的某些地方采用了C语言的记号“．”来表示Bézier曲线段中的节点.例如,如果b为Bézier曲线段,即b∈B1,则b．p0,表示b的初始点,b．p1表示b的第1个控制点,其余类推.另外,对于Bézier曲线段b(p0,p1,p2,p3),在不引起歧义的情况下,为简单起见,用来表示；在可能引起歧义的情况下,用来表示.
　　集合Bk=｛bk=(b1,b2,...,bk)｜bi∈B1(i=0,...,k)且bi．p3=bi+1．p0(i=0,...,k-1)｝称为k段连续Bézier曲线.为平面上所有分段Bézier曲线的集合,本文的论述都排除Bézier曲线的退化情形,即4个控制节点共线的情况.
　　定义1.1. Bézier曲线段的延展
如果b1,b2∈B1,且b1为b2的一部分,则称b2为b1的延展.如果还满足
　　（1） b1．p0=b2．p0,即b1,b2有共同的始点,则称b2为b1的正向延展.
　　（2） b1．p3=b2．p3,即b1,b2有共同的终点,则称b2为b1的负向延展.
2 数学基础
　　定理2.1. 延展基本定理
　　若b1,b2∈B1,则b2为b1的正向延展的充分必要条件为:存在k∈（0,1］,使得（这里,我们记b1=(p0,p1,p2,p3),b2=(p′0,p′1,p′2,p′3)）.
　　(1) p′0=p0;
　　(2) -p′0+p′1=(-p0+p1);
　　(3) p′0-2p′1+p′2=(p0-2p1+p2);
　　(4) -p′0+3p′1-3p′2+p′3=(-p0+3p1-3p2+p3).
　　证明:（1） 充分条件.如果b1,b2的控制节点满足上述4个条件,则对于b1上的每一个点t=t0,
Cb1(t0)=(1-t0)3.p0+3(1-t0)2.t0.p1+3(1-t0).t20.p2+t30.p3,
我们均能找到b2上的点,参数t=kt0与之对应.
Cb2(kt0)=(1-kt0)3.p′0+3(1-kt0)2.kt0.p′1+3(1-kt0).k2t20.p′2+k3t30.p′3.
容易验证,Cb2(kt0)=Cb1(t0),故Bézier曲线段b1为b2的一部分,且条件1满足,故b2为b1的正向延展.
　　（2） 必要条件.按照定义,如果b2为b1的正向延展,即为曲线段的一部分.设b1的终止点p3在Bézier曲线段b2上的参数为k,则可得b1的参数方程为
Cb1=(1-kt)3.p′0+3(1-kt)2kt.p′1+3(1-kt).k2t2.p′2+k3t3.p′3.
=(1-t)3p0+3(1-t)2tp1+3(1-t).t2p2+t3p3.
比较t,t2,t3的系数和常数即可知条件(1)～(4)成立.
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　□
　　定义2.1. 如果b2为b1的正向延展,且定理2.1中的k值为t0,则称b2为b1的t0正向延展.
　　为了表述方便,我们定义从Bézier曲线段B1到平面的4个算子D0,D1,D2,D3,设b(p0,p1,p2,p3)∈B1,如果定义
　　D0(b)=p0;
　　D1(b)=-p0+p1;
　　D2(b)=p0-2p1+p2;
　　D3(b)=-p0+3p1-3p2+p3.
那么,定理1可简单地描述为:b1,b2∈B1,则b2为b1的正延伸的充要条件是:存在k∈（0,1］,使得
D0(b2)=D0(b1), D1(b2)=D1(b1), D2(b2)=D2(b1), D3(b2)=D3(b1).
　　命题2.1. 若bk1,bk2,b∈B1,且bk1为b的k1正向延展,bk2为b的k2正向延展,且k1＞k2,则bk2为bk1的k2/k1正向延展（由定理2.1,易证）.
　　命题2.1表明,Bézier曲线段的延展方向是唯一的,不会出现如图1所示的现象.

图1
　　定义2.2. 曲线段（其中b+k为Bézier曲线段b的k正向延展）称为b的完全正向延展曲线.
　　推论2.1. b+上的任一有限连续曲线段均为三次Bézier曲线.
　　对于上面的任一有限连续曲线段c,取足够小的k,使得cbk,由于bk为三次Bézier曲线,故c亦为Bézier曲线.
　　定义2.3. 若b1,b2∈B1,且均为平面上某一完全正向延展曲线的一部分,则称b1,b2为同胞.同胞关系为等价关系,由定义可知,同胞关系满足反身性和对称性.下面验证同胞关系的传递性.
　　命题2.2. 同胞关系为等价关系.
　　下面只需证明同胞关系满足递推性即可.假设b1,b2为同胞,b2,b3为同胞.由同胞关系的定义,b1,b2均在一完全正向延展曲线（设为C+1）上.显然从b1起点（或终点）开始的C+1正向部分即为b+1（如图2所示）.同理,从b2的起点（或终点）开始的C+1那部分曲线即为b+2,由于b+1,b+2均为C+1的一部分,且b+1,b+2均沿C+1无限延伸,故我们有b+1b+2或b+2b+1.对于b+2,b+3,我们也有同样结果,即b+2b+3或b+3b+2.从而总共可能有下列4种情形:

图2
　　（1） b+1b+2,b+2b+3,则b+1b+2b+3,b+1b+3,从而b1,b3均为b+3中的一部分,b1,b3为同胞.
　　（2） b+2b+1,b+3b+2,则b+3b+1,同（1）,我们有b1,b3为同胞.
　　（3） b+1b+2,b+3b+2,则b+1,b+3均为b+2的一部分,从而b1,b3均为b+2的一部分,b1,b3为同胞.
　　（4） b+2b+1,b+2b+3,如果b+1b+3,或b+3b+1,则b1,b3为同胞,下面证明必然有b+1b+3或b+3b+1.假设b+1b+3且b+3b+1,由于b+2为b+1与b+3的共同部分,则记b2=b2(p0,p1,p2,p3),记b+1的起点为pb1,记b+3的起点为pb3,如图3所示.

图3
　　由此可知,为的正向延展,亦为的正向延展.由命题2.1可知,或者为的延展,或者p3pb3为的延展.与所假设的b+1b+3且b+3b+1矛盾.
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 □
3 第1类节点缩减算子及算法
3.1 第1类节点缩减算子N1（精确节点缩减算子）
　　我们定义B2上的第1类节点缩减算子N1如下,对B2上的分段Bézier曲线（b1,b2）,其中b1,b2∈B1,
（1） 如果b1．p3=b2．p0,b1,b2为同胞,且b1与b2在点b1．p3的两侧,则N(b1,b2)=,其中Bézier曲线段ｖ为b+1上b1．p0至b2．p3的那一部分,此时称（b1,b2）可N1合并.
（2） 否则,N1（b1,b2）=（b1,b2）.
3.2 基于结点缩减算子的Bézier曲线段简化算法
　　对属于Bk中的k段Bézier曲线（b1,b2,...,bk）,置Result∈B为空,变量CurB为当前Bézier曲线段,算法描述如下:
　　（1） 置CurB=b1,i=2.
　　（2） 如果i＞k,转(4).
　　（3） 将节点缩减算子N1应用到（CurB,bi）上.
　　（a） 如果N1（CurB,bi）=（CurB,bi）,则将Bézier曲线段CurB添加至Result中,并置CurB=bi,i++;转至（2）.
　　（b） 否则,N1（CurB,bi）可约减为Bézier曲线段b,则置CurB=b,i++;转（2）.
　　（4） 结束,（b1,b2,...,bk）的约简结果存储于Result中.
　　定理3.2.1. 对任意b∈Bk,经过上述算法简化后的分段Bézier曲线的节点数最少.
　　证明:（反证法）设Result（b1,b2,...,bn）为上述算法所得结果,如果存在另一种分段Bézier曲线表示（b′1,b′2,...,b′k）,其段数k＜n.
　　由于Result（b1,b2,...,bn）为上述算法的结果,bi,bi+1不可能成为某一Bézier曲线的相邻两段,否则将会被算法第（3）步所合并.
　　由于k＜n,则至少有一段Bézier曲线b′i(i≤k)跨越了Result中的节点bj的终点.如图4所示,我们有与bj为同胞,为b′i的同胞（b′i为的延展）,b′i与为同胞,与bj+1为同胞.

图4
　　从而由同胞关系的递推性可知,bj与bj+1为同胞,且bj,bj+1在节点bj．p3的两侧,故（bj,bj+1）可被节点缩减算子约简,与Result（b1,...,bn）为算法N1的结果相矛盾.
　　由定理3.2.1,对任意分段Bézier曲线,我们可以利用算法求得最简的分段表示.
3.3 B2上的N1算子的具体实现
　　对B2上的曲线段（b1,b2）,设b1(p0,p1,p2,p3),b2(p3,p4,p5,p6),如果b1,b2可以N1合并,则由定义,p6∈b+1,为的正向延展.
　　设为的1/k正向延展,则由定理1可知,k满足
(-p0+3p1-3p2+p3).k3+(3p0-6p1+3p2).k2+(-3p0+3p1).k+p0-p6=0.
取方程的x方向投影,由卡当公式可求得k.验证上式的y方向投影,若不满足方程,则（b1,b2）不可N1合并,即N1（b1,b2）=（b1,b2）.若满足方程,则表示p6在的完全正向延展线b+1上,求得b+1上Bézier曲线段的控制点p′4p′5.
　　如果p4=p′4,p5=p′5 ,则N1（b1,b2）=.否则,N1（b1,b2）=（b1,b2）.
至此,我们完整地给出了Bézier曲线的最优简化算法.
4 第2、3类节点缩减算子
　　在实际应用中,节点缩减算子N1有着很大的局限性,我们需要引入带误差的节点缩减算子.
4.1 第2类节点缩减算子Nδ2
　　对给定误差δ＞0,对于（b1,b2）∈B2,设b1(p0,p1,p2,p3),b2(p3,p4,p5,p6),由三次方程求出k值
［(-p0+3p1-3p2+p3).k3+(3p0-6p1+3p2).k2+(-3p0+3p1).k+p0-p6］x=0.
若k值之一满足
‖(-p0+3p1-3p2+p3).k3+(3p0-6p1+3p2).k2+(-3p0+3p1).k+p0-p6‖＜δ,
其中‖p‖表示点p到原点的距离,且设b1的k正向延展为b+,终点为p′6,曲线b+的部分(设为b)的控制点为p′4,p′5.如果‖p4-p′4‖＜δ,‖p5-p′5‖＜δ,则Nδ2（b1,b2）= b.否则,Nδ2（b1,b2）=（b1,b2）.
　　第2类算子Nδ2可说是N1的实际应用中的变体.在实际应用中,特别是对Bézier曲线的交互编辑中,还需要保证在曲线光滑的情况下强行缩减节点.对于此类要求,我们给出了第3类节点缩减算子.
4.2 第3类节点缩减算子N3
　　对于（b1,b2）∈B2,我们定义算子N3,设b1=b1(p0,p1,p2,p3),b2=b2(p3,p4,p5,p6).
　　（1） 若存在Bézier曲线段b,且起点为p0,终点为p6,且与（b1,b2）在p0,p6,处有相同的单位切矢与曲率,则N3（b1,b2）=b.
　　（2） 否则,N3（b1,b2）=（b1,b2）.
　　下面讨论算子N3的具体实现.
　　记为b1在起点p0的曲率,为b2在终点p6的曲率.
　　令向量若存在b∈B1,使得N3（b1,b2）=b,则设b的两个控制点为p′1,p′2.由N3定义,可假设
(1)
由曲率相等,我们有
(2)
组可化为一个四次方程求解.若存在正实根L1≥0,L2≥0,则N3（b1,b2）=b（b的控制点可由式(1)求得）,否则,N3（b1,b2）=（b1,b2）.
　　将Nδ2或N3替换算法N1,就得到了基于Nδ2或N3的节点缩减算法.
5 结 论
　　针对实际应用中对分段Bézier化简的需要,我们给出了3类Bézier曲线的节点缩减算子以及基于这3类算子的算法.对于基于N1算子的算法,我们证明了经它化简后的分段Bézier曲线为最简的Bézier曲线表达,为便于实用,我们给出了N1的修正算子Nδ2以及强行缩减算子N3.在实际应用中取得了很好的效果.
　　作者曹锋,1971年生,博士,主要研究领域为彩色系统图形图像处理.张克君,1971年生,博士生,主要研究领域为多媒体系统.
　　本文通讯联系人:曹锋,北京 100871,北京大学计算机科学技术研究所
作者单位：北京大学计算机科学技术研究所文字信息处理技术国家重点实验室　北京 100871
参考文献
［1］Eck M. Least squares degree reduction of Bézier curves. Computer Aided Design, 1995,27(11):845～851
［2］唐荣锡,汪嘉业,彭群生.计算机图形学教程.北京:科学出版社,1994
(Tang Rong-xi, Wang Jia-ye, Peng Qun-sheng. A Course on Computer Graphics. Beijing: Science Press, 1994)
［3］孙家广,杨长贵.计算机图形学(第2版).北京:清华大学出版社,1996
(Sun Jia-guang, Yang Chang-gui. Computer Graphics(2nd ed.). Beijing: Tsinghua University Press, 1996)
（1998-03-03收稿）
