Imaginez-vous dans un café bondé : le percolateur à expresso siffle, les tasses s’entrechoquent et des dizaines de conversations se superposent. Depuis un petit haut-parleur fixé au plafond, une mélodie à peine audible se fait entendre. Vous sortez votre smartphone, appuyez sur un bouton et tendez le microphone pendant trois secondes. En une fraction de seconde, l’écran affiche le titre exact du morceau, l’artiste, la pochette de l’album et même les paroles synchronisées au dixième de seconde près — par exemple à 2 minutes et 14 secondes.

Du point de vue de la théorie de l’information et du traitement numérique du signal (DSP), cette prouesse quotidienne résout un défi mathématique redoutable :

1. Rapport signal sur bruit catastrophique ($\text{SNR} < -10\,\text{dB}$) : Plus de 90 % de l’énergie acoustique captée provient du bruit ambiant (voix, chocs, ventilation).
2. Réponse impulsionnelle de la pièce inconnue : Le signal original $s(t)$ subit la distorsion du haut-parleur et la réverbération des murs (convolution avec $h_{\text{room}}(t)$), donnant $x(t) = (s * h_{\text{room}})(t) + n(t)$.
3. Décalage temporel arbitraire ($t_0$ inconnu) : L’extrait de 3 secondes $[t_0, t_0 + 3\,\text{s}]$ commence à n’importe quel instant du morceau.
4. Un catalogue de 100 millions de titres ($10^8$ chansons) : Plus de 1 000 ans d’audio continu doivent être fouillés en quelques centaines de millisecondes.

Cet article décortique l’architecture en quatre étapes de l’empreinte acoustique Shazam publiée par Avery Li-Chun Wang en 2003 (“An Industrial-Strength Audio Search Algorithm”, ISMIR), puis explore son problème dual : le problème de la soirée cocktail (Cocktail Party Problem) et la séparation aveugle de sources (BSS) par Analyse en Composantes Indépendantes (ICA / FastICA).

Chapitre 1 : Pourquoi la corrélation directe et le hachage cryptographique échouent totalement

Les fonctions de hachage cryptographiques (SHA-256, MD5) reposent sur l’effet d’avalanche : modifier un seul bit en entrée inverse aléatoirement 50 % des bits de sortie. Le moindre bruit thermique ou réencodage MP3 détruit complètement le hachage.

Quant à la corrélation croisée temporelle $R_{x s_i}[\tau] = \sum_{n=0}^{L-1} x[n]\, s_i[n + \tau]$ sur $10^8$ chansons (à $f_s = 8000\,\text{Hz}$, soit $L = 24\,000$ échantillons pour 3 secondes), elle exigerait d’évaluer $1{,}92 \times 10^{14}$ décalages $\tau$, soit $4{,}6 \times 10^{18}$ opérations (4,6 ExaFLOPs) par requête ! De plus, la réverbération de la pièce $h_{\text{room}}(t)$ brouille la phase du signal temporel $x[n]$, faisant chuter la corrélation vers zéro alors même que l’oreille humaine (insensible à la phase selon la loi de Helmholtz) reconnaît parfaitement la musique.

Chapitre 2 : Étape 1 — Transformée de Fourier à court terme (STFT) et incertitude de Gabor-Heisenberg

Pour éliminer la sensibilité à la phase, l’étape 1 convertit l’onde 1D $x[n]$ (sous-échantillonnée à $f_s = 8000\,\text{Hz}$) en un spectrogramme temps-fréquence 2D à l’aide d’une fenêtre de Hann $w[n] = 0{,}5 - 0{,}5\cos\left(\frac{2\pi n}{N-1}\right)$ de taille $N$ et d’un pas d’avancement $H$ :

Le choix de la longueur de fenêtre $N$ est gouverné par le principe d’incertitude temps-fréquence de Gabor-Heisenberg :

