基于動態(tài)時間彎曲的軌道波形匹配方法

朱洪濤， 李 姍， 肖 勇， 魏 暉(南昌大學(xué) 機(jī)電工程學(xué)院，南昌 330031)

軌道平直度測量儀(簡稱平直尺)利用激光測距原理，可實時將所測軌道波形以數(shù)據(jù)的形式反映出來。目前市場上生產(chǎn)的平直尺，在實際工程上主要有兩方面的應(yīng)用：一方面是為了測量鋼軌的焊縫，以此來評價鋼軌焊縫的焊接質(zhì)量[1]；另一方面是為了分析軌道表面的短波不平順，對某段鋼軌的波形進(jìn)行處理和分析[2]。由于測量采用靜態(tài)測量方法[3]，并且因測量裝置的限制，僅通過平直尺的單次測量難以滿足測量要求，故需要進(jìn)行多次測量，再利用匹配技術(shù)對數(shù)據(jù)進(jìn)行整合和分析，來客觀顯示軌道上的短波變化規(guī)律。

目前在軌道短波的匹配研究中，Kong等[4]采用動態(tài)規(guī)劃(DP)算法，對二維曲線進(jìn)行匹配，但未考慮曲線不完全匹配的情況；Ucoluk等[5]研究了曲線的自動匹配問題，但在局部匹配中采用了窮舉法，這使匹配復(fù)雜度較高而匹配效率低下，并且沒有運(yùn)用到實際測量中進(jìn)行測試，缺乏說服力；余先川等[6]提出基于區(qū)域的匹配，該方法一般通過求解曲線相關(guān)系數(shù)來實現(xiàn)，但計算量大，運(yùn)行時間較長；牛小兵等[7]提出了基于特征的匹配方法，可以提取有縮放、平移和旋轉(zhuǎn)不變性的特征點，具有快速、準(zhǔn)確的特點，但如果特征點的提取不好，則會產(chǎn)生較大的誤差，嚴(yán)重影響匹配效果。以上這些傳統(tǒng)匹配算法只能對坐標(biāo)系內(nèi)的曲線進(jìn)行剛性的變換和匹配，無法解決不同坐標(biāo)系下曲線的動態(tài)匹配問題。

本文利用二維坐標(biāo)轉(zhuǎn)換公式，將待匹配曲線經(jīng)旋轉(zhuǎn)和平移后，統(tǒng)一到同一坐標(biāo)系下?；诖?，提出了一種基于動態(tài)時間彎曲(DTW)的軌道短波匹配方法，通過對橫坐標(biāo)時間軸的彎曲和變形，發(fā)現(xiàn)相似波形并構(gòu)造累積代價矩陣；利用遞歸思想，可計算兩條曲線的最短彎曲路徑，并求出兩條待匹配曲線之間的單點對應(yīng)關(guān)系，以此來進(jìn)行精準(zhǔn)的點對點匹配，從而實現(xiàn)了軌道短波的精準(zhǔn)動態(tài)匹配。

1 系統(tǒng)的構(gòu)成及測量原理

1.1 系統(tǒng)的構(gòu)成

測量系統(tǒng)主要由激光位移傳感器、編碼器、接近開關(guān)、步進(jìn)電機(jī)、步進(jìn)電機(jī)驅(qū)動器、STC單片機(jī)及上位機(jī)組成，測量系統(tǒng)的結(jié)構(gòu)圖如圖1所示。

圖1 測量系統(tǒng)結(jié)構(gòu)圖Fig.1 Structure diagram of measuring system

1.2 系統(tǒng)測量原理

設(shè)定激光傳感器在導(dǎo)軌上運(yùn)動一次時，所采集的數(shù)據(jù)點為N個。將第一點的測量值y0作為參考點，激光器向后測量的N-1個點y1至yN-1中，利用第一點的測量值y0依次減去其他被測點yi(i=1,2,…,N-1)，則可求出兩點之間的相對距離y，即

y=y0-yi(i=1,2,…,N-1)

(1)

通過獲取傳感器探頭與被測軌面之間的距離，可以間接表示出所測鋼軌的表面形狀曲線。測量原理圖如圖2所示。

2 匹配前的坐標(biāo)轉(zhuǎn)換

在實際測量過程中，由于受軌道原始形狀的影響，每次測量的數(shù)據(jù)是在不同坐標(biāo)系下完成的，如圖3所示。所以，為了進(jìn)一步對數(shù)據(jù)進(jìn)行匹配，首先需要將數(shù)據(jù)進(jìn)行坐標(biāo)系的轉(zhuǎn)換，將所測數(shù)據(jù)統(tǒng)一在同一坐標(biāo)系下。

