Detection And Classification Of Matches Between Time-Based Media

• US 20090052784A1
• Filed: 07/16/2008
• Published: 02/26/2009
• Est. Priority Date: 08/22/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Faust, Jeff, Baluja, Shumeet, Yagnik, Jay, Covell, Michele
• Granted Patent: US 8,238,669 B2
• Time in Patent Office: Days
• US Class Current: 382/209
• CPC Class Codes: G06F 16/783 using metadata automatically derived from the content
• CPC Class Codes: G06V 20/48 Matching video sequences

Abstract

A system and method detects matches between portions of video content. A matching module receives an input video fingerprint representing an input video and a set of reference fingerprints representing reference videos in a reference database. The matching module compares the reference fingerprints and input fingerprints to generate a list of candidate segments from the reference video set. Each candidate segment comprises a time-localized portion of a reference video that potentially matches the input video. A classifier is applied to each of the candidate segments to classify the segment as a matching segment or a non-matching segment. A result is then outputted identifying a matching portion of a reference video from the reference video set based on the segments classified as matches.

Claims

1. A computer-implemented method for detecting duplicate video content, the method comprising:

receiving an input fingerprint representing an input video;

generating a list of candidate segments from a reference video set, the list of candidate segments comprising time-localized segments of reference videos in the reference video set;

classifying candidate segments from the list of candidate segments as either a matching candidate segment or a non-matching candidate segment using a classifier; and

producing a result identifying a matching portion of a reference video from the reference video set based on the classification of the candidate segments.

2. The method of claim 1, wherein generating the list of candidate segments from the reference video set comprises:

obtaining reference fingerprints representing the reference videos in the reference video set;

identifying partial matches between the input fingerprint and the reference fingerprints; and

determining a set of initial candidate reference videos based on the identified partial matches.

3. The method of claim 2, further comprising:

obtaining a set of input sub-fingerprints for the input fingerprint, wherein each input sub-fingerprint comprises a sequence of input sub-fingerprint keys;

obtaining sets of reference sub-fingerprints for the reference videos, wherein each reference sub-fingerprint comprises a sequence of reference sub-fingerprint keys;

and

determining the set of initial candidate reference videos based on matches between the reference sub-fingerprint keys and the input sub-fingerprint keys.

4. The method of claim 2, further comprising:

determining a figure of merit for each reference video based time-localized matches between the reference videos and the input video; and

determining the set of initial candidate reference videos based on the figure of merit.

5. The method of claim 2, further comprising:

sorting reference sub-fingerprints representing the reference videos in a sort order from most discriminative to least discriminative; and

determining the candidate segments based at least in part on the sort order of the reference sub-fingerprints.

6. The method of claim 2, further comprising:

sorting reference keys of reference sub-fingerprints representing a reference video in a sort order from most discriminative to least discriminative; and

determining the candidate segments based at least in part on the sort order of the reference keys.

7. The method of claim 2, further comprising:

determining temporally consecutive matches between input video sub-fingerprints representing the input video and reference video sub-fingerprints representing a reference video; and

determining the list of candidate segments based on the temporally consecutive matches.

8. The method of claim 1, wherein classifying the candidate segments comprises:

determining a quality measure indicating a match quality between the reference video and the candidate segment based on a known matching model; and

classifying the candidate segment as a matching segment or a non-matching segment based on the quality measure.

9. The method of claim 1, further comprising:

receiving an input key representing a portion of values from the input fingerprint; and

querying a reverse index table to obtain one or more sub-fingerprint identifiers identifying a time-localized segment of a reference video from the reference video set having a key matching the input key.

10. The method of claim 9, wherein the input key comprises adjacent values from an input sub-fingerprint.

11. The method of claim 9, wherein the input key comprises non-adjacent values from an input sub-fingerprint.

12. The method of claim 9, wherein the reverse index table stores a first level blacklist identifier code in association with a first reference key responsive to more than a predefined percentage of reference sub-fingerprints representing the reference videos containing the first reference key.

13. The method of claim 9, wherein the reverse index table stores a second level blacklist identifier code in association with a first reference key responsive to more than a predefined number of reference sub-fingerprints representing the reference videos containing the first reference key.

14. The method of claim 1, wherein generating the list of candidate segments comprises:

determining premium reference videos from the set of reference videos labeled as having premium content; and

generating the list of candidate segments based on the determination of the premium reference videos.

28. The computer readable storage medium of claim 13, wherein generating the list of candidate segments comprises:

determining premium reference videos from the set of reference videos labeled as having premium content; and

generating the list of candidate segments based on the determination of the premium reference videos.

