Comment fonctionne Shazam (2022)

 (cameronmacleod.com)
2 points par GN⁺ 2023-12-06 | 1 commentaires | Partager sur WhatsApp
  • Pour retrouver un morceau à partir de quelques secondes d’enregistrement micro, Shazam ne compare pas l’audio entier : il crée une empreinte audio (fingerprint) et la recherche dans une base de données
  • Une comparaison directe de la forme d’onde par glissement n’est pas réaliste à l’échelle de 10 millions de morceaux, ni face au bruit micro, aux variations de volume et aux effets de fréquence
  • Le principe central consiste à convertir l’audio en spectrogramme, à repérer les pics de fréquence marqués, puis à stocker des paires de pics sous forme de hash pour permettre une comparaison rapide
  • Les pics résistent relativement bien au bruit et réduisent le volume de stockage, mais ils doivent être répartis uniformément dans le temps et les fréquences pour reconnaître n’importe quel segment d’un morceau
  • Lors de la reconnaissance, on regroupe en histogramme les différences temps de la piste - temps de l’échantillon des hash correspondants, puis on choisit comme bonne réponse le morceau le plus fortement concentré dans une même case

Le problème que Shazam doit résoudre

  • Shazam est une application qui enregistre pendant quelques secondes un morceau diffusé autour de vous, le recherche dans une base de données, puis affiche le résultat
  • Avant de devenir une application, Shazam était un service basé sur un numéro de téléphone
    • L’utilisateur appelait ce numéro et devait approcher le micro de son téléphone de la musique
    • Au bout de 30 secondes, Shazam coupait l’appel et envoyait par SMS les informations sur le morceau en cours d’écoute
    • En 2002, la qualité des appels mobiles rendait encore plus difficile la reconnaissance des morceaux
  • Sur un petit exemple, on peut faire glisser un extrait audio sur toute la piste et vérifier s’il correspond
    • Mais si l’on doit chercher dans une base de données de 10 millions de morceaux sans savoir de quel titre il s’agit, le temps de recherche explose
  • Dans la pratique, un échantillon capté au micro peut voir sa forme d’onde modifiée par le bruit de fond, des effets de fréquence et des variations de volume, ce qui rend une simple comparaison par glissement peu fiable

Vue d’ensemble du système

  • L’approche de Shazam se divise en deux flux : register et recognise
    • register est le flux qui stocke un morceau pour pouvoir le retrouver plus tard
    • recognise est le flux qui identifie à quel morceau correspond un court extrait audio
  • Les deux flux passent par les mêmes étapes de prétraitement
    • calcul du spectrogramme de l’audio
    • recherche des pics, c’est-à-dire des composantes fréquentielles les plus fortes du spectrogramme
    • création de hash en associant les pics par paires
  • Le flux register enregistre les hash calculés dans la base de données
  • Le flux recognise compare les hash créés à partir du nouvel audio avec les hash de la base de données pour identifier le morceau à l’étape de matching

Calcul du spectrogramme

  • La transformée de Fourier indique quelles fréquences sont présentes dans un signal audio
    • Si l’on applique la transformée de Fourier à une onde sinusoïdale de 20Hz, un grand pic apparaît autour de 20Hz
    • Comme une onde sinusoïdale ne contient qu’une seule fréquence, on l’appelle aussi pure tone
  • Le résultat de la transformée de Fourier est le spectre fréquentiel
    • Une représentation centrée sur l’axe du temps relève du time domain
    • Une représentation centrée sur l’axe des fréquences relève du frequency domain
    • Sur l’axe Y du spectre fréquentiel, on lit l’intensité de chaque composante de fréquence ; plus une composante est forte, plus elle s’entend dans le signal du time domain
  • Si l’on additionne plusieurs ondes sinusoïdales, leurs composantes fréquentielles se combinent
    • Si l’on ajoute à une onde de 20Hz une onde de 50Hz d’intensité moitié moindre, on obtient un pic à 20Hz et un autre plus petit à 50Hz
    • Tous les signaux audio peuvent être reconstruits à partir de telles ondes
  • Le frequency domain révèle des informations difficiles à voir dans le time domain
    • Même si du bruit modifie la forme du signal dans le time domain, les principaux pics de fréquence peuvent rester bien visibles dans le frequency domain
  • Si l’on applique une seule transformée de Fourier à tout le morceau, on ne voit que l’intensité globale des fréquences, alors qu’en réalité les fréquences d’un morceau varient au fil du temps
    • En découpant le morceau en petits segments, en appliquant une transformée de Fourier à chacun, puis en réunissant le tout, on obtient un spectrogramme
    • Le spectrogramme représente simultanément le temps, la fréquence et l’intensité, cette dernière pouvant être affichée par des couleurs
  • Dans le spectrogramme de l’exemple “Like a Stone”, les points les plus lumineux, donc la plupart des fréquences fortes, apparaissent en dessous de 5000Hz
    • Cette répartition est courante dans la musique ; la plupart des fréquences d’un piano se situent entre 27Hz et 4186Hz

