机器视觉轮廓表示之曲线拟合.doc

稻草人自动化培训

机器视觉轮廓表示之曲线拟合
7.2曲线拟合
本章将讨论三种常用的曲线模型拟合边缘点的方法：直线段，圆锥曲线段和三次样条 曲线段.一般来说，在用曲线模型拟合边缘点之前应考虑如下两个问題：
① 用什么方法进行边缘点曲线模型拟合？
② 如何测量拟合的逼近程度？
下面几节将讨论曲线模型拟合边缘点方法，其中假设边缘位置足够精确，不会对拟合 结果产生影响.
设d1是边缘点到一条拟合曲线的距离，该距离值有正负符号，在曲线同一侧的边缘具有相同的正负符号.目前有许多种拟合曲线与候选边缘点拟合效果的测量方法，每一种都取决于拟合曲线和候选点之间的误差.下面是一些常用的方法.

① 最大绝对误差(maximum absolute error, MAE )
测量最坏情况下边缘点偏离曲线的距离

② 均方差（mean squared error，MSE )
给出边缘点偏离拟合曲线的总的测度

③ 规范化最大误差（normalized maximum error，NME )
最大绝对误差与曲线长度S之比

④ 误差符号变化次数
这里的误差就是指d1，即边缘点偏离拟合曲线的距离.误差符号变化次数可作为轮廓边缘模型与边缘点曲线适合程度的测度.
⑤ 曲线长度与端点距离之比
曲线复杂程度的测度.
符号变化是一种评价拟合好坏的很有用的参数.比如，用直线段逼近边缘表.如果符号变化一次，则说明边缘点可以由直线段来逼近，符号变化两次，说明边缘可以由二次曲线逼近，符号变化三次，说明边缘模型是三次曲线，依此类推.如果符号变化数量很大，则意味着曲线复杂度增加一点将不能显著地改善拟合效果.一种好的拟合所对应的符号变化具有随机模式.相同符号连续出现多次说明存在拟合系统误差，这种误差可能是由于错误的曲线模型引起的。
曲线拟合模型的选择取决于应用场合.如果场景是由直线段组成，则使用直线段（或多线段)模型比较合适。直线段模型也可作为其它拟合模型的初始拟合模型.圆弧段是估计曲率的最有用的一种表示，因为曲线可以分割成具有分段恒定曲率的曲线段.圆锥曲线段是一种表示直线段和圆弧段序列以及椭圆和高次弧段序列的有效方法.三次样条曲线适合于平滑曲线模型，因为三次样条曲线并不要求正切矢量和曲率的估计值一定是分段恒定的。

7.2.1多直线段
多直线段是指端点连接端点的直线段序列，直线段序列的连接点称为顶点.多直线段 适合具有线段序列的边缘列表的拟合.多线段算法的输入值是边缘点有序表{（x1，y1），（x2，y2），…，（xn，yn）}。边缘点坐标可以计算到子象素精度.由于线段的两个端点对应两个边缘点，即线段拟合在这两个边缘点之间进行，因此仅需要精确计算对应端点的两个边缘点的坐标。
拟合边缘表并把第一个边缘点（x1，y1）和最后一个边缘点（xk，yk）连接起来的直线段公式如下：

