Generating and matching hashes of multimedia content

FIELD OF THE INVENTION

0001The invention relates to a method and arrangement for generating a hash signal identifying an information signal. The invention also relates to a method and arrangement for matching such a hash signal with hash signals stored in a database.

BACKGROUND OF THE INVENTION

0002Hash functions are generally known in the field of cryptography, where they are used, inter alia, to identify large amounts of data. For instance, in order to verify correct reception of a large file, it suffices to send the hash value (also referred to as signature) of that file. If the returned hash value matches the hash value of the original file, there is almost complete certainty that the file has been correctly received by the receiving party. The remaining uncertainty is introduced due to the fact that a collision might occur: i.e. two different files may have the same hash value. A carefully designed hash function minimizes the probability of collision.

0003A particular property of a cryptographic hash is its extreme fragility. Flipping a single bit in the source data will generally result in a completely different hash value. This makes cryptographic hashing unsuitable for identifying multimedia content where different quality versions of the same content should yield the same signature. Signatures of multimedia content that are to a certain extent invariant to data processing (as long as the processing retains an acceptable quality of the content) are referred to as robust signatures or, which is our preferred naming convention, robust hashes. By using a database of robust hashes and content identifiers, unknown content can be identified, even if it is degraded (e.g. by compression or AD/DA conversion). Robust hashes capture the perceptually essential parts of audio-visual content.

0004Using a robust hash to identify multimedia content is an alternative to using watermarking technology for the same purpose. There is, however, also a great difference. Whereas watermarking requires action on original content (viz. watermark embedding) before being released, with its potential impact on content quality and logistical problems, robust hashing requires no action before release. The drawback of hashing technology is that access to a database is needed (e.g. hashing is only viable in a connected context), whereas watermark detectors can operate locally (for example in non-connected DVD players).

0005Untied States Patent 4,677,466 discloses a known method of deriving a signature from a television signal for broadcast monitoring. In this prior art method, the signature is derived from a short video or audio sequence after the occurrence of specified event such as a blank frame.

OBJECT AND SUMMARY OF THE INVENTION

0006A first aspect of the invention provides a method of generating a hash signal to identify content in an information signal, the method comprising: dividing the information signal into frames; computing a hash word for each frame; and concatenating successive hash words to constitute the hash signal, wherein the computing of a hash word for each frame includes: dividing each frame of the information signal into disjoint bands or blocks, and calculating a property of the signal in each of said bands or blocks.

0007A further aspect of the invention provides a method of generating a hash signal 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 said block; comparing the value of the extracted feature with a threshold; generating for each block a hash bit indicating whether the value of the extracted feature is larger or smaller than said threshold; determining for each block reliability information indicating whether the value of the extracted feature differs substantially from said threshold; combining said hash bits and said reliability information of the blocks into a hash value having reliable hash bits for which the extracted feature differs substantially from said threshold, and unreliable bits for which the extracted feature does not differ substantially from said threshold. A further aspect of the invention provides a method to identify multimedia content utilizing matching an input block of hash words representing at least a part of an information signal with hash signals identifying respective information signals stored in a database, the method comprising: selecting a hash word of said input block of hash words; searching said hash word in the database to obtain a found hash word; calculating a difference between the input block of hash words and a stored block of hash words in which the found hash word has the same position as the selected hash word in the input block; and repeating the selecting, searching and calculating for a further selected hash word until said difference is lower than a predetermined threshold.

0008A further aspect of the invention provides a method to identify multimedia content utilizing matching a hash value representing an unidentified information signal with a plurality of hash values stored in a database and identifying a respective 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; for each stored hash value found during 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; and determining for which stored hash values the bit error rate is minimal and sufficiently small.

0009A further aspect of the invention provides a method to identify multimedia content utilizing matching a hash signal representing an unidentified information signal with a plurality of hash signals stored in a database and identifying a respective 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; for each stored hash value found during the searching: selecting in the database the corresponding series of stored hash values; and 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; and determining for which series of stored hash values the bit error rate is minimal and sufficiently small.

0010It is a general object of preferred aspects of the invention to provide a robust hashing technology. More particularly, it is a first object of preferred aspects of the invention to provide a method and arrangement for extracting a limited number of hashing bits from multimedia content. The hashing bits are robust, but not in a sense that the probability of bit errors is zero. It is known that non-exact pattern matching (i.e. searching for the most similar hash value in the database) is NP-complete. In layman's terms, this means that the best search strategy is an exhaustive search, which is prohibitive in many applications dealing with large databases. Therefore, a second object of preferred aspects of the invention is to provide a method and arrangement that overcomes this NP-complete search complexity.

0011The first object is achieved by dividing the information signal into successive (preferably overlapping) frames, computing a hash word for each frame, and concatenating successive hash words to constitute a hash signal (or hash in short). The hash word is computed by thresholding a scalar property or vector of properties of the information signal, for example, the energy of disjoint frequency bands or the mean luminance of image blocks.

