基于曲线形态的曲线相似性度量

陈涛

（四川大学计算机学院，成都610065）

具有相似性的数据序列构成的曲线具有相似的形态特征。提出一种基于用切线向量来标识曲线特征，计算切线向量集之间的相似度，进而对数据序列进行相似性度量，达到数据序列分类识别的方法。该方法用连续性函数将点列分段连接成一条曲线，再求解所有点的切线向量组成向量集，通过比较两列数据点列切线向量集的相似度来识别和将点列识别。最后通过实验，证明该方法的有效性、准确性、广泛适用性。

曲线形态；切线向量；曲线识别

0 引言

随着计算机科学计算的飞速发展，利用计算机系统和数学技术在生产生活中帮助人们实现智能识别和自动处理各种事务是计算机应用的研究热点。在气象变化分析、股票变化分析、金融数据分析、电磁信号分析[1]、运动曲线识别等需要进行模式识别的方面都有广泛的应用需求。

计算机将现实世界的某种信息通过数学模型按照顺序记录保存于计算机存储器中，形成了信息到数据点列的映射。要实现计算机系统智能识别信息和自动处理事务，就需要将保存于计算机中的数据点列进行识别，然后再根据预先设定的处理程序进行相应的自动处理。对数据点列的自动识别，就成了实现这一目标的关键。点列分类识别的实质就是将不同的点列进行对比，计算不同点列之间的相似度，根据相似度来确定某一点列是属于哪一类。

在已有的研究中，与本文相类似的研究是关于时间序列相似性度量。计算机记录数据时，是按照时间顺序记录存储的，因此形成的数据点列可以看作是时间序列数据。近年来，在有关时间序列相似性搜索方面，欧氏距离（Euclid Distance）、普通Lp规范距离（Simple LpNorm）、动态时间弯曲距离（Dynamic Time Warping，DTW）、DM模式距离（Pattern Distance）、Lpmin最小距离（Minimum Distance）[2-7]等在不同应用背景中均可作为度量相似性的有效方法。DM模式距离更接近自然语言描述，模式定义的物理意义明确，划分更趋合理，但其表示方法较粗糙，得出的结论不够明确。在此基础上，张建业等人提出了基于斜率表示的时间序列相似性度量方法[8]。该方法物理意义明确，具有直观性，且计算过程简洁；对于数据的大小不敏感，强调曲线形状的相似性，提高了相似性度量准确度，但该方法采用分段直线化方法，对于现实世界中的非离散信息数据进行相似性度量时，度量准确性就会下降，另外这些方法针对的是时间序列，并且要求参与度量的时间序列时间长度要一样，限制了适用范围。

本文从不同的角度出发，研究证明了曲线上点的切线向量组成的向量集对曲线形态特征有表征作用，如果将点列中的点以某种曲线相互连接起来，将其绘制成图来看，点列就有了自己的形态特征，相似的点列在形态上必然是相似的，反之亦然。但是如果将点与点之间全都用直线连接，不能准确地反映点列对应的现实信息的真实情况，误差较大。使用二次多项式曲线进行连接，在采样点足够密的条件下，则可以较为精确地逼近真实情况。然后计算曲线上各点的切线组成切线向量，计量不同点列的曲线切线向量之间的相似度，从而实现将点列所映射的现实信息进行了识别和分类的目标。

1 曲线的形态表示

寻找两条曲线的相似性度量的途径，考虑到连续曲线生成后，它的形态是唯一的，可以从曲线的形态上去对比分析做相似性度量，从而将曲线识别和分类。导数是微分学的基本概念，是函数的局部性质，一个函数在某一点的导数描述了这个函数在这一点附近的变化率[9]，对与函数对应的曲线变化有影响，重要的是，导数也具有唯一性。导数也即是函数在某点的切线的斜率。因此，连续曲线的形态与其上的点的切线有着密切联系。

1.1 曲线切线的特性

对于连续曲线，其上的任意一点均有且仅有一条切线，曲线切线不仅唯一，而且还有方向性，通过对连续曲线特点进行研究分析，连续曲线具有以下特点。

