Imagine estar dentro de uma cafeteria movimentada: a máquina de expresso sibila com vapor de alta pressão, xícaras batem nos pires e dezenas de conversas se sobrepõem. De um alto-falante simples no teto, mal se ouve uma melodia. Você pega o smartphone, toca num botão e ergue o microfone por apenas três segundos. Em menos de um segundo, a tela exibe o título exato da música, o artista, a capa do álbum e até a letra sincronizada no tempo exato da reprodução — digamos, aos 2 minutos e 14 segundos.

Sob a ótica da teoria da informação e do processamento digital de sinais (DSP), essa mágica cotidiana resolve quatro desafios matemáticos extremos:

1. Relação sinal-ruído catastrófica (\(\text{SNR} < -10\,\text{dB}\)): Mais de 90% da energia acústica captada pelo microfone consiste em ruído ambiente aditivo (vozes, pratos, vapor).
2. Resposta ao impulso da sala desconhecida: O áudio original \(s(t)\) sofre distorção no alto-falante e reverberação nas paredes (convolução com \(h_{\text{room}}(t)\)), resultando em \(x(t) = (s * h_{\text{room}})(t) + n(t)\).
3. Deslocamento temporal arbitrário (\(t_0\) desconhecido): O trecho de 3 segundos \([t_0, t_0 + 3\,\text{s}]\) começa em qualquer ponto desconhecido da faixa.
4. Espaço de busca de 100 milhões de músicas (\(10^8\) faixas): Mais de 1.000 anos de áudio contínuo precisam ser vasculhados em poucos centenas de milissegundos.

Neste artigo, dissecamos a arquitetura em quatro estágios da impressão digital acústica do Shazam criada por Avery Li-Chun Wang em 2003 (“An Industrial-Strength Audio Search Algorithm”, ISMIR) e exploramos seu problema dual: o Problema da Festa de Coquetel (Cocktail Party Problem) e a Separação Cega de Fontes (BSS) via Análise de Componentes Independentes (ICA / FastICA).

Capítulo 1: Por que a correlação direta de onda e o hash criptográfico falham completamente

Funções de hash criptográficas (SHA-256, MD5) possuem o efeito avalanche: alterar um único bit na entrada inverte aleatoriamente 50% dos bits de saída. Qualquer compressão MP3 ou ruído térmico destrói o hash.

Por sua vez, calcular a correlação cruzada no domínio do tempo \(R_{x s_i}[\tau] = \sum_{n=0}^{L-1} x[n]\, s_i[n + \tau]\) em \(10^8\) músicas (a \(f_s = 8000\,\text{Hz}\), \(L = 24.000\) amostras em 3 segundos) exige testar \(1{,}92 \times 10^{14}\) posições \(\tau\), totalizando \(4{,}6 \times 10^{18}\) operações (4,6 ExaFLOPs) por consulta! Além disso, as reflexões da sala \(h_{\text{room}}(t)\) distorcem a fase da forma de onda \(x[n]\), derrubando a correlação temporal para zero, embora a cóclea humana (insensível à fase segundo Helmholtz) reconheça a música sem dificuldade.

Capítulo 2: Estágio 1 — Transformada de Fourier de Tempo Curto (STFT) e incerteza de Gabor-Heisenberg

Para eliminar a sensibilidade à fase, o Estágio 1 converte o sinal 1D \(x[n]\) (subamostrado para \(f_s = 8000\,\text{Hz}\)) em um espectrograma 2D tempo-frequência usando uma janela de Hann \(w[n] = 0{,}5 - 0{,}5\cos\left(\frac{2\pi n}{N-1}\right)\) de tamanho \(N\) e passo \(H\):

A escolha de \(N\) obedece ao princípio da incerteza tempo-frequência de Gabor-Heisenberg:

Um \(N\) muito grande (\(4096\)) oferece alta resolução de frequência, mas borra ataques de percussão por \(\Delta t = 512\,\text{ms}\); um \(N\) muito pequeno (\(128\)) localiza transientes, mas mistura semitons vizinhos (\(\Delta f = 62{,}5\,\text{Hz}\)). O Shazam adota o equilíbrio ideal \(N = 1024\) (\(\Delta t = 128\,\text{ms}\), \(\Delta f = 7{,}8125\,\text{Hz}\)).

