Multi-media content identification using multi-level content signature correlation and fast similarity search

• US 8,335,786 B2
• Filed: 05/27/2010
• Issued: 12/18/2012
• Est. Priority Date: 05/28/2009
• Status: Active Grant

• Current Assignee: Roku, Inc.
• Original Assignee: Zeitera LLC
• Inventors: Pereira, Jose Pio, Kulkarni, Sunil Suresh, Merchant, Shashank, Ramanathan, Prashant, Gajjar, Pradipkumar Dineshbhai
• Primary Examiner(s): Lewis, Cheryl
• Assistant Examiner(s): Waldron, Scott A
• Application Number:
  US12/788,796
• Publication Number:
  US 20100306193A1
• Time in Patent Office: 936 Days
• Field of Search: 707728-730, 707/747
• US Class Current: 707/728
• CPC Class Codes: G06F 16/7328 Query by example, e.g. a complete video frame or video sequence graphical querying G06F16/7335
• CPC Class Codes: G06F 16/783 using metadata automatically derived from the content
• CPC Class Codes: G06V 20/48 Matching video sequences

Abstract

A method is presented for large media data base query and media entry identification based on multi-level similarity search and reference-query entry correlation. Media content fingerprinting detects unique features and generates discriminative descriptors and signatures used to form preliminary reference data base. The preliminary reference data base is processed and a subset-set of it is selected to form a final reference data base. To identify a media query a fast similarity search is performed first on the reference database resulting in a preliminary set of likely matching videos. For each preliminary likely matching video a further multi-level correlation is performed which includes iterative refinement, sub-sequence merging, and final result classification.

Claims

1. A method of preprocessing media content for storage and access in a media reference database, the method comprising:

generating a signature term frequency (STF) for a signature of provided media content in a first media reference database, wherein the STF is a frequency of occurrence of the signature in the first media reference database and represents a measure of uniqueness for the signature as compared to existing signatures in the first media reference database; and

entering the signature using a hash index in a second media reference database, wherein the STF of the signature is less than a specified threshold, wherein the specified threshold represents a level of information content and uniqueness for the signature.

2. The method of claim 1 further comprising:

correlating selected query signatures with signatures stored in the second media reference database to determine a possible detected media sequence by making a first access of the second media reference database for a selected query signature using a first hash index and making a second access of the second media reference database for the selected query signature using a second hash index, wherein a bit that is close to a threshold for determining a state of the bit in the first hash index is changed to an opposite state for the second hash index.

3. The method of claim 1, wherein the STF is generated for each signature by combining the number of times each signature appears in a same reference content within a specified time window and the number of times each signature occurs in the first media reference database.

4. The method of claim 1, wherein the STF is generated for each signature by combining the number of times each signature appears in a same reference content.

5. The method of claim 1 wherein the STF is increased by a large value for each signature when the signature is similar to a signature in a dictionary list, wherein a distance measure is used to detect similarity of signatures on the dictionary list which includes a selected list of frequently occurring signatures observed from current and previous databases.

6. The method of claim 1, further comprising:

entering each signature in a dictionary of frequent signatures that is a collection of frequent signatures generated from one or more video reference databases, where each signature has more than a specified number of similar matching signatures within a certain bit error distance.

7. A method to detect a query sequence of audio and video signatures in a data base of audio and video signatures, the method comprising:

searching the database of audio and video signatures in response to a query sequence of audio and video signatures using a hash index for each query signature;

retrieving a set of database signatures that are similar as determined by a distance measure of the audio and video signatures to the query sequence of audio and video signatures in response to use of the hash index for each query signature to select a database entry;

generating a correlation in time score between corresponding pairs of signatures from the set of database signatures and the query sequence of audio and video signatures, wherein the correlation in time score is based on a first similarity score between a first query and a first reference signature, a second similarity score between a second query and a second reference signature, and a frame correlation between frames for the first query, the second query, and associated reference frames; and

identifying a matching sequence between query and reference if the correlation in time score is above a determined threshold.

8. The method of claim 7, further comprising:

accessing a second database and performing a correlation in time between corresponding pairs of signatures from a second set of database signatures and the query sequence of audio and video signatures, wherein the second database is indexed by video id and time location.

9. The method of claim 7 wherein correlation is performed in spatial domain using x,y locations of matching feature points and scale of matching feature points, and which are used as factors in calculating a final correlation score for pairs of matching reference and query signatures.

