Microcomputer Applications Vol. 26, No.9, 2010 技术交流 微型电脑应用 2010年第26卷第9期
文章编号：1007-757X(2010)10-0037-03
一种简单的二次B样条曲线拟合算法
高剑光
摘 要：针对双圆弧拟合算法绘制一条B样条曲线，需要反复多次计算各坐标分量的3次多项式，计算量大，绘制拟合速度极慢，难以满足实际需要等情况，该算法提出了一种简单的二次B样条曲线拟合算法，该算法提高了B样条曲线的绘制速度，有效地解决了4个点以上控制点的拟合问题。 关键词：双圆弧；B样条曲线；二次曲线；拟合算法 中图分类号：TP311 文献标志码：A （1）
（2）
（ 3）
（4） （5）
（6）
·37·
Microcomputer Applications Vol. 26, No.9, 2010 开发应用 微型电脑应用 2010年第26卷第9期
线gA和gB确定之后，选取不同的θ（即选取不同的公切点）决定了双圆弧的参数。这里选取θ= -a，亦即选取三角形的内心作为公切点。
关于双圆弧拟合，目前国内外常用的方法有两种。内向法和交点法。内向法计算简便，但可能法向误差不能保证符合要求。交点法的法向误差较小，但交点计算复杂，需解四次非线性方程，计算量之大可想而知。实际自由曲线拟合绘制过程中，也常采用3次B样条基函数进行拟合运算，为了使得曲线比用折线来代替要绘制的曲线看上去更光滑，应尽可能多地进行曲线上位置点的拟合计算，这样，绘制一条B样条曲线就需要反复多次计算各坐标分量的3次多项式，其计算量也相当大，绘制拟合速度极慢，难以满足实际需要。
图3 两条插值曲线段打圈情形
2 二次B样条曲线拟合算法
本文提出了一种简单的2次B样条曲线拟合算法，即用两条2次曲线近似一条3次曲线，以期达到计算量小，光滑度也达到要求，提高B样条曲线的绘制速度，适应各应用领域的快速绘制要求。
2.1 算法及其实现过程
通常情况我们是将4点拟合成一条三次B样条曲线，由于3次曲线有拐点，而2次曲线没有。所以对于4点我们不可能拟合成一条2次曲线，而是用2条2次曲线拼接，中间出现一拐点，来近似1条3次曲线。
算法实现过程如下：
2次B样条曲线段参数方程表示为
P(t)=(1-t)^2*A+2*t*(1-t)*B+t^2*C , （0≤t≤1） （7） 显然曲线段从A点出发到C点中止，在A点曲线与直
（如图2所示）
线B-A相切，在C点与C-B相切。
乘系数0.293不是一定要这个值，其实可以用其他参数，
不超过0.5都合适。取这个值是保证正方形角上4点恰好可以拟合成一个圆。
把T1作为目标曲线在P2点处的一阶导矢，T2作为目标
（如图4所示） 曲线在点P3处的一阶导矢：
D1=P2 + T1； （15） D2=P3 + T2； （16） 假设组成目标曲线的两条B样条曲线段为 P1(t)=(A1,B1,C1)； （17）
P2(t)=(A2,B2,C2)； （ 18）
取
A1=P2B1=D1
C1=(D1+D2)/2A2=(D1+D2)/2B2=D2C2=P3
（19）
通过求导易知在连接点导数都是D2-D1，故两曲线段C在D1和D2的中点(D1+D2)/2处相连且一阶导数连续。 2.2 算法运用实例
给定平面上的一列点P1- P2,……, Pn拟合出一条依次经过这些点的二次B样条曲线。将点列前后各延拓一点，成为P0, P1, P2……, Pn, Pn+1，延拓办法为：将P3做线段P1 P2中垂线的镜像，镜像点作为P0，将点Pn-2做线段Pn-1 Pn中垂线的镜像，镜像点作为Pn+1。依次将点列P0, P1, P2……, Pn, Pn+1相邻4点按上面的算法拟合成两条B样条曲线段，所有这些曲线段首尾相连，且在结点处的一阶导数连续，它们构成所需要的目标曲线。（如图4所示）做出了给定平面上4个点P1 ,P2, P3, P4，拟合出依次经过这些点的二次B样条曲线；
(D+D)/23
图2 A、B、C三点控制的曲线段
曲线段由A,B,C 3点控制，将它简记为
P(t)=(A,B,C) （8） 给定平面上4个点P1, P2, P3, P4拟合成2条相连的从P2到P3的2次样条曲线，方法如下：
4
图4 过4点拟合的二次B样条曲线
T1= P3- P1； （9） T1= T1/|| T1||； 单位化 （10） T1= T1*min(||P2- P1||,|| P3- P2||)*0.293； （11） T2= P4- P2； （12） T2= T2/|| T2||； 单位化 （13） T2= T2*min(||P3- P2||,|| P4- P3||)*0.293； （14） 在此缩放是避免两条插值曲线段打圈。（如图3所示）
（如图5所示）做出了经过平面上给定的5个点，拟合
出2次B样条曲线。同样的方法，可以做出经过给定的n个点，拟合出的B样条曲线。
图5 过5点拟合的二次B样条曲线
（下转第41页）
·38·
Microcomputer Applications Vol. 26, No.9, 2010 开发应用 微型电脑应用 2010年第26卷第9期
商品C1 , C2 , C3的记录如表 1 (选客户 U1作为参照 ) : 即经过 Web使用挖掘数据预处理后 ,得到数据集 S10 ={s1，s2，⋯，s 10}：s1=(0, 0, 0) s2=(5, 3, 5) s3=(7, 5, 4) s4= (5, 4, 5) s5=(3,8, 6) s6=(4,8,7) s7=(6,4,6) s8=(1,1,3) s9=(6,3,4) s 1 0=(2,2,4)。
表格3 客户数据描述 [1**********]果在很大程度取决于初始聚类中心的选取，本文依此为出发点，综合考虑距离和密度，提出一种选择K-means初始聚类中心的算法。实验结果表明，改进后的K-means算法，能够消除对初始聚类中心的敏感性，且极大改善聚类结果。应用结果也表明，改进后的K-means算法能更好的应用于实际问题。
参考文献
[1] 郭媛香.聚类算法在 B2C电子商务客户细分中的应用[J].
忻州师范学院学报,2009,25(2):27-29.
[2] 闪四清,陈茵等.数据挖掘[M].北京:清华大学出版
社,2003:101-102.
[3] Fuyuan Cao, Jiye Liang, Guang Jiang. An initialization
method for the K-Means algorithm using neighborhood model[J]. Computers and Mathematics with Applications,2009, 58: 474-483.
[4] Adil M. Bagirov. Modified global k-means algorithm for
minimum sum-of-squares clustering problem[J]s. Pattern Recognition 41 (2008) 3192-3199.
[5] Wei Li. Modified K-means clustering algorithm[C].Image
and Signal Processing, 2008.Volume 4, 27-30 May 2008 Page(s):618 - 621
[6] 王洪春,彭宏.基于模糊C-均值的增量式聚类算法[J].微
电子学与计算机,2007,24 (6) :156 - 158.
[7] 黄光球,王西邓.基于网格划分策略的改进人工鱼群算
法[J].微电子学与计算机,2007,24(7):83 - 86.
(收稿日期：2009-11-16)
复多次计算各坐标分量的3次多项式，计算量大，绘制拟合速度极慢，难以满足实际需要等情况，提出了一种简单的2次B样条曲线拟合算法——采用4点来确定2条2次曲线，用2条2次曲线近似1条3次曲线，既弥补了3次曲线以及双圆弧拟合中计算量大的缺陷，又弥补了2次曲线的不足，更有效地解决了4个以上控制点的拟合问题。
应用改进的K-means算法对上面的数据进行处理，初始聚类中心为s2、s7、s8，得到{s1,s8,s10}∈Z1，{s5,s6}∈Z2，
{s2,s3,s4,s7,s9}∈Z3。与文献[1]的聚类结果相比，本文的聚
类质量要好，将s 1 0 与s 1、s8归为一类，这也与表中的情况相符合。s 1 0显然是购买比较少的客户，在聚类中心的选择上，本文的方法也比文献[1]的方法好，避免将异常点选为聚类的中心。
5 结束语
但聚类的结K-means算法是一种广泛应用的聚类算法，
（上接第38页）
3 算法的比较
用双圆弧拟合离散型值点生成自由曲线，是近年来非圆曲线的零件自动编程与加工中常用的一种数学模型。双圆弧拟合方法以其计算相对简单，总体上一阶光滑，易于局部处理等特点，已得到了较为广泛的应用。但其计算量大。本文讨论的简单的2次B样条曲线拟合算法。采用4点来确定2条2次曲线，用2条2次曲线近似1条3次曲线的方法。既弥补了3次曲线以及双圆弧拟合中计算量大的缺陷，又弥补了2次曲线的不足，具有以下优点：
1、计算量小，快速性。因为拟合采用二次曲线拟合算法，拟合速度较快，而且避免了解大量的方程组，提高了运算速度。
2、光滑性。由于B样条曲线是连续的，且它不通过任何一个控制点（型值点），比Bezier曲线更光滑。
3、局部性。B样条曲线具有非整体性，即改变某一个控制点仅影响其附近的一段曲线，更有效地解决了4个以上控制点的拟合问题。
参考文献
[1] Barsky B A. Computer Graphics and Geometric Modeling
Using Beta-Spline [M].Heidelberg:Springer-Verlag,1988. [2] Hoschek J,Lasser D. Fundamentals of Computer Aided
Geometric Design[M]. Wellesley, MA:A K Peters,1993. [3] 施法中.计算机辅助几何设计与非均匀有理B样条[M].
北京:北京航空航天大学出版社,1994,228-255.
[4] 王沫然.MATLAB与科学计算（第2版）[M].北京:电子
工业出版社,2003.
高校应用[5] 虞铭财,杨勋年,汪国昭.整体最优双圆拟合[J]．
数学学报A辑,2004,19(2):225-232.
[6] 苏步清,刘鼎元.计算几何[M].上海;上海科技出版社,
1981:121-140.
[7] 阎童,王琦.双圆弧拟合在轮廓仿真加工中的应用[J].小
型微型机算机系统,1998,19(10):57-60.
4 结语
本文针对双圆弧拟合算法绘制一条B样条曲线需要反
(收稿日期：2009-12-30)
·41·
Microcomputer Applications Vol. 26, No. 10, 2010 ABSTRACTS & KEY WORDS 微型电脑应用 2010年第26卷第10期
estimation algorithm based on simulation. It shows that the improvement of OFDM system performance is at the expense of the complexity system. Key Words: OFDM; Channel Estimation; Pilot
Design and Implementation of Windows Server Performance Monitor……………………………………………………………（22） Jiang Yilian (ShanXi Radio and TV University, Technology Department, Xian 710068, China)
Abstract: This paper mainly introduces a windows server performance monitor system, which is a subsystem of IT resource management system. The system can monitor the performance of server in real time, and provides the graphics display and alarm of the performance data when they beyond the limitation. The system has three layers, and its chief business is implemented in web server. In addition, this paper introduces the key techniques which involve in implementation of system: data collection, communication and graphics display and so on. The techniques which are introduced in the paper can be used for reference in developing semblable software. Key words: Windows Server; Performance Monitor; PDH
Estimation and Simulation of Time-varying Coefficient β Based on Kalman Filter………………………………………………（25） Mei Ting, Li Jianxun(Department of Automation, Shanghai Jiaotong University, Shanghai 200240, China)
Abstract: This paper aims to predict systematic risk of Shanghai industrial stock returns. Ten industrial betas are modeling by a new model, which brings in two unknown coefficients based on Random Walk of time-varying systematic risk. Simulation results show that the new model whose forecast errors are more precise is more effective, the new model is more suitable to describe variability of systematic risk of Shanghai industrial stock returns. By the recursive process of kalman filter, the innovation and its covariance matrix and likelihood function are got, and then push on parameter estimation,return the result estimated to process of kalman filter, which make the prediction.
Key words: Kalman Filter; Maximum Likelihood Estimation; Random Walk; Time-varying Risk Coefficient
Torque Sensor Design and Its Application on the Manipulator……………………………………………………………………（30） Huang Yuntian(Department of Automation, Shanghai Jiaotong University, Shanghai 200240, China)
Abstract: This paper studies the design of torque sensor. Firstly, it introduces the material selection and structure design of the torque sensor, finds the best position of the torque sensor to paste gauges based on the ANSYS software. Secondly, it debates the design of signal processing circuit, uses equipment to finish the static calibration to get the performance index.Finnally, experiment is designed to show the validity of the torque sensor in collision detection for the safe human-machine interaction of manipulator.
Key words: Torque Sensor; Static Calibration; Manipulator; Collision Detection
Face Detection and Tracking in Video Sequences……………………………………………………………………………………（33） Pan Jie, Xiong Huilin (School of Electronic Information and Electrical Engineering, Shanghai Jiaotong University, Shanghai 200240)
Abstract: Object detection and tracking is one of the most popular and important issues in the domain of computer vision. The AdaBoost algorithm based on cascade structure and the Camshift algorithm based on color feature are recognized as one of the most effective approaches for face detection and traction.This paper propose to combine the AdaBoost algorithm, Camshift algorithm with the Kalman filtering algorithm to implement multi-view face detection and tracking in video sequences. A modified AdaBoost algorithm was proposed to reduce the training time, and meanwhile, guaranteed the detection accuracy.
Key words:AdaBoost; Camshift; Kalman Filtering; Skin Color Feature
One Simple Algorithm Based on the Secondary B-Spline Curve Fitting……………………………………………………………（37） Gao Jianguang (School of Software, Shanghai Jiaotong University, Shanghai 200240, China)
Abstract: Because of fussy calculate in the course of fitting a thrice B-spline curve by four points. This paper put forward a simple arithmetic of secondary B-spline curve fitting. That is to say thrice B-spline curve is replaced with two secondary B-spline curves that can produce simple compute, satisfactory slick degree and quick speed.
Key words: Double Circular; B-spline Curve; Secondary Curve; Fitting Algorithm
Application of Improved K-means Algorithm in The Customer Segmentation Of B2C E-commerce …………………………（39） Shi Hongjun, Han Bing (Automation Department, Shanghai Jiaotong University, Shanghai 21004)
Abstract: Customer segmentation is the foundation for accurately making marketing strategies and successfully managing groups of customers. But the higher requirements are proposed with the development of the Internet and the e-commerce. A new K-means algorithm is proposed to find the initial clustering center with the consideration of the density and the distance. The new methods to divide the customer’s database are used. Experiments demonstrate that the proposed method can produce a high purity clustering result and the result is useful for marketing strategies. Key words: Data Mining; K-means Algorithm; Customer Segmentation
Background Modeling Based on Fusion of Mixture Gaussian Model and LBP Texture Model…………………………………（42） Liu Quanzhi, Hu Fuqiao(School of Electronic Information and Electric Engineering, Shanghai Jiaotong University, Shanghai 200240, China)
Abstract: This paper present a novel non-parametric foreground-background model which explores the complex temporal and spatial dependencies in non-stationary scenes. The model adapts to scenes which contain small motions. The Model uses GMM(Gaussian Mixture Model) to compute the probability of foreground d pixel with color information. It also uses LBP(Local Binary Pattern) texture model to compute the probability of foreground pixel with texture information. Finally, it uses data fusion algorithm named D-S evidence theory to do an information fusion in the decision level. Extensive experiments with non-stationary scenes demonstrate the utility and performance of the proposed approach.
III