圖2 測量系統(tǒng)原理圖(mm)Fig.2 Schematic diagram of measuring system(mm)

圖3 實際測量坐標(biāo)圖Fig.3 Practical measurement coordinate diagram

設(shè){o;x,y}和{o;x(1),y(1)}為測量平面的兩組坐標(biāo)系，橫坐標(biāo)表示測量里程，縱坐標(biāo)為軌道短波不平順值。對于軌道表面的同一測量點a，在不同位置下的測量值因坐標(biāo)系的不同而不同。如圖4所示，坐標(biāo)系{o;x(1),y(1)}相對于坐標(biāo)系{o;x,y}平移了(x0,y0)，且逆時針旋轉(zhuǎn)了角度θ，使得測量點a在{o;x,y}和{o;x(1),y(1)}兩坐標(biāo)系下的測量值分別為(x,y)和(x1,y1)，為了將測量重復(fù)段內(nèi)的數(shù)據(jù)進(jìn)行匹配，須對坐標(biāo)系進(jìn)行統(tǒng)一和轉(zhuǎn)換。

圖4 不同坐標(biāo)系下的數(shù)值顯示Fig.4 Numerical display in different coordinates

坐標(biāo)轉(zhuǎn)換公式為

x=x1cosθ-y1sinθ+x0

y=x1sinθ+y1cosθ+y0

(2)

將式(2)轉(zhuǎn)化為矩陣表達(dá)式為

(3)

Ai-1=RiAi+Bi-1(i=1,2,…,n)

(4)

根據(jù)迭代思想，將其他i個坐標(biāo)系轉(zhuǎn)換到第一個坐標(biāo)系{o;x,y}的轉(zhuǎn)換表達(dá)式為

(5)

3 基于動態(tài)時間彎曲的波形匹配算法

動態(tài)時間彎曲(Dynamic Time Warping,DTW)算法由于具有很好的魯棒性，較高的匹配精度，通常應(yīng)用在語音識別等模式識別領(lǐng)域[8-9]。該算法通過對橫坐標(biāo)時間軸的扭曲和變換，發(fā)現(xiàn)相似波形，使其特征與參考模板進(jìn)行匹配[10]。由于實際測量過程中，每次測量方向和角度的變化以及人為或環(huán)境影響的偶然誤差存在，使所測重合部分的數(shù)據(jù)不會完全相同，測量曲線在匹配過程中會有一定的變形和偏差。故在匹配過程中，需要對待匹配曲線的橫坐標(biāo)進(jìn)行彎曲變形后，才能進(jìn)行高精度的動態(tài)匹配。引入DTW算法，從而實現(xiàn)了軌道波形的精準(zhǔn)點對點匹配。

3.1 動態(tài)時間彎曲算法原理

由測量原理可知，數(shù)據(jù)采集中的橫坐標(biāo)是每隔5 mm測一個點，等距測量可以等效為等時間間隔測量，故可將橫軸的里程等價為時間來衡量。假設(shè)在第i個坐標(biāo)系{o;x(i),y(i)}內(nèi)的N個測量數(shù)據(jù)存放在時間序列P，在第i-1個坐標(biāo)系{o;x(i-1),y(i-1)}內(nèi)的M個數(shù)據(jù)存放在時間序列Q，那么

P=[p1,p2,p3,…,pn,…,pN]

Q=[q1,q2,q3,…,qm,…,qM]

定義距離函數(shù)：dij=f(pi,qj)。

其中f表示實際采用的測距函數(shù)，最常用的是二階距離[11]，即：

(6)

由式(6)可知，根據(jù)時間序列P、Q內(nèi)不同數(shù)據(jù)對象之間點與點的歐氏距離，構(gòu)成了N×M的動態(tài)時間扭曲距離矩陣d

在矩陣d中，相鄰矩陣元素的集合構(gòu)成了一條彎曲路徑，記為W={w1,w2,…，wk}，其中W中的第k個元素wk=(dij)k。彎曲路徑需滿足以下條件[12-13]

(1)有界性：w1=d11，wk=dMN；

(2)連續(xù)性：若wk=(pa,qb)，wk-1=(pa′,qb′)，則有0≤|a-a′|≤1,0≤|b-b′|≤1;

(3)單調(diào)性：若wk=(pa,qb)，wk-1=(pa′,qb′)，則有a≥a′,b≥b′;

(4)邊界條件：彎曲路徑中的總元素數(shù)k需滿足max(M,N)≤k≤M+N-1；

