Time Warp Edit Distance

Definition

δ λ , ν ( A 1 p , B 1 q ) = M i n { δ λ , ν ( A 1 p − 1 , B 1 q ) + Γ ( a p ′ → Λ ) d e l e t e   i n   A δ λ , ν ( A 1 p − 1 , B 1 q − 1 ) + Γ ( a p ′ → b q ′ ) a g r e e m e n t δ λ , ν ( A 1 p , B 1 q − 1 ) + Γ ( Λ → b q ′ ) d e l e t e   i n   B
whereas

Γ ( α p ′ → Λ ) = d L P ( a p ′ , a p − 1 ′ ) + ν ⋅ ( t a p − t a p − 1 ) + λ
Γ ( α p ′ → b q ′ ) = d L P ( a p ′ , b q ′ ) + d L P ( a p − 1 ′ , b q − 1 ′ ) + ν ⋅ ( | t a p − t b q | + | t a p − 1 − t b q − 1 | )
Γ ( Λ → b q ′ ) = d L P ( b p ′ , b p − 1 ′ ) + ν ⋅ ( t b q − t b q − 1 ) + λ

Whereas the recursion δ λ , ν is initialized as:
δ λ , ν ( A 1 0 , B 1 0 ) = 0 ,
δ λ , ν ( A 1 0 , B 1 j ) = ∞   f u ¨ r   j ≥ 1
δ λ , ν ( A 1 i , B 1 0 ) = ∞   f u ¨ r   i ≥ 1
with a 0 ′ = b 0 ′ = 0

Implementation

An implementation of the TWED-Algorithm in C or Matlab can be downloaded from the authors's homepage