Empreinte basée sur les pics

  • L’empreinte audio commence par la recherche de pics dans le spectrogramme
    • Un pic est la composante fréquentielle la plus forte à un instant donné
    • En musique, un son puissant, comme une note marquée dans un solo de guitare, peut devenir le pic à cet instant
  • Les pics sont relativement moins sensibles au bruit
    • Pour rendre un pic méconnaissable, le bruit doit être plus fort que ce pic
    • Les pics du spectrogramme correspondent aux composantes fréquentielles les plus fortes de la piste
  • Ne stocker que les pics réduit le volume de données nécessaire à l’empreinte
    • On ne conserve pas toutes les informations de fréquence, seulement les composantes les plus fortes
    • Il y a donc moins de données à parcourir, ce qui accélère la recherche d’empreintes
  • Les pics doivent être répartis uniformément à la fois dans le temps et dans les fréquences
    • S’ils se concentrent dans une seule zone temporelle, il devient impossible de reconnaître un extrait provenant du reste du morceau
    • S’ils se concentrent dans une bande de fréquences étroite, un bruit fort sur cette bande, comme un klaxon, peut modifier la sélection des pics et rendre ce passage difficile à reconnaître

Trouver les pics avec un maximum filter

  • Pour trouver des pics de manière uniforme, on peut utiliser la technique de traitement d’image du maximum filter
  • Le maximum filter cherche la valeur maximale dans le voisinage de chaque pixel, puis remplace ce pixel par cette valeur de maximum local
    • Dans l’exemple, on examine une zone de 3x3 autour de chaque pixel
    • Ce traitement a pour effet d’étendre les pics locaux à la zone voisine
  • Le spectrogramme filtré par maximum ressemble à une version basse résolution du spectrogramme d’origine
    • Les pics du signal s’étendent et occupent alors d’autres pixels
    • Les cases de même couleur correspondent chacune à un pic local de l’image d’origine
  • Le maximum filter possède un paramètre de taille de boîte pour définir la zone de recherche du maximum local
    • Une petite boîte produit davantage de pics
    • Une grande boîte produit moins de pics
  • La position des pics est restaurée en cherchant les points où les valeurs du spectrogramme original et du spectrogramme filtré sont identiques
    • Les points qui ne sont pas des pics sont remplacés par la valeur du pic local et changent donc de valeur
    • Seuls les points dont la valeur reste inchangée sont des pics
  • Si l’on trace tous les pics, on obtient une constellation map
    • Ce nom vient de sa ressemblance avec une image du ciel nocturne
  • Le nombre de pics a un impact direct sur la taille de l’empreinte
    • Quand il faut stocker des millions de morceaux, il est important de garder des empreintes compactes
    • Réduire le nombre de pics diminue aussi la précision et le nombre d’occasions de faire correspondre correctement un échantillon au bon morceau
  • Il existe deux façons de réduire le nombre de pics
    • utiliser les N pics les plus forts, avec un N proportionnel à la durée de l’audio pour éviter de surreprésenter les morceaux courts
    • utiliser tous les pics au-dessus d’un certain seuil, ce qui ne garantit pas une taille d’empreinte par unité de temps, mais peut être plus précis

