2009 IEEE International Conference on Robotics and Automation
Kobe International Conference Center
Kobe, Japan, May 12-17, 2009

Detecting Repeated Motion Patterns
via Dynamic Programming using Motion Density
Koichi Ogawara and Yasufumi Tanabe and Ryo Kurazume and Tsutomu Hasegawa
Abstract— In this paper, we propose a method that detects
repeated motion patterns in a long motion sequence efficiently.
Repeated motion patterns are the structured information thatcan be obtained without knowledge of the context of motions.
They can be used as a seed to find causal relationships between
motions or to obtain contextual information of human activity,
which is useful for intelligent systems that support humanactivity in everyday environment.
The major contribution of the proposed method is two-fold:(1) motion density is proposed as a repeatability measure and(2) the problem of finding consecutive time frames with large
motion density is formulated as a combinatorial optimization
problem which is solved via Dynamic Programming (DP) in
polynomial time O(N log N ) where N is the total amountof data. The proposed method was evaluated by detecting
repeated interactions between objects in everyday manipulation
tasks and outperformed the previous method in terms of both
detectability and computational time.

I. INTRODUCTION
Supporting daily life is one of the upcoming key applications of robotics technology and the capability to understandhuman activity is essential for this purpose. One of the common approaches to understand human activity is to design
a set of necessary and sufficient task-dependent recognizers
that detect significant actions as well as capture the necessary
parameters to describe the action [1], [2], [3]. However, thevariety of human activity in everyday environment is very
diverse as opposed to those in a well-designed environment
such as a factory, it is not practical to prepare recognizers tocover all of them.
For this reason, a desirable system should have a mechanism to learn new knowledge, new recognizers, from observation incrementally. As a bootstrap process to realize thismechanism, we are trying to detect repeated motion patterns
as a structured information in observation data that can beextracted without knowledge of the context of a task. The
basic idea is if a particular motion pattern appears manytimes in observation data, this pattern must be meaningful
to the user or to the task. When a system detects repeatedmotion patterns while observing daily activity for a long
period of time, e.g. several days, these patterns can beconsidered as meaningful actions and the causal relationships
between these actions can be used to predict the next actionof a user or to learn contextual information of human activity,
K. Ogawara is with Faculty of Engineering, Kyushu University, Fukuoka,
JAPAN ogawara@is.kyushu-u.ac.jp
Y. Tanabe is with Department of Electrical Engineering and Computer
Science, Kyushu University, Fukuoka, JAPANR. Kurazume and T. Hasegawa are with Faculty of Information Scienceand Electrical Engineering, Kyushu University, Fukuoka, JAPAN

978-1-4244-2789-5/09/$25.00 ©2009 IEEE

which is useful for intelligent systems that support humanactivity in everyday environment.
In this paper, we propose a method that detects previously
unknown repeated motion patterns in a long motion sequence
efficiently. The contribution of the proposed method is twofold. The first contribution is to introduce a notion of
motion density as a repeatability measure which evaluates thenumber of similar motions for each time frame. The second
contribution is that the problem of finding variable-length repeated motion patterns, that is consecutive time frames withlarge motion density, is formulated as a combinatorial optimization problem which is solved via Dynamic Programming(DP) in polynomial time O(N log N ) in average where N is
the total amount of data, while most of the previous methods
assume known-length patterns [4] or take O(N 2 ) time [5].
Among few exceptions is [6] which takes O(N 1+1/α ) time,
however it solves the problem in three-steps. On the other
hand, the proposed method finds repeated motion patterns
under a single energy minimization framework.
The remainder of this paper is organized as follows. In
Section II, we give an overview of the related research.
Then we introduce a notion of motion density in Section
III and extend the framework to cover interrelated multiple
time series data for our particular application in Section IV.
The details of the proposed method is explained in Section
V. The experimental results are presented in Section VI and
we conclude the paper in Section VII.
II. R ELATED W ORK
TrajectoryT
Fig. 1.

