基于轮廓重心参数调整的Bezier曲线拟合方法

郦悦华，吴继伟

基于轮廓重心参数调整的Bezier曲线拟合方法

郦悦华，吴继伟

传统的3次Bezier曲线拟合方法在拟合汉字轮廓曲线时，迭代次数多，效率较低。针对拟合的效率，设计了一种基于3次Bezier曲线的汉字曲线轮廓拟合新方法。该方法的核心是简单高效的参数迭代算法。在3次Bezier曲线控制点的求取方法上，采用最小二乘法拟合；在参数的优化问题上，用过型值点重心的直线与拟合曲线间的交点求解参数，迭代优化参数取值。该迭代算法占用资源少，运算量小，计算简便。实验结果表明，针对一般型值点和汉字轮廓特征点的曲线拟合，在相同精度要求下，该算法迭代次数少，收敛速度快，能达到更好的拟合效果。

Bezier曲线拟合；最小二乘法；型值点重心迭代；汉字曲线轮廓描述

0 引言

在图形工程实践中，经常需要将由型值点用参数多项式曲线来逼近，从而达到容易造型和修改的目的。目前，型值点拟合的基本方法是采用3次Bezier曲线拟合。Bezier曲线以其优良的性质，在诸多形式的参数多项式曲线中独树一帜，一经问世，就受到工业界的重视和广泛应用。用Bezier曲线拟合型值点的算法，能使拟合后的曲线光顺。文献[1-3]提供了大量的实践证明，这种方法是完全可行的。

目前，汉字曲线轮廓字形广泛使用3次Bezier曲线描述。原因有二：一是Bezier曲线具有良好的直观性和局部修改性，方便交互式地修改曲线的形状；二是Bezier曲线与其它曲线一样也具有仿射变换不变性，这使得对字形作任意放大和缩小变换时，曲线均能精确地描述字形轮廓。汉字曲线轮廓字库连续性好，字形美观而且变化丰富，缩放后可保证文字质量，汉字曲线轮廓字库需要较少的存储空间，在工业界广泛应用[4-6]。

用Bezier曲线拟合型值点的传统方法是参数型最小二乘法，这是当前主要的拟合技术[7-12]。3次Bezier曲线C(t)的参数方程是公式（1）：

参数型最小二乘法拟合首先要得到参数t的取值。在首次拟合时，参数t的取值用累加弦长法求解出。由于仅靠一次拟合的精度不能满足要求，需要在前一次拟合的基础上优化参数t，以达到预期的精度要求。而参数的优化方式影响到迭代次数和迭代精度。传统的做法是找到拟合曲线上对应于型值点距离最近的一点，以这一点的t值作为下一次迭代的参数，持续迭代过程，直至误差精度满足要求后迭代结束，这种方法为最短距离迭代算法。

最短距离迭代算法进行曲线拟合时存在以下两个问题：

（1）参数的求解公式复杂，需要求解的参数多，占用资源，不够快速，给算法的设计带来难度，并且计算量大。

（2）用累加弦长法首次求解参数t，欲达到目标精度，收敛较慢，迭代次数较多。

针对以上各种算法的不足，本文提出了一种更为简单的迭代方法，使用三次Bezier曲线拟合型值点，基于型值点轮廓重心的参数进行迭代，达到更好的拟合效果。通过实验试算，本文提出的方法应用于汉字轮廓特征点的拟合问题上，取得了理想的效果。

1 方法和技术

首先，假设型值点均位于起始点和终止点连线的同一侧，在实际情况中，位置处于同一侧的型值点总是可以通过分割型值点集得到。

先做如下的定义：

定义1相邻的型值点两两间用线段连接，形成的多边形叫型值点多边形。

定义2型值点多边形的重心坐标叫型值点轮廓重心。

定义3相邻的两个型值点与型值点重心构成的三角形的面积为型值点权值如公式（2）：

1.1 型值点轮廓重心的计算

（1）将型值点多边形分割成三角形

连接起始点Q0和终止点Qn，得到一条线段。过型值点做线段的垂线，垂足分别为，并求解垂足的坐标。连接相应的线段，这样就把具有n个顶点的多边形分割为个个三角形。

（2）对分割后的每个三角形，计算它们相应的的重心坐标和面积。

三角形的面积可由公式（4）求得公式（4）：

图1 型值点多边形重心

如图1所示，在得到每一块三角形的重心和面积后，计算多边形的重心。由公式（5）得到多边形的重心坐标如公式（5）：

1.2 基于最小二乘法的三次Bezier 曲线拟合

三次Bezier曲线由4个点控制点来描述，0P是起点，1P是第一控制点，2P是第二控制点，3P是终点。其中起点坐标，终点的坐标是待定点的坐标是。

（1）记Ci是拟合曲线上对应于参数ti的点如公式（6）：

（2）用最小二乘法拟合，要求拟合曲线上的点Ci与型值点之间的距离的平方差之和达到极小。即公式（7）：

1.3 参数ti的优化问题

进行最小二乘法拟合时，必须先确定参数ti的值。首次拟合时，传统方法采用累加弦长法，将型值点间的弦长累加作为参数ti。本文用型值点权值wi来确定参数ti的值。相比于累加弦长法，虽然按权值确定参数ti的初始误差较大，但迭代收敛速度快，误差能很快收敛，最终效果优于累加弦长法。

