Three-dimensional wavelet based video fingerprinting

• US 8,611,689 B1
• Filed: 12/15/2010
• Issued: 12/17/2013
• Est. Priority Date: 05/09/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): Park, Chan S
• Assistant Examiner(s): Thomas, Mia M
• Application Number:
  US12/968,825
• Time in Patent Office: 1,098 Days
• Field of Search: 382/100, 382/207, 382/248, 382/251, 382/253, 382/232, 382/305, 382/115, 382/118, 382/107, 382/278, 382/291, 348/395.1, 380/201, 380/210, 713/176
• US Class Current: 382/251
• 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: H04N 21/23418 involving operations for analysing video streams, e.g. detecting features or characteristics television picture signal circuitry for scene change detection H04N5/147; filtering for image enhancement G06T5/00; methods or arrangements for recognising scenes G06V20/00; arrangements characterised by components specially adapted for monitoring, identification or recognition of video in broadcast systems H04H60/59

Abstract

A method and system generates and compares fingerprints for videos in a video library. The video fingerprints provide a compact representation of the spatial and sequential characteristics of the video that can be used to quickly and efficiently identify video content. Because the fingerprints are based on spatial and sequential 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. Further, duplicate videos can be detected and discarded in order to preserve storage space.

Claims

1. A method for indexing a digital video library comprising a plurality of videos, each video having a plurality of video segments, the method comprising:

generating a three-dimensional wavelet transform for each of the plurality of video segments, each three-dimensional wavelet transform comprising a plurality of coefficients;

quantizing, by a computing device, a subset of N coefficients of the plurality of coefficients of each of the three-dimensional wavelet transforms to generate a quantized subset of N coefficients for each of the three-dimensional wavelet transforms, wherein each quantized coefficient comprises either a first symbol representing a positive coefficient, or a second symbol representing a negative coefficient;

setting each remaining coefficient not in the subsets of N coefficients to zero;

generating a plurality of video fingerprints from the quantized subsets of N coefficients and the remaining coefficients that are set to zero, each video fingerprint corresponding to a different video segment of the plurality of videos in the digital video library, wherein each video fingerprint represents spatial information within frames and sequential characteristics between the frames of the video segment;

indexing the plurality of video fingerprints; and

storing the indexed video fingerprints in a computer readable storage medium.

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

3. The method of claim 2, wherein the first hash process comprises a min-hash process.

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

5. The method of claim 2, further comprising:

storing a plurality of hash tables;

dividing the signature into a plurality of signature blocks; and

storing each signature block in a different one of the plurality of hash tables according to a second hash process.

6. The method of claim 5, wherein the second hash process is a locality sensitive hash process.

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

8. The method of claim 1, further comprising:

selecting, prior to quantizing, N coefficients having the largest absolute values as the subset of N coefficients.

9. The method of claim 1, further comprising:

selecting, prior to quantizing, N coefficients having magnitudes above a predetermined threshold value as the subset of N coefficients.

10. The method of claim 1, further comprising:

selecting, prior to quantizing, N coefficients having the largest values and having magnitudes above a predetermined threshold value as the subset of N coefficients.

11. The method of claim 1, wherein generating the three-dimensional wavelet transform for each of the video segments comprises:

generating the three-dimensional wavelet transform for a given video segment based on two spatial dimensions and a time dimension of the given video segment.

12. A non-transitory computer-readable storage medium storing instructions for indexing a digital video library, the instructions when executed by a processor cause the processor to perform steps including:

generating a three-dimensional wavelet transform for each of the plurality of video segments, each three-dimensional wavelet transform comprising a plurality of coefficients;

quantizing a subset of N coefficients of the plurality of coefficients of each of the three-dimensional wavelet transforms to generate a quantized subset of N coefficients for each of the three-dimensional wavelet transforms, wherein each quantized coefficient comprises either a first symbol representing a positive coefficient, or a second symbol representing a negative coefficient;

setting each remaining coefficient not in the subsets of N coefficients to zero;

generating a plurality of video fingerprints from the quantized subsets of N coefficients and the remaining coefficients that are set to zero, each video fingerprint corresponding to a different video segment of the plurality of videos in the digital video library, wherein each video fingerprint represents spatial information within frames and sequential characteristics between the frames of the video segment;

indexing the plurality of video fingerprints; and

storing the indexed video fingerprints in a computer readable storage medium.

13. The computer-readable storage medium of claim 12, wherein indexing comprises generating a signature for a first video fingerprint of the plurality of video fingerprints according to a first hash process, wherein the signature is uniquely associated with the first video fingerprint and comprises fewer bits than the first video fingerprint.

14. The computer-readable storage medium of claim 13, wherein the first hash process comprises a min-hash process.

15. The computer-readable storage medium of claim 13, 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.

16. The computer-readable storage medium of claim 13, further comprising instructions for:

storing a plurality of hash tables;

dividing the signature into a plurality of signature blocks; and

storing each signature block in a different one of the plurality of hash tables according to a second hash process.

17. The computer-readable storage medium of claim 16, wherein the second hash process is a locality sensitive hash process.

18. The computer-readable storage medium of claim 16, wherein storing the indexed video fingerprints includes storing a unique identifier indicating a video segment associated with the stored signature block.

19. A system for indexing a digital video library comprising:

one or more processors; and

a non-transitory computer-readable storage medium storing instructions executable by the one or more processors, the instructions when executed causing the one or more processors to;

generate a three-dimensional wavelet transform for each of the plurality of video segments, each three-dimensional wavelet transform comprising a plurality of coefficients;

quantize a subset of N coefficients of the plurality of coefficients of each of the three-dimensional wavelet transforms to generate a quantized subset of N coefficients for each of the three-dimensional wavelet transforms, wherein each quantized coefficient comprises either a first symbol representing a positive coefficient, or a second symbol representing a negative coefficient;

setting each remaining coefficient not in the subsets of N coefficients to zero;

generate a plurality of video fingerprints from the quantized subsets of N coefficients and the remaining coefficients that are set to zero, each video fingerprint corresponding to a different video segment of the plurality of videos in the digital video library, wherein each video fingerprint represents spatial information within frames and sequential characteristics between the frames of the video segment;

index the plurality of video fingerprints; and

store the indexed video fingerprints in a computer readable storage medium.

20. The system of claim 19, wherein indexing comprises generating a signature for a first video fingerprint of the plurality of video fingerprints according to a first hash process, wherein the signature is uniquely associated with the first video fingerprint and comprises fewer bits than the first video fingerprint.

21. The system of claim 20, 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.