1.1.1 曲线缩放与切线变化

设一条连续曲线方程，为了简便，该曲线方程为多次单项式，但不影响最终结论。

对其放大m倍，得到：

对变换后的函数求导，得到：

对于（1）式中的任何一点p，将其放大m倍后代入（3）式中，可得到：

观察（4）式和（1）式求导后的p点导数可知，将曲线放大，对应点的导数保持不变，即曲线变换前后对应点处的切线向量平行。对于更一般的k次多项式曲线函数，由于其多项式中的每一项与（1）式类似，则k次多项式可同理证明。

从以上的论证可以看出，对一条曲线段进行等比例放大或者缩小，曲线段变换前后对应点处的切线向量平行。而对曲线段进行缩放不会改变曲线的形态特征。

因此可以得出结论一：两段曲线段的形态一样，则两段曲线对应各点的切线向量平行；改变两段曲线的等比例关系，即形态不再完全一样，则两段曲线对应各点的切线向量平行性也会改变。

反过来看，如果两曲线段上对应点处的切线向量平行，那么这两段曲线形态是否完全一样？经过研究论证，答案是肯定的，以下给出论证过程。

1.1.2 切线对曲线的约束

同样，设连续曲线的函数方程为：

则：

这里在x的定义域上取一区间段[a ,b]，使其满足对于任意x1,x2∈[a ,b]，都有

任意两点(x1,y1),(x2,y2)，设x2-x1=m(b-a)，将这两点平移，使x1移动到c点，使ma=c，对应的x2移动到d点，d=mb。对这两点同样用k次多项式拟合，并设多项式方程为：

则：

这里对于任意：

代入g(x)并在等号两侧同乘，得到：

由于常数项可以通过在Y轴上平移变为a0/m，整个等式等同于（1）式在区间[a,b]段的曲线等比例放大了m倍。由此可知，对于通过坐标平面上的任意两点的曲线段，在满足（2）的条件下，如果它在曲线段端点处的导数与（1）在端点处的导数对应相等，则这个曲线段与f(x)对应段成比例关系。从论证过程也不难看出，改变对应点切线向量之间的平行关系，就改变了两曲线段之间的比例关系，使两者之间的形态不再完全相同。也即是说，对于一条曲线，将其定义域划分为足够小的区间段，则可用其在所有区间段端点处的切线向量序列，刻画了曲线的形态。

从上面的论证可以得出结论二：如果两曲线段上对应点处的切线向量平行，那么这两段曲线大小成等比例关系，形态完全一样；如果两曲线段上对应点处的切线向量不平行，那么这两段曲线之间形态则不完全一样，只存在一定的相似度。

以上两个结论，共同指明了一点：对于两个曲线段，可以通过对比两者之间对应点处的切线向量之间的平行性关系，来判断两曲线段形态相似性程度。这就为本文讨论的方法提供了理论基础。

1.2 点列形态表示和度量

由于计算机系统的固有特点，任何信息采集记录到计算机中，都是以离散的数值保存。为了能够点列的形态特征量化，以利用前述连续曲线的形态可由曲线上点列的切线向量集合来表征的特性，需要将点列中的各点用连续曲线进行连接。将点列上的所有点用一个连续性方程进行连接，往往是难以实现的，因此，采用分段连续曲线连接。具体讲就是每次只取用少数几个点进行连续曲线连接，取点数量取决于选用的连续曲线方程的次数，然后依次进行分段连接直至点列终点。

1.2.1 点列连接及求切线向量集过程

在1.1小节的论证过程中，针对的是有限制的曲线段，在曲线段定义区间内，不能出现不同的点的切线向量相等。本文经过研究思考，选用二次多项式方程进行分段连接。在进行连接时，分两种情况进行考虑：

（1）第一种情况，参与对比的两列点列T和L分布对等。点列分布对等指的是将其中一列点列的横坐标经过某种比例缩放，或者还需要加上平移，之后能与另一列点列的横坐标重合。

这种情况的处理过程较为简单，分别对两列点列做如下操作：