15. A computer readable storage medium storing computer executable code for detecting duplicate video content, the computer executable program code when executed cause an application to perform steps of:

receiving an input fingerprint representing an input video;

generating a list of candidate segments from a reference video set, the list of candidate segments comprising time-localized segments of reference videos in the reference video set;

classifying candidate segments from the list of candidate segments as either a matching candidate segment or a non-matching candidate segment using a classifier; and

producing a result identifying a matching portion of a reference video from the reference video set based on the the classification of the candidate segments.

16. The computer readable storage medium of claim 15, wherein generating the list of candidate segments from the reference video set comprises:

obtaining reference fingerprints representing the reference videos in the reference video set;

identifying partial matches between the input fingerprint and the reference fingerprints; and

determining a set of initial candidate reference videos based on the identified partial matches.

17. The computer readable storage medium of claim 16, further comprising:

obtaining a set of input sub-fingerprints for the input fingerprint, wherein each input sub-fingerprint comprises a sequence of input sub-fingerprint keys;

obtaining sets of reference sub-fingerprints for the reference videos, wherein each reference sub-fingerprint comprises a sequence of reference sub-fingerprint keys; and

determining the set of initial candidate reference videos based on matches between the reference sub-fingerprint keys and the input sub-fingerprint keys.

18. The computer readable storage medium of claim 16, further comprising:

determining a figure of merit for each reference video based time-localized matches between the reference videos and the input video; and

determining the set of initial candidate reference videos based on the figure of merit.

19. The computer readable storage medium of claim 16, further comprising:

sorting reference sub-fingerprints representing the reference videos in a sort order from most discriminative to least discriminative; and

determining the candidate segments based at least in part on the sort order of the reference sub-fingerprints.

20. The computer readable storage medium of claim 16, further comprising:

sorting reference keys of a reference sub-fingerprints representing a reference video in a sort order from most discriminative to least discriminative; and

determining the candidate segments based at least in part on the sort order of the reference keys.

21. The computer readable storage medium of claim 16, further comprising:

determining temporally consecutive matches between input video sub-fingerprints representing the input video and reference video sub-fingerprints representing a reference video; and

determining the list of candidate segments based on the temporally consecutive matches.

22. The computer readable storage medium of claim 15, wherein classifying the candidate segments comprises:

determining a quality measure indicating a match quality between the reference video and the candidate segment based on a known matching model; and

classifying the candidate segment as a matching segment or a non-matching segment based on the quality measure.

23. The computer readable storage medium of claim 15, further comprising:

receiving an input key representing a portion of values from the input fingerprint; and

querying a reverse index table to obtain one or more sub-fingerprint identifiers identifying a time-localized segment of a reference video from the reference video set having a key matching the input key.

24. The computer readable storage medium of claim 23, wherein the input key comprises adjacent values from an input sub-fingerprint.

25. The computer readable storage medium of claim 23, wherein the input key comprises non-adjacent values from an input sub-fingerprint.

26. The computer readable storage medium of claim 23, wherein the reverse index table stores a first level blacklist identifier code in association with a first reference key responsive to more than a predefined percentage of reference sub-fingerprints representing the reference videos containing the first reference key.

27. The computer readable storage medium of claim 23, wherein the reverse index table stores a second level blacklist identifier code in association with a first reference key responsive to more than a predefined number of reference sub-fingerprints representing the reference videos containing the first reference key.

29. A system for detecting duplicate video content comprising:

An ingest server for receiving an input video;

A fingerprinting module for generating an input fingerprint representing the input video;

a reference database storing reference fingerprints representing a set of reference videos;

a matching module coupled to the fingerprinting module and the reference database, the matching module for generating a list of candidate segments from the set of reference videos based on the input fingerprint, classifying the candidate segments as matching segments or non-matching segments, and producing a result identifying a matching portion of a reference video from the set of reference videos based on the classification of the candidate segments.

30. The system of claim 29, wherein the reference database comprises:

a fingerprint repository for storing the reference fingerprints, wherein each reference fingerprint comprises a sequence of reference sub-fingerprints representing time-localized segments of the reference videos; and

a reverse index table storing a mapping between identifiers of the reference videos and reference keys, wherein the reference keys comprise localized sets of values from the reference sub-fingerprints.

31. The system of claim 30, wherein the reverse index table stores a first level blacklist identifier code in association with a first reference key responsive to more than a predefined percentage of the reference sub-fingerprints containing the first reference key.

32. The system of claim 30, wherein the reverse index table stores a second level blacklist identifier code in association with a first reference key responsive to more than a predefined threshold of the reference sub-fingerprints containing the first reference key.