Endpoint based video fingerprinting

• US 8,611,422 B1
• Filed: 06/19/2007
• Issued: 12/17/2013
• Est. Priority Date: 06/19/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Yagnik, Jay, Rowley, Henry A., Ioffe, Sergey
• Primary Examiner(s): Orgad, Edan
• Assistant Examiner(s): Kabir, Jahangir
• Application Number:
  US11/765,292
• Time in Patent Office: 2,373 Days
• Field of Search: 375/240.01, 375/240.12, 375/240.16
• US Class Current: 375/240.16
• CPC Class Codes: G06F 16/783 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/7834 using audio features
• CPC Class Codes: G06T 1/0021 Image watermarking
• 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: G06V 20/48 Matching video sequences

Abstract

A method and system generates and compares fingerprints for videos in a video library. The video fingerprints provide a compact representation of the temporal locations of discontinuities in the video that can be used to quickly and efficiently identify video content. Discontinuities can be, for example, shot boundaries in the video frame sequence or silent points in the audio stream. Because the fingerprints are based on structural discontinuity characteristics rather than exact bit sequences, visual content of videos can be effectively compared even when there are small differences between the videos in compression factors, source resolutions, start and stop times, frame rates, and so on. Comparison of video fingerprints can be used, for example, to search for and remove copyright protected videos from a video library. Furthermore, duplicate videos can be detected and discarded in order to preserve storage space.

Claims

1. A method of fingerprinting a video having a sequence of video frames, the method performed by a computer system, the method comprising:

identifying, by the computer system, a plurality of discontinuities in features of audio-visual content of the video, wherein the sequence of video frames includes frames associated with one or more associated discontinuities and frames not associated with discontinuities;

generating an encoded data representation representing the sequence of video frames, wherein the frames associated with the one or more associated discontinuities are represented by first values in the encoded data representation, and wherein frames not associated with the discontinuities are represented by second values in the encoded data representation, the second values different than the first values, and wherein the first values and the second values are arranged in a sequence in the encoded data representation corresponding to the sequence of video frames;

segmenting, by the computer system, the encoded data representation into a plurality of partially overlapping segments, wherein consecutive segments represent portions of the audio-visual content that overlap by one or more frames;

generating, by the computer system, a fingerprint for each segment; and

storing the fingerprints to a computer readable storage medium to represent the sequence of video frames.

2. The method of claim 1, wherein a first discontinuity of the plurality of discontinuities comprises a shot boundary in the sequence of video frames.

3. The method of claim 1, wherein identifying a plurality of discontinuities comprises analyzing depicted motion between the frames and determining an endpoint frame where the motion is at a peak.

4. The method of claim 1, wherein identifying a plurality of discontinuities comprises analyzing volume of an audio stream associated with the sequence of video frames and determining an endpoint frame where the volume is below a predetermined threshold volume.

5. The method of claim 1, further comprising normalizing the sequence of video frames by reducing at least one of frame size and color information.

6. The method of claim 1, wherein generating the encoded data representation further comprises:

associating a first frame in the sequence of frames with one or more bits;

setting the one or more bits to a first value if the first frame corresponds to one of the locations of the identified plurality of discontinuities; and

setting the one or more bits to a second value if the first frame does not correspond to one of the locations of the identified plurality of discontinuities.

7. The method of claim 1, wherein a first fingerprint of the plurality of fingerprints overlaps a second fingerprint of the plurality of fingerprints by a number of bits.

8. The method of claim 1, further comprising storing a video fingerprint sequence for the video, wherein the fingerprint sequence comprises the plurality of fingerprints in sequential order.

9. A method for managing a digital video library, the method performed by a computer system, the method comprising:

identifying, by the computer system, a plurality of discontinuities in features of audio-visual content of a video in the digital video library, the video having a sequence video frames, wherein the sequence of video frames includes frames associated with one or more associated discontinuities and frames not associated with discontinuities;

generating an encoded data representation representing the sequence of video frames, wherein the frames associated with the one or more associated discontinuities are represented by first values in the encoded data representation, and wherein frames not associated with the discontinuities are represented by second values in the encoded data representation, the second values different than the first values, and wherein the first values and the second values are arranged in a sequence in the encoded data representation corresponding to the sequence of video frames;

segmenting, by the computer system, the encoded data representation into a plurality of partially overlapping segments, wherein consecutive segments represent portions of the audio-visual content that overlap by one or more frames;

generating, by the computer system, a sequence of video fingerprints including a fingerprint for each of the partially overlapping segments;

indexing the sequence of video fingerprints; and

storing the indexed video fingerprints to a tangible computer readable storage medium.

10. The method of claim 9, wherein a first discontinuity in the at least one video comprises a shot boundary in a sequence of frames of the at least one video.

11. The method of claim 9, wherein a first discontinuity in the at least one video comprises a silent point in an audio stream of the at least one video.

12. The method of claim 9, wherein indexing comprises generating a signature for a first video fingerprint of the sequence of video fingerprints according to a first hash process, and wherein the signature is uniquely associated with the first video fingerprint and comprises fewer bits than the first video fingerprint.

13. The method of claim 12, wherein the first hash process is a min-hash process.

14. The method of claim 12, wherein the first hash process comprises:

re-arranging bits of the first video fingerprint according to a predetermined number of pre-defined permutations; and

storing a location of a first “

1”

in the re-arranged bits following each permutation.

