基于平面有序离散点的特征点检测方法比较

夏静

摘要

本文针对曲线曲面重构问题中的基于平面有序离散点的特征点检测方法进行了研究。曲线的特征点选取的个数和准确性直接决定拟合曲线的连续性和精确性。通过对拟二分法和贪心算法的MATLAB程序实现，分析了两种不同算法在选取特征点上的算法优劣及在不同数量的样本点上的结果展现，为工程上进行曲线重构提供了很好的实践基础。

【关键词】有序离散点 拟二分法 贪心算法 曲线重构

逆向工程技术是随着计算机技术的发展和成熟以及数据测量技术的进步而迅速发展起来的一门新兴学科与技术。它改变了CAD從图纸到实物的设计模式，为产品的设计提供了一条新的途径。离散点的曲线曲面重构是逆向工程中的重要问题，是研究曲线和曲面性质的重要途径。然而，在某些情况下，测量所得的数据本身可能并不精确，使得所得到的采样点集并非完全落在原物体上，这时要求构造一条曲线严格通过给定的数据点就没有意义。因此，在容许误差范围内给出一条最为逼近的数据点显得更为合理，即曲线逼近方法。

传统的曲线逼近方法是在给定数据点的基础上分别通过参数化、插值或者拟合来生成初始曲线，然后计算曲率大小检测曲线的特征点，在保证误差条件下移除一些点以得到最少的曲线段数，使得加工效率得到提高，但这种方法由于初始所用数据点很多，导致在求解拟合曲线时系数矩阵太大，运行效率低下；或者直接根据各种离散曲率计算方法，计算各数据点的曲率以得到一些特征点，然后再进行样条曲线求解，这种方法虽然较前一种方法有其优越性，但是在计算曲率阶段仍然具有一定的复杂度。

而另一种方法是跳过参数化，直接根据所给的离散点信息检测曲线的特征点检测方法。事实上，曲线图形的信息主要集中在曲线的特征点上，而特征点多发生在转角大的地方，如何快速有效的检测出这些点并记录下它们的位置，就能在后续的处理中保证图形的拓扑性质不变。本文就是通过研究两种不同的特征点检测方法，通过不同数量的样本点的特征点检测实现，分析不同的检测方法在面对不同体量的样本点时对特征点检测的运行效率和精确性。

1 核心概念

1.1 曲线重构

曲线重构问题归根到底是对曲线进行逼近问题。而曲线逼近问题是曲线插值与拟合的统称。

根据给定一组有序的数据点，

，这些点可以是从某个形状上测量得到的，也可以是设计人员给出的，构造出一条曲线顺序通过这些数据点，所构造的曲线称为插值曲线。

但是在实际应用中，往往拿到的数据本身是有偏差的，这时就要求所得到的近似函数与原数据点的偏差按某种标准最小，以反映所给数据的总体趋势，消除局部波动的影响，这就是曲线拟合问题。

基于所处理的是具有微小噪声的离散数据，因此是一个拟合问题。在实际应用中，最小二乘法是度量逼近程度的最常用的一种方法。

1.2 数据多边形

介绍具体特征点检测算法前，需要先了解数据多边形的概念。

数据多边形，是由检测到的特征点为节点进行分段线性插值得到的折线多边形，艮P：若检测到的特征点记为：

，则数据多边形为

，其中，

分割每一直线段

，使其数据点数目与同一区间的原数据点数目相同。在此基础上，我们考虑以两点之间欧几里得距离为判定逼近好坏的标准，并寻找出相应的特征点，也就是：给定容许误差ε，对每一直线段

，若直线段上的每一点与其相应区间上的原数据点的欧几里得距离≤ε，那么就称Di+1为特征点。

2 特征点检测方法

2.1 拟二分法

拟二分法基于二分法的原理。