Repeated Patterns in a Time Series Data

While there has been a large body of work regarding
efficiently locating previously known patterns in time series
data [7], [8], [9], we focus on locating previously unknown
repeated patterns in this study as shown in Fig. 1. Finding
unknown repeated patterns, or motifs, has been a well-known
task in the bioinformatics community [10], in the data mining
community [4], [11] and in the motion analysis community[12], [5], [6].
Finding repeated patterns has been studied extensively inanalysis of nucleic acid sequences decades ago where thetime series data is a sequence of discrete symbols from1743

a set of 4 bases. Staden proposed a method that detects
the most repeated known-length pattern by a voting scheme
considering all the possible combination of patterns [10]. The
computational time is linearly proportional to N , where N
is the total amount of data.
The continuous counterpart has received much attention in
the data mining community as well as in the motion analysis
community. In the early stages, Liu et al. proposed a methodin that a continuous time series data is first discretized into
a sequence of symbols and the most repeated known-length
pattern is found probabilistically by a voting scheme usinga hash function in O(N ) time [4].
To deal with unknown-length repeated patterns, several
approaches based on Dynamic Programming (DP) have been
proposed. Ogawara et al. proposed a method that detects a setof motion patterns appeared in all M observation data in thesame order using multi-dimensional DP matching in O(N M )time [13]. Uchida et al. proposed a method that detects pairwise similar motion patterns from a single observation datausing logical DP matching in O(N 2 ) time [5].
To reduce computational time, Yankov et al. proposed amethod that extends [4] to deal with uniform scaling of
the known-length repeated motion patterns in O(N 1+1/a )time [11]. To find totally unknown-length repeated motion
patterns, Meng et al. proposed a three-steps method inO(N 1+1/a ) time in that it finds k-nearest-neighbor data
points using Locality Sensitive Hashing (LSH), then it connects these detected data points along time axis to findrepeated motion candidates and finally it performs spectralclustering to find the repeated motion patterns [6]. However,
the output from each step cannot be guaranteed to be theglobal optimum.
In contrast to Meng’s method, the proposed method finds
repeated motion patterns from a continuous time series
data under a single energy minimization framework inO(N log N ) time, thus it finds the global optimum in termsof the given energy function. Another advantage is that it can
detect consistent repeated motion patterns among interrelated
multiple continuous time series data which is not possible
with other methods.
Ogawara et al. previously proposed a method that finds
consistent repeated motion patterns among interrelated multiple continuous time series data in O(N log N ) time [14].
However, the problem is formulated as a combinatorial
optimization problem with two correlated parameters. These
two parameters are estimated alternately but independently,
thus the global optimum is not guaranteed to be obtained.
In the proposed method, the problem is re-formulated as a
combinatorial optimization problem with a single parameterand the global optimum is analytically obtained via Dynamic
Programming (DP).
Finding repeated patterns can be seen as a data compression problem where repeated patterns would be codedwith a shorter word. Zhao et al. proposed a method thatcompresses a vector quantized motion data using Huffman
coding which minimizes both the amount of information tocode the entire data and the size of the dictionary under

Minimum Description Length (MDL) principle [12]. It works
well on ballet motion, however the result is severely affectedby non-repeated patterns which dominates a time series datain general.
III. M OTION D ENSITY
Fig. 1 shows an example of the problem of interest. Givena long time series data of arbitrary dimensions, we wantto find unknown repeated patterns efficiently where minor
variation of shape and length is allowed.
Here, we introduce a notion of motion density as arepeatability measure which evaluates the density of similar
motions at around each time frame. With that, the problem
is formulated as to find consecutive time frames with large
motion density under an energy minimization framework.
Motion density md(x, t) represents the density of similar
motion segments in the neighborhood of data point ox,t attime t in time series data x. In this study, motion density
is defined as the number of motion segments found withinradius R around ox,t excluding the one to which ox,t belongs:
md(x, t) = #{msj |ox,t ∈/ msj , msj ⊂ ∪ox,k , |ox,k −ox,t | < R}
(1)
where motion segment msj is a continuous sequence of ox,kwithout a gap. If motion density is high, that means there
are many repeated motion patterns similar to the one aroundox,t .
Moon Segmentsin the neighborhood

