Detecting repeated patterns using Partly Locality Sensitive Hashing
Koichi Ogawara, Yoshinori Tanabe, Ryo Kurazume, Tsutomu Hasegawa · 2010
Repeated patterns are useful clues to learn previously unknown events in an unsupervised way. This paper presents a novel method that detects relatively long variable-length unknown repeated patterns in a motion sequence efficiently. The major contribution of the paper is two-fold: (1) Partly Locality Sensitive Hashing (PLSH) [1] is employed to find repeated patterns efficiently and (2) the problem of finding consecutive time frames that have a large number of repeated patterns is formulated as a combinatorial optimization problem which is solved via Dynamic Programming (DP) in polynomial time O(N1+1/α) thanks to PLSH where N is the total amount of data. The proposed method was evaluated by detecting repeated interactions between objects in everyday manipulation tasks and outperformed previous methods in terms of accuracy or computational time.