Generating and matching hashes of multimedia content

• US 7,921,296 B2
• Filed: 05/07/2007
• Issued: 04/05/2011
• Est. Priority Date: 02/12/2001
• Status: Active Grant

• Current Assignee: Gracenote, Inc. (RR Donnelley & Sons Company)
• Original Assignee: Gracenote, Inc. (RR Donnelley & Sons Company)
• Inventors: Baggen, Constant Paul Marie Jozef, Haitsma, Jaap Andre, Kalker, Antonius Adrianus Cornelis Maria, Oostveen, Job Cornelis
• Primary Examiner(s): Vu; Kimyen
• Assistant Examiner(s): Paliwal; Yogesh
• Application Number:
  US11/800,904
• Publication Number:
  US 20080263360A1
• Time in Patent Office: 1,429 Days
• Field of Search: 713/180
• US Class Current: 713/180
• CPC Class Codes: G06F 16/683 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/7834 using audio features
• CPC Class Codes: G06F 16/785 using colour or luminescence
• CPC Class Codes: G06T 1/0028 Adaptive watermarking, e.g. Human Visual System [HVS]-based watermarking
• CPC Class Codes: G06T 1/005 Robust watermarking, e.g. average attack or collusion attack resistant
• CPC Class Codes: G06T 2201/0051 Embedding of the watermark in the spatial domain
• CPC Class Codes: G06T 2201/0061 Embedding of the watermark in each block of the image, e.g. segmented watermarking
• CPC Class Codes: G06T 2201/0065 Extraction of an embedded watermark; Reliable detection
• 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: G10H 1/0058 Transmission between separate instruments or between individual components of a musical system G10H1/0083 takes precedence
• CPC Class Codes: G10H 2210/295 Spatial effects, musical uses of multiple audio channels, e.g. stereo Helmholtz resonance effects G10H2210/275; reverberation or echo G10H2210/281
• CPC Class Codes: G10H 2240/061 MP3, i.e. MPEG-1 or MPEG-2 Audio Layer III, lossy audio compression
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04H 2201/90 characterised by the use of signatures
• CPC Class Codes: H04H 60/37 for identifying segments of broadcast information, e.g. scenes or extracting programme ID
• CPC Class Codes: H04H 60/56 Arrangements characterised by components specially adapted for monitoring, identification or recognition covered by groups H04H60/29-H04H60/54
• CPC Class Codes: H04N 19/467 characterised by the embedded information being invisible, e.g. watermarking

Abstract

Hashes are short summaries or signatures of data files which can be used to identify the file. The disclosed method generates robust hashes for multimedia content, for example, audio clips. The audio clip is divided into successive (preferably overlapping) frames. For each frame, the frequency spectrum is divided into bands. A robust property of each band (e.g. energy) is computed and represented by a respective hash bit. An audio clip is thus represented by a concatenation of binary hash words, one for each frame. To identify a possibly compressed audio signal, a block of hash words derived therefrom is matched by a computer with a large database. Such matching strategies are also disclosed. In an advantageous embodiment, the extraction process also provides information as to which of the hash bits are the least reliable. Flipping these bits considerably improves the speed and performance of the matching process.

Claims

1. A method to identify multimedia content, the method comprising:

receiving an input block of hash words, the input block representing at least a part of an information signal;

interrogating a look-up table with a selected hash word from the input block to obtain a found hash word;

comparing, by a computer, the input block and a stored block of hash words in which the found hash word has the same position as the selected hash word;

selectively identifying the stored block of hash words as a matching reference signal based on the outcome of the comparing;

wherein the selected hash word comprises a plurality of reliable hash bits and unreliable hash bits; and

the interrogating comprises interrogating the look-up table with reliable bits of the selected hash word.

2. The method of claim 1, further comprising selecting a further hash word in response to determining that the difference between the input block and the stored block is greater than a predetermined threshold.

3. The method of claim 2, wherein the selecting of the further hash word comprises reversing an unreliable bit from the selected hash word.

4. The method of claim 3, wherein the selecting of the further hash word comprises:

receiving information indicative of reliability of a bit of the selected hash word; and

using said the information to determine the unreliable bit.

5. The method of claim 1, wherein the selectively identifying of the stored block of hash words as a matching reference signal comprises:

calculating a bit error rate between bits of the input block and corresponding bits of the stored block; and

identifying the stored block of hash words as the matching reference signal based on the calculated bit error rate.

6. The method of claim 1, further comprising returning an identification associated with the stored block.

7. A method to identify subject content, the method comprising:

receiving a hash value associated with an information signal, the hash value comprising one or more reliable hash bits and one or more unreliable hash bits;

interrogating a look up table with the one or more reliable bits to determine one or more matching stored hash values;

for each of the one or more matching stored hash values, calculating, by a computer, a bit error rate, the bit error rate representing a relationship between the one or more bits of the hash value and the corresponding bits of a matching stored hash value from the one or more matching stored hash values;

selecting a matching stored hash value from the one or more matching stored hash values, for which the bit error rate is minimal; and

identifying the matching stored hash value, for which the bit error rate is minimal, as the matching stored hash value associated with the subject content.

8. The method of claim 7, wherein the subject content is audio content.

9. The method of claim 7, wherein the subject content is video content.