B样条曲线的光顺设计 - 浙江大学本科生毕业论文

毕业论文

的拼接处，原来的光顺结果可能会被破坏，从而得不到更好的结果。

图9 左图是图4 的例子加了噪音后的原曲线，右图是曲率线图。蓝色表示光顺前的曲率线，红色则 表示按3.2.4 所述算法光顺后所得的曲率线。即使有分段和混合，中间部分的光顺性反而更差了。

该算法比起第2 章所述的整体方法，更多地考虑了局部性；而比起局部方法，又是一段一段地去光顺，考虑了部分地整体性。因此，它可以说是“大局部”方法。我们希望得到类似的方法，既考虑局部，又不忽略全局整体性，从而得到更好且更鲁棒的光顺效果。

4 基于L1 范数优化的光顺算法

4.1 向量c 与向量e

我们已知插值点（或型值点）Pi(xi,yi)(i?1,...,n) ，我们希望反求出这些型值点 位置与其对应的曲率向量间的关系。如果我事先给定了参数u1,...,un ，它可以是均匀 也可以是非均匀的。那么，由参考文献[1]，由三次B 样条的基本性质，在每个插值

T

点Pi 处的一阶导数与二阶导数都可由P?[x1,y1，...,xn,yn] 阵仅与参数u1,...,un 有关，与Pi 所处的位置无关。

又由参数平面曲线s(t) ?(x(t), y(t)) ，其曲率为

k ?

乘上一个矩阵得到，这个矩

x?(t) y ?(t) ?x ?(t) y?(t) (x?2 (t)+y?2 (t))3/ 2

尽管一阶导数与二阶导数与P 是线性关系，但是曲率与它却是非线性关系。为了使优化更为简单，一种方法是将二阶导数当作是曲率；另一种方法则是在优化过程中将一阶导数作为常数来处理，因为当型值点的偏移量较小时，可以认为一阶导数不发生太大的变化。

10

毕业论文

令c 为型值点处曲率所构成的向量。当我们将曲线的一阶导数作为常数，曲率向量c 与P 满足线性关系，即可以得到一个矩阵A，使得c=AP。具体如何求，可以参考附录中所附的matlab 代码。

而ei ?(ci?1?ci)/(ui?1?ui)，当u1,...,un为事先给定的常数时，它与曲率向量c存 在线性关系。因此，存在矩阵B，使得e=BP 成立。具体如何求，可以参考附录中所附的matlab 代码。

4.2 数学模型的构建

4.2.1 光顺判别准则C3 与优化目标

如第3章中所述，光顺判别准则C3有三个优化目标：（1）曲线的拐点数；（2）曲率线的拐点数；（3）曲率线的变化幅度。

而第三章中，董光昌先生等提出的曲线光顺方法，回弹法对应减少曲率线变化的幅度，直尺卡样法对应减少曲线的拐点数，曲尺卡样法对应减少曲率线的变化幅度。

我们先考虑曲率线的变化幅度，这是三个优化目标中相对容易量化的目标。向量 e 中的每一个值表示该插值点处曲率的变化幅度，因此，减少向量e 的L1 范数或L2 范数，即可减少曲率线的变化幅度；最小化|| e ||1

化幅度。

或者|| e ||2 即可对应最小化曲率的变

再考虑前两个优化目标，它们都是希望减少拐点数。曲线的拐点数，即第一振动 数，我们用Nc 来表示；曲率线的拐点数，即第二振动数，我们用Ne 来表示。由第 3 章所述，第一振动数代表的是曲线光顺性发生“质变”的次数，它是最重要的优化目标。因此，我们首要考虑如何优化Nc 。而第一振动数与第二振动数是相似的，只要我们知道如何优化Nc ，总可以用类似的方法去优化Ne ，就如直尺卡样法和曲尺卡样法一样。

4.2.2 曲线的拐点数与c 的L0 范数

曲率向量c 的L0 范数，即曲率向量c 中非零元的个数。

11

毕业论文

图10 曲率线图c=[1,2,-1,1,-1,3]’

图11 曲率线图c=[1,2,0,1,-1,3]’

图10 中的拐点数为4，而其c 的L0 范数为6。图11 中拐点数为2，其c 的L0 范数为5。

易有不等式

Nc ?? ||c||0 ?1

因为只有当向量c 中相邻的两个非零元的符号不同，才会产生一个拐点，那么当c 的L0 范数固定，最多只会产生非零元个数减一个拐点。从这点来看，c 的L0 范数为拐点数的上界，优化c 的L0 范数，能在一定程度上减少拐点数。

如果我们将向量c 中某个非零元ci 变成0，而其他值保持同号：

（1）当ci 的两个相邻的非零元都与它异号时，它变成零，拐点数会减少2。如将图10 中第3 个元素-1 变成0 就变成了图11，而图11 的拐点数比图10 的拐点数少了2。

（2）当ci 得相邻非零元有一个与它同号，它变成零，拐点数不会改变。我们知道优化c 的L0 范数，可以近似转化为优化c 的L1 范数。当我们去优化c

12

毕业论文

的L1 范数时，一般来说，c 中的每个元素在优化后不会与原来异号，或者是同号，或者是变成零，即确保不会增加拐点数。根据上述讨论，优化c 的L1 范数，应该能够有效地减少曲线的拐点数。下面图示是实验论证。

图12 左边为原曲线，右边为曲率图。蓝色为优化c 的L1 范数前，红色为优化后。

图13 左边为原曲线，右边为曲率图。可以看出，优化后拐点明显减少。

图14 左边为原曲线，右边为曲率图。

通过实验，我们认为优化L0 范数，可以有效地去除多余的拐点。

13