由彎曲路徑的必要條件可知，滿足上述條件的彎曲路徑不止一條，根據(jù)窮舉法，可以將所有的彎曲路徑一一列出。但時間序列P和Q的DTW距離指兩時間序列間的最短彎曲路徑Wbest[14]

(7)

其中K為消除時間序列長度不一的影響因子。

為求解式(7)，由遞歸思想，構(gòu)造累積代價矩陣γ，即

(8)

式(8)中，i=1，2，…，N；j=1,2,……，M，γ(0,0)=0，γ(i,0)=γ(0，j)=+∞故時間序列P和Q的DTW距離為

DTW(P，Q)=γ(N，M)

(9)

3.2 數(shù)據(jù)匹配算法的實現(xiàn)

由平直尺的測量原理可知，前后兩次測量數(shù)據(jù)的時間序列P和Q中有一半數(shù)據(jù)是重復(fù)測量所得。若要將相似的時間序列Pi和Qj匹配，首先通過求解彎曲路徑曲線W的距離，找到經(jīng)過時間軸的彎曲和變形后兩個時間序列之間的最短彎曲路徑Wbest(即DTW距離)，并在此過程中確定兩時間序列各點的最佳對應(yīng)關(guān)系。如圖5所示。

圖5 最短彎曲路徑下各點對應(yīng)關(guān)系Fig.5 One-to-one match in the shortest bending

由圖5中的最佳對應(yīng)關(guān)系確定的最佳彎曲路徑圖,如圖6所示。

圖6 最佳彎曲路徑圖Fig.6 The optimum bending path diagram

對于最短彎曲路徑下的各點對應(yīng)關(guān)系，存在以下幾種情況[15]

①單點對應(yīng)：Pi中的一個元素和Qj中的唯一元素相對應(yīng)；

②多點對應(yīng)：Pi中的一個元素和Qj中的多個元素相對應(yīng)或Qj中的一個元素和Pi中的多個元素相對應(yīng)。由彎曲路徑的必要條件可知，Qj和Pi中的多個元素在時間序列上是連續(xù)的。

對于單點對應(yīng)的情況，表明兩時間序列有唯一最優(yōu)解，兩點已匹配成功。現(xiàn)在假設(shè)

4 數(shù)據(jù)匹配實驗及分析

4.1 數(shù)據(jù)匹配實驗

對于前后兩次測量的數(shù)據(jù)，首先經(jīng)過坐標(biāo)系的旋轉(zhuǎn)和平移，將數(shù)據(jù)統(tǒng)一到同一坐標(biāo)系下。為了保證后期匹配的高精度，則要判斷兩條曲線相似部分是否對齊，即是否完全統(tǒng)一在同一坐標(biāo)系下。構(gòu)造目標(biāo)函數(shù)H(x)

(10)

其中，y為標(biāo)準(zhǔn)坐標(biāo)系{o;x,y}下的函數(shù)，y′為通過坐標(biāo)轉(zhuǎn)換后的函數(shù)，n為測量曲線中的數(shù)據(jù)總量。旋轉(zhuǎn)和平移量在迭代過程中不斷變化，使目標(biāo)函數(shù)H(X)的值不斷變化，當(dāng)目標(biāo)函數(shù)H(X)值最小時，則判定為兩條曲線相似部分對齊，此時的旋轉(zhuǎn)和平移量認(rèn)為最佳值。由實際測量可知，相鄰兩次測量的角度偏移量較小，雖然人為因素或環(huán)境因素引起的偶然誤差存在，但對后期的匹配影響不大，故旋轉(zhuǎn)和平移誤差有較好的魯棒性。

根據(jù)測量原理可確定相似波形段，利用動態(tài)時間彎曲算法求解出相似波形段中的單點對應(yīng)關(guān)系，進(jìn)而對數(shù)據(jù)進(jìn)行匹配和處理。匹配流程圖如圖7所示。

圖7 短波匹配流程圖Fig.7 Shortwave matching flow chart

匹配后的圖像如圖8所示。

圖8 軌道波形匹配圖Fig.8 Rail shortwave matching diagram

4.2 匹配算法的比較與評價

由動態(tài)時間彎曲算法原理及實現(xiàn)過程可知，最短彎曲路徑下所對應(yīng)的DTW值，間接反映了兩條曲線的相似度即匹配的好壞。兩曲線匹配的越好，其相似度越高，最短彎曲路徑越短，對應(yīng)的DTW數(shù)值越?。粌汕€匹配越差，匹配曲線越不相似，最短彎曲路徑越長，對應(yīng)的DTW值也越大。理想情況下，兩條匹配曲線完全匹配時求解的最短彎曲路徑為0，即DTW值為0。

