Cómo funciona Shazam (2022)

 (cameronmacleod.com)
2 puntos por GN⁺ 2023-12-06 | 1 comentarios | Compartir por WhatsApp
  • Shazam encuentra una canción con solo unos segundos de grabación de micrófono creando una huella digital de audio (fingerprint) y buscándola en una base de datos, en lugar de comparar todo el audio completo
  • Comparar la forma de onda desplazándola tal cual no es realista a escala de 10 millones de canciones, ni funciona bien por el ruido del micrófono, los cambios de volumen y los efectos de frecuencia
  • El flujo clave consiste en convertir el audio en un spectrogram, encontrar los picos de frecuencia intensos y luego guardar pares de picos como hashes para compararlos rápidamente
  • Los picos tienden a mantenerse relativamente bien incluso con ruido y reducen la cantidad de datos almacenados, pero deben distribuirse de manera uniforme en tiempo y frecuencia para poder reconocer cualquier parte de una canción
  • En la etapa de reconocimiento, las diferencias Track time - Sample time de los hashes coincidentes se agrupan en un histograma, y se elige como respuesta la canción que más se concentra en un mismo bin

El problema que Shazam tiene que resolver

  • Shazam es una app que graba durante unos segundos una canción que está sonando alrededor y luego la busca en una base de datos para mostrar el resultado
  • Antes de convertirse en app, Shazam era un servicio basado en número telefónico
    • El usuario llamaba a un número y tenía que acercar el micrófono del celular hacia la música
    • Después de 30 segundos, Shazam cortaba la llamada y enviaba por SMS la información de la canción que había escuchado
    • En 2002, la calidad de las llamadas móviles hacía todavía más difícil el reconocimiento de canciones
  • En un ejemplo pequeño, se podría mover poco a poco un fragmento de audio sobre toda la pista para comprobar si coincide
    • Pero si se busca en una base de datos de 10 millones de canciones sin saber de cuál se trata, el tiempo aumenta muchísimo
  • Las muestras reales tomadas por micrófono pueden cambiar su forma de onda por ruido de fondo, efectos de frecuencia y variaciones de volumen, así que una comparación simple por desplazamiento no encaja bien

Flujo general del sistema

  • El método de Shazam se divide en los flujos de register y recognise
    • register es el flujo para guardar canciones y poder encontrarlas después
    • recognise es el flujo para identificar a qué canción pertenece un fragmento corto de audio
  • Ambos flujos pasan por la misma etapa de preprocesamiento
    • cálculo del spectrogram del audio
    • búsqueda de los picos de frecuencia más intensos dentro del spectrogram
    • generación de hashes agrupando esos picos en pares
  • El flujo de register guarda en la base de datos los hashes calculados
  • El flujo de recognise compara los hashes creados a partir de un audio nuevo con los hashes de la base de datos para identificar la canción en la etapa de matching

Cálculo del spectrogram

  • La transformada de Fourier indica qué frecuencias contiene un audio
    • Si se aplica la transformada de Fourier a una onda seno de 20Hz, aparece un gran spike cerca de 20Hz
    • Como una onda seno contiene una sola frecuencia, también se le llama pure tone
  • El resultado de la transformada de Fourier es el frequency spectrum
    • La representación centrada en el eje del tiempo es el time domain
    • La representación centrada en el eje de frecuencia es el frequency domain
    • El eje Y del frequency spectrum muestra la intensidad de cada componente de frecuencia, y los componentes más intensos se oyen con más claridad en la señal del time domain
  • Si se suman varias ondas seno, sus componentes de frecuencia se combinan
    • Si a una onda seno de 20Hz se le suma una onda seno de 50Hz con la mitad de intensidad, aparecen un spike de 20Hz y otro más pequeño de 50Hz
    • Todas las señales de audio pueden reconstruirse a partir de este tipo de ondas
  • El frequency domain revela información que no se ve con claridad en el time domain
    • Aunque se agregue ruido y cambie la forma en el time domain, en el frequency domain los spikes principales de frecuencia pueden seguir viéndose claramente
  • Si se aplica una sola vez la transformada de Fourier a toda la canción, solo se ve la intensidad total de las frecuencias, pero en una canción real las frecuencias cambian con el tiempo
    • Si se divide la canción en pequeños segmentos, se aplica la transformada de Fourier a cada uno y luego se combinan, se obtiene un spectrogram
    • El spectrogram representa al mismo tiempo tiempo, frecuencia e intensidad, y la intensidad puede mostrarse con colores
  • En el spectrogram del ejemplo, “Like a Stone”, los puntos más brillantes, es decir, la mayoría de las frecuencias intensas, aparecen por debajo de 5000Hz
    • Esta distribución es común en la música, y la mayor parte del rango de frecuencias del piano está entre 27Hz y 4186Hz