Une fenêtre trop longue ($N = 4096$) offre une résolution fréquentielle fine mais étale les attaques de percussions sur $\Delta t = 512\,\text{ms}$ ; une fenêtre trop courte ($N = 128$) localise les transitoires mais fusionne les notes adjacentes ($\Delta f = 62{,}5\,\text{Hz}$). Shazam adopte le compromis optimal $N = 1024$ ($\Delta t = 128\,\text{ms}$, $\Delta f = 7{,}8125\,\text{Hz}$).

Chapitre 3 : Étape 2 — Extraction de pics parcimonieux : La « Constellation Map »

Pour survivre à un rapport signal sur bruit de $-10\,\text{dB}$, Avery Wang élimine 99,9 % des données du spectrogramme et ne conserve que les coordonnées $(t_i, f_i)$ des maxima locaux 2D dans un voisinage $\mathcal{N}(m_i, k_i)$ :

Projeté sur le plan $(t, f)$, ce nuage de points évoque une carte céleste, d’où le nom de Constellation Map (carte de constellations).

1. Des sommets qui percent le brouillard : Le bruit de fond additif élève le « niveau de la mer », submergeant les vallées, mais les plus hauts sommets spectraux (transitoires de caisse claire, formants vocaux) émergent toujours aux mêmes coordonnées $(t_i, f_i)$.
2. Invariance à l’égalisation (EQ) et au gain (AGC) : L’amplitude $S(t_i, f_i)$ est totalement jetée ! Seul le couple $(t_i, f_i)$ est conservé, rendant l’empreinte insensible au volume du micro et au filtrage fréquentiel $|H_{\text{room}}(f)|^2$.

Chapitre 4 : Étape 3 — Hachage combinatoire 32 bits de paires Ancre-Cible

Indexer un pic isolé par sa seule fréquence $f_i \in [0, 1023]$ (10 bits = 1 024 compartiments) provoquerait des centaines de millions de collisions.

L’astuce géniale de Wang consiste à former des paires combinatoires Ancre-Cible (Combinatorial Hashing) : Chaque point d’ancrage $p_1 = (t_1, f_1)$ est associé à un maximum de $F \approx 10$ (facteur de fan-out) points cibles $p_2 = (t_2, f_2)$ situés dans une zone cible juste en avant dans le temps ($\Delta t = t_2 - t_1 \in [\tau_{\min}, \tau_{\max}]$). Les deux fréquences et leur différence de temps relative $\Delta t = t_2 - t_1$ sont condensées dans un entier de 32 bits $h$ :

• Un million de fois moins de collisions : L’espace de hachage passe de 10 bits ($10^3$ compartiments) à 30 bits ($2^{30} \approx 1{,}07 \times 10^9$ compartiments) !
• Invariance parfaite par translation temporelle : Puisque $\Delta t' = (t_2 - t_0) - (t_1 - t_0) = t_2 - t_1$, l’instant de départ inconnu $t_0$ s’annule algébriquement ! Même si 70 % des pics sont détruits par le bruit ($p = 0{,}3$), $p^2 = 9\,\%$ des paires survivent intactes.

  flowchart TD
    A["Audio capté au micro x(t)<br/>(3 secondes, SNR < -10 dB, départ t0 inconnu)"] --> B["Étape 1 : Transformée de Fourier à court terme (STFT)<br/>Fenêtre de Hann w[n], Spectrogramme S(m, k) = |X(m, k)|²"]
    B --> C["Étape 2 : Extraction de la Constellation Map<br/>Conserver uniquement les maxima locaux 2D (t_i, f_i)"]
    C --> D["Étape 3 : Appariement combinatoire Ancre-Cible<br/>Coupler l'ancre (t1, f1) aux points cibles (t2, f2)"]
    D --> E["Hachage 30 bits invariant par translation<br/>h = (f1 << 20) | (f2 << 10) | (t2 - t1)"]
    E --> F["Étape 4 : Recherche O(1) par index inversé<br/>Récupérer les candidats (Song_ID, t_db)"]
    F --> G["Histogramme des décalages temporels<br/>Voter pour δ = t_db - t_sample"]
    G --> H["Pic de Dirac dans l'histogramme !<br/>Identification du titre Song_ID et du temps δ = t0"]

