Um pouco de como funciona o Shazam

Este artigo foi originalmente publicado em https://infosimples.com/ por Renan Kataoka em Setembro de 2015. Ele foi importado para o Medium da Infosimples, a nova casa dos artigos da Infosimples.

Shazam é um aplicativo de celular que reconhece quase qualquer música que esteja tocando nos arredores. Você pode estar numa livraria, ao som de um jazz calmante ou numa cafeteria no melhor estilo americano, onde o Jukebox toca um animadíssimo — porém desconhecido — country dos anos 80. Basta abrir o app, gravar um pequeno pedaço da música e o Shazam te mostrará o seu nome, seu artista e onde comprá-la.

Dê alguns segundos ao Shazam e ele descobre a música pra você!

Nesse artigo, baseado nesse post, eu tentarei explicar um pouco do funcionamento deste app.

Músicas digitais

Fisicamente, o som é uma onda mecânica, que se propaga pelo ar com diferentes amplitudes e frequências. Visualmente, ele pode ser representado por curvas irregulares, com altos e baixos. Se você já mexeu no Gravador de Voz do Windows, deve saber do que estou falando.

Quando o computador grava um som, ele tira várias amostras dessa onda contínua, gerando um conjunto de muitos pontos:

Exemplo de como um computador tira amostras de um som. T é o intervalo de tempo entre essas amostras

Se estes pontos estiverem muito próximos um do outro, o computador conseguirá recompô-lo facilmente. Neste caso, imagine que eles estão tão próximos que, se os ligarmos com minúsculas retas, elas se parecerão muito com a onda original. Portanto, quanto maior a taxa de amostragem, (ou seja, menor o intervalo de tempo entre as amostras), mais próximo o som digital será do som original. Em outras palavras, uma boa taxa de amostragem resulta em um som límpido.

Por exemplo, as músicas de um CD (assim como a maioria das músicas que você escuta no seu smartphone ou MP3 Player) são armazenadas a 44100 amostras por segundo (44,1kHz). Um DVD armazena seus arquivos de áudio a mais do dobro dessa taxa: 96kHz. Audiófilos dizem que uma música digital perfeitamente nítida só é atingida à taxa de 192kHz.

Além da qualidade de som, uma taxa de amostragem minimamente aceitável é necessária para que o computador consiga reconstruir a onda original corretamente:

O gráfico acima é exemplo de uma onda reconstruída incorretamente. Perceba que o som reconstituído pelo computador (pontilhado em vermelho) é diferente do som original (em preto). Isso acontece porque duas amostras estão muito afastadas uma da outra, e o computador ‘liga os pontos’ de maneira errada. De acordo com a regra de Nyquist, — e também não é muito difícil de ver — a taxa de amostragem precisa ser pelo menos o dobro da frequência da onda original.

A matemática por trás do Shazam

Quando lidamos com sinais, é muito importante que conheçamos um pouco de trigonometria e números complexos. Vamos simplificar um pouco as coisas pra que você consiga entender os conceitos mais importantes com o mínimo necessário desse conhecimento. Os conceitos mais importantes são os seguintes:

Senos e cossenos
Uma senoide pode ser escrita da seguinte forma:

\(f(t) = D + Asin(k + \omega t) \)

A sinusoid with all its parameters.

Tenha em mente que os parâmetros mais importantes desta função são a amplitude A e a frequência angular \(\omega\), já que eles mudam a forma da onda e nos mostram como ela se comporta ao longo do tempo, enquanto que D e k são parametros que apenas a desloca nas direções de y e x respectivamente. A nos mostra o quão alto a onda pode chegar, e \(\omega \) o quão rápido a onda varia ao longo do eixo dos tempos. Se você tem ambas as informações, é possível descrever completamente a onda.

Números complexos

Números complexos são uma ferramenta auxiliar na matemática. Contudo, no ensino médio, certamente você não deve ter encontrado uma utilidade real pra eles. Apesar deles não terem muito sentido em aplicações cotidianas, suas propriedades podem tornar algumas operações matemáticas muito fáceis. Eles são úteis, por exemplo, em engenharia elétrica, onde constantemente lidamos com correntes, tensões, e outras grandezas periódicas.

