Você ouve uma música de família no clube ou restaurante. Você já ouviu essa música milhares de vezes em muito tempo e o sentimentalismo da música realmente toca seu coração. Você quer desesperadamente ouvi-la de novo pela manhã, mas não se lembra do nome dela! Felizmente, em nosso incrível mundo futurista, você tem um telefone com software de reconhecimento de música instalado. Você pode relaxar, já que o Software lhe disse o nome da música, então você sabe que pode ouvi-la continuamente até que se torne parte de você ... ou você fica desesperado ...
Tecnologias móveis juntamente com o imenso progresso no processamento de sinais de áudio nos proporcionou, desenvolvedores de algoritmos , a capacidade de criar reconhecedores de música. Um dos aplicativos de reconhecimento de música mais populares é Shazam . Capture uma música em 20 segundos, independentemente de ser a introdução, o verso ou o refrão, o aplicativo criará uma impressão digital da amostra gravada, consultará o banco de dados e usará seu algoritmo de reconhecimento de música para dizer exatamente qual. é a música que você está ouvindo.
Como o Shazam realmente funciona? Algoritmo de Shazam O aplicativo foi exposto pela primeira vez por seu inventor Avery Li-Chung Wang em 2003. Neste artigo, discutiremos os fundamentos do algoritmo de reconhecimento de música Shazam.
Do analógico para o digital - Sinal de uma amostra
O que é realmente bom? É algum tipo de material místico que não podemos tocar, mas que voa em nossos ouvidos e nos faz ouvir coisas?
É claro, esse não é o caso. Sabemos que o som é na verdade uma vibração que se propaga como um onda mecânica onda mecânica de pressão e viaja através de um meio, como ar ou água. Quando essa vibração chega aos nossos ouvidos, especialmente no tímpano, ela move pequenos ossos que transmitem as vibrações às células ciliadas bem no fundo do nosso ouvido interno. Além disso, as poucas células ciliadas produzem impulsos elétricos que são transmitidos ao nosso cérebro através do nervo auditivo do ouvido.
Dispositivos de gravação imitam esse processo, pressionando a onda sonora em um sinal elétrico. Uma verdadeira onda sonora no ar é um contínuo sinal de pressão. Em um microfone, o primeiro componente elétrico ao encontrar este sinal é traduzido em um sinal de tensão analógico - novamente, contínuo. Este sinal contínuo não é tão útil no mundo digital, então antes de ser processado, ele deve ser traduzido em sinal discreto um sinal discreto que pode ser armazenado digitalmente. Isso é feito capturando um valor digital que representa a amplitude do sinal.
A conversão envolve quantização a quantização da entrada que necessariamente introduz uma pequena quantidade de erro. Portanto, em vez de uma simples conversão, um conversor analógico para digital O conversor analógico para digital realiza muitas conversões em partes muito pequenas do sinal - um processo conhecido como amostragem
o Teorema de Nyquist-Shannon O teorema de Nyquist-Shannon nos diz qual taxa de amostragem é necessária para capturar uma certa frequência em um sinal contínuo. Em particular, para capturar todas as frequências que um ser humano pode ouvir em um sinal de áudio, devemos amostrar o sinal em uma frequência duas vezes maior que a faixa de audição humana. O ouvido humano pode detectar frequências entre aproximadamente 20 Hz e 20.000 Hz. Como resultado, a maior parte do tempo o áudio gravado tem uma taxa de amostragem de 44.100 Hz. Esta é a frequência de amostragem de Discos compactos discos compactos e também é o mais usado com MPEG-1 Áudio ( VCD , SVCD , MP3 ) Esta taxa específica foi inicialmente escolhida pela Sony, porque poderia ser gravada em um equipamento de vídeo modificado rodando a uma taxa de 25 quadros por segundo ( AMIGO ) ou 30 quadros por segundo (usando um NTSC gravador de vídeo monocromático) e cobrindo a largura de banda de 20.000 Hz necessária para corresponder ao pensamento profissional de equipamento de gravação analógico). Portanto, ao escolher a frequência da amostra que precisa ser gravada, você provavelmente vai querer escolher 44.100 Hz.
Gravação - capturando o som
Gravar um sinal de áudio amostrado é fácil. Como as placas de som modernas já vêm com conversores analógico para digital, você só precisa selecionar uma linguagem de programação, encontrar uma biblioteca adequada e definir a taxa de amostragem, o número de canais (mono ou estéreo) e, geralmente, o tamanho. a amostra (por exemplo, amostras de 16 bits). Em seguida, abra a linha de sua placa de som, como qualquer fluxo de entrada, e escreva em uma matriz de bytes. É assim que você pode fazer em 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(); Leia os dados de 'TargetDataLine'. (Neste exemplo, 'Running' é uma variável global que é interrompida por outro thread - por exemplo, se tivermos uma GUI com o botão STOP).
qual escola de psicologia desenvolveu o princípio de fechamento
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); } Domínio do tempo e domínio da frequência
O que temos nesta matriz de bytes é o sinal registrado de tempo do domínio domínio . O sinal no domínio do tempo representa a mudança na amplitude do sinal ao longo do tempo.
Nas primeiras décadas do século 19, Jean-Baptiste Joseph Fourier fez a notável descoberta de que nenhum sinal no domínio do tempo é equivalente à soma de alguns números (possivelmente infinitos) de sinais sinusoidais simples, uma vez que cada componente tem uma certa frequência senoidal , amplitude e fase. A série de sinusóides que juntas formam o sinal original no domínio do tempo é conhecida como a série de Fourier .
Em outras palavras, é possível representar qualquer sinal no domínio do tempo simplesmente fornecendo o conjunto de frequências, amplitudes e fases correspondentes a cada senoide que compõe o sinal. Esta representação do sinal é conhecida como domínio de frequência domínio de frequência . De certa forma, o domínio da frequência atua como um tipo de impressão digital ou assinatura para o sinal no domínio do tempo, fornecendo uma representação estática de um sinal dinâmico.
o que é uma análise heurística
A animação a seguir mostra a série de Fourier de uma onda quadrada de 1 HZ onda quadrada e como uma onda quadrada (aproximada) pode ser gerada a partir de componentes sinusoidais. O sinal é exibido no domínio do tempo acima e no domínio da frequência abaixo.
Fonte: René Schwarz
A análise de um sinal no domínio da frequência simplifica imensamente muitas coisas. É mais conveniente no mundo do processamento digital de sinais porque o engenheiro pode estudar o espectro (a representação do sinal no domínio da frequência) e determinar quais frequências estão presentes e quais estão faltando. Depois disso, pode-se fazer a filtragem, aumentar ou diminuir algumas frequências, ou simplesmente reconhecer a altura exata das frequências.
A transformada discreta de Fourier
Portanto, precisamos encontrar uma maneira de converter nosso sinal do momento do domínio para o domínio da frequência. Aqui nós a chamamos de transformação discreta de Fourie Transformada Discreta de Fourier (DFT) para ajudar. DFT é um método matemático para realizar Análise de Fourier em um sinal discreto (amostra). Converte uma lista finita de amostras equidistantes de uma função na lista de coeficientes de uma combinação finita de sinusóides complexos, ordenados por suas frequências, considerando se os sinusóides foram amostrados na mesma proporção.
Um dos algoritmos numéricos mais populares para calcular o DFT é o Transformação rápida de Fourier (FFT). O mais amplamente utilizado é a variação FFT Algoritmo Cooley – Tukey . Este algoritmo é do tipo dividir e conquistar que divide recursivamente um DFT em vários pequenos DFTs. Embora a avaliação de um DFT exija diretamente OU( n 2) operações, com um Cooley-Tukey FFT é calculado em i OU( n registro n ) operações.
Não é difícil encontrar uma biblioteca adequada para o FFT. Aqui estão alguns deles:
- C - FFTW
- C ++ - EigenFFT
- Java - JTransform
- Pitão - NumPy
- Rubi - Ruby-FFTW3 (Interface para FFTW)
Abaixo está um exemplo de uma função FFT escrita em Java. (FFT tem números complexos como entrada. Para entender a relação entre números complexos e funções trigonométricas, leia sobre 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 E aqui está um exemplo de um sinal antes e depois da análise FFT:
Reconhecimento de música: impressões digitais em uma música
Um efeito colateral infeliz do FFT é que perdemos muitas informações sobre o tempo (embora teoricamente isso possa ser evitado, o desempenho de sobrecarga é enorme) para uma música de 3 minutos, podemos ver todas as frequências e suas magnitudes, mas não Não tenho ideia de quando eles apareceram na música. Mas essa é a chave da informação que torna a música assim! De alguma forma, temos que saber quando cada frequência apareceu.
É por isso que introduzimos o tipo de janela deslizante, ou fragmento de dados, bem como a transformação desta parte da informação. O tamanho de cada fragmento pode ser determinado de diferentes maneiras. Por exemplo, se quisermos gravar o som em estéreo, com amostras de 16 bits, a 44.100 Hz, um segundo desse som terá 44.100 amostras * 2 bytes * 2 canais ≈ 176 kB. Se tomarmos 4 kB para o tamanho de um segmento, teremos 44 dados para analisar a cada segundo da música. Essa é uma densidade boa o suficiente para uma análise detalhada.
Agora vamos voltar à programação:
byte audio [] = out.toByteArray() int totalSize = audio.length int sampledChunkSize = totalSize/chunkSize; Complex[][] result = ComplexMatrix[sampledChunkSize][]; for(int j = 0;i No loop interno, estamos colocando os dados do domínio do tempo (as amostras) em um número complexo com parte imaginária 0. No loop externo, iteramos por todos os segmentos e realizamos uma análise FFT de cada um.
como criar um robô
Assim que tivermos as informações sobre a frequência do sinal, podemos começar a formar nossa impressão digital da música. Esta é a parte mais importante de todo o processo de reconhecimento musical do Shazam. O principal desafio é como distinguir, no oceano das frequências captadas, as frequências que são mais importantes. Intuitivamente, podemos procurar as frequências com a magnitude mais alta (comumente chamadas de picos).
Entretanto, em uma música, a faixa de frequência forte pode variar entre C - C1 baixo (32,70 Hz) e C - C8 alto (4.186,01 Hz). Este é um ótimo intervalo no convés. Portanto, em vez de analisar toda a faixa de frequência de uma vez, podemos escolher várias faixas menores. Escolha com base nas frequências comuns de componentes musicais importantes e analise cada um separadamente. Por exemplo, podemos usar os intervalos esse cara escolheu para sua implementação do algoritmo Shazam. Estes são 30 Hz - 40 Hz, 40 Hz - 80 Hz e 80 Hz - 120 Hz para os tons baixos (abrangendo o baixo, por exemplo), e 120 Hz - 180 Hz e 180 Hz - 300 Hz para o leste e o tons mais altos (cobrindo a maioria dos outros instrumentos e vozes).
Agora, dentro de cada intervalo, podemos determinar a frequência com a maior magnitude. Essas informações constituem uma assinatura para essa parte da música e essa assinatura se torna parte da impressão digital da música como um 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] Observe que devemos assumir que a gravação não foi feita em perfeitas condições (por exemplo, uma “sala para surdos”) e, como resultado, um fator de aproximação deve ser incluído. Uma análise do fator de aproximação deve ser levada a sério e em um sistema real, o programa deve ter uma opção para definir este parâmetro com base nas condições de registro.
Para facilitar a busca, essa assinatura passa a ser a chave em uma tabela de hashtag. O valor correspondente é o tempo em que esse conjunto de frequências apareceu na música, junto com o ID da música (título da música e artista). Aqui está um exemplo de como esses registros podem aparecer no banco de dados.
Hashtag Tempo em segundos Canção 30 51 99 121 19553,52 Canção A do artista A 33 56 92 151 18512,32 Canção B do artista B 39 26 89 141 25115,34 Música C do artista C 32 67 100 128 27078,43 Canção D do artista D 30 51 99 121 19510,89 Canção E do artista E 34 57 95 111 20054,52 Canção A do artista A 34 41 93 161 20211,89 Canção E do artista E
Se executarmos uma biblioteca inteira de músicas por meio desse processo, podemos construir um banco de dados completo com uma impressão digital de cada música na biblioteca.
Relacionado: Um tutorial de aprendizado profundo: de perceptrons a redes profundas Escolha de uma música
Para identificar uma música que está tocando no clube, grave a música em seu telefone e execute a gravação usando o mesmo processo de rastreamento digital de antes. Em seguida, você pode iniciar a pesquisa correspondente no banco de dados de hashtag.
o que é renderização do lado do servidor
Acontece que muitas das hashtags correspondem a várias canções. Por exemplo, pode ser que alguma parte de uma música soe exatamente como algum fragmento da música E. Claro, isso não é surpreendente - os músicos sempre 'pegaram emprestado' letras de músicas uns dos outros e, atualmente, os produtores mostram todas as outras músicas A Hora. Cada vez que iniciamos a partir de uma hashtag, o número de correspondências possíveis fica menor, mas é provável que essa informação por si só não reduza a correspondência a uma única música. Portanto, há mais uma coisa que precisamos verificar com nosso algoritmo de reconhecimento de música, que é o layout.
A amostra que foi registrada no clube pode estar em qualquer ponto da música, portanto, simplesmente não podemos corresponder ao carimbo de data / hora da hashtag que corresponde à nossa marca de amostra. No entanto, com vários algoritmos de hashtag correspondentes, podemos analisar o tempo relativo da combinação e, portanto, aumentar nossa segurança.
Por exemplo, se você olhar a tabela acima, verá que a hashtag '30 51 99 121 195 'corresponde à música A e à música E. Se um segundo depois correspondermos ao hash '34 57 95 111 200', que é mais uma combinação para uma música, mas, neste caso, sabemos que os hashes correspondem e também as diferenças de horário.
// 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; } } Vamos levar Eu1 e Eu2 como momentos na música gravada, e j1 e j2 como momentos na música do banco de dados. Podemos dizer que temos duas partidas com diferença horária se:
RecordedHash (i1) = SongInDBHash (j1) E RecordedHash (i2) = SongInDBHash (j2)
E
abs (eu1- Eu2) = abs (j1- j2)
Isso nos dá flexibilidade para gravar a música do início, meio ou fim.
Por fim, é improvável que cada momento da música que gravamos no clube coincida com cada momento correspondente da mesma música em nossa biblioteca, que gravamos no estúdio. A gravação inclui muito ruído que irá introduzir alguns erros nas partidas. Então, em vez de tentar remover todas as músicas, exceto a correta de nossa lista de correspondências, no final, nos reconciliamos para classificar todas as músicas em ordem decrescente de probabilidade, e nossa favorita é a primeira música na lista de classificação.
Baixo para cima
Esta é uma visão geral de todo o processo de reconhecimento e reconciliação musical, de cima para baixo:
Para este tipo de sistema, o banco de dados pode ficar muito grande, por isso é importante usar algum tipo de banco de dados variável. Não há necessidade especial de relacionamentos, e o modelo de dados acaba sendo bem simples, então é um bom caso para usar algum tipo de banco de dados NoSQL.
Conclusão, Shazam!
Este tipo de software de reconhecimento de música pode ser usado para encontrar semelhanças entre as músicas. Agora que você entende como o Shazam funciona, você pode ver como isso pode ter aplicações além do simples Shazaming do que aquela música nostálgica que toca no rádio do táxi. Por exemplo, você pode ajudar a identificar o plágio na música ou descobrir quem foi a inspiração inicial para alguns pioneiros do blues, jazz, rock, pop ou qualquer outro gênero. Talvez uma boa experiência fosse preencher o banco de dados com música clássica de Bach, Beethoven, Vivaldi, Wagner, Chopin e Mozart e tentar encontrar as semelhanças entre as canções. Eu acho que até Bob Dylan, Elvis Presley e Robert Johnson eram plagiadores!
Mas ainda não podemos condená-los, porque a música é simplesmente uma onda que ouvimos, memorizamos e repetimos em nossas cabeças, onde ela evolui e muda até que gravamos em estúdio e passamos para o próximo grande gênio musical.
Relacionado: Uma introdução à teoria do aprendizado de máquina e suas aplicações: um tutorial visual com exemplos
