Generating and matching hashes of multimedia content

• US 20080263360A1
• Filed: 05/07/2007
• Published: 10/23/2008
• Est. Priority Date: 02/12/2001
• Status: Active Grant

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.), Gracenote, Inc. (RR Donnelley & Sons Company)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.), Gracenote, Inc. (RR Donnelley & Sons Company)
• Inventors: Oostveen, Job Cornelis, Haitsma, Jaap Andre, Maria Kalker, Antonius Andrianus Cornelis, Jozef Baggen, Constant Paul Marie
• Granted Patent: US 7,921,296 B2
• Time in Patent Office: Days
• 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. Hashing multimedia content (audio, video, images) is difficult because the hash of original content and processed (e.g. compressed) content may differ significantly. The disclosed method generates robust hashes for multimedia content, for example, audio clips. The audio clip is divided (12) into successive (preferably overlapping) frames. For each frame, the frequency spectrum is divided (15) into bands. A robust property of each band (e.g. energy) is computed (16) and represented (17) 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 (20) with a large database (21). Such matching strategies are also disclosed. In an advantageous embodiment, the extraction process also provides information (19) 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 content in an information signal, the method comprising:

dividing the information signal into frames;

dividing each frame of the information signal into disjoint bands;

calculating a property of the information signal in each of said bands to compute a hash word for each frame;

generating a hash signal by concatenating successive hash words; and

obtaining a match of the information signal with a known content item, based on the hash signal.

2. The method of claim 1, wherein the computing of a hash word for a frame comprises:

comparing properties in the bands associated with the frame with respective thresholds; and

representing the results of said comparisons by respective bits of the hash word.

3. The method of claim 2, wherein the threshold comprises a property of a neighboring band.

4. The method of claim 2, wherein the threshold comprises a property of a corresponding band in a previous frame.

5. The method of claim 1, wherein the bands are frequency bands of the frequency spectrum of the respective frame of the information signal.

6. The method of claim 5, wherein the frequency bands have an increasing bandwidth as a function of the frequency.

7. The method of claim 5, wherein the property of the information signal is the energy of a frequency band.

8. The method of claim 5, wherein the property of the information signal is the tonality of a frequency band.

9. The method of claim 1, wherein the dividing of the information signal into frames comprises dividing the information signal into overlapping frames.

10. The method of claim 1, wherein:

the information signal is a video signal;

the dividing of each frame of the information signal into disjoint bands comprises dividing each frame of the information signal into blocks; and

the property of the information signal is the mean luminance of a block.

11. The method of claim 1, further comprising generating information indicative of reliability of a bit in the hash word, based on the results of comparing of the properties in the bands associated with the frame with respective thresholds.

12. A method to identify content in an information signal, the method comprising:

dividing the information signal into blocks;

extracting for each block a feature of the information signal within a block;

comparing the value of the extracted feature with a threshold;

generating for each block a hash bit based on the outcome of the comparing;

determining for each hash bit reliability information based on the difference between a value associated with the extracted feature and the threshold; and

combining hash bits generated for the blocks and the reliability information for each hash bit into a hash value, the hash value having reliable hash bits and unreliable hash bits.

13. The method of claim 12, wherein the information signal is an audio signal.

14. 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 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; and

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

15. The method of claim 14, 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.

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

17. The method of claim 16, 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.

18. 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 a bit error rate, the bit error rate representing a relationship between the one or more reliable bits 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.

19. The method of claim 18, wherein the subject content is audio content.

20. The method of claim 18, wherein the subject content is video content.

21. A machine-readable medium embodying instructions which, when executed by a machine, cause the machine to:

divide the information signal into frames;

divide each frame of the information signal into disjoint bands;

calculate a property of the information signal in each of said bands to compute a hash word for each frame;

generate a hash signal by concatenating successive hash words; and

obtain a match of the information signal with a known content item based on the hash signal.

22. An apparatus to identify content in an information signal, the method comprising:

a framing circuit to divide the information signal into frames;

a band division circuit to divide each frame of the information signal into disjoint bands;

a computing circuit to determine a property of the information signal in each of said bands to compute a hash word for each frame;

a hash signal generator to generate a hash signal by concatenating successive hash words; and

a matching circuit to obtain a match of the information signal with a known content item, based on the hash signal.

23. The apparatus of claim 22, wherein the computing circuit is to:

compare properties in the bands associated with the frame with respective thresholds; and

represent the results of said comparisons by respective bits of the hash word.

24. The apparatus of claim 22, wherein the bands are frequency bands of the frequency spectrum of the respective frame of the information signal.

25. The apparatus of claim 22, wherein the dividing of the information signal into frames comprises dividing the information signal into overlapping frames.

26. The apparatus of claim 22, wherein:

the information signal is a video signal;

the band division circuit is to divide each frame of the information signal into blocks; and

the property of the information signal is the mean luminance of a block.

27. The apparatus of claim 22, wherein the framing circuit, the band division circuit, the computing circuit, the hash signal generator, and a matching circuit are associated with a portable device.

28. A system to identify content in an information signal, the system comprising:

means for dividing the information signal into frames;

means for dividing each frame of the information signal into disjoint bands;

means for calculating a property of the information signal in each of said bands to compute a hash word for each frame;

means for generating a hash signal by concatenating successive hash words; and

means for obtaining a match of the information signal with a known content item, based on the hash signal.