Comment Shazam fonctionne-t-il, au juste ?

• La reconnaissance musicale consiste à convertir les vibrations de l’air captées par le micro en forme d’onde, puis à les compresser en un spectrogramme et en un petit nombre de pics de fréquence marqués afin de créer l’empreinte du morceau
• Comme la forme d’onde brute varie facilement selon le volume et l’environnement de lecture, elle est difficile à utiliser comme critère d’identification ; il faut appliquer une FFT sur de courts segments pour faire apparaître la structure fréquentielle dans le temps et permettre une comparaison stable
• Les pics conservés ne sont pas traités comme des points isolés, mais regroupés en paires anchor et target zone pour produire des hash ; ces combinaisons servent d’hash d’empreinte assez spécifiques pour distinguer un enregistrement précis
• La recherche ne compare pas les morceaux un par un : elle utilise une architecture hash-first qui retrouve directement les entrées à partir des hash comme clé, puis vérifie à la fin si les écarts temporels entre les hash correspondants coïncident aussi afin d’augmenter la fiabilité
• Les grandes bases de données côté serveur et les approches on-device diffèrent par leur échelle et leurs contraintes, mais l’idée centrale reste de jeter l’essentiel de l’information pour ne garder que des pics repères, afin de retrouver rapidement un morceau même à partir d’un extrait court et bruité

---

Le processus d’interprétation inverse du son

• Le micro d’un téléphone mesure les vibrations de l’air avec un diaphragme très fin, puis les convertit et les stocke sous forme de forme d’onde, c’est-à-dire une suite de nombres représentant la pression de l’air au fil du temps
  • Le tympan de l’oreille reçoit la même onde de pression, mais le téléphone la traite non comme un son en soi, mais comme une séquence de nombres
  • Le son entrant est échantillonné des dizaines de milliers de fois par seconde, généralement à 44 100 Hz
• Avec la seule forme d’onde brute, il est difficile d’identifier un morceau : le même titre joué plus fort produit une forme d’onde totalement différente, et des morceaux différents peuvent aussi produire des formes d’onde semblables
  • Comme l’environnement de lecture peut aussi modifier la forme d’onde d’un même morceau, la forme d’onde elle-même ne convient pas comme critère d’identification
• Pour réduire ce problème, il faut découper la forme d’onde en petits fragments puis appliquer une FFT pour décomposer les fréquences présentes à chaque instant
  • Formulé comme une question : « quels tons purs faut-il additionner pour recréer ce court fragment sonore ? »
  • En empilant côte à côte le résultat de chaque fragment, on obtient un spectrogramme avec un axe du temps, un axe des fréquences et un axe de luminosité
• La FFT exploite le fait que n’importe quelle forme d’onde, aussi complexe soit-elle, peut être exprimée comme une somme d’ondes sinusoïdales de fréquences, d’amplitudes et de phases différentes
  • Par exemple, en lui donnant 1 024 échantillons, elle renvoie un spectre indiquant la quantité d’énergie présente à chaque fréquence
  • Pour chaque bin de fréquence, on multiplie tous les échantillons par la sinusoïde de cette fréquence puis on les additionne ; si cette fréquence est réellement présente dans le signal, la somme augmente, sinon elle s’annule
• Le point clé de la FFT, c’est sa vitesse : une décomposition naïve demanderait des millions d’opérations par fragment, alors que la FFT réduit cela à environ n log n grâce aux symétries mathématiques
  • Cette vitesse permet de l’exécuter des centaines de fois par seconde même sur un téléphone
  • L’appareil fait glisser cette fenêtre en continu sur l’audio, applique la FFT à chaque fragment, puis empile les résultats pour construire le spectrogramme
• Un exemple simple avec une seule fréquence pure aide à comprendre, mais la musique réelle est bien plus complexe
  • Si l’on injecte de la vraie musique ou un fredonnement dans le micro, le spectrogramme paraît bien plus désordonné, mais la FFT en révèle tout de même la structure en temps réel
  • Dans l’exemple du navigateur, tout l’audio est traité à l’intérieur du navigateur, sans enregistrement ni envoi vers l’extérieur

