Efficient storage of fingerprints

• US 20050141707A1
• Filed: 01/21/2003
• Published: 06/30/2005
• Est. Priority Date: 02/05/2002
• Status: Active Grant

• Current Assignee: Gracenote, Inc. (RR Donnelley & Sons Company)
• Original Assignee: Gracenote, Inc. (RR Donnelley & Sons Company)
• Inventors: Haitsma, Jaap Andre, Kalker, Antonius Adrianus Cornelis Maria, Schimmel, Steven Marco
• Granted Patent: US 7,477,739 B2
• Time in Patent Office: Days
• US Class Current: 380/201
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/433 using audio data
• CPC Class Codes: G06F 16/634 Query by example, e.g. query by humming
• CPC Class Codes: G06F 16/683 using metadata automatically derived from the content

Abstract

A robust fingerprinting system is disclosed. Such a system can recognize unknown multimedia content (U(t)) by extracting a fingerprint (a series of hash words) from said content, and searching a resembling fingerprint in a database in which fingerprints of a plurality of known contents (K(t)) are stored. In order to more efficiently store the fingerprints in the database and to speed up the search, the hash words (H(n)) of known signals (K(t)) are sub-sampled (13) by a factor M prior to storage in the database (14). The hash words (H(n)) of unknown signals (U(t)) are divided (16) into M interleaved sub-series (H0(n) . . . HM−1(n)). The interleaved sub-series are selectively (17) applied to the database (14) under the control of a computer (15). If only one of the sub-series sufficiently matches a stored fingerprint, the signal is identified.

Claims

1. A method of storing fingerprints identifying audio-visual media signals in a database, the method comprising, for each audio-visual signal, the steps of:

dividing said audio-visual media signal into a sequence of frames;

sub-sampling said sequence of frames by a factor M to obtain a sub-sampled sequence of frames;

extracting, for each frame of said sub-sampled sequence of frames, a hash word representing a perceptually essential property of the signal within said frame, to obtain a respective sub-sampled sequence of hash words;

storing said sub-sampled sequence of hash words as fingerprint in said database.

2. A method as claimed in claim 1, wherein said successive frames are overlapping.

3. An arrangement for storing fingerprints identifying audio-visual media signals (K(t)) in a database, the arrangement comprising:

framing means (11) for dividing said audio-visual media signals into a sequence of frames;

sub-sampling means (13) for sub-sampling said sequence of frames by a factor M to obtain a sub-sampled sequence of frames;

means (12) for extracting, for each frame of said sub-sampled sequence of frames, a hash word (H(n)) representing a perceptually essential property of the signal within said frame, to obtain a respective sub-sampled sequence of hash words;

a database (14) for storing said sub-sampled sequence of hash words as fingerprint in said database.

5. A method as claimed in claim 3, wherein said successive frames are overlapping.

8. A method as claimed in claim 5, wherein said successive frames are overlapping.

4. A method of identifying an unknown audio-visual media signal, the method comprising the steps of:

dividing at least a part of the unknown audio-visual media signal into a series of frames;

extracting, for each frame, a hash word representing a perceptually essential property of the signal within said frame, to obtain a respective series of hash words;

dividing said series of hash words into M interleaved sub-series of hash words;

successively applying said M sub-series to a database in which, for a plurality of multi-media signals, a sub-sampled sequence of hash words has been stored;

identifying the unknown signal as the multi-media signal of which at least a part of the stored sub-sampled sequence of hash words substantially matches at least one of the M applied sub-series of hash words.

6. An arrangement for identifying an unknown audio-visual media signal, the arrangement comprising:

framing means (11) for dividing at least a part of the unknown audio-visual media signal (U(t)) into a series of frames;

means (12) for extracting, for each frame, a hash word representing a perceptually essential property of the signal within said frame, to obtain a respective series of hash words;

interleaving means (16) for dividing said series of hash words into M interleaved sub-series of hash words;

selection means (17) for successively applying said M sub-series to a database in which for a plurality of multi-media signals, a sub-sampled sequence of hash words has been stored;

computer means (15) for identifying the unknown signal as the multi-media signal of which at least a part of the stored sub-sampled sequence of hash words substantially matches at least one of the M applied sub-series of hash words.

7. A method of identifying an unknown audio-visual media signal, the method comprising the steps of:

receiving, from a remote station, a series of hash words generated by dividing at least a part of the unknown audio-visual media signal into a series of frames, and extracting, for each frame, a hash word representing a perceptually essential property of the signal within said frame;

dividing said series of hash words into M interleaved sub-series of hash words;

successively applying said M. sub-series to a database in which, for a plurality of multi-media signals, a sub-sampled sequence of hash words has been stored;

identifying the unknown signal as the multi-media signal of which at least a part of the stored sub-sampled sequence of hash words substantially matches at least one of the M applied sub-series of hash words.