Generating and matching hashes of multimedia content

• US 7,549,052 B2
• Filed: 02/11/2002
• Issued: 06/16/2009
• Est. Priority Date: 02/12/2001
• Status: Active Grant

• Current Assignee: Gracenote, Inc. (RR Donnelley & Sons Company)
• Original Assignee: Koninklijke Philips N.V., Gracenote, Inc. (RR Donnelley & Sons Company)
• Inventors: Oostveen, Job Cornelis, Baggen, Constant Paul Marie Jozef, Haitsma, Jaap Andre, Kalker, Antonius Adrianus Cornelis Maria
• Primary Examiner(s): Vu; KimYen
• Assistant Examiner(s): Paliwal; Yogesh
• Application Number:
  US10/073,772
• Publication Number:
  US 20020178410A1
• Time in Patent Office: 2,682 Days
• Field of Search: 713168-181, 713/186, 713/162, 382/100, 382/199, 714/704, 375/225, 380/54, 380/55, 380/232, 348/461, 348/467
• 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 match a hash value representing an unidentified information signal with a plurality of hash values stored in a database and to identify a respective one of a plurality of information signals, the method comprising:

receiving said hash value in the form of a plurality of reliable hash bits and unreliable hash bits;

searching in the database the stored hash values for which holds that the reliable bits of the applied hash value match the corresponding bits of the stored hash value while ignoring unreliable bits of the applied hash value and corresponding bits of the stored hash value;

for each stored hash value found in response to the searching, calculating the bit error rate between the reliable bits of the hash value representing the unidentified information signal and the corresponding bits of the stored hash value;

determining for which stored hash values the bit error rate is minimal; and

returning an identification of the respective one of the plurality of information signals that corresponds to the minimal bit error rate.

2. The method of claim 1, further comprising generating the hash value, the generating of the hash value comprising:

dividing the unidentified information signal into frames;

computing a hash word for each frame; and

concatenating successive hash words to constitute the hash value.

3. The method of claim 2, wherein the computing of a hash word for each frame includes:

dividing each frame of the information signal into one of bands or blocks;

calculating a property of the signal in each of said bands or blocks;

comparing the properties in the bands or blocks with respective thresholds; and

generating respective bits of the hash word based on the results of said comparisons.

4. The method as claimed in claim 3, wherein the property of a neighboring band or block constitutes said threshold.

5. The method as claimed in claim 3, wherein the property of a corresponding band or block in a previous frame constitutes said threshold.

6. The method as claimed in claim 3, wherein the bands or blocks are frequency bands of the frequency spectrum of the respective frame of the unidentified information signal.

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

8. The method as claimed in claim 6, wherein said property is the energy of a frequency band.

9. The method as claimed in claim 6, wherein said property is the tonality of a frequency band.

10. The method as claimed in claim 3, wherein the unidentified information signal is a video signal, the frames of which are divided into blocks, the mean luminance of a block constituting the property of said block.

11. The method of claim 2, wherein the dividing of the unidentified information signal into frames includes dividing the unidentified information signal into overlapping frames.

12. The method as claimed in claim 1, wherein the unidentified information signal is an audio signal.

13. A method to match a hash signal representing an unidentified information signal with a plurality of hash signals stored in a database and to identify a respective one of a plurality of information signals, the method comprising:

receiving said hash signal in the form of a series of hash values, each hash value having reliable hash bits and unreliable hash bits;

applying one of the hash values of said series to the database;

searching in the database the stored hash values for which holds that the reliable bits of the applied hash value match the corresponding bits of the stored hash value while ignoring unreliable bits of the applied hash value and corresponding bits of the stored hash value;

for each stored hash value found in response to the searching;

selecting in the database the corresponding series of stored hash values;

calculating the bit error rate between the reliable bits of the series of hash values representing the unidentified information signal and the corresponding bits of the selected series of hash values in the database while ignoring unreliable bits of the series of hash values and corresponding bits of the selected series of hash values in the database; and

determining for which series of stored hash values the bit error rate is minimal; and