Transformer des paires de pics en hash

  • Si l’empreinte n’était qu’un ensemble de pics individuels du spectrogramme, les doublons augmenteraient vite
    • Si la fréquence de chaque pic est codée sur 10 bits, on peut représenter 2^10=1024 fréquences individuelles
    • Avec des milliers de points par piste, les répétitions deviennent nombreuses
  • L’empreinte doit avant tout être unique
    • Plus elle est unique, plus la recherche est rapide
    • Cela aide aussi à reconnaître davantage de morceaux
  • L’approche de Shazam crée des hash non pas à partir de pics seuls, mais de paires de pics
    • Le hash contient les fréquences fA, fB des deux pics et l’écart temporel ΔT entre eux
    • Si chaque pic porte une fréquence codée sur 10 bits et que ΔT est aussi codé sur 10 bits, cela fait au total 30 bits d’information
    • 2^30=1,073,741,824 possibilités sont bien plus nombreuses que les 1024 possibilités d’un point isolé
  • La création des paires repose sur un point d’ancrage et une zone cible
    • On choisit un point comme anchor point
    • On calcule une target zone du spectrogramme pour cet anchor point
    • On forme une paire entre l’anchor point et tous les points situés dans cette target zone
  • L’article de Shazam n’explique pas en détail comment la target zone est choisie
    • Sur l’illustration de l’article, la target zone commence légèrement après l’anchor point dans le temps et est centrée autour de sa fréquence
  • Les paires créées sont stockées dans la base de données sous forme de hash
    • Les éléments du hash sont fA, fB et ΔT
    • Comme informations supplémentaires, on stocke le temps du point A et le Track ID
    • Le temps du point A et le Track ID servent ensuite, lors du matching, à retrouver un instant précis d’un morceau précis
  • L’ensemble de tous les hash d’une piste constitue l’empreinte de cette piste

Méthode de matching

  • Le flux recognise crée une empreinte à partir de l’échantillon, puis la compare aux empreintes déjà stockées dans la base de données
  • L’algorithme de matching se déroule en quatre étapes
    • récupérer dans la base de données tous les hash qui correspondent à ceux de l’empreinte de l’échantillon
    • regrouper les hash par morceau
    • vérifier, pour chaque morceau, si les hash sont alignés dans le temps
    • choisir la piste qui possède le plus grand nombre de hash alignés
  • abracadabra ne stocke pas directement le triplet (fA, fB, ΔT), mais une valeur unique renvoyée par hash(fA, fB, ΔT)
    • Au lieu de chercher trois valeurs pour chaque hash, on n’en cherche qu’une seule
  • Chaque hash de la base est associé à un Track ID, ce qui permet un regroupement par morceau
    • Une fois ce regroupement fait, on peut attribuer un score à chaque piste candidate
  • Si l’échantillon correspond bien à un morceau, les hash de l’échantillon doivent bien s’aligner sur un segment de la piste d’origine
    • Le bruit peut créer dans l’échantillon des pics qui ressemblent à des pics d’autres instants
    • Il arrive aussi que des hash correspondent à tort à un mauvais morceau
  • On vérifie l’alignement en calculant, pour chaque hash correspondant, la valeur temps de la piste - temps de l’échantillon
    • Les vrais hash correspondants partagent la même valeur de différence
    • Dans l’exemple, les lignes avec une différence de 10 sont les vraies correspondances, les autres étant de fausses correspondances
  • On transforme ces différences en histogramme et on utilise la plus grande case comme score du morceau
    • Pour un morceau qui ne correspond pas bien, toutes les cases de l’histogramme restent faibles
    • Pour un bon match, une forte pointe apparaît dans une même case
  • On ne choisit pas simplement le morceau qui a le plus grand nombre de hash correspondants à cause du biais lié à la longueur des morceaux
    • Les morceaux longs ont naturellement plus de chances d’accumuler des correspondances que les morceaux courts
    • Spotify contient même des pistes de plus de 4 heures, ce qui peut fortement biaiser le résultat

