Como funciona o Shazam? Algoritmos de reconhecimento de música, impressão digital e processamento

Você ouve uma música familiar no clube ou no restaurante. Você ouviu essa música mil vezes há muito tempo, e o sentimentalismo da música realmente toca seu coração. Você quer desesperadamente gravá-lo amanhã, mas não consegue se lembrar do nome! Felizmente, em nosso incrível mundo futurista, você tem um telefone com software de reconhecimento de música instalado e está salvo. Você pode relaxar, porque o software lhe disse o nome da música, e você sabe que pode ouvi-la de novo e de novo até que se torne parte de você... ou você se cansa dela.

As tecnologias móveis, juntamente com o enorme progresso no processamento de sinais de áudio, deram a nós, desenvolvedores de algoritmos, a capacidade de criar reconhecedores de música. Um dos aplicativos de reconhecimento de música mais populares é o Shazam. Se você capturar 20 segundos de uma música, não importa se é introdução, verso ou refrão, ele criará uma impressão digital para a amostra gravada, consultará o banco de dados e usará seu algoritmo de reconhecimento de música para dizer exatamente qual música você está ouvindo .

Mas como funciona o Shazam? O algoritmo do Shazam foi revelado ao mundo por seu inventor Avery Li-Chung Wang em 2003. Neste artigo vamos falar sobre os fundamentos do algoritmo de reconhecimento de música do Shazam.

Analógico para Digital - Amostragem de um Sinal

O que é som realmente? É algum tipo de material místico que não podemos tocar, mas que voa em nossos ouvidos e nos faz ouvir coisas?

Claro, este não é bem o caso. Sabemos que, na realidade, o som é uma vibração que se propaga como uma onda mecânica de pressão e deslocamento, através de um meio como o ar ou a água. Quando essa vibração chega aos nossos ouvidos, particularmente ao tímpano, ela move pequenos ossos que transmitem a vibração ainda mais para as pequenas células ciliadas no fundo do ouvido interno. Finalmente, as pequenas células ciliadas produzem impulsos elétricos, que são transmitidos ao nosso cérebro através do nervo auditivo.

Dispositivos de gravação imitam esse processo de maneira bastante próxima, usando a pressão da onda sonora para convertê-la em um sinal elétrico. Uma onda sonora real no ar é um sinal de pressão contínua. Em um microfone, o primeiro componente elétrico a encontrar esse sinal o traduz em um sinal de voltagem analógico - novamente, contínuo. Este sinal contínuo não é tão útil no mundo digital, portanto, antes de poder ser processado, deve ser traduzido em um sinal discreto que possa ser armazenado digitalmente. Isso é feito capturando um valor digital que representa a amplitude do sinal.

A conversão envolve a quantização da entrada e, necessariamente, introduz uma pequena quantidade de erro. Portanto, em vez de uma única conversão, um conversor analógico-digital realiza muitas conversões em pedaços muito pequenos do sinal - um processo conhecido como amostragem

O Teorema de Nyquist-Shannon nos diz qual a taxa de amostragem necessária para capturar uma certa frequência em sinal contínuo. Em particular, para capturar todas as frequências que um humano pode ouvir em um sinal de áudio, devemos amostrar o sinal em uma frequência duas vezes maior do que o alcance da audição humana. O ouvido humano pode detectar frequências aproximadamente entre 20 Hz e 20.000 Hz. Como resultado, o áudio é mais frequentemente gravado a uma taxa de amostragem de 44.100 Hz. Esta é a taxa de amostragem de discos compactos e também é a taxa mais comumente usada com áudio MPEG-1 (VCD, SVCD, MP3). (Esta taxa específica foi originalmente escolhida pela Sony porque poderia ser gravada em equipamentos de vídeo modificados rodando a 25 quadros por segundo (PAL) ou 30 quadros por segundo (usando um gravador de vídeo monocromático NTSC) e cobrir a largura de banda de 20.000 Hz considerada necessária para combinar com o equipamento de gravação analógico profissional da época.) Assim, ao escolher a frequência da amostra que precisa ser gravada, você provavelmente desejará usar 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, basta escolher uma linguagem de programação, encontrar uma biblioteca apropriada, definir a frequência da amostra, número de canais (normalmente mono ou estéreo), tamanho da amostra (por exemplo, amostras de 16 bits ). Em seguida, abra a linha da sua placa de som como qualquer fluxo de entrada e grave em uma matriz de bytes. Veja como isso pode ser feito 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();