由文獻(xiàn)[16-17]可知，傳統(tǒng)匹配方法中常用的方法是基于區(qū)域的數(shù)據(jù)匹配，該算法通過求解曲線相關(guān)系數(shù)來實現(xiàn)。本文以傳統(tǒng)匹配算法中的基于區(qū)域的匹配算法為代表，比較動態(tài)時間彎曲算法與傳統(tǒng)匹配方法的匹配精度問題。對同一測量數(shù)據(jù)分別利用傳統(tǒng)匹配算法和動態(tài)時間彎曲算法匹配，匹配圖像如圖9所示。

(a) 基于區(qū)域的傳統(tǒng)算法匹配

(b) 動態(tài)時間彎曲算法匹配圖9 兩種算法的波形匹配圖Fig.9 Waveforms mosaic based on two algorithms

通過DTW距離計算式(7)～(9)可知，圖9(a)的DTW值為0.012 4，圖9(b)的DTW值為0.003 3。

利用平直尺對某段鋼軌進(jìn)行測量。為了不失一般性，在所測60組數(shù)據(jù)中分別利用傳統(tǒng)匹配算法和動態(tài)時間彎曲算法進(jìn)行曲線匹配，并求解匹配后所對應(yīng)的DTW值。兩種算法的DTW值如圖10所示。

圖10 兩種算法的DTW值Fig.10 The value of DTW by using two algorithms

對以上60組數(shù)據(jù)進(jìn)行數(shù)據(jù)統(tǒng)計分析，可求出兩種算法下的DTW均值；對數(shù)據(jù)標(biāo)準(zhǔn)化處理后，可通過標(biāo)準(zhǔn)差的大小反映兩種算法的穩(wěn)定性[18]，如表1所示。

表1 兩種匹配算法的數(shù)值統(tǒng)計Tab.1 Numerical statistics by using two algorithms

由表1可知，通過傳統(tǒng)算法匹配所求得的DTW均值為0.030 2，約是動態(tài)時間彎曲算法匹配所得DTW均值(0.004 4)的10倍，即通過動態(tài)時間彎曲算法進(jìn)行的數(shù)據(jù)匹配，匹配精度比基于區(qū)域的傳統(tǒng)匹配算法的匹配精度提高約10倍，匹配效果比傳統(tǒng)匹配算法好。并且，將兩組數(shù)據(jù)標(biāo)準(zhǔn)化處理后所求得的標(biāo)準(zhǔn)差表明，利用動態(tài)時間彎曲算法進(jìn)行的數(shù)據(jù)匹配，匹配穩(wěn)定性較好，沒有出現(xiàn)誤差較大的情況。

5 結(jié) 論

本文基于動態(tài)時間彎曲算法對軌道波形進(jìn)行匹配，通過構(gòu)造累積代價矩陣，利用遞歸思想，可計算兩條曲線的最短彎曲路徑，并求出兩條待匹配曲線之間的單點對應(yīng)關(guān)系，從而進(jìn)行數(shù)據(jù)點與點之間的精準(zhǔn)動態(tài)匹配。將傳統(tǒng)匹配中基于區(qū)域的匹配算法與動態(tài)時間彎曲算法作比較，實驗結(jié)果表明：

(1)基于動態(tài)時間彎曲的匹配方法，解決了傳統(tǒng)匹配方法中剛性匹配的問題。通過對橫坐標(biāo)軸的彎曲變形，可找到待匹配曲線的最佳匹配關(guān)系，實現(xiàn)精準(zhǔn)的動態(tài)匹配。

(2)基于動態(tài)時間彎曲的匹配精度比傳統(tǒng)匹配算法高約10倍，能較好的對測量數(shù)據(jù)進(jìn)行匹配。

(3)基于動態(tài)時間彎曲算法下的DTW值標(biāo)準(zhǔn)差為0.248 1，比基于區(qū)域的傳統(tǒng)匹配方法標(biāo)準(zhǔn)差小，故基于動態(tài)時間彎曲算法的匹配穩(wěn)定性較好，可信度較高。

(4)本算法還可以運(yùn)用在測量數(shù)據(jù)的重復(fù)性分析、鋼軌輪廓匹配、測量曲線相似比較等方面。

參 考 文 獻(xiàn)

[1] 程小紅. 鋼軌焊接接頭平直度檢測儀研制[D]. 成都: 西南交通大學(xué),2010.