Une empreinte plus forte quand elle contient moins d’information

• Le système ne stocke pas l’intégralité du spectrogramme : il ne conserve que les pics les plus élevés, qu’il compresse en un ensemble clairsemé de points
  • En éliminant les signaux faibles et en ne gardant que les points les plus puissants, on ne conserve que les repères acoustiquement importants
• Si l’on jette ainsi l’essentiel, c’est parce que stocker et rechercher dans tout le spectrogramme serait trop lent, même pour un ordinateur
  • Plus le seuil est élevé, plus les signaux faibles disparaissent et seuls les grands pics subsistent
• Cette approche augmente la résistance au bruit
  • Le bruit de fond ajoute de l’énergie faible sur l’ensemble du spectrogramme, mais ne crée généralement pas les pics dominants d’une zone donnée
  • Les repères restants sont donc les fréquences dominantes qui émergent malgré le bruit
• En contrepartie, cette méthode d’empreinte tend à moins bien fonctionner quand on chante directement le morceau
  • Même en chantant très juste, il y a de fortes chances que les hash produits diffèrent de ceux de l’original
  • C’est pourquoi des systèmes basés sur le machine learning plus récents traitent les fredonnements et le chant à partir de la mélodie plutôt que des fréquences exactes

Relier les points pour créer des hash

• Un point seul distingue mal, mais une combinaison de deux points est beaucoup moins fortuite, ce qui la rend adaptée comme hash d’empreinte
  • Par exemple, un simple 1 200 Hz à un moment donné peut apparaître dans des milliers de morceaux, mais la combinaison d’un 1 200 Hz suivi 0,3 seconde plus tard d’un 2 400 Hz est bien plus spécifique
• L’algorithme prend chaque pic à tour de rôle comme anchor, définit à sa droite une target zone avec une plage temporelle et fréquentielle, puis l’associe à tous les pics qu’elle contient
  • Chaque paire produit un court hash à partir de trois nombres : les deux fréquences et l’écart de temps
• Un hash fonctionne comme un code court qui donne toujours le même résultat pour la même entrée, mais une valeur complètement différente dès que l’entrée change un peu
  • Les systèmes de type Shazam ont des mécanismes pour gérer de petites variations, mais fondamentalement le hash est construit à partir de fréquences et de timings exacts
• En pratique, ce hash agit donc moins comme l’empreinte du morceau lui-même que comme celle d’un enregistrement précis
  • C’est pourquoi les reprises ou les remixes sont plus difficiles à reconnaître
• Même un morceau de 3 minutes peut produire plusieurs milliers de ces hash d’empreinte, et la base de données les stocke tous
  • Le téléphone arrive avec un petit nombre de hash tirés d’un extrait de 5 secondes, tandis que la base de données dispose de millions de hash extraits d’un très grand nombre de morceaux avant d’entrer dans l’étape de matching

Trouver la correspondance exacte

• Chaque hash sert en quelque sorte d’adresse ; pour chacun des hash obtenus depuis l’extrait, le système interroge directement une immense table afin de trouver les morceaux qui contiennent ce hash
  • Au lieu de parcourir les morceaux un par un, il utilise le hash lui-même comme clé d’accès
• L’approche intuitive song-first oblige à examiner tous les morceaux un à un et à vérifier les recouvrements de hash, ce qui ralentit à mesure que le nombre de morceaux augmente
  • Le texte la décrit comme une complexité en O(N)
  • Une base de données d’exemple et une liste de hash d’un extrait de 5 secondes servent à visualiser cette inefficacité
• L’ordinateur peut inverser le raisonnement avec une approche hash-first
  • Pour chaque hash, il demande directement : « quels morceaux contiennent ce hash ? »
  • Le texte compare cela à l’index d’un livre : au lieu de relire toutes les pages, on va directement à l’entrée du mot recherché
• Cette approche rend la recherche proche de O(1)
  • Qu’il y ait 100 morceaux ou 100 millions, le traitement prend globalement un temps comparable
  • Comme le nombre de hash possibles est très élevé, même avec des millions de morceaux, chaque adresse ne contient généralement qu’un petit nombre d’entrées