Chapitre 5 : Étape 4 — Index inversé et histogramme de coïncidence temporelle ($\Delta T$)

Pour chaque correspondance $(\text{Song\_ID}, t_{\text{db}, k})$ issue de l’index inversé, le serveur calcule la différence de décalage temporel :

Pour un mauvais titre, les valeurs $\delta_k$ se dispersent aléatoirement. Pour la bonne chanson, toutes les vraies correspondances vérifient $t_{\text{db}, k} = t_{\text{sample}, k} + t_0$, de sorte que tous les $\delta_k = t_0$ s’accumulent dans la même case de l’histogramme, formant un pic de Dirac géant !

Chapitre 6 : Le défi complémentaire — Le problème de la soirée cocktail et l’ICA (FastICA)

Que faire si, au lieu d’éliminer les voix du café, nous voulons séparer physiquement les $M$ locuteurs simultanés à partir du mélange $\mathbf{x}(t) = \mathbf{A}\mathbf{s}(t)$ sans connaître ni les voix $\mathbf{s}(t)$ ni la matrice de mélange $\mathbf{A}$ ? C’est le problème de la soirée cocktail (Colin Cherry, 1953) ou séparation aveugle de sources (BSS).

6.1 Pourquoi l’Analyse en Composantes Principales (PCA) échoue

Le blanchiment spatial (PCA Whitening) via la matrice de covariance $\mathbf{\Sigma}_x = \mathbb{E}[\mathbf{x}\mathbf{x}^\top] = \mathbf{E}\mathbf{\Lambda}\mathbf{E}^\top$ donne :

Les signaux $\mathbf{z}(t)$ sont décorrélés, mais $\mathbf{U} \in O(M)$ reste une matrice de rotation orthogonale inconnue ($\mathbf{U}\mathbf{U}^\top = \mathbf{I}$) ! Comme toute rotation $\mathbf{R}(\theta)\mathbf{z}$ préserve la covariance identité $\mathbf{I}$, les statistiques du second ordre sont aveugles à l’angle $\theta$.

6.2 Inverser le théorème central limite : Maximiser la non-gaussianité

L’Analyse en Composantes Indépendantes (ICA) (Comon 1994, Bell & Sejnowski 1995, Hyvärinen 1999) exploite le théorème central limite (TCL) à rebours :

1. Super-gaussianité de la voix humaine : Les silences inter-syllabiques ($s_i \approx 0$) et les impulsions vocaliques confèrent à la parole une distribution de Laplace à forte kurtosis ($\text{kurt}(y) = \mathbb{E}[y^4] - 3(\mathbb{E}[y^2])^2 \gg 0$).
2. Maximisation de la négentropie : Selon le TCL, toute combinaison linéaire $y = \mathbf{w}^\top \mathbf{z} = q_1 s_1 + q_2 s_2$ est plus gaussienne que les voix pures. En cherchant le vecteur unitaire $\mathbf{w}$ qui maximise la non-gaussianité via la négentropie $J(y) = H(y_{\text{gauss}}) - H(y) \propto (\mathbb{E}[G(y)] - \mathbb{E}[G(\nu)])^2$ avec $g(y) = \tanh(a_1 y)$, l’algorithme FastICA (méthode de Newton sur la sphère unité) isole chaque voix en 10 à 20 itérations :

  flowchart TD
    S["Voix originales indépendantes s(t)<br/>(Loi de Laplace super-gaussienne, Kurtosis >> 0)"] --> MIX["Mélange acoustique inconnu x(t) = A s(t)<br/>(Le théorème central limite rend le mélange plus gaussien)"]
    MIX --> WHITE["Étape 1 : Blanchiment spatial PCA<br/>z(t) = Λ^(-1/2) E^T x(t), Covariance E[zz^T] = I"]
    WHITE --> ROT["Inconnue restante : Rotation orthogonale U<br/>z(t) = U s(t) (Angle θ invisible au 2nd ordre)"]
    ROT --> ICA["Étape 2 : Analyse en Composantes Indépendantes (FastICA)<br/>Maximiser la non-gaussianité (Kurtosis / Négentropie J(y))"]
    ICA --> NEWTON["Itération de point fixe de Newton<br/>w+ ← E[z g(w^T z)] - E[g'(w^T z)]w"]
    NEWTON --> OUT["Ondes vocales séparées y(t) = W x(t)<br/>Séparation aveugle de sources réussie !"]

