Efficient three-dimensional motion pattern retrieval in large motion capture databases

This dissertation studies 3D motion capture data based on the analysis of geometric structures of data matrices. Effective retrieval of motion patterns from motion streams requires efficient motion indexing, classification, recognition and segmentation techniques. Although 3D motion data has been increasingly generated in many applications, no efficient approaches have been available to segment data streams, to classify and index isolated multi-attribute data. This study addresses these issues and proposes generic approaches applicable to any data sequences of multiple attributes.;Motion data for dozens of variables has accordingly dozens of attributes, and might have different lengths for any two motions. A motion data matrix can be considered to be a sequence of high dimensional points in a high dimensional space. Although the number of points can be different for any two motion data matrices, the geometric structures or data distributions would be similar if two motions are similar. Singular value decomposition (SVD) is explored to capture the geometric structures of motion data. It exposes different directions of data distributions and data variances along these directions, and these directions and variances can be utilized for our purposes.;To index multi-attribute motion data, different vectors are extracted before dimensionality reduction for feature vectors, and two interval-based indexing structures are proposed. The first indexing approach inserts the identifier of a motion into one leaf node, making it possible to search for any less similar motions, or for motions with any variations. The second approach narrows down similarity ranges determined by available motion data, and inserts the identifier of a motion into all possible leaf nodes with identifiers of similar motions. This multiple insertion approach reduces query time to several microseconds. At each tree level, only one component of the query vector needs to be checked for a query. Searching time is independent of the number of pattern motions indexed by the tree, making the index structure well scalable to large data repositories.;For segmenting and recognizing motion streams by similarity search, two similarity measures are defined. MAS, or Main Angular Similarity measure, considers the most dominating components from SVD, while kWAS considers multiple weighted dominating components. The similarity measures can be applied to stream segmentation with high recognition accuracy. Different motions having similar data distributions are further differentiated by data projections which can reflect the motion temporal orders.;When there are a large number of repetitions for each motion, classification can be utilized to classify unknown motions. Support vector machine (SVM) classifiers are explored for classification. Highly discriminative feature vectors are extracted by using SVD, and SVM classifiers with decision values and with probability estimates are used for isolated motions and for motion streams, respectively. A novel clustering technique has been proposed to significantly reduce the number of motion classes involved for each motion classification. For segmenting motion streams using classification, motion temporal coherence is coupled with SVM classifiers for better recognition performance.;Experiments with hand gestures and human body motions demonstrate the utility of the proposed indexing, similarity measure and classification approaches. Data can have a large number of attributes, different lengths, and local and global scaling as long as different attributes are correlated.