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

• US 20040088722A1
• Filed: 11/01/2002
• Published: 05/06/2004
• Est. Priority Date: 11/01/2002
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Peker, Kadir A.
• Granted Patent: US 7,103,222 B2
• Time in Patent Office: Days
• US Class Current: 725/19
• 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 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 multi-dimensional data 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

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.