①每次选取三个点的坐标作为已知量，代入二次多项式函数y=ax2+bx+c求出三个未知系数的值，得到某次分段连接的曲线函数Li和Ti，如此反复，直至点列终点。在取点时，为了准确性，上一分段的最后一个点，是下一分段的起点。

②分别求出Li和Ti上各点的切线，构成表征分段曲线形态的切线向量集DLi和DTi。

（2）除第一种情况的其他情况归为第二种情况。在这种情况下，不同点列的分布不仅不对等，还可能有点的密度分布不均匀，点列长度不一致等情形。因此需要进行数据处理，使其能够运用1.1小节中的理论。数据处理过程的核心就是找出两列点列中需要用来参与计算切线向量然后进行比对的点。处理过程步骤为：

①根据点列T和L的定义域区间求出区间比例值。

设T的定义区间为[a,b]，L的区间为[c,d]，区间比例值则为：

h=(b-a)(d-c)

②设曲线T、L对应的点列（横坐标）分别为：

若m>n，T对应点列中点的数量比L多，以L为基准，即对两列点列分别分段连接时，每次先对L进行分段连接，然后计算出T中应该连接的区间段。

③同第一种情况一样，上一分段连接的最后一个点，是[li,li+2]下一分段连接的起点。以第(i+1)2次分段连续曲线连接来说明，先对L以[li,li+2]区间的点进行连接，求出连接曲线方程Li；

④计算出 T对应的拟合区间为[(li-l1)h+t1,(li+2-l1)h+t1,]，找出该区间内T的点列[tj,tj+1,…,tk]，如果tj>(li-l1)h+t1，则往前搜索点并加入原有点列，直至满足tj≤(li-l1)h+t1。

⑤将T中 的 点 列[tj,tj+1,…,tk] 按 照 公 式(tj-t1)h+l1,(j=j,…,k)，分别求出点列[tj,tj+1,…,tk]在Li曲线段上对应的点横坐标，并与[li,li+2]组合后排序，同时剔除多余的相等元素后，分别代入Li曲线方程，求出表征Li曲线段的形态的切线向量集DLi。

⑥将T中该区间上的已知点[ ]tj,tj+1,…,tk，每三个点求解二次多项式连接函数，用公式(li-l1)h+t1,(i=i,i+1,i+2)求出Li曲线段上三个点对应于Ti曲线段上的三个横坐标点，将这三个点与[ ]tj,tj+1,…,tk组合在一起后排序，同时剔除多余的相等元素后，分别代入各自所属的曲线段方程，求出表征Ti曲线段的形态的切线向量集DTi。

1.2.2两点列相似性度量

根据1.1小节中的研究结论，两条曲线按照一定方法确定出参与比对的点的切线向量平行，两切线向量的夹角余弦值为1，则对应的曲线段形态相似度为1。如果切线向量不平行，两切线向量的夹角余弦值小于1，则说明曲线段形态相似度小于1。两切线向量的夹角余弦值小于1，余弦值越小，两曲线段形态差异越大。因此，可以通过计算和比较两条曲线上点的切线向量集对应切线向量的夹角余弦值，来对曲线相似性进行度量。

按照1.2.1中的方法得到两条曲线T和L的切线向量集：

2 实验结果及分析

本文的实验使用的平台为MATLAB，编程、绘制曲线图，以及观察分析结果都很方便。实验围绕验证本文方法的有效性、准确性、广泛适用性以及确定影响相似性度量的精度的因素展开，将对现实情况中可能出现的各种情况进行试验，实验过程、结果及分析如下：

（1）第一组实验：

曲线f1=2t2和f2=t2的相似度度量，这两条曲线不成比例关系，两者形态上的度量结果应当小于1。

取t1=-3:0.1:3；取t2=-3:0.1:3；用MATLAB作图如图1。

相似度度量结果：

R_mean=9.813076407741855e-01

取t1=-3:0.06:3；取t2=-3:0.1:3；用MATLAB作图如图2。

图1

图2

相似度度量结果：

R_mean=9.815434298610891e-01

取t1=-3:0.06:3；取t2=-3:0.06:3；用MATLAB作图如图3。