规范化最大误差常作为线段拟合边缘列
表好坏的置度.需要指出，上面的公式都是在点
向直线段的垂直投影落在线段内这个假设下进
行的.对于其它情况,则应修正公式，以便计算
点到最近的线段端点的距离.下面介绍两种拟
合多线段的方法：自顶面下的分裂和自底而上
的合并.
1.多直线段分裂
自顶而下的分裂算法(top-down splitting)
是将整条曲线作为初始曲线，通过反复增加顶点
数来进行直线段拟合曲线。考虑图7.5所示的边
缘点曲线（可以认为是由离散边缘点构成），将
第一个和最后一个边缘点连成的直线作为曲线的
初始拟合，用AB标记.在边缘表中计算规范化最
大误差，如果该误差值髙于某一阈值，则在离直
线段最远的边缘点上设置一个顶点，用C来标记，
从而形成两个拟合直线段AC和CB,边缘表也分割
成对应于两个新直线段的两个子边缘表.在每一个
子边缘表中，重复上面所述的分裂算法，形成两个新的直线段及对应的两个更小的子边缘表.这样的分裂过程可以一直进行下去，直到所有的直线段对应的规范化最大误差均低于某一阈值为止.多线段分裂也称为迭代分解。
2.线段合并
线段合并(merging)是指用一条直线段尽量多地拟合边缘表中的边缘点.当边缘点离直线段太远而无法用该直线段拟合时，则开始新的直线段拟合.合并方法也称为自底而上合并(boltom-up merging)的多线段拟合方法.
确定边缘点离直线段的距离有许多种方法.一种方法是使用序贯最小二乘法，完成直 线段到边缘点的最小二乘法拟合，并在每次处理新的边缘点时递增地更新线段参数.拟合算法将计算边缘点与直线段模型之间的偏差(残差）平方.当偏差超过某一阈值时，引进一

个顶点，并将上—个线段的端点作为新的起点开始新的直线段拟合。
误差带算法是另一种确定顶点位置的方法，如图7.6所示，主要工作是计算两条平行 且离中心线距离为ε的直线段，ε值表示离中心直线的绝对偏离值,拟合直线段就位于误差带内.当新的边缘在误差带内，就可以用当前拟合直线表示该边缘，然后重新计算误差带的位置拟合直线段不必与误差带边保持平行.位于线段端点的顶点是下一线段的起点.显然，这一方法常产生大量的线段.由于拟合直线段行进到误差带边界时才产生角点， 因此，不能精确估计角点位置和角度。
3.分裂和合并
自顶而下的迭代分解方法和自底而上的合并方法组合起来，形成合并和分裂算法.单 独使用分裂或合并算法时，成功率往往不是很高，改进的方法是交叉使用分裂和合并算法.分解过程以后，如果新的线段能以很小的规范化误差拟合边缘，则可用单一直线段代替相邻的几个线段.请注意，由于多直线段总是比单直线段的拟合误差小，因此很有必要使用规范化误差.在线段合并后，新的线段可能在不同点处分裂.这样，分裂和合并交替作用直到没有线段被合并和分裂为止，图7.7所示的是先分裂后合并来修补坏顶点位置的示意图。

一种有效的分裂和合并算法是从边缘表中的前k个边缘构成的子列表开始，而不是 整个边缘列表.用直线段拟合子表中第一和最后一个边缘点之间的边缘点.如果某点的规范化最大误差太大,则将子列表缩到最大误差对应的边缘点处，这样一直进行下去，就可以得到第一条拟合直线段,这实际上是分裂算法.置当前拟合的直线段为旧线段，再在剩下的边缘点集中取前k个边缘构成新子列表,用分裂算法求取第二条拟合直线段.比较当前直线段和原直线段的方向，如果它们具有相似的方向，则将这两条直线段合并，这是合并算法。
实际的轮廓曲线并不全是由直线段组成，可能还包含有各种弧线或肖由曲线.因此， 仅使用直线段得到的拟合结果比较粗糙，人们自然想到了用弧线段逼近.通常的弧线有二 次、三次或更高次的曲线，这些通称为多项式曲线，下面主要讨论次曲线和三次样条曲线.

7.2.2 二次曲线
下面讨论如何用二次曲线逼近边缘表.二次曲线的一般表示如下：

二次曲线也称圆锥曲线，因为二次曲线都是用平面
切割正圆锥面的截线，如图7.8所示.若平面不通过锥顶
，且不平行任一母线,则截线为椭圆，其中圆是椭圆的一
种特殊情况，此时的平面垂直于锥轴；若平面不通过锥
顶但平行于一条母线时，截线为抛物线；若平面不通过
锥顶，且平行于锥轴，截线为双曲线.当平面通过锥顶时
,椭圆变为一点，双曲线变为一对相交的直线，抛物线变
为与圆锥相切的一条直线.由此可见，使用二次曲线来逼
近数字轮廓曲线，可以有效地拟合数字曲线中的直线和
圆弧等各种二次曲线.由于二次曲线中除了特殊的直线
外，最简单的情况是圆弧，因而得到了大量的研究.我
们将单独讨论圆弧逼近方法.
1. 圆弧段
用直线段逼近边缘表以后，其中的一些直线段序列可以由圆弧段来代替，比如，用直线段拟合一个圆弧可能需要许多个直线段才能满足拟合误差，如果对这些直线段用圆弧段来拟合，则仅需要一条圆弧段即可，因此可见，圆弧段拟合此直线段能拟合得更紧凑，下面讨论的圆弧拟合是在多边形顶点上进行的。
具有半径r和圆心坐标（x0，y0）的圆弧隐式方程为

子得到圆的半径。

用圆弧段拟合多直线段时，圆弧段的网个端点要经过多直线段的某构个顶点，第三个 点位于这两个顶点之间，第三个点可能有如下几种情况：
①离两个顶点定义的直线最远的多直线段顶点；
②离两个顶点定义的直线最远的边缘点；
③两个顶点之间所有顶点的中点；
③ 两个顶点之间所有边缘的中点。
计算所有边缘点和圆弧段之间的距离误差，检查最大绝对误差和符号变化次数，如果 规范化最大误差低于某一阈值，而符号变化次数很大,则接受这一圆弧段；否则，保留多线段逼近.关于圆弧段逼近的文献很多,感兴趣的读者可以参见文献[Jiar 1992，Chen 1996]。
用直线段和圆弧段可以有效地表示数字轮廓曲线，但是用两种不同的线段基元表示轮廓会造成不便.下一节讨论的圆锥曲线允许直线段、圆弧段和其它基元共同出现在同一种表示中.圆锥曲线段表示也提供了曲线之间平滑过渡的方法，也是角点的显式表示。
2.圆锥曲线
圆锥曲线可以拟合轮廓多直线段上的三个顶点.将圆锥曲线段连接在一起的点称为结点.圆锥样条曲线是圆锥曲线的一个序列，它们的端点和端点连接在一起，在结点处具有相等的正切，使两个邻接曲线段之间平滑过渡.设多直线段端点为Vi，圆锥逼近如图 7.9所示。

圆锥样条中的每一个圆锥曲线由两个端点、两个正切和第三点确定.结点位于多线段顶点之间

这里所示的计算圆锥样条算法使用了一个圆锥曲线的引导形式，以表示由三条直线约束的圆锥曲线，如图7.11所示.直线方程为

设多直线段中的第一和最后一个顶点为A和B，C是多线段的中间顶点，用弦连AB连接第一和最后一个顶点.圆锥曲线导向形式是端点位于A和B的圆锥曲线族，正切AC和 BC由下面方程定义

锥曲线来代替.软顶点序列对应于缓变方向角的直线段序列,很可能是对光滑曲线的采样点进行拟合的结果.角点对应的顶点角大180°+ T1,或小于180°-T1 ，其中T1是阈值， 角点不可能成为圆锥曲线的一部分.结点位于某一条直线段上，该直线段的端点上具有软顶点.一个圆锥曲线不可能有拐点，所以两个圆锥曲线只能通过结点来连接.结点在直线段上的位置由直线段端点的软顶点相对角度确定.设两个软顶点Vi和Vi+1的角度分別是Ai和Ai+1.如果Ai = Ai+1 ,那么结点可以位于顶点的中间，也就是说，在式（7.16)中V= 1/2.由于圆锥曲线不可能偏离直线段而足够迅速地弯曲去跟踪角点，因此如果角度不相等，那么，结点位置应该偏离具有较大角度的那个角点.式(7.16)的V值可以由下式计算

由软顶点连接的每一个直线段序列可由穿过第一和最后一个顶点（或结点）的导向圆 锥代替.第一和最后一个直线段的方向角定义了正切.正切和端点确定圆锥5个自由度的 4个.让圆锥穿过位于序列中央的软顶点可以完全确定圆锥。

稻草人自动化培训