returning an identification of the respective one of the plurality of information signals that corresponds to the minimal bit error rate.

14. The method as claimed in claim 13, further comprising repeating the applying, searching, selecting, calculating, determining and returning for other hash values of the unidentified information signal until a series of stored hash values is found for which the bit error rate is minimal, wherein the returning returns the identification of the respective one of the plurality of information signals that corresponds to this minimal bit error rate.

15. A system comprising:

a receiving module to receive a subject hash value in the form of a plurality of reliable hash bits and unreliable hash bits, the hash value representing an unidentified information signal;

a searching module to search, in a database, stored hash values for which holds that the reliable bits of the hash value representing the unidentified information signal match the corresponding bits of the stored hash value while ignoring unreliable bits of the hash value representing the unidentified information signal and corresponding bits of the stored hash value;

a bit error evaluator to;

calculate the bit error rate between the reliable bits of the hash value representing the unidentified information signal and the corresponding bits of the stored hash value for each stored hash value found in response to the search, and

determine for which stored hash values the bit error rate is minimal; and

a return module to return an identification of the respective one of the plurality of information signals that corresponds to the minimal bit error rate.

16. The system as claimed in claim 15, wherein the unidentified information signal is an audio signal.

17. The system of claim 15, further comprising a hash value generator to:

divide the unidentified information signal into frames;

compute a hash word for each frame; and

concatenate successive hash words to constitute the hash value representing the unidentified information signal.

18. The system of claim 15, wherein the hash value generator is to divide the unidentified information signal into frames by dividing the unidentified information signal into overlapping frames.

19. The system of claim 15, wherein the hash value generator is to compute a hash word for each frame by:

dividing each frame of the information signal into one of bands or blocks;

calculating a property of the signal in each of said bands or blocks;

comparing the properties in the bands or blocks with respective thresholds; and

generating respective bits of the hash word based on the results of said comparisons.

20. The system as claimed in claim 19, wherein the property of a neighboring band or block constitutes said threshold.

21. The system as claimed in claim 19, wherein the property of a corresponding band or block in a previous frame constitutes said threshold.

22. The system as claimed in claim 19, wherein the unidentified information signal is a video signal, the frames of which are divided into blocks, the mean luminance of a block constituting the property of said block.

23. The system as claimed in claim 19, wherein the bands or blocks are frequency bands of the frequency spectrum of the respective frame of the unidentified information signal.

24. The system as claimed in claim 23, wherein the frequency bands have an increasing bandwidth as a function of the frequency.

25. The system as claimed in claim 23, wherein said property is the energy of a frequency band.

26. The system as claimed in claim 23, wherein said property is the tonality of a frequency band.

27. A system to match a hash signal representing an unidentified information signal with a plurality of hash signals stored in a database and to identify a respective one of a plurality of information signals, the system comprising:

a receiving module to receive said hash signal in the form of a series of hash values, each hash value having reliable hash bits and unreliable hash bits;

an applying module to apply one of the hash values of said series to the database;

a searching module to search in the database the stored hash values for which holds that the reliable bits of the applied hash value match the corresponding bits of the stored hash value while ignoring unreliable bits of the applied hash value and corresponding bits of the stored hash value;

a selecting module to select in the database the corresponding series of stored hash values for each stored hash value found in response to the searching;

a calculating module to calculate the bit error rate between the reliable bits of the hash value representing the unidentified information signal and the corresponding bits of the selected series of hash values in the database while ignoring unreliable bits of the series of hash values and corresponding bits of the selected series of hash values in the database;

a determining module to determine for which series of stored hash values the bit error rate is minimal; and

a returning module to return an identification of the respective one of the plurality of information signals that corresponds to the minimal bit error rate.

28. The system as claimed in claim 27, wherein:

the applying module, the searching module, the selecting module, the calculating module, and the determining module are to repeat applying, searching, selecting, calculating, determining, and returning respectively for other hash values of the unidentified information signal until a series of stored hash values is found for which the bit error rate is minimal, wherein the returning module to return the identification of the respective one of the plurality of information signals that corresponds to this minimal bit error rate.