10. The method of claim 7, further comprising:

performing a correlation in space between corresponding pairs of signatures from a second set of database signatures and the query sequence of video signatures using spatial information in the associated data of the signatures, wherein the second database is indexed by video id and time location.

11. The method of claim 7 further comprising:

sub-dividing audio and video into smaller chapters based on time; and

searching the data base of audio and video signatures in a cluster search by use of a cluster index to detect chapters of the matching audio and video sequence, wherein the individual reference audio and video are sub-divided into smaller chapters and the most likely audio and video chapters are returned as a result of the cluster search.

12. The method of claim 11, further comprising:

detecting a likely time location of a matching video section, wherein a query consists of multiple overlapping query windows.

13. The method of claim 7 further comprising:

binning using a segment based Hough transform for segments of multiple trend lines within a selected range of query and original video frames as part of a correlation method to detect a best matching sequence within matching reference audio and video sequences; and

selecting a best bin.

14. The method of claim 7 further comprising:

performing frame to frame signature correlation on a detected trend line to generate a correlation score; and

thresholding the correlation score of matching sequences or individual frames to detect a matching sequence.

15. The method of claim 7, further comprising;

merging detected sequences that are overlapping and have similar slopes to generate merged overlapping sequences, wherein slopes are calculated for lines between matching sequences'"'"' starting and ending points with reference signature time values on an x-axis and query time values on a y-axis;

merging detected sequences that are not-overlapping with a gap between the detected sequences and have similar slopes to generate merged non-overlapping sequences;

combining the merged overlapping sequences and the merged non-overlapping sequences to generate merged sequences; and

retaining in the database of audio and video signatures the merged sequences that have relatively better correlation score as compared to a previously detected original or best merged sequence.

16. The method of claim 7, further comprising:

identifying an exact start and an end of a matching sequence between query and original videos;

iteratively extending the query and original start or end frame numbers so as to evaluate iteratively longer sequences; and

retaining extended sequences that have a relatively better correlation score to improve the accuracy of detected sequences.

17. The method of claim 7 further comprising:

performing in parallel a similarity search and a time correlation on separate partitions of the database of audio and video signatures;

sorting detected sequences according to a measure of the similarity of signatures; and

selecting best matches to report to a user.

18. The method of claim 7 further comprising:

weighing individual signatures in one or more databases based on uniqueness of each signature.

19. The method of claim 7 further comprising:

accessing a different database generated using orthogonal information to that in the data base of audio and video signatures; and

performing a correlation in time between corresponding pairs of signatures from an orthogonal set of database signatures and the query sequence of audio and video signatures.

20. The method of claim 7 further comprising:

performing trend correlation for an extended query and original sequence to enabling faster correlation; and

enabling a wider viewpoint detection.

21. A method of generating a score for confidence of matching a query media sequence with a reference media sequence, the method comprising:

generating a feature correlation score based on a correlation between multiple signatures of matching frames of the query media sequence and the reference media sequence;

generating a sequence correlation score using relative differences in frame numbers of the reference media sequence and the query media sequence;

generating a match confidence score based on a function of the feature correlation score and the sequence correlation score for the reference media sequence and the query media sequence; and

adding the reference media sequence with a generated match confidence score that exceeds a selectable confidence threshold to a list of matching media sequences, wherein the selectable confidence threshold is selected based on an accuracy chart that describes a false positive rate for types of distortion in content quality.

22. A method of performing fast sequence correlation comprising:

performing a fast similarity search using a direct hash index of signatures to identify a first plurality of likely matching chapters of a query media sequence and a reference media sequence;

performing a sequence correlation on a reference chapter and a query chapter to identify a second plurality of likely matching chapters of the query media sequence and the reference media sequence;

performing the fast similarity search and the sequence correlation in parallel on separate partitions of a reference database having a plurality of reference media sequences;

thresholding the first plurality of likely matching chapters and the second plurality of likely matching chapters to eliminate reference media sequences that have a low likelihood of matching and to determine a plurality of most likely matching reference media sequences; and

selecting the best matches from among the plurality of the most likely matching reference media sequences.

23. The method of claim 22 further comprising:

using a classifier with input from multiple matching sequences of media content to identify the separate partitions of the reference database that are likely to have matching media content.