- Jeff, Kai-Tai Tang itjeff[at]cityu.edu.hk
- Howard Leung howard[at]cityu.edu.hk
- Taku Komura itjeff[at]cityu.edu.hk
- Hubert Pak-Ho Shum itjeff[at]cityu.edu.hk

Repetitive patterns are segments that appear frequently in a given signal. The signal data can be either discrete or continuous. The former includes DNA sequence, text paragraphs, etc. while the latter includes speech, motion data, etc. For a discrete signal, repetitive patterns can be found by exact matching with string matching techniques or inexact matching with dynamic programming. Unlike discrete signal, a continuous signal contains an infinite number of states thus it is impractical to identify exactly matched states. Hence, a point cloud similarity approach is proposed to inexactly match for similar segment pairs and then approximate the optimal matching path by segmental dynamic time warping. In existing applications, a known template should already be present in order to query for the desired pattern in the input data. It motivates us to find repetitive patterns in an unsupervised way if there is no information about any known patterns.

Hence, we propose an inexact matching algorithm that finds repetitive motion without prior knowledge about the type and number of repetitive patterns. A self-similarity (point cloud) matrix is built and similar motion segment pairs are located by clustering nearby points. The mapping paths are located at the diagonals in the matrix that represents simialr motion segments that to be traced.

Our proposed algorithm which has two phrases. In the first phase, the longest similar motion segment pairs are to be searched. First, the self-similarity matrix of an input motion is constructed. A measurement for motion similarity that conforms to human perception has been applied. The repetitive patterns would be located as diagonal patterns. To enhance the searching, the start points of the repetitive patterns are estimated. The diagonal patterns are then traced by extending the pattern from a start point with a sliding window matching by Dynamic Time Wrapping (DTW) that checks whether the extension of pattern is valid. In the the second phase, in which the periodicity of the cyclic patterns is determined.

We have several contributions. First we have enhance the searching in the self-similarity matrix by automatically determine some candidate start points. Second, the pattern extension method approximates the optimal path of our wanted patterns. Also, the cyclic motions are classified and their periodicity (cycle number and length). The cycle lengths are estimated by tuning some parameters, followed by fine-tuning the cycle start/end points that outweighs the existing work in efficiency and accuracy.

Searching for longest repetitive patterns involves a few steps. Determine whether a posture pair is "similar" or "dissimilar" is important, and it will be discussed first. And then the point-cloud similarity approach is adapted and the self-similarity matrix is considered. To measure the similarity between two postures, it is important that the evaluation conforms to observer’s feeling. Hence, the feature that can model the perceived similarity between postures is adapted (Please refer to the Emulating human perception of motion similarity project page). The discovery of unknown repetitive patterns in a given motion can be solved by considering the self-similarity matrix of an input motion. The posture pairs are either marked as dark or white when they are determined as "similar" or "dissimilar" respectively. It is the approximation of the motion matching path and this consists of two steps. The start point of each repetitive pattern is determined automatically. It is an important because the start points defining from where the diagonal tracing algorithm starts.

The points that are qualified as start points should be satisfied into two criteria. First, it should have one free end (no neighbors) and one end connected with neighbor points. Second, the free end should is restricted to one side in order to ensure the pairs of previous postures are not similar but upcoming postures are similar. The pattern is growing by locating the start point first. And then a sliding window technique is used. The pattern tracing starts from the bottom-left corner of the point cloud. It is because the bottom-left is the nearer to the time zero (the starting of the whole motion).

Classification of cyclic and acyclic patterns is done by considering the property of patterns that are belonging to the same cyclic group. In the self-similarity matrix, the cyclic patterns are always exists in a family of diagonal lines and are aligning together in a right angled triangle shape as shown in Figure 11(a). It shows the diagonal lines that are extracted from a motion that a move was repeated 8 times. When we translate the 2D self-similarity matrix into a 1D sequence as shown Figure 11(b), it is observed that for a diagonal line its min(start1, start2) and max(end1, end2) are close to the other diagonal lines of the same cyclic motion. Next, we group the possible cyclic patterns by an adaptive k-NN.

After the classification of cyclic and acyclic patterns, the periodicity of the cyclic patterns are then determined. First, the start/end points are listed and sorted by ascending order, and we have a set of points {si}. And then, the difference between the si+1 and si are calculated. The difference values are summed up to a larger blocks of length B, such that is the minimum length of a cycle is expected to be, until all the difference values are considered. A range threshold (Th-ratio) is selected in order to restrict the variation of the difference values, such that the values out of the range [1/Th-ratio, Th-ratio] will be ignored. Finally, the medium length of those blocks are taken. The number of cycle is then calculated by Trunc( N/median(B)+o ), where N is the length of the whole cyclic motion. An offset o is added that to be tuned to tune up/down of the integer result. By tuning of several parameters, the system is trained and hence the estimator is built.

**Kai-Tai Tang**, Howard Leung, Taku Komura, and Hubert P.-H. Shum, "Finding repetitive patterns in 3D human motion captured data", In Proceedings of the 2nd international Conference on Ubiquitous information Management and Communication (ICUIMC'08), Suwon, Korea, Jan 31 - Feb 01, 2008.

Any suggestions or comments are welcome. Please send them to Jeff Tang

This website is maintained by Jeff Tang

Copyright @ 2008 3D Motion Capture Laboratory. All rights reserved.

Last update: 25 Nov, 2008 .