abracadabra et ressources

  • abracadabra est un projet open source qui implémente l’approche décrite dans l’article de Shazam
    • Son code Python permet de suivre le calcul du spectrogramme, la détection des pics, le hashing et le matching
    • Il peut aussi être utilisé comme library dans d’autres projets
  • Implémentations et ressources associées

À lire aussi

1 commentaires

 
GN⁺ 2023-12-06
Avis sur Hacker News

  • Le Wall Street Journal a réalisé une vidéo très bien faite qui explique Shazam
    https://www.wsj.com/video/series/in-depth-features/how-shaza...
    Chris, cofondateur de Shazam

    • Je me demande si Shazam avait un bureau à Rancho Bernardo, à San Diego, parce qu’il était originaire de San Diego avant de partir au Royaume-Uni
      Lawn Love a loué la suite à l’étage au-dessus de 2014 à 2018, mais les développeurs de l’app mobile Shazam dans ce bureau sont restés discrets même après l’acquisition, et je n’ai jamais entendu de bouchons de champagne sauter

  • Quand Shazam est sorti en 2008, son approche basée sur le hachage était un choix astucieux
    À leur place, j’aurais commencé par trouver une façon de transformer tous les morceaux en hachages de la manière la plus efficace possible en calcul
    Si le produit sortait aujourd’hui, l’axe R&D de base serait probablement l’entraînement d’un modèle, ce qui aurait pu être beaucoup moins efficace et plus coûteux à héberger
    C’est un problème sur lequel on a l’impression qu’un modèle ferait du bon travail, mais comme le nombre de morceaux est fini, l’approche par hachage a de fortes chances d’être nettement plus performante

    • Plus précisément, il ne s’agit pas de transformer chaque morceau en un seul hachage, mais de transformer chaque morceau en des centaines à des milliers de hachages
      Le principe est de voir combien de hachages issus d’un court extrait — quelques dizaines, au plus quelques petites centaines — correspondent, et s’ils correspondent globalement de façon continue
      Même aujourd’hui, je ne pense pas qu’on le ferait par entraînement de modèle, parce qu’un très grand nombre de nouveaux morceaux sont ajoutés chaque jour et qu’il faudrait réentraîner en permanence
      Le hachage reste une meilleure approche, non seulement pour l’efficacité, mais aussi pour la robustesse globale
    • En 1975, l’approche ingénieuse était le code de Parsons, qui se rapprochait lui aussi d’un hachage de chanson calculable de tête
      On pouvait ensuite chercher un morceau comme on cherche un mot dans un dictionnaire, et j’espère que cette idée ne disparaîtra pas facilement
      [1]: https://en.wikipedia.org/wiki/Parsons_code
    • Petite correction : Shazam n’a pas été lancé en 2008, mais en 2002 comme service téléphonique, avec les résultats envoyés par SMS
      La première app mobile était destinée à BREW en 2006
      2008 correspond seulement au lancement de l’App Store par Apple ; avant cela, les tiers ne pouvaient pas créer d’apps iPhone
    • Honnêtement, pour un outil comme Shazam, il n’y a pas de différence fondamentale énorme entre une base de données + algorithme de hachage et un modèle auto-supervisé
      Les deux sont d’excellentes solutions d’indexation et de compression, simplement à des échelles de données différentes
    • Si l’on entraînait un modèle pour cela, je me demande comment éviter de relancer tout le processus d’entraînement à chaque ajout de nouveau morceau
      Il existe peut-être une façon de créer un modèle d’embedding capable de calculer un vecteur d’embedding pour chaque nouveau morceau sans réentraînement complet

  • Shazam est l’un de ces rares produits qui, depuis 20 ans, n’a pas perdu son côté magique
    C’est vraiment très proche de ce vers quoi les ingénieurs devraient tendre

    • Pour quelqu’un qui s’y connaît techniquement, l’extraction d’empreintes musicales est un problème concret et compréhensible, mais si l’on entre dans les détails sans avoir vu la solution déjà trouvée, cela devient assez difficile
      Contrairement à des fonctionnalités comme la reconnaissance d’images d’animaux ou d’objets, qui paraissent similaires de l’extérieur mais relèvent surtout d’une étrange magie du machine learning, cela correspond à un domaine rare mais compréhensible
    • En même temps, l’app qui consistait à « toucher, écouter et obtenir le résultat immédiatement » est devenue une app obèse lente et bourrée de pubs
      Je me souviens l’avoir finalement supprimée parce qu’elle n’arrivait même pas à se charger à temps sur un iPhone de génération précédente
    • Google est allé encore plus loin
      La fonction Now Playing détecte les chansons en continu et les conserve dans l’historique, et Google Assistant permet de rechercher un morceau simplement en le fredonnant
      Cela ne marche pas de façon fiable, mais parfois il tombe exactement juste
    • C’est même devenu encore plus magique
      J’ai essayé d’identifier une chanson que quelqu’un chantait dans America’s Got Talent, et j’ai été surpris de voir que le résultat renvoyait au chanteur précis passé dans AGT
      Je me suis demandé s’ils indexaient aussi les programmes TV
    • Les ingénieurs visent ce genre de produits
      Mais que feraient les chefs de produit, sinon continuer à dégrader le produit pour obtenir leurs bonus et leurs vacances ?

  • Il existe aussi Chromaprint, qui fonctionne d’une manière un peu différente
    Il se base sur les motifs de variation de hauteur, et non sur les maxima du spectre
    Chromaprint est utilisé par AcoustID, une grande base de données publique qui relie des empreintes audio à des enregistrements MusicBrainz
    Il est étonnant de voir la quantité énorme de musique qu’elle contient, alors même qu’elle bénéficie de bien moins de soutien commercial que Shazam
    [1]: https://oxygene.sk/2011/01/how-does-chromaprint-work/

    • Il me semble que Chromaprint doit comparer le morceau entier
      C’est utile pour détecter les doublons, mais la conception des empreintes de Shazam permet de faire correspondre un court fragment à un morceau complet

  • Excellent article qui saisit bien ce qu’est un spectrogramme, et presque incontournable pour quiconque veut comprendre le fonctionnement de l’extraction d’empreintes audio
    Comme il existe des algorithmes approximatifs similaires pour d’autres médias, cela vaut la peine d’étudier calmement cet article pour comprendre le hachage dans le monde réel

    • La technique générale du spectrogramme avait déjà été inventée par Philips avant Shazam
      Ce que Shazam a fait, c’est hacher de manière combinatoire afin de réduire les faux positifs

  • Il existe un excellent site qui traite par correspondance algorithmique non pas les chansons, mais la classification par genre et les ramifications en sous-genres produites par les signatures des nouveaux morceaux
    C’est une ressource étonnante, maintenue comme projet personnel parallèle, mais elle semble risquer de disparaître pour des raisons comme des problèmes d’hébergement
    Il existait autrefois Music DNA de Pandora ou une fonctionnalité similaire de LastFM, mais ce site ressemble au réseau visuel de connexions de toute la musique créée par l’humanité jusqu’en 2023 ; s’il disparaissait, ce serait une perte pour tout le Web
    Every Noise At Once
    https://everynoise.com

  • Il est surprenant de voir à quel point cette approche est intuitive, et à quel point elle correspond bien à nos propres processus de perception
    En gros, elle consiste à identifier des fragments de mélodie, puis à essayer de les aligner dans l’ordre
    C’est un peu comme lorsque nous reconnaissons quelque chose après avoir entendu seulement 5, 7 ou 10 notes
    Je crois avoir aussi lu d’autres méthodes d’empreinte audio qui s’appuient sur des éléments comme les pics de volume ; même si elles peuvent fonctionner tout aussi bien, elles ne correspondent absolument pas à la façon dont notre cerveau procède
    Cette méthode ne repose pas sur des « artefacts artificiels » : elle fonctionne fondamentalement d’une manière proche de la nôtre, ce qui est assez élégant
    Techniquement, ce n’est pas toujours une mélodie, mais dans la plupart des cas il est probable que ce le soit

  • Je me demande comment Shazam gère les cas où l’axe temporel n’est pas linéaire ou pas constant
    Par exemple avec les bandes, le wow and flutter, ou les situations où le tempo accélère puis ralentit en continu
    À ma connaissance, l’extraction d’empreintes est très sensible au temps, et même découper en fragments d’environ 50 ms ne résout pas entièrement le problème
    La dernière fois que j’ai regardé, la technique générale pour ce type de problème, le Dynamic Time Warping, était trop coûteuse en calcul

  • Articles connexes. Je serais curieux d’en voir d’autres s’il y en a
    How Shazam Works (2003 Paper) - https://news.ycombinator.com/item?id=33299853 - octobre 2022, 1 commentaire
    Creating Shazam in Java (2010) - https://news.ycombinator.com/item?id=32530056 - août 2022, 36 commentaires
    Shazam turns 20 - https://news.ycombinator.com/item?id=32520593 - août 2022, 227 commentaires
    How Shazam Works (2015) - https://news.ycombinator.com/item?id=23806142 - juillet 2020, 7 commentaires
    Designing an audio adblocker - https://news.ycombinator.com/item?id=18855029 - janvier 2019, 186 commentaires
    Show HN: A radio/podcast adblocker featuring ML and Shazam-like fingerprinting - https://news.ycombinator.com/item?id=18459058 - novembre 2018, 2 commentaires
    Show HN: Shazam-like acoustic fingerprinting of continuous audio streams - https://news.ycombinator.com/item?id=15809291 - novembre 2017, 76 commentaires
    How Shazam Works (2015) - https://news.ycombinator.com/item?id=15350729 - septembre 2017, 13 commentaires
    Tell HN: Shazam picks up song from my kitchen light - https://news.ycombinator.com/item?id=11593305 - avril 2016, 2 commentaires
    How Shazam works - https://news.ycombinator.com/item?id=9870408 - juillet 2015, 48 commentaires
    Patent infringement claim re: “Creating Shazam in Java” blogpost (2010) - https://news.ycombinator.com/item?id=9594480 - mai 2015, 18 commentaires
    The Shazam Effect (2014) - https://news.ycombinator.com/item?id=9593429 - mai 2015, 37 commentaires
    The Shazam Effect - https://news.ycombinator.com/item?id=8634357 - novembre 2014, 34 commentaires
    Ask HN: Is there an audio search technology that finds exact and similar audio? - https://news.ycombinator.com/item?id=8420141 - octobre 2014, 3 commentaires
    Source code example of the Shazam algorithm - https://news.ycombinator.com/item?id=5724422 - mai 2013, 16 commentaires
    Creating Shazam in Java - https://news.ycombinator.com/item?id=5723863 - mai 2013, 43 commentaires
    An Industrial-Strength Audio Search Algorithm (Shazam) - https://news.ycombinator.com/item?id=2621103 - juin 2011, 4 commentaires
    Shazam's Search for Songs Creates New Music Jobs - https://news.ycombinator.com/item?id=2215295 - février 2011, 1 commentaire
    How does the music-identifying app Shazam work its magic? - https://news.ycombinator.com/item?id=2214992 - février 2011, 2 commentaires
    Implementing Shazam with Java in a weekend - https://news.ycombinator.com/item?id=1702975 - septembre 2010, 23 commentaires
    Shazam: not magic after all - https://news.ycombinator.com/item?id=909263 - octobre 2009, 28 commentaires

How does the music-identifying app Shazam work its magic? - https://news.ycombinator.com/item?id=893353 - octobre 2009, 16 commentaires

  • Cela ressemble à une approche inverse d’une ingénierie similaire dans l’industrie de la pop, qui cherche à créer des tubes fondés sur les genres.