图3

相似度度量结果：

R_mean=9.813020769315147e-01

实验分析：

本组实验第一例和第三例中两列点的分布都是对等分布，第三例比第一例取点更密，虽然两者实验结果有差异，但仅有5.5e-06，第二例中两列点列点的分布疏密不同，虽然其中一列点的数量比第一例中多，但结果与第一例之间的差异为2.4e-04，是第一例和第三例之间差异的44倍。

本组实验结论：

参与度量的两列点列如果点的分布对等，取点疏密对度量结果的影响较小，但是当点的分布不对等，差异较大时，度量的精度相比点分布对等情形，受到较大影响。但总的来看，三个例子度量的结果是符合预期的，且两个例子结果之间的误差小，表明本文方法的有效性、准确性和稳定性。

（2）第二组实验：

曲线f1=sin t和f2=0.5sin(2t-1)的相似度度量，理论上，这两条曲线相似性度量结果应为1。

取t1=0:0.08:pi；取 t2=0.5:0.04:0.5(pi+1)；用MATLAB作图如图4。

图4

相似度度量结果：R_mean=1。

取t1=0:0.08:pi；取 t2=0.5:0.08:0.5(pi+1)；用MATLAB作图如图5。

相似度度量结果：

R_mean=9.999981555798608e-01

取t1=0:0.06:pi；t2=0.5:0.12:0.5(pi+1)；用MATLAB作图如图6。

相似度度量结果：

R_mean=9.999934377788184e-01

结果分析：本组实验得到的图形，无论从直观上看，还是从求得的相似度度量结果看，两条曲线的形态相似度很高，属于同一类型的曲线。实际上，本组实验提供点列数据所用的函数组，f2是f1先向左平移1，再等比例缩小0.5倍，所以两条曲线形态理论上完全一致，R_mean应当等于1。而实验中三个例子所得结果之间均有差异，原因在于：

①本组第一例中取点的情形属于1.2.1所述的第一种情况，两列点列的点分布对等，从1.1小节中的论证可知，成比例关系的曲线在对应点处的切线平行，切线夹角余弦值为1。虽然使用二次多项式函数连接点列，近似取代了原本正弦函数曲线，但是对两列点列都做同种连接，其成比例的性质不会改变，也即是两列点列的相似性不会改变，本例的结果也证明了这一点。

②本组三个例子的结果差异来自于两列点列取点密度不一致造成的。第一例中，两列点列取点密度为1:1，第二例为2:1，第三例为4:1，随着两列点列密度差异越大，相似性度量的结果越来越小。原因分析为，由于两列点列之间点的分布不对等时，需要按照1.2.1中第二种情况介绍的方法进行插值计算出两列点列参与计算切线的对应点，而二次多项式函数在连接点列中各点时，相对于点列分布对等情形，曲线段的形态会产生变形，因此结果会出现误差。

图5

图6

本组实验结论：

点列之间相似性的度量精度受到点列之间点的分布影响，不同点列之间点的分布差异性越大，则度量精度越低。

（3）第三组实验

曲线f1=cos(t-π)，f2=t2和f3=4t2，本组实验将不同类型的曲线放在一起进行对比观察。

取t1,t2,t3=-0.5pi:0.05:0.5pi；用MATLAB作图如图7。

相似度度量结果：

f1和f2相似度：

R_mean=9.354131466024146e-01

f1和f3相似度：

R_mean=7.223296489701438e-01

当取t1=-0.5pi:0.05:0.5pi；

t2=-0.5pi:0.07:0.5pi；

t3=-0.5pi:0.09:0.5pi；

相似度度量结果：

f1和f2相似度：

R_mean=9.358714811142291e-01

f1和f3相似度：

R_mean=7.225048915067527e-01

结果分析：从直观上看三条曲线的形态，f1和f2相似度高，f1和f3相似度低，对于不同的两条函数曲线，比较两者形态上的相似性，在给定的区间内，实验的结果也很好地符合了实际情况。另外，在不同的取点频率下，虽然度量结果有所差别，但差别很小，与前两组实验的结论是一致的。表明本文的方法准确性、稳定性较好。

