Method and system for fingerprinting digital video object based on multiresolution, multirate spatial and temporal signatures

• US 8,009,861 B2
• Filed: 03/02/2007
• Issued: 08/30/2011
• Est. Priority Date: 04/28/2006
• Status: Active Grant

• Current Assignee: Vobile Incorporated (Vobile Group Ltd.)
• Original Assignee: Vobile Incorporated (Vobile Group Ltd.)
• Inventors: Lu, Jian, Wang, Yangbin
• Primary Examiner(s): Wu; Jingge
• Assistant Examiner(s): Ansari; Tahmina
• Application Number:
  US11/681,567
• Publication Number:
  US 20070253594A1
• Time in Patent Office: 1,642 Days
• Field of Search: None
• US Class Current: 382/100
• CPC Class Codes: G06F 16/7847 using low-level visual features of the video content
• 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: H04N 19/20 using video object coding
• CPC Class Codes: H04N 21/8358 involving watermark protecting executable software by watermarking G06F21/16; image watermarking in general G06T1/0021; watermarks inserted in still images for transmission purposes H04N1/32144; inserting watermarks during video coding H04N19/467

Abstract

A method and system for generating a fingerprint for a video object. The method includes obtaining a plurality of frames associated with a video object. Additionally, the method includes, for each of the plurality of frames, processing information associated with the plurality of frames, determining a plurality of spatial signatures for the each of the plurality of frames based on at least information associated with the each of the plurality of frames, and determining a plurality of temporal signatures for the each of the plurality of frames based on at least information associated with the plurality of frames. The plurality of spatial signatures corresponds to a plurality of resolutions respectively, and the plurality of temporal signatures corresponding to a plurality of frame rates respectively.

Claims

1. A computer implemented method for generating a fingerprint for a video object that is performed by a computer system programmed to perform the method, comprising:

obtaining, by the computer system, a plurality of frames associated with a video object;

for each of the plurality of frames,

processing, by the computer system, information associated with the plurality of frames;

determining, by the computer system, a plurality of spatial signatures for the each of the plurality of frames based on at least information associated with the each of the plurality of frames, the plurality of spatial signatures corresponding to a plurality of resolutions respectively;

determining, by the computer system, a plurality of temporal signatures for the each of the plurality of frames based on at least information associated with the plurality of frames, the plurality of temporal signatures corresponding to a plurality of frame rates respectively;

processing, by the computer system, information associated with the plurality of spatial signatures and the plurality of temporal signatures; and

determining a frame fingerprint for the each of the plurality of frames, the frame fingerprint including the plurality of spatial signatures corresponding to the plurality of resolutions respectively and the plurality of temporal signatures corresponding to the plurality of frame rates respectively;

processing, by the computer system, a plurality of frame fingerprints for the plurality of frames respectively, the plurality of frame fingerprints including the frame fingerprint for the each of the plurality of frames;

determining, by the computer system, a video fingerprint for the video object, the video fingerprint including the plurality of frame fingerprints; and

storing, by the computer system, the video fingerprint for the video object in a data storage separate from the video object, wherein the video object is not modified by the video fingerprint.

2. The method of claim 1, and further comprising:

for the each of the plurality of frames,

determining, by the computer system, a plurality of spatial-temporal signatures for the each of the plurality of frames based on at least information associated with the plurality of frames, the plurality of spatial-temporal signatures corresponding to a plurality of combinations of resolutions and frame rates respectively;

processing, by the computer system, information associated with the plurality of spatial-temporal signatures;

wherein the frame fingerprint further including the plurality of spatial-temporal signatures corresponding to the plurality of combinations of resolutions and frame rates respectively.

3. The method of claim 1, and further comprising:

for the each of the plurality of frames, storing, by the computer system the frame fingerprint for the each of the plurality of frames in the data storage.

4. The method of claim 1, and further comprising storing, by the computer system, the video fingerprint for the video object in a video fingerprint database.

5. The method of claim 1 wherein the determining a plurality of spatial signatures comprises for each of the plurality of resolutions, dividing, by the computer system, the each of the plurality of frames into a number of columns and a number of rows, the each of the plurality of resolutions begin represented by, at least, the number of columns and the number of rows.

6. The method of claim 1 wherein the determining a plurality of temporal signatures comprises for each of the plurality of frame rates, determining, by the computer system, a difference value corresponding to the each of the plurality of frames and an adjacent frame associated with the each of the plurality of frames, the each of the plurality of frame rates being inversely proportional to an time interval between the each of the plurality of frames and the adjacent frame.