Capítulo 3: Estágio 2 — Extração esparsa de picos: O «Mapa de Constelações»

Para sobreviver a \(\text{SNR} < -10\,\text{dB}\), Avery Wang descarta 99,9% do espectrograma e retém apenas as coordenadas \((t_i, f_i)\) dos máximos locais 2D dentro de uma vizinhança \(\mathcal{N}(m_i, k_i)\):

Plotados no plano \((t, f)\), esses pontos lembram estrelas no céu noturno — daí o nome Constellation Map (Mapa de Constelações).

1. Picos de montanha que furam a neblina: O ruído de fundo eleva o «nível do mar», submergindo os vales, mas os picos espectrais mais altos (ataques de caixa, formantes vocais) continuam emergindo exatamente nas mesmas coordenadas \((t_i, f_i)\).
2. Invariância a equalização (EQ) e ganho (AGC): A amplitude \(S(t_i, f_i)\) é totalmente descartada! Apenas o par \((t_i, f_i)\) é salvo, garantindo imunidade total ao volume do microfone e ao filtro \(|H_{\text{room}}(f)|^2\).

Capítulo 4: Estágio 3 — Hashing combinatório de 32 bits de pares Âncora-Alvo

Indexar picos isolados apenas pela frequência \(f_i \in [0, 1023]\) (10 bits = 1.024 gavetas) geraria centenas de milhões de colisões.

A solução genial de Wang foi o pareamento combinatório Âncora-Alvo (Combinatorial Hashing): Cada ponto âncora \(p_1 = (t_1, f_1)\) é pareado com até \(F \approx 10\) (fator de fan-out) pontos-alvo \(p_2 = (t_2, f_2)\) numa zona-alvo à frente no tempo (\(\Delta t = t_2 - t_1 \in [\tau_{\min}, \tau_{\max}]\)). As duas frequências e sua diferença de tempo relativa \(\Delta t = t_2 - t_1\) são compactadas em um único hash inteiro de 32 bits \(h\):