（4）第四组实验

在前面的几组实验中，有一个共同点是，随着横坐标变化，一个横坐标始终只对应一个纵坐标值，对于一个横坐标有多个纵坐标值的复杂情况下，本文方法同样能够适用，只需要将数据做一个简单的分离，然后用前述方法进行比对即可。下面的实验以椭圆为例，来证明本文方法的广泛适用性。

取t1=-1:0.1:1；t2=-0.5:0.05:0.5；用MATLAB作图如图8。

由于横坐标同时对应两个纵坐标值，按照前面的步骤无法用二次多项式曲线进行连接，为此，需要对点列进行先行处理：

将点列进行搜索，找出同一个横坐标下有多个纵坐标值的点，按照纵坐标由大到小（或者由小到大）顺序依次分离出来组成新的点列，对其他点列也做同样处理，让后对新构成的点列分别按照本文前面所述的方法进行相似性度量。

在本例中，将椭圆分成上下两个部分，将两椭圆的上、下部分分别进行比对度量，用MATLAB作图如图9。

在实验中，对两部分分别进行相似性度量的结果均为1，与理论预期一致，表明了本文方法的准确性和广泛适用性。

3 结语

现实世界中用数学语言描述现象反映到计算机中，就成为计算机中保存的一系列点列，利用计算机技术对这些点列按照需求进行数据处理，自动识别其中包含的信息和特征，能够帮助人们进行自动处理和控制生产生活方面的事务。本文从曲线的形态特征入手，将计算机中保存的点列用连续函数进行分段拟合，求解出各点的切线，利用切线向量对曲线形态具有刻画作用的特点，通过计算两列点列拟合出的曲线的切线向量之间夹角余弦值，从而识别出两列点列之间的相似度。

图9

本文所述方法的主要创新点在于：

可以对计算机中的多种类型点列之间的相似度进行有效度量，而不用关注这些点列对应于现实世界中的是离散点集还是曲线，也不用关注曲线是否是连续的；对于参与度量的点列，不要求它们的长度大小相同，也不要求点在定义域上分布是否均匀，还可以对复杂的数据点列进行度量，如第四组实验，这些特点，使本方法具有广泛的适用性、通用性。

从研究探讨过程和实验结果可以看出，利用本文的方法可以有效的度量出两列点列整体的相似性关系。影响度量精度的最主要的因素是计算机在采集和记录信息时，采样频率和间隔如果保持一致，使不同点列中点的分布对等，那么度量的结果是完全准确的。另外，从本文所讲述的计算过程可以看出，在进行分段连接的同时，计算出了两列点列该分段的切线向量之间的余弦值，所以这个方法能够很方便地实现将点列各个分段的相似性程度也显示出来的功能，以方便人们观察分析。对于计算机计算出来相似性度量的结果，为人们提供了参考的依据，至于设置什么样阈值条件对点列所对应的现实世界中的信息进行分类和处理，则需要人们根据需要和经验进行设置。

本文所提出的方法，既可以使用二次多项式去进行分段曲线拟合，也可以使用其他多次多项式，使用二次多项式将给定点列进行分段拟合，原因在于二次多项式用于本文所研究的方法有诸多优点：

（1）现实情况中，无论是直线还是曲线，都可以用二次多项式分段近似取代。对于直线，在用直线上的点求二次多项式时，二次多项式可以退化为直线。对于任何曲线，只要将曲线分段充分小，就可用二次多项式去近似的取代。

（2）本文所提出的方法的数学理论基础为1.1小节中所证明的关于曲线的两个特性。用二次多项式拟合给定点列的三个点成为一段曲线，该曲线段的导数是单调的，始终可以满足1.1.2中（2）式的要求，。

（3）在求二次多项式方程系数时，只需要不共线三个点就可以求解，计算机计算二次函数运算量较小，可以提高计算机的运算效率，节约时间。

本文的研究集中于二维曲线，既然曲线上点的切线对曲线形态特征具有表征作用，那么可以很自然地推想到将该方法用于三维曲线相似性度量，这也是下一步研究方向。