Como o Shazam funciona (2022)

 (cameronmacleod.com)
2 pontos por GN⁺ 2023-12-06 | 1 comentários | Compartilhar no WhatsApp
  • O Shazam encontra uma música com apenas alguns segundos de gravação pelo microfone criando uma impressão digital de áudio (fingerprint) e pesquisando no banco de dados, em vez de comparar o áudio inteiro
  • Comparar deslocando a forma de onda original não é viável na prática em uma escala de 10 milhões de músicas, além de sofrer com ruído de microfone, variações de volume e efeitos de frequência
  • O fluxo principal é transformar o áudio em um spectrogram, encontrar picos fortes de frequência e então armazenar pares de picos como hashes para comparação rápida
  • Os picos tendem a permanecer relativamente bem mesmo com ruído e reduzem o volume de dados armazenados, mas precisam estar distribuídos de forma uniforme no tempo e na frequência para permitir reconhecimento em qualquer trecho da música
  • Na etapa de reconhecimento, a diferença Track time - Sample time dos hashes correspondentes é agrupada em um histograma, e a música com a maior concentração em um mesmo bin é escolhida como resposta

O problema que o Shazam precisa resolver

  • O Shazam é um app que grava por alguns segundos uma música tocando ao redor, procura essa música em um banco de dados e mostra o resultado
  • Antes de virar app, o Shazam era um serviço baseado em número de telefone
    • O usuário ligava para um número e aproximava o microfone do celular da música
    • Após 30 segundos, o Shazam encerrava a ligação e enviava por SMS as informações da música que estava tocando
    • Em 2002, a qualidade das chamadas de celular tornava o reconhecimento ainda mais difícil
  • Em um exemplo pequeno, daria para mover um trecho de áudio ao longo da faixa inteira e verificar se há correspondência
    • Mas, sem saber qual é a música, pesquisar em um banco de dados com 10 milhões de músicas aumenta muito o tempo de busca
  • Na prática, uma amostra capturada pelo microfone pode ter ruído de fundo, efeitos de frequência e variações de volume, então uma simples comparação por deslizamento da forma de onda não funciona bem

Fluxo geral do sistema

  • A abordagem do Shazam se divide em dois fluxos: register e recognise
    • register é o fluxo de armazenar a música para que ela possa ser encontrada depois
    • recognise é o fluxo de descobrir a qual música pertence um pequeno trecho de áudio
  • Os dois fluxos passam pelas mesmas etapas de pré-processamento
    • cálculo do spectrogram do áudio
    • busca dos peaks, os componentes de frequência mais fortes no spectrogram
    • formação de hashes a partir de pares de peaks
  • No fluxo de register, os hashes calculados são armazenados no banco de dados
  • No fluxo de recognise, os hashes gerados a partir de um novo áudio são comparados com os hashes do banco de dados, e na etapa de matching a música é identificada

Cálculo do Spectrogram

  • A transformada de Fourier mostra quais frequências existem em um áudio
    • Se aplicarmos a transformada de Fourier a uma senoide de 20Hz, aparece um grande spike perto de 20Hz
    • Como a senoide contém apenas uma frequência, ela também é chamada de pure tone
  • O resultado da transformada de Fourier é o frequency spectrum
    • A representação centrada no eixo do tempo é o time domain
    • A representação centrada no eixo da frequência é o frequency domain
    • O eixo Y do frequency spectrum representa a intensidade de cada componente de frequência, e componentes mais fortes tendem a ser mais audíveis no sinal em time domain
  • Quando várias senoides são somadas, seus componentes de frequência se combinam
    • Se adicionarmos a uma senoide de 20Hz uma senoide de 50Hz com metade da intensidade, aparecerão um spike em 20Hz e um spike menor em 50Hz
    • Todo sinal de áudio pode ser reconstruído a partir dessas ondas
  • O frequency domain revela informações que nem sempre aparecem com clareza no time domain
    • Mesmo que o ruído altere a forma no time domain, os principais spikes de frequência ainda podem continuar nítidos no frequency domain
  • Se aplicarmos a transformada de Fourier apenas uma vez à música inteira, veremos apenas a intensidade total das frequências, mas as frequências reais de uma música mudam ao longo do tempo
    • Ao dividir a música em pequenos trechos, aplicar a transformada de Fourier em cada trecho e juntar os resultados, obtemos um spectrogram
    • O spectrogram representa ao mesmo tempo tempo, frequência e intensidade, e a intensidade pode ser mostrada por cores
  • No spectrogram do exemplo “Like a Stone”, os pontos mais claros, ou seja, a maior parte das frequências fortes, aparece abaixo de 5000Hz
    • Esse tipo de distribuição é comum em música, e a maior parte da faixa de frequências de um piano está entre 27Hz e 4186Hz

