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é