Chapitre 7 : Implémentation complète en Python (Shazam & FastICA)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

import numpy as np
from scipy.ndimage import maximum_filter
from collections import defaultdict

class ShazamFingerprinter:
    def __init__(self, fs=8000, n_fft=1024, hop_length=256, neighborhood=(15, 15), fan_out=10):
        self.fs, self.n_fft, self.hop_length = fs, n_fft, hop_length
        self.neighborhood, self.fan_out = neighborhood, fan_out
        self.database = defaultdict(list)

    def stft_spectrogram(self, signal):
        window = np.hanning(self.n_fft)
        n_frames = 1 + (len(signal) - self.n_fft) // self.hop_length
        spec = np.zeros((self.n_fft // 2, n_frames))
        for m in range(n_frames):
            frame = signal[m * self.hop_length : m * self.hop_length + self.n_fft] * window
            spec[:, m] = 10.0 * np.log10(np.abs(np.fft.rfft(frame)[:self.n_fft // 2])**2 + 1e-10)
        return spec

    def extract_peaks(self, spec, pct=85):
        mask = (maximum_filter(spec, size=self.neighborhood) == spec) & (spec > np.percentile(spec, pct))
        f_idx, t_idx = np.where(mask)
        order = np.argsort(t_idx)
        return list(zip(t_idx[order], f_idx[order]))

    def generate_hashes(self, peaks, dt_min=2, dt_max=60, df_max=150):
        hashes = []
        for i, (t1, f1) in enumerate(peaks):
            cnt = 0
            for t2, f2 in peaks[i + 1:]:
                dt = t2 - t1
                if dt < dt_min: continue
                if dt > dt_max: break
                if abs(f2 - f1) <= df_max:
                    h = (int(f1 & 0x3FF) << 20) | (int(f2 & 0x3FF) << 10) | int(dt & 0x3FF)
                    hashes.append((h, int(t1)))
                    cnt += 1
                    if cnt >= self.fan_out: break
        return hashes

    def recognize(self, snippet):
        q_hashes = self.generate_hashes(self.extract_peaks(self.stft_spectrogram(snippet)))
        hist = defaultdict(lambda: defaultdict(int))
        for h, t_s in q_hashes:
            for song_id, t_db in self.database.get(h, ()):
                hist[song_id][t_db - t_s] += 1
        best_song, best_votes, best_dt = None, 0, 0
        for song_id, counts in hist.items():
            dt, votes = max(counts.items(), key=lambda x: x[1])
            if votes > best_votes:
                best_song, best_votes, best_dt = song_id, votes, dt
        return best_song, best_votes, best_dt * self.hop_length / self.fs

def fast_ica(X, max_iter=200, tol=1e-7):
    m, n = X.shape
    Xc = X - np.mean(X, axis=1, keepdims=True)
    eigvals, eigvecs = np.linalg.eigh((Xc @ Xc.T) / n)
    Z = (np.diag(1.0 / np.sqrt(eigvals + 1e-12)) @ eigvecs.T) @ Xc
    W = np.eye(m)
    for _ in range(max_iter):
        WZ = W @ Z
        g, gp = np.tanh(WZ), 1.0 - np.tanh(WZ)**2
        W_new = (g @ Z.T) / n - np.diag(np.mean(gp, axis=1)) @ W
        u, _, vt = np.linalg.svd(W_new)
        W_new = u @ vt
        if np.max(np.abs(np.abs(np.diag(W_new @ W.T)) - 1.0)) < tol:
            break
        W = W_new
    return W @ Z