Fingerprint basado en picos

  • La huella digital de audio comienza encontrando picos en el spectrogram
    • Un pico es el componente de frecuencia más grande en un instante específico
    • En música, un sonido fuerte como el de un solo de guitarra puede convertirse en el pico de ese momento
  • Los picos son relativamente menos sensibles al ruido
    • Para que el ruido vuelva irreconocible un pico, tendría que ser más grande que ese pico
    • Un pico del spectrogram es uno de los componentes de frecuencia más intensos de la pista
  • Si se guardan solo los picos, se reduce la cantidad de datos necesaria para el fingerprint
    • En lugar de guardar toda la información de frecuencia, se conservan solo los componentes de frecuencia más intensos
    • Al reducir los datos a buscar, la búsqueda del fingerprint se vuelve más rápida
  • Los picos deben distribuirse de forma uniforme tanto en tiempo como en frecuencia
    • Si se concentran solo en una parte del tiempo, no se podrán reconocer muestras de otras secciones de la canción
    • Si se concentran en una banda de frecuencia estrecha, un ruido fuerte en esa banda, como una bocina de auto, puede cambiar la selección de picos y dificultar el reconocimiento de esa sección

Encontrar picos con maximum filter

  • Para encontrar picos de manera uniforme, se puede usar la técnica de procesamiento de imágenes maximum filter
  • maximum filter busca el valor máximo dentro del vecindario alrededor de cada pixel y cambia ese pixel por el valor de ese máximo local
    • El ejemplo usa una región de 3x3 alrededor de cada pixel
    • Este proceso expande los picos locales hacia el área vecina
  • El spectrogram al que se le aplica maximum filter se ve como una versión de baja resolución del spectrogram original
    • Esto pasa porque los picos de la señal se expanden y ocupan otros pixeles
    • Los cuadros del mismo color corresponden a un mismo pico local de la imagen original
  • maximum filter tiene como parámetro el tamaño de la caja usada para encontrar máximos locales
    • Si se usa una caja pequeña, aparecen más picos
    • Si se usa una caja grande, aparecen menos picos
  • La posición de los picos se recupera encontrando los puntos donde el valor del spectrogram original y el del spectrogram filtrado son iguales
    • Los puntos que no son picos cambian al valor del pico local y por eso ya no coinciden
    • Solo los puntos cuyo valor se mantiene igual son picos
  • Si se dibujan todos los picos juntos, se obtiene un constellation map
    • Recibe ese nombre porque parece una imagen del cielo nocturno
  • La cantidad de picos afecta directamente el tamaño del fingerprint
    • Si hay que almacenar millones de canciones, es importante mantener pequeño el fingerprint
    • Si se reducen los picos, también baja la precisión y disminuyen las posibilidades de hacer matching correcto con la muestra
  • Hay dos formas de reducir la cantidad de picos
    • usar los N picos principales, donde N debe ser proporcional a la duración del audio para que las canciones cortas no queden sobrerrepresentadas
    • usar todos los picos por encima de cierto threshold, lo que no garantiza un tamaño de fingerprint por hora, pero puede ser más preciso

Convertir pares de picos en hashes

  • Si el fingerprint fuera solo un conjunto de picos individuales del spectrogram, la redundancia crecería muy rápido
    • Si la frecuencia de cada pico se representa con 10 bits, se pueden representar 2^10=1024 frecuencias individuales
    • Si hay miles de puntos por pista, habrá muchas repeticiones
  • La unicidad del fingerprint es importante
    • Cuanto mayor sea la unicidad, más rápida será la búsqueda
    • También ayuda a reconocer más canciones
  • El método de Shazam crea hashes usando pares de picos, no picos individuales
    • El hash incluye las frecuencias fA, fB de los dos picos y la diferencia de tiempo ΔT entre ellos
    • Si cada pico tiene información de frecuencia de 10 bits y ΔT también se representa con 10 bits, en total hay 30 bits de información
    • 2^30=1,073,741,824 posibilidades son muchísimo más que las 1024 de un punto individual
  • Para generar los pares se usan un anchor point y una target zone
    • Se elige un punto como anchor point
    • Se calcula la target zone del spectrogram con respecto a ese anchor point
    • Se crean pares entre el anchor point y todos los puntos dentro de la target zone
  • El paper de Shazam no explica en detalle cómo se elige la target zone
    • En la imagen del paper, la target zone empieza un poco después en el tiempo que el anchor point y está centrada alrededor de la frecuencia del anchor point
  • Los pares generados se guardan en la base de datos como hashes
    • Los componentes del hash son fA, fB y ΔT
    • Como información adicional se guardan el tiempo del Point A y el Track ID
    • El tiempo del Point A y el Track ID luego se usan en el matching para encontrar un momento específico de una canción específica
  • El conjunto de todos los hashes de una pista forma el fingerprint de esa pista

