¿Cómo funciona Shazam? Algoritmos de reconocimiento de música, huellas dactilares y procesamiento

Escuchas una canción familiar en el club o en el restaurante. Escuchaste esta canción mil veces hace mucho tiempo, y el sentimentalismo de la canción realmente toca tu corazón. ¡Deseas desesperadamente escucharlo mañana, pero no puedes recordar su nombre! Afortunadamente, en nuestro increíble mundo futurista, tienes un teléfono con un software de reconocimiento de música instalado y estás a salvo. Puedes relajarte, porque el software te dijo el nombre de la canción, y sabes que puedes escucharla una y otra vez hasta que se convierta en parte de ti... o te canses de ella.

Las tecnologías móviles, junto con el enorme progreso en el procesamiento de señales de audio, nos han brindado a los desarrolladores de algoritmos la capacidad de crear reconocedores de música. Una de las aplicaciones de reconocimiento de música más populares es Shazam. Si captura 20 segundos de una canción, sin importar si es una introducción, un verso o un estribillo, creará una huella digital para la muestra grabada, consultará la base de datos y usará su algoritmo de reconocimiento de música para decirle exactamente qué canción está escuchando. .

Pero, ¿cómo funciona Shazam? El algoritmo de Shazam fue revelado al mundo por su inventor Avery Li-Chung Wang en 2003. En este artículo repasaremos los fundamentos del algoritmo de reconocimiento de música de Shazam.

De analógico a digital: muestreo de una señal

¿Qué es realmente el sonido? ¿Es algún tipo de material místico que no podemos tocar pero que vuela a nuestros oídos y nos hace oír cosas?

Por supuesto, este no es el caso. Sabemos que en realidad el sonido es una vibración que se propaga como una onda mecánica de presión y desplazamiento, a través de un medio como el aire o el agua. Cuando esa vibración llega a nuestros oídos, particularmente al tímpano, mueve pequeños huesos que transmiten la vibración más allá de las pequeñas células ciliadas en lo profundo de nuestro oído interno. Finalmente, las pequeñas células ciliadas producen impulsos eléctricos, que se transmiten a nuestro cerebro a través del nervio auditivo del oído.

Los dispositivos de grabación imitan este proceso bastante de cerca, utilizando la presión de la onda de sonido para convertirla en una señal eléctrica. Una onda de sonido real en el aire es una señal de presión continua. En un micrófono, el primer componente eléctrico que encuentra esta señal la traduce a una señal de voltaje analógico, de nuevo, continua. Esta señal continua no es tan útil en el mundo digital, por lo que antes de poder procesarla, debe traducirse a una señal discreta que pueda almacenarse digitalmente. Esto se hace capturando un valor digital que representa la amplitud de la señal.

La conversión implica la cuantificación de la entrada y necesariamente introduce una pequeña cantidad de error. Por lo tanto, en lugar de una sola conversión, un convertidor de analógico a digital realiza muchas conversiones en partes muy pequeñas de la señal, un proceso conocido como muestreo.

El teorema de Nyquist-Shannon nos dice qué tasa de muestreo es necesaria para capturar una determinada frecuencia en señal continua. En particular, para capturar todas las frecuencias que un ser humano puede escuchar en una señal de audio, debemos muestrear la señal a una frecuencia dos veces mayor que la del rango de audición humana. El oído humano puede detectar frecuencias aproximadamente entre 20 Hz y 20 000 Hz. Como resultado, el audio se graba con mayor frecuencia a una frecuencia de muestreo de 44.100 Hz. Esta es la frecuencia de muestreo de los discos compactos y también es la frecuencia más utilizada con audio MPEG-1 (VCD, SVCD, MP3). (Esta velocidad específica fue elegida originalmente por Sony porque podía grabarse en un equipo de video modificado que funcionaba a 25 cuadros por segundo (PAL) o 30 cuadros por segundo (usando una grabadora de video monocromática NTSC) y cubría el ancho de banda de 20,000 Hz que se creía necesario para coincida con el equipo de grabación analógico profesional de la época.) Por lo tanto, al elegir la frecuencia de la muestra que se necesita grabar, probablemente querrá ir con 44,100 Hz.

