What algorithms are commonly used for audio fingerprinting?

Audio fingerprinting algorithms identify audio clips by generating compact, unique signatures that can be efficiently matched against a database. Three widely used approaches include spectral peak-based methods, chroma-based techniques, and wavelet transforms, each with distinct trade-offs in accuracy, robustness, and computational cost.

Spectral peak-based algorithms, popularized by Shazam, extract fingerprints by identifying prominent time-frequency points in a spectrogram. These “landmark” points (e.g., local energy maxima in frequency bins) are combined into hash keys that encode their relative timing and frequency relationships. For example, a triplet of peaks at times t1, t2, t3 with frequencies f1, f2, f3 might generate a hash based on (f1, f2, f3, t2-t1, t3-t2). This method is robust to noise because it focuses on dominant features rather than the full audio spectrum. Chroma-based techniques like those in Chromaprint (used by AcoustID) emphasize harmonic content by mapping spectral energy to the 12 semitone bins of the musical scale. By analyzing how these chroma vectors change over time, the algorithm captures melodic and harmonic patterns, making it effective for music identification even with pitch shifts or tempo changes. Wavelet-based methods like Waveprint decompose audio using wavelet transforms instead of Fourier transforms, capturing both frequency and temporal localization. This can improve resilience to compression artifacts, as wavelets better preserve transient features during time-frequency analysis.

After feature extraction, most systems use hashing and indexing to enable fast comparisons. MinHash or locality-sensitive hashing (LSH) reduces feature sets to compact signatures while preserving similarity relationships, allowing approximate nearest-neighbor searches. Some implementations also employ database optimizations like inverted indexes or tree structures to accelerate matching. For example, a system might first filter candidates using coarse chroma-based fingerprints before applying detailed spectral peak matching for verification. Trade-offs between fingerprint size, matching speed, and robustness to distortions (e.g., background noise, codec artifacts) often dictate algorithm choice. Open-source libraries like Dejavu (Python) or FPCore (C++) demonstrate practical implementations of these concepts.