Media fingerprinting and identification system

• US 8,195,689 B2
• Filed: 05/03/2010
• Issued: 06/05/2012
• Est. Priority Date: 06/10/2009
• Status: Active Grant

• Current Assignee: Roku, Inc.
• Original Assignee: Zeitera LLC
• Inventors: Ramanathan, Prashant, Pereira, Jose Pio, Merchant, Shashank
• Primary Examiner(s): Lewis, Cheryl
• Application Number:
  US12/772,566
• Publication Number:
  US 20100318515A1
• Time in Patent Office: 764 Days
• Field of Search: None
• US Class Current: 707/769
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/48 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/783 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/7847 using low-level visual features of the video content
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 20/46 Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames
• CPC Class Codes: Y10S 707/913 Multimedia

Abstract

The overall architecture and details of a scalable video fingerprinting and identification system that is robust with respect to many classes of video distortions is described. In this system, a fingerprint for a piece of multimedia content is composed of a number of compact signatures, along with traversal hash signatures and associated metadata. Numerical descriptors are generated for features found in a multimedia clip, signatures are generated from these descriptors, and a reference signature database is constructed from these signatures. Query signatures are also generated for a query multimedia clip. These query signatures are searched against the reference database using a fast similarity search procedure, to produce a candidate list of matching signatures. This candidate list is further analyzed to find the most likely reference matches. Signature correlation is performed between the likely reference matches and the query clip to improve detection accuracy.

Claims

1. A method of searching reference multimedia signatures that represent audio and video content of reference multimedia clips for a corresponding query multimedia clip, the method comprising:

generating an N dimension signature based on an N dimension descriptor and a traversal hash signature based on a combination of dimensions of the N dimension descriptor for each feature identified in a set of reference multimedia clips;

storing each N dimension signature and a link to a corresponding reference multimedia clip at a location in a reference signature database addressable by the traversal hash signature;

generating an N dimension query signature based on an N dimension query descriptor and a traversal hash query signature based on a combination of dimensions of the N dimension query descriptor for a query multimedia clip; and

searching the reference signature database using the traversal hash query signature to find similar signatures that are within a specified signature distance, wherein the similar signatures are aggregated in a candidate list of closely matching signatures that correspond to similar reference multimedia clips.

2. The method of claim 1, wherein a multimedia clip comprises image pixel data, video pixel data, or audio waveform data.

3. The method of claim 1, further comprising:

generating an N dimension descriptor for at least one feature of a reference multimedia clip; and

quantizing each dimension of the N dimension descriptor to generate the N dimension signature.

4. The method of claim 3, further comprising:

creating a Bx by By grid having Bx*By blocks located at the center of the at least one feature, the at least one feature having dimensions specified by a scalex and a scaley multiplication factors, each block having a Cx by Cy pixel grid;

computing multiple intensity differences for each pixel in the Cx by Cy pixel grid to another pixel in both x and y directions for a specified pixel offset that is greater than 1;

computing weighted sum combinations of the multiple intensity differences as x-gradient values and as a y-gradient values; and

generating the N dimension descriptor as a concatenation of combinations of the x-gradient values and y-gradient values for each block of the Bx*By blocks.

5. The method of claim 4, wherein the combinations of the x-gradient values and y-gradient values are combinations of a positive sum of x-gradient value, a negative sum of x-gradient values, a positive sum of y-gradient values, and a negative sum of y-gradient values for each of the Bx*By blocks, wherein the N dimension descriptor is an N=4*Bx*By dimension descriptor.

6. The method of claim 4, wherein the scalex multiplication factor or the scaley multiplication factor or both are adjusted to account for an expected error margin of +/−

D %, wherein D % represents effects of image distortions.

7. The method of claim 4, wherein the location of the center of the feature is adjusted to account for an expected error margin of +/−

D %, wherein D represents effects of image distortions.

8. The method of claim 1, further comprising:

combining multiple dimensions of the N dimension descriptor to form combined values; and

