Search and storage of media fingerprints

• US 20070033163A1
• Filed: 05/24/2004
• Published: 02/08/2007
• Est. Priority Date: 05/30/2003
• Status: Abandoned Application

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Epstein, Michael, Krasinski, Raymond
• Application Number:
  US10/557,979
• Publication Number:
  US 20070033163A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/43 Querying
• CPC Class Codes: G06V 20/48 Matching video sequences

Abstract

Recognizing that a variety of different fingerprints may correspond to the same dataset, the search of a database of fingerprints to find a match to a target fingerprint is performed with relaxed criteria for declaring a match between two fingerprints. By matching “similar”, but not “exact”, fingerprints, redundant fingerprints need not be stored for each dataset. When a new fingerprint is found, a first-in first-out (FIFO) strategy is used to allocate space in a limited memory-space to store the new entry.

Claims

1. A system for searching a plurality of fingerprints for a select fingerprint that corresponds to a target fingerprint, comprising:

a comparator that is configured to compare a given fingerprint to the target fingerprint, and to identify the given fingerprint as the select fingerprint when a match is determined, and,

a sequencer that provides the given fingerprint from the plurality of fingerprints to the comparator,

wherein

the comparator is configured to determine the match based on a quantitative measure associated with differences between the given fingerprint and the target fingerprint, such that the match can be determined when one or more differences exist between the given fingerprint and the target fingerprint.

2. The system of claim 1, wherein

the quantitative measure is dependent upon a count of the differences between the given fingerprint and the target fingerprint.

3. The system of claim 1, wherein

the comparator is configured to determine the match by comparing the quantitative measure to a threshold value.

4. The system of claim 3, wherein

the system is further configured to dynamically adjust the threshold value based on prior determinations of matches.

5. The system of claim 1, wherein

the comparator includes

a difference determinator that is configured to identify the differences between the given fingerprint and the target fingerprint;

and

a quantifier, operably coupled to the difference determinator, that is configured to determine the quantitative measure based on the identified differences.

6. The system of claim 5, wherein

the difference determinator includes an exclusive-or function.

7. The system of claim 6, wherein

the quantifier includes

a lookup table that provides a quantity value based on the identified differences, and

the quantifier determines the quantitative measure based on the quantity value.

8. The system of claim 5, wherein

the quantifier includes

a lookup table that provides a quantity value based on the identified differences, and

the quantifier determines the quantitative measure based on the quantity value.

9. The system of claim 1, further including

a memory controller that is configured to store the target fingerprint as one of the plurality of fingerprints when the match is not determined.

10. The system of claim 9, wherein

the memory controller is configured to use a first-in first-out strategy to store the target fingerprint in a memory.

11. A system for searching a plurality of fingerprints for a select fingerprint that corresponds to a target fingerprint, comprising:

a comparator that is configured to compare a given fingerprint to the target fingerprint, and to identify the given fingerprint as the select fingerprint when a match is determined,

a sequencer that provides the given fingerprint from the plurality of fingerprints to the comparator,

a memory that is configured to contain the plurality of fingerprints, and

a memory controller that is configured to store the target fingerprint as one of the plurality of fingerprints in the memory when the match is not determined, using a first-in first-out (FIFO) strategy.

12. The system of claim 11, wherein

the plurality of fingerprints are stored in the memory in a sorted order.

13. The system of claim 12, wherein

the comparator is configured to determine the match when a number of differences between the given fingerprint and the target fingerprint is less than a threshold value that is greater than one, thereby allowing the match to be determined when one or more differences exist between the given fingerprint and the target fingerprint.

14. A method of searching a plurality of fingerprints for a matching fingerprint that corresponds to a target fingerprint, comprising:

selectively comparing a given fingerprint from the plurality of fingerprints to the target fingerprint to determine whether the given fingerprint is the matching fingerprint,

wherein

the given fingerprint is determined to be the matching fingerprint when a number of differences between the given fingerprint and the target fingerprint is less than a threshold value that is greater than one,

thereby allowing the given fingerprint to be determined to be the matching fingerprint when one or more differences exist between the given fingerprint and the target fingerprint.

15. The method of claim 14, wherein

comparing the given fingerprint to the target fingerprint includes:

identifying differences between the given fingerprint and the target fingerprint, and

quantifying the number of difference based on the identified differences.

16. The method of claim 15, wherein

identifying the differences includes effecting an exclusive-or of the given fingerprint and the target fingerprint.

17. The method of claim 16, wherein

quantifying the number of differences includes accessing a lookup table to obtain a quantity value based on the identified differences.

18. The method of claim 17, wherein

quantifying the number of differences includes accessing a lookup table to obtain a quantity value based on the identified differences.

19. The method of claim 14, further including

storing the target fingerprint as one of the plurality of fingerprints when the matching fingerprint is not found in the plurality of fingerprints.

20. The method of claim 19, wherein

storing the target fingerprint includes applying a first-in first-out strategy to store the target fingerprint in a limited-size memory.