Recentemente, o BI.ZONE participou da conferência HighLoad ++. É claro que chegamos lá não apenas para olhar as bancas de outras pessoas, mas trouxemos algo interessante. Funcionários de diferentes departamentos da empresa prepararam tarefas para os convidados da conferência, cuja solução oferecemos prêmios. Uma das tarefas de Golang foi dedicada ao reconhecimento de som. Pedimos à autora que falasse sobre ela.
Declaração do problema
Em nossa tarefa, precisamos indexar um certo número de faixas e aprender a procurar no banco de dados a composição original por sua amostra. Nesse caso, a amostra pode muito bem ser barulhenta, gravada em um microfone ruim, pode ter uma frequência diferente. A maior parte do código já foi escrita para o participante, ele só precisa implementar a função de impressão digital, que remove a impressão digital da pista.
Como gravar um som
É claro que qualquer faixa é uma onda mecânica de natureza analógica. As ondas na física têm duas características: frequência e amplitude. No que diz respeito às ondas sonoras, por simplicidade, podemos assumir que a amplitude é o volume e a frequência é o tom, embora, na verdade, sons altos pareçam mais altos para uma pessoa na mesma amplitude.
Ou seja, do ponto de vista da física, cada composição é descrita por uma função contínua, o que significa que qualquer peça arbitrariamente pequena da música conterá uma quantidade infinita de informações (embora se esse seja algum tipo de pós-punk, provavelmente haverá pouca informação nas faixas menos). Por esse motivo, o sinal analógico não pode ser salvo; você terá que lidar com a digitalização. A principal abordagem para a digitalização de sinais analógicos é a modulação por código de pulso, que será discutida nesta seção. O PCM consiste em três estágios: discretização, quantização e codificação. Vamos analisar brevemente o que acontece em cada um deles.
Discretização
Portanto, temos uma função de amplitude versus tempo. Se alguém tiver uma pergunta, onde está a frequência, ela ficará oculta atrás das curvas do gráfico de funções. Ela ainda não está visível, mas mais tarde a puxaremos para fora. Como estamos falando de um sinal analógico, a função é contínua e definida em todo o conjunto de argumentos possíveis (qualquer número real de zero ao final da faixa). Ou seja, sabemos o valor da função a qualquer momento e temos muitos momentos. Obviamente, não precisamos de muito, portanto, basta pegar um subconjunto discreto. Para fazer isso, salvaremos o valor do sinal em um pequeno intervalo fixo. Deve ser pequeno o suficiente para não ouvir a diferença de ouvido, mas grande o suficiente para não economizar muito, porque isso também é indesejável.
De fato, ao digitalizar, não é o intervalo definido, mas a frequência, que é chamada de "frequência de amostragem". Dependendo das tarefas, a frequência de amostragem pode variar de 8 kHz em telefones a vários milhares de kHz em equipamentos de áudio profissional. As músicas para audição comum fora dos estúdios de gravação geralmente são armazenadas a uma frequência de 44,1 kHz ou 48 kHz.
Quantização
Graças à discretização, agora temos vários pontos em vez de um gráfico de funções contínuas, mas ainda não podemos trabalhar com isso, precisamos estragar ainda mais o som. A função inicial da amplitude versus tempo comparou a amplitude do continuum com o tempo do continuum. Com o tempo, descobrimos isso e agora precisamos criar algo com amplitude, porque seus valores atuais estão espalhados pelo conjunto de números reais de maneira muito caótica para que possamos salvá-los sem problemas. Por exemplo, entre eles, com certeza, existem outros irracionais que não podemos salvar de forma alguma sem arredondamentos.
A quantização é um processo durante o qual arredondamos amplitudes para valores de um conjunto pré-selecionado. Obviamente, queremos que o número de amplitudes seja uma potência de dois. Para trilhas de áudio comuns, é utilizada a quantização de 16 bits, ou seja, o número de amplitudes será 65 536 (2 a 16 graus). A gravação de som profissional pode ser realizada com maior precisão, mas poucas pessoas de ouvido conseguem distinguir quantização de 16 bits de 24 bits. Então, pegamos o poder de dois, pegamos um monte de amplitudes inteiras e os chamamos de níveis de quantização. Então será possível dizer que o sinal é quantizado em 65 536 níveis (soa autoritativamente, certo?). Cada amplitude é arredondada para um dos níveis, o que, em última análise, permite armazenar seu valor em 16 bits, e de ouvido essa gravação é indistinguível do som contínuo analógico.
Como ilustração, você pode ver a figura abaixo ou gerar suas próprias imagens em Python (o código é ainda mais baixo). O canto superior direito da ilustração mostra cinco níveis de quantização. Ou seja, a faixa terá apenas cinco níveis de volume.
Alguns exemplosimport numpy as np import matplotlib.pyplot as plt import math as m def f(x): return m.sin(x) q = 1/2
Codificação
No estágio de codificação, salvamos os resultados das etapas anteriores de forma compreensível. Todas as ações anteriores a isso geralmente são executadas por equipamento especializado, mas queremos ter um arquivo no computador ou uma matriz na memória onde haverá amplitudes. Portanto, nesta fase, os sinais do equipamento são convertidos em uma matriz de números, que chamaremos de PCM (modulação de código de pulso) no futuro. Seus índices são de tempo condicional (índice de intervalo após a amostragem) e as amplitudes são armazenadas nele, arredondadas para números inteiros no estágio de quantização.
Transformada de Fourier
Inicialmente, tínhamos uma onda mecânica e um desejo de digitalizá-la, mas agora temos um sinal digitalizado e um desejo de obter frequências a partir dele. O desejado pode ser alcançado usando a transformada de Fourier. Apenas no caso, vou recontar seu valor aplicado nesse problema. A transformação de Fourier permite que você tome qualquer função e a decomponha na soma de senos e cossenos. Estamos interessados nisso, porque as ondas sinusóides e cosseno são sobre vibrações, e o som é sobre vibrações. Ou seja, usando a transformada de Fourier, é possível obter os componentes de uma oscilação complexa, descobrir sua amplitude e frequência, apenas observando quais coeficientes estão na frente dos argumentos seno e seno (ou cosseno). Por exemplo, existe essa onda.
A ondaDe fato, sabemos que ela é definida pela função 10sin (3x) + sin (x) + 4sin (4x) + 20sin (2x), mas isso é agora, e a onda sonora real consiste em uma infinidade de termos e gostaríamos de poder trabalhe com isso. Então, vamos executar esta função através da transformação de Fourier usando o programa
FourierScope e ver o espectro de amplitude.
Espectro de amplitudeÉ assim que os quatro seios se parecem. É fácil ver que o gráfico corresponde aos coeficientes dos senos e seus argumentos.
Deve-se esclarecer que, de fato, foi uma demonstração do poder não da própria transformada de Fourier, mas de sua versão discreta, adequada para sinais que passaram pela modulação do código de pulso com todas as suas discretizações e quantizações. Seria supérfluo apresentar um algoritmo para a transformada discreta de Fourier, então vamos concordar com o fato de que existe uma coisa chamada DFT, bem como sua modificação, a rápida transformada de Fourier (FFT). Nesse caso, o significado aplicado da FFT é o seguinte: o algoritmo recebe um pedaço de PCM na entrada e fornece uma matriz contendo as amplitudes, e os compartimentos de frequência são os índices. É uma questão de caixas de frequência, não apenas de frequências, já que a conversão é discreta. Na verdade, era ingênuo esperar que você pudesse aumentar o sinal ao longo do artigo e depois obter frequências sem problemas e imprecisões. De fato, o compartimento de frequência é um conjunto de frequências que a FFT não consegue distinguir uma da outra.
Vale a pena notar que as FFTs geralmente são escritas incorretamente ao reescrever um algoritmo de livros e artigos. Abaixo está um código mais correto para trabalhar com a FFT, exatamente o que esperávamos dos participantes em sua solução.
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... }
A tecnologia moderna permite que você escreva a transformação rápida de Fourier em apenas algumas linhas. A FFT é usada para segmentos de tamanho fftWindowSize e retorna uma matriz de números complexos, que usaremos para impressões digitais no futuro.
Em geral, a transformação de Fourier é o local mais fino de todo o problema. Primeiro, o tamanho da lixeira é $ \ frac {frequency \ sampling} {size \ window} $. Dessa forma, você pode ampliar a janela e obter mais frequências, o que é bom, mas, é claro, tem consequências negativas. O aumento no tamanho da janela leva ao fato de analisarmos o PCM em grandes intervalos e perdermos sons de curta duração. Em diferentes circunstâncias, isso pode piorar repetidamente o programa se sons curtos fizerem parte da composição, ou pode melhorar se forem apenas ruídos. Ou talvez não afete nada. Em uma situação tão difícil, o programador deve agir decisivamente: pegue um bom número, como $ 2 ^ 9 $ ou $ 2 ^ {10} $, e tente não se preocupar com os meandros onde isso não é necessário. O suficiente para resolver o problema, mas em um aplicativo sério você ainda precisa usar algumas janelas do Hamming e muito mais para pensar.
Impressão digital
A tarefa é aprender a ter um hash que pode ser mapeado para uma faixa e que é insensível a mudanças, tendo as frequências e amplitudes da composição. Eles podem ser muito diferentes: um pouco de ruído, uma mudança de todas as frequências, tocando outra música em paralelo, e assim por diante. Você também precisa considerar que o banco de dados pode conter simultaneamente muitas trilhas semelhantes que precisam ser diferenciadas uma da outra. Ou talvez todas as faixas sejam diferentes, e o problema não será estabelecer qual é a mais adequada, mas entender que nenhuma é a mais adequada. Em geral, existe um certo escopo para a criatividade.
Você pode imprimir de diferentes maneiras. Digamos que faça um hash na forma de uma lista de vários indicadores diferentes. Entre eles, pode estar, por exemplo, o número médio de passagens de sinal zero, BPM, valores médios de frequência. Eu fiz isso nas versões anteriores do
Musicbrainz , e os problemas dessa abordagem estão escritos
aqui . E você pode considerar conceitos mais abstratos, como ritmo, analisando a faixa usando o algoritmo EM (
artigo ). Em geral, completa liberdade de expressão. Infelizmente, a maioria dos algoritmos propostos, aparentemente, não possui uma implementação pública; portanto, apenas pegar e compará-los não funcionará.
A implementação principal é descrita
neste artigo. É especialmente bom que você possa implementar esse algoritmo em várias linhas. Por exemplo, no artigo original, propõe-se dividir as frequências em 6 intervalos, encontrar a amplitude máxima em cada uma, obter a média de todas as seis e salvar os compartimentos que são maiores que a média, mas muitas outras implementações são possíveis.
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) }
A função acima implementa o algoritmo de impressão digital. No final, uma matriz de frequências (ou melhor, compartimentos) é passada para a função `hash ()`, que deve transformar uma matriz de vários números em um número. Você pode fazer isso de qualquer maneira adequada, pode até tentar usar o md5 (embora isso seja uma má ideia).
Sobre o teste
Vários casos de teste foram preparados:- Pré-teste normal com uma faixa. O original e a amostra coincidiram completamente.
- Outro pré-teste com duas faixas. Os originais coincidiram com as amostras.
- Um número um pouco maior de faixas é indexado, todas são pesquisadas alternadamente.
- Um grande número de faixas é carregado, elas são pesquisadas, mas após a redução da amostra.
- As faixas são indexadas após a redução da amostra, as originais são pesquisadas.
- Indexou várias faixas semelhantes, procurando uma similar, mas não no banco de dados.
- Várias faixas são indexadas, são pesquisadas, mas com ruído.
Alguns links interessantes
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/