Video mining using unsupervised clustering of video content

• US 7,375,731 B2
• Filed: 11/01/2002
• Issued: 05/20/2008
• 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., Divakaran, Ajay
• Primary Examiner(s): Sajous; Wesner
• Application Number:
  US10/285,831
• Publication Number:
  US 20040085323A1
• Time in Patent Office: 2,027 Days
• Field of Search: 345/581, 345/440, 345/589, 345638-639, 345/475, 382/190, 382/232, 382/233, 382/254, 707/100, 707/3, 707/501.1, 715716-720, 348422-423, 348/412, 348/415, 348/425, 348/437, 348/438, 348/474, 348/500, 348512-515, 386/68, 706/12, 706/20, 706/45
• US Class Current: 345/581
• 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
• CPC Class Codes: G06V 20/47 Detecting features for summarising video content

Abstract

A method mines unknown content of a video by first selecting one or more low-level features of the video. For each selected feature, or combination of features, time series data is generated. The time series data is then self-correlated to identify similar segments of the video according to the low-level features. The similar segments are grouped into clusters to discover high-level patterns in the unknown content of video.

Claims

1. A method for mining content of a sequence of frames of a video, comprising:

selecting a low-level feature of the content of the sequence of frames of the video;

generating time-series data from the content of the sequence of frames of the video, the time series data comprising the selected low-level feature;

implicitly constructing windows for the time-series data, in which the windows are multi-resolution, a distance D between two windows of size w at points x_i and x_i in the time series data is measured as

$D_w<br><br>\left(x_i,x_j\right)=\underset{k=0}{\overset{w-1}{\sum <br><br>}}<br><br>{\left(x_{i+k}-x_{j+k}\right)}^2,$

and k is an index for the points x_i and x_j in the windows;

self-correlating the time-series data, using the multi-resolution windows, to determine similar segments of the sequence of frames of the video according to the low-level feature, and wherein all similar segments are found at a plurality of temporal resolutions; and

clustering the similar segments to discover high-level patterns in the content of the sequence of frames of the video.

2. The method of claim 1 wherein the content of the sequence of frames of the video is unknown.

3. The method of claim 1 wherein a production style of the sequence of frames of the video is unknown.

4. The method of claim 1 wherein the video includes video and audio data.

5. The method of claim 1 wherein the low-level feature is selected from a group consisting of motion activity, color, texture, audio, semantic descriptors, and combinations thereof.

6. The method of claim 1 further comprising:

thresholding the low-level feature.

7. The method of claim 1 further comprising:

smoothing the time-series data.

8. The method of claim 1 further comprising:

weighting the time-series data.

9. The method of claim 1 further comprising:

selecting a plurality of low-level features of the content of the sequence of frames of the video;

generating the time-series data from the content of the sequence of frames of the video for each of the selected low-level features;

self-correlating the time series data for each of the selected low-level features to determine similar segments of the video according to the plurality of low-level features; and

clustering the similar segments to discover the high-level patterns in the content of the video.

10. The method of claim 9 further comprising:

associating the plurality of sets of clusters to infer the high-level patterns.

11. The method of claim 1 further comprising:

self-correlating the time-series data in a point cross-distance matrix to measure the point cross-distances.

12. The method of claim 11 wherein the point cross-distances are represented by substantially diagonal lines in the point cross-distance matrix.

13. The method of claim 1 further comprising:

time warping the time-series data to find the similar segments.

14. The method of claim 13 wherein the time warping is performed by dynamic programming.

15. The method of claim 1 further comprising:

merging the similar segments using a Hough transform on the time-series data.

16. The method of claim 1 further comprising:

labeling the clusters.

17. The method of claim 16 further comprising:

correlating the labels in time.

18. The method of claim 17 wherein the time correlation is simultaneous.

19. The method of claim 17 wherein the time correlation is time shifted.

20. The method of claim 17 further comprising:

generating conditions and results of occurrences of the labels to discover the high-level patterns.

21. The method of claim 1 further comprising:

summarizing the sequence of frames of the video according to the high-level patterns.

22. The method of claim 1 wherein the self-correlating further comprises:

measuring point cross-distances in the time series-data.

23. The method of claim 1 wherein the self-correlating further comprises:

forming a cross-product of the time-series data.

24. The method of claim 1 wherein the time-series data is a color histogram of consecutive frames in the video, and the self-correlating further comprises:

intersecting the color histogram with itself.

25. The method of claim 1 wherein the time-series data is a function of the low-level feature and the frames of the video.

26. The method of claim 1 wherein the time-series data is multi-dimensional.