Senos, cossenos e números complexos estão fortemente relacionados. Essa relação pode ser expressa na seguinte fórmula que contém a unidade imaginária i: \(f(t) = Ae^{i \omega t}\). Essa notação pode ser um pouco esquisita àqueles que nunca estudaram números complexos muito a fundo. O que significa elevar um número real à unidade imaginária?

Como resultado da expansão da série de MacLaurin, do Cálculo, é possível mostrar que senos e cossenos podem ser escritos com o auxílio de unidade de Euler e de outros parâmetros, elevados a unidade imaginária i. Se você quer ir mais a fundo, recomendo você ler este post, que contém informações bem completas sobre séries e sequências, mas para o entendimento deste artigo é suficiente saber que as principais propriedades de uma senoide podem ser representadas na forma complexa \(f(t) = Ae^{i \omega t}\), uma vez que ela contem ambos A e \(\omega \).f(t) também é igual àquela fórmula que vemos no ensino médio: A(cos(ωt)+isen(ωt)). A única diferença é que nós fizemos o ângulo nela contido (geralmente \(\theta\)) variável no tempo (ωt).

Com isso em mente, podemos mostrar uma forma gráfica diferente de representar uma senoide, com um gráfico apenas para A e \(\omega\). Nós logo vamos ver o porquê disso.

Acima, \(f(t) = sin(20 \pi t)\). Note que A = 1 e \(\omega = \frac{20 \pi}{2 \pi} = 10\). Abaixo de \(f(t), F(w)\), onde explicitamos apenas A e \(\omega \).

Fazendo isso, estamos passando a onda do domínio do tempo para o domínio da frequência. Isso é muito intuivo para senoides simples, mas vai ficar um pouco mais complexo pra ondas irregulares. Felizmente, há uma operação matemática que nos leva de um domínio ao outro. É a chamada Transformada de Fourier:

\( F(\omega) = \int_{-\infty}^\infty f(t){e}^{-i \omega t}\,\mathrm{d}t\)

f(t) é a função no domínio do tempo, enquanto que F(w) é a função no domínio da frequência. Não há a necessidade de entender integrais aqui, só tenha em mente que existe uma maneira algébrica de transformarmos uma função no domínio do tempo para uma no domínio da frequência (e vice-versa — usando a Transformada de Fourier Inversa).

Decompondo formas esquisitas em senoides

Para facilitar a nossa explicação, vamos, estrategicamente somar algumas senoides com diferentes frequências e amplitudes com a ajuda de um software gráfico. Não se preocupe com a função esquisita que escolhemos, por enquanto só observe o seu gráfico

\(f(t) = \frac {4} {\pi}[sin(\pi t) + \frac {sin(3 \pi t)}{3}+ \frac {sin(5 \pi t)}{5}+ \frac {sin(7 \pi t)}{7}+ \frac {sin(9 \pi t)}{9}+ \frac {sin(11 \pi t)}{11}]\)

Note que ela lembra muito uma onda quadrada…

…tanto que se continuarmos somando senoides seguindo este padrão, ela será exatamente uma onda quadrada:

Legal, não?

O ponto que queremos chegar é que podemos conseguir desenhar muitas formas apenas somando senos e cossenos. Na verdade, se o fizermos corretamente, podemos plotar qualquer onda periódica só somando senoides.

Any waveform (even crazy ones) can be written as a sum of sines and cosines!

Essa decomposição nos é útil pois é muito fácil trabalhar com funções trigonométricas.

Contudo, pode ser um pouco confuso trabalhar com tantos senos e cossenos no domínio do tempo já que teremos muitas informações. E é aqui que entra a transformada de Fourier.

Pra entender, dê uma olhada na figura abaixo. Observe como uma onda composta por 6 senoides diferentes (em vermelho) pode ser facilmente representada no domínio da frequência (em azul). Note que ambos os domínios contém a mesma informação, mas o domnínio da frequência as apresenta de uma maneira muito mais simples.

Voltando ao Shazam

O Shazam compara o trecho de música que você gravou com as músicas que ele possui em sua base de dados. Pode parecer muito simples, mas tenha em mente que o Shazam contém dados de mais de 11 milhões de músicas. A busca levaria muito se essa comparação não fosse otimizada.

