¿Cómo demonios funciona Shazam?
(perthirtysix.com/how-the-heck-does-shazam-work)- El reconocimiento musical funciona convirtiendo las vibraciones del aire captadas por el micrófono en una forma de onda, y luego comprimiéndola en un espectrograma y en un pequeño conjunto de picos de frecuencia intensos para crear la huella de una canción
- Como la forma de onda cruda cambia fácilmente según el volumen y el entorno de reproducción, es difícil usarla como criterio de identificación; al aplicar FFT a intervalos cortos se revela la estructura de frecuencias en el tiempo y se logra una comparación más estable
- Los picos que se conservan no se usan como puntos aislados, sino que se agrupan en pares de anchor y target zone para formar hashes; estas combinaciones funcionan como hashes de huella lo bastante específicos como para distinguir una grabación concreta
- La búsqueda no compara canción por canción, sino que usa una estructura hash-first que busca directamente por clave hash; al final también verifica si coinciden los intervalos de tiempo entre los hashes para aumentar la confiabilidad
- Aunque una base de datos masiva en servidor y un enfoque on-device difieren en escala y restricciones, la idea central es la misma: descartar la mayor parte de la información y quedarse solo con los picos landmark para encontrar rápidamente una canción incluso en clips cortos y ruidosos
El proceso de interpretar el sonido al revés
- El micrófono del teléfono mide las vibraciones del aire con un diafragma muy delgado y las convierte en una secuencia de números que representa la presión del aire a lo largo del tiempo, es decir, una forma de onda
- El tímpano humano recibe las mismas ondas de presión, pero el teléfono las trata no como sonido en sí, sino como una secuencia numérica
- El sonido entrante se muestrea decenas de miles de veces por segundo, normalmente a 44,100 Hz
- Con la forma de onda cruda sola es difícil identificar una canción; incluso la misma canción, si se reproduce más fuerte, puede generar una forma de onda totalmente distinta, y canciones diferentes también pueden producir formas parecidas
- Como el entorno de reproducción también puede cambiar la forma de onda de una misma canción, la forma de onda en sí no sirve bien como criterio de identificación
- Para reducir este problema, hay que dividir la forma de onda en fragmentos pequeños y aplicar FFT para descomponer qué frecuencias están presentes en cada instante
- Convertido en una pregunta, equivale a: "¿Qué tonos puros habría que sumar para reconstruir este pequeño fragmento de sonido?"
- Si apilas lateralmente los resultados de cada fragmento, obtienes un espectrograma compuesto por eje temporal, eje de frecuencia y eje de brillo
- La FFT aprovecha que cualquier forma de onda, por compleja que sea, puede expresarse como la suma de ondas sinusoidales con distintas frecuencias, amplitudes y fases
- Por ejemplo, si ingresas 1,024 muestras, devuelve un espectro que muestra cuánta energía hay en cada frecuencia
- En cada bin de frecuencia, multiplica y suma todas las muestras con la onda sinusoidal de esa frecuencia; si esa frecuencia está presente en la señal real, la suma crece, y si no, se cancela
- La clave de la FFT es la velocidad: una descomposición ingenua requeriría millones de operaciones por fragmento, pero la FFT usa simetrías matemáticas para reducirlo aproximadamente a n log n
- Gracias a esa velocidad, puede ejecutarse cientos de veces por segundo incluso en un teléfono
- El dispositivo va desplazando esta ventana sobre el audio, aplica FFT a cada fragmento y apila los resultados para construir el espectrograma
- Un ejemplo simple con un tono sintético de una sola frecuencia ayuda a entender la idea, pero la música real es mucho más compleja
- Si metes música real o un tarareo al micrófono, el espectrograma se ve mucho más desordenado, pero la FFT aun así revela estructura en tiempo real
- En el ejemplo del navegador, todo el audio se procesa dentro del navegador y no se graba ni se envía al exterior
Cuanto menos, más fuerte la huella
- El sistema no guarda todo el espectrograma, sino que lo comprime dejando solo los picos más altos como un conjunto disperso de puntos
- Al descartar las señales débiles y conservar solo los puntos más intensos, quedan únicamente los landmarks acústicamente importantes
- La razón para tirar la mayor parte de la información es que almacenar y buscar el espectrograma completo sería demasiado lento incluso para una computadora
- Cuanto más alto se fija el umbral, más desaparecen las señales tenues y solo sobreviven los picos grandes
- Este enfoque mejora la resistencia al ruido
- El ruido de fondo añade energía baja por todo el espectrograma, pero normalmente no llega a crear el pico más fuerte de una región específica
- Los landmarks que quedan son las frecuencias dominantes que logran sobresalir por encima del ruido
- En cambio, este método de huella suele rendir peor cuando alguien canta directamente la canción
- Incluso si canta muy bien, es probable que se generen hashes distintos a los de la grabación original
- Por eso, sistemas más recientes basados en machine learning procesan tarareos y canto a partir de la melodía, en lugar de depender de frecuencias exactas
Conectar puntos para crear hashes
- Un solo punto tiene poca capacidad de discriminación, pero la combinación de dos puntos es mucho menos casual y por eso sirve mejor como hash de huella
- Por ejemplo, una frecuencia de 1,200 Hz en cierto momento puede aparecer en miles de canciones, pero la combinación de 1,200 Hz seguida 0.3 segundos después por 2,400 Hz es mucho más específica
- El algoritmo toma cada pico por turno como anchor y define a su derecha una target zone con un rango de tiempo y frecuencia, emparejándolo con todos los picos dentro de esa zona
- Cada par genera un hash corto a partir de tres números: las dos frecuencias y la diferencia de tiempo
- Un hash funciona como un código corto que siempre produce el mismo resultado para la misma entrada, pero cambia por completo si la entrada se altera aunque sea un poco
- Los sistemas tipo Shazam tienen mecanismos para manejar pequeñas variaciones, pero en esencia el hash se construye a partir de frecuencias y tiempos exactos
- Como resultado, este hash funciona más como la huella de una grabación específica que de la canción en abstracto
- Por eso es más difícil acertar con covers o remixes
- Incluso una sola canción de 3 minutos puede producir miles de estos hashes de huella, y la base de datos los almacena todos
- El teléfono lleva unos pocos hashes obtenidos de un clip de 5 segundos, y la base de datos lleva millones de hashes extraídos de una enorme cantidad de canciones antes de pasar a la fase de matching
Encontrar la coincidencia exacta
- Cada hash se usa como una especie de dirección, y para cada hash obtenido del clip el sistema consulta directamente una tabla gigantesca para encontrar las canciones que contienen ese hash
- En lugar de recorrer canción por canción, accede usando el propio hash como clave
- El enfoque intuitivo song-first tendría que revisar cada canción una por una y comprobar superposiciones de hashes, por lo que se vuelve más lento a medida que crece el número de canciones
- El texto lo expresa como tiempo O(N)
- Con una base de datos de ejemplo y una lista de hashes de un clip de 5 segundos, se visualiza esta ineficiencia
- La computadora puede darle la vuelta y procesarlo con un enfoque hash-first
- Para cada hash, pregunta directamente: "¿Qué canciones contienen este hash?"
- Se compara con el índice al final de un libro: en vez de releer todas las páginas, vas directo a la entrada de una palabra concreta
- Este enfoque hace que la consulta quede cerca de O(1)
- Ya haya 100 canciones o 100 millones, el tiempo de procesamiento es aproximadamente similar
- Como la cantidad posible de hashes es enorme, incluso con millones de canciones cada dirección suele contener solo unos pocos elementos
- No basta con compartir el mismo hash; la verificación final ocurre en los intervalos de tiempo
- Por ejemplo, si dentro del clip 17403C y 19A998 están separados por 1.2 segundos, entonces en la canción candidata esos mismos dos hashes también deben aparecer separados por 1.2 segundos
- Solo cuando coinciden las diferencias temporales entre hashes y además hay suficientes coincidencias se obtiene un matching de alta confianza
- Todo el sistema está diseñado alrededor de tareas que las computadoras hacen especialmente bien
- Se centra en comparar números y consultar direcciones
- Por eso, incluso frente a millones de canciones, toda la búsqueda termina en mucho menos de 1 segundo
Enfoques más modernos
- Muchos servicios de reconocimiento de canciones como Shazam envían el clip de audio al servidor y realizan el matching en una gran base de datos de huellas alojada allí
- Usan esta arquitectura porque la base de datos es muy grande, cambia constantemente y la búsqueda requiere recursos de cómputo considerables
- En cambio, el reconocimiento on-device de Apple y Now Playing de Google Pixel se ejecutan completamente de forma local dentro del teléfono
- Usan una base de datos más pequeña y seleccionada, junto con modelos optimizados
- A cambio de no ser totalmente exhaustivos, priorizan la velocidad e incluyen enfoques de machine learning más sofisticados y resistentes al ruido y a transformaciones del audio
- El enfoque on-device es más rápido y funciona sin conexión a internet, pero tiene la limitación de que la base de datos de canciones que puede igualar es mucho más pequeña
- La incorporación de canciones nuevas también suele ser más lenta
- Si se detecta un cambio de ubicación, puede ser necesario volver a descargar nuevos datos
- Las diferencias en canciones populares por región también influyen en la composición de los datos on-device
- Los éxitos de Japón y los de Estados Unidos pueden ser distintos
- Tanto si el matching ocurre en el servidor como dentro del dispositivo, la técnica central es la misma
- Al descartar la mayor parte de la información y conservar solo unos pocos picos landmark, incluso un clip de 5 segundos grabado en una cafetería ruidosa se convierte en un conjunto de coordenadas lo bastante preciso como para señalar una canción entre millones
- La clave del reconocimiento no se parece tanto a escuchar mucho, sino a descartar con precisión lo que debe ignorarse
El paper en que se basa
- Buena parte del texto se basa en el paper de Avery Wang de 2003, An Industrial-Strength Audio Search Algorithm
- Si quieres profundizar en procesamiento de señales y diseño de sistemas, ese paper es el punto de partida más directo
- El flujo completo va desde la transformación de la forma de onda, selección de picos, hashes de pares de picos, consulta por índice invertido y verificación por alineación temporal
- La combinación de estas etapas es lo que permite identificar canciones rápidamente incluso con clips cortos y ruidosos
1 comentarios
Comentarios de Hacker News
Estaría bien ver también material sobre Shazam Está el artículo original: https://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf, y si de verdad te interesa, también vale la pena buscar la charla del autor en YouTube En https://news.ycombinator.com/item?id=18069968 hay una publicación de un empleado de Shazam, en https://news.ycombinator.com/item?id=38538996 hay una explicación aprobada por el cofundador, y en https://news.ycombinator.com/item?id=41127726 hay una recreación del algoritmo hecha en Go Al final, en ML, muchas veces el valor de los datos es mayor que el del código mismo
Mi hipótesis reciente es que tal vez no sea así en absoluto En música popular casi siempre acertó, pero varias veces intenté usar Shazam con unas piezas de synth bastante buenas que sonaron durante los descansos de una competencia de patinaje sobre hielo, y no encontró ni una correctamente Puede que todavía no se hubieran publicado o que fueran música extremadamente de nicho, pero también parece posible que Shazam simplemente haya fallado a lo grande
Esto obviamente es la misma familia de tecnología que se usa también en el ACR de la TV Pero da la impresión de que Shazam tiene mucha mejor reputación en línea porque respeta la intención y el consentimiento del usuario Si en la TV se implementara algo parecido, pero sin que los datos terminaran solo en la venta de publicidad, quizá podría existir una versión que realmente beneficie al consumidor
Este probablemente sea de los mejores materiales para explicar visualmente el algoritmo original de audio fingerprinting del artículo de Shazam de 2003 Aunque también parece probable que para estas alturas ya lo hayan reemplazado en algún momento por un modelo de ML
Hay un algoritmo llamado DTW(dynamic time warping) que suele pasarse por alto Mi intuición es que Shazam también debe haber usado esto en cierta medida
Reconocer la misma grabación no es tan difícil Si es la misma grabación, la progresión de acordes y el timing se pueden repetir con exactitud, así que este tipo de tecnología de reconocimiento existe desde hace mucho más de 10 años En cambio, identificar una canción a partir de otra grabación distinta, como una versión cover, es mucho más difícil Audible Magic afirma en https://www.audiblemagic.com/2024/02/07/identifying-cover-songs-live-performances-ai-clones-and-more/ que puede reconocer múltiples versiones en vivo de la misma canción e incluso parodias, pero obviamente eso usa AI y más cómputo
Pensé "otra vez este tema", pero luego vi que era SCP Este dominio se ve algo sospechoso Una explicación más completa que la publicación de CameronMacLeod de 2022 es https://news.ycombinator.com/item?id=38531428, y la publicación de Slate de 2009 es https://news.ycombinator.com/item?id=893353
Debería agregar esto a mi lista de proyectos El Dinosaur game, pero haciendo que salte no con una tecla sino con un quiquiriquí
Me pregunto si hay alguna forma de impedir que apps como Shazam lo detecten No sé, mezclar ruido u otra técnica parecida
Hice esto como proyecto de ciencias en 1986 con una Apple ][c