7. A computer implemented method for generating a spatial signature for a frame of a video object with a computer system programmed to perform the method, comprising:

obtaining, by the computer system, a frame associated with a video object;

dividing, by the computer system, the frame into a plurality of blocks, the plurality of blocks corresponding to a plurality of locations respectively, each of the plurality of blocks including a plurality of pixels, the plurality of pixels corresponding to a plurality of pixel values respectively;

determining, by the computer system, a plurality of average pixel values for the plurality of blocks respectively;

processing, by the computer system, the plurality of average pixel values;

determining, by the computer system, a plurality of ranks for the plurality of blocks respectively based on at least information associated with the plurality of average pixel values, each of the plurality of ranks corresponding to a block;

processing, by the computer system, information associated with the plurality of ranks;

determining, by the computer system, a sequence of ranks based on at least information associated with the plurality of ranks and the plurality of locations; and

storing a spatial signature for the frame in a data storage separate from the video object, wherein the spatial signature for the frame includes information associated with the sequence of ranks, and wherein the frame of the video object is not modified by the spatial signature.

8. The method of claim 7 wherein the determining a sequence of ranks comprises:

scanning, by the computer system, the plurality of blocks based on a predetermined pattern;

determining, by the computer system, a sequence of blocks as a result of the scanning process; and

arranging, by the computer system, the each of the plurality of ranks based on a location of the corresponding block in the sequence of blocks.

9. The method of claim 8 wherein the predetermined pattern is associated with a raster scan.

10. The method of claim 7 wherein the plurality of ranks is a plurality of ordinal ranks.

11. The method of claim 7 wherein:

the dividing the frame into a plurality of blocks includes dividing, by the computer system, the frame into a number of columns and a number of rows;

wherein the spatial signature for the frame corresponds to a resolution represented by, at least, the number of columns and the number of rows.

12. The method of claim 11 wherein the resolution is a base resolution, and the spatial signature is a based spatial signature.

13. A computer implemented method for generating a temporal signature for a frame of a video object that is performed by a computer system programmed to perform the method, comprising:

obtaining, by the computer system, a first plurality of frames associated with a video object, the first plurality of frames including at least a frame, each of the first plurality of frames including a first plurality of pixels and corresponding to an adjacent frame, the adjacent frame including a second plurality of pixels;

processing, by the computer system, information associated with the first plurality of frames;

determining, by the computer system, a plurality of difference values for the first plurality of frames respectively, each of the plurality of difference values corresponding to the each of the first plurality of frames and the adjacent frame;

processing, by the computer system, information associated with the plurality of difference values;

determining, by the computer system, a plurality of ranks corresponding to the first plurality of frames respectively based on at least information associated with the plurality of difference values, the plurality of ranks including a rank corresponding to the frame, the rank being a temporal signature for the frame; and

storing, by the computer system, the temporal signature for the frame in a data store separate from the video object, wherein the first plurality of frames associated with the video object are not modified by the temporal signature.

14. The method of claim 13, and further comprising:

obtaining, by the computer system, a second plurality of frames;

processing, by the computer system, information associated with the second plurality of frames; and

determining, by the computer system, the first plurality of frames based on at least information associated with the second plurality of frames.

15. The method of claim 14 wherein the determining the first plurality of frames comprises:

receiving, by the computer system, information associated with a time period including a start time and an end time;

placing, by the computer system, the frame at the start time of the time period; and

selecting, by the computer system, at least some frames from the second plurality of frames within the time period, the first plurality of frames including the selected frames.

16. The method of claim 13 wherein the determining a plurality of difference values comprises:

for the each of the first plurality of frames,

determining, by the computer system, magnitudes of differences between first values for the first plurality of pixels and second values for the second plurality of pixels respectively;

summing, by the computer system, the magnitudes of differences to determine one of the plurality of difference values.

17. The method of claim 13 wherein the plurality of ranks is a plurality of ordinal ranks.

18. The method of claim 13 wherein:

the first plurality of frames corresponds to a first frame rate, the rank being the temporal signature for the frame corresponding to the first frame rate.

19. The method of claim 18, wherein

the video object corresponds to a second frame rate;

wherein if the first frame rate is lower than the second frame rate, the first plurality of frames are down-sampled frames for the video object.

20. A computer implemented method for generating a spatial-temporal signature for a frame of a video object with a computer system programmed to perform the method, comprising:

obtaining, by the computer system, a first plurality of frames associated with a video object, the first plurality of frames including at least a frame, each of the first plurality of frames corresponding to an adjacent frame;

dividing, by the computer system, each of the first plurality of frames, wherein the divided frame includes a first plurality of blocks corresponding to a plurality of locations respectively, each of the first plurality of blocks corresponding to a second plurality of blocks including the each of the first plurality of blocks, the second plurality of blocks being associated with blocks on the first plurality of frames respectively;

processing, by the computer system, information associated with the first plurality of frames;

for each of the first plurality of blocks,

determining, by the computer system, a plurality of difference values for the second plurality of blocks respectively, each of the plurality of difference values being associated with the each of the second plurality of blocks and a corresponding block on the adjacent frame;

processing, by the computer system, information associated with the plurality of difference values;

determining, by the computer system, a first plurality of ranks corresponding to the second plurality of blocks respectively based on at least information associated with the plurality of difference values;

processing, by the computer system, information associated with the first plurality of ranks;

determining, by the computer system, a rank for the each of the first plurality of blocks based on at least information associated with the first plurality of ranks;

processing, by the computer system, information associated with a second plurality of ranks corresponding to the first plurality of blocks respectively, the second plurality of ranks including the rank;

determining, by the computer system, a sequence of ranks based on at least information associated with the second plurality of ranks and the plurality of locations for the first plurality of blocks; and

storing, by the computer system, a spatial-temporal signature for the frame independent of the video object, wherein the spatial-temporal signature for the frame includes information associated with the sequence of ranks, and wherein the first plurality of frames associated with the video object are not modified by the spatial-temporal signature.

21. The method of claim 20 wherein the first plurality of blocks are on a same frame at a same instant in time.

22. The method of claim 20 wherein the second plurality of blocks are at a same location on different frames respectively along a temporal axis.

23. The method of claim 20 wherein the determining a sequence of ranks comprises:

scanning, by the computer system, the first plurality of blocks based on a predetermined pattern;

determining, by the computer system, a sequence of blocks on the frame as a result of the scanning process; and

arranging, by the computer system, the each of the second plurality of ranks based on a location of the corresponding block in the sequence of blocks.

24. The method of claim 20 wherein:

the first plurality of frames corresponds to a first frame rate, the spatial-temporal signature for the frame corresponding to the first frame rate.

25. The method of claim 24, wherein

the video object corresponds to a second frame rate;

if the first frame rate is lower than the second frame rate, the first plurality of frames are down-sampled frames for the video object.

26. The method of claim 20, and further comprising:

obtaining, by the computer system, a second plurality of frames;

processing, by the computer system, information associated with the second plurality of frames;

determining, by the computer system, the first plurality of frames based on at least information associated with the second plurality of frames.

27. The method of claim 26 wherein the determining the first plurality of frames comprises:

receiving, by the computer system, information associated with a time period including a start time and an end time;

placing, by the computer system, the frame at the start time of the time period; and

selecting, by the computer system, at least some frames from the second plurality of frames within the time period, the first plurality of frames including the selected frames.

28. A non-transitory computer readable medium including instructions that programs a processor of a computer system to generate a fingerprint for a video object, the non-transitory computer readable medium comprising:

one or more instructions that programs the processor to obtain a plurality of frames associated with a video object;

one or more instructions for each of the plurality of frames,

that programs the processor to process information associated with the plurality of frames;

that programs the processor to determine a plurality of spatial signatures for the each of the plurality of frames based on at least information associated with the each of the plurality of frames, the plurality of spatial signatures corresponding to a plurality of resolutions respectively;

that programs the processor to determine a plurality of temporal signatures for the each of the plurality of frames based on at least information associated with the plurality of frames, the plurality of temporal signatures corresponding to a plurality of frame rates respectively;

that programs the processor to process information associated with the plurality of spatial signatures and the plurality of temporal signatures;

that programs the processor to determine a frame fingerprint for the each of the plurality of frames, the frame fingerprint including the plurality of spatial signatures corresponding to the plurality of resolutions respectively and the plurality of temporal signatures corresponding to the plurality of frame rates respectively;

one or more instructions that programs the processor to process a plurality of frame fingerprints for the plurality of frames respectively, the plurality of frame fingerprints including the frame fingerprint for the each of the plurality of frames;

one or more instructions that programs the processor to determine a video fingerprint for the video object, the video fingerprint including the plurality of frame fingerprints; and

one or more instructions that programs to processor to store the video fingerprint for the video object in a memory storage separately from the video object, wherein the plurality of frames associated with the video object are not modified.

29. A non-transitory computer readable medium including instructions that programs a processor of a computer system to generate a spatial signature for a frame of a video object, the non-transitory computer readable medium comprising:

one or more instructions that programs the processor to obtain a frame associated with a video object;

one or more instructions that programs the processor to divide the frame into a plurality of blocks, the plurality of blocks corresponding to a plurality of locations respectively, each of the plurality of blocks including a plurality of pixels, the plurality of pixels corresponding to a plurality of pixel values respectively;

one or more instructions that programs the processor to determine a plurality of average pixel values for the plurality of blocks respectively;

one or more instructions that programs the processor to process the plurality of average pixel values;

one or more instructions that programs the processor to determine a plurality of ranks for the plurality of blocks respectively based on at least information associated with the plurality of average pixel values, each of the plurality of ranks corresponding to a block;

one or more instructions that programs the processor to process information associated with the plurality of ranks;

one or more instructions that programs the processor to determine a sequence of ranks based on at least information associated with the plurality of ranks and the plurality of locations; and

one or more instructions that programs the processor to store a spatial signature for the frame in a memory separately from the video object, wherein the spatial signature for the frame includes information associated with the sequence of ranks, wherein the frame associated with the video object is not modified by the spatial signature.

30. A non-transitory computer readable medium including instructions that programs a processor of a computer system to generate a temporal signature for a frame of a video object, the non-transitory computer readable medium comprising:

one or more instructions that programs the processor to obtain a first plurality of frames associated with a video object, the first plurality of frames including at least a frame, each of the first plurality of frames including a first plurality of pixels and corresponding to an adjacent frame, the adjacent frame including a second plurality of pixels;

one or more instructions that programs the processor to process information associated with the first plurality of frames;

one or more instructions that programs the processor to determine a plurality of difference values for the first plurality of frames respectively, each of the plurality of difference values corresponding to the each of the first plurality of frames and the adjacent frame;

one or more instructions that programs the processor to process information associated with the plurality of difference values;

one or more instructions that programs the processor to determine a plurality of ranks corresponding to the first plurality of frames respectively based on at least information associated with the plurality of difference values, the plurality of ranks including a rank corresponding to the frame, the rank being a temporal signature for the frame; and

one or more instructions that programs the processor to store the temporal signature for the frame in a fingerprint database separate from the video object, wherein the video object is not modified by the temporal signature.

31. A non-transitory computer readable medium including instructions that programs a processor a computer system to generate a spatial-temporal signature for a frame of a video object, the non-transitory computer readable medium comprising:

one or more instructions that programs the processor to obtain a first plurality of frames associated with a video object, the first plurality of frames including at least a frame, each of the first plurality of frames corresponding to an adjacent frame;

one or more instructions that programs the processor to dividing each of the first plurality of frames, wherein the divided frame includes a first plurality of blocks corresponding to a plurality of locations respectively, each of the first plurality of blocks corresponding to a second plurality of blocks including the each of the first plurality of blocks, the second plurality of blocks being associated with blocks on the first plurality of frames respectively;

one or more instructions that programs the processor to process information associated with the first plurality of frames;

one or more instructions, for each of the first plurality of blocks,

that programs the processor to determine a plurality of difference values for the second plurality of blocks respectively, each of the plurality of difference values being associated with the each of the second plurality of blocks and a corresponding block on the adjacent frame;

that programs the processor to process information associated with the plurality of difference values;

that programs the processor to determine a first plurality of ranks corresponding to the second plurality of blocks respectively based on at least information associated with the plurality of difference values;

that programs the processor to process information associated with the first plurality of ranks;

that programs the processor to determine a rank for the each of the first plurality of blocks based on at least information associated with the first plurality of ranks;

one or more instructions for processing information associated with a second plurality of ranks corresponding to the first plurality of blocks respectively, the second plurality of ranks including the rank;

one or more instructions that programs the processor to determine a sequence of ranks based on at least information associated with the second plurality of ranks and the plurality of locations for the first plurality of blocks; and

one or more instructions that programs the processor to store the spatial-temporal signature for the frame in a fingerprint database separate from the video object, wherein the spatial-temporal signature for the frame includes information associated with the sequence of ranks, and wherein the video object is not modified by the spatial-temporal signature.