Sabendo disso, nós precisaríamos gerar ‘elementos’ de nossa gravação que pudessem ser rapidamente comparados com elementos das bases de dados do Shazam. Esses elementos precisam ser gerados da mesma forma. Chamaremos eles de fingerprints.

Um esquema simplificado de como o Shazam faz o seu trabalho

Alguns parágrafos acima falamos um pouco de como uma onda pode ser decomposta numa soma de senoides, as quais podem ser escritas em termos de frequências se aplicarmos a Transformada de Fourier nela. Suponha que você quer fazer isso para um trecho de música que você gravou, só pra ver o que acontece.

No meio do caminho, você vai se deparar com um problema. Lembra de como o computador enxerga essa onda como um conjunto de pontos ao invés de uma curva contínua? Por essa razão, você não pode aplicar a Transformada de Fourier na forma apresentada acima, já que a integral é uma operação definida apenas para intervalos contínuos.

Por causa disso, ao invés de usarmos a Transformada de Fourier convencional, usaremos a chamada Transformada de Fourier Discreta, ou simplesmente DFT (Discrete Fourier Transform), cuja fórmula é:

Onde:

- \(X(n)\) é o domínio da frequência na n-ésima ‘caixa’;

- \(N\) é o tamanho da janela;

- \(x[k]\) é a função (no domínio do tempo) que você deseja transformar;

Note que alguns parâmetros novos apareceram aqui. Isso é porque nós vamos aplicar a DFT várias vezes para pequenos trechos de onda e não na onda inteira de uma vez, como fizemos com a senoide do primeiro exemplo. Isso é pra que nós possamos obter os espectros de frequência de cada pequeno período de tempo, os quais vamos chamar (os períodos de tempo) de blocos. Em outras palavras, nós vamos obter vários gráficos de Amplitude x Frequência (X(n)), um para cada bloco.

Aqui selecionamos um bloco de 0.5s de som com seu espectro de frequências. Teremos uma par desse a cada 0.5s de música. Note que temos muitas frequências presentes aqui, diferentemente do nosso exemplo anterior.

O parâmetro que define o tamanho desse bloco é o N maiúsculo. Chamaremos ele de Tamanho da Janela. Quando maior o tamanho da janela (ou seja, maior a porção de onda ‘selecionada’), maiores serão so nossos blocos e menor será a quantidade de gráficos Amplitude x Frequência (espectro de frequência) que nós obteremos.

Uma janela, cujo tamanho é obrigatoriamente uma potência de 2, não pode ser muito grande nem muito pequena para que consigamos gerar os espectros corretamente. Uma janela grande proporciona uma pequena amostra de blocos, mas é mais precisa ao amostrar as frequências. O oposto acontece para janelas pequenas. Tamanhos de janela padrão estão entre 1024 e 4096.

Essas operações podem ser realizadas facilmente com os módulos matemáticos do Ruby ou do Python. Posteriormente, nós vamos ver um algoritimo pra fazer essas contas mais rápido.

O que queremos dizer com ‘preciso’?

Nos últimos parágrafos eu mencionei o termo ‘precisão’, dizendo que janelas maiores providenciam maior exatidão na amostragem de frequências. Pra entender o que isso significa, nós vamos um pouco mais a fundo nas transformadas de Fourier.

Pra fins didáticos, vamos assumir que a onda que estamos analisando é contínua. Como vimos, nós precisamos aplicar a transformada de Fourier em parte do trecho de música que você gravou. Como estamos assumindo que esta onda é contínua, nós podemos multiplicar essa função (o som) por um degrau de Heaviside pra que ela se torne 0 em todos os pontos, com excessão da parte que desejamos analisar. Podemos assim, aplicar a transformada de Fourier original na nossa onda.

Nota: Se não ficou claro o entendimento sobre o degrau de Heaviside, faça uma leitura rápida no artigo do link. Seu princípio é bem fácil de compreender.

Denotando o pedaço de música gravado por \(S(t)\), a função de Heaviside por \(H(t)\), o trecho do pedaço de música gravado por \(PartOfS(t)\) e a transformada de Fourier por \(\mathcal{F}\), temos:

\(PartOfS(t) = S(t) x H(t)\)

Aplicando a transformada de Fourier de ambos os lados:

\(\mathcal{F}[PartOfS(t)] = \mathcal{F}[S(t) x H(t)]\)