Moon Segmentof InterestR

ox ,t2ox ,t1(1) Moon Density is high(2) Moon Density is low

ox ,t3ox ,t3(3) Moon Density is high(4) Moon Density is low

Pose Space

Shape Space

Fig. 2.

Motion Density

Fig. 2 shows examples of motion density. The curve in Fig.
2 (1) to (3) represent the 2D slice of a time series data ofarbitrary dimensions in Pose Space. Here, we assume that thetime series data represents a trajectory, e.g. 6 D.O.F. positionof a rigid object or joint angles of a human body, and Pose
Space is the space where the time series data is directly
projected without conversion.

1744

1. Building Kd-Tree

1. Normalizaon
1Tt

Dim. = 6 -1
Mo on Density in Pose Space
2. Capturing Local Shape Informaon

2. Finding data points in the neighborhood

DCT_WIDTH

1o x ,t
T

t-1

-1

R
t

K-1 K K+1

Dim. = DCT_WIDTH x 6
Cosine table
3. Applying DCT of Gaussian
Dimensionality Reduconin i-th parameter space
Dim. = DCT_BANK x 6

X

DCT_BANK

3. Embedded segmentaon algorithm in Kd-tree search
t-1 t
Table

4. Applying PCA
Dimensionality Reduconin the enre parameter spaceMoon Segment
Link List

Start
End

…K-1 K K+1 …
Start
End

Tbl[i].Visit_count.index
.p_MS

Start
End

PCA_BANK

Fig. 4.

Dim. = PCA_BANK

Kd-tree with Embedded Segmentation Algorithm

Mo on Density in Shape Space

Fig. 3.

Conversion from Pose Space to Shape SpaceIn the case of Fig. 2 (1), there are several similar motion
segments in the neighborhood of ox,t1 , 2 in this case, thus the
motion density mdp (x, t1 ) is relatively high, On the other
hand, in the case of Fig. 2 (2), there is no other motion
segment in the neighborhood of ox,t2 , thus the motion density
mdp (x, t2 ) is low.
In the case of Fig. 2 (3), there are several motion segmentsin the neighborhood of ox,t3 , thus mdp (x, t3 ) is high.
However, as shown in the figure, the shape of these motion
segments are completely different, thus these should not be
considered as repeated motion patterns.
To take the similarity of shape into consideration, anotherspace named Shape Space is defined. In this space, each data
point at time t encodes the local shape of the original timeseries data at around ox,t so that data points similar in shape
locally are projected to be in the neighborhood.
Motion density is also computed in Shape Space and bothof the motion densities are used as a repeatability measure
at time t. Fig. 2 (4) shows the converted trajectory of Fig. 2(3) into Shape Space and motion density mds (x, t3 ) is low
in this space.
A. Definition of Shape SpaceIn Shape Space, the metric between two data points iscomputed as the similarity in shape between two motion
segments around the data points. The conversion from Pose
Space to Shape Space is made of 4 steps as shown in Fig.
3.
Here, we assume that the original time series data in Pose
Space represents a trajectory of an object and each data point
is made of 6 parameters, 3 for translation and 3 for rotation(quaternion). However, the following conversion generalizes
to any parameterization including joint angles.