• Le fait de partager des hash identiques ne suffit pas : la vérification finale porte sur les écarts temporels
  • Par exemple, si 17403C et 19A998 sont espacés de 1,2 seconde dans l’extrait, alors le morceau candidat doit présenter ces deux mêmes hash avec le même écart de 1,2 seconde
  • Il faut que les différences temporelles entre les hash correspondants s’alignent, et qu’il y ait suffisamment de correspondances, pour obtenir un matching fiable
• L’ensemble du système est conçu pour exploiter les tâches que les ordinateurs exécutent particulièrement bien
  • Il repose surtout sur la comparaison de nombres et la recherche par adresse
  • C’est pourquoi, même face à des millions de morceaux, toute la recherche se termine en bien moins d’une seconde

Des approches plus modernes

• De nombreux services de reconnaissance musicale comme Shazam envoient l’extrait audio à un serveur, où le matching est effectué dans une vaste base de données d’empreintes
  • Cette architecture est utilisée parce que la base de données est très grande, évolue en permanence et demande une puissance de calcul importante pour la recherche
• À l’inverse, la reconnaissance on-device d’Apple et Now Playing sur les Google Pixel exécutent tout localement sur le téléphone
  • Ils utilisent une base de données plus petite et plus sélective, ainsi que des modèles optimisés
  • Ils privilégient la vitesse à l’exhaustivité complète, et peuvent aussi intégrer des approches de machine learning plus sophistiquées, plus robustes au bruit et aux transformations audio
• L’approche on-device est plus rapide et fonctionne sans connexion Internet, mais elle a pour contrainte une base de morceaux reconnus bien plus réduite
  • L’ajout de nouveaux titres y est généralement plus lent
  • Si un changement de localisation est détecté, il peut être nécessaire de récupérer de nouvelles données
• Les différences de popularité musicale selon les régions influencent aussi la composition des données on-device
  • Les hits au Japon ne sont pas forcément les mêmes qu’aux États-Unis
• Que le matching ait lieu sur serveur ou dans l’appareil, la technique clé reste la même
  • En jetant la majorité des informations pour ne garder qu’un petit nombre de pics repères, même un extrait de 5 secondes enregistré dans un café bruyant devient un ensemble de coordonnées suffisamment précis pour désigner un morceau parmi des millions
  • Au fond, l’essentiel de la reconnaissance n’est pas tant d’écouter beaucoup que de savoir éliminer avec précision ce qu’il faut ignorer

L’article scientifique à l’origine

• Une grande partie du texte s’appuie sur l’article de 2003 d’Avery Wang, An Industrial-Strength Audio Search Algorithm
  • Pour approfondir le traitement du signal et la conception du système, cet article constitue le point de départ le plus direct
• Le déroulé complet va de la transformation de la forme d’onde à la sélection des pics, au hash de paires de pics, à la recherche par index inversé, puis à la vérification par alignement temporel
  • La combinaison de ces étapes permet d’identifier rapidement un morceau même à partir d’un extrait court et bruité

[GN⁺]

Avis sur Hacker News

• Ce serait bien de consulter aussi des ressources sur Shazam Il y a l’article original : https://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf, et si le sujet vous intéresse vraiment, la présentation YouTube de l’auteur vaut aussi le détour https://news.ycombinator.com/item?id=18069968 contient un message d’un employé de Shazam, https://news.ycombinator.com/item?id=38538996 une explication validée par le cofondateur, et https://news.ycombinator.com/item?id=41127726 une reproduction de l’algorithme en Go Au final, je pense que même en ML, la valeur des données dépasse souvent celle du code lui-même

• Mon intuition récente est que ce n’est peut-être pas du tout le cas Ça marchait plutôt bien sur la musique populaire, mais j’ai essayé plusieurs fois de Shazam-er des morceaux de synthé assez sympas passés pendant les pauses d’une compétition de patinage sur glace, et il n’en a trouvé aucun correctement C’étaient peut-être des morceaux pas encore sortis ou extrêmement niche, mais il est aussi possible que Shazam ait simplement complètement échoué