Método de matching

  • El flujo de recognise crea un fingerprint a partir de la muestra y lo compara con los fingerprints ya almacenados en la base de datos
  • El algoritmo de matching avanza en cuatro pasos
    • trae de la base de datos todos los hashes que coinciden con el fingerprint de la muestra
    • agrupa los hashes por canción
    • para cada canción, verifica si los hashes se alinean en el tiempo
    • elige la pista con la mayor cantidad de hashes alineados
  • abracadabra no busca directamente la 3-tupla (fA, fB, ΔT), sino que la guarda como un valor único devuelto por hash(fA, fB, ΔT)
    • En vez de buscar tres valores por cada hash, puede buscar uno solo
  • Cada hash de la base de datos está asociado a un Track ID, así que se pueden agrupar por canción
    • Después de agruparlos así, se puede asignar una puntuación a cada pista candidata
  • Si la muestra coincide con una canción, los hashes de la muestra deberían alinearse bien con una sección de la canción original
    • El ruido puede crear picos que parezcan venir de otros momentos dentro de la muestra
    • También puede pasar que un hash coincida con la canción equivocada
  • La alineación se comprueba calculando el valor Track time - Sample time para cada hash coincidente
    • Los hashes que realmente coinciden comparten la misma diferencia
    • En el ejemplo, las filas con diferencia 10 son el true match, y las demás diferencias son false match
  • Luego se construye un histograma con esos valores de diferencia y se usa el bin más grande como score de la canción
    • En una canción que no hace buen match, todos los bins tienen valores bajos
    • En una buena coincidencia, aparece un gran spike en un solo bin
  • La razón por la que no se elige simplemente la canción con más hashes coincidentes es el sesgo por longitud de la canción
    • Las canciones largas tienen más probabilidad de acumular más matches que las cortas
    • En Spotify incluso hay pistas de más de 4 horas, así que el resultado podría sesgarse mucho

