Three-dimensional wavelet based video fingerprinting

• US 8,094,872 B1
• Filed: 05/09/2007
• Issued: 01/10/2012
• 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): Repko, Jason M
• Assistant Examiner(s): Thomas, Mia M
• Application Number:
  US11/746,339
• Time in Patent Office: 1,707 Days
• Field of Search: 382/100, 382/115, 382/118, 382/107, 382/207, 382/195, 382/232, 382/248, 382/251, 380/26, 380/54, 380/201, 380/210, 380/287, 713/176
• US Class Current: 382/100
• 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 fingerprinting a video, comprising:

receiving the video;

segmenting the video into a plurality of video segments including a first video segment, the first video segment having a plurality of video frames;

performing a three-dimensional transform on the plurality of video frames in the first video segment to generate a three-dimensional wavelet, wherein the three-dimensional wavelet represents spatial information within the video frames and sequential characteristics between the video frames;

quantizing the three-dimensional wavelet to generate a first video fingerprint;

storing a video fingerprint sequence to a non-transitory computer readable storage medium, wherein each video fingerprint in the video fingerprint sequence is associated with a different video segment in the plurality of video segments;

comparing the video fingerprint sequence to a reference fingerprint sequence; and

determining a similarity between the video fingerprint sequence and the reference fingerprint sequence based on the comparison.

2. The method of claim 1, wherein performing the three-dimensional transform on the plurality of frames comprises performing a Haar wavelet transform on each row, column, and time column of the plurality of frames.

3. The method of claim 1, further comprising:

encoding and flattening the three-dimensional wavelet to a one-dimensional structure.

4. The method of claim 1, further comprising normalizing the plurality of frames by converting at least one of frame size, frame rate, and color information to a standard format.

5. The method of claim 1, wherein a second video segment of the plurality of video segments overlaps the first video segment by one or more frames.

6. The method of claim 1, wherein quantizing the three-dimensional wavelet comprises:

selecting a subset of N coefficients of the three-dimensional wavelet, where N is an integer; and

setting negative coefficients of the N coefficients to a first fixed value;

setting positive coefficients of the N coefficients to a second fixed value;

setting remaining coefficients of the three-dimensional wavelet to a third fixed value, wherein the remaining coefficients are not among the N coefficients.

7. The method of claim 6, wherein the first fixed value represents −

1, the second fixed value represents +1, and the third fixed value represents zero.

8. The method of claim 6, wherein selecting the N coefficients comprises:

selecting N largest magnitude coefficients of the three-dimensional wavelet.

9. The method of claim 6, wherein selecting the N coefficients comprises:

selecting N coefficients having a magnitude greater than a threshold magnitude.

10. The method of claim 1, wherein storing the video fingerprint comprises:

indexing the video fingerprint to an index storing an association between the video fingerprint and an identifier of the first video segment.

11. A computer system for generating a video fingerprint comprising:

one or more processors; and

a non-transitory computer readable storage medium storing computer-executable program modules executable by the one or more processors, the computer-executable program modules comprising;

an input module adapted to receive a video;

a segmenting module adapted to segment the video into a plurality of video segments including a first video segment, each segment including at least two frames;

a transform module adapted to perform a three-dimensional transform on the at least two frames in the first video segment to generate a three-dimensional wavelet, wherein the three dimensional wavelet represents spatial characteristics and sequential characteristics of the at least two frames associated with the first video segment;

a quantizing module adapted to quantize the three-dimensional wavelet to generate a first video fingerprint;

an output module adapted to store a video fingerprint sequence to a non-transitory computer readable storage medium, wherein each video fingerprint in the video fingerprint sequence is associated with a different video segment in the plurality of video segments; and

a comparison module adapted to compare the video fingerprint sequence to a reference fingerprint sequence and determine a similarity between the video fingerprint sequence and the reference fingerprint sequence based on the comparison.

12. The computer system of claim 11, further comprising a normalization module adapted to normalize the received video to a predetermined format.

13. The computer system of claim 11, wherein performing the three-dimensional transform on the first video segment comprises performing a Haar wavelet transform on each row, column, and time column of the first video segment.

14. The computer system of claim 11, wherein the quantization module is further configured to encode and flatten the three-dimensional wavelet to a one-dimensional structure.

15. The computer system of claim 11, the computer readable storage medium further storing program instructions for normalizing the first video segment by converting at least one of frame size, frame rate, and color information to a standard format.

16. The computer system of claim 11, wherein a second video segment of the plurality of video segments overlaps the first video segment by one or more frames.

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

receiving the video;

segmenting the video into a plurality of video segments including a first video segment, the first video segment having a plurality of video frames;

performing a three-dimensional transform on the plurality of video frames in the first video segment to generate a three-dimensional wavelet, wherein the three-dimensional wavelet represents spatial information within the video frames and sequential characteristics between the video frames;

quantizing the three-dimensional wavelet to generate a first video fingerprint;

storing a video fingerprint sequence to a non-transitory computer readable storage medium, wherein each video fingerprint in the video fingerprint sequence is associated with a different video segment in the plurality of video segments;

comparing the video fingerprint sequence to a reference fingerprint sequence; and

determining a similarity between the video fingerprint sequence and the reference fingerprint sequence based on the comparison.

18. The non-transitory computer-readable storage medium of claim 17, wherein performing the three-dimensional transform on the plurality of frames comprises performing a Haar wavelet transform on each row, column, and time column of the plurality of frames.

19. The non-transitory computer-readable storage medium of claim 17, further comprising:

encoding and flattening the three-dimensional wavelet to a one-dimensional structure.

20. The non-transitory computer-readable storage medium of claim 17, the instructions when executed further causing the processor to normalize the plurality of frames by converting at least one of frame size, frame rate, and color information to a standard format.

21. The non-transitory computer-readable storage medium of claim 17, wherein a second video segment of the plurality of video segments overlaps the first video segment by one or more frames.