Fingerprint baseado em peaks

  • A impressão digital de áudio começa com a busca de peaks no spectrogram
    • Um peak é o componente de frequência mais forte em um determinado instante
    • Em música, um som forte como o de um solo de guitarra pode se tornar o peak naquele momento
  • Os peaks são relativamente menos afetados por ruído
    • Para tornar um peak irreconhecível, o ruído precisa ser maior do que ele
    • Um peak no spectrogram é o componente de frequência mais forte da faixa naquele ponto
  • Armazenar apenas os peaks reduz a quantidade de dados necessária para o fingerprint
    • Em vez de guardar todas as informações de frequência, ficam apenas os componentes mais fortes
    • Com menos dados para pesquisar, a busca do fingerprint fica mais rápida
  • Os peaks precisam estar distribuídos de maneira uniforme tanto no tempo quanto na frequência
    • Se ficarem concentrados em apenas um lado do tempo, amostras de outras partes da música não poderão ser reconhecidas
    • Se ficarem concentrados em uma faixa estreita de frequência, um ruído alto em uma banda específica, como uma buzina de carro, pode mudar a escolha dos peaks e dificultar o reconhecimento daquele trecho

Encontrando peaks com maximum filter

  • Para encontrar peaks de forma uniforme, pode-se usar a técnica de processamento de imagem maximum filter
  • O maximum filter encontra o maior valor na vizinhança de cada pixel e substitui esse pixel pelo valor desse máximo local
    • No exemplo, ele observa uma região 3x3 ao redor de cada pixel
    • Esse processo tem o efeito de expandir os picos locais para a área ao redor
  • O spectrogram após maximum filter parece uma versão de baixa resolução do spectrogram original
    • Isso acontece porque os peaks do sinal se expandem e passam a ocupar outros pixels
    • Caixas da mesma cor correspondem a um único peak local da imagem original
  • O maximum filter tem como parâmetro o tamanho da caixa usado para encontrar o máximo local
    • Com uma caixa pequena, surgem mais peaks
    • Com uma caixa grande, surgem menos peaks
  • A posição dos peaks pode ser recuperada encontrando os pontos em que o spectrogram original e o spectrogram filtrado têm o mesmo valor
    • Pontos que não são peak são substituídos pelo valor do peak local e por isso mudam de valor
    • Apenas os pontos cujo valor permanece igual são peaks
  • Ao desenhar todos os peaks juntos, forma-se um constellation map
    • Esse nome vem da semelhança com uma imagem do céu noturno
  • A quantidade de peaks afeta diretamente o tamanho do fingerprint
    • Se for preciso armazenar milhões de músicas, é importante manter o fingerprint pequeno
    • Reduzir peaks também reduz a precisão e diminui a chance de a amostra fazer matching com a música correta
  • Existem duas formas de reduzir a quantidade de peaks
    • usar os N principais peaks, com N proporcional à duração do áudio para evitar que músicas curtas fiquem super-representadas
    • usar todos os peaks acima de um determinado threshold, o que não garante um tamanho de fingerprint por unidade de tempo, mas pode ser mais preciso

Transformando pares de peaks em hashes

  • Se o fingerprint fosse apenas um conjunto de peaks isolados do spectrogram, a repetição aumentaria rapidamente
    • Se a frequência de cada peak for representada com 10 bits, é possível representar 2^10=1024 frequências individuais
    • Com milhares de pontos por faixa, haveria muita repetição
  • O fingerprint precisa de unicidade
    • Quanto maior a unicidade, mais rápida a busca
    • Isso também ajuda a reconhecer mais músicas
  • A abordagem do Shazam cria hashes com pares de peaks, e não com um peak isolado
    • O hash inclui as frequências fA, fB dos dois peaks e a diferença de tempo ΔT entre eles
    • Se cada peak tiver 10 bits de informação de frequência e ΔT também for representado com 10 bits, teremos 30 bits de informação no total
    • As 2^30=1.073.741.824 possibilidades são muito maiores do que as 1024 possibilidades de um ponto único
  • A geração dos pares usa um anchor point e uma target zone
    • Um ponto é escolhido como anchor point
    • Calcula-se a target zone do spectrogram em relação a esse anchor point
    • O anchor point é combinado em pares com todos os pontos dentro da target zone
  • O artigo do Shazam não explica em detalhe como a target zone é escolhida
    • Na imagem do artigo, a target zone começa um pouco depois do anchor point no tempo e fica centrada na frequência do anchor point
  • Os pares gerados são armazenados no banco de dados como hashes
    • Os componentes do hash são fA, fB e ΔT
    • Como informação adicional, são armazenados o Point A time e o Track ID
    • Point A time e Track ID serão usados depois no matching para localizar um momento específico de uma música específica
  • O conjunto de todos os hashes de uma faixa específica forma o fingerprint dessa faixa