15. The method of claim 12, wherein the signature is divided into a plurality of signature blocks, and wherein each signature block is stored in a hash table according to a second hash process.

16. The method of claim 15, wherein the second hash process is a locality sensitive hash process.

17. The method of claim 15, wherein storing the indexed video fingerprints includes storing a unique identifier indicating a video segment associated with the stored signature block.

18. A computer-implemented method for identifying duplicate video content in a video library comprising:

receiving, by a computer system, a video comprising a sequence of frames;

identifying, by the computer system, a plurality of discontinuities in features of audio-visual content of the received video, wherein the sequence of video frames includes frames associated with one or more associated discontinuities and frames not associated with discontinuities;

generating an encoded data representation representing the sequence of video frames, wherein the frames associated with the one or more associated discontinuities are represented by first values in the encoded data representation, and wherein frames not associated with the discontinuities are represented by second values in the encoded data representation, the second values different than the first values, and wherein the first values and the second values are arranged in a sequence in the encoded data representation corresponding to the sequence of video frames;

segmenting, by the computer system, the encoded data representation into a plurality of partially overlapping segments, wherein consecutive segments represent portions of the audio-visual content that overlap by one or more frames;

generating, by the computer system, a fingerprint sequence for the received video including a fingerprint for each of the partially overlapping segments;

searching a reference database for reference videos having reference fingerprint sequences that match the fingerprint sequence for the received video; and

determining at least one reference video corresponding to at least one matching reference fingerprint sequence.

19. The method of claim 18, wherein a first discontinuity of the plurality of discontinuities comprises a shot boundary in the sequence of video frames.

20. The method of claim 18, wherein a first discontinuity of the plurality of discontinuities comprises a silent point in an audio stream of the video.

21. The method of claim 18, further comprising removing the at least one reference video corresponding to the at least one matching reference fingerprint sequence from the video library.

22. The method of claim 18, further comprising generating a signature sequence for the fingerprint sequence, wherein a first signature of the signature sequence is divided into a plurality of signature blocks.

23. The method of claim 22, further comprising:

comparing a first signature block of the plurality of signature blocks to reference signature blocks in a first hash table;

incrementing a matching count for a reference video segment associated with a matching reference signature block in the first hash table; and

designating the reference video segment as a matching reference segment if the matching count is greater than a predetermined threshold.

24. The method of claim 23, further comprising determining a number of consecutive matching reference segments that match consecutive received segments of the received video.

25. A non-transitory computer-readable storage medium storing instructions for generating a video fingerprint, the instructions including a plurality of modules executable by one or more computer systems, the plurality of modules comprising:

an input module adapted to receive a video have a sequence of video frames;

an endpoint detection module adapted to identify a plurality of discontinuities in features of audio-visual content of the video, wherein the sequence of video frames includes frames associated with one or more associated discontinuities and frames not associated with discontinuities;

an encoding module adapted to generate an encoded data representation representing the sequence of video frames, wherein the frames associated with the one or more associated discontinuities are represented by first values in the encoded data representation, and wherein frames not associated with the discontinuities are represented by second values in the encoded data representation, the second values different than the first values, and wherein the first values and the second values are arranged in a sequence in the encoded data representation corresponding to the sequence of video frames;

a segmenting module adapted to segment the encoded data representation into a plurality of partially overlapping segments, wherein consecutive segments represent portions of the audio-visual content that overlap by one or more frames, and to generate a sequence of fingerprints including a fingerprint for each of the partially overlapping segments; and

an output module adapted to output the sequence of fingerprints.

26. The non-transitory computer-readable storage medium of claim 25, wherein a first discontinuity of the plurality of discontinuities is a shot boundary in the sequence of video frame.

27. The non-transitory computer-readable storage medium of claim 25, wherein a first discontinuity of the plurality of discontinuities is a silent point in an audio stream of the video.

28. The non-transitory computer-readable storage medium of claim 25, further comprising a normalization module adapted to normalize the received video to a predetermined format.

29. A system for identifying duplicate video content in a video database comprising:

an ingest server adapted to receive a video comprising a sequence of video frames;

an endpoint detection module adapted to identify a plurality of discontinuities in features of audio-visual content of the video, wherein the sequence of video frames includes frames associated with one or more associated discontinuities and frames not associated with discontinuities;

an encoding module adapted to generate an encoded data representation representing the sequence of video frames, wherein the frames associated with the one or more associated discontinuities are represented by first values in the encoded data representation, and wherein the frames not associated with discontinuities are represented by second values in the encoded data representation, the second values different than the first values, and wherein the first values and the second values are arranged in a sequence in the encoded data representation corresponding to the sequence of video frames;

a segmenting module adapted to segment the encoded data representation into a plurality of partially overlapping segments, wherein consecutive segments represent portions of the audio-visual content that overlap by one or more frames, and to generate a sequence of fingerprints including a fingerprint for each of the partially overlapping segments;

an indexing module adapted to assign an index value to the received video according to at least one of the sequence of video fingerprints for the video;

a reference database comprising a plurality of reference fingerprints associated with a plurality of reference videos; and

a matching module adapted to search the reference database to identify at least one of the plurality of reference videos in the reference database having a similar video fingerprint to one or more of the sequence of video fingerprints of the received video.

30. The system of claim 29, wherein a first discontinuity of the plurality of discontinuities comprises a shot boundary in the sequence of video frames.

31. The system of claim 29, wherein a first discontinuity of the plurality of discontinuities is a silent point in an audio stream of the video.