0012The second object is achieved by selecting a single hash word of an input block of hash words, searching said hash word in the database, calculating a difference between the input block of hash words and a corresponding stored block of hash words. These steps are repeated for further selected hash words until said difference is lower than a predetermined threshold.

0013Further features of the invention are defined in the subclaims.

BRIEF DESCRIPTION OF THE DRAWINGS

0014<ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">Fig. 1</figref> is a schematic diagram of an embodiment of an arrangement for extracting a hash signal from an audio signal in accordance with the invention.</li><li><figref idref="f0002">Fig. 2</figref> is a diagram illustrating the subdivision of an audio signal spectrum into logarithmically spaced bands.</li><li><figref idref="f0002">Fig. 3</figref> is a diagram illustrating hash words extracted from an audio clip.</li><li><figref idref="f0003">Fig. 4</figref> is a schematic diagram of an embodiment of an arrangement for extracting a hash signal from a video signal in accordance with the invention.</li><li><figref idref="f0003">Fig. 5</figref> is a diagram illustrating hash words extracted from a video sequence.</li><li><figref idref="f0004">Fig. 6</figref> is a flow chart of operations carried out by a computer which is shown in <figref idref="f0001">Fig. 1</figref> in accordance with the invention.</li><li><figref idref="f0004">Fig. 7</figref> is a diagram to illustrate the operation of a computer which is shown in <figref idref="f0001">Fig. 1</figref>.</li><li><figref idref="f0005">Fig. 8</figref> shows a graph of the number or bit errors in hash words forming an extracted hash block which is shown in <figref idref="f0002">Fig. 3</figref>.</li><li><figref idref="f0005">Fig. 9</figref> shows a graph of the most reliable bit of the hash words of the hash block which is shown in <figref idref="f0002">Fig. 3</figref>.</li><li><figref idref="f0006">Fig. 10</figref> is a flow chart of operations carried out by the computer which is shown in <figref idref="f0001">Fig. 1</figref> in accordance with a further embodiment of the invention.</li></ul>

DESCRIPTION OF EMBODIMENTS

0015Before describing a preferred embodiment, a general description of considerations underlying this invention will be elucidated.

0016Two signals (audio, video, image) can differ quite drastically (e.g. by compression) in a signal theoretical sense, whereas they are perceptually indistinguishable. Ideally, a hash function mimics the behavior of the human auditory system (HAS) or human visual system (HVS), i.e. it produces the same hash signal for content that is considered the same by the HAS/HVS. However, many kinds of processing (compression, noise addition, echo addition, D/A and A/D conversion, equalization etc.) can be applied to the signal and there is no algorithm that is able to mimic the HAS/HVS perfectly. A complicating factor is that even the HAS/HVS varies from person to person as well as in time, and even the notion of one single HAS/HVS is untenable. Also, the classical definition of a hash does not take time into account: a robust hash should not only be able to identify the content, but should also be able to identify time (intervals). For this reason the following definition for a robust hash is herein used: A robust hash is a function that associates with every basic time-unit of multimedia content a semi-unique bit-sequence that is continuous with respect to content similarity as perceived by the HAS/HVS.

0017In other words, if the HAS/HVS identifies two pieces of audio, video or image as being very similar, the associated hashes should also be very similar. In particular, the hashes of original content and compressed content should be similar. Also, if hash words are computed for overlapping frames, the hash words should be similar, i.e. hashes should have a low pass character. On the other hand, if two signals really represent different content, the robust hash should be able to distinguish the two signals (semi-unique). This is similar to the collision requirement for classical cryptographic hashes. The required robustness of the hashing function is achieved by deriving the hash function from robust features (properties), i.e. features that are to a large degree invariant to processing. Robustness can be expressed by the Bit Error Rate (BER), which is defined as the ratio of the number of erroneous bits and the total number of bits.

0018Robust hashing enables content identification which is the basis for many interesting applications. Consider the example of identification of content in a multimedia database. Suppose one is viewing a scene from a movie and would like to know from which movie the shot originates. One way of finding out is by comparing the scene to all fragments of the same size of all movies in the database. Obviously, this is totally infeasible in case of a large database: even a short video scene is represented by a large amount of bytes and potentially these have to be compared to the whole database. Thus, for this to work, one needs to store a large amount of easily accessible data and all these data have to be compared with the video scene to be identified. Therefore, there is both a storage problem (the database) as well as a computational problem (matching large amounts of data). Robust hashing alleviates both problems by reducing the number of bits needed to represent the video scenes: fewer bits need to be stored and fewer bits need to be used in the comparison.

0019Robust hashing of audio signals will be described first. The audio signal will be assumed to be mono audio that has been sampled at a sample frequency of 44.1 kHz (CD-quality). If the audio is stereo, there are two options: either hash signals are extracted for the left and the right channel separately, or the left and the right channel are added prior to hash signal extraction.