Como funciona o matching

  • No fluxo de recognise, cria-se um fingerprint a partir da amostra e ele é comparado com os fingerprints já armazenados no banco de dados
  • O algoritmo de matching segue quatro etapas
    • buscar no banco de dados todos os hashes que correspondem ao fingerprint da amostra
    • agrupar os hashes por música
    • verificar, em cada música, se os hashes se alinham no tempo
    • escolher a faixa com a maior quantidade de hashes alinhados
  • O abracadabra não pesquisa diretamente a 3-tuple (fA, fB, ΔT), mas a armazena como um único valor retornado por hash(fA, fB, ΔT)
    • Em vez de consultar três valores para cada hash, é possível consultar apenas um
  • Cada hash do banco de dados está associado a um Track ID, o que permite o agrupamento por música
    • Depois desse agrupamento, já é possível atribuir uma pontuação a cada faixa candidata
  • Se a amostra realmente corresponder a uma música, os hashes da amostra devem se alinhar bem a um trecho da música original
    • O ruído pode criar peaks que parecem peaks de outros momentos dentro da amostra
    • Também pode acontecer de um hash coincidir com a música errada
  • O alinhamento é verificado calculando Track time - Sample time para cada hash correspondente
    • Os hashes que realmente correspondem compartilham o mesmo valor de diferença
    • No exemplo, as linhas com diferença 10 são true match, e as outras diferenças são false match
  • Esses valores de diferença são colocados em um histograma, e o maior bin é usado como score da música
    • Em uma música que não combina bem, todos os bins ficam com valores baixos
    • Em uma boa correspondência, aparece um grande spike em um dos bins
  • O motivo para não escolher simplesmente a música com mais hashes correspondentes é o viés de duração da música
    • Músicas longas têm mais chance de acumular matches do que músicas curtas
    • No Spotify, há faixas com mais de 4 horas, o que pode distorcer bastante o resultado

abracadabra e materiais de referência

  • abracadabra é um projeto open source que implementa a abordagem do artigo do Shazam
    • Com o código em Python, é possível acompanhar o processo de spectrogram, busca de peaks, hashing e matching
    • Ele também pode ser usado como library em outros projetos
  • Implementações e materiais relacionados

Leituras relacionadas