E, do teorema da convolução:

\(\mathcal{F}[PartOfS(t)] = \mathcal{F}[S(t)] \bigotimes \mathcal{F}[H(t)]\)

A convolução é uma operação matemática assim como a divisão e a multiplicação, denotada por \(\bigotimes\). Aqui, não há necessidade de entendê-la completamente. O ponto é que a transformada de Fourier resultante depende do termo que multiplica \(S(t)\). Se nós escolhermos qualquer função diferente do degrau de Heaviside, o resultado da transformada de Fourier será diferente.

A primeira vista não faz sentido escolher outra função que não o degrau de Heaviside para realizar esta operação. Afinal, queremos que \(S(t) = 0\) em qualquer ponto exceto nos quais desejamos operar, certo?

Na verdade não é bem assim. Se \(PartOfS(t)\) é muito pequena, um fenômeno indesejado chamado vazamento espectral pode se acentuar e muitas frequências indesejadas podem aparecer no nosso gráfico. Nesse caso, podemos ajustar uma função de janelamento (parecida com o degrau de Heaviside) para, estrategicamente, reduzir esse vazamento. Três exemplos famosos de funções de janelamento são a janela de Hamming, a janela de Kaiser e a janela de Hann.

Cada janela possui suas peculiaridades, mas em geral, podemos dizer que uma Transformada de Fourier usando a Janela de Hamming fornece resultados consistentes para a maioria dos sinais que vamos analisar.

De volta ao termo ‘preciso’, vimos que se particionarmos um som demasiadamente (ou seja, caso escolhamos uma janela muito pequena), os efeitos do vazamento espectral serão maiores. Essa é uma das razões pela qual você não pode escolher uma janela de tamanho muito baixo.

Ainda, é possível mostrar — apesar de não ser imediato — que, quando aplicamos a DFT em uma onda, é impoossível distinguir duas frequências maiores que \(AudioSampleRate/WindowSize\). Portanto, esse parâmetro, chamado frequência de resolução, vai ficando melhor a medida que o tamanho da janela aumenta. Por exemplo, se nós amostrarmos uma música de 44.1 kHz com uma janela de tamanho 1024, será impossível verificar variações de frequência inferiores a 43.07Hz dentro da música.

Esse detalhe é muito importante. Já que isso ocorre, nós não podemos pensar mais em um espectro contínuo de frequências, mas em ‘porções’ discretas, com vários conjuntos de frequência que chamaremos de ‘caixa’ contendo pequenos intervalos delas. No exemplo acima, a primeira caixa conterá frequências que vão de 0 a 43.07Hz, a segunda caixa conterá frequências que vão de 43.07Hz a 86.14Hz e assim por diante.

Aliás, 43.07Hz é uma frequência de resolução muito ruim. Nós devemos ou aumentar o tamanho da janela ou diminuir a taxa de amostragem do áudio pra obter uma frequência de resolução melhor (ou seja, com menores intervalos entre as frequências).

O que a DFT nos forcece?

Quando aplicamos a DFT para um bloco (a pequena porção de som que você gravou), obteremos com uma porção de números complexos. Como comentamos anteriormente, estes números são muito importantes, pois contêm informação de amplitude e freqüência do nosso som. Se repetirmos esse processo para todos os blocos que compõem o nosso som, obeteremos ainda mais números complexos.

Esse conjunto de números complexos com o decorrer do tempo representam o que chamaremos de espectograma do som. O nosso próximo passo é descobrir como usá-lo pra construir os nossos fingerprints.

O processo de fingerprinting e as ‘targets zones’

Para cada bloco, nós obteremos \(\frac {N}{2}\)caixas em forma de números complexos (isso se deve ao Teorema de Nyquist). Portanto, cada bloco conterá uma porção de elementos que contêm informação de frequência e amplitude daquele som. Sendo assim, precisamos organizar estes elementos de forma que eles condensem apenas as informações mais significativas aos nossos ouvidos.

Em linhas gerais, podemos dizer que num som interpretado pelo corpo humano, a frequência representa o seu tom e a amplitude representa o seu volume;