[2] YAN Ziquan, GU Aijun, LIU Weining, et al. Effects of wheelset vibration on initiation and evolution of rail short-pitch corrugation[J]. Journal of Central South University,2012(9):2681-2688.

[3] JELALI M.Performance assessment of control systems in rolling mills-application to strip thick thickness and flatness control[J]. Journal of Process Control, 2007,17:805-816.

[4] KONG W,KIMIA B B. On solving 2D and 3D puzzles using curve matching[C]∥Proceedings of the CVPR.Hawaii, USA,2001.

[5] UCOLUK G, TOROSLUL H. Automatic reconstruction of broken 3-D surface objects[J]. Computers and Graphics, 1999, 23(4):573-582.

[6] 余先川,呂中華,胡丹.遙感圖像配準(zhǔn)技術(shù)綜述[J]. 光學(xué)精密工程,2013(11):2960-2972.

YU Xianchuan,Lü Zhonghua,HU Dan.Reviwe of remote sensing image registration techniques[J].Optics and Precision Engineering, 2013(11):2960-2972.

[7] 牛小兵,林玉池,趙美蓉,等.基于特征的二維圖像匹配法測量幾何量[J].天津大學(xué)學(xué)報,2001(3):396-339.

NIU Xiaobing,LIN Yuchi,ZHAO Meirong, et al.Measurement of geometric parameters based on feature based image mosaic method[J].Journal of TianJin University,2001(3):396-399.

[8] 肖輝,胡運(yùn)發(fā). 基于分段時間彎曲距離的時間序列挖掘[J]. 計算機(jī)研究與發(fā)展,2005(1):72-78.

XIAO Hui,HU Yunfa.Data mining based on segmented time warping distance in time series database[J].Journal of Computer Research and Development,2005(1):72-78.

[9] 李正欣,張鳳鳴,李克武,等. 一種支持DTW距離的多元時間序列索引結(jié)構(gòu)[J]. 軟件學(xué)報,2014(3):560-575.

LI Zhengxin,ZHANG Fengming,LI Kewu, et al.Index structure for multivariate time series under DTW distance metric[J].Journal of Software,2014(3):560-575.

[10] 鄒朋成,王建東,楊國慶,等. 輔助信息自動生成的時間序列距離度量學(xué)習(xí)[J]. 軟件學(xué)報,2013(11):2642-2655.

ZOU Pengcheng,WANG Jiandong,YANG Guoqing, et al. Distance metric learning based on side information autogeneration for time series[J]. Journal of Software,2013(11):2642-2655.

[11] 楊靖. 基于動態(tài)時間彎曲的時間序列相似性搜索技術(shù)的研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),2013.

[12] 鄒朋成,王建東,楊國慶,等. 輔助信息自動生成的時間序列距離度量學(xué)習(xí)[J]. 軟件學(xué)報,2013(11):2642-2655.

ZOU Pengcheng,WANG Jiandong,YANG Guoqing, et al.Distance metric learning based on side information autogeneration for time series[J].Journal of Software,2013(11):2642-2655.

[13] PREKOPCSAK Z,LEMIRE D. Time series classification by class-specific Mahalanobis distance measures[J]. Advances in Data Analysis and Classification, 2012,6(3):185-200.

[14] GHAREHBAGHI A, ASK P, BABIC A. A pattern recognition framework for detecting dynamic changes on cyclic time series[J]. Pattern Recognition, 2015, 48(3):696-708.

[15] 杜永峰,李萬潤,李慧,等. 基于時間序列分析的結(jié)構(gòu)損傷識別[J].振動與沖擊,2012,31(12):108-111.

DU Yongfeng,LI Wanrun,LI Hui, et al. Structural damage identification based on time series analysis[J]. Journal of Vibration and Shock,2012,31(12):108-111.

[16] 嚴(yán)大勤,孫鑫. 一種基于區(qū)域匹配的圖像匹配算法[J]. 儀器儀表學(xué)報,2006(增刊1):749-750.

YAN Daqin,SUN Xin.Image mosaics algorithm based on area matching[J].Chinese Journal of Scientific Instrument,2006(Sup1):749-750.

[17] 顧費(fèi)勇. 基于圖像的自適應(yīng)圖像匹配算法研究[D].杭州:浙江大學(xué),2008.

[18] 蔣瑜,陶俊勇,王得志,等. 一種新的非高斯隨機(jī)振動數(shù)值模擬方法[J]. 振動與沖擊,2012,31(19):169-173.

JIANG Yu,TAO Junyong,WANG Dezhi, et al. A novel approach for numerical simulation of a non-Gaussian random vibration[J].Journal of Vibration and Shock,2012,31(19):169-173.