comparing the combined values with a traversal hash threshold to form the traversal hash signature.

9. The method of claim 8, further comprising:

combining multiple dimensions of the N dimension query descriptor to form query combined values; and

comparing the query combined values with the traversal hash threshold to form the traversal hash query signature.

10. The method of claim 1, wherein the traversal hash signature includes additional bits representing a quadrant having the center of an underlying feature and a scale of the underlying feature.

11. The method of claim 1, wherein the traversal hash signature includes a polarity value that indicates whether the underlying feature is a light coloring on a dark background or a dark coloring on a light background.

12. The method of claim 1, further comprising:

sorting the candidate list according to a count of the number of times a closely matching signature appears in the candidate list to find likely reference multimedia clip match signatures.

13. The method of claim 12, further comprising:

determining a plurality of scores, wherein each score is based on a distance between the N dimension query signature and a different one of the likely reference multimedia clip match signatures; and

comparing the plurality of scores with a score threshold to determine whether a reference multimedia clip associated with a score is a true positive match or a false positive match.

14. The method of claim 1, further comprising:

counting a frequency of occurrence of multimedia clip identifications associated with each closely matching signature in the candidate list; and

sorting by the frequency of occurrence to find T likely reference multimedia clip matches, where T=1 or T>

1.

15. The method of claim 1, further comprises:

generating features from the multimedia clips;

computing one or more descriptors for each of the generated features; and

computing one or more signatures and associated traversal hash signatures for each of the one or more descriptors.

16. The method of claim 1, further comprising:

storing a secondary copy of each N dimension signature for each corresponding reference multimedia clip according to a multimedia id and timestamp as a secondary index, wherein the traversal hash signature is a primary index.

17. The method of claim 16, further comprises,

comparing the N dimension query signature to signatures in the reference signature database associated with the traversal hash signature to find similar signatures that are within a specified signature distance.

18. A method of forming accurate descriptors of features in multimedia clips, the method comprising:

determining a scale and a location of the center parameters for each feature of a plurality of features selected from a frame from a multimedia clip;

creating a Bx by By grid having Bx*By blocks located at the center of each feature and each block having a Cx by Cy pixel grid;

computing for each block, functions of multiple intensity differences between each pixel in a block'"'"'s Cx by Cy pixel grid and another pixel for a specified pixel offset that is greater than 1 and based on the scale and location of center parameters;

generating a first N dimension descriptor as a concatenation of the functions for each block of the Bx*By blocks; and

adjusting individually the scale and location of center parameters to account for an expected error margin due to image distortions to generate at least a second N dimension descriptor as a concatenation of the functions for each block of the Bx*By blocks as adjusted according to the expected error margin.

19. The method of claim 18, wherein the scale is specified by a scalex and a scaley multiplication factors and the multiple intensity differences are computed in both x and y directions based on the scalex, scaley, and location of center parameters.

20. The method of claim 19, wherein the functions of the multiple intensity differences are combinations of a positive sum of x-gradient value, a negative sum of x-gradient values, a positive sum of y-gradient values, and a negative sum of y-gradient values for each of the Bx*By blocks, wherein the x-gradient values are weighted sum of combinations of the multiple intensity differences in the x direction and the y-gradient values are weighted sum of combinations of the multiple intensity differences in the y direction and N is equal to 4*Bx*By.

21. A non-transitory computer readable medium storing a computer program which causes a computer system to perform a method of searching reference multimedia signatures that represent audio and video content of reference multimedia clips for a corresponding query multimedia clip, the method comprising:

generating an N dimension signature based on an N dimension descriptor and a traversal hash signature based on a combination of dimensions of the N dimension descriptor for each feature identified in a set of reference multimedia clips;

storing each N dimension signature and a link to a corresponding reference multimedia clip at a location in a reference signature database addressable by the traversal hash signature;