1) Normalization
Because the range of values is totally different among
the parameters, translation v.s. rotation, the values arenormalized in each parameter space independently.
Motion density in Pose Space is computed from thenormalized data points.
2) Capturing Shape Information
To capture the local shape information, DCT WIDTH
normalized data points around time t are gathered toform a shape vector in i-th parameter space. The number of dimension is increased from 6 to DCT WIDTH× 6.
3) Applying DCT of Gaussian
Discrete Cosine Transform (DCT) of Gaussian is applied to the shape vectors for dimensionality reductionin i-th parameter space. The number of dimension is
reduced to DCT BANK × 6.
4) Applying PCA
Principal Component Analysis (PCA) is applied tothe set of reduced shape vectors for dimensionality
reduction in the entire parameter space. The numberof dimension is further reduced to PCA BANK.
We can directly apply PCA to a shape vector without applying DCT of Gaussian. The reason why DCT of Gaussian
is applied intermediately is that PCA in high dimensional
space takes time. PCA after DCT of Gaussian dramaticallyreduces the computational time, while the quality of dimensionality reduction is comparable with PCA only approach.
From the viewpoint of computational complexity, the time
for applying PCA is considered to be a constant, but it makes
the algorithm considerably faster in practice.
B. Finding Motion Segments using Kd-tree
To count the number of motion segments within the hypersphere of radius R around a data point, Kd-tree with anembedded segmentation algorithm is used. The algorithm
works as shown in Fig. 4.

1745

1) Building Kd-tree
Two Kd-trees are built separately for the set of data
points both in Pose Space and in Shape Space. The data
points are recursively subdivided by a hyper-plane perpendicular to the axis along which the variance of theremaining data points becomes maximum. The computational time for building Kd-tree is O(N log N ).
2) Finding Data Points in the Neighborhood
For each data point at time t, all the data points within
the hyper-sphere of radius R are searched. The averagecomputational time is close to O(log N ), however it
becomes O(N ) in the worst case if all the data points
lie within the hyper-sphere.
3) Embedded Segmentation Algorithm in Kd-tree
SearchAfter finding all the data points within the hypersphere, these points have to be grouped into segments.
However, if segmentation is performed separately after
Kd-tree search finishes, additional time is required tosort the data points whose computational time is ether
O(N ) or O(K log K) where K is the number of thedata points found within the hyper-sphere.
Thus, a segmentation algorithm is embedded in the
search algorithm of Kd-tree without increasing computational complexity. As shown in Fig. 4, it maintains
a table of length N each of which holds 3 parameters:(1) visit count is used to check if it is already visitedof not, (2) index holds the table-index of another data
point that belongs to the same motion segment and(3) p M S is a pointer to the corresponding Motion
Segment structure. It also maintains the linked-list of
Motion Segment structure each of which holds the startand end time of the motion segment.
The flow of the algorithm is presented in TABLE I.
This algorithm is called with the time parameter twhenever a new data point within radius R is foundduring a single Kd-tree search. If the mean numberof data points around a data point is K̄, then thisis called K̄ × N times in total. For each call, theset of Motion Segment structure is updated using oneof the following functions: mergeMotionSegment() isto merge two consecutive segments together, enlargeMotionSegment() extends the range of the segment toinclude time t and addNewMotionSegment() creates a
new segment at time t. visit count is incremented oncein each Kd-tree search, that is N times.
When all the data points within the hyper sphere arevisited, the data points are already grouped into motion
segments and motion density is calculated by justcounting the number of segments.
C. Consistency between Motion Densities
Since repeated motion patterns must appear in both motion
densities, a motion segment that is not shared by both ofthe motion densities is removed. Using remaining motion
segments, motion density is calculated as eq.(1).

TABLE IE MBEDDED S EGMENTATION A LGORITHM
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Input: t;idxl = idxr = t;
if tbl[t-1].visit count == visit countidxl = t-1;
do (idxl = tbl[idxl].index)
while (idxl != tbl[idxl].index);
tbl[t-1].index = idxl;
end;
if tbl[t+1].visit count == visit countidxr = t+1;
do (idxr = tbl[idxr].index)
while (idxr != tbl[idxr].index);
tbl[t+1].index = idxr;
end;
if idxl != t && idxr != t
mergeMotionSegment(tbl[idxl].p MS, tbl[idxr].p MS);tbl[t].idx = idxl;
else if idxl != t
enlargeMotionSegment(tbl[idxl].p MS, t);
tbl[t].idx = idxl;
else if idxr != t
enlargeMotionSegment(tbl[idxr].p MS, t);
tbl[t].idx = idxr;
else
addNewMotionSegment(t);tbl[t].idx = t;end;
tbl[t].visit count = visit count;

