act fingerprints and amethod to efficiently search for matching fingerprints in afingerprint database.
This paper describes an audio fingerprinting system that is suitablefor a large number of applications. After defining the concept ofan audio fingerprint in Section 2 and elaborating on possibleapplications in Section 3, we focus on the technical aspects of theproposed audio fingerprinting system. Fingerprint extraction isdescribed in Section 4 and fingerprint searching in Section 5.
2. AUDIO FINGERPRINTING CONCEPTS
2.1 Audio Fingerprint Definition
Recall that an audio fingerprint can be seen as a short summary ofan audio object. Therefore a fingerprint function F should map anaudio object X, consisting of a large number of bits, to afingerprint of only a limited number of bits.Here we can draw an analogy with so-called hash functions1,which are well known in cryptography. A cryptographic hashfunction H maps an (usually large) object X to a (usually small)hash value (a.k.a. message digest). A cryptographic hash functionallows comparison of two large objects X and Y, by justcomparing their respective hash values H(X) and H(Y). Strictmathematical equality of the latter pair implies equality of theformer, with only a very low probability of error. For a properlydesigned cryptographic hash function this probability is 2-n, wheren equals the number of bits of the hash value. Using cryptographichash functions, an efficient method exists to check whether or nota particular data item X is contained in a given and large data setY={Yi}. Instead of storing and comparing with all of the data in Y,
1 In the literature fingerprinting is sometimes also referred to as
robust or perceptual hashing[5].Permission to make digital or hard copies of all or part of thiswork for personal or classroom use is granted without feeprovided that copies are not made or distributed for profit orcommercial advantage and that copies bear this notice and thefull citation on the first page.
© 2002 IRCAM – Centre Pompidou
A Highly Robust Audio Fingerprinting System
it is sufficient to store the set of hash values {hi = H(Yi)}, and to
compare H(X) with this set of hash values.
At first one might think that cryptographic hash functions are a
good candidate for fingerprint functions. However recall from the
introduction that, instead of strict mathematical equality, we are
interested in perceptual similarity. For example, an original CD
quality version of ‘Rolling Stones – Angie’ and an MP3 version at
128Kb/s sound the same to the human auditory system, but their
waveforms can be quite different. Although the two versions are
perceptually similar they are mathematically quite different.
Therefore cryptographic hash functions cannot decide upon
perceptual equality of these two versions. Even worse,
cryptographic hash functions are typically bit-sensitive: a single
bit of difference in the original object results in a completely
different hash value.
Another valid question the reader might ask is: “Is it not possible
to design a fingerprint function that produces mathematically
equal fingerprints for perceptually similar objects?” The question
is valid, but the answer is that such a modeling of perceptual
similarity is fundamentally not possible. To be more precise: it is a
known fact that perceptual similarity is not transitive. Perceptual
similarity of a pair of objects X and Y and of another pair of
objects Y and Z does not necessarily imply the perceptual
similarity of objects X and Z. However modeling perceptual
similarity by mathematical equality of fingerprints would lead to
such a relationship.
Given the above arguments, we propose to construct a fingerprint
function in such a way that perc