• Um milhão de vezes menos colisões: O espaço de hash salta de 10 bits (\(10^3\) gavetas) para 30 bits (\(2^{30} \approx 1{,}07 \times 10^9\) gavetas).
• Invariância exata à translação temporal: Como \(\Delta t' = (t_2 - t_0) - (t_1 - t_0) = t_2 - t_1\), o instante inicial desconhecido \(t_0\) cancela-se algebricamente! Mesmo que 70% dos picos sejam destruídos pelo ruído (\(p = 0{,}3\)), \(p^2 = 9\,\%\) dos pares sobrevivem intactos.

  flowchart TD
    A["Áudio do microfone x(t)<br/>(3 segundos, SNR < -10 dB, início t0 desconhecido)"] --> B["Estágio 1: Transformada de Fourier de Tempo Curto (STFT)<br/>Janela de Hann w[n], Espectrograma S(m, k) = |X(m, k)|²"]
    B --> C["Estágio 2: Extração do Mapa de Constelações<br/>Manter apenas máximos locais 2D (t_i, f_i)"]
    C --> D["Estágio 3: Pareamento combinatório Âncora-Alvo<br/>Unir âncora (t1, f1) com alvos (t2, f2)"]
    D --> E["Hash de 30 bits invariante à translação<br/>h = (f1 << 20) | (f2 << 10) | (t2 - t1)"]
    E --> F["Estágio 4: Busca O(1) no índice invertido<br/>Obter lista candidata (Song_ID, t_db)"]
    F --> G["Histograma de diferenças temporais<br/>Votar em δ = t_db - t_sample"]
    G --> H["Pico delta de Dirac no histograma!<br/>Identificação de Song_ID e posição exata δ = t0"]

Capítulo 5: Estágio 4 — Índice invertido e histograma de coincidência temporal (\(\Delta T\))

Para cada correspondência \((\text{Song\_ID}, t_{\text{db}, k})\) no índice invertido, o servidor calcula a diferença de deslocamento temporal:

Em músicas incorretas, \(\delta_k\) espalha-se aleatoriamente. Na música correta, todos os acertos verdadeiros obedecem a \(t_{\text{db}, k} = t_{\text{sample}, k} + t_0\), de modo que todos os \(\delta_k = t_0\) acumulam-se no mesmo compartimento do histograma, formando um pico delta de Dirac gigante.

Capítulo 6: O desafio complementar — O Problema do Coquetel e Separação Cega (ICA)

E se, em vez de descartar as vozes da cafeteria, quisermos separar fisicamente as \(M\) vozes simultâneas a partir da mistura \(\mathbf{x}(t) = \mathbf{A}\mathbf{s}(t)\) sem conhecer as vozes \(\mathbf{s}(t)\) nem a matriz de mistura \(\mathbf{A}\)? Esse é o Problema da Festa de Coquetel (Colin Cherry, 1953) ou Separação Cega de Fontes (BSS).

6.1 Por que a Análise de Componentes Principais (PCA) falha

O branqueamento espacial (PCA Whitening) via covariância \(\mathbf{\Sigma}_x = \mathbb{E}[\mathbf{x}\mathbf{x}^\top] = \mathbf{E}\mathbf{\Lambda}\mathbf{E}^\top\) produz:

Embora \(\mathbf{z}(t)\) seja descorrelacionado, \(\mathbf{U} \in O(M)\) continua sendo uma matriz de rotação ortogonal desconhecida (\(\mathbf{U}\mathbf{U}^\top = \mathbf{I}\)). Como qualquer rotação \(\mathbf{R}(\theta)\mathbf{z}\) preserva a covariância identidade \(\mathbf{I}\), estatísticas de segunda ordem são cegas ao ângulo \(\theta\).

6.2 Invertendo o Teorema Central do Limite: Maximizar a não-gaussianidade (FastICA)

A Análise de Componentes Independentes (ICA) (Comon 1994, Bell & Sejnowski 1995, Hyvärinen 1999) inverte o Teorema Central do Limite (TCL):

1. Supergaussianidade da fala humana: As pausas entre sílabas (\(s_i \approx 0\)) e os picos vocálicos seguem uma distribuição de Laplace com alta curtose (\(\text{kurt}(y) = \mathbb{E}[y^4] - 3(\mathbb{E}[y^2])^2 \gg 0\)).
2. Maximização da negentropia: Pelo TCL, qualquer mistura \(y = \mathbf{w}^\top \mathbf{z} = q_1 s_1 + q_2 s_2\) é mais gaussiana que as vozes originais. Ao buscar o vetor unitário \(\mathbf{w}\) que maximiza a não-gaussianidade via negentropia \(J(y) = H(y_{\text{gauss}}) - H(y) \propto (\mathbb{E}[G(y)] - \mathbb{E}[G(\nu)])^2\) com \(g(y) = \tanh(a_1 y)\), a iteração de ponto fixo de Newton do FastICA isola cada voz em 10 a 20 passos:

  flowchart TD
    S["Vozes originais independentes s(t)<br/>(Distribuição de Laplace supergaussiana, Curtose >> 0)"] --> MIX["Mistura acústica desconhecida x(t) = A s(t)<br/>(O Teorema Central do Limite aproxima a mistura de uma gaussiana)"]
    MIX --> WHITE["Passo 1: Branqueamento espacial PCA<br/>z(t) = Λ^(-1/2) E^T x(t), Covariância E[zz^T] = I"]
    WHITE --> ROT["Incógnita restante: Rotação ortogonal U<br/>z(t) = U s(t) (Ângulo θ invisível à 2ª ordem)"]
    ROT --> ICA["Passo 2: Análise de Componentes Independentes (FastICA)<br/>Maximizar não-gaussianidade (Curtose / Negentropia J(y))"]
    ICA --> NEWTON["Iteração de ponto fixo de Newton<br/>w+ ← E[z g(w^T z)] - E[g'(w^T z)]w"]
    NEWTON --> OUT["Ondas de voz limpas e separadas y(t) = W x(t)<br/>Separação cega de fontes concluída!"]

Capítulo 7: Implementação completa em 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