Imagina estar en medio de una cafetería bulliciosa: la máquina de espresso silba con vapor a alta presión, los platos entrechocan y decenas de personas conversan simultáneamente. Desde un altavoz barato en el techo apenas se distingue una melodía. Sacas tu teléfono, tocas un botón y sostienes el micrófono en el aire durante solo tres segundos. En menos de un segundo, la pantalla muestra el título exacto de la canción, el artista, la portada del álbum e incluso la letra sincronizada en el instante preciso (por ejemplo, en el minuto 2:14).
Desde la teoría de la información y el procesamiento digital de señales (DSP), esta proeza cotidiana resuelve cuatro desafíos matemáticos extremos:
- Relación señal-ruido catastrófica ($\text{SNR} < -10\,\text{dB}$): Más del 90 % de la energía acústica captada por el micrófono proviene de ruido ambiental aditivo (voces, golpes, máquinas).
- Respuesta al impulso de la sala desconocida: La señal original $s(t)$ sufre distorsión en el altavoz y reverberación multicamino en paredes y techo (convolución con $h_{\text{room}}(t)$), observándose únicamente $x(t) = (s * h_{\text{room}})(t) + n(t)$.
- Desfase temporal arbitrario ($t_0$ desconocido): El fragmento de 3 segundos $[t_0, t_0 + 3\,\text{s}]$ comienza en cualquier punto desconocido de la canción.
- Espacio de búsqueda de 100 millones de canciones ($10^8$ pistas): Más de 1.000 años de audio continuo deben consultarse en pocos cientos de milisegundos.
En este artículo desglosamos la arquitectura en cuatro etapas de la huella acústica de Shazam formulada por Avery Li-Chun Wang en 2003 (“An Industrial-Strength Audio Search Algorithm”, ISMIR) y abordamos su problema dual: el problema de la fiesta de cóctel (Cocktail Party Problem) y la separación ciega de fuentes (BSS) mediante Análisis de Componentes Independientes (ICA / FastICA).
Capítulo 1: Por qué fallan la correlación directa de ondas y el hashing criptográfico
Las funciones hash criptográficas (SHA-256, MD5) están diseñadas con efecto avalancha: cambiar un solo bit de entrada invierte aleatoriamente el 50 % de los bits de salida. Cualquier compresión MP3 o mínimo ruido térmico destruye por completo el hash.
Por otro lado, calcular la correlación cruzada en el dominio del tiempo $R_{x s_i}[\tau] = \sum_{n=0}^{L-1} x[n]\, s_i[n + \tau]$ sobre $10^8$ canciones (a $f_s = 8000\,\text{Hz}$, $L = 24.000$ muestras en 3 segundos) implica evaluar $1{,}92 \times 10^{14}$ posiciones de deslizamiento $\tau$, requiriendo $4{,}6 \times 10^{18}$ operaciones (4,6 ExaFLOPs) por consulta. Además, las reflexiones de la sala $h_{\text{room}}(t)$ distorsionan la fase de la onda $x[n]$, hundiendo la correlación temporal a cero aunque el oído humano (insensible a la fase según Helmholtz) reconozca perfectamente la melodía.
Capítulo 2: Etapa 1 — Transformada de Fourier de Tiempo Corto (STFT) e incertidumbre de Gabor-Heisenberg
Para eliminar la sensibilidad a la fase, la Etapa 1 transforma la señal 1D $x[n]$ (submuestreada a $f_s = 8000\,\text{Hz}$) en un espectrograma 2D tiempo-frecuencia aplicando una ventana de Hann $w[n] = 0{,}5 - 0{,}5\cos\left(\frac{2\pi n}{N-1}\right)$ de longitud $N$ y salto $H$:
$$X(m, k) = \sum_{n=0}^{N-1} x[n + mH]\, w[n]\, e^{-i \frac{2\pi k n}{N}}, \qquad S(m, k) = |X(m, k)|^2$$La elección de $N$ está regida por el principio de incertidumbre tiempo-frecuencia de Gabor-Heisenberg:
$$\sigma_t \cdot \sigma_\omega \ge \frac{1}{2} \quad \Longleftrightarrow \quad \Delta t \cdot \Delta f = \left(\frac{N}{f_s}\right) \cdot \left(\frac{f_s}{N}\right) = 1$$Un $N$ demasiado grande ($4096$) ofrece gran resolución frecuencial pero difumina los golpes de batería durante $\Delta t = 512\,\text{ms}$; un $N$ demasiado pequeño ($128$) localiza ataques pero mezcla semitonos vecinos ($\Delta f = 62{,}5\,\text{Hz}$). Shazam elige el punto óptimo $N = 1024$ ($\Delta t = 128\,\text{ms}$, $\Delta f = 7{,}8125\,\text{Hz}$).
Capítulo 3: Etapa 2 — Extracción dispersa de picos: El «Mapa de Constelaciones»
Para resistir un $\text{SNR} < -10\,\text{dB}$, Avery Wang descarta el 99,9 % del espectrograma y conserva únicamente las coordenadas $(t_i, f_i)$ de los máximos locales 2D dentro de una vecindad $\mathcal{N}(m_i, k_i)$:
$$(m_i, k_i) \in \mathcal{P} \iff S(m_i, k_i) > S(m, k) \quad \forall (m, k) \in \mathcal{N}(m_i, k_i) \setminus \{(m_i, k_i)\}$$Al graficar estos puntos sobre el plano $(t, f)$, parecen estrellas en el cielo nocturno, recibiendo el nombre de Constellation Map (Mapa de Constelaciones).
- Cumbres que sobresalen de la niebla: El ruido de fondo eleva el «nivel del mar», sumergiendo los valles, pero las cumbres espectrales más altas (transitorios de caja, formantes vocales) siguen emergiendo exactamente en las mismas coordenadas $(t_i, f_i)$.
- Invariancia frente a ecualización (EQ) y ganancia (AGC): ¡La amplitud $S(t_i, f_i)$ se descarta por completo! Solo se guarda el par $(t_i, f_i)$, logrando inmunidad total al volumen del micrófono y al filtrado $|H_{\text{room}}(f)|^2$.
Capítulo 4: Etapa 3 — Hashing combinatorio de 32 bits de pares Ancla-Objetivo
Indexar picos individuales por su sola frecuencia $f_i \in [0, 1023]$ (10 bits = 1.024 cubetas) produciría cientos de millones de colisiones.
La genialidad de Wang fue el emparejamiento combinatorio Ancla-Objetivo (Combinatorial Hashing): Cada punto ancla $p_1 = (t_1, f_1)$ se empareja con hasta $F \approx 10$ (factor de fan-out) puntos objetivo $p_2 = (t_2, f_2)$ dentro de una zona adelantada en el tiempo ($\Delta t = t_2 - t_1 \in [\tau_{\min}, \tau_{\max}]$). Las dos frecuencias y su diferencia temporal relativa $\Delta t = t_2 - t_1$ se empaquetan en un hash entero de 32 bits $h$:
$$h = \text{Hash}(f_1,\; f_2,\; t_2 - t_1) = (f_1 \ll 20) \;\mid\; (f_2 \ll 10) \;\mid\; (\Delta t)$$- Un millón de veces menos colisiones: El espacio hash pasa de 10 bits ($10^3$ cubetas) a 30 bits ($2^{30} \approx 1{,}07 \times 10^9$ cubetas).
- Invariancia exacta al desplazamiento temporal: Como $\Delta t' = (t_2 - t_0) - (t_1 - t_0) = t_2 - t_1$, ¡el instante inicial desconocido $t_0$ se cancela algebraicamente! Incluso si el ruido destruye el 70 % de los picos ($p = 0{,}3$), sobrevive el $p^2 = 9\,\%$ de los pares.
flowchart TD
A["Audio del micrófono x(t)<br/>(3 segundos, SNR < -10 dB, inicio t0 desconocido)"] --> B["Etapa 1: Transformada de Fourier de Tiempo Corto (STFT)<br/>Ventana de Hann w[n], Espectrograma S(m, k) = |X(m, k)|²"]
B --> C["Etapa 2: Extracción del Mapa de Constelaciones<br/>Conservar solo máximos locales 2D (t_i, f_i)"]
C --> D["Etapa 3: Emparejamiento combinatorio Ancla-Objetivo<br/>Unir ancla (t1, f1) con objetivos (t2, f2)"]
D --> E["Hash de 30 bits invariante a la traslación<br/>h = (f1 << 20) | (f2 << 10) | (t2 - t1)"]
E --> F["Etapa 4: Búsqueda O(1) en índice invertido<br/>Obtener lista candidata (Song_ID, t_db)"]
F --> G["Histograma de diferencias temporales<br/>Votar por δ = t_db - t_sample"]
G --> H["¡Pico delta de Dirac en el histograma!<br/>Identificación de Song_ID y posición exacta δ = t0"]
Capítulo 5: Etapa 4 — Índice invertido e histograma de coincidencia temporal ($\Delta T$)
Para cada coincidencia $(\text{Song\_ID}, t_{\text{db}, k})$ en el índice invertido, el servidor calcula la diferencia de desfase temporal:
$$\delta_k = t_{\text{db}, k} - t_{\text{sample}, k}$$En canciones incorrectas, $\delta_k$ se dispersa al azar. En la canción correcta, todos los aciertos verdaderos cumplen $t_{\text{db}, k} = t_{\text{sample}, k} + t_0$, por lo que todos los $\delta_k = t_0$ caen en la misma celda del histograma formando un pico delta de Dirac gigante.
| Métrica | Correlación cruzada temporal | Hash criptográfico (SHA-256) | Huella Chroma (Chromaprint) | Shazam Constelación + Hash combinatorio |
|---|---|---|---|---|
| Representación | Muestras PCM $x[n]$ | Flujo de bytes bruto | Vectores de 12 semitonos | Pares de picos STFT $(f_1, f_2, \Delta t)$ |
| Robustez a $-10\,\text{dB}$ | Muy baja (fase y ruido) | Nula (efecto avalancha) | Moderada | Excepcional (cumbres sobre el ruido) |
| Fragmento de 3s ($t_0$) | Escaneo de $10^{14}$ posiciones | Imposible | Ventana deslizante | Invariancia exacta ($\Delta t$ cancela $t_0$) |
| Complejidad ($10^8$ pistas) | $O(N_{\text{songs}} \cdot L^2)$ (horas) | $O(1)$ (inútil con ruido) | Búsqueda sublineal | Índice invertido $O(1)$ + histograma $O(1)$ |
Capítulo 6: El problema complementario — El efecto fiesta de cóctel y separación ciega (ICA)
¿Y si en lugar de descartar las voces de la cafetería queremos separar físicamente las $M$ voces superpuestas a partir de la mezcla $\mathbf{x}(t) = \mathbf{A}\mathbf{s}(t)$ sin conocer las voces $\mathbf{s}(t)$ ni la matriz de mezcla $\mathbf{A}$? Este es el problema de la fiesta de cóctel (Colin Cherry, 1953) o separación ciega de fuentes (BSS).
6.1 Por qué falla el Análisis de Componentes Principales (PCA)
El blanqueamiento espacial (PCA Whitening) mediante la covarianza $\mathbf{\Sigma}_x = \mathbb{E}[\mathbf{x}\mathbf{x}^\top] = \mathbf{E}\mathbf{\Lambda}\mathbf{E}^\top$ produce:
$$\mathbf{z}(t) = \mathbf{\Lambda}^{-1/2} \mathbf{E}^\top \mathbf{x}(t) = \mathbf{U}\mathbf{s}(t), \qquad \mathbb{E}\!\left[\mathbf{z}\mathbf{z}^\top\right] = \mathbf{I}$$Aunque $\mathbf{z}(t)$ está incorrelacionado, $\mathbf{U} \in O(M)$ sigue siendo una matriz de rotación ortogonal desconocida ($\mathbf{U}\mathbf{U}^\top = \mathbf{I}$). Como cualquier rotación $\mathbf{R}(\theta)\mathbf{z}$ mantiene la covarianza identidad $\mathbf{I}$, las estadísticas de segundo orden son ciegas al ángulo $\theta$.
6.2 Invertir el Teorema del Límite Central: Maximizar la no gaussianidad (FastICA)
El Análisis de Componentes Independientes (ICA) (Comon 1994, Bell & Sejnowski 1995, Hyvärinen 1999) invierte el Teorema del Límite Central (TLC):
- Supergaussianidad del habla humana: Las pausas entre sílabas ($s_i \approx 0$) y los picos vocálicos siguen una distribución de Laplace con alta curtosis ($\text{kurt}(y) = \mathbb{E}[y^4] - 3(\mathbb{E}[y^2])^2 \gg 0$).
- Maximización de la negentropía: Por el TLC, cualquier mezcla $y = \mathbf{w}^\top \mathbf{z} = q_1 s_1 + q_2 s_2$ es más gaussiana que las fuentes puras. Al buscar el vector unitario $\mathbf{w}$ que maximiza la no gaussianidad mediante la negentropía $J(y) = H(y_{\text{gauss}}) - H(y) \propto (\mathbb{E}[G(y)] - \mathbb{E}[G(\nu)])^2$ con $g(y) = \tanh(a_1 y)$, la iteración de punto fijo de Newton de FastICA separa cada voz en 10–20 pasos:
flowchart TD
S["Voces originales independientes s(t)<br/>(Distribución de Laplace supergaussiana, Curtosis >> 0)"] --> MIX["Mezcla acústica desconocida x(t) = A s(t)<br/>(El Teorema del Límite Central acerca la mezcla a una gaussiana)"]
MIX --> WHITE["Paso 1: Blanqueamiento espacial PCA<br/>z(t) = Λ^(-1/2) E^T x(t), Covarianza E[zz^T] = I"]
WHITE --> ROT["Incógnita restante: Rotación ortogonal U<br/>z(t) = U s(t) (Ángulo θ invisible al 2º orden)"]
ROT --> ICA["Paso 2: Análisis de Componentes Independientes (FastICA)<br/>Maximizar no gaussianidad (Curtosis / Negentropía J(y))"]
ICA --> NEWTON["Iteración de punto fijo de Newton<br/>w+ ← E[z g(w^T z)] - E[g'(w^T z)]w"]
NEWTON --> OUT["Ondas de voz limpias y separadas y(t) = W x(t)<br/>¡Separación ciega de fuentes completada!"]
Capítulo 7: Implementación completa en Python (Shazam & FastICA)
| |