Como o Shazam realmente funciona?
(perthirtysix.com/how-the-heck-does-shazam-work)- O reconhecimento de música funciona convertendo as vibrações do ar captadas pelo microfone em uma forma de onda e depois comprimindo isso em um espectrograma e em um pequeno conjunto de picos fortes de frequência para criar a impressão digital da música
- Como a forma de onda bruta muda facilmente conforme o volume e o ambiente de reprodução, é difícil usá-la como critério de identificação; ao aplicar FFT em pequenos trechos, a estrutura de frequências ao longo do tempo fica visível e a comparação se torna estável
- Os picos preservados não são tratados como pontos isolados, mas agrupados em pares de anchor e target zone para gerar hashes, e essas combinações funcionam como hashes de impressão digital específicos o bastante para distinguir uma gravação em particular
- A busca não compara as músicas uma por uma; ela usa uma estrutura hash-first que encontra diretamente pelo hash como chave e, no final, ainda verifica se os intervalos de tempo entre os hashes coincidem para aumentar a confiabilidade
- Bancos de dados massivos baseados em servidor e abordagens on-device diferem em escala e restrições, mas o essencial é descartar quase toda a informação e manter apenas os picos de referência para encontrar rapidamente a música mesmo em clipes curtos e barulhentos
O processo de interpretar o som ao contrário
- O microfone do celular mede as vibrações do ar com um diafragma muito fino e as converte em uma forma de onda, uma sequência de números que representa a pressão do ar ao longo do tempo
- O tímpano do ouvido recebe a mesma onda de pressão, mas o celular trata isso não como o som em si, e sim como uma sequência numérica
- O som recebido é amostrado dezenas de milhares de vezes por segundo, normalmente em 44.100 Hz
- É difícil identificar uma música apenas pela forma de onda bruta: a mesma música, se tocada mais alto, vira uma forma de onda completamente diferente, e músicas diferentes também podem gerar formas de onda parecidas
- Como a forma de onda da mesma música pode mudar conforme o ambiente de reprodução, a própria forma de onda não é adequada como critério de identificação
- Para reduzir esse problema, é preciso dividir a forma de onda em pequenos pedaços e aplicar FFT para decompor quais frequências estão presentes em cada instante
- Em forma de pergunta, isso equivale a: "quais tons puros precisam ser somados para recriar este pequeno trecho de som?"
- Ao empilhar lado a lado o resultado de cada trecho, obtém-se um espectrograma com eixo do tempo, eixo da frequência e eixo do brilho
- A FFT explora o fato de que qualquer forma de onda, por mais complexa que seja, pode ser representada como a soma de ondas senoidais com frequências, amplitudes e fases diferentes
- Por exemplo, ao inserir 1.024 amostras, ela devolve um espectro mostrando quanta energia existe em cada frequência
- Para cada bin de frequência, todos os samples são multiplicados por uma senoide daquela frequência e somados; se aquela frequência estiver no sinal real, a soma cresce, e se não estiver, ela se cancela
- O ponto central da FFT é a velocidade: uma decomposição ingênua exigiria milhões de operações por trecho, mas a FFT reduz isso para algo em torno de n log n usando simetrias matemáticas
- Essa velocidade já é suficiente para rodar centenas de vezes por segundo até em um celular
- O dispositivo continua deslizando essa janela sobre o áudio, aplica FFT a cada trecho e empilha os resultados para formar o espectrograma
- Um exemplo simples com um tom sintético de frequência pura ajuda a entender, mas a música real é muito mais complexa
- Quando música real ou um humming entra pelo microfone, o espectrograma parece muito mais bagunçado, mas a FFT ainda revela a estrutura em tempo real
- No exemplo do navegador, todo o áudio é processado dentro do próprio navegador, sem gravação nem envio externo
A impressão digital fica mais forte quanto menos guarda
- O sistema não armazena o espectrograma inteiro; ele comprime tudo mantendo apenas os maiores picos como um conjunto esparso de pontos
- Ao descartar sinais fracos e manter só os pontos mais fortes, restam apenas os marcos acusticamente importantes
- O motivo de descartar a maior parte é que armazenar e pesquisar o espectrograma completo seria lento demais até para computadores
- Quanto maior o limiar, mais sinais tênues desaparecem e só os grandes picos sobrevivem
- Essa abordagem aumenta a resistência a ruído
- O ruído de fundo adiciona baixa energia ao espectrograma inteiro, mas normalmente não chega a criar o pico mais forte de uma região específica
- Os marcos que permanecem são as frequências dominantes que emergem por cima do ruído
- Em compensação, esse método de impressão digital tende a ter desempenho pior quando alguém canta a música diretamente
- Mesmo cantando muito bem, há grande chance de produzir hashes diferentes dos da gravação original
- Por isso, sistemas mais novos baseados em machine learning tratam humming e canto com base na melodia, e não em frequências exatas
Ligando os pontos para criar hashes
- Um ponto sozinho tem pouco poder de distinção, mas a combinação de dois pontos é muito menos aleatória, então é adequada como hash de impressão digital
- Por exemplo, um 1.200 Hz em certo instante pode aparecer em milhares de músicas, mas a combinação em que 2.400 Hz aparece 0,3 segundo depois é muito mais específica
- O algoritmo toma cada pico como anchor em sequência, define à direita uma target zone com intervalo de tempo e frequência e o emparelha com todos os picos dentro dela
- Cada par gera um hash curto a partir de três números: as duas frequências e a diferença de tempo
- Um hash sempre produz o mesmo resultado para a mesma entrada e funciona como um código curto que muda completamente se a entrada mudar um pouco
- Sistemas do tipo Shazam têm mecanismos para lidar com pequenas variações, mas, em essência, o hash é criado a partir de frequências e timings exatos
- Como resultado, esse hash funciona mais como a impressão digital de uma gravação específica do que da música em abstrato
- Por isso, covers e remixes são mais difíceis de reconhecer
- Mesmo uma única faixa de 3 minutos pode gerar milhares desses hashes de impressão digital, e o banco de dados armazena todos eles
- O celular leva para a etapa de matching um pequeno conjunto de hashes extraídos de um clipe de 5 segundos, enquanto o banco de dados leva milhões de hashes extraídos de um enorme conjunto de músicas
Encontrando a correspondência exata
- Cada hash funciona como uma espécie de endereço, e o sistema consulta diretamente uma tabela gigante para cada hash obtido do clipe, a fim de descobrir quais músicas possuem aquele hash
- Em vez de percorrer as músicas uma por uma, ele usa o próprio hash como chave de acesso
- A abordagem intuitiva song-first teria de verificar cada música individualmente e ver se há sobreposição de hashes, ficando mais lenta conforme o número de músicas cresce
- O texto descreve isso como tempo O(N)
- Um banco de dados de exemplo e uma lista de hashes de um clipe de 5 segundos são usados para visualizar essa ineficiência
- O computador pode inverter isso e processar tudo no modo hash-first
- Para cada hash, ele pergunta diretamente: "quais músicas contêm este hash?"
- É comparável ao índice no fim de um livro: em vez de reler todas as páginas, você vai direto ao verbete da palavra específica
- Essa abordagem torna a consulta quase O(1)
- Seja com 100 músicas ou 100 milhões, o processamento acontece em mais ou menos o mesmo tempo
- Como o número de hashes possíveis é enorme, mesmo com milhões de músicas cada endereço normalmente contém só poucos itens
- Não basta compartilhar o mesmo hash; a verificação final acontece nos intervalos de tempo
- Por exemplo, se dentro do clipe 17403C e 19A998 estão separados por 1,2 segundo, então na música candidata esses mesmos dois hashes também precisam aparecer com 1,2 segundo de intervalo
- Só quando as diferenças de tempo entre hashes coincidem entre si e o número de coincidências é suficiente é que se obtém uma correspondência confiável
- O sistema inteiro é desenhado para tirar proveito do que computadores fazem especialmente bem
- Ele é centrado em comparação de números e consulta por endereços
- Por isso, mesmo diante de milhões de músicas, a consulta completa termina em bem menos de 1 segundo
Abordagens mais modernas
- Muitos serviços de reconhecimento musical, como o Shazam, enviam o clipe de áudio para um servidor e fazem o matching em um grande banco de dados de impressões digitais no servidor
- Essa arquitetura é usada porque o banco de dados é enorme, muda o tempo todo e a busca exige recursos computacionais consideráveis
- Em contrapartida, o reconhecimento on-device da Apple e o Now Playing do Google Pixel executam tudo localmente no celular
- Eles usam um banco de dados menor e selecionado, além de modelos otimizados
- Em vez de buscar cobertura total, priorizam velocidade e também incluem abordagens de machine learning mais sofisticadas, mais resistentes a ruído e a transformações no áudio
- A abordagem on-device é mais rápida e funciona sem internet, mas tem a limitação de trabalhar com um banco de músicas reconhecíveis muito menor
- A incorporação de músicas novas também costuma ser mais lenta
- Se uma mudança de localização for detectada, talvez seja necessário baixar novos dados outra vez
- Diferenças regionais nas músicas populares também influenciam a composição desses dados on-device
- Os hits do Japão e os hits dos Estados Unidos podem ser diferentes
- Quer o matching aconteça no servidor ou dentro do aparelho, a técnica central é a mesma
- Ao descartar a maior parte da informação e manter apenas alguns picos de referência, até um clipe de 5 segundos gravado em um café barulhento se transforma em um conjunto de coordenadas preciso o bastante para apontar uma música entre milhões
- O núcleo do reconhecimento deixa de ser ouvir muita coisa e passa a ser descartar com precisão aquilo que deve ser ignorado
O artigo que serviu de base
- Boa parte do texto se baseia no artigo de 2003 de Avery Wang, An Industrial-Strength Audio Search Algorithm
- Se você quiser se aprofundar em processamento de sinais e no desenho do sistema, esse artigo é o ponto de partida mais direto
- O fluxo completo segue por transformação da forma de onda, seleção de picos, hash de pares de picos, consulta por índice invertido e verificação de alinhamento temporal
- A combinação dessas etapas torna possível identificar músicas rapidamente mesmo a partir de clipes curtos e barulhentos
1 comentários
Comentários do Hacker News
Vale a pena ver também os materiais sobre o Shazam Tem o artigo original em https://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf e, se o interesse for real, também vale procurar a apresentação do autor no YouTube Em https://news.ycombinator.com/item?id=18069968 há uma postagem de um funcionário do Shazam, em https://news.ycombinator.com/item?id=38538996 há uma explicação confirmada por um cofundador, e em https://news.ycombinator.com/item?id=41127726 há uma reprodução do algoritmo em Go No fim das contas, acho que em muitos casos o valor de ML está mais nos dados do que no código em si
Meu palpite recente é mais na linha de que talvez não seja nada disso Com música popular em geral funcionou bem, mas tentei usar o Shazam várias vezes com umas músicas synth bem boas que tocaram no intervalo de uma competição de patinação no gelo e ele não acertou nenhuma Pode ser que ainda não tivessem sido lançadas ou que fossem músicas extremamente de nicho, mas também parece possível que o Shazam simplesmente tenha falhado feio
Isso obviamente é da mesma família de tecnologia usada em ACR de TV Mas o Shazam tem uma reputação muito melhor online, aparentemente porque respeita a intenção e o consentimento do usuário Se algo parecido fosse implementado na TV sem que os dados fossem apenas para vender anúncios, talvez desse para imaginar um formato que realmente beneficiasse o consumidor
Este texto provavelmente é uma das melhores explicações visuais do algoritmo original de audio fingerprinting do artigo do Shazam de 2003 Dito isso, também parece provável que a esta altura eles já tenham migrado para algum modelo de ML em algum momento
Existe um algoritmo chamado DTW(dynamic time warping) que costuma ser ignorado Meu chute é que o Shazam também deve ter usado isso em algum grau
Reconhecer a mesma gravação não é tão difícil Se for a mesma gravação, a progressão de acordes e o timing podem se repetir com precisão, então esse tipo de tecnologia de reconhecimento já existia muito antes de 10 anos atrás Por outro lado, identificar a mesma música em versões cover, ou seja, em gravações diferentes, é bem mais difícil A Audible Magic afirma em https://www.audiblemagic.com/2024/02/07/identifying-cover-songs-live-performances-ai-clones-and-more/ que consegue identificar várias versões ao vivo da mesma música e até paródias, o que naturalmente envolve AI e mais capacidade de processamento
Eu já pensei “lá vamos nós de novo com esse assunto”, mas aí vi que era SCP Esse domínio parece meio suspeito Uma análise mais completa do que o texto de 2022 do CameronMacLeod é https://news.ycombinator.com/item?id=38531428, e o texto da Slate de 2009 é https://news.ycombinator.com/item?id=893353
Acho que preciso colocar isso na minha lista de projetos Seria divertido fazer um Dinosaur game em que o pulo não fosse com tecla, mas com um cocoricó
Fiquei curioso se existe alguma forma de impedir que apps como o Shazam detectem algo Tipo misturar ruído ou usar alguma outra técnica
Em 1986 eu tentei fazer isso como projeto de ciências com um Apple ][c