Grabación - Captura del sonido

Grabar una señal de audio muestreada es fácil. Dado que las tarjetas de sonido modernas ya vienen con convertidores de analógico a digital, simplemente elija un lenguaje de programación, busque una biblioteca adecuada, configure la frecuencia de la muestra, la cantidad de canales (generalmente mono o estéreo), el tamaño de la muestra (por ejemplo, muestras de 16 bits). ). Luego abra la línea desde su tarjeta de sonido como cualquier flujo de entrada y escriba en una matriz de bytes. Así es como se puede hacer eso en Java:

 private AudioFormat getFormat() { float sampleRate = 44100; int sampleSizeInBits = 16; int channels = 1; //mono boolean signed = true; //Indicates whether the data is signed or unsigned boolean bigEndian = true; //Indicates whether the audio data is stored in big-endian or little-endian order return new AudioFormat(sampleRate, sampleSizeInBits, channels, signed, bigEndian); } final AudioFormat format = getFormat(); //Fill AudioFormat with the settings DataLine.Info info = new DataLine.Info(TargetDataLine.class, format); final TargetDataLine line = (TargetDataLine) AudioSystem.getLine(info); line.open(format); line.start();

Simplemente lea los datos de TargetDataLine . (En este ejemplo, el indicador running es una variable global que es detenida por otro subproceso; por ejemplo, si tenemos una GUI con el botón DETENER).

 OutputStream out = new ByteArrayOutputStream(); running = true; try { while (running) { int count = line.read(buffer, 0, buffer.length); if (count > 0) { out.write(buffer, 0, count); } } out.close(); } catch (IOException e) { System.err.println("I/O problems: " + e); System.exit(-1); }

Dominio del tiempo y dominio de la frecuencia

Lo que tenemos en esta matriz de bytes es una señal registrada en el dominio del tiempo. La señal en el dominio del tiempo representa el cambio de amplitud de la señal a lo largo del tiempo.

A principios de 1800, Jean-Baptiste Joseph Fourier hizo el notable descubrimiento de que cualquier señal en el dominio del tiempo es equivalente a la suma de un número (posiblemente infinito) de señales sinusoidales simples, dado que cada componente sinusoidal tiene una cierta frecuencia, amplitud, y fase. La serie de sinusoides que juntas forman la señal original en el dominio del tiempo se conoce como su serie de Fourier.

En otras palabras, es posible representar cualquier señal en el dominio del tiempo simplemente dando el conjunto de frecuencias, amplitudes y fases correspondientes a cada sinusoide que forma la señal. Esta representación de la señal se conoce como el dominio de la frecuencia. De alguna manera, el dominio de la frecuencia actúa como un tipo de huella digital o firma para la señal en el dominio del tiempo, proporcionando una representación estática de una señal dinámica.

La siguiente animación demuestra la serie de Fourier de una onda cuadrada de 1 Hz y cómo se puede generar una onda cuadrada (aproximada) a partir de componentes sinusoidales. La señal se muestra arriba en el dominio del tiempo y abajo en el dominio de la frecuencia.

Analizar una señal en el dominio de la frecuencia simplifica enormemente muchas cosas. Es más conveniente en el mundo del procesamiento de señales digitales porque el ingeniero puede estudiar el espectro (la representación de la señal en el dominio de la frecuencia) y determinar qué frecuencias están presentes y cuáles faltan. Después de eso, uno puede filtrar, aumentar o disminuir algunas frecuencias, o simplemente reconocer el tono exacto de las frecuencias dadas.

La transformada discreta de Fourier

Entonces necesitamos encontrar una manera de convertir nuestra señal del dominio del tiempo al dominio de la frecuencia. Aquí pedimos ayuda a la transformada discreta de Fourier (DFT). La DFT es una metodología matemática para realizar el análisis de Fourier en una señal discreta (muestreada). Convierte una lista finita de muestras igualmente espaciadas de una función en la lista de coeficientes de una combinación finita de sinusoides complejos, ordenados por sus frecuencias, considerando si esos sinusoides se han muestreado a la misma velocidad.

Uno de los algoritmos numéricos más populares para el cálculo de DFT es la transformada rápida de Fourier (FFT). Con mucho, la variación de FFT más utilizada es el algoritmo de Cooley-Tukey. Este es un algoritmo de divide y vencerás que divide recursivamente una DFT en muchas DFT más pequeñas. Mientras que evaluar una DFT requiere directamente operaciones O( n 2 ) , con una FFT de Cooley-Tukey se calcula el mismo resultado en operaciones O( n log n ) .

No es difícil encontrar una biblioteca apropiada para FFT. Aquí hay algunos de ellos:

• C -FFTW
• C++ – FFT propia
• Java – JTransform
• Python – NumPy
• Ruby – Ruby-FFTW3 (Interfaz a FFTW)

A continuación se muestra un ejemplo de una función FFT escrita en Java. (FFT toma números complejos como entrada. Para comprender la relación entre los números complejos y las funciones trigonométricas, lea sobre la fórmula de Euler).

 public static Complex[] fft(Complex[] x) { int N = x.length; // fft of even terms Complex[] even = new Complex[N / 2]; for (int k = 0; k < N / 2; k++) { even[k] = x[2 * k]; } Complex[] q = fft(even); // fft of odd terms Complex[] odd = even; // reuse the array for (int k = 0; k < N / 2; k++) { odd[k] = x[2 * k + 1]; } Complex[] r = fft(odd); // combine Complex[] y = new Complex[N]; for (int k = 0; k < N / 2; k++) { double kth = -2 * k * Math.PI / N; Complex wk = new Complex(Math.cos(kth), Math.sin(kth)); y[k] = q[k].plus(wk.times(r[k])); y[k + N / 2] = q[k].minus(wk.times(r[k])); } return y; }

Y aquí hay un ejemplo de una señal antes y después del análisis FFT:

Reconocimiento de música: toma de huellas dactilares de una canción

Un efecto secundario desafortunado de FFT es que perdemos una gran cantidad de información sobre el tiempo. (Aunque teóricamente esto se puede evitar, los gastos generales de interpretación son enormes). Para una canción de tres minutos, vemos todas las frecuencias y sus magnitudes, pero no tenemos ni idea de cuándo aparecieron en la canción. ¡Pero esta es la información clave que hace que la canción sea lo que es! De alguna manera necesitamos saber en qué momento apareció cada frecuencia.

Es por eso que introducimos una especie de ventana deslizante, o fragmento de datos, y transformamos solo esta parte de la información. El tamaño de cada trozo se puede determinar de diferentes maneras. Por ejemplo, si grabamos el sonido, en estéreo, con muestras de 16 bits, a 44.100 Hz, un segundo de dicho sonido serán 44.100 muestras * 2 bytes * 2 canales ≈ 176 kB. Si elegimos 4 kB para el tamaño de un fragmento, tendremos 44 fragmentos de datos para analizar en cada segundo de la canción. Esa es una densidad lo suficientemente buena para el análisis detallado necesario para la identificación de audio.

Ahora volvamos a la programación:

 byte audio [] = out.toByteArray() int totalSize = audio.length int sampledChunkSize = totalSize/chunkSize; Complex[][] result = ComplexMatrix[sampledChunkSize][]; for(int j = 0;i < sampledChunkSize; j++) { Complex[chunkSize] complexArray; for(int i = 0; i < chunkSize; i++) { complexArray[i] = Complex(audio[(j*chunkSize)+i], 0); } result[j] = FFT.fft(complexArray); }

En el ciclo interno, colocamos los datos en el dominio del tiempo (las muestras) en un número complejo con parte imaginaria 0. En el ciclo externo, iteramos a través de todos los fragmentos y realizamos un análisis FFT en cada uno.

Una vez que tenemos información sobre la composición de frecuencias de la señal, podemos comenzar a formar nuestra huella digital de la canción. Esta es la parte más importante de todo el proceso de reconocimiento de audio de Shazam. El principal desafío aquí es cómo distinguir, en el océano de frecuencias capturadas, qué frecuencias son las más importantes. Intuitivamente, buscamos las frecuencias de mayor magnitud (comúnmente llamadas picos).

Sin embargo, en una canción, el rango de frecuencias fuertes puede variar entre C bajo - C1 (32,70 Hz) y C alto - C8 (4186,01 Hz). Este es un gran intervalo para cubrir. Entonces, en lugar de analizar todo el rango de frecuencias a la vez, podemos elegir varios intervalos más pequeños, elegidos en función de las frecuencias comunes de componentes musicales importantes, y analizar cada uno por separado. Por ejemplo, podríamos usar los intervalos que eligió este tipo para su implementación del algoritmo Shazam. Estos son 30 Hz - 40 Hz, 40 Hz - 80 Hz y 80 Hz - 120 Hz para los tonos graves (cubriendo el bajo, por ejemplo), y 120 Hz - 180 Hz y 180 Hz - 300 Hz para los tonos medios y agudos. (cubriendo voces y la mayoría de los otros instrumentos).

Ahora, dentro de cada intervalo, podemos simplemente identificar la frecuencia con la magnitud más alta. Esta información forma una firma para este fragmento de la canción, y esta firma se convierte en parte de la huella digital de la canción como un todo.

 public final int[] RANGE = new int[] { 40, 80, 120, 180, 300 }; // find out in which range is frequency public int getIndex(int freq) { int i = 0; while (RANGE[i] < freq) i++; return i; } // result is complex matrix obtained in previous step for (int t = 0; t < result.length; t++) { for (int freq = 40; freq < 300 ; freq++) { // Get the magnitude: double mag = Math.log(results[t][freq].abs() + 1); // Find out which range we are in: int index = getIndex(freq); // Save the highest magnitude and corresponding frequency: if (mag > highscores[t][index]) { points[t][index] = freq; } } // form hash tag long h = hash(points[t][0], points[t][1], points[t][2], points[t][3]); } private static final int FUZ_FACTOR = 2; private long hash(long p1, long p2, long p3, long p4) { return (p4 - (p4 % FUZ_FACTOR)) * 100000000 + (p3 - (p3 % FUZ_FACTOR)) * 100000 + (p2 - (p2 % FUZ_FACTOR)) * 100 + (p1 - (p1 % FUZ_FACTOR)); }

Tenga en cuenta que debemos asumir que la grabación no se realiza en perfectas condiciones (es decir, una “sala de sordos”), y como resultado debemos incluir un factor de fuzz. El análisis del factor fuzz debe tomarse en serio y, en un sistema real, el programa debe tener una opción para establecer este parámetro en función de las condiciones de la grabación.

Para facilitar la búsqueda de audio, esta firma se convierte en la clave en una tabla hash. El valor correspondiente es el momento en que apareció este conjunto de frecuencias en la canción, junto con el ID de la canción (título de la canción y artista). Este es un ejemplo de cómo podrían aparecer estos registros en la base de datos.

Si ejecutamos una biblioteca completa de canciones a través de este proceso de identificación de música, podemos construir una base de datos con una huella digital completa de cada canción en la biblioteca.

El algoritmo musical: identificación de canciones

Para identificar una canción que se está reproduciendo actualmente en el club, grabamos la canción con nuestro teléfono y ejecutamos la grabación a través del mismo proceso de huellas dactilares de audio que el anterior. Luego podemos comenzar a buscar en la base de datos etiquetas hash coincidentes.

Da la casualidad de que muchas de las etiquetas hash corresponderán al identificador de música de varias canciones. Por ejemplo, puede ser que alguna pieza de la canción A suene exactamente como alguna pieza de la canción E. Por supuesto, esto no es sorprendente: los músicos siempre han "tomado prestados" licks y riffs unos de otros, y en estos días los productores toman muestras de otras canciones todo el tiempo. el tiempo. Cada vez que hacemos coincidir una etiqueta hash, el número de posibles coincidencias se reduce, pero es probable que esta información por sí sola no reduzca la coincidencia a una sola canción. Entonces, hay una cosa más que debemos verificar con nuestro algoritmo de reconocimiento de música, y ese es el tiempo.

La muestra que grabamos en el club puede ser de cualquier punto de la canción, por lo que no podemos simplemente hacer coincidir la marca de tiempo del hash coincidente con la marca de tiempo de nuestra muestra. Sin embargo, con múltiples hashes coincidentes, podemos analizar el tiempo relativo de las coincidencias y, por lo tanto, aumentar nuestra certeza.

Por ejemplo, si observa la tabla anterior, verá que la etiqueta hash 30 51 99 121 195 corresponde tanto a la canción A como a la canción E. Si, un segundo después, hacemos coincidir el hash 34 57 95 111 200 , es uno más coincide con la canción A, pero en este caso sabemos que tanto los valores hash como las diferencias de tiempo coinciden.

 // Class that represents specific moment in a song private class DataPoint { private int time; private int songId; public DataPoint(int songId, int time) { this.songId = songId; this.time = time; } public int getTime() { return time; } public int getSongId() { return songId; } }

Tomemos i 1 e i 2 como momentos en la canción grabada, y j 1 y j 2 como momentos en la canción de la base de datos. Podemos decir que tenemos dos partidos con diferencia horaria si:

<span style=font-family: TimesNewRoman;> RecordedHash(i 1 ) = SongInDBHash(j 1 ) AND RecordedHash(i 2 ) = SongInDBHash(j 2 ) </span>

<span style=font-family: TimesNewRoman;>Y</span>

<span style=font-family: TimesNewRoman;> abs(i 1 - i 2 ) = abs (j 1 - j 2 ) </span>

Esto nos da flexibilidad para grabar la canción desde el principio, la mitad o el final.

Finalmente, es poco probable que cada momento de la canción que grabamos en el club coincida con cada momento correspondiente de la misma canción en nuestra biblioteca, grabada en el estudio. La grabación incluirá mucho ruido que introducirá algún error en los partidos. Entonces, en lugar de tratar de eliminar todas las canciones excepto la correcta de nuestra lista de coincidencias, al final, clasificamos todas las canciones coincidentes en orden descendente de probabilidad, y nuestra favorita es la primera canción en la lista de clasificación.

De arriba a abajo

Para responder a la pregunta, "¿Cómo funciona Shazam?" aquí hay una descripción general de todo el proceso de reconocimiento y coincidencia de música, de arriba a abajo:

Para este tipo de sistema, la base de datos puede ser bastante grande, por lo que es importante utilizar algún tipo de base de datos escalable. No hay una necesidad especial de relaciones, y el modelo de datos termina siendo bastante simple, por lo que es un buen caso para usar algún tipo de base de datos NoSQL.

¿Cómo funciona Shazam? ahora lo sabes

Este tipo de software de reconocimiento de canciones se puede utilizar para encontrar similitudes entre canciones. Ahora que comprende cómo funciona Shazam, puede ver cómo esto puede tener aplicaciones más allá de simplemente Shazamear esa canción nostálgica que suena en la radio del taxi. Por ejemplo, puede ayudar a identificar el plagio en la música, o averiguar quién fue la inspiración inicial de algunos pioneros del blues, el jazz, el rock, el pop o cualquier otro género. Tal vez un buen experimento sería llenar la base de datos de muestras de canciones con la música clásica de Bach, Beethoven, Vivaldi, Wagner, Chopin y Mozart e intentar encontrar las similitudes entre las canciones. ¡Uno pensaría que incluso Bob Dylan, Elvis Presley y Robert Johnson son plagiarios!

Pero aún no podemos condenarlos, porque la música es solo una onda que escuchamos, memorizamos y repetimos en nuestra cabeza, donde evoluciona y cambia hasta que la grabamos en el estudio y se la pasamos al próximo gran genio musical.