Media fingerprinting and identification system

• US 8,364,703 B2
• Filed: 05/03/2012
• Issued: 01/29/2013
• 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, Stojancic, Mihailo M.
• Primary Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US13/463,137
• Publication Number:
  US 20120215789A1
• Time in Patent Office: 271 Days
• Field of Search: 707/747, 707/769, 707/770, 707/913, 707/914, 707/916, 707/999.003, 707/999.107
• 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 for automatically fingerprinting multimedia content received from a distributed source, and search monitoring for information corresponding to the multimedia content on a portable device, the method comprising:

generating on a portable device an N-dimensional query descriptor for a feature identified in a temporal segment of audio data received on the portable device;

generating on the portable device an N-dimensional query signature based on a quantization of the N-dimensional query descriptor;

generating on the portable device a traversal hash query signature based on a combination of dimensions of the N-dimension query descriptor; and

searching a reference multimedia clip database on the portable device using the traversal hash query signature to find a set of signatures that are within a specified signature distance to the N-dimensional query signature, wherein the portable device is provided access to data related to multimedia content associated with a likely matching signature selected from the set of signatures.

2. The method of claim 1 further comprising:

generating on a portable device an N-dimensional descriptor for each feature identified in a temporal segment of reference audio data received on the portable device;

generating on the portable device an N-dimensional signature based on a quantization of the N-dimensional descriptor;

generating on the portable device a traversal hash signature based on a combination of dimensions of the N-dimension descriptor; and

storing each N-dimensional signature at a location on the portable device in a reference signature database addressable by the traversal hash signature.

3. The method of claim 2, wherein the traversal hash signature includes additional bits representing a time stamp of an underlying feature.

4. The method of claim 1 further comprising:

searching a reference multimedia clip database on a remote server accessible by the portable device using the traversal hash query signature to find a set of signatures that are within a specified signature distance to the N-dimensional query signature, wherein the portable device is provided access to data related to multimedia content associated with a likely matching signature selected from the set of signatures.

5. The method of claim 1 further comprising:

generating on a remote server an N-dimensional descriptor for each feature identified in a temporal segment of reference audio data received on the remote server;

generating on the remote server an N-dimensional signature based on a quantization of the N-dimensional descriptor;

generating on the remote server a traversal hash signature based on a combination of dimensions of the N-dimension descriptor, wherein the traversal hash signature includes additional bits representing a time stamp of an underlying feature; and

storing each N-dimensional signature at a location in a reference signature database on the remote server accessible by the portable device and addressable by the traversal hash signature.

6. The method of claim 5, 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.

7. The method of claim 6, 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.

8. The method of claim 1, wherein the portable device is configurable to select image pixel data, video pixel data, or audio data for analysis.

9. The method of claim 1 further comprising:

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

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

10. The method of claim 1, wherein the traversal hash query signature includes additional bits representing a time stamp of an underlying feature.

11. The method of claim 1 further comprising:

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

12. The method of claim 11 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 matching reference multimedia clip 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.

13. The method of claim 1, further comprises:

identifying features in the audio data and in video data, wherein the audio data and video data are selected from the multimedia content;

generating audio descriptors and separately generating video descriptors for each of the generated features; and

generating one or more signatures and associated traversal hash signatures for each of the audio descriptors and video descriptors.

14. A computer readable non-transitory medium storing a computer program which causes a computer system to perform a method for automatically fingerprinting multimedia content received from a distributed source, and search monitoring for information corresponding to the multimedia content on a portable device, the method comprising:

generating on a portable device an N-dimensional query descriptor for a feature identified in a temporal segment of audio data received on the portable device;

generating on the portable device an N-dimensional query signature based on a quantization of the N-dimensional query descriptor;

generating on the portable device a traversal hash query signature based on a combination of dimensions of the N-dimension query descriptor; and

searching a reference multimedia clip database initiated by the portable device using the traversal hash query signature to find a set of signatures that are within a specified signature distance to the N-dimensional query signature, wherein the portable device is provided access to data related to multimedia content associated with a likely matching signature selected from the set of signatures.

