Efficient processing of warping time series join of motion capture data

Abstract

Discovering non-trivial matching subsequences from two time series is very useful in synthesizing novel time series. This can be applied to applications such as motion synthesis where smooth and natural motion sequences are often required to be generated from existing motion sequences. We first address this problem by defining it as a problem of l-ε-join over two time series. Given two time series, the goal of l-ε-join is to find those non-trivial matching subsequences by detecting maximal l-connections from the ε-matching matrix of the two time series. Given a querying motion sequence, the l-ε-join can be applied to retrieve all connectable motion sequences from a database of motion sequences. To support efficient l-ε-join of time series, we propose a two-step filter-and-refine algorithm, called Warping Time Series Join (WTSJ) algorithm. The filtering step serves to prune those sparse regions of the ε-matching matrix where there are no maximal l-connections without incurring costly computation. The refinement step serves to detect closed l-connections within regions that cannot be pruned by the filtering step. To speed up the computation of ε-matching matrix, we propose a blockbased time series summarization method, based on which the block-wise ε-matching matrix is first computed. Lots of pairwise distance computation of elements can then be avoided by applying the filtering algorithm on the block-wise ε-matching matrix. Extensive experiments on l-ε-join of motion capture sequences are conducted. The results confirm the efficiency and effectiveness of our proposed algorithm in processing l-ε-join of motion capture time series. © 2009 IEEE.