System and method for measuring similarity between a set of known temporal media segments and a one or more temporal media streams

• US 6,675,174 B1
• Filed: 02/02/2000
• Issued: 01/06/2004
• Est. Priority Date: 02/02/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hampapur, Arun, Bolle, Rudolf Maarten
• Primary Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US09/496,604
• Time in Patent Office: 1,434 Days
• Field of Search: 707/100, 707/102, 707/104.1, 345/723
• US Class Current: 1/1
• CPC Class Codes: G06F 16/71 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/785 using colour or luminescence
• CPC Class Codes: G06F 16/7864 using domain-transform features, e.g. DCT or wavelet transform coefficients
• CPC Class Codes: G06V 20/40 in video content extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

This invention is a scaleable system to perform exact matching or similarity matching between a large store of reference temporal media sequences and a query target temporal media sequence. The system is not limited to finding exact matching media segments but also can find media segments that are similar. One kind of similarity between media segments is the similarity between a long commercial and a short commercial, where the short commercial is formed by sub-segments of the longer commercial. Another kind of similarity of two media segment is when they depict three-dimensional actions that are similar and imaged from similar viewpoints. Given a reference media segment, a multitude of features are computed in a consistent way from either predetermined or media content-dependent key intervals. These features are stored in segment index tables along with identifiers of the corresponding reference media segments. At search time, again, a multitude of features is computed from each key interval and now the features are used to search the segment index table for identifiers of stored media segments. If the key intervals are similar, many if not all, features computed from the key intervals point to the same reference media identifier.

Claims

1. A computer system for associating one or more features codes with one or more reference streams, the system comprising:

one or more central processing units and one or more memories; and

an index generation process that creates one or more of the feature codes by performing the steps of;

selecting a key interval from a reference stream;

transforming a media region of one or more selected key intervals of the media stream into one or more characteristic feature spaces;

quantizing the characteristic spaces into one or more domain regions;

deriving domain codes based on one or more domain regions selected from one or more characteristic spaces;

quantizing one or more feature values to determine the feature codes associated with each domain region; and

using the feature and domain codes to index into a memory index structure which associates the respective feature codes and domain codes with one or more parts of the reference streams from which they were derived.

2. A system, as in claim 1, where the memory structure is any one or more of the following:

a table, a structured index, a tree, and a connected graph.

3. A system, as in claim 1, where the media stream includes any one or more of the following:

a audio stream, a video stream, an information stream, a digital information stream, and a digital information stream that may contain viruses.

4. A system, as in claim 1, where the domain regions are quantizations of one or more characteristic spaces of the reference stream, including any one or more of the following:

one or more audio frequency ranges, one or more regions of an image, one or more frames of a video, one or more data packets, and one or more set intervals of a temporal signal.

5. A system, as in claim 1, where the feature values are derived based on computations from the reference streams, including any one or more of the following:

a hue, an amplitude, a frequency, a brightness, and an optical flow.

6. A system, as in claim 1, where the parts of the media stream include any one or more of the following:

the entire media stream and one or more of the selected key intervals.

7. A system, as in claim 6, where the key intervals are selected based on one or more of the following criteria:

non-overlapping regular intervals of the reference stream, overlapping regular intervals of the reference stream, a repeated pattern of overlapped intervals of the reference stream, a repeated pattern of non-overlapped intervals of the reference stream, and an analysis of the content of the reference streams.

8. A system, as in claim 1, where the order in which the steps of transforming a media region, deriving domain codes, and quantizing feature values are interchangeable.

9. A system, as in claim 1, the feature codes and domain codes are invariant to some set of transformations of the reference streams.

10. A system, as in claim 1, where the index generation process associates the feature codes with a reference media stream in the memory structure.

11. A system, as in claim 1, where a recognition of one or more target media streams is performed by a recognition process having the steps of:

transforming a target media region of one or more target selected key intervals of the target media stream into one or more target characteristic spaces;

quantizing the target characteristic spaces into one or more target domain regions;

deriving domain codes based on one or more domain regions selected from one or more characteristic spaces;

quantizing one or more target feature values to determine the target feature codes associated with each target domain region; and

using the target feature codes and domain codes in conjunction with the index structure to determine a similarity score between the target stream and each of the reference streams represented in the index structure.

12. A system, as in claim 11, where

the order in which steps of transforming the target media region, deriving domain codes, and quantizing feature values are interchangeable.

13. A system, as in claim 11, where the feature codes and domain codes are invariant to some set of transformation of the reference streams.

14. A system, as in claim 11, where a similarity score is determined as follows by performing the following steps:

using the target domain and feature codes to accumulate votes for each of the reference streams and selected key intervals with the reference streams;

matching a reference stream and a key interval within the reference stream based on the votes accumulated;

tracking the matches over successive target key intervals to determine temporal ordering of the matches; and

selecting one or more matching reference streams and one or more matching intervals within each of the selected matching reference streams and associating them with one or more of the selected key intervals of the target stream.

15. A method for creating a search index for one or more media streams, the method comprising the steps of:

transforming a reference media region of one or more reference selected key intervals of the media stream into one or more characteristic spaces;

quantizing the characteristic spaces into one or more domain regions, each of the domain regions having a reference domain identifier;

quantizing one or more feature values to determine one or more feature codes associated with each domain region; and

creating an index using the respective feature codes and domain identifiers.

16. A method, as in claim 15, where the media stream is a reference media stream and the respective feature code is a reference feature code and the respective domain identifier is a reference domain identifier.

17. A method, as in claim 16, further comprising the steps of:

using the index to associate the respective reference feature codes and reference domain identifiers with one or more parts of the reference media stream in one or more indexed memory structures.

18. A computer program product which performs the steps of:

transforming a reference media region of one or more reference selected key intervals of the media stream into one or more characteristic spaces;

quantizing the characteristic spaces into one or more domain regions, each of the domain regions having a reference domain identifier;

quantizing one or more feature values to determine one or more feature codes associated with each domain region; and

creating an index using the respective feature codes and the domain identifiers.

19. A system for creating a search index for one or more media streams, the system comprising:

means for transforming a reference media region of one or more reference selected key intervals of the media stream into one or more characteristic spaces;

means for quantizing the characteristic spaces into one or more domain regions, each of the domain regions having a reference domain identifier;

means for quantizing one or more feature values to determine one or more feature codes associated with each domain region; and

means for creating an index using the respective feature codes and the domain identifiers.

20. A method for creating a search index for one or more media streams, the method comprising the steps of:

transforming a reference media region of one or more reference selected key intervals of a target media stream into one or more characteristic spaces;

quantizing the characteristic spaces into one or more domain regions, each of the domain regions having a reference target domain identifier;

quantizing one or more feature values to determine one or more target feature codes associated with each domain region; and

creating an index using the respective target feature codes and target domain identifiers.

21. A method, as in claim 20, further comprising the steps of:

using the target feature codes and target domain identifiers to index into an indexed memory structure; and

tracking the number of successful hits on the indexed memory structure to determine that the target media stream has been indexed in the indexed memory structure.

22. A method, as in claim 21, where a successful hit occurs when the target feature code and target domain identifier create an index similar to one of the indexes in the indexed memory structure.

23. A method, as in claim 22, where a successful match occurs when there is a series of successful hits in a temporal order listed in the indexed memory structure.

24. A method, as in claim 23, where the temporal order is pre-specified.

25. A method, as in claim 24, where the pre-specification includes any one or more of the following:

a time order, a reverse time order, and one or more time intervals.

26. A method, as in claim 21, where a reference media stream indexed in the memory structure is one or more commercials and the target media stream is one or more television shows.