Pattern discovery in multi-dimensional time series using multi-resolution matching

• US 7,103,222 B2
• Filed: 11/01/2002
• Issued: 09/05/2006
• Est. Priority Date: 11/01/2002
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Peker, Kadir A.
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): Akhavannik, Hadi
• Application Number:
  US10/285,928
• Publication Number:
  US 20040088722A1
• Time in Patent Office: 1,404 Days
• Field of Search: 382/181
• US Class Current: 382/181
• CPC Class Codes: G06F 16/739 in form of a video summary, e.g. the video summary being a video sequence, a composite still image or having synthesized frames
• CPC Class Codes: G06F 16/7834 using audio features
• CPC Class Codes: G06F 16/785 using colour or luminescence
• CPC Class Codes: G06F 16/7857 using texture G06F16/7837 takes precedence
• CPC Class Codes: G06F 16/786 using motion, e.g. object motion or camera motion

Abstract

A method discovers patterns in unknown multi-dimensional data. A time-series of the multi-dimensional data is generated and a point cross-distance matrix is constructed by self-correlating the time-series. All minimum cost paths in the point cross-distance matrix are located at multiple time resolutions. The minimum cost paths are then related to temporal sub-sequences in the multi-dimensional data to discover high-level patterns in the unknown multi-dimensional data.

Claims

1. A computerized method for discovering patterns in unknown multi-dimensional data, comprising:

generating a time series of the unknown multi-dimensional data;

constructing a point cross-distance matrix by self-correlating the time series;

locating all minimum cost paths in the point cross-distance matrix at a plurality of time resolutions; and

relating the minimum cost paths to sub-sequences in the times series to discover high-level patterns in the unknown multi-dimensional data.

2. The method of claim 1 wherein the time series data is generated from selected features of the multi-dimensional data.

3. The method of claim 1 wherein the time series is thresholded.

4. The method of claim 1 wherein the point-cross distance matrix is filtered.

5. The method of claim 1 wherein the unknown multi-dimensional data are unknown content of a video.

6. The method of claim 1 wherein the unknown multi-dimension data is partitioned into clusters according to the high-level patterns.

7. The method of claim 1 wherein all of the minimum cost paths are located at multiple temporal resolutions using windows of size w.

8. The method of claim of claim 7 wherein a distance in the point cross-distance matrix for two windows of the size w is

$\begin{array}{c}{D}_w\end{array}$

( x i , x j ) = ∑

k = 0 w - 1 ⁢

( x i + k - x j + k ) 2 , and D 1 ⁡

( x i , x j ) = ( x i + k - x j + k ) 2 , and D w ⁡

( x i , x j ) = ∑

k = 0 w - 1 ⁢

D 1 ⁡

( x i + k , x j + k ) ,

where x_i and x_j are end points of the window.

9. The method of claim 8 wherein all of the minimum cost paths are located by searching the point cross-distance matrix for diagonal line segments of distances less than a predetermined threshold.

10. The method of claim 1 wherein all of the minimum cost paths are substantially parallel to a major diagonal of the point cross-distance matrix.

11. The method of claim 7 wherein the multiple temporal resolutions are obtained by sub-sampling the time series using multi-scaling.

12. The method of claim 11 wherein the scaling uses wavelets.

13. The method of claim 1 wherein dynamic time warping is applied to the time series to stretch and compress time in the time series.

14. The method of claim 1 further comprising:

applying dynamic programming to find optimum minimum cost paths in the point cross-distance matrix.

15. The method of claim 1 further comprising:

only processing an upper half of the point cross-distance matrix.

16. The method of claim 1 further comprising:

merging any minimum cost paths whose end points are within a predetermine distance of each other.

17. The method of claim 1 further comprising:

merging any minimum cost paths where one path is a superset of another path.

18. The method of claim 1 further comprising:

eliminating any minimum distance path shorter then a predetermined length.

19. The method of claim 1 wherein the multi-dimensional data is a speech signal.

20. The method of claim 1 wherein the multi-dimensional data is a linear polymer.

21. The method of claim 20 wherein the linear polymer is a protein.

22. The method of claim 16 wherein the merging uses a Hough transform.

23. The method of claim 1 further comprising:

applying an edge detector to the point cross-distance matrix to find all of the minimum cost paths.