Basta ler os dados de TargetDataLine . (Neste exemplo, o sinalizador running é uma variável global que é interrompida por outro thread - por exemplo, se tivermos GUI com o botão STOP.)

 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 neste array de bytes é sinal gravado no domínio do tempo. O sinal no domínio do tempo representa a mudança de amplitude do sinal ao longo do tempo.

No início de 1800, Jean-Baptiste Joseph Fourier fez a notável descoberta de que qualquer sinal no domínio do tempo é equivalente à soma de algum número (possivelmente infinito) de sinais sinusoidais simples, dado que cada componente sinusoidal tem uma certa frequência, amplitude, e fase. A série de senoides que juntos formam o sinal original no domínio do tempo é conhecida como sua 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 senóide que compõe o sinal. Essa representação do sinal é conhecida como domínio da 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.

A animação a seguir demonstra a série de Fourier de uma onda quadrada de 1 Hz e como uma onda quadrada (aproximada) pode ser gerada a partir de componentes senoidais. O sinal é mostrado no domínio do tempo acima e no domínio da frequência abaixo.

Analisar 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 ausentes. Depois disso, pode-se filtrar, aumentar ou diminuir algumas frequências, ou apenas reconhecer o tom exato das frequências dadas.

A Transformada Discreta de Fourier

Então, precisamos encontrar uma maneira de converter nosso sinal do domínio do tempo para o domínio da frequência. Aqui pedimos ajuda à Transformada Discreta de Fourier (DFT). A DFT é uma metodologia matemática para realizar a análise de Fourier em um sinal discreto (amostrado). Ele converte uma lista finita de amostras igualmente espaçadas de uma função na lista de coeficientes de uma combinação finita de senoides complexas, ordenadas por suas frequências, considerando se essas senoides foram amostradas na mesma taxa.

Um dos algoritmos numéricos mais populares para o cálculo da DFT é a transformada rápida de Fourier (FFT). De longe, a variação mais comumente usada de FFT é o algoritmo Cooley-Tukey. Este é um algoritmo de divisão e conquista que divide recursivamente uma DFT em muitas DFTs menores. Enquanto a avaliação de uma DFT requer diretamente operações O( n 2 ) , com uma FFT Cooley-Tukey o mesmo resultado é calculado em operações O( n log n ) .

Não é difícil encontrar uma biblioteca apropriada para FFT. Aqui estão alguns deles:

• C - FFTW
• C++ – EigenFFT
• Java – JTransform
• Python – NumPy
• Ruby – Ruby-FFTW3 (Interface para FFTW)

Abaixo está um exemplo de uma função FFT escrita em Java. (FFT recebe números complexos como entrada. Para entender a relação entre números complexos e funções trigonométricas, leia sobre a 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; }

E aqui está um exemplo de um sinal antes e depois da análise FFT:

Reconhecimento de música: impressão digital de uma música

Um efeito colateral infeliz da FFT é que perdemos uma grande quantidade de informações sobre o tempo. (Embora teoricamente isso possa ser evitado, as despesas gerais da apresentação são enormes.) Para uma música de três minutos, vemos todas as frequências e suas magnitudes, mas não temos ideia de quando na música elas apareceram. Mas esta é a informação chave que faz da música o que ela é! De alguma forma, precisamos saber em que ponto do tempo cada frequência apareceu.

É por isso que introduzimos uma espécie de janela deslizante, ou bloco de dados, e transformamos apenas essa parte da informação. O tamanho de cada pedaço pode ser determinado de algumas maneiras diferentes. Por exemplo, se gravarmos o som, em estéreo, com amostras de 16 bits, a 44.100 Hz, um segundo desse som será de 44.100 amostras * 2 bytes * 2 canais ≈ 176 kB. Se escolhermos 4 kB para o tamanho de um pedaço, teremos 44 pedaços de dados para analisar em cada segundo da música. Essa é uma densidade boa o suficiente para a análise detalhada necessária para a identificação de áudio.

Agora de volta à programação:

 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); }

No loop interno, estamos colocando os dados no domínio do tempo (as amostras) em um número complexo com parte imaginária 0. No loop externo, iteramos todos os pedaços e executamos a análise FFT em cada um.

Assim que tivermos informações sobre a composição de 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 de áudio do Shazam. O principal desafio aqui é como distinguir, no oceano de frequências capturadas, quais frequências são as mais importantes. Intuitivamente, buscamos as frequências de maior magnitude (comumente chamadas de picos).