0020Even if we only have a short piece of audio (of the order of seconds), we would like to determine which song it is. As audio can be seen as an endless stream of audio-samples, it is necessary to subdivide audio signals into time intervals or frames and to calculate a hash word for every frame.

0021Very often, when trying to match hashes in a database, it is impossible to determine the frame boundaries. This synchronization problem is particularly applicable to audio hashing. This problem is solved by dividing the signal into overlapping frames. Overlapping also ensures that hash words of contiguous frames have a certain amount of correlation. In other words, the hashes change slowly over time.

0022<figref idref="f0001">Fig. 1</figref> shows a schematic diagram of an embodiment of an arrangement for generating an audio hash signal in accordance with the invention. The audio signal is first downsampled in a downsampler <b>11</b> to reduce the complexity of subsequent operations and restrict the operation to a frequency range of 300-3000 Hz, which is most relevant for the Human Auditory System.

0023In a framing circuit <b>12</b>, the audio signal is divided into frames. The frames are weighed by a Hanning window having a length of 16384 samples (≈0.4 seconds) and an overlap factor of 31/32. The overlap is chosen in such a way that a high correlation of the hash words between subsequent frames is ensured. The spectral representation of every frame is computed by a Fourier transform circuit <b>13.</b> In the next block <b>14,</b> the absolute values (magnitudes) of the (complex) Fourier coefficients are computed.

0024A band division stage <b>15</b> divides the frequency spectrum into a number (e.g. 33) of bands. In <figref idref="f0001">Fig. 1</figref>, this is schematically shown by selectors <b>151</b>, each of which selects the Fourier coefficients of the respective band. In a preferred embodiment of the arrangement, the bands have a logarithmic spacing, because the HAS also operates on approximately logarithmic bands. By choosing the bands in this manner, the hash will be less susceptible to processing changes such as compression and filtering. In the preferred embodiment, the first band starts at 300Hz and every band has a bandwidth of one musical tone (i.e. the bandwidth increases by a factor of 2^1/12≈1.06 per band). <figref idref="f0002">Fig. 2</figref> shows an example of a spectrum <b>201</b> of a frame and the subdivision thereof into logarithmically spaced bands <b>202</b>.

0025Subsequently, for every band a certain (not necessarily scalar) characteristic property is calculated. Examples of properties are energy, tonality and standard deviation of the power spectral density. In general, the chosen property can be an arbitrary function of the Fourier coefficients. Experimentally it has been verified that the energy of every band is a property that is most robust to many kinds of processing. This energy computation is carried out in an energy computing stage <b>16</b>. For each band, it comprises a stage <b>161</b> which computes the sum of the (squared) magnitudes of the Fourier coefficients within that band.

0026In order to get a binary hash word for each frame, the robust properties are subsequently converted into bits. The bits can be assigned by calculating an arbitrary function of the robust properties of possibly different frames and then comparing it to a threshold value. The threshold itself might also be a result of another function of the robust property values.