generating an N dimension query signature based on an N dimension query descriptor and a traversal hash query signature based on a combination of dimensions of the N dimension query descriptor for a query multimedia clip; and

searching the reference signature database using the traversal hash query signature to find similar signatures that are within a specified signature distance, wherein the similar signatures are aggregated in a candidate list of closely matching signatures that correspond to similar reference multimedia clips.

22. The non-transitory computer readable medium of claim 21, further comprising:

generating an N dimension descriptor for at least one feature of a reference multimedia clip;

creating a Bx by By grid having Bx*By blocks located at the center of the at least one feature, the at least one feature having dimensions specified by a scalex and a scaley multiplication factors, each block having a Cx by Cy pixel grid;

computing multiple intensity differences for each pixel in the Cx by Cy pixel grid to another pixel in both x and y directions for a specified pixel offset that is greater than 1;

computing weighted sum combinations of the multiple intensity differences as x-gradient values and as a y-gradient values;

generating the N dimension descriptor as a concatenation of combinations of the x-gradient values and y-gradient values for each block of the Bx*By blocks; and

quantizing each dimension of the N dimension descriptor to generate the N dimension signature.

23. The non-transitory computer readable medium of claim 22, wherein the combinations of the x-gradient values and y-gradient values are combinations of a positive sum of x-gradient value, a negative sum of x-gradient values, a positive sum of y-gradient values, and a negative sum of y-gradient values for each of the Bx*By blocks, wherein the N dimension descriptor is an N=4*Bx*By dimension descriptor.

24. The non-transitory computer readable medium of claim 22, wherein the scalex multiplication factor or the scaley multiplication factor or both are adjusted to account for an expected error margin of +/−

D %, wherein D % represents effects of image distortions.

25. The non-transitory computer readable medium of claim 22, wherein the location of the center of the feature is adjusted to account for an expected error margin of +/−

D %, wherein D % represents effects of image distortions.

26. The non-transitory computer readable medium of claim 21, further comprising:

storing a secondary copy of each N dimension signature for each corresponding reference multimedia clip according to a multimedia id and timestamp as a secondary index, wherein the traversal hash signature is a primary index.

27. The non-transitory computer readable medium of claim 26, further comprises:

comparing the N dimension query signature to signatures in the reference signature database associated with the traversal hash signature to find similar signatures that are within a specified signature distance.

28. A method for creating a media database, the method comprising:

generating a plurality of signatures from descriptors of selected media content;

selecting a signature from the plurality of signatures based on a distribution of bit values in the selected signature and on values of a corresponding descriptor;

generating a traversal hash signature from the corresponding descriptor; and

storing the selected signature in a media database at a location within a set of contiguous locations based on the traversal hash signature used as a primary index.

29. The method of claim 28, further comprising:

storing a second copy of the selected signature in the media database at another location within a set of contiguous locations based on a multimedia identification value and a timestamp of the media content associated with the selected signature.

30. The method of claim 28, further comprising:

selecting a signature from the plurality of signatures that are associated with a corresponding descriptor made up of descriptor values and identified by a function of the descriptor values that meets or exceeds a threshold value.

31. The method of claim 28, further comprising:

computing an average distance between a feature center location and M selected near features'"'"' center locations to determine a spatial diversity value, wherein the average distance, or “

closeness”

indicates the density of features in terms of location; and

eliminating signatures that are too close based on an established threshold for closeness.

32. The method of claim 28, further comprising:

computing signature bit distance values between each signature for a current frame in the media database and each signature in a following frame in the media database;

determining whether the signature bit distance values are less than or equal to a first robustness threshold R; and

eliminating signatures that have bit distance values greater than R that are not temporally robust.

33. The method of claim 28, further comprising:

computing hash bit distance values between each traversal hash signature for a current frame in the media database and each traversal hash signature in a following frame in the media database;

determining whether the hash bit distance values are less than or equal to a second robustness threshold Q; and

eliminating traversal hash signatures that have bit distance values greater than Q that are not temporally robust.