二分法的原理为，在己知参数曲线的表达式的前提下，基于曲线的凸包性质.如果曲线上任意一点到其弦线的距离小于等于给定的误差，就把弦线作为该曲线的逼近，否则按照参数区间把曲线一分为二，直到得到的子曲线段都满足到其弦线的距离不超过给定的误差为止。

而拟二分法是基于离散点，未知曲线表达式的前提下，不断计算逼近直线与对应样本点两点之间的欧几里得距离，通过无限逼近误差的方法检测特征点。详细算法如表1所示。

2.2 贪心算法

贪心算法主要基于实际生产加工中提高加工速度的考虑。在生产加工中，为了提高生产效率，需要减少逼近参数曲线的线段数量，从这一方面来说，自然是段数越少越好。实际上，在己知参数曲线的表达式的前提下，人们是基于参数，把曲线按照参数区间平均分段，每条子曲线段由其弦线逼近，直到得到的子曲线段都满足到其弦线的距离不超过给定的误差为止。其基本思想为：

曲线参数域[0，1]，对于给定的误差s，曲线平均分为n段，每段的参数区间长度为

其中，M是曲线二阶导数的上界。这是一个非常简单的方法，并且当误差较大时这种方法工作地非常好，但是该方法有下列缺点：

（1）这种方法依赖参数，曲线不同，参数导数值不同，因而分解的段数不同；

（2）计算二阶导数精确的界不容易；

对于有序离散点，直接考虑应用型值点的值进行数据多边形逼近，并且保证多边形与采样点的最大偏移量，尽可能的等于逼近精度，这样就减少了特征点的数量，就就是所谓的“贪心”。如表2所示。

3 算例比较及分析

为验证两种方法的优劣，以sin（l/x），区间为[0.1，2]为对象进行对比实验，采样点数分别为：381及939，在最大容许无法范围内，结果如表3所示。

通过表3，可以看出，对于初始数据点相对较少的情况，拟二分法的运行速度相对于贪心算法比较快，耗时较少，效率比较高，并且对于特征点的检测与贪心算法持平。但是对于初始数据点比较多的情况，拟二分法的运行的时间比较长，并且所检测得到的特征点要多于贪心算法，这是由于每一次该算法都是把区间分成两个小区间，在计算的过程中一直处于添加特征点的状态，使得它所得到的很多特征点实际并非我们所要的特征点，也就是说通过拟二分法得到的特征点，在去掉其中的某些特征点后，利用剩下的特征点所得到的逼近曲线仍然满足所给的容许误差，因此，从特征点最少最优的角度来说，贪心算法要优于拟二分法。

如表4所示，从误差角度分析，样本点较少的情况下，低于500时，拟二分法计算效率较快，但误差略逊于贪心算法；样本点一旦增多，贪心算法的优势明显，无论是计算效率还是误差方面，都胜过拟二分法，且其特征点数相对于拟二分法较少。

4 结论

本文针对实际工程应用中有序离散点的拟合曲线的特征点检测方法进行研究，通过对拟二分法及贪心算法的理论分析和实例比较，得出：

（1）在样本点较少的情况下，一般少于500个样本点的情况下，采用拟二分法检测特征点的方法速率较快，且特征点个数及误差范围都可接受；

（2）在样本点个数超过500个情况下，贪心算法无论是特征点个数，精度及运算效率都略优于拟二分法。

因此，两者比较，在工程上更要求精度的前提下，本文的结论是贪心算法更优。当然，在理论和实际工作中，尚有诸多特征点的检测方法及后续的曲线逼近方法，笔者将继续深入研究，希望能给出一个更快速、更精确、更适用于工程实现的检测和重构方法。

参考文献

[1]孟高峰.基于散乱数据的曲线曲面重构研究[D].南开：天津大学，2005.

[2]苏步青.计算几何[M].北京：人民教育出版社，1985-32-101.

[3]李雅青.列表轮廓零件数控自动编程技术自适应算法[J].华北工学院学报，2000.