得到参数ti的值后，用最小二乘法进行第一次拟合。之所以要先估计参数ti，是因为在首次拟合给定的轮廓段的型值点时，没有得到型值点的拟合曲线，无法求出曲线弧长。因此第一次拟合时，按型值点权值求出参数ti的值，再用参数型最小二乘法去拟合给定型值点，这种方法是合理的，但由于是估计值，显然不够精确，因此最短距离法和文章方法在首次拟合时都不能得到较好的拟合效果。仅仅一次拟合效果不理想，所以有必要优化参数ti的取值。在参数ti的取值的优化技术上，传统的做法是求解出型值点与拟合曲线距离最近的点的ti值，作为下一次迭代的参数。本文提出了一种基于型值点重心的参数ti优化方法。此方法的优点是计算量小，拟合速度快，拟合误差小。

已知求得的Bezier曲线C(t)，(0≤t≤1)，离散型值点列如公式（9）：

3 总结

本文提出了基于型值点重心的三次Bezier曲线拟合算法。算法基于型值点重心计算参数，迭代更新控制点的位置。算法相当简单并且十分有效。本文介绍的拟合算法，经过试算验证和软件模拟，这些方法在理论上是可行的。

基于传统的最短距离的迭代方法计算量大、计算复杂。在新算法中， 各个型值点与重心之间的直线斜率都只进行一次计算， 计算量小， 对于点数庞大的型值点集， 减少了计算的繁琐， 避免了大量求解高次多项式根的问题， 减少了空间数据的存储量， 节省了计算时间， 具有一定的实用价值。

在汉字曲线轮廓特征点的拟合问题上，本文方法得到了很好的效果。采用本方法拟合汉字曲线轮廓，可以达到均方误差和迭代次数上的更优选择，是一种理想的解决办法。展示的结果也表明算法能产生优化的拟合曲线，算法在汉字曲线轮廓拟合上有着广阔的应用前景。但是在接近直线分布型值点上的拟合性能不好，本算法暂时还不能应用于直线分布的型值点拟合。

[1] Deepak C. Srivastava, VipulRastogi, RajitGhosh. A rapid Bézier curve method for shape analysis and point representation of asymmetric folds[J]. Journal of Structural Geology, 2010 (32):685-692.

[2] M.Sarfraz , A.Masood. Capturing outlines of planar images using Bezier cubics[J] . Computers& Graphics, 2007 (31):719–729.

[3] AsifMasood, Muhammad Sarfraz. Capturing outlines of 2D objects with Bézier cubic approximation[J]. Image and Vision Computing, 2009 (27):704–712.

[4] 李培培. 曲线造型中关于拟合、参数化及形状优化问题的研究[D].山东大学,2012.

[5] 陈登梅. 曲线字库自动生成方法的研究[D].山东大学,2007.

[6] 严红娟. 女书曲线轮廓字形自动生成方法研究与实现[D].中南民族大学,2013.

[7] 张明星. 广义Bézier曲线与B样条曲线的研究[D].中南大学,2013.

[8] 杨林英. Bézier曲线的拼接及扩展[D].西北师范大学,2013.

[9] 张娴. 基于曲率分析的三次B-spline曲线保形采样方法研究[D].西北农林科技大学,2012.

[10] 张超,王文静. 一种改进的折线转分段Bezier曲线的拟合方法[J]. 测绘通报,2011,12:72- 74.

[11] 王家润,赵南松,华文元,等. 分段连续三次Bezier曲线控制点的构造算法[J]. 计算机工程与应用,2010,22:190-193.

[12] 张娴,张志毅,田素垒,等. 基于曲率分析的三次Bezier曲线采样方法的研究[J]. 计算机工程与应用,2013,05:160-162+253.

A Bezier Curve Fitting Method Based on Parameter Agustment of Contour Center

Li Yuehua, Wu Jiwei
(Department of control science and Engineering, Tongji University, Shanghai 201804,China)

When Fitting Chinese outline outline curves, the traditional cubic Bezier curve fit method is short fortoo many iterations and low efficiency. In response to the curve fit efficiency, the paper designs a new algorithmtofit Chinese outline fonts basedoncubic Bezier curve. The key of this method is a parameter iterative algorithm which is simple and efficient. Least-squares solution is applied to get the control points of cubic Bezier curves. In terms ofparameters optimization, intersections of lines that cross the contour center and fitting curve are used to calculate parameter through iterative optimization. Compared with traditional curve fitting method, this method has lowcost incalculation and is easy to compute. From the experiments with common data points and Chinese outline fonts, it is found that the results ofthe proposed method is better with less iterationsand faster in the speed of convergence rate under the same precision condition.

Bezier Curve; Least-Squares Solution; Contour Center Iteration; Chinese Outline Fonts

TP311.13

A

2014.11.12）

1007-757X(2015)01-0017-05

上海市科委科技攻关项目（11dz1505202）

郦悦华（1989-），男，同济大学，控制科学与工程系，硕士研究生，研究方向：计算机软件及图像处理，上海，201801

吴继伟（1974-），男，同济大学，控制科学与工程系，讲师，研究方向：图像处理及模式识别，数据挖掘，上海，201801