Matching data objects by matching derived fingerprints

• US 20070071330A1
• Filed: 11/08/2004
• Published: 03/29/2007
• Est. Priority Date: 11/18/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: Oostveen, Job, Haitsma, Jaap, Kalker, Antonius Andrianus
• Application Number:
  US10/579,412
• Publication Number:
  US 20070071330A1
• Time in Patent Office: Days
• US Class Current: 382/228
• CPC Class Codes: G06F 16/683 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/783 using metadata automatically derived from the content
• CPC Class Codes: G06F 2218/00 Aspects of pattern recognition specially adapted for signal processing
• 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: G06V 20/48 Matching video sequences
• CPC Class Codes: G10L 25/48 specially adapted for particular use

Abstract

The invention relates to methods and apparatus for matching a query data object with a candidate data object by esetracting and comparing fingerprints of said data objects. In an embodiment of the invention apparatus comprising a fingerprint extraction module (110), a fingerprint matching module (210), a statistical module (120) and an identification module is provided. The fingerprint extraction module (110) receives an information signal forming part of a query object and constructs a query fingerprint. The fingerprint matching module (210) compares the query fingerprint to candidates stored in a database (215) to find at least on potentially best matching candidate. Meanwhile, the statistical module determines a statistical model of the query fingerprint so as to, for instance, determine the statistical distribution of certain information inside the query fingerprint. The threshold determiner (120) is arranged, on the basis of the distribution of the query fingerprint to derive an adaptive threshold distance within which the query fingerprint and a potentially best matching candidate may be declared similar by the identification module (130). By setting a threshold which may depend on statistical data derived from the query and/or candidate fingerprint, an improved false acceptance rate F.A.R. may be achieved.

Claims

1. A method of comparing a query fingerprint to a candidate fingerprint, the method being characterised by comprising:

determining a statistical model of the query fingerprint and/or a candidate fingerprint and, on the basis of the statistical model, deriving a threshold distance within which the query fingerprint and the candidate fingerprint may be declared similar.

3. The method of claim 1, wherein if a candidate fingerprint is found to be separated from the query fingerprint by a distance less than the threshold distance, and the distance between the candidate and the query fingerprint is less than the distance between any other candidate fingerprint and the query fingerprint, then the candidate fingerprint is declared the best matching candidate fingerprint and the candidate object represented by the best matching candidate fingerprint and the query object represented by the query fingerprint are deemed to be the same.

4. The method of claim 1, wherein the statistical model comprises the result of performing an internal correlation on the query fingerprint and/or the candidate fingerprint.

5. The method of claim 4, wherein the fingerprints comprise a plurality of frames containing binary values and the statistical model is computed for the query fingerprint by determining a transition probability q for the query fingerprint by determining how many bits of a frame of the query fingerprint F(m,k) are different from their corresponding bit in their preceding fingerprint frame F(m,k−

1) and dividing the number of transitions by a maximum value M*(k−

1), which would be obtained if all fingerprint bits were of an opposite state to their corresponding preceding bit, where each fingerprint comprises M bits per frame and spans K frames, in which k is the frame index (ranging from 0 to K) and m is the bit-index within a frame (ranging from 0 to M).

6. The method of claim 5, wherein the threshold distance T is computed from the following equation based on a desired False Acceptance Rate (FAR):

2. A method of matching a query object to a known object, wherein a plurality of candidate fingerprints representing a plurality of candidate objects are pre-stored in a database, the method comprising receiving an information signal forming part of the query object and constructing a query fingerprint therefrom and comparing the query fingerprint to a candidate fingerprint in the database, the method being characterised by the further steps of:

determining a statistical model for the query fingerprint and/or the candidate fingerprint; and

on the basis of the statistical model, deriving a threshold distance within which the query fingerprint and the candidate fingerprint may be declared similar.

7. Apparatus for matching a query object to a known object, the apparatus comprising a fingerprint extraction module (110) for receiving an information signal forming part of a query object and constructing a query fingerprint therefrom and a fingerprint matching module (210) for comparing the query fingerprint to candidate fingerprints stored in a database (215) to one or more candidate fingerprints, the apparatus being characterised by also comprising:

a statistical module (120) for determining a statistical model of the query fingerprint and/or one or more of the one or more candidate fingerprints;

a threshold determiner (120) deriving, on the basis of the statistical model, a threshold distance T within which the query fingerprint and a potentially best matching candidate fingerprint may be declared similar; and

an identification module (230) arranged such that if a candidate fingerprint is found to be separated from the query fingerprint by a distance less than the threshold distance T, and the distance between the candidate and the query fingerprint is less than the distance between any other candidate fingerprint and the query fingerprint, then the candidate fingerprint is declared the best matching candidate fingerprint and the candidate object represented by the best matching candidate fingerprint and the query object represented by the query fingerprint are deemed to be the same.

8. The apparatus of claim 7, wherein the statistical module (120) performs an internal correlation on the query fingerprint and/or the one or more candidate fingerprints.

9. The method of claim 8, wherein the fingerprints comprise a plurality of frames containing binary values and the statistical module (120) computes the statistical model for the query fingerprint or/and the candidate fingerprint by determining a transition probability q by determining how many bits of a frame of the query fingerprint F(m,k) are different from their corresponding bit in the preceding fingerprint frame F(m,k−

1) and dividing the number of transitions by a maximum value M*(k−

1), which would be obtained if all fingerprint bits were of an opposite state to their corresponding preceding bit, where each fingerprint comprises M bits per frame and spans K frames, in which k is the frame index (ranging from 0 to K) and m is the bit-index within a frame (ranging from 0 to M).

10. The method of claim 9, wherein the threshold determiner (130) computes the threshold distance T from the following equation based on a desired False Acceptance Rate (FAR):