Recientemente, BI.ZONE participó en la conferencia HighLoad ++. Está claro que llegamos allí no solo para mirar los stands de otras personas, sino que trajimos algo interesante. Los empleados de diferentes departamentos de la compañía prepararon tareas para los invitados a la conferencia, cuya solución ofrecimos premios. Una de las tareas de Golang estaba dedicada al reconocimiento de sonido. Le pedimos a su autor que hablara de ella.
Declaración del problema.
En nuestra tarea, necesitamos indexar un cierto número de pistas y aprender a buscar en la base de datos la composición original por su muestra. En este caso, la muestra puede ser ruidosa, grabada en un micrófono defectuoso, puede tener una frecuencia diferente. La mayor parte del código ya ha sido escrito para el participante, solo necesita implementar la función de huella digital, que elimina la huella digital de la pista.
Como grabar un sonido
Está claro que cualquier pista es una onda mecánica que tiene una naturaleza analógica. Las ondas en física tienen dos características: frecuencia y amplitud. Con respecto a las ondas de sonido, por simplicidad, podemos suponer que la amplitud es el volumen y la frecuencia es el tono, aunque en realidad los sonidos altos parecen ser más fuertes para una persona con la misma amplitud.
Es decir, desde el punto de vista de la física, cada composición se describe mediante una función continua, lo que significa que cualquier pieza arbitrariamente pequeña de la canción contendrá una cantidad infinita de información (aunque si esto es algún tipo de post-punk, entonces probablemente habrá un poco de información en las pistas menos) Debido a esto, la señal analógica no se puede guardar; tendrá que lidiar con su digitalización. El enfoque principal para la digitalización de señales analógicas es la modulación de código de pulso, que se discutirá en esta sección. PCM consta de tres etapas: discretización, cuantización y codificación. Analicemos brevemente lo que sucede en cada uno de ellos.
Discreción
Entonces, tenemos una función de amplitud versus tiempo. Si alguien tiene una pregunta, dónde está la frecuencia, entonces está oculta detrás de las curvas del gráfico de función. Todavía no es visible, pero luego la sacaremos. Como estamos hablando de una señal analógica, la función es continua y se define en el conjunto completo de argumentos posibles (cualquier número real desde cero hasta el final de la pista). Es decir, conocemos el valor de la función en cualquier momento, y tenemos muchos momentos. Obviamente no necesitamos tanto, así que solo tome un subconjunto discreto. Para hacer esto, guardaremos el valor de la señal en un pequeño intervalo fijo. Debe ser lo suficientemente pequeño para que no escuchemos la diferencia de oído, pero lo suficientemente grande como para no ahorrar demasiado, porque esto tampoco es deseable.
De hecho, cuando se digitaliza, no se establece el intervalo, sino la frecuencia, que se denomina "frecuencia de muestreo". Dependiendo de las tareas, la frecuencia de muestreo puede ser de 8 kHz en teléfonos a varios miles de kHz en equipos de audio profesionales. La música para escuchar normalmente fuera de los estudios de grabación generalmente se almacena a una frecuencia de 44,1 kHz o 48 kHz.
Cuantización
Gracias a la discretización, ahora tenemos un montón de puntos en lugar de un gráfico de función continua, pero aún no podemos trabajar con él, necesitamos estropear aún más el sonido. La función inicial de la amplitud frente al tiempo comparó la amplitud del continuo con el tiempo del continuo. Con el tiempo, lo descubrimos, y ahora tenemos que encontrar algo con una amplitud, porque sus valores actuales están dispersos en el conjunto de números reales demasiado caóticos para que podamos salvarlos sin problemas. Por ejemplo, entre ellos, seguro, hay algunos irracionales que no podemos guardar de ninguna manera sin redondear.
La cuantización es un proceso durante el cual redondeamos las amplitudes a valores de un conjunto preseleccionado. Por supuesto, queremos que el número de amplitudes sea una potencia de dos. Para pistas de audio ordinarias, se utiliza la cuantización de 16 bits, es decir, el número de amplitudes será 65 536 (de 2 a 16 grados). La grabación de sonido profesional se puede realizar con mayor precisión, pero pocas personas pueden distinguir la cuantización de 16 bits de la de 24 bits. Entonces, tomamos el poder de dos, tomamos un montón de amplitudes enteras y las llamamos niveles de cuantización. Entonces será posible decir que la señal se cuantifica en más de 65 536 niveles (suena autoritativamente, ¿verdad?). Cada amplitud se redondea a uno de los niveles, lo que en última instancia le permite almacenar su valor en 16 bits, y al oído tal grabación es indistinguible del sonido continuo analógico.
Como ilustración, puede ver la imagen a continuación o generar sus propias imágenes en Python (el código es aún más bajo). La parte superior derecha de la ilustración muestra cinco niveles de cuantización. Es decir, la pista tendrá solo cinco niveles de volumen.
Algunos ejemplosimport numpy as np import matplotlib.pyplot as plt import math as m def f(x): return m.sin(x) q = 1/2
Codificación
En la etapa de codificación, guardamos los resultados de los pasos anteriores en una forma comprensible. Todas las acciones antes de esto generalmente son realizadas por equipos especializados, pero queremos tener un archivo en la computadora o una matriz en la memoria donde habrá amplitudes. En consecuencia, en esta etapa, las señales del equipo se convierten en una serie de números, que llamaremos PCM (modulación de código de pulso) en el futuro. Sus índices son tiempo condicional (índice de intervalo después del muestreo), y las amplitudes se almacenan en él, redondeadas a enteros en la etapa de cuantificación.
Transformada de Fourier
Inicialmente, teníamos una onda mecánica y un deseo de digitalizarla, pero ahora tenemos una señal digitalizada y un deseo de obtener frecuencias de ella. Lo deseado se puede lograr usando la transformada de Fourier. Por si acaso, volveré a contar su valor aplicado en este problema. La transformación de Fourier le permite tomar cualquier función y descomponerla en la suma de senos y cosenos. Estamos interesados en esto, porque las sinusoides y las ondas de coseno son vibraciones, y el sonido se trata de vibraciones. Es decir, utilizando la transformación de Fourier, puede obtener los componentes de una oscilación compleja, averiguar su amplitud y frecuencia, simplemente observando qué coeficientes están frente a los argumentos seno y seno (o coseno). Por ejemplo, existe tal ola.
La olaDe hecho, sabemos que está definido por la función 10sin (3x) + sin (x) + 4sin (4x) + 20sin (2x), pero esto es ahora, y la onda de sonido real consiste en una miríada de términos, y nos gustaría poder trabaja con eso. Entonces,
ejecutemos esta función a través de la transformada de Fourier usando el programa
FourierScope y observemos el espectro de amplitud.
Espectro de amplitudAsí es como se ven los cuatro senos. Es fácil ver que el gráfico corresponde a los coeficientes de los senos y sus argumentos.
Debería aclararse que, de hecho, fue una demostración del poder no de la transformación de Fourier en sí, sino de su versión discreta, adecuada para señales que pasaron por la modulación de código de pulso con todas sus discretizaciones y cuantizaciones. Sería superfluo presentar un algoritmo para la transformada discreta de Fourier, por lo que debemos estar de acuerdo en el hecho de que existe algo llamado DFT, así como su modificación, la transformada rápida de Fourier (FFT). En este caso, el sentido aplicado de la FFT es el siguiente: el algoritmo recibe una pieza de PCM en la entrada y proporciona una matriz que contiene las amplitudes, y los intervalos de frecuencia son los índices. Es una cuestión de intervalos de frecuencia, no solo frecuencias, ya que la conversión es discreta. En esencia, era ingenuo esperar que se pueda aumentar la señal en todo el artículo y luego obtener frecuencias sin problemas e inexactitudes. De hecho, el bin de frecuencia es un conjunto de frecuencias que la FFT no puede distinguir entre sí.
Vale la pena señalar que las FFT a menudo se escriben incorrectamente al reescribir un algoritmo de libros y artículos. A continuación se muestra un código más correcto para trabajar con FFT, que es exactamente lo que esperábamos de los participantes en su solución.
import "github.com/mjibson/go-dsp/fft" ... blocksCount := len(pcm) / fftWindowSize for i := 0; i < blocksCount; i++ { complexArray := fft.FFTReal(pcm[i*fftWindowSize : i*fftWindowSize+fftWindowSize]) // use complexArray... }
La tecnología moderna le permite escribir una transformación rápida de Fourier en solo unas pocas líneas. FFT se usa para segmentos de tamaño fftWindowSize y devuelve una matriz de números complejos, que usaremos en el futuro para tomar huellas digitales.
En general, la transformación de Fourier es el lugar más delgado en todo el problema. Primero, el tamaño del contenedor es $ \ frac {frecuencia \ muestreo} {size \ window} $. En consecuencia, puede ampliar la ventana y obtener más frecuencias, lo cual es bueno, pero, por supuesto, tiene consecuencias negativas. El aumento en el tamaño de la ventana lleva al hecho de que analizamos PCM a grandes intervalos y perdemos sonidos de corta duración. En diferentes circunstancias, esto puede empeorar repetidamente el programa si los sonidos cortos son parte de la composición, o puede mejorar si solo son ruidos. O tal vez no afecte nada en absoluto. En una situación tan difícil, el programador debe actuar con decisión: tome un buen número, como $ 2 ^ 9 $ o $ 2 ^ {10} $, y trate de no molestarse con las complejidades donde esto no es necesario. Suficiente para resolver el problema, pero en una aplicación seria todavía tiene que usar alguna ventana de Hamming y mucho más para pensar.
Huella digital
La tarea es aprender a tener un hash que se pueda asignar a una pista y que sea insensible a los cambios, teniendo las frecuencias y amplitudes de la composición. Pueden ser muy diferentes: un poco de ruido, un cambio de todas las frecuencias, reproducir otra canción en paralelo, etc. También debe tener en cuenta que la base de datos puede contener simultáneamente muchas pistas similares que deben distinguirse entre sí. O tal vez todas las pistas serán diferentes, y el problema no será establecer cuál es la más adecuada, sino comprender que ninguna es adecuada. En general, hay un cierto margen para la creatividad.
Puede tomar una impresión de diferentes maneras. Digamos que haga un hash en forma de una lista de varios indicadores diferentes. Entre ellos puede estar, por ejemplo, el número promedio de cruces de señal cero, BPM, valores de frecuencia promedio. Lo hice en versiones anteriores de
Musicbrainz , y los problemas de este enfoque están escritos
aquí . Y puede considerar conceptos más abstractos, como ritmo, analizar la pista utilizando el algoritmo EM (
artículo ). En general, completa libertad de expresión. Desafortunadamente, la mayoría de los algoritmos propuestos, aparentemente, no tienen una implementación pública, por lo que simplemente tomarlos y compararlos no funcionará.
La implementación principal se describe en
este artículo. Es especialmente bueno que pueda implementar este algoritmo en varias líneas. Por ejemplo, en el artículo original, se propone dividir las frecuencias en 6 intervalos, encontrar la amplitud máxima en cada uno, tomar el promedio de los seis y guardar los contenedores que son más altos que el promedio, pero son posibles muchas otras implementaciones.
var freqBins = [...]int16{40, 80, 120, 180, 300} func getKeyPoints(frame []freq_domain) int { highScores := make([]float64, len(freqBins)) recordPoints := make([]uint, len(freqBins)) for bin := freqBins[0]; bin < freqBins[len(freqBins)-1]; bin++ { magnitude := frame[bin] binIdx := 0 for freqBins[binIdx] < bin { binIdx++ } if magnitude > highScores[binIdx] { highScores[binIdx] = magnitude recordPoints[binIdx] = (uint)(bin) } } return hash(recordPoints) }
La función anterior implementa el algoritmo de huellas digitales. Al final, se pasa una matriz de frecuencias (o más bien, bins) a la función hash (), que debería convertir una matriz de varios números en un número. Puede hacerlo de cualquier manera adecuada, incluso puede intentar usar md5 (aunque esta es una mala idea).
Acerca de las pruebas
Se prepararon varios casos de prueba:- Prueba previa normal con una pista. El original y la muestra coincidieron completamente.
- Otra prueba previa con dos pistas. Los originales coincidieron con las muestras.
- Se indexa un número ligeramente mayor de pistas, todas se buscan alternativamente.
- Se carga una gran cantidad de pistas, se buscan, pero después de la disminución de la resolución.
- Las pistas se indexan después del muestreo descendente, se buscan las originales.
- Indexado varias pistas similares, buscando una similar, pero no en la base de datos.
- Se indexan varias pistas, se buscan, pero con ruido.
Algunos enlaces interesantes
https://metacpan.org/pod/Audio::Ofa::Utilhttps://www.researchgate.net/publication/228347102_A_Review_of_Audio_Fingerprintinghttp://www.freshmeat.net/projects/songprinthttps://link.springer.com/article/10.1007/s11265-005-4152-2https://github.com/acoustid/chromaprinthttps://laplacian.wordpress.com/2009/01/10/how-shazam-works/