基于曲線形態的曲線相似性度量

陳濤

（四川大學計算機學院，成都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）在求二次多項式方程系數時，只需要不共線三個點就可以求解，計算機計算二次函數運算量較小，可以提高計算機的運算效率，節約時間。

本文的研究集中于二維曲線，既然曲線上點的切線對曲線形態特征具有表征作用，那么可以很自然地推想到將該方法用于三維曲線相似性度量，這也是下一步研究方向。