（应用数学专业论文）基于bezier曲线的手绘图.pdf

中文摘要 在计算机动画造型中，平面曲线图设计一直没有很好地与手绘结合起来，这 主要在于手绘曲线拟合的算法不精确，模型单一，人工交互能力较弱，以及数字 曲线的数据点一般较多，为数据存储和处理带来了极大负担。 现有的手绘平面曲线图的修正拟合方法，以使用多边形逼近法、少数圆弧逼 近法，以及多边形和圆弧二者结合起来的方法为主，其共同点是选择原数字曲线 上的点作为逼近多边形。 手绘曲线是一种特殊的数字曲线，它的数据点与日常图像边缘检测得到的点 有一定的区别，因为后者相对较稠密，而确定手绘曲线的数据点相对稀疏。不过， 它们都是数字曲线，有许多相似之处，从而有相似的处理方法。手绘曲线可以画 出需要的曲线( 图形) ，这为某些仿真试验、异形设计等带来了极大的方便。但 它往往比较粗糙，噪声较大，与目标曲线有一定的差别。因此，希望建立某种方 法对手绘曲线进行处理，使得到的曲线既去除了噪声，又能抓住原曲线的特征； 同时表达该曲线的数据点较少。 本文从数据点的选取入手，按手绘曲线的时间顺序，随时计算曲线曲率等特 征，根据手绘速度及曲线特征( 如曲率) 变化取得数据点，基于由此得到的数据 点，适当选取控制顶点绘制b e z i e r 曲线图，从全局逼近手绘曲线。这一方法得到 的控制点不一定在原曲线上，其优点在于能抓住原手绘曲线的特征，去除了原曲 线的噪声，反应绘图的愿望，并且确定该主曲线的数据点较少。 关键词：手绘曲线，主曲线，逼近，b e z i e r 曲线，b 样条曲线 a b s t r a c t i nc o m p u t e ra n i m a t i o nm o l d i n g ，g r a p h i cc u r v e sd e s i g nh a v en o tb e e nw e l l i n t e g r a t e dw i t t lh a n d - p a i n t e d i ti sm a i n l yb e c a u s eo ft h a tt h ea c c u r a c yo fa l g o r i t h mi s i m p r e c i s ei nh a n d p a i n t e df i t t i n gi nc u r v ed e s i g n , t h ed e s i g nm o d e li st o os i m p l e ，t h e w e a k n e s si nt h eh u m a n - c o m p u t e ri n t e r a c t i o n , a n dt h eh u g en u m b e ro fd a t ap o i n t s t h e s ea l lb r o u g h ta b o u tag r e a tt r o u b l ei ns t o r a g i n ga n dp r o c e s s i n go fd a t ap o i n t s t h e r eh a v eb e e ns o m em e t h o d so ff i t t i n gh a n d p a i n t e dc u r v e s ，s u c ha st h eu s eo f p o l y g o n , a r ca p p r o x i m a t i o nm e t h o ds e p a r a t e l y , a n dt h eu s eo fb o t hp o l y g o na n da r c a p p r o x i m a t i o nm e t h o d t h ec o m m o np o i n ti st h a tt h e yc h o s et h ep o i n t so f t h eo r i g i n a l c u r v e sa sa p p r o a c h i n gp o l y g o n h a n d p a i n t e dc u r v e sa r es p e c i a ld i g i t a lc h iv e s c o m p a r i n gw i t ht h ed a t ap o i n t s g e t t i n gf r o mt h eg e n e r a lp i c t u r e s ，1 e yh a v et h i n n e rd a t ap o i n t st h a n t h a to ft h el a t t e r s h o w e v e r , t h e ya r eb o t hd i g i t a lc u r v e s ；t h e r ea r em a n ys i m i l a r i t i e st od ow i t ht h e m h a n d - p a i n t e dw a y sa r e u s e dt o g e tt h ec u r v e s ( g r a p h i c s ) ，w h i c hm a k et h i n g s c o n v e n i e n tf o rs o m es i m u l a t i o nt e s t s ，a n dc o n t o u r e dd e s i g n u n s a t i s f a c t o r i l y , i ti s o f t e nm o r er o u g h , m o r en o i s y , a n di sd i f f e r e n tf r o mo u r sd e m a n d t h e r e f o r e ，n e w w a y sa r er e q u e s t e dt o d e a lw i t ht h eh a n d - p a i n t e dc u r v e s t h i sk i n do fw a y sc a n r e m o v et h en o i s e ，g r a s pt h ec h a r a c t e r i s t i c so ft h eo r i g i n a lc u r v e ，a n dh a v et h el e s sd a t a p o i n t sa d d i t i o n a l l y t h i sa r t i c l es t a r t sw i t ht h es e l e c t i o no fd a t ap o i n t s ，g e tt h ed a t ap o i n t sw h i c ha r e c h r o n o l o g i c a l l yc h a n g e da g a i n s ts o m ef e a t u r e ss u c h a sd r a w i n gs p e e da n dt h e c h a r a c t e r i s t i c so ft h ec u r v e s ( s u c ha st h ec u r v a t u r e ) b a s e do nt h es e l e c t e dd a t ap o i n t s ， t h ec o n t r o lp o i n t sa r ec h o s e na p p r o p r i a t e l yt od r a wt h eb e z i e rc u r v e sa p p r o a c h i n gt h e h a n d p a i n t e dc u r v e s t h ec o n t r o lp o i n t sd e r i v e db yt h i sw a ym a y n o tn e c e s s a r i l yb e o nt h eo r i g i n a lc u r v e s t h ea d v a n t a g ei st h a ti tr e m o v et h en o i s e ，g r a s pt h e c h a r a c t e r i s t i c so ft h eo r i g i n a lc u r v e ，a n dh a v et h el e s sd a t ap o i n t sa d d i t i o n a l l y k e y w o r d s ：h a n d - p a i n t e dc u r v e s ，p r i n c i p a lc u r v e ，a p p r o a c h i n g ，b e z i e rc u i v c s ， b - s p l i n ec u w e s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究t 作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤注盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名： 傀镌 签字日期： 西矿年磊日 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘堂 有关保留、使用学位论文的规定。 特授权苤盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 磊磁 签字日期：三。妨年月- 日 导师签名： 讯匆弘 签字同期：2 。y 年月日 第一章绪论 1 1 曲线造型概述 第一章绪论 计算机辅助几何设计( c o m p u t e ra i d e dg e o m e t r i cd e s i g n ) 简称c a g d ，主 要研究在计算机图象系统的环境下对曲线、曲面信息的表示、逼近、分析和综合。 它起源于飞机、船舶的外形放样( l o f t i n g ) 工艺。随着计算机图形显示对于真 实性、实时性和交互性要求的日益增强，计算机辅助几何设计在近十几年来得到 了长足的发展。c a g d 是一门新兴边缘学科，它与逼近论、微分几何、代数几何、 数值分析、拓扑学、微分方程、分形小波等近代数学各个分支学科都有交叉和渗 透；其研究领域深入到了计算机图形学、几何造型、计算机辅助设计和加工 ( c a d & c a m ) 、数据结构、程序语言、图象学、解剖学等学科方向；并在工业 产品造型、机械设计制造、动画制作、多媒体技术、计算机视觉模拟、计算机图 形软件编制等方面有着广泛的应用。 c a g d 以c o o n s 【l j 、b e z i e r 等大师的c o o n s 线曲面造型技术和b e z i e r l t t t 线曲面造 型技术为理论基础。典型代表有b 样条曲纠2 - 3 】和隐式曲线( 如代数曲线) 掣4 。5 1 。 b e z i e r 曲线是法国雷诺( r e n a u l t ) 汽车公司的工程师b e z i e r 在1 9 7 1 年给出的 一种由控制多边形定义曲线的方法【6 】，b e z i e r 方法在c a g d 中占有重要的位置， b e z i e r 曲线、曲面在自由曲线、曲面的设计中，一直保持着不可替代的重要作用。 它为c a g d 学科的发展及c a d & c a m 技术的发展奠定了坚实的基础，在实践中表 现出强大的生命力。这种以控制多边形定义曲线的方法具有自然和直观的特点， 用这种方法进行曲线设计时，能够直观交互地使人对设计对象的控制达到直接的 几何化程度。 无论在理论上还是在应用上，我们都希望曲线的结构尽可能简单，同时其表 达的信息要足够丰富和完整，曲线整体要达到一定高的光滑度。 1 9 7 2 年，f o r r e s t 把b e z i e r 曲线表示为如下形式【刀 c ( f ) = 二群( f ) 号( o f 1 ) ， ( 1 1 ) 其中，鲜( d = ( ：) ( 1 一矿一九( f = 。，1 ，力) 为刀次b e n l s t e i l l 基函数，p 为控制多边 形的顶点。f o n e s t 给出的b e z i e r 曲线表达形式简单，具有很强的几何直观性，并 有许多良好的性质：端点插值性、凸包性、保凸性、几何与仿射不变性、对称性 第一章绪论 和变差缩减性等；并具有d ec a s t e l j a u 求值、升阶、离散、插值和包络生成等简单 的算法。b e z i e r 曲线比较好地解决了整体形状控制问题。在c a g d 的发展中，美 国通用汽车公司的g o r d o n 与r i e s e n f e l d 在1 9 7 4 年将b e z i e r 曲线进行了拓广，把n 次 b e r n s t e i n 基函数转换成，z 次b 样条基函数，构造了等距节点b 样条曲线【8 1 。b 样条 曲线不仅具有b e z i e r 曲线的几何特征，而且还具有曲线形状局部可调及连续阶数 可调等b e z i e r 曲线所没有的特征。后来，b o e h m 和c o h e r e 等人又给出了b 样条曲线 的节点插入技术和升阶技术【9 1 0 】。而在手绘图形中，所取得的数据点有阶段性特 点，要求分别对有序数据点光顺，故可以采用b e z i e r 曲线及b 样条曲线方法。 1 2 主曲线概述 主曲线概念是h a s t i e 和s t u e t z l e 于1 9 8 4 年提出的【1 1 】，主曲线是通过数据分布 “中心线并满足“自相合”的光滑曲线，研究主曲线的目的是根据给定的数据 集合求出一个曲线，使得这个曲线对给定的数据集合是某种意义下的对偶，形象 地说，希望能寻找通过数据分布“中心线”的曲线和曲面，使它能真实的反映数 据的形态，即曲线是数据集合的“骨架 ，数据集合是这个曲线的“点云”。由此 可见，主曲线对数据的信息保持性好。其理论基础是寻找嵌入高维空间的非欧氏 低维流形，也是线性主成分的非线性推广【1 2 1 。主曲线在计算机方面有许多应用， 诸如线性对撞机中对电子束运行轨迹的控制、图像处理中辨识冰原轮廊、脱机手 写的主曲线模板化的数据可视化等。其中脱机手写识别是一个经典问题，并且在 银行、税务和邮政系统等领域有重要的应用和广阔的发展前景。 1 3 本文主要工作 本文首先针对b e z i e r 曲线及b 样条曲线的造型问题做了进一步的研究，从 手绘图形中读入数据点集合 卑) ，使用主曲线分析修正数据顺序以及走向，减少 原手绘图的控制点，所得到的点集 牙) 做为控制顶点，进而综合运用b e z i e r 方法 及b 样条方法，输出平滑后的曲线。 第二章b e z i e r 曲线和b 样条曲线 第二章b e z i e r 曲线和b 样条曲线 2 1b e z i e r 曲线的定义 定义2 1 给定刀+ 1 个空间向量五( f = o ，1 ，刀) ，称，z 次参数曲线段 尸o ) = e 巨量，。( f ) o s f 1 ( 2 1 ) 为b e z i e r 曲线，式中二项分布密度函数为 i 置刃( f ) = q f ( 1 - t ) ” 卜稿忙o ，l ，一 q 。2 在取定原点0 以后，依次用线段连接蓐( i = o ，l ，船) 中相邻两个向量的终点， 这样组成的n 边折线多边形称为b e z i e r 多边形，或特征多边形。尽。( f ) 为，z 次 b e r n s t e i n 基函数。图2 1 给出了n ：5 时的六个b e r n s t e i n 基函数的图形。 图2 - 1n = 5 时的b e r n s t e i n 基函数 下面用一个例子来解释该方法：给定四点只，露，只，只，用下面方法构 造一条曲线：对任意t f o ，1 1 ，取 或= ( 1 - t ) e o + 嵋，科= ( 1 - t ) g + 幔，雹= ( 1 - t ) p 2 + 也 霹= ( 1 - t ) b l ：+ 刎，砰= ( 1 - t ) b ? + 趔 鹾= ( 1 一f ) 彰+ t b ? 图2 2b e z i e r 曲线的构造 p 3 第二章b e z i e r 曲线和b 样条曲线 t 盘4 p ( t ) = 露，则对f 【o ，l 】，p ( t ) 为r 3 中一条曲线，称为基于控制顶点e o ，弓， 最，只的贝齐尔曲线。易知： p ( f ) = ( 1 一f ) 3p o + 3 ( 1 一f ) 2t p l + 3 ( i t ) t 2 罡+ f 3 忍 b e z i e r 曲线的实例如图2 3 所示。 2 2b e m s t e i n 基函数的性质 图2 3b e z i e r 曲线实例 ( i ) 正性 尽埘o , l 当t = 0 , 1 1 ) ( 吼2 ，刀一1 ) ( 2 - 3 ) i b o ，。( 0 ) = 吃。( 1 ) = 1 ， 风，。( 1 ) = 鼠，。( o ) = o ， 1 0 b o ，。( ) ，或，。( f ) l ，当( o ，1 ) ( i i ) 权性 忍，。( f ) 兰1 ，f 【o ，1 】 ( 2 - 4 ) ( i i i ) 对称性 垦。( t ) = 最却( 1 一t ) ( i = o ，1 ，行) ( 2 5 ) ( i v ) 导函数 。( f ) = 刀 e - l , n - i ( f ) 一忍加。( f ) ) ( i = o ，l ，刀) ( 2 6 ) ( v ) 最大值 忍。( t ) 在t = 二处达到最大值。 ( v i ) 递推性 e ，。( t ) = ( 1 - t ) b i 俨。( f ) + 啦1 川( t ) ( i = o ，1 ，n ) ( 2 - 7 ) 这里统一规定：凡当指标超出以致记号不具意义时，例如噩。，。( f ) 和峨扩。( t ) 等，都视其为实数零。 第二章b e z i e r 曲线和b 样条曲线 2 3b e z i e r 曲线的性质 ( i )端点性质 由( 2 3 ) 式得到p ( o ) = 磊，p ( 1 ) = 瓦，这表明了b e z i e r 曲线是以瓦和瓦为 其起点和终点的。 记嘻= 历一五一。( i = 1 ，2 ，n ) ，代表b e z i e r 多边形的边向量。由( 2 1 ) 和( 2 6 ) 式有p ( o ) = 崛，p ，( 1 ) = 玎瓦。说明b e z i e r 曲线是分别以磊和厅。为其起点和终点 的切方向。 类似地有p ( o ) = 刀( 力一i ) ( k z - - k , ) ，p ( 1 ) = 以( 以一1 ) ( 玩一瓦一。) 。因此曲线在两 端点的副法向量分别为 r ( o ) 兰p ( o ) p ( o ) - - n 2 ( n - 1 ) 5 。毛 r ( 1 ) - - p 7 ( o r o ) - - n 2 ( n - 1 ) 或一。瓦 一般地，起点的，阶导向量7 ( o ) 仅同相邻的，条边向量茸( i = l ，2 ，r ) 有 关，与更远的各条边无关。终点情况与此对称。 ( i i ) 对称性 保持b e z i e r 曲线( 2 1 ) 的诸顶点五的位置不变，只把次序完全颠倒，所得 的新多边形顶点记为历= 瓦一，( i = o ，l ，n ) 。这样得到的一条b e z i e r 曲线与原来 的曲线相同，只是有相反的定向，见图2 - 4 。这是因为，记新的b e z i e r 曲线为，( f ) 时，有 h0 尸( f ) = 历忍，。( f ) = 瓦一。忍，。( f ) = 五色一，。( t ) i = oi = 0i = n = 巨e ，。( 1 - t ) = p ( 1 - t ) i = 0 这个性质即，b e z i e r 曲线及其多边形的两个端点的地位对称( 非形状对称) 。 ( i i i ) 凸包性质 由b e r n s t e i n 基函数的正性和权性知，量，。( t ) ( i = o ，1 ，z ) 构成权函数。对于 固定的f ，尸( f ) 是多边形各顶点巨( i = o ，1 ，n ) 的加权平均，权因子依次是墨。( t ) o = o ，, - - - , ，z ) 。该性质表明b e z i e r 曲线完全含在其特征多边形的凸包中，如图2 - 5 所示。 第二章b e z i e r 曲线和b 样条曲线 图2 4 控制顶点的对称性 ( i v ) 几何不变性 b e z i e r 曲线( 2 1 ) 式是向量表示式， 只与特征多边形有关。 2 4b 样条曲线的定义 图2 5b e z i e r 曲线的凸包 曲线的形状不依赖于坐标系的选择， 虽然b e z i e r 曲线较好地解决了整体形状控制问题，但仍存在连接问题和局部 修改问题。而b 样条曲线不仅具有b e z i e r 曲线的几何特征，而且还具有曲线形 状局部可调及连续阶数可调等b e z i e r 曲线所没有的特征。 定义2 2 给定m + n + 1 个空间向量瓦( k = o ，l ，m + n ) ，记 暑一( f ) = 瓦，。( t ) ，0 i 1 ( 2 - 8 ) 其中 巧。( f ) = ( 一1 ) 7 巴。( h 刀一，一，0 l 0 _ 白、 存在，则 厂( 五) = 娥乏乞( 工) 谚 为主曲线并满足自相合特性，其中万= 瑚m 如a x 曲 点) 。 从理论上讲，随着局部邻域的逐渐减小，得到曲线也越来越逼近光滑主曲线。 算法步骤如下：初始设尼= 1 ： s t e p1 使用k 个球形邻域 反( 五，磊) ，反( 五，暖) ，鼠( 五，皖) 覆盖样本数 据； s t e p2 对每一个邻域反( 名，4 ) ，i = l ，2 ，k 内数据点五。，薯2 ，计算 e 舡( x ) 、c o v 蔚( x ) 及其特征向量岛= ( 参。，磊：，岛) ； s t 印3 令磊= m i n 鲧砷， ，m = 1 ，j ，其中龟哪为& 川) ( 丑，巧) 内数据 点协方差矩阵的主特征向量，且量( 乃，4 ) c 乓( 乃，西) ，计算最( 乃，磊) ， i = 1 ，2 ，k 内数据点在磊上的投影，及局部重构向量靠； s t e p4 连接露，应用样条函数或局部光滑化方法，得到近似光滑的主曲线； s t e p5 计算全局重构误差g m s e t ，如果g m s e 。- g m s e 小于某个阈值， 第三章主曲线 则停止迭代。否则令k = 后+ l ，转s t e pl 。 图3 3 是一个简单的例子，从该图中可发现主曲线有两个明显的优点：一方 面对数据的信息保持性好，另一方面它较好地勾画出了原始信息的轮廓。 敷据点 一生曲拽 图3 3 一组数据集的主曲线 在手绘曲线中，数据点集不像上图那般杂乱而且繁多，手绘图形所取得的初 始数据是明显呈线条走势的有序点集。主曲线的运用可以使其排列更符合人们的 期望位置，从而减少曲线中因鼠标、绘图笔等输入工具做图所带来的不必要的拐 点、尖点等。 第四章手绘曲线 第四章手绘曲线 4 1 手绘曲线的性质和主曲线 4 1 1 手绘曲线的性质 手绘曲线本质上是顺次连接数据点得到的折线，这些点是鼠标在绘图板上移 动时，计算机按一定时间间隔捕捉鼠标所在的位置得到的点( 称为基本点) 。当 鼠标移动较快时，点较稀疏；反之，则较稠密。如图4 1 中的手绘曲线( a ) 是顺 次连接( b ) 中的点得到的折线。手绘曲线有两个特征：( 1 ) 不光滑。如图l 中的 b 处出现了尖角，而且很多地方都有细微的凹凸，如图4 1 中的c 处，这主要是由 于绘图时手控制不稳，有细微的抖动所致。( 2 ) 确定曲线的数据点相对较多。( 3 ) 曲线的数据点在两端点及中间部分的密度不同，两端取点较密集，中间取点较稀 疏。图4 1 中的曲线由3 6 个点确定。 q 一 i ； 。； - ， ( a ) ( b ) 图4 一l 手绘曲线和它的基本点 4 1 2 手绘曲线的主曲线 定义4 1 设s ，、s ，是有限长曲线，称s 。上的所有点到s ，距离的平均值为s 到s ，的 距离。显然，曲线蜀到s ，的距离和s ，到s 。的距离可能不一样。 定义4 2 如果厂是光滑地从手绘曲线尹“中间 穿过，且使尹到它的距离最近 的最短曲线曲线，厂称为手绘曲线尹的主曲线。 显然，这个概念定义得比较模糊，何为“中间 ? 实际上，可以把手绘曲线 的主曲线看成是绘图者要画的曲线，称为源曲线，而手绘曲线可以看成是源曲线 受到随机噪声的干扰得到的曲线，它上面的点在源曲线的附近振荡。显然，源曲 线一定比手绘曲线短，下面工作的目的就是恢复源曲线。 第四章手绘曲线 4 1 3 手绘曲线预处理 由于手绘的任意性较大，一般不能找到一个函数来表示它的主曲线，因此手 绘曲线的主曲线不易得到，一般只能得到它的近似曲线。实际上，手绘曲线上转 角处的点、始点和终点附近的点对手绘曲线的走向起主要确定作用，把这些决定 手绘曲线走向的点叫做控制点。把控制点光滑地连接起来得到的曲线，就可以看 成主曲线的近似。因此，为了得到这些控制点，可以用折线逼近手绘曲线尹，使 到折线s 的距离尽可能短。然后将s 的顶点用基样条光滑地连接起来，将所得 的曲线作为主曲线的近似。 实际上，用计算机求出尹到s 的真正距离是不可能的，因为尹有无数个点， 只有将曲线厂离散化，用近似距离估计。前面已经指出，手绘曲线是由基本点确 定，那么能不能用这些点到s 的平均距离来近似表示厂到s 的距离? 不能。因为 当鼠标移动较快时，所得的点较稀疏，反之则较稠密。而得到的、看到的和要用 的都是将这些点顺次连接起来的曲线，而不是那些点。况且在稠密处，很多点才 表示一段很短的曲线，而稀疏处很少几个点就能表示很长一段曲线。实际上手绘 曲线上的每一点都同样重要，而不在于它是否是基本点。因此，为了较准确地得 到厂到s 的距离，按如下方法选取厂上的点：对长度小于某个预设的标准的线段， 则直接选取该线段的端点，对长度大于该标准的线段，则在该线段上插入一些点， 以保证在厂上选取的任意两个相邻点间的距离小于该标准。把所获得的这些点叫 做手绘曲线的数据点，将数据点到s 的平均距离作为尹到s 的平均距离的近似。 4 2 手绘曲线直线拟合 当手绘曲线近似于直线时，其主曲线为直线，则直接搜索这条直线。 4 2 1 直线识别 ( 1 ) 排除显然不近似于直线的情况。对明显不是直线的情况，可以简单地 排除：在手绘曲线数据点中随机选择4 个不同的点，然后将它们按在曲线上的顺 序排列，顺次用线段连接起来，得n 3 个方向向量u ，、“，、u ，求出u ，对“。的偏 移角度口( 见图4 2 a ) ，u ，对u ，的偏移角度，如果口+ 大于某个预定的值，则 认为该手绘曲线肯定不近似于直线，否则可能是直线。当然，也有可能某曲线与 直线相差很远，但可能随机选择的点太特殊，没有把它排除掉( 如图4 2 b ) ，但 可用( 2 ) 中的方法将它排除掉。 第四章手绘曲线 i ，爬吩， 兮营二j y ： ，i ( a ) ( b ) ： 图4 - 2 ( a ) 用4 个点排除不是直线的情况( b ) 点取得太特殊暂无法排除 ( 2 ) 判断手绘曲线是否为直线的方法。当( 1 ) 无法排除曲线不是直线的 情况时，则求手绘曲线数据点的第一主元线段j ( 数据点的第一主元线是在所有 直线中，数据点到它上面的期望平方距离最小的直线，s 是第一主元线上包含所 有数据点的正交投影点的最短线段) ，再求所有数据点到s 的平均距离d ，设s 的 长度为z ，e r r o r o 是预设的最大允许相对误差，若d ， e r r o r ，则确定该手绘曲线 的主曲线为一条直线，否则为一般曲线。 4 2 2 用随机摄动遗传算法搜索主曲( 直) 线 当手绘曲线的主曲线为直线时，则只需找到一条直线，使手绘曲线到它的距 离最短。第一主元线并不是这样的直线，因为它是基于均方距离的；而主曲( 直) 线是基于平均( 绝对值) 距离的。不过，第一主元线和主曲线靠得很近( 这很显 然) ，可以把它作为搜索主曲线的初始直线，因此，在第一主元线段的两端点运 用随机摄动遗传算法【1 2 】搜索主曲( 直) 线上的两个点。最后，把得到的直线上的 包含所有数据点的正交投影点的线段作为主曲线。 4 3 用折线逼近法搜索主曲线 当手绘曲线的主曲线为一般曲线时，运用折线逐步逼近法，搜索手绘曲线的 控制点，然后运用基样条把它们光滑地连接起来，作为手绘曲线主曲线的近似。 折线逼近法的基本思路为：从初始折线出发，逐渐增加顶点以增加折线的边数， 每增加一个顶点，都通过优化有惩罚的距离函数调整顶点的位置，得到当前边数 的最佳逼近折线。当满足停止条件时结束搜索。 ( i ) 投影 设厂是由顶点，+ 。和线段，& 组成的逼近折线，其中s ，是连接顶点 坼和。所得的线段。在这一步，手绘曲线的数据点集x 。( 至多) 被分为2 庀+ 1 个 互不相交的集合巧，砭，圪+ 。和墨，足，即厂的顶点和边的最近邻域。 k 和& 的构造如下：从而开始，顺次在以中取点，若x i 关于s ，所在直线的 投影点没有落在线段而上，则将薯放入k 中，直到某x ，关于墨所在直线的投影点 第四章手绘曲线 落在线段_ 上为止，将工，放入s 中，继续顺