• C’est évidemment la même famille de technologies que celle utilisée pour l’ACR des TV Mais si Shazam a une bien meilleure réputation en ligne, c’est sans doute parce qu’il respecte l’intention et le consentement de l’utilisateur Si on implémentait quelque chose de similaire sur les TV sans que les données servent uniquement à vendre de la pub, on pourrait peut-être avoir quelque chose de réellement bénéfique pour le consommateur

  • Cela dit, si la valeur se limite au fait d’indiquer le titre de l’émission ou du film en cours, ce n’est finalement pas très différent des infos qui s’affichent déjà quand on appuie sur pause

• Cet article est probablement l’une des meilleures explications visuelles de l’algorithme original d’audio fingerprinting du papier Shazam de 2003 Cela dit, j’imagine qu’à un moment ils sont probablement passés à un modèle de ML

• Il existe un algorithme appelé DTW (dynamic time warping), souvent négligé Intuitivement, je me dis que Shazam en utilisait peut-être aussi dans une certaine mesure

  • J’ai déjà utilisé DTW autrefois pour le suivi de bots sur un site de réseau social donné Les bots ont tendance à agir en meute, donc DTW fonctionne bien pour aligner souplement des comportements répétés avec décalage

• Reconnaître le même enregistrement n’est pas si difficile Si c’est exactement le même enregistrement, la progression harmonique et le timing peuvent être répétés à l’identique, donc ce type de reconnaissance existait déjà bien avant il y a dix ans En revanche, reconnaître une version cover du même morceau à partir d’un enregistrement différent est bien plus difficile Audible Magic affirme dans https://www.audiblemagic.com/2024/02/07/identifying-cover-songs-live-performances-ai-clones-and-more/ pouvoir identifier plusieurs versions live d’un même titre ainsi que des parodies, mais cela repose évidemment sur de l’IA et davantage de calcul

  • Dire que ce n’est pas si difficile omet énormément de choses À l’échelle de la société entière, ça peut sembler une technologie simple résolue depuis longtemps, mais si on demandait à des développeurs individuels de la recréer eux-mêmes sans chercher la réponse, je doute qu’ils soient nombreux à y arriver réellement
  • On parle de quelque chose qui date d’au moins plus de 20 ans À l’époque où je faisais du consulting pour Gracenote, j’ai le souvenir d’avoir vu comment cela fonctionnait
  • Dans ce cas, il suffirait peut-être simplement de supprimer les informations de timing

• Je me suis dit « encore ce sujet ? », puis j’ai vu que c’était SCP Ce domaine a l’air un peu suspect Pour une analyse plus complète que l’article de CameronMacLeod de 2022, il y a https://news.ycombinator.com/item?id=38531428, et pour l’article de Slate de 2009, c’est https://news.ycombinator.com/item?id=893353

  • Je ne vois pas très bien ce que signifie SCP dans ce contexte Le secure copy auquel je pense d’habitude ne colle pas du tout Merci quand même pour les liens ; la question du titre m’intrigue vaguement depuis longtemps, mais je ne m’y étais jamais vraiment plongé, donc je vais lire les trois
  • Cela dit, les éléments interactifs de cet article sont plutôt réussis

• Il faut que j’ajoute ça à ma liste de projets Un Dinosaur game où l’on saute non pas avec une touche, mais en faisant un cocorico, ça pourrait être drôle

• Je me demande s’il existe un moyen d’empêcher les applications comme Shazam de détecter un morceau En ajoutant du bruit, par exemple, ou avec d’autres techniques

  • À moins que le bruit ne soit plus fort que l’original sur certaines fréquences dominantes, ça me paraît difficile L’article en donne aussi un exemple : pour accélérer la recherche, l’algorithme ne conserve en gros que les pics de fréquence et jette presque tout le reste
  • Les producteurs et les DJ règlent généralement ce problème en ne sortant tout simplement pas le morceau, ou en le publiant bien plus tard

• J’ai fait ça comme projet scientifique en 1986 sur Apple ][c