Patent ID: 8639506

Claim:
A method of determining the matching between a first and a second sampled signals using an improved Dynamic Time Warping algorithm wherein the matching is determined by finding the optimal paths through a matrix of points representing possible time alignments between the signals, the method comprising the steps of: (a) generating a sequence of first feature vectors U:=(u 1 ; u 2 ; . . . ; u M ) and second feature vectors V:=(v 1 ; v 2 ; . . . ;v N ) that represent temporal and spectral behavior of the first and second signals respectively; (b) setting a similarity matrix D g (m; n) and a length matrix M(m;n) as empty at start up; (c) defining appropriate synchronization points, SP, in locations (m,n); (d) calculating a similarity S(m;n) for the synchronization points, wherein S(m; n) is defined between any two feature vectors, u m and v n , as a distance between the vectors, and (e) for each synchronization point, m;n (i) setting M(m;n)=1, (ii) applying a forward path algorithm for the point, (iii) for all paths found in the previous step whose length exceeds the minimum length L min , L min being a predefined parameter, applying a backward path algorithm for the synchronization point where the path starts, (iv) selecting the longest of all paths that pass through the considered SP and return a total path, backwards and forwards, and its average score if it exceeds the minimum length L min in both dimensions; wherein the path algorithms comprise the following steps: for the considered point (m; n), set (m′; n′)=(m; n)+(i; j), where (i; j)ε{(1; 1); (1; 2); (2; 1) . . . ; (r; r−1)} for the forward path and (i; j)ε{(−1;−1); (−1;−2); (−2;−1 . . . (−s;−(s−1))} for the backward path where r and s are predefined parameters; for each considered value of m′;n′ if the following conditions are met: the normalized global similarity score of the current path is greater than any previous paths, if any, at that location, wherein Dg ⁡ ( m , n ) + S ⁡ ( m ′ , n ′ ) M ⁡ ( m , n ) + 1 > Dg ⁡ ( m ′ , n ′ ) M ⁡ ( m ′ ⁢ n ′ ) if there is no previous paths at that location (M(m′,n′)=0), only the second condition is evaluated; the normalized global similarity is greater than a predefined cutoff threshold Thr, wherein Dg ⁡ ( m , n ) + S ⁡ ( m ′ , n ′ ) M ⁡ ( m , n ) + 1 > Thr adding a new frame-pair position (m′; n′) to the currently considered path; M(m′, n′) is set to M(m, n)+1; Dg(m′, n′) is set to Dg(m, n)+S(m′, n′) and applying the path algorithm again from the point m′;n′, the new point m;n being considered is m;n=m′; n′; and iteratively processing while the conditions are met for each considered point.