IV. E XTENSION TO I NTERRELATED M ULTIPLE
C ONTINUOUS T IME S ERIES DATA

T
Trajectory

Object 1

T

Object 2

T

ConflictObject 3

Data Label

Fig. 5.

T

N N N A A N N C C N A A N A C C N N N N

Finding Consistent Repeated Motion Patterns

So far, we implicitly assume a single time series data.
Here, we extend our framework to cover interrelated multiple
continuous time series data. Fig. 5 shows an example of the
problem. The input is multiple trajectories of objects, 3 inthis case, and the algorithm is required to output the motion
patterns that appear many times in the input trajectories.
If the multiple trajectories are independent of each other,
then the algorithm has only to be applied to each trajectory
separately. However, if the trajectories are interrelated witheach other, the algorithm has to find the consistent repeatedmotion patterns among the trajectories.
This is the case when repeated interactions between objects are of interest. In Fig. 5, there are 3 possible interactions

1746

between: (A) Obj.1 and Obj.2, (B) Obj.1 and Obj.3, (C)Obj.2 and Obj.3. If two of them are detected at the sametime, this means a conflicting situation.
In the proposed method, we assume that there occurs asingle significant interaction at most at a certain moment.
This assumption is not necessarily true when there are 4 ormore objects, or a motion is composed of more than two
objects, but it is satisfied in most cases.
Then, the problem is formulated as a combinatorial optimization problem in that a data label x ∈ {A, B, C, N on}
is assigned to each time frame as shown in the bottom of
Fig. 5. ′′ A′′ , “B ′′ , “C ′′ mean there occurs a repeated motion
between the respective object pairs, while ′′ N on′′ means
there is non-repeated motion at that time.
Please note that this formulation is a natural extension
from the single time series data case in that we have only
two labels: repeated and not-repeated.
V. A LGORITHM D ETAILSEm (T S, X) =X

em (T S, xt , t)tem (T S, xt , t)