No entanto, em uma música a faixa de frequências fortes pode variar entre baixo C - C1 (32,70 Hz) e alto C - C8 (4.186,01 Hz). Este é um intervalo enorme para cobrir. Então, em vez de analisar toda a faixa de frequência de uma só vez, podemos escolher vários intervalos menores, escolhidos com base nas frequências comuns de componentes musicais importantes, e analisar cada um separadamente. Por exemplo, podemos usar os intervalos que 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 graves (cobrindo o baixo, por exemplo) e 120 Hz - 180 Hz e 180 Hz - 300 Hz para os tons médios e agudos (cobrindo os vocais e a maioria dos outros instrumentos).

Agora, dentro de cada intervalo, podemos simplesmente identificar a frequência com a maior magnitude. Essa informação forma uma assinatura para esse pedaço 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] < 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)); }

Observe que devemos assumir que a gravação não é feita em perfeitas condições (ou seja, uma “sala de surdos”), e como resultado devemos incluir um fator fuzz. A análise do fator fuzz deve ser levada a sério e, em um sistema real, o programa deve ter a opção de definir esse parâmetro com base nas condições da gravação.

Para facilitar a pesquisa de áudio, essa assinatura se torna a chave em uma tabela de hash. O valor correspondente é a hora em que esse conjunto de frequências apareceu na música, juntamente 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.

Se executarmos uma biblioteca inteira de músicas por meio desse processo de identificação de músicas, podemos construir um banco de dados com uma impressão digital completa de todas as músicas da biblioteca.

O algoritmo da música: identificação da música

Para identificar uma música que está tocando no clube, gravamos a música com nosso telefone e executamos a gravação pelo mesmo processo de impressão digital de áudio acima. Em seguida, podemos começar a pesquisar no banco de dados por tags de hash correspondentes.

Por acaso, muitas das tags de hash corresponderão ao identificador de música de várias músicas. Por exemplo, pode ser que alguma parte da música A soe exatamente como uma parte da música E. Claro, isso não é surpreendente - os músicos sempre “pegaram emprestado” licks e riffs uns dos outros, e hoje em dia os produtores sampleiam outras músicas todas A Hora. Cada vez que combinamos uma tag de hash, o número de correspondências possíveis diminui, 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, e esse é o tempo.

O sample que gravamos no clube pode ser de qualquer ponto da música, então não podemos simplesmente combinar o timestamp do hash combinado com o timestamp do nosso sample. No entanto, com vários hashes correspondentes, podemos analisar o tempo relativo das correspondências e, portanto, aumentar nossa certeza.

Por exemplo, se você observar a tabela acima, verá que a tag hash 30 51 99 121 195 corresponde tanto à música A quanto à música E. Se, um segundo depois, correspondermos ao hash 34 57 95 111 200 , será mais um match para a música A, mas neste caso sabemos que os hashes e as diferenças de tempo correspondem.

 // 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 tomar i 1 e i 2 como momentos na música gravada, e j 1 e j 2 como momentos na música do banco de dados. Podemos dizer que temos duas partidas com diferença de fuso horário se:

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

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

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

Isso nos dá flexibilidade para gravar a música desde o início, meio ou fim.

Finalmente, é improvável que cada momento da música que gravamos no clube corresponda a cada momento correspondente da mesma música em nossa biblioteca, gravada no estúdio. A gravação incluirá muito ruído que introduzirá algum erro nas partidas. Então, em vez de tentar eliminar todas as músicas, exceto a correta, da nossa lista de correspondências, no final, classificamos todas as músicas correspondentes em ordem decrescente de probabilidade, e nossa favorita é a primeira música na lista de classificação.

De cima para baixo

Para responder à pergunta: “Como o Shazam funciona?” aqui está uma visão geral de todo o processo de reconhecimento e correspondência de música, 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 escalável. Não há necessidade especial de relações, e o modelo de dados acaba sendo bem simples, então é um bom caso para usar algum tipo de banco de dados NoSQL.

Como o Shazam funciona? Agora você sabe

Este tipo de software de reconhecimento de músicas pode ser usado para encontrar as 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 de simplesmente Shazaming aquela música nostálgica tocando no rádio do táxi. Por exemplo, pode ajudar a identificar o plágio na música, ou descobrir quem foi a inspiração inicial de alguns pioneiros do blues, jazz, rock, pop ou qualquer outro gênero. Talvez uma boa experiência seja preencher o banco de dados de samples de músicas com as músicas clássicas de Bach, Beethoven, Vivaldi, Wagner, Chopin e Mozart e tentar encontrar as semelhanças entre as músicas. Você pensaria que até Bob Dylan, Elvis Presley e Robert Johnson eram plagiadores!

Mas ainda não podemos condená-los, porque a música é apenas uma onda que ouvimos, memorizamos e repetimos em nossas cabeças, onde evolui e muda até que a gravamos no estúdio e a passamos para o próximo grande gênio musical.