location rs to rt,where the movement period for sample A is map(DA(f,tA),6)=DA(f/a(tA),tA),where a(t)is the [tA:tA+TA]and for sample B is [tB,tB+TBl.Without loss scaling factor function.Then the mapping function satisfies of generality,we assume TA TB. the following relationship: Then,the two spectrograms DA(f,t)and DB(f,t)satisfy N,f-1t≤tA3a=-二 the following relationship: map(DA(f,t),5)=DA(f/a(t),t)=a(t)DB(f,t),(6) DA(f,tA)=aDB(af,tB), (2) where o(1)is called scaling ratio of the current where t is in (ti,ti. speed distribution. Proof.Consider the ith micro-unit ui of the trajectory.Ac- cording to property 1,there exists oo =(tAi-tAi-1)/(tBi- Proof.We first consider a single part h of the hand,e.g.,the tBi-1)and we can scale the distribution of sample A at oo to index finger,that is moved by a small distance of dh from get the same distribution as sample B.So, location rs to rt.By our assumption that the movement speed DA(f/ao,t)=aoDB(f,t) (7) is constant for the short time duration,we have the movement speed of h,vh.A dh/TA,in sample A and vh,B=dh/TB Note that every micro-unit is small enough that the distribution in sample B.Therefore,we have Uh.A =Un.B/a,where a= in frequency domain is unchanged during this interval.From TA/TB. the above,we can get the complete expression of the scaling In the gesture signal,suppose there is a path p corresponding ratio,which is to the reflection from part h of the hand.Using the signal models in [3],we have: a(t)=a0= tAi-tA-1,tE(tAi-1t,iEN.(8) tBi-tBi-1 Sp(t)=Ape-j(wunt/c+0p) (3) ▣ where w is the carrier frequency of the passband signal.As Property 1 and 2 show that we can achieve speed alignment sample A and sample B start from the same location,we can between different samples by dynamically scaling the frequen- use the same Ap and p in Eq.(3). cies while ensuring that the aligned segments represent the Now consider the Fourier transform of gesture signal in same trajectory.Note that we can find the exact match between sample A.Sp.A(f,t)=F[sp.A(t)}: frequency distributions when the hand precisely follows the Sp.A(f,tA)=FApe-i(wh.A()/e0) trajectory r(t).In reality,the hand may deviate from the trajectory r(t)so that our goal is to minimize the difference FApe-joh((-i)/a)/e) between the matched frequency distributions. aSp.B(af,tB), (4) IV.DYNAMIC SPEED WARPING In this section,we design an optimization algorithm for where t1 E [tA,tA+TA]and t2 E [tB,tB+TB].In the last measuring similarity of gesture signals based on speed adapt- step,we use the time scaling property of the Fourier transform, ation properties derived in Section III.Our optimization prob- F()(f),where the capitalized function X(f) lem considers small variations in gesture trajectories so that is the Fourier transforms of the non-capitalized function x(t).our objective is to minimize the difference between gesture As Eq.(4)holds for all different parts of the hand,we spectrograms instead of finding the exact mapping functions can use the linearity of continuous-time Fourier transform as in Section III.We then present a dynamic programming Ffax(t)+by(t)}ax(f,t)+bY(f,t).to get: algorithm,which is similar to the DTW algorithm.to find the optimal solution that satisfies both the speed and the cumulative movement distance constraints.Finally,we show Da(f.ta) 下{图-图 the micro-benchmark of this similarity measure on gesture signals and discuss the impact of parameters for the algorithm. DB(af,tB) (5) A.Problem Formulation ◇ In reality,the gesture spectrogram is discretized in both the time and the frequency domain.Given two spectrograms Property 2.Consider that two gesture signal samples A X[n],n 1...N and Y[m];m 1...M,where[n]is the and B of the same gesture type.We can divide the entire spectral of time-frame n.Consider a discrete warping function trajectory into micro-units u1,u2,....Assume that the time F[k=c().k 1...K,where c(k)=(i(k),j()),such that sample A passes through these micro-units in turn is that maps the spectral of X[i(k)]onto that of Y[j(k)]at the tA1,tA2,...while the time for sample B is tB1,tB2,.... kth warping.Here,i()and j(k)represents the frame index There exists a mapping function:R×Rd→R×Rd that of X and Y,respectively.The warping function should be: IIf there are more than one path corresponds to a single hand component. 2Note that (t)can be greater than 1 here,which means that in the current we can treat each path as a separate component with a different path speed micro-unit,the sample B is mapped to the sample A at the scaling ratio of and the above result still holds. 1/a(t).location rs to rt, where the movement period for sample A is [tA, tA + TA] and for sample B is [tB, tB + TB]. Without loss of generality, we assume TA  TB. Then, the two spectrograms DA(f, t) and DB(f, t) satisfy the following relationship: DA(f, tA) = ↵DB(↵f, tB), (2) where ↵ (↵ = TA TB  1) is called scaling ratio of the current speed distribution. Proof. We first consider a single part h of the hand, e.g., the index finger, that is moved by a small distance of dh from location rs to rt. By our assumption that the movement speed is constant for the short time duration, we have the movement speed of h, vh,A = dh/TA, in sample A and vh,B = dh/TB in sample B. Therefore, we have vh,A = vh,B/↵, where ↵ = TA/TB. In the gesture signal, suppose there is a path p corresponding to the reflection from part h of the hand1. Using the signal models in [3], we have: sp(t) = Ape￾j(!vht/c+✓p) , (3) where ! is the carrier frequency of the passband signal. As sample A and sample B start from the same location, we can use the same Ap and ✓p in Eq. (3). Now consider the Fourier transform of gesture signal in sample A, Sp,A(f, t) = F{sp,A(t)}: Sp,A(f, tA) = F n Ape￾j(!vh,A(t1￾tA)/c+✓p) o = F n Ape￾j(!vh,B((t2￾tB)/↵)/c+✓p) o = ↵Sp,B(↵f, tB), (4) where t1 2 [tA, tA + TA] and t2 2 [tB, tB + TB]. In the last step, we use the time scaling property of the Fourier transform, F{x(kt)} = 1 |k|X(f /k), where the capitalized function X(f) is the Fourier transforms of the non-capitalized function x(t). As Eq. (4) holds for all different parts of the hand, we can use the linearity of continuous-time Fourier transform F{ax(t) + by(t)} = aX(f, t) + bY (f, t), to get: DA(f, tA) = ￾ ￾ ￾ ￾ ￾ F (X p2P sp,A(tA) )￾ ￾ ￾ ￾ ￾ = ￾ ￾ ￾ ￾ ￾ X p2P Sp,A(f, tA) ￾ ￾ ￾ ￾ ￾ = ￾ ￾ ￾ ￾ ￾ X p2P ↵Sp,B(↵f, tB) ￾ ￾ ￾ ￾ ￾ = ↵DB(↵f, tB) (5) Property 2. Consider that two gesture signal samples A and B of the same gesture type. We can divide the entire trajectory into micro-units u1, u2, ··· . Assume that the time that sample A passes through these micro-units in turn is tA1, tA2, ··· while the time for sample B is tB1, tB2, ··· . There exists a mapping function ￾ : R ⇥ R+ 0 ! R ⇥ R+ 0 that 1If there are more than one path corresponds to a single hand component, we can treat each path as a separate component with a different path speed and the above result still holds. map(DA(f, tA), ￾) = DA(f /↵(tA), tA), where ↵(t) is the scaling factor function. Then the mapping function satisfies the following relationship: 8i 2 N⇤, if tAi￾1  t  tAi, 9 ↵(t) = tAi￾tAi￾1 tBi￾tBi￾1 , map(DA(f, t), ￾) = DA(f /↵(t), t) = ↵(t)DB(f, t0 ), (6) where t 0 is in (tBi￾1, tBi] 2. Proof. Consider the ith micro-unit ui of the trajectory. Ac￾cording to property 1, there exists ↵0 = (tAi ￾ tAi￾1)/(tBi ￾ tBi￾1) and we can scale the distribution of sample A at ↵0 to get the same distribution as sample B. So, DA(f /↵0, t) = ↵0DB(f, t0 ) (7) Note that every micro-unit is small enough that the distribution in frequency domain is unchanged during this interval. From the above, we can get the complete expression of the scaling ratio, which is ↵(t) = ↵0 = tAi ￾ tAi￾1 tBi ￾ tBi￾1 , t 2 (tAi￾1 , tAi] , i 2 N⇤ . (8) Property 1 and 2 show that we can achieve speed alignment between different samples by dynamically scaling the frequen￾cies while ensuring that the aligned segments represent the same trajectory. Note that we can find the exact match between frequency distributions when the hand precisely follows the trajectory r(t). In reality, the hand may deviate from the trajectory r(t) so that our goal is to minimize the difference between the matched frequency distributions. IV. DYNAMIC SPEED WARPING In this section, we design an optimization algorithm for measuring similarity of gesture signals based on speed adapt￾ation properties derived in Section III. Our optimization prob￾lem considers small variations in gesture trajectories so that our objective is to minimize the difference between gesture spectrograms instead of finding the exact mapping functions as in Section III. We then present a dynamic programming algorithm, which is similar to the DTW algorithm, to find the optimal solution that satisfies both the speed and the cumulative movement distance constraints. Finally, we show the micro-benchmark of this similarity measure on gesture signals and discuss the impact of parameters for the algorithm. A. Problem Formulation In reality, the gesture spectrogram is discretized in both the time and the frequency domain. Given two spectrograms X[n], n = 1 ...N and Y [m], m = 1 ...M, where X[n] is the spectral of time-frame n. Consider a discrete warping function F[k] = c(k),k = 1 ...K, where c(k)=(i(k), j(k)), such that maps the spectral of X[i(k)] onto that of Y [j(k)] at the kth warping. Here, i(k) and j(k) represents the frame index of X and Y , respectively. The warping function should be: 2Note that ↵(t) can be greater than 1 here, which means that in the current micro-unit, the sample B is mapped to the sample A at the scaling ratio of 1/↵(t)