mdp (xt , t)))
< mdp (xt , t) >mds (xt , t)
− log(1 − exp(−))< mds (xt , t) >= − log(1 − exp(−

where mdp (xt , t) and mds (xt , t) are the motion densities
defined in Pose Space and Shape Space. < mdp (xt , t) >and < mds (xt , t) > are the mean values of mdp (xt , t) andmds (xt , t) respectively.
Es (X) is a term regarding the prior distribution of X.
It penalizes the difference between consecutive data labels
which leads to reject short motion segments. It is decomposed intoX
Es (X) =es (xt , xt+1 )tA. Problem Formulation
The problem is formulated as a combinatorial optimization problem regarding data labels X = {xt |xt ∈{A, B, · · · , N on}, 1 ≤ t ≤ N } as shown in Fig. 5. There
are two types of data labels: ′′ A′′ , “B ′′ , · · · mean the current
data point is a repeated motion belonging to the time series
data of that label, while ′′ N on′′ means the current data point
is non-repeated motion.
In the case of finding consistent interactions between
objects, there are M = m(m − 1)/2 data labels where mis the number of objects in the scene and data point oi,trepresents relative position between i-th object pairs at timet.
Given multiple time series data T S = {oi,t |1 ≤ i ≤M, 1 ≤ t ≤ N }, we find X that minimizes an energyfunction defined ase(xt , xt+1 ) = T (xt 6= xt+1 ) · K,
where K is a constant and T (s)true, otherwise T (s) = 0.

=

1 iff s=B. Energy Minimization via Dynamic Programminges ( xt , xt +1 )ev (TS , xt ) + em (TS , xt )Object 1

Object 2

Object 1

Object 3

䞉䞉䞉

䞉䞉䞉

A

䞉䞉䞉

A

B

䞉䞉䞉

Find the shortest PATH
Non 䞉䞉䞉

Data Label䞉䞉䞉N N N A A N N A A B N N N A C C N N N N
N means “Non”

E(T S, X) = Ev (T S, X) + Em (T S, X) + Es (X)Ev (T S, X) is a term regarding velocityi,t , that is thevelocity of the relative position between i-th object pairs attime t, and it penalizes stationary or non-interacted objects.
In our particular application, objects stay still in most of
the period in a time series data, thus we have to avoid thecase where huge number of motionless regions are detected
as repeated motion patterns. Otherwise, this term is notnecessary. It is decomposed intoX
Ev (T S, X) =ev (T S, xt , t)tev (T S, xt , t) = − log(1 − exp (−Fig. 6.

(2)

velocityxt ,t))< velocityxt ,t >where < velocityxt ,t > is the mean value of velocityxt ,t .
Em (T S, X) is a term regarding motion density and it
penalizes data points with small number of similar motion
segments in the neighborhood. It is decomposed into

Estimation of Data Labels via Dynamic Programming

All the terms in eq.(2) satisfies first order Markov property,
the energy minimization problem can be analytically solved
by Dynamic Programming as shown in Fig. 6.
The trouble is we know nothing about the energy terms Ev
and Em regarding data label ′′ N on′′ . In general, the lower
these energy terms are, the fewer the number of detected
repeated motion patterns be. However, it is not clear how
these terms are determined, since the appropriate value iscontext dependent. So we decided to adaptively change thevalues of these terms so as to output the desired number ofmotion patterns which is provided by a user.
First, the range of the value ev (T S, xt , t) + em (T S, xt , t)is calculated by checking all the combination of t and xt .
Then, assuming eN on,t = ev (T S, N on, t) + em (T S, N on, t)
is a fixed value independent of t, the optimal eN on,t within
the range is obtained in binary-search fashion so as to best
outputs the desired number of repeated motion patterns via
Dynamic Programming.

1747

C. Separation of Motion Patterns on a Same Time Series
Data

ms2

ms2

A A A A A A

A A A A A A

A A A A A
radius R

ms1

ms3

A
A
A
A
A

Obj.2

radius R

A A A A A

ms1

ms3

Obj.1

A
A
A
A
A

Fig. 8.

A1

Nearest data point within radius R(1) Overlap Ra!o from ms1 to ms2

Fig. 7.

Obj.4

Obj.3

So far, different motion patterns on a same time series data
are labelled as the same. To separate these motion patterns,
the following algorithm is applied.

Objects used in the Experiment

A2

B1

C1

C2

C3

(2) Overlap Ra!o from ms2 to ms1

Separation of motion patterns using mutual overlap ratio

Suppose one of the trajectory is labelled as in Fig. 7 and3 motion segments are detected via DP. Then, for each pairof motion segments msi and msj , the overlap ratio ORi,j iscalculated as the number of nearest data points within radius
R in msj divided by the length of msi . If mutual overlap
ratio, both ORi,j and ORj,i , is greater than 0.5, two motion
segments are grouped as the same motion pattern.
In the case of Fig. 7, OR1,2 = 45 and OR2,1 = 64 , thus
ms1 and ms2 are grouped as the same.
The nearest data point on each motion segment withinradius R is computed during Kd-tree search, thus there is no
increase in computational complexity.
D. Computational Complexity
The required computational time is O(N log N ) for building Kd-tree, O(N log N ) in average for motion density estimation and O(M 2 N ) for DP analysis. By assuming M <<N , the total average computational time is O(N log N ).
VI. E XPERIMENTAL R ESULT
A. Experimental Setup
4 different manipulation tasks were performed by a subject
and were used to evaluate the proposed method. There
were 4 objects in the scene and an electromagnetic motion
tracking system (Polhemus FASTRAK) was used to observe
the trajectory of each object at 30Hz during demonstrations.
Fig. 8 shows the objects used in this experiment.
As shown in Fig. 9, 6 actions are defined. A subject
was instructed to perform a task following a scenario madeby combining 6 actions. To emulate the change in theenvironment during long-term observation, the subject was
instructed to relocate the objects on the table several times
so that the relative relationship between stationary objects
was changed.

A1: Pour from Obj.1 to Obj.2 from the le
A2䠖 Pour from Obj.1 to Obj.2 from the right
B1: Pour from Obj.3 to Obj.2
C1: Mix inside Obj.2 with Obj.4
C2: Spoon up from Obj.1 with Obj.4
C3: Put into Obj.2 with Obj.4
Fig. 9.

6 Repeated Actions in the Scenario

is 0.4 and K in Es term is 15. These values were determined
empirically.
The proposed method was compared with the method
proposed in [14]. There are two noticeable differences between them. The first difference is that the desired number ofmotion patterns is provided by a user in the proposed method,while it is automatically selected in the previous method,
though it is highly sensitive to the parameters. The second
difference is that motion patterns in a same time series data
can be discriminated in the proposed method, while it is notpossible in the previous method.
TableII, III, IV, V shows the results of detecting repeatedmotion patterns using two different methods. All the computations were done on Xeon 3.0GHz PC.
As an error measure, Precision and Recall are calculated
from True Positive (TP), False Positive (FP) and False
Negative (FN) as
Precision =TP
TP, Recall =.
TP + FPTP + FN

The proposed method outperformed the previous method
in all the scores. However, there is a noticeable failure in
TABLE V where the number of detected action C3 is zero.
This is because, in this scenario, C3 always follows just afterC2 and these two consecutive actions were detected as asingle action which were labelled as C2.

B. Evaluation
In all the experiments, we use 33 for DCT WIDTH, 4
for DCT BANK and 6 for PCA BANK so as to equalize
the dimensions of Pose Space and Shape Space. Both of theradius of the hyper-sphere in Pose Space and in Shape Space

VII. C ONCLUSION
This paper presents a method that detects repeated motion
patterns from a continuous time series data under a single
energy minimization framework in O(N log N ) time where

1748

TABLE II
E VALUATION OF DATA S ET 1 [896 FRAMES ]ActionPresented Number
Proposed Method
Previous Method [14]

A1
4
4
4

TP
4
4

FN
0
0

FP
0
0

Precision
1.00
1.00

Recall1.00
1.00

Time[msec]
1164
15873

TABLE IIIE VALUATION OF DATA S ET 2 [1428 FRAMES ]ActionPresented Number
Proposed Method
Previous Method [14]

A1
3
3

A2
3
3

TP
6
5

5

FN
0
1

FP
0
2

Precision
1.00
0.71

Recall1.00
0.83

Time[msec]
2401
80624

TABLE IVE VALUATION OF DATA S ET 3 [3737 FRAMES ]ActionPresented Number
Proposed Method
Previous Method [14]

A1
6
5
0

B1
7
7
6

C1
6
6
2

TP
18
8

FN
1
11

FP
0
0

Precision
1.00
1.00

Recall0.95
0.42

Time[msec]
14800
1769685

TABLE VE VALUATION OF DATA S ET 4 [5177 FRAMES ]ActionPresented Number
Proposed Method
Previous Method [14]

B1
7
7
5

C1
5
3

C2
10
6
5

C3
10
0

TP
16
10

N is the total amount of data. The algorithm outputs top
L repeated motion patterns, where the desired number L isprovided by a user.
The problem is formulated as a combinatorial optimization
problem in that the data label with large motion density
is assigned to each time frame, which then be solved via
Dynamic Programming (DP) analytically.
The proposed method was evaluated by detecting repeatedinteractions between objects in everyday manipulation tasks
and outperformed the previous method[14] in terms of both
detectability and computational time.
ACKNOWLEDGMENTS
This study was supported by Program for Improvement ofResearch Environment for Young Researchers from Special
Coordination Funds for Promoting Science and Technology(SCF) commissioned by the Ministry of Education, Culture,
Sports, Science and Technology (MEXT) of Japan.
R EFERENCES[1] K. Ikeuchi and T. Suehiro, “Toward an assembly plan from observation
part i: Task recognition with polyhedral objects,” IEEE Trans. Robotics
and Automation, vol. 10, no. 3, pp. 368–384, 1994.
[2] Y. Kuniyoshi, M. Inaba, and H. Inoue, “Learning by watching,” IEEE
Trans. Robotics and Automation, vol. 10, no. 6, pp. 799–822, 1994.
[3] K. Bernardin, K. Ogawara, K. Ikeuchi, and R. Dillmann, “A sensor
fusion approach for recognizing continuous human grasping sequencesusing hidden markov models,” IEEE Transactions on Robotics, vol. 21,
no. 1, pp. 47–57, 2005.

FN
16
22

FP
5
4

Precision
0.76
0.71

Recall0.50
0.31

Time[msec]
26703
8388985[4] J. Lin, E. Keogh, S. Lonardi, and P. Patel, “Finding motifs in timeseries,” in Proc. of the 2nd Workshop on Temporal Data Mining, 2002,
pp. 53–68.
[5] S. Uchida, A. Mori, R. Kurazume, R. Taniguchi, and T. Hasegawa,“Logical dp matching for detecting similar subsequence,” in Proc. of
Asian Conference of Computer Vision, 2007.
[6] J. Meng, J. Yuan, M. Hans, and Y. Wu, “Mining motifs from humanmotion,” in Proc. of EUROGRAPHICS’08, 2008.
[7] R. Agrawal, C. Faloutsos, and A. Swami, “Efficient similarity searchin sequence databases,” in Proc. of 4th International Conference onFoundations of Data Organization and Algorithms, 1993, pp. 69–84.
[8] C.-S. Perng, H. Wang, S. R. Zhang, and D. S. Parker, “Landmarks:
A new model for similarity-based pattern querying in time series
databases,” in 16th International Conference on Data Engineering(ICDE’00), 2000, pp. 33–42.
[9] T. Mori, Y. Nejigane, M. Shimosaka, Y. Segawa, T. Harada, and
T. Sato, “Online recognition and segmentation for time-series motion
with hmm and conceptual relation of actions,” in Int. conf. onIntelligent Robots and Systems, 2005, pp. 2569–2574.
[10] R. Staden, “Methods for discovering novel motifs in nucleic acidsequences,” Computer Applications in the Biosciences, vol. 5, no. 5,
pp. 293–298, 1989.
[11] D. Yankov, E. Keogh, J. Medina, B. Chiu, and V. Zordan, “Detecting
time series motifs under uniform scaling,” in Proc. of the 13th ACM
KDD Intl. Conf. on Knowledge Discovery and Data Mining, 2007, pp.
844–853.
[12] T. Zhao, T. Wang, and H. Shum, “Learning a highly structured motion
model for 3d human tracking,” in Proc. of Asian Conference ofComputer Vision, 2002.
[13] K. Ogawara, J. Takamatsu, H. Kimura, and K. Ikeuchi, “Extractionof essential interactinos through multiple observations of humandemonstrations,” IEEE Transactions on Industrial Electronics, vol. 50,
no. 4, pp. 667–675, 2003.
[14] K. Ogawara, Y. Tanabe, R. Kurazume, and T. Hasegawa, “Learning
meaningful interactions from repetitious motion patterns,” in IEEE/RSJ
2008 Int. Conf. on Intelligent Robots and Systems, 2008, pp. 3350–
3355.

1749