Se usarmos uma janela de tamanho 1024 em um som contendo uma taxa de amostragem de 11025Hz, por exemplo, obteremos 512 números complexos para cada bloco. Podemos assim filtrar esses números, de tal maneira que restem apenas aqueles que contêm, simultaneamente, as frequências mais significativas e as maiores amplitudes. Faremos isso realizando a seguinte rotina:

• Criar um vetor contendo 6 outros vetores vazios dentro dele. Este vetor será chamado ‘bands’, e terá as seguintes características:
• O primeiro vetor conterá caixa\([A(0)..A(9)]\), que representa a amplitude das 10 primeiras caixas de frequência (5.38Hz a 102.18Hz = \(\frac {FrequencyResolution}{2}\) a \(9*FrequencyResolution + \frac {FrequencyResolution}{2}\);
• O segundo vetor conterá caixa\([A(10)..A(19)]\), representando a amplitude das 10 frequências seguintes (107.56Hz a 204.49 Hz);
• O terceiro vetor conterá caixa\([A(20)..A(39)]\);
• O quarto vetor conterá caixa\([A(40)..A(79)]\);
• O quinto vetor conterá caixa\([A(80)..A(159)]\);
• O sexto vetor conterá caixa\([A(160)..A(511)]\);
• Para cada um dos seis vetores, mandenha somente a maior amplitude de cada um e elimine os outros valores. Além disso, guarde o índice dessas amplitudes num vetor a parte (este passo é muito importante!);
• Tire a média das 6 amplitudes que restaram;
• No vetor de índices, mantenha apenas os índices cujas amplitudes sejam maiores que a média.

​Note que nós iremos chama with the average value of frequencies contained on it. As we don’t know exactly the ones that are inside of it, its the most sensible thing to do.

No item anterior, quando construimos os vetores, nós usamos uma escala bastante peculiar com passos diferentes entre si. Isto se deve ao fato de que o ouvido humano possui percepção logarítimica. Por isso condensamos uma maior quantidade de frequências, especialmente as mais altas, em poucos vetores (ou seja, as últimas bandas contém uma maior extensâo de frequências pois são menos perceptíveis aos nossos ouvidos, enquanto o inverso ocorre com frequências pequenas e intermediárias).

Nós obtivemos um array de índices com no máximo 6 valores. Esses índices contém a informação das frequências cujas amplitudes sâo as maiores de suas bandas. Para obter o seu valor numérico, basta fazer a multiplicação (\(Índice+ ½\)) \(\times\)(\(\frac {SampleRate}{N}\)) nestes valores.

Note que esse processo será feito uma vez para cada caixa, então nós teremos um vetor de até 6 elementos para pequeno período discreto de tempo. Com essas informações, agora conseguimos obter uma relação frequência x tempo, que constituirá uma função. A representação gráfica dela terá esta forma:

5 frequências relevantes no primeiro bloco, 2 no segundo, 1 no terceiro e assim por diante…

Vamos recapitular o que fizemos até então. Primeiro, nós aplicamos a DFT para o som em questão. Isso nos levou do domínio do tempo ao domínio da frequência. Graficamente, nós tinhamos um gráfico de Amplitude x Tempo e obtivemos um gráfico de Amplitude x Frequência. O último passo que descrevemos aqui nos levou do gráfico de Amplitude x Frequência ao gráfico de Frequência x Tempo. Perceba que, no ponto em que estamos, temos um conjunto de medidas que estão se tornando cada vez mais passíveis de comparaçâo.

O próximo passo é discutirmos o como realizar esssa comarações de maneira eficiente.

Eficiência temporal

Imagine que o grafico a esquerda (abaixo) é na verdade um fingerprint de uma música no banco de dados do Shazam e o gráfico a direita é o fingerprint do som que você gravou em seu smartphone.

Dois conjuntos idênticos de 4 pontos.

Eventualmente, nós poderíamos fazer o gráfico da direita ‘caminhar’ pelo gráfico da esquerda e, caso os pontos se sobreponham, diríamos que conseguimos um ‘match’ entre os fingerprints. Contudo, isso seria bastante ineficiente, uma vez que teríamos que fazer muitas comparações, alêm de ter que repetir isso para mais de 11 milhões de músicas diferentes.

Assim, é coerente que criemos regras pra tornarmos essa busca mais eficiente.

O artigo de referência seguere o conceito de zonas-chave (target zones). Elas irão nos ajudar a tornar essas comparações mais rápidas.

As regras que definem uma zona-chave são as seguintes:

• Um ponto no gráfico Frequência x Tempo é biunivocamente relacionada com uma zona-chave. Uma zona-chave de um ponto é chamada de pivô;
• Os pontos serão enumerados de baixo pra cima, da esquerda pra direita;
• A zona-chave de um ponto consiste num conjunto dos cinco pontos subsequentes do (índice do ponto + 3) ponto. Se é impossível formar um conjunto de cinco pontos, o consjunto será constituído do maior número de pontos disponível.
• Se a regra acima é impossível de ser aplicada para um dado ponto, ele não possui zona-chave.

Pontos 2 e 5 e suas respectivas zonas-chave.

Compreendido este conceito, nós faremos associações entre os pivôs e cada um dos pontos que compõem a sua zona-chave. Portanto, para cada pivô, haverá no máximo 5 associações. Elas serão feitas tanto server-side, para todos os pontos das mais de 11 milhões de músicas do Shazam, como client-side, para o pedaço da música que você gravou. Essas associações terão a forma ‘chave’=>’valor’ (um hashtable!).

Tanto para server e client-side, cada chave da associação será um vetor contendo os seguintes elementos:

- \([f(pivo), f(ponto), \Delta t(ponto,pivo)]\), onde \(f\) denota frequência e \(\Delta t\) denota intervalo de tempo.

Note que nós usamos \(\Delta t\) e não o tempo absoluto como um dos elementos identificadores. Isso assegura que nossa busca será independente no tempo.

Para os valores, os identificadores serão um pouco diferentes. Em server-side, eles serão um vetor contendo a seguinte informação:

- \([t(pivo), SongId]\), onde \(t\)denota o tempo absoluto e \(SongId\) denota o ‘Id’ da música no banco de dados.

Em client-side, será apenas \(t(pivo)\).

Assim, nossas associaçôes vão ficar:

Em server-side: \([f(pivo), f(ponto), \Delta t(ponto,pivo)] => [t(pivo), SongId] \)

Em client-side: \([f(pivo), f(ponto), \Delta t(ponto,pivo)] => t(pivo)\)

Vamos ver um exemplo:

Suponhamos que o fingerprint acima se refere a música ‘Beat It’ do Michael Jackson e que sua ID no banco de dados do Shazam é 2243 (só um palpite). As associações para o ponto 2 serão:

• \([2, 2, 1] => [1, 2243] \)
• \([6, 2, 1] => [1, 2243]\)
• \([1, 2, 2] => [1, 2243]\)
• \([2, 2, 3] => [1, 2243]\)
• \([9, 2, 4] => [1, 2243]\)

​

Só tenha em mente que essas frequências que usamos no exemplo são fictícias. 1~9Hz são frequências tão baixas que um humano usual não conseguiria escutar. Em teoria, esses valores vão de 20Hz a 20kHz.

Passos de 1 segundo são igualmente inapropriados, por serem muito grandes. Geralmente, usa-se passos de 0.064~0.256 segundos.

Todas as associações de todos os pontos constituem um fingerprint. Finalmente chegamos neles!

Note como nas chaves nós identificamos pares de frequências (do ponto em relação ao pivô) com suas respectivas distâncias temporais ao invés de o fazermos ponto a ponto com seus tempos absolutos. Isso torna as nossas associações muito mais únicas, melhorando a nossa busca e, ao mesmo tempo, gerando menos ‘falsos positivos’.

Se considerarmos um passo de 0.128s e uma média de 3 frequências significativas por unidade de tempo, uma música de 3 minutos terá um fingerprint com cerca de 27000 associações. Pode parecer bastante, mas vamos ver que ver que este método será muito mais rápido que o método de varredura.

Critérios de correspondência

Do momento da gravação do trecho da música desconhecida a geraçäo do fingerprint, a maior parte das associações que serão geradas serão exatamente iguais as do banco de dados. Se as chaves do banco de dados estiverem indexadas, tudo o que precisamos fazer é coletar todas as músicas que contiverem as chaves da nossa gravação. Se fizermos isso para todas as chaves, obteremos uma lista de músicas candidatas a nossa gravação.

Obviamente, a música com o maior número de correspondências entre associações é a que possui a maior probabilidade de ser aquela que procuramos. Apesar deste método funcionar com a maioria das gravações, não é certo de que isto acontecerá sempre. Por este motivo, é sensato que desenvolvamos critérios de pontuação para otimizar a nossa taxa de correspondência.

Critérios de pontuação

Até então, temos cerca de 95% do nosso trabalho feito. Mas note que as associações dos fingerprints tem informações que ainda não usamos. Tanto em client-side como em server-side, os valores dos fingerprints possuem o atributo ‘tempo absoluto’​. Vamos ver como podemos tirar proveito deste número.

Lembremo-nos da nossa primeira regra das zonas-chave:

• Um ponto no gráfico está biunivocamente relacionado a uma zona-chave.

Isso significa que uma chave de associação é bastante peculiar dentro de um fingerprint de uma canção. Apesar de ser possível que uma música contenha exatamente a mesma chave dentro de sua fingerprint com um valor diferente associado a ela, isso ocorrerá com baixa frequência. Portanto, um par de associações diferentes tem grandes chances de estarem igualmente distanciadas no tempo (i.e.: o tempo absoluto da primeira associação menos o tempo absoluto da segunda associação) tanto nos fingerprints gerados pelo celular como nos fingerprints existentes no banco de dados do Shazam.

Note que nós estamos fazendo duas comparações envelvendo o tempo: uma entre ponto e pivô — o terciro valor no vetor da chave — que vai aparecer diversas vezes em associações diferentes, mas no trio torna-se bastante peculiar — e outra entre duas associações diferentes, usando o tempo absoluto — que é ainda mais peculiar. Desta forma estamos criando um filtro muito poderoso para falsos positivos.

Podemos então determinar um critério de pontuação muito simples:

• Para cada associação correspondente entre o fingerprint da gravação e o fingerprint do banco de dados do Shazam’s, somamos \((+1)\) a pontuação da música correspondente​.

​

• Para cada par de associações correspondentes, tomar a distância no tempo entre elas (uma para o par de associações do celular e outra para o par de associações no BD do Shazam). Se elas forem iguais, somamos \((+1)\). Se elas forem diferentes, somamos \((-1)\).

​

• Para o processo de pontuação acima, tomar o cuidado de ‘caminhar’ pelos pares de associações. Por exemplo, se temos uma correspondência para os valores \(([1, 2, 3], [2, 2, 1], [3, 4, 3], [1, 1, 1], [2, 1, 2])\), poderíamos tomar os seguintes pares: [1, 2, 3] e [2, 2, 1], depois [2, 2, 1] e [3, 4, 3], depois [3, 4, 3] e [1, 1, 1] e assim por diante. Evite manter a primeira chave enquanto muda a segunda, pois a chave estática pode, eventualmente, ser um falso positivo. Isso acabaria somando diversos \((-1)s\) , o que arruinaria o nosso método.
• Para cada sequência de correspondências descritas pelo método acima, somar \((+1)\);

​Lembre-se de que o tempo é quantizado na geração dos fingerprints, então a nossa segunda comparação é confiável o bastante. Ainda, podemos ajustar estes métodos de acordo com as nossas especificações para obter melhores resultados.

Otimizando o processo de fingerprinting

Antes de começar a escrever qualquer código, vamos ver algumas otimizações que podemos fazer para aumentar a performance da nossa busca.

Downsampling

Antes de gerar os nossos fingerprints (tanto em server-side como em client-side), é uma boa ideia reduzir aritificialmente a taxa de amostragem original dos nossos áudios. Isso nos permitirá utilizar uma freqência de resolução estável enquanto reduzimos o número de associações por fingerprint. Como um bônus, vamos reduzir a quantidade de memória ocupada pela gravação no nosso smartphone e o tempo de upload para os servidores do Shazam.

Como exemplo, podemos fazer um downsample de uma música a 44.1kHz para 11kHz, mandendo a taxa de amostragem para elevar a frequência de resolução de 4 vezes o nosso valor original. Apesar dessas mudanças afetarem dramaticamente a qualidade do nosso som, as frequências dominantes se mantêm as mesmas e os fingerprints podem ser gerados normalmente. Para fazer isso, basta tomar a média de cada conjunto de 4 amplitudes antes de criar o vetor de bandas, ao invés de tomar cada um dos seus valores.

Uma alternativa a DFT: O algorítimo de Cooley-Tukey

Vamos recapitular o algorítimo da DFT:

Suponha que escolhemos uma janela de tamanho 1024 para aplicar a DFT numa música de 11025Hz com duraçâo de 3 minutos. Teremos então um intervalo de tempo de (1024/11025) = 0.093s entre cada bloco, que nos fornece (180/0.093) = 1936 blocos.

Para cada caixa, teremos que fazer (1024–1) somas e 1024 multiplicações, totaliando 2047 operações por caixa. Façamos isso 1024 vezes (para cada caixa na janela). Multiplique este valor por 1936. Assim, teremos feito 4 bilhões de operações para uma música.

Mesmo para um PC poderoso, fazer este processo para a biblioteca de 5000 músicas do seu iPod levaria alguns dias. E isso não parece ser muito eficiente…

Felizmente, existe uma maneira mais rápida de realizar este processo, chamado método de Cooley-Tukey, ou simplesmente Transformada Rápida de Fourier (ou FFT). Ele se aproveita da periodicidade de senos e cossenos para calcular recursivamente valores complexos para que eles possam ser reutilizados em contas posteriores.

Não há necessidade de entender esse processo a fundo. Para tanto, precisaremos de um pouco de matemática, então caso você queira pular esta parte, siga em frente. Apenas tenha em mente que há um jeito mais eficiente de calcular a DFT e nós o usaremos posteriormente em nosso código.

Primeiro, vamos dividir a DFT original em duas partes: uma contendo as componentes pares a outra contendo as componentes ímpares. Vamos começar pelas partes pares, as quais denotaremos pelo sufixo even.

Para tomarmos os valores pares da somatória, vamos fazer \(k = 2m\). Como também queremos que 0 seja o limite inferior da soma (apenas pra manter a notação), nós mantemos o índice \(m\) e mudamos o limite superior da soma para \((\frac {N}{2} — 1)\). Assim, teremos:

Para os valores ímpares, os quais denotaremos pelo sufixo odd, faremos \(k = 2m + 1\). Assim:

De tal maneira,

Se nós, estrategicamente, colocarmos \(e^{-2 \pi i n/N}\) em evidência em \(X(n)_{odd}\), teremos:

Chamando o primeiro fator de \(\bar X(n)_{even}\) e o segundo de \(\bar X(n)_{odd}\), teremos que:

E, da periodicidade da FFT:

Voltando ao fator ‘e’, aplicando a propriedade distributiva no termo abaixo, vemos que:

Portanto:

O poder deste método está nestas duas expressões acima.

Vamos esclarecer isto. Para simplificar, vamos criar outra função \(F\):

\( F(n) = \begin{cases} \bar X(n/2) & \quad \text{se } n \text{ é par}\\ \bar X((n+1)/2) & \quad \text{se } n \text{ é ímpar}\\ \end{cases}\)

E, supondo uma janela de N = 8:

Agora, \(X(0)\) pode ser escrito de uma maneira diferente:

Note como F é dependente de \(\bar X(n)_{even}\) e de \(\bar X(n)_{odd}\) Lembre que estes termos contém metade das operações da DFT original.

Também note que devemos calcular \(X(0),X(1),…, X(8)\)para obter todo o espectro.

Agora, voltemos a expressão final. Se tomarmos, por exemplo \( X(4)\)

Ambos \(X(0)\)e \(X(4)\) usam \(F(0)\), \(F(1)\) e o mesmo fato multiplicativo ‘e’. Isso significa que conseguimos obter 2 DFTs de uma vez usando os mesmos cálculos. Estes ainda contêm metade do número de operações da DFT original! Olhe o diagrama abaixo:

Este processo também é conhecido como ‘multiplicação em borboleta’

Este método possui complexidade O(N*log(N)), e para grandes janelas é muito mais rápido que a DFT original.

Caramba, tivemos bastante informação até aqui! Talvez alguma coisas não tenham ficado muito claras, mas tudo fará sentido quando virmos uma aplicação prática em código. Por instante, parabéns pelo esforço em chegar até o final do artigo :)

Originally published at infosimples.com.