0027In the present arrangement, a bit derivation circuit <b>17</b> converts the energy levels of the bands into a binary hash word. In a simple embodiment, the bit derivation stage generates one bit for each band, for example, a '1' if the energy level is above a threshold and a '0' if the energy level is below said threshold. The thresholds may vary from band to band. Alternatively, a band is assigned a hash bit '1' if its energy level is larger than the energy level of its neighbor, otherwise the hash bit is '0'. The present embodiment uses an even improved version of the latter alternative. To prevent a major single frequency in the audio signal from producing identical hash words for successive frames, variations of the amplitude over time are also taken into account. More particularly, a band is assigned a hash bit '1' if its energy level is larger than the energy level of its neighbor and if that was also the case in the previous frame, otherwise the hash bit is '0'. If we denote the energy of a band m of frame n by EB(n,m) and the m-th bit of the hash word H of frame n by H(n,m), the bit derivation circuit 17 generates the bits of the hash word in the following manner: <maths id="math0001"><math display="block"><mi mathvariant="normal">H</mi><mo>(</mo><mi mathvariant="normal">n</mi><mo>,</mo><mi mathvariant="normal">m</mi><mo>)</mo><mo>=</mo><mo>{</mo><mtable><mtr><mtd><mn>1</mn><mspace width="1em" /><mi>if EB</mi><mo>(</mo><mi mathvariant="normal">n</mi><mo>,</mo><mi mathvariant="normal">m</mi><mo>)</mo><mo>-</mo><mi>EB</mi><mo>(</mo><mi mathvariant="normal">n</mi><mo>,</mo><mi mathvariant="normal">m</mi><mo>+</mo><mn>1</mn><mo>)</mo><mo>-</mo><mo>(</mo><mi>EB</mi><mo>(</mo><mi mathvariant="normal">n</mi><mo>-</mo><mn>1</mn><mo>,</mo><mi mathvariant="normal">m</mi><mo>)</mo><mo>-</mo><mi>EB</mi><mo>(</mo><mi mathvariant="normal">n</mi><mo>-</mo><mn>1</mn><mo>,</mo><mi mathvariant="normal">m</mi><mo>+</mo><mn>1</mn><mo>)</mo><mo>)</mo><mo>></mo><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn><mspace width="1em" /><mi>if EB</mi><mo>(</mo><mi mathvariant="normal">n</mi><mo>,</mo><mi mathvariant="normal">m</mi><mo>)</mo><mo>-</mo><mi>EB</mi><mo>(</mo><mi mathvariant="normal">n</mi><mo>,</mo><mi mathvariant="normal">m</mi><mo>+</mo><mn>1</mn><mo>)</mo><mo>-</mo><mo>(</mo><mi>EB</mi><mo>(</mo><mi mathvariant="normal">n</mi><mo>-</mo><mn>1</mn><mo>,</mo><mi mathvariant="normal">m</mi><mo>)</mo><mo>-</mo><mi>EB</mi><mo>(</mo><mi mathvariant="normal">n</mi><mo>-</mo><mn>1</mn><mo>,</mo><mi mathvariant="normal">m</mi><mo>+</mo><mn>1</mn><mo>)</mo><mo>)</mo><mo>≤</mo><mn>0</mn></mtd></mtr></mtable></math><img file="EP1362485B1_D0001.tif" /></maths>

0028To this end, the bit derivation circuit 17 comprises, for each band, a first subtractor <b>171</b>, a frame delay <b>172</b>, a second subtractor <b>173</b>, and a comparator <b>174</b>. The 33 energy levels of the spectrum of an audio frame are thus converted into a 32-bit hash word. The hash words of successive frames are finally stored in a buffer <b>18</b>, which is accessible by a computer <b>20</b>. The computer stores the robust hashes of a large number of original songs in a database <b>21</b>.

0029In a subsequent operation, the same arrangement computes the hash of an unknown audio clip. Reference numeral <b>31</b> in <figref idref="f0002">Fig. 3</figref> shows the hash words of 256 successive overlapping audio frames (≈3 seconds) of the audio clip as stored in the database <b>21.</b> In the Figure, each row is a 32-bit hash word, a white pixel represents a '1' bit of the hash word, a black pixel represents a '0' bit, and time proceeds from top to bottom. Reference numeral <b>32</b> shows the hash words extracted from the same audio clip after MP3 compression at 32 kBit/s. Ideally, the two hash blocks should be identical, but due to the compression some bits are different. The difference is denoted <b>33</b> in <figref idref="f0002">Fig. 3</figref>.

0030Robust hashing of image or video signals will now be described. Again, the robust hashes are derived from specific features of the information signal. The first question to be asked is in which domain to extract said features which determine the hash word. In contrast to audio, where the frequency domain optimally represents the perceptual characteristics, it is less clear which domain to use. For complexity reasons it is preferable to avoid complex operations, like DCT or DFT transformations. Therefore, features in the spatio-temporal domain are computed. Moreover, to allow easy feature extraction from most compressed video streams as well, features are chosen which can be easily computed from block-based DCT coefficients.

0031Based on these considerations, the preferred algorithm is based on simple statistics, like mean and variance, computed over relatively large image regions. The regions are chosen in a fairly simple way: the image frame is divided into square blocks of 64 by 64 pixels. The features are extracted from the luminance component. This is, however, not a fundamental choice: the chrominance components may be used, as well. As a matter of fact, the easiest way to increase the number of hash bits is to extract them from the chrominance components in a similar way as the extraction from the luminance.

0032<figref idref="f0003">Fig. 4</figref> shows a block diagram of an arrangement for generating a hash signal identifying a video signal in accordance with the invention. The arrangement receives successive frames of the video signal. Each frame is divided (<b>41</b>) in M+1 blocks. For each of these blocks, the mean of the luminance values of the pixels is computed (<b>42</b>). The mean luminance of block k in frame p is denoted F(p,k) for k=0,...,M.

0033In order to make the hash independent of the global level and scale of the luminance, the luminance differences between two consecutive blocks are computed (<b>43</b>). Moreover, in order to reduce the correlation of the hash words in the temporal direction, the difference of spatial differential mean luminance values in consecutive frames is also computed (<b>44, 45</b>). In other words, a simple spatio-temporal 2x2 Haar filter is applied to the mean luminance. The sign of the result constitutes (<b>46</b>) the hash bit H(p,k) for block k in frame p. In mathematical notation: <maths id="math0002"><math display="block"><mi mathvariant="normal">H</mi><mfenced><mi mathvariant="normal">p</mi><mo>⁢</mo><mi mathvariant="normal">k</mi></mfenced><mo mathvariant="normal">=</mo><mrow><mo mathvariant="normal">{</mo><mtable><mtr><mtd><mn mathvariant="normal">1</mn></mtd><mtd><mi>if</mi><mspace width="1em" /><mfenced><mi mathvariant="normal">F</mi><mfenced><mi mathvariant="normal">p</mi><mo>⁢</mo><mi mathvariant="normal">k</mi></mfenced><mo mathvariant="normal">-</mo><mi mathvariant="normal">F</mi><mo mathvariant="normal">(</mo><mi mathvariant="normal">p</mi><mo mathvariant="normal">,</mo><mi mathvariant="normal">k</mi><mo mathvariant="normal">-</mo><mn mathvariant="normal">1</mn><mo mathvariant="normal">)</mo></mfenced><mo mathvariant="normal">-</mo><mfenced><mi mathvariant="normal">F</mi><mrow><mo mathvariant="normal">(</mo><mi mathvariant="normal">p</mi><mo mathvariant="normal">-</mo><mn mathvariant="normal">1</mn><mo mathvariant="normal">,</mo><mi mathvariant="normal">k</mi><mo mathvariant="normal">)</mo><mo mathvariant="normal">-</mo><mi mathvariant="normal">F</mi><mo>⁢</mo><mfenced><mi mathvariant="normal">p</mi><mo mathvariant="normal">-</mo><mn mathvariant="normal">1</mn><mo mathvariant="normal">,</mo><mi mathvariant="normal">k</mi><mo mathvariant="normal">-</mo><mn mathvariant="normal">1</mn></mfenced></mrow></mfenced><mo mathvariant="normal">≥</mo><mn mathvariant="normal">0</mn></mtd></mtr><mtr><mtd><mn mathvariant="normal">0</mn></mtd><mtd><mi>if</mi><mspace width="1em" /><mfenced><mi mathvariant="normal">F</mi><mfenced><mi mathvariant="normal">p</mi><mo>⁢</mo><mi mathvariant="normal">k</mi></mfenced><mo mathvariant="normal">-</mo><mi mathvariant="normal">F</mi><mo mathvariant="normal">(</mo><mi mathvariant="normal">p</mi><mo mathvariant="normal">,</mo><mi mathvariant="normal">k</mi><mo mathvariant="normal">-</mo><mn mathvariant="normal">1</mn><mo mathvariant="normal">)</mo></mfenced><mo mathvariant="normal">-</mo><mfenced><mi mathvariant="normal">F</mi><mrow><mo mathvariant="normal">(</mo><mi mathvariant="normal">p</mi><mo mathvariant="normal">-</mo><mn mathvariant="normal">1</mn><mo mathvariant="normal">,</mo><mi mathvariant="normal">k</mi><mo mathvariant="normal">)</mo><mo mathvariant="normal">-</mo><mi mathvariant="normal">F</mi><mo>⁢</mo><mfenced><mi mathvariant="normal">p</mi><mo mathvariant="normal">-</mo><mn mathvariant="normal">1</mn><mo mathvariant="normal">,</mo><mi mathvariant="normal">k</mi><mo mathvariant="normal">-</mo><mn mathvariant="normal">1</mn></mfenced></mrow></mfenced><mo mathvariant="normal">&lt;</mo><mn mathvariant="normal">0</mn></mtd></mtr></mtable></mrow></math><img file="EP1362485B1_D0002.tif" /></maths>

0034In this example, each frame is divided in 33 blocks (i.e., M=32) of size 64×64. A complete hash H consists of the bits extracted from 30 consecutive frames. Such a hash block, consisting of 30 hash words of 32 bits each (960 bits) leads to a sufficiently small false positive probability, as will be shown below. A typical original hash block is depicted <b>51</b> in <figref idref="f0003">Fig. 5</figref>, where black and white correspond to'0' and' 1', respectively. The corresponding hash block of the same material scaled horizontally to 94% is denoted by reference numeral <b>52.</b> Numeral <b>53</b> denotes the difference between the hash blocks <b>51</b> and <b>52</b>. In this case the bit error rate equals 11.3%. Note how indeed the erroneous bits have a strong correlation in the temporal (vertical) direction.

0035The process of matching extracted hash blocks to the hash blocks in a large database will now be described. This is a non-trivial task since it is well-known that imperfect matching (remember that the extracted hash words may have bit errors) is NP-complete. This will be shown by means of the following (audio) example. In a database, 100,000 songs of approximately five minutes (≡25000 hash words per song) are stored. It will be assumed that a hash block having 256 hash words (e.g. hash block 32 in <figref idref="f0002">Fig. 3</figref>) has been extracted from the unknown audio clip. It is now to be determined to which of the 100,000 stored songs the extracted hash block matches best. Hence the position of a hash block in one of the 100,000 songs has to be found, which most resembles the extracted hash block, i.e. for which the bit error rate (BER) is minimal or, alternatively, for which the BER is lower than a certain threshold. The threshold directly determines the false positive rate, i.e. the rate at which songs are incorrectly identified from the database.

0036Two 3 seconds audio clips (or two 30-frame video sequences) are declared similar if the Hamming distance between the two derived hash blocks H₁ and H₂ is below a certain threshold T. This threshold T directly determines the false positive rate P_f, i.e. the rate at which two audio clips / video sequences are incorrectly declared equal (i.e. incorrectly in the eyes of a human beholder): the smaller T, the smaller the probability P_f will be. On the other hand, a small value T will negatively effect the false negative probability P_n, i.e. the probability that two signals are 'equal', but not identified as such. In order to analyze the choice of this threshold T, we assume that the hash extraction process yields random i.i.d. (independent and identically distributed) bits. The number of bit errors will then have a binomial distribution with parameters (n,p), where n equals the number of bits extracted and p (=0.5) is the probability that a '0' or '1' bit is extracted. Since n (32x256=8192 for audio, 32×30=960 for video) is large in our application, the binomial distribution can be approximated by a normal distribution with a mean µ=np and standard deviation σ = √np(1-p). Given a hash block H₁, the probability that a randomly selected hash block H₂ has less than T=αn errors with respect to H₁ is given by: <maths id="math0003" num="(1)"><math display="block"><msub><mi mathvariant="normal">P</mi><mi mathvariant="normal">f</mi></msub><mfenced><mi mathvariant="normal">α</mi></mfenced><mo mathvariant="normal">=</mo><mfrac><mn mathvariant="normal">1</mn><mrow><mn mathvariant="normal">2</mn><mo>⁢</mo><mi mathvariant="normal">π</mi></mrow></mfrac><munderover><mo mathvariant="normal">∫</mo><mrow><mo mathvariant="normal">(</mo><mn mathvariant="normal">1</mn><mo mathvariant="normal">-</mo><mn mathvariant="normal">2</mn><mo>⁢</mo><mi mathvariant="normal">α</mi><mo mathvariant="normal">)</mo><msqrt><mi mathvariant="normal">n</mi></msqrt></mrow><mi mathvariant="normal">∞</mi></munderover><msup><mi mathvariant="normal">e</mi><mfrac><msup><mi mathvariant="normal">x</mi><mn mathvariant="normal">2</mn></msup><mn mathvariant="normal">2</mn></mfrac></msup><mo>⁢</mo><mi>dx</mi><mo mathvariant="normal">=</mo><mfrac><mn mathvariant="normal">1</mn><mn mathvariant="normal">2</mn></mfrac><mo>⁢</mo><mi>erfc</mi><mo>⁢</mo><mfenced><mfrac><mrow><mn mathvariant="normal">1</mn><mo mathvariant="normal">-</mo><mn mathvariant="normal">2</mn><mo>⁢</mo><mi mathvariant="normal">α</mi></mrow><msqrt><mn mathvariant="normal">2</mn></msqrt></mfrac><mo>⁢</mo><msqrt><mi mathvariant="normal">n</mi></msqrt></mfenced></math><img file="EP1362485B1_D0003.tif" /></maths>

0037However, in practice the robust hashes have high correlation along the time axis. This is due to the large time correlation of the underlying video sequence, or the overlap of audio frames. Experiments show that the number of erroneous bits are normally distributed, but that the standard deviation is approximately 3/2 times larger than the i.i.d. case. Equation (1) therefore is modified to include this factor 3/2. <maths id="math0004" num="(2)"><math display="block"><msub><mi mathvariant="normal">P</mi><mi mathvariant="normal">f</mi></msub><mfenced><mi mathvariant="normal">α</mi></mfenced><mo mathvariant="normal">=</mo><mfrac><mn mathvariant="normal">1</mn><mn mathvariant="normal">2</mn></mfrac><mo>⁢</mo><mi>erfc</mi><mo>⁢</mo><mfenced><mfrac><mrow><mn mathvariant="normal">1</mn><mo mathvariant="normal">-</mo><mn mathvariant="normal">2</mn><mo>⁢</mo><mi mathvariant="normal">α</mi></mrow><mn mathvariant="normal">3</mn></mfrac><mo>⁢</mo><msqrt><mn mathvariant="normal">2</mn><mo>⁢</mo><mi mathvariant="normal">n</mi></msqrt></mfenced></math><img file="EP1362485B1_D0004.tif" /></maths>

0038The threshold for the BER used during experiments was α=0.25. This means that, of 8192 bits, less than 2048 bit errors have to occur in order to decide that the hash block originates from the same song. In this case the bit errors have a normal distribution with a mean µ of np=4096 and a standard deviation σ of 3√(np(1-p))=135.76. The chosen threshold setting then corresponds to the false alarm probability of 15.2σ. Hence, the false alarm probability equals 1.8·10^-52. Note, however, that the false alarm probability will be higher in practice if music with similar hash words (e.g. a Mozart piece played by two different pianists) is included in the database.

0039Searching the position of the extracted hash block in the database can be done by brute force matching. This will take around 2.5 billion (=25000×100,000) matches. Moreover, the number of matches increases linearly with the size of the database.

0040In accordance with an aspect of the invention, the computer <b>20</b> uses a more efficient strategy for finding the corresponding song in the database <b>21</b>. <figref idref="f0004">Fig. 6</figref> is a flow chart of operations carried out by the computer. Upon storing an original song in the database, the computer updates a lookup table (LUT) in a step <b>60</b>. The LUT is shown as a separate memory <b>22</b> in <figref idref="f0001">Fig. 1</figref>, but it will be appreciated that it will be part of the large database memory <b>21</b> in practice. As is shown in <figref idref="f0004">Fig. 7</figref>, the LUT <b>22</b> has an entry for each possible 32-bit hash word. Each entry of the LUT points to the song(s) and the position(s) in that song where the respective hash word occurs. Since a hash word can occur at multiple positions in multiple songs, the song pointers are stored in a linked list. Thus the LUT can generate multiple candidate songs. Note that a LUT containing 2³² entries can be impractical when there is only a limited number of songs in the database. In such a case, it is advantageous to implement the LUT with a hash table and a linked list. Reference numeral <b>70</b> in <figref idref="f0004">Fig. 7</figref> denotes a block of 256 hash words extracted from the unknown audio clip (e.g. hash block <b>32</b> in <figref idref="f0002">Fig. 3</figref>).

0041In a first embodiment of the matching method, it will be assumed that every now and then a single hash word has no bit errors. In a step <b>61</b>, a single hash word H(m) is selected from the hash block and sent to the database. Initially, this will be the last hash word H(256) of the extracted hash block. In the example shown in <figref idref="f0004">Fig. 7</figref>, this is the hash word 0x00000001. The LUT in the database points to a certain position in song 1. Let it be assumed that this position is position p. In a step <b>62</b>, the computer calculates the BER between the extracted hash block and the block of hash words from position p-255 until position p of song 1 (denoted <b>71</b> in <figref idref="f0004">Fig. 7</figref>). In a step <b>63</b>, it is checked whether the BER is low (&lt;0.25) or high. If the BER is low, there will be a high probability that the extracted hash words originate from song 1. If the BER is high, either the song is not in the database or the single hash word H(m) contains an error. The latter will be assumed to be the case in this example. Another single hash word is then selected in a step <b>64</b> and looked up in the LUT. In <figref idref="f0004">Fig. 7</figref>, the last but one single hash word H(255) is now being looked up. This hash word appears to occur in song 2. The BER between input block <b>70</b> and stored block <b>72</b> appears to be lower than 0.25 now, so that song 2 is identified as the song from which the audio clip originates. Note that the last hash word in the stored block <b>52</b> is 0x00000000. Apparently, the previously selected hash word 0x0000001 had one bit error.

0042The computer thus only looks at one single hash word at a time and assumes that every now and then such a single hash word has no bit errors. The BER of the extracted hash block is then compared with the corresponding (on the time axis) hash blocks of the candidate songs. The title of the candidate song with the lowest BER will be chosen as the song from which the extracted hash words originate, provided that the lowest BER is below the threshold (step <b>65</b>). Otherwise, the database will report that the extracted hash block was not found. Another single hash word will then be tried. If none of the single hash words leads to success (step <b>66</b>), the database will respond by reporting the absence of the candidate song in the database (step <b>67</b>).

0043The above-described method relies on the assumption that every now and then an extracted hash word has no bit errors, i.e. it is perfectly equal to the corresponding stored hash word. Extensive experiments have shown that this occurs regularly a few times per second for most audio. This is shown, for example, in <figref idref="f0005">Fig. 8</figref> which shows the number of bit errors in the 256 hash words forming the extracted block of <figref idref="f0002">Fig. 3B</figref>

0044. Thirteen hash words occur without any bit errors in this 3-second audio clip.

0045However, it is unlikely that hash words without any bit errors occur when the audio is severely processed. In that case, the title of the song cannot be retrieved by means of the previous method. To this end, another embodiment of the matching method will be described. This method uses soft information of the hash extraction algorithm to find the extracted hash words in the database. Soft information is understood to mean the reliability of a bit, or the probability that a hash bit has been retrieved correctly. In this embodiment, the arrangement for extracting the hash words includes a bit reliability determining circuit. The bit reliability determining circuit is denoted <b>19</b> in the audio hash extraction arrangement which is shown in <figref idref="f0001">Fig. 1</figref>. It circuit receives the differential energy band levels in the form of real numbers. If the real number is very close to the threshold (which is zero in this example), the respective hash bit is unreliable. If instead the number is very far from the threshold, it is a reliable hash bit. The threshold can be fixed or controlled such that the number of reliable bits is fixed.

0046The bit reliability determining circuit <b>19</b> determines the reliability of every hash bit, and thus enables the extraction arrangement or the computer <b>20</b> to generate a list of most probable alternative hash words for each hash word. By assuming again that at least one of the alternative hash words is correct, the song title can be received correctly and easily. <figref idref="f0005">Fig. 9</figref> shows, for all the 256 hash words of hash block <b>32</b> in <figref idref="f0002">Fig. 3</figref>, which bit of the hash word is the most reliable.

0047<figref idref="f0006">Fig. 10</figref> is a flow chart of operations carried out by the computer in this embodiment of the method of finding the extracted hash block in the database. The same reference numerals are used for operations already described before. Again, the last extracted hash word (0x00000001, see <figref idref="f0004">Fig. 7</figref>) of the hash block is initially selected and sent to the database (step <b>61</b>). The LUT in the database points to position p in song 1. The BER between the extracted hash block and the corresponding block <b>71</b> in song 1 is calculated (step 62). Meanwhile, it is known from the previous example that the BER is high. In a step <b>101</b>, the computer now consults the bit reliability determining circuit <b>19</b> (<figref idref="f0001">Fig. 1</figref>) and learns that bit 0 is the least reliable bit of this particular hash word. The next most probable candidate hash word is now obtained by flipping said bit. The new hash word (0x00000000) is sent to the database in a step <b>102.</b> As is shown in <figref idref="f0004">Fig. 7</figref>, the hash word 0x00000000 leads to two possible candidate songs in the database: song 1 and song 2. If, for example, the extracted hash words now have a low BER with the hash words of song 2, song 2 will be identified as the song from which the extracted hash block originates. Otherwise, new hash word candidates will be generated, or another hash word will be used to try to find the respective song in the database. This strategy is continued until it is found in a step <b>103</b> that there are no further alternative candidate hash words.

0048Note that, once a piece of audio is identified in practice as originating from a certain song, the database can first try to match the extracted hash words with that song before generating all the candidate hash words.

0049A very simple way of generating a list of most probable hash words is to include all the hash words with N most reliable bits being fixed and every possible combination for the remaining bits. In the case of 32 bits per hash and choosing N=23, a list of 512 candidate hash words is required. Furthermore it means that the 9 least reliable bits of the hash word can be wrong before an audio excerpt cannot be identified anymore. For the case shown in <figref idref="f0004">Figure 6</figref>, this means that 117 hash words, instead of 13 with the previous method, will yield a correct pointer to the song in the database.

0050In an alternative embodiment of the matching method, the matching is done only on the basis of hash bits being marked as reliable. This method is based on the insight that it is unnecessary to compare unreliable bits of a received hash with the corresponding bits in the database. This leads to a far smaller bit error rate, although this comes at the cost of a more complicated search strategy and a larger bandwidth needed to transmit all necessary information to the database.

0051A few applications of robust hashing will now be described. <ul id="ul0002" list-style="dash" compact="compact"><li>Broadcast Monitoring: A broadcast monitoring system consists of two parts: a central database containing the hashes of a large number of songs, and monitoring stations that extract a hash block from the audio that is broadcast by, for instance, radio stations. The monitoring station will send the extracted hash block to the central database and then the database will be able to determine which song has been broadcast.</li><li>Mobile Phone Audio Info: Imagine that you are in a bar and hear a song of which you want to know the title. You then just pick up your mobile telephone and call an audiohash database. The audiohash database will then hear the song and extract a hash block. If it then finds the hash block in the database, it will report back the title of the song.</li><li>Connected Content (MediaBridge): The company Digimarc currently has an application called MediaBridge, which is based on watermarking technology. The idea is that a watermark in a piece of multimedia will direct a user to a certain URL on the Internet where he can get some extra information. E.g. an advertisement in a magazine is watermarked. By holding this advertisement in front of a webcam, a watermark detector will extract a watermark key that is sent to a database. This database then contains the URL to which the user will be redirected. The same application can work with the use of robust hashing technology. In the future, one might even think of a person pointing his mobile videophone at a real-life object. The audio hash database will then report back information about this object, either directly or via an URL on the Internet.</li><li>Multimedia Quality Metering: If the hash words of high quality original content are listed in the database, a quality measure can be obtained by determining the BER of the extracted hash words of processed multimedia content.</li></ul>

0052From an abstract point of view, the robust audio hashes are derived from an audio signal by comparing energy in different frequency bands and over time. A generalization of this approach is to consider any cascade of LTI and non-linear functions. In particular, a robust hash can also be obtained by applying a (dyadic) filter bank (an LTI operator), followed by squaring or taking absolute words (a non-linear function), followed by a difference operator over time and/or band (an LTI operator), finally followed by a thresholding operator. By applying a carefully designed linear filter bank as an initial operator, the complexity of a FFT can be avoided. Moreover, as many compression engines have a linear filter bank as an initial phase, there is the option to integrate feature extraction with compression.

0053It is further noted that robust hashing and digital watermarks can be used in combination to identify content. The method described above and some watermark detection algorithms have a number of initial processing steps in common, viz. the computation of the spectral representation. This leads to the idea that watermark detection and feature extraction can easily be integrated in one application. Both retrieved watermark and hash words can then be sent to a central database for further analysis, to allow identification of content.

0054In summary, 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.