1 comentários

 
GN⁺ 2023-12-06
Opiniões no Hacker News

  • Há um vídeo bem produzido do Wall Street Journal explicando o Shazam
    https://www.wsj.com/video/series/in-depth-features/how-shaza...
    Chris, cofundador do Shazam

    • Fico curioso se o motivo de o Shazam ter um escritório em Rancho Bernardo, em San Diego, era o fato de ele ser originalmente de San Diego antes de ir para o Reino Unido
      A Lawn Love alugou a suíte do andar de cima de 2014 a 2018, mas os desenvolvedores do app móvel do Shazam naquele escritório continuaram discretos mesmo depois da aquisição, e nunca ouvimos barulho de champanhe de comemoração

  • Quando o Shazam saiu, em 2008, a abordagem baseada em hashes foi uma escolha inteligente
    Se fosse eu, teria começado criando um jeito de transformar todas as músicas em hashes da forma mais eficiente possível em termos de computação
    Se fosse lançado hoje, a direção básica de P&D provavelmente seria treinar um modelo, mas isso poderia ser muito menos eficiente e mais caro de hospedar
    Parece o tipo de problema em que um modelo se sairia bem, mas, como o número de músicas é finito, é bem possível que o método de hash tenha desempenho muito melhor

    • Mais precisamente, não é que cada música seja transformada em um único hash; cada música é transformada em centenas a milhares de hashes
      A estrutura procura quantos hashes vindos de uma amostra curta — dezenas, ou no máximo algumas poucas centenas — batem, em geral de forma contínua
      Mesmo hoje, acho que isso não seria feito com treinamento de modelo, porque uma quantidade enorme de músicas novas é adicionada todos os dias e seria preciso retreinar continuamente
      Hashes ainda parecem uma abordagem melhor não só em eficiência, mas também em robustez geral
    • A abordagem inteligente de 1975 era o Parsons code, que também era algo próximo de transformar uma música em hash de um jeito calculável de cabeça
      Depois disso, era possível encontrar uma música como quem procura uma palavra no dicionário, e espero que essa ideia não desapareça facilmente
      [1]: https://en.wikipedia.org/wiki/Parsons_code
    • Uma pequena correção: o Shazam não foi lançado em 2008, mas sim em 2002 como um serviço por ligação telefônica, que enviava o resultado por SMS
      O primeiro app para celular foi para BREW, em 2006
      2008 foi apenas quando a Apple lançou a App Store; antes disso, terceiros não podiam criar apps para iPhone
    • Sinceramente, em uma ferramenta como o Shazam não há uma diferença fundamental tão grande entre um banco de dados + algoritmo de hashing e um modelo auto-supervisionado
      Ambos são ótimas soluções de indexação e compressão; a diferença está apenas na escala dos dados
    • Se isso fosse treinado como um modelo, fico curioso sobre como seria possível evitar rodar de novo o processo inteiro de treinamento sempre que uma música nova fosse adicionada
      Talvez exista uma forma de criar um modelo de embeddings capaz de calcular um vetor de embedding para cada música nova sem um retreinamento completo

  • O Shazam é um raro produto que, por 20 anos, não perdeu a sensação de mágica
    É realmente muito próximo do que tecnólogos deveriam mirar

    • Para quem entende tecnicamente, extrair impressões digitais de música é um problema concreto e compreensível, mas, se você entrar nos detalhes sem ver a solução já conhecida, é um problema bastante difícil
      Diferentemente de recursos que parecem parecidos por fora, como reconhecimento de imagens de animais ou objetos, mas que na maioria das vezes são quase uma mágica de machine learning estranha, ele se encaixa em um domínio de problema raro, porém compreensível
    • Ao mesmo tempo, o app que era “toque, ouça e receba o resultado” virou um app inchado, lento e cheio de anúncios
      Lembro que, em um iPhone de geração anterior, ele nem conseguia carregar a tempo, e acabei apagando o app
    • O Google levou isso um passo além
      O recurso Now Playing detecta músicas continuamente e as registra no histórico, e no Google Assistant dá para pesquisar uma música só cantarolando
      Não funciona de forma confiável, mas às vezes acerta em cheio
    • Na verdade, ficou ainda mais mágico
      Tentei encontrar uma música que alguém estava cantando no America’s Got Talent e fiquei surpreso quando o resultado voltou como aquele cantor que apareceu no AGT
      Fiquei pensando se eles indexam até programas de TV
    • Tecnólogos miram produtos assim
      Mas o que gerentes de produto fariam se não continuassem estragando o produto para ganhar bônus e férias?

  • Também existe o Chromaprint, que funciona de um jeito um pouco diferente
    Ele se baseia em padrões de mudança de altura, não nos valores máximos do espectro
    O Chromaprint é usado no AcoustID, um grande banco de dados público que conecta impressões digitais de áudio a gravações do MusicBrainz
    É surpreendente a quantidade enorme de músicas que há nele, mesmo sem tanto suporte comercial quanto o Shazam
    [1]: https://oxygene.sk/2011/01/how-does-chromaprint-work/

    • Acho que o Chromaprint precisa comparar a música inteira
      Ele é bom para detecção de duplicatas, mas o desenho das impressões digitais do Shazam permite combinar um trecho curto com a música inteira

  • É um ótimo texto que captura bem o que um espectrograma faz, e é quase leitura obrigatória para quem quer entender como funciona a extração de impressões digitais de áudio
    Existem algoritmos aproximados parecidos em outras mídias, então vale estudar este texto com calma para entender hashing no mundo real

    • A técnica geral de espectrograma já tinha sido inventada pela Phillips antes do Shazam
      O que o Shazam fez foi aplicar hashing de forma combinatória para reduzir falsos positivos

  • Há um excelente site que trata, por meio de correspondência algorítmica, não de músicas em si, mas da classificação de gêneros e das ramificações de subgêneros criadas por assinaturas de músicas novas
    É um material incrível mantido como projeto paralelo pessoal, mas parece correr risco de desaparecer por motivos como problemas de hospedagem
    Antigamente havia o Music DNA da Pandora ou recursos semelhantes do LastFM, mas este site parece uma rede visual de conexões de toda a música criada pela humanidade até 2023, então seu desaparecimento seria uma perda para toda a web
    Every Noise At Once
    https://everynoise.com

  • É impressionante como esse método é intuitivo e como combina bem com o nosso próprio processo de percepção
    Em linhas gerais, ele identifica fragmentos de melodia e depois tenta encaixá-los em ordem
    É parecido com quando ouvimos apenas 5, 7 ou 10 notas e já reconhecemos alguma coisa
    Acho que já li sobre outros métodos de extração de impressão digital de músicas que dependem de coisas como picos de volume; embora esses métodos também possam funcionar igualmente bem, eles não correspondem em nada ao modo como o nosso cérebro faz isso
    Este método é bem interessante porque não se apoia em “subprodutos artificiais”, mas basicamente funciona de forma parecida com a nossa
    Tecnicamente, nem sempre é melodia, mas na maioria dos casos é muito provável que seja

  • Fico curioso sobre como o Shazam lida com casos em que o eixo do tempo não é linear ou não é constante
    Casos como fitas, wow and flutter, ou situações em que a reprodução fica continuamente mais rápida e mais lenta
    Até onde sei, a extração de impressões digitais é muito sensível ao tempo, e cortar em trechos de cerca de 50 ms não resolve completamente o problema
    Da última vez que vi, a técnica geral para esse tipo de problema, Dynamic Time Warping, tinha um custo computacional alto demais

  • Artigos relacionados. Fico curioso se houver mais
    How Shazam Works (2003 Paper) - https://news.ycombinator.com/item?id=33299853 - outubro de 2022, 1 comentário
    Creating Shazam in Java (2010) - https://news.ycombinator.com/item?id=32530056 - agosto de 2022, 36 comentários
    Shazam turns 20 - https://news.ycombinator.com/item?id=32520593 - agosto de 2022, 227 comentários
    How Shazam Works (2015) - https://news.ycombinator.com/item?id=23806142 - julho de 2020, 7 comentários
    Designing an audio adblocker - https://news.ycombinator.com/item?id=18855029 - janeiro de 2019, 186 comentários
    Show HN: A radio/podcast adblocker featuring ML and Shazam-like fingerprinting - https://news.ycombinator.com/item?id=18459058 - novembro de 2018, 2 comentários
    Show HN: Shazam-like acoustic fingerprinting of continuous audio streams - https://news.ycombinator.com/item?id=15809291 - novembro de 2017, 76 comentários
    How Shazam Works (2015) - https://news.ycombinator.com/item?id=15350729 - setembro de 2017, 13 comentários
    Tell HN: Shazam picks up song from my kitchen light - https://news.ycombinator.com/item?id=11593305 - abril de 2016, 2 comentários
    How Shazam works - https://news.ycombinator.com/item?id=9870408 - julho de 2015, 48 comentários
    Patent infringement claim re: “Creating Shazam in Java” blogpost (2010) - https://news.ycombinator.com/item?id=9594480 - maio de 2015, 18 comentários
    The Shazam Effect (2014) - https://news.ycombinator.com/item?id=9593429 - maio de 2015, 37 comentários
    The Shazam Effect - https://news.ycombinator.com/item?id=8634357 - novembro de 2014, 34 comentários
    Ask HN: Is there an audio search technology that finds exact and similar audio? - https://news.ycombinator.com/item?id=8420141 - outubro de 2014, 3 comentários
    Source code example of the Shazam algorithm - https://news.ycombinator.com/item?id=5724422 - maio de 2013, 16 comentários
    Creating Shazam in Java - https://news.ycombinator.com/item?id=5723863 - maio de 2013, 43 comentários
    An Industrial-Strength Audio Search Algorithm (Shazam) - https://news.ycombinator.com/item?id=2621103 - junho de 2011, 4 comentários
    Shazam's Search for Songs Creates New Music Jobs - https://news.ycombinator.com/item?id=2215295 - fevereiro de 2011, 1 comentário
    How does the music-identifying app Shazam work its magic? - https://news.ycombinator.com/item?id=2214992 - fevereiro de 2011, 2 comentários
    Implementing Shazam with Java in a weekend - https://news.ycombinator.com/item?id=1702975 - setembro de 2010, 23 comentários
    Shazam: not magic after all - https://news.ycombinator.com/item?id=909263 - outubro de 2009, 28 comentários

How does the music-identifying app Shazam work its magic? - https://news.ycombinator.com/item?id=893353 - outubro de 2009, 16 comentários

  • Parece uma abordagem de sentido oposto a uma engenharia semelhante, na qual a indústria da música pop tenta criar hits baseados em gêneros