abracadabra y materiales de referencia

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-12-06
Opiniones en Hacker News

  • The Wall Street Journal tiene un video muy bien hecho que explica Shazam
    https://www.wsj.com/video/series/in-depth-features/how-shaza...
    Chris, cofundador de Shazam

    • Me pregunto si la razón por la que Shazam tenía una oficina en Rancho Bernardo, San Diego, era que él originalmente era de San Diego antes de irse al Reino Unido
      Lawn Love alquiló la suite del piso de arriba entre 2014 y 2018, y los desarrolladores de la app móvil de Shazam en esa oficina se mantuvieron discretos incluso después de la adquisición; nunca oímos ningún festejo con champaña

  • Cuando Shazam salió en 2008, el enfoque basado en hashes fue una elección inteligente
    Yo habría empezado por crear una forma de convertir cada canción en hashes de la manera más eficiente posible en términos de cómputo
    Si se lanzara hoy, la línea básica de I+D probablemente habría sido entrenar un modelo, lo cual podría haber sido mucho menos eficiente y más caro de hospedar
    Aunque es un problema en el que uno siente que un modelo podría hacerlo bien, dado que el número de canciones es finito, es muy probable que el método de hashes tenga mucho mejor rendimiento

    • Para ser precisos, no convierte cada canción en un solo hash, sino que convierte cada canción en cientos o miles de hashes
      La estructura consiste en encontrar cuántos hashes, de las decenas o como mucho unos pocos cientos bajos obtenidos de una muestra corta, coinciden y si lo hacen de forma más o menos continua
      Aun hoy no creo que lo harían con entrenamiento de modelos, porque todos los días se agregan enormes cantidades de canciones nuevas y habría que reentrenar continuamente
      Los hashes siguen pareciendo un mejor enfoque no solo por eficiencia, sino también en términos de robustez general
    • El enfoque ingenioso de 1975 fue el código Parsons, que también era algo cercano a hashear canciones de una forma calculable mentalmente
      Luego se podía buscar una canción como se busca una palabra en un diccionario, y espero que esta idea no desaparezca fácilmente
      [1]: https://en.wikipedia.org/wiki/Parsons_code
    • Una corrección menor: Shazam no se lanzó en 2008, sino en 2002 como un servicio telefónico, y enviaba el resultado por mensaje de texto
      La primera app para celular fue en 2006 para BREW
      2008 fue simplemente cuando Apple lanzó la App Store; antes de eso, terceros no podían crear apps para iPhone
    • Sinceramente, en una herramienta como Shazam no hay una diferencia fundamental tan grande entre una base de datos + algoritmo de hashing y un modelo auto-supervisado
      Ambos son excelentes soluciones de indexación y compresión; solo cambia la escala de los datos
    • Si se entrenara esto como un modelo, me pregunto cómo se podría evitar volver a ejecutar el proceso completo de entrenamiento cada vez que se agregue una canción nueva
      Quizá haya alguna forma de crear un modelo de embeddings que permita calcular un vector de embedding para cada canción nueva sin un reentrenamiento completo

  • Shazam es uno de esos raros productos que, en 20 años, no ha perdido esa sensación de magia
    Está realmente cerca de lo que los tecnólogos deberían aspirar a construir

    • Para alguien con conocimientos técnicos, la extracción de huellas musicales es un problema concreto y comprensible, pero si uno entra en los detalles sin ver antes cómo ya se resolvió, es bastante difícil
      A diferencia de funciones que por fuera parecen similares, como el reconocimiento de imágenes de animales u objetos, pero que en su mayoría se acercan a una extraña magia de machine learning, esto encaja en un dominio poco común pero comprensible
    • Al mismo tiempo, una app que era “tocas, escucha y te da el resultado” se convirtió en una app inflada lenta y llena de anuncios
      Recuerdo que en un iPhone de la generación anterior ni siquiera cargaba a tiempo, así que terminé borrándola
    • Google lo llevó un paso más allá
      La función Now Playing detecta canciones continuamente y las deja en el historial, y en Google Assistant incluso se puede buscar una canción solo tarareándola
      No funciona de manera confiable, pero a veces acierta exactamente
    • Más bien se volvió aún más mágica
      Intenté encontrar una canción que alguien estaba cantando en America’s Got Talent y me sorprendió que el resultado volviera con ese cantante de AGT
      Me pregunté si también indexan programas de televisión
    • Los tecnólogos aspiran a ese tipo de producto
      Pero uno se pregunta qué harían los product managers si no siguieran arruinando el producto para conseguir bonos y vacaciones

  • También existe Chromaprint, que funciona de una forma un poco distinta
    Se basa en patrones de cambio de tono, no en los máximos del espectro
    Chromaprint se usa en AcoustID, una gran base de datos pública que vincula huellas de audio con grabaciones de MusicBrainz
    Sorprende que contenga una cantidad enorme de música aun sin tanto respaldo comercial como Shazam
    [1]: https://oxygene.sk/2011/01/how-does-chromaprint-work/

    • Tengo la impresión de que Chromaprint necesita comparar la canción completa
      Es bueno para detectar duplicados, pero el diseño de huellas de Shazam permite hacer coincidir un fragmento corto con una canción completa

  • Es un artículo excelente que capta muy bien qué hace un espectrograma, y casi imprescindible para quien quiera entender cómo funciona la extracción de huellas de audio
    También hay algoritmos aproximados similares en otros medios, así que vale la pena estudiar este artículo con calma para entender el hashing en el mundo real

    • Las técnicas generales de espectrogramas ya habían sido inventadas por Philips antes de Shazam
      Lo que hizo Shazam fue hashear de manera combinatoria para reducir los falsos positivos

  • Hay un sitio excelente que trata con matching algorítmico no canciones, sino clasificación de géneros y las ramificaciones de subgéneros que generan las firmas de canciones nuevas.
    Es un recurso increíble mantenido como proyecto personal paralelo, pero parece estar en riesgo de desaparecer por motivos como problemas de hosting.
    Antes existían Music DNA de Pandora o funciones similares de LastFM, pero este sitio es como una red visual de conexiones de toda la música creada por la humanidad hasta 2023, así que si desaparece sería una pérdida para toda la web.
    Every Noise At Once
    https://everynoise.com

  • Es sorprendente lo intuitivo que es este método y lo bien que encaja con nuestro propio proceso de percepción.
    A grandes rasgos, identifica fragmentos de melodía y luego intenta alinearlos en orden.
    Es parecido a cómo podemos reconocer algo con solo escuchar 5, 7 o 10 notas.
    Creo haber leído también sobre otros métodos de extracción de huellas de canciones que dependen de cosas como picos de volumen; aunque esos métodos puedan funcionar igual de bien, no se parecen en nada a lo que hace nuestro cerebro.
    Este método es bastante genial porque no se apoya en un “subproducto artificial”, sino que básicamente funciona de una manera similar a la nuestra.
    Técnicamente no siempre es una melodía, pero probablemente en la mayoría de los casos sí lo sea.

  • Me da curiosidad cómo maneja Shazam los casos en que el eje temporal no es lineal o no es constante.
    Por ejemplo, cintas, wow and flutter, o situaciones en las que algo se acelera y desacelera constantemente.
    Hasta donde sé, la extracción de huellas es muy sensible al tiempo, y cortarla en fragmentos de unos 50 ms no lo resuelve por completo.
    La última vez que lo vi, la técnica general para este tipo de problema, Dynamic Time Warping, tenía un costo computacional demasiado alto.

  • Son artículos relacionados. Si hay más, me interesa conocerlos.
    How Shazam Works (2003 Paper) - https://news.ycombinator.com/item?id=33299853 - octubre de 2022, 1 comentario
    Creating Shazam in Java (2010) - https://news.ycombinator.com/item?id=32530056 - agosto de 2022, 36 comentarios
    Shazam turns 20 - https://news.ycombinator.com/item?id=32520593 - agosto de 2022, 227 comentarios
    How Shazam Works (2015) - https://news.ycombinator.com/item?id=23806142 - julio de 2020, 7 comentarios
    Designing an audio adblocker - https://news.ycombinator.com/item?id=18855029 - enero de 2019, 186 comentarios
    Show HN: A radio/podcast adblocker featuring ML and Shazam-like fingerprinting - https://news.ycombinator.com/item?id=18459058 - noviembre de 2018, 2 comentarios
    Show HN: Shazam-like acoustic fingerprinting of continuous audio streams - https://news.ycombinator.com/item?id=15809291 - noviembre de 2017, 76 comentarios
    How Shazam Works (2015) - https://news.ycombinator.com/item?id=15350729 - septiembre de 2017, 13 comentarios
    Tell HN: Shazam picks up song from my kitchen light - https://news.ycombinator.com/item?id=11593305 - abril de 2016, 2 comentarios
    How Shazam works - https://news.ycombinator.com/item?id=9870408 - julio de 2015, 48 comentarios
    Patent infringement claim re: “Creating Shazam in Java” blogpost (2010) - https://news.ycombinator.com/item?id=9594480 - mayo de 2015, 18 comentarios
    The Shazam Effect (2014) - https://news.ycombinator.com/item?id=9593429 - mayo de 2015, 37 comentarios
    The Shazam Effect - https://news.ycombinator.com/item?id=8634357 - noviembre de 2014, 34 comentarios
    Ask HN: Is there an audio search technology that finds exact and similar audio? - https://news.ycombinator.com/item?id=8420141 - octubre de 2014, 3 comentarios
    Source code example of the Shazam algorithm - https://news.ycombinator.com/item?id=5724422 - mayo de 2013, 16 comentarios
    Creating Shazam in Java - https://news.ycombinator.com/item?id=5723863 - mayo de 2013, 43 comentarios
    An Industrial-Strength Audio Search Algorithm (Shazam) - https://news.ycombinator.com/item?id=2621103 - junio de 2011, 4 comentarios
    Shazam's Search for Songs Creates New Music Jobs - https://news.ycombinator.com/item?id=2215295 - febrero de 2011, 1 comentario
    How does the music-identifying app Shazam work its magic? - https://news.ycombinator.com/item?id=2214992 - febrero de 2011, 2 comentarios
    Implementing Shazam with Java in a weekend - https://news.ycombinator.com/item?id=1702975 - septiembre de 2010, 23 comentarios
    Shazam: not magic after all - https://news.ycombinator.com/item?id=909263 - octubre de 2009, 28 comentarios

How does the music-identifying app Shazam work its magic? - https://news.ycombinator.com/item?id=893353 - octubre de 2009, 16 comentarios

  • Parece el enfoque inverso de una ingeniería similar en la que la industria de la música pop intenta crear éxitos basados en géneros