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

• US 8,830,331 B2
• Filed: 10/16/2013
• Issued: 09/09/2014
• 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:
  US14/054,901
• Publication Number:
  US 20140044355A1
• Time in Patent Office: 328 Days
• Field of Search: 382/103
• 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 for identifying a video signal comprising the steps of:

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

executing the following steps on the processing device;

a) selecting a portion of the video signal;

b) generating at least one histogram corresponding to a frequency of occurrence of a feature in the portion of the video signal;

c) assigning a weighting value to each of the features represented in one of the plurality of histograms;

d) selecting at least a portion of the features according to the weighting value assigned;

e) creating a digital fingerprint for the portion of the video signal from the features selected;

f) repeating steps (a)-(e) to generate a plurality of the digital fingerprints for the video signal;

g) concatenating the plurality of digital fingerprints to generate a digital signature for the video signal; and

h) storing the digital signature in a database.

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

selecting at least one additional feature from the video signal; and

including the additional feature in the digital fingerprint.

3. The method of identifying the video signal of claim 1 wherein the processing device executes the additional step of normalizing a height and a width of the video signal prior to generating the plurality of histograms.

4. The method of identifying the video signal of claim 1 wherein the video signal includes a visual component and an audio component and the feature is extracted from one of the visual component and the audio component.

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

obtaining a plurality of frames from the portion of the video signal;

detecting a set of features in a first frame selected from the plurality of frames;

detecting a change in the set of features in a second frame selected from the plurality of frames;

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

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

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

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

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

assigning a cost value to a plurality of edit operations;

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

adding the cost value of each of the identified edit operations to determine a total cost; and

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

9. The method of identifying the video signal of claim 2 wherein each 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 video signal.

11. The method of identifying the video signal of claim 9 wherein the processing device executes the additional steps of:

selecting a color space prior to generating the plurality of histograms, wherein at least one color histogram is generated as a function of the selected color space;

identifying at least one desired color as a function of the at least one color histogram; and

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

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

12. The method for identifying the video signal of claim 9 wherein the digital fingerprint includes a first motion, a second motion, a first color, a second color, and a time-normalization marker.

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

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

executing the following steps on the processing device;

selecting a portion of the video signal;

obtaining a plurality of frames from the portion of the video signal;

segmenting each of the plurality of frames into a plurality of regions;

generating a plurality of histograms from the plurality of frames, each histogram corresponding to a frequency of occurrence of a feature in the plurality of frames;

assigning a weighting value to each of the features represented in one of the plurality of histograms, wherein the weighting value is a magnitude and a direction of the motion identified in each of the regions;

selecting at least one of the plurality of regions to include in the digital fingerprint according to the motion in the region;

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

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

creating a digital fingerprint from the features selected;

storing the digital fingerprint in a database;

selecting at least one additional feature from the plurality of frames of the video signal; and

including the additional feature in the digital fingerprint, wherein each additional feature is one of a scene change and an object displayed in the video signal.

13. A method for identifying a near duplicate 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;

extracting a first digital signature of the first video signal using the processing device, wherein the first digital signature corresponds to at least one perceptual feature of the first video;

assigning a cost value to each of a plurality of edit operations;

comparing the first digital signature to a second digital signature using the processing device to determine a number of edit operations between the first digital signature and the second digital signature;

adding each of the edit operations to determine a total cost of the edit operations; and

comparing the total cost of the edit operations against a predetermined level to determine whether the second digital signature corresponds to a second video signal that is a near-duplicate of the first video signal.

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

a processing device configured to receive the first video signal, wherein the processing device is configured to;

a) select a portion of the first video signal,

b) generate at least one histogram corresponding to at least one perceptual feature in the portion of the first video signal selected,

c) assign a weighting value to each perceptual feature represented in the histogram,

d) select at least a portion of the perceptual features according to the weighting value assigned,

e) create a digital fingerprint for the portion of the first video signal from the selected features,

f) repeat steps (a)-(e) to generate a plurality of digital fingerprints for the first video signal, and

g) concatenate the plurality of digital fingerprints to generate a first digital signature for the first video signal; and

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

wherein the processing device is further configured to compare the first digital signature to at least a portion of the additional digital signatures to identify near-duplicate video signals.

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 compares the first digital signature to the additional digital signatures using a video edit distance.

17. The system of claim 16 wherein the processing device is further configured to:

compare the digital fingerprints in the first video signal to the digital fingerprints in the additional digital signatures, and

identify the first digital signature as a partial match of one of the additional digital signatures when the video edit distance between at least three digital fingerprints in the first video signal and corresponding digital fingerprints in the additional digital signature is zero.

18. The system of claim 14 wherein the first video signal includes a visual component and an audio component and the perceptual feature is extracted from either the visual component or the audio component.

19. The system of claim 14 wherein the processing device is further configured to:

determine a time marker corresponding to an occurrence of the perceptual feature, and

include the time marker of the occurrence in the digital fingerprint.