Method and apparatus for detecting near duplicate videos using perceptual video signatures

• US 8,587,668 B2
• Filed: 07/27/2009
• Issued: 11/19/2013
• Est. Priority Date: 07/25/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Anvato, Inc. (Alphabet Inc.)
• Inventors: Haritaoglu, Ismail
• Primary Examiner(s): Abdi, Amara
• Application Number:
  US13/055,786
• Publication Number:
  US 20110122255A1
• Time in Patent Office: 1,576 Days
• Field of Search: 382/103, 382/170, 382/107, 348/180, 348/E17.001, 700/94, 707/E17.022
• US Class Current: 348/180
• CPC Class Codes: G06F 16/7834 using audio features
• CPC Class Codes: G06F 16/7837 using objects detected or recognised in the video content
• CPC Class Codes: G06F 16/785 using colour or luminescence
• CPC Class Codes: G06F 16/786 using motion, e.g. object motion or camera motion
• 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 5/913 for scrambling ; for copy protection

Abstract

Methods and apparatus for detection and identification of duplicate or near-duplicate videos using a perceptual video signature are disclosed. The disclosed apparatus and methods (i) extract perceptual video features, (ii) identify unique and distinguishing perceptual features to generate a perceptual video signature, (iii) compute a perceptual video similarity measure based on the video edit distance, and (iv) search and detect duplicate and near-duplicate videos. A complete framework to detect unauthorized copying of videos on the Internet using the disclosed perceptual video signature is disclosed.

Claims

1. A method of identifying a video signal comprising the steps of:

receiving a first video signal at a processing device from an input device operably connected to the processing device;

executing the following steps on a processing device;

extracting at least one perceptual feature from a plurality of frames of the first video signal;

assigning a weighting value to each perceptual feature;

selecting at least a portion of the perceptual features according to the weighting value;

extracting at least one additional feature from the plurality of frames of the first video signal;

creating a digital fingerprint from the selected perceptual features and from the at least one additional feature;

creating a first digital signature from a plurality of the digital fingerprints;

storing the first digital signature which identifies the video signal according to the sorted perceptual features in a database;

assigning a cost value to a plurality of edit operations;

comparing the first digital signature to a second digital signature to identify each edit operation required to transform the first digital signature to the second digital signature;

adding a total cost of from the cost value for each of the edit operations; and

comparing the total cost of the edit operations against a predetermined level to determine whether the first and the second digital signatures identify a near-duplicate video signal.

2. The method of identifying a video signal of claim 1 wherein the processing device executes the additional step of normalizing a height and a width of the first video signal prior to extracting the perceptual feature.

3. The method of identifying a video signal of claim 1 wherein the first video signal includes a visual and an audio component and the perceptual feature is extracted from either the visual or audio component.

4. The method of identifying a video signal of claim 1 wherein the processing device executes the additional steps of:

detecting a set of perceptual features in a first frame;

detecting a change in the set of perceptual features in a second frame;

determining a time marker at which the change in the set of perceptual features occurred; and

including the time marker of the change in the digital fingerprint.

5. The method of identifying a video signal of claim 4 wherein the time marker is normalized with respect to a length of the first video signal.

6. The method of identifying a video signal of claim 1 wherein the digital fingerprint is generated using a first frame and a second frame separated by about 1 second.

7. The method of identifying a video signal of claim 1 wherein the processing device executes the additional step of concatenating multiple digital fingerprints to create the first digital signature wherein the digital fingerprints are stored in the database as a part of the digital signature.

9. The method of identifying a video signal of claim 1 wherein each perceptual feature is one of a motion and a color and each additional feature is one of a scene change and an object displayed in the first video signal and wherein the processing device executes the additional steps of:

selecting a color space prior to extracting the perceptual feature,

identifying at least one desired color according to a color histogram; and

segmenting the frame into a plurality of regions according to each desired color;

wherein the weighting value is the color histogram identifying the colors in the frame and wherein the color and a centroid and a size of each selected region are included in the digital fingerprint.

10. The method for identifying a video signal of claim 1 wherein each perceptual feature is one of a motion and a color and each additional feature is one of a scene change and an object displayed in the first video signal and wherein the digital fingerprint includes a first and a second motion, a first and a second color, and a first time-normalization marker.

8. A method of identifying a video signal comprising the steps of:

receiving a video signal at a processing device from an input device operably connected to the processing device;

executing the following steps on a processing device;

extracting at least one perceptual feature from a plurality of frames of the video signal;

assigning a weighting value to each perceptual feature;

selecting at least a portion of the perceptual features according to the weighting value, wherein each perceptual feature is one of a motion and a color;

extracting at least one additional feature from the plurality of frames of the video signal, wherein each additional feature is one of a scene change and an object displayed in the video signal;

creating a digital fingerprint from the selected perceptual features and from the at least one additional feature;

storing the digital fingerprint which identifies the video signal according to the sorted perceptual features in a database;

segmenting the frames into a plurality of regions prior to extracting the perceptual feature;

selecting at least one region to include in the digital fingerprint according to a magnitude of motion energy in the region; and

including the magnitude and a direction of the motion energy and a centroid and a size of each selected region in the digital fingerprint,

wherein the weighting value is the magnitude and the direction of the motion energy identified in each of the regions.

11. The method of identifying a video signal of claim 8 wherein the processing device executes the additional step of normalizing a height and a width of the video signal prior to extracting the perceptual feature.

12. The method of identifying a video signal of claim 8 wherein the processing device executes the additional steps of:

detecting a set of perceptual features in a first frame;

detecting a change in the set of perceptual features in a second frame;

determining a time marker at which the change in the set of perceptual features occurred; and

including the time marker of the change in the digital fingerprint.

13. The method of identifying a video signal of claim 8 wherein the processing device executes the additional step of concatenating multiple digital fingerprints to create a digital signature wherein the digital fingerprints are stored in the database as a part of the digital signature.

14. A system for comparing a first video signal to a second video signal for the purpose of identifying near-duplicate videos comprising:

a processing device that receives the first video signal and that calculates a first perceptual digital signature of the first video signal, the first perceptual digital signature comprising a plurality of perceptual digital fingerprints; and

a database, operably connected to the processing device and storing a plurality of additional perceptual digital signatures, each additional perceptual digital signature comprising a plurality of perceptual digital fingerprints;

wherein the processing device;

divides the first perceptual digital signature into a plurality of segments for comparison to the additional perceptual digital signatures using a video edit distance;

compares the first perceptual digital signature to at least a portion of the additional perceptual digital signatures to identify near-duplicate videos; and

identifies each segment of the first perceptual digital signature as a partial match of the additional digital signature if the video edit distance between at least three fingerprints of the first perceptual digital signature and three fingerprints of the additional perceptual digital signatures is zero.

15. The system of claim 14 further comprising a network connecting the database to the processing device.

16. The system of claim 14 wherein the processing device identifies the first video signal as a near-duplicate of the second video signal if at least three segments of the first perceptual digital signature are a partial match of the additional perceptual digital signature.

17. The system of claim 14 wherein the database includes perceptual digital signatures of at least one copyrighted video and the processing device identifies if the first video signal is infringing the copyrighted video.

18. The method of identifying a video signal of claim 14 wherein the processing device executes the additional step of normalizing a height and a width of the video signal prior to calculating the first perceptual digital signature.