15. The computer readable non-transitory medium of claim 14, wherein the reference multimedia clip database is located on the portable device.

16. The computer readable non-transitory medium of claim 14, wherein the reference multimedia clip database is located on a remote server accessible by the portable device.

17. The computer readable non-transitory medium of claim 14 further comprising:

generating on a portable device an N-dimensional descriptor for each feature identified in a temporal segment of reference audio data received on the portable device;

generating on the portable device an N-dimensional signature based on a quantization of the N-dimensional descriptor;

generating on the portable device a traversal hash signature based on a combination of dimensions of the N-dimension descriptor; and

storing each N-dimensional signature at a location on the portable device in a reference signature database addressable by the traversal hash signature.

18. The computer readable non-transitory medium of claim 14 further comprising:

generating on a remote server an N-dimensional descriptor for each feature identified in a temporal segment of reference audio data received on the remote server;

generating on the remote server an N-dimensional signature based on a quantization of the N-dimensional descriptor;

generating on the remote server a traversal hash signature based on a combination of dimensions of the N-dimension descriptor; and

storing each N-dimensional signature at a location in a reference signature database on the remote server accessible by the portable device and addressable by the traversal hash signature.

19. The computer readable non-transitory medium of claim 18 further comprising:

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

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

20. The computer readable non-transitory medium of claim 18 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.

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

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.

22. The computer readable non-transitory medium of claim 14, wherein the portable device is configurable to select image pixel data, video pixel data, or audio data for analysis.

23. The computer readable non-transitory medium of claim 14 further comprising:

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

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

24. The computer readable non-transitory medium of claim 14, wherein the traversal hash query signature includes additional bits representing a time stamp of an underlying feature.

25. The computer readable non-transitory medium of claim 14 further comprising:

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

26. The computer readable non-transitory medium of claim 25 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 matching reference multimedia clip 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.

27. The computer readable non-transitory medium of claim 14 further comprising:

identifying features in the audio data and in video data, wherein the audio data and video data are selected from the multimedia content;

generating audio descriptors and separately generating video descriptors for each of the generated features; and

generating one or more signatures and associated traversal hash signatures for each of the audio descriptors and video descriptors.

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

generating a plurality of audio signatures from audio descriptors of audio content and a plurality of video signatures from video descriptors of video content, wherein the audio content and the video content are identified as original content and selected from multimedia content received on a portable device;

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

generating a traversal hash audio signature from the corresponding audio descriptor; and

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

29. The method of claim 28, wherein the reference multimedia clip database is located on the portable device.

30. The method of claim 28, wherein the reference multimedia clip database is located on a remote server accessible by the portable device.

31. The method of claim 28 further comprising:

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

generating a traversal hash video signature from the corresponding video descriptor; and

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

32. The method of claim 28, wherein the media database is located on the portable device and the portable device is provided access to data related to the multimedia content.

33. The method of claim 28, wherein the media database is located on a remote server accessible from the portable device and the remote server is provided access to data related to the multimedia content.

34. The method of claim 28, further comprising:

storing a second copy of the selected audio 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 multimedia content associated with the selected audio signature.

35. The method of claim 28, further comprising:

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

36. The method of claim 28, further comprising:

computing signature bit distance values between each audio signature for a current audio frame in the media database and each audio signature in a following audio 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 audio signatures that have bit distance values greater than R that are not temporally robust.

37. The method of claim 28, further comprising:

computing hash bit distance values between each traversal hash audio signature for a current audio frame in the media database and each traversal hash audio signature in a following audio 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 audio signatures that have bit distance values greater than Q that are not temporally robust.

38. The method of claim 28, further comprising:

organizing a traversal hash audio signature array to contain a plurality of traversal hash audio signatures, wherein each traversal hash audio signature identifies a cluster of audio signatures and a link reference to a list of audio signature records for an identified cluster of audio signatures; and

performing a similarity search for audio signatures within the identified cluster of audio signatures that have a signature distance of less than or equal to a specified distance R.