Comment fonctionne Shazam ? Algorithmes de reconnaissance musicale, empreintes digitales et traitement

Vous entendez une chanson familière dans le club ou le restaurant. Vous avez écouté cette chanson il y a mille fois, et la sentimentalité de la chanson touche vraiment votre cœur. Vous voulez désespérément le cœur demain, mais vous ne vous souvenez plus de son nom ! Heureusement, dans notre incroyable monde futuriste, vous avez un téléphone avec un logiciel de reconnaissance musicale installé, et vous êtes sauvé. Vous pouvez vous détendre, car le logiciel vous a dit le nom de la chanson, et vous savez que vous pouvez l'entendre encore et encore jusqu'à ce qu'elle fasse partie de vous… ou que vous en ayez marre.

Les technologies mobiles, ainsi que les énormes progrès du traitement du signal audio, nous ont donné aux développeurs d'algorithmes la possibilité de créer des outils de reconnaissance musicale. L'une des applications de reconnaissance musicale les plus populaires est Shazam. Si vous capturez 20 secondes d'une chanson, qu'il s'agisse d'une intro, d'un couplet ou d'un refrain, il créera une empreinte digitale pour l'échantillon enregistré, consultera la base de données et utilisera son algorithme de reconnaissance musicale pour vous dire exactement quelle chanson vous écoutez. .

Mais comment fonctionne Shazam ? L'algorithme de Shazam a été révélé au monde par son inventeur Avery Li-Chung Wang en 2003. Dans cet article, nous allons passer en revue les principes fondamentaux de l'algorithme de reconnaissance musicale de Shazam.

Analogique vers numérique - Échantillonnage d'un signal

Qu'est-ce que le son vraiment ? Est-ce une sorte de matière mystique que nous ne pouvons pas toucher mais qui vole dans nos oreilles et nous fait entendre des choses ?

Bien sûr, ce n'est pas tout à fait le cas. Nous savons qu'en réalité, le son est une vibration qui se propage comme une onde mécanique de pression et de déplacement, à travers un milieu tel que l'air ou l'eau. Lorsque cette vibration arrive à nos oreilles, en particulier le tympan, elle déplace de petits os qui transmettent la vibration plus loin aux petites cellules ciliées situées au plus profond de notre oreille interne. Enfin, les petites cellules ciliées produisent des impulsions électriques, qui sont transmises à notre cerveau par le nerf auditif de l'oreille.

Les appareils d'enregistrement imitent assez fidèlement ce processus, en utilisant la pression de l'onde sonore pour la convertir en un signal électrique. Une onde sonore réelle dans l'air est un signal de pression continu. Dans un microphone, le premier composant électrique à rencontrer ce signal le traduit en un signal de tension analogique - encore une fois, continu. Ce signal continu n'est pas si utile dans le monde numérique, donc avant de pouvoir être traité, il doit être traduit en un signal discret qui peut être stocké numériquement. Cela se fait en capturant une valeur numérique qui représente l'amplitude du signal.

La conversion implique la quantification de l'entrée, et elle introduit nécessairement une petite quantité d'erreur. Par conséquent, au lieu d'une seule conversion, un convertisseur analogique-numérique effectue de nombreuses conversions sur de très petites parties du signal - un processus connu sous le nom d'échantillonnage

Le théorème de Nyquist-Shannon nous indique quel taux d'échantillonnage est nécessaire pour capturer une certaine fréquence dans un signal continu. En particulier, pour capter toutes les fréquences qu'un humain peut entendre dans un signal audio, nous devons échantillonner le signal à une fréquence double de celle de la plage d'audition humaine. L'oreille humaine peut détecter des fréquences comprises approximativement entre 20 Hz et 20 000 Hz. Par conséquent, l'audio est le plus souvent enregistré à un taux d'échantillonnage de 44 100 Hz. C'est le taux d'échantillonnage des disques compacts, et c'est aussi le taux le plus couramment utilisé avec l'audio MPEG-1 (VCD, SVCD, MP3). (Ce taux spécifique a été choisi à l'origine par Sony car il pouvait être enregistré sur un équipement vidéo modifié fonctionnant à 25 images par seconde (PAL) ou 30 images par seconde (à l'aide d'un enregistreur vidéo monochrome NTSC) et couvrir la bande passante de 20 000 Hz jugée nécessaire pour correspondre à l'équipement d'enregistrement analogique professionnel de l'époque.) Ainsi, lors du choix de la fréquence de l'échantillon à enregistrer, vous voudrez probablement opter pour 44 100 Hz.

Enregistrement - Capturer le son

L'enregistrement d'un signal audio échantillonné est facile. Étant donné que les cartes son modernes sont déjà équipées de convertisseurs analogique-numérique, choisissez simplement un langage de programmation, trouvez une bibliothèque appropriée, définissez la fréquence de l'échantillon, le nombre de canaux (généralement mono ou stéréo), la taille de l'échantillon (par exemple, des échantillons 16 bits ). Ouvrez ensuite la ligne de votre carte son comme n'importe quel flux d'entrée et écrivez dans un tableau d'octets. Voici comment cela peut être fait en Java :

 private AudioFormat getFormat() { float sampleRate = 44100; int sampleSizeInBits = 16; int channels = 1; //mono boolean signed = true; //Indicates whether the data is signed or unsigned boolean bigEndian = true; //Indicates whether the audio data is stored in big-endian or little-endian order return new AudioFormat(sampleRate, sampleSizeInBits, channels, signed, bigEndian); } final AudioFormat format = getFormat(); //Fill AudioFormat with the settings DataLine.Info info = new DataLine.Info(TargetDataLine.class, format); final TargetDataLine line = (TargetDataLine) AudioSystem.getLine(info); line.open(format); line.start();

Lisez simplement les données de TargetDataLine . (Dans cet exemple, le drapeau running est une variable globale qui est arrêtée par un autre thread - par exemple, si nous avons une interface graphique avec le bouton STOP.)

 OutputStream out = new ByteArrayOutputStream(); running = true; try { while (running) { int count = line.read(buffer, 0, buffer.length); if (count > 0) { out.write(buffer, 0, count); } } out.close(); } catch (IOException e) { System.err.println("I/O problems: " + e); System.exit(-1); }

Domaine temporel et domaine fréquentiel

Ce que nous avons dans ce tableau d'octets est un signal enregistré dans le domaine temporel. Le signal dans le domaine temporel représente le changement d'amplitude du signal dans le temps.

Au début des années 1800, Jean-Baptiste Joseph Fourier a fait la découverte remarquable que tout signal dans le domaine temporel équivaut à la somme d'un nombre (éventuellement infini) de signaux sinusoïdaux simples, étant donné que chaque composante sinusoïdale a une certaine fréquence, amplitude, et phases. La série de sinusoïdes qui forment ensemble le signal original dans le domaine temporel est connue sous le nom de série de Fourier.

En d'autres termes, il est possible de représenter n'importe quel signal temporel en donnant simplement l'ensemble des fréquences, des amplitudes et des phases correspondant à chaque sinusoïde qui compose le signal. Cette représentation du signal est connue sous le nom de domaine fréquentiel. À certains égards, le domaine fréquentiel agit comme un type d'empreinte digitale ou de signature pour le signal dans le domaine temporel, fournissant une représentation statique d'un signal dynamique.

L'animation suivante montre la série de Fourier d'une onde carrée de 1 Hz et comment une onde carrée (approximative) peut être générée à partir de composantes sinusoïdales. Le signal est affiché dans le domaine temporel ci-dessus et dans le domaine fréquentiel ci-dessous.

L'analyse d'un signal dans le domaine fréquentiel simplifie énormément de choses. C'est plus pratique dans le monde du traitement numérique du signal car l'ingénieur peut étudier le spectre (la représentation du signal dans le domaine fréquentiel) et déterminer quelles fréquences sont présentes et lesquelles manquent. Après cela, on peut faire du filtrage, augmenter ou diminuer certaines fréquences, ou simplement reconnaître le ton exact à partir des fréquences données.

La transformée de Fourier discrète

Nous devons donc trouver un moyen de convertir notre signal du domaine temporel au domaine fréquentiel. Ici, nous faisons appel à la transformée de Fourier discrète (DFT) pour nous aider. La DFT est une méthodologie mathématique pour effectuer une analyse de Fourier sur un signal discret (échantillonné). Il convertit une liste finie d'échantillons équidistants d'une fonction en la liste des coefficients d'une combinaison finie de sinusoïdes complexes, ordonnés par leurs fréquences, en considérant si ces sinusoïdes avaient été échantillonnés à la même fréquence.

L'un des algorithmes numériques les plus populaires pour le calcul de la DFT est la transformée de Fourier rapide (FFT). La variante de loin la plus couramment utilisée de la FFT est l'algorithme Cooley-Tukey. Il s'agit d'un algorithme de division pour régner qui divise de manière récursive une DFT en plusieurs petites DFT. Alors que l'évaluation d'une DFT nécessite directement O( n 2 ) opérations, avec une FFT Cooley-Tukey le même résultat est calculé en O( n log n ) opérations.

Il n'est pas difficile de trouver une bibliothèque appropriée pour FFT. En voici quelques-uns :

• C – FFTW
• C++ – EigenFFT
• Java – JTransform
• Python – NumPy
• Ruby – Ruby-FFTW3 (interface avec FFTW)

Vous trouverez ci-dessous un exemple de fonction FFT écrite en Java. (FFT prend des nombres complexes en entrée. Pour comprendre la relation entre les nombres complexes et les fonctions trigonométriques, lisez la formule d'Euler.)

 public static Complex[] fft(Complex[] x) { int N = x.length; // fft of even terms Complex[] even = new Complex[N / 2]; for (int k = 0; k < N / 2; k++) { even[k] = x[2 * k]; } Complex[] q = fft(even); // fft of odd terms Complex[] odd = even; // reuse the array for (int k = 0; k < N / 2; k++) { odd[k] = x[2 * k + 1]; } Complex[] r = fft(odd); // combine Complex[] y = new Complex[N]; for (int k = 0; k < N / 2; k++) { double kth = -2 * k * Math.PI / N; Complex wk = new Complex(Math.cos(kth), Math.sin(kth)); y[k] = q[k].plus(wk.times(r[k])); y[k + N / 2] = q[k].minus(wk.times(r[k])); } return y; }

Et voici un exemple de signal avant et après analyse FFT :

Reconnaissance musicale : empreinte digitale d'une chanson

Un effet secondaire malheureux de la FFT est que nous perdons beaucoup d'informations sur le timing. (Bien que théoriquement cela puisse être évité, les frais généraux de performance sont énormes.) Pour une chanson de trois minutes, nous voyons toutes les fréquences et leurs amplitudes, mais nous n'avons aucune idée du moment où elles sont apparues dans la chanson. Mais c'est l'information clé qui fait de la chanson ce qu'elle est ! D'une manière ou d'une autre, nous devons savoir à quel moment chaque fréquence est apparue.

C'est pourquoi nous introduisons une sorte de fenêtre glissante, ou bloc de données, et ne transformons que cette partie de l'information. La taille de chaque morceau peut être déterminée de différentes manières. Par exemple, si nous enregistrons le son, en stéréo, avec des échantillons 16 bits, à 44 100 Hz, une seconde de ce son sera de 44 100 échantillons * 2 octets * 2 canaux ≈ 176 ko. Si nous choisissons 4 Ko pour la taille d'un morceau, nous aurons 44 morceaux de données à analyser à chaque seconde de la chanson. C'est une densité suffisante pour l'analyse détaillée nécessaire à l'identification audio.

Revenons maintenant à la programmation :

 byte audio [] = out.toByteArray() int totalSize = audio.length int sampledChunkSize = totalSize/chunkSize; Complex[][] result = ComplexMatrix[sampledChunkSize][]; for(int j = 0;i < sampledChunkSize; j++) { Complex[chunkSize] complexArray; for(int i = 0; i < chunkSize; i++) { complexArray[i] = Complex(audio[(j*chunkSize)+i], 0); } result[j] = FFT.fft(complexArray); }

Dans la boucle interne, nous mettons les données du domaine temporel (les échantillons) dans un nombre complexe avec une partie imaginaire 0. Dans la boucle externe, nous parcourons tous les morceaux et effectuons une analyse FFT sur chacun.

Une fois que nous avons des informations sur la composition en fréquence du signal, nous pouvons commencer à former notre empreinte numérique de la chanson. C'est la partie la plus importante de l'ensemble du processus de reconnaissance audio Shazam. Le principal défi ici est de savoir comment distinguer, dans l'océan des fréquences captées, quelles fréquences sont les plus importantes. Intuitivement, nous recherchons les fréquences avec la magnitude la plus élevée (communément appelées pics).

Cependant, dans une chanson, la gamme de fréquences fortes peut varier entre le do grave - do1 (32,70 Hz) et le do aigu - do8 (4 186,01 Hz). C'est un intervalle énorme à couvrir. Ainsi, au lieu d'analyser l'ensemble de la gamme de fréquences en une seule fois, nous pouvons choisir plusieurs intervalles plus petits, choisis en fonction des fréquences communes des composants musicaux importants, et analyser chacun séparément. Par exemple, nous pourrions utiliser les intervalles que ce type a choisis pour son implémentation de l'algorithme Shazam. Ce sont 30 Hz - 40 Hz, 40 Hz - 80 Hz et 80 Hz - 120 Hz pour les tonalités basses (couvrant la guitare basse, par exemple), et 120 Hz - 180 Hz et 180 Hz - 300 Hz pour les tonalités moyennes et supérieures. (couvrant les voix et la plupart des autres instruments).

Maintenant, dans chaque intervalle, nous pouvons simplement identifier la fréquence avec la magnitude la plus élevée. Cette information forme une signature pour ce morceau de la chanson, et cette signature devient une partie de l'empreinte digitale de la chanson dans son ensemble.

 public final int[] RANGE = new int[] { 40, 80, 120, 180, 300 }; // find out in which range is frequency public int getIndex(int freq) { int i = 0; while (RANGE[i] < freq) i++; return i; } // result is complex matrix obtained in previous step for (int t = 0; t < result.length; t++) { for (int freq = 40; freq < 300 ; freq++) { // Get the magnitude: double mag = Math.log(results[t][freq].abs() + 1); // Find out which range we are in: int index = getIndex(freq); // Save the highest magnitude and corresponding frequency: if (mag > highscores[t][index]) { points[t][index] = freq; } } // form hash tag long h = hash(points[t][0], points[t][1], points[t][2], points[t][3]); } private static final int FUZ_FACTOR = 2; private long hash(long p1, long p2, long p3, long p4) { return (p4 - (p4 % FUZ_FACTOR)) * 100000000 + (p3 - (p3 % FUZ_FACTOR)) * 100000 + (p2 - (p2 % FUZ_FACTOR)) * 100 + (p1 - (p1 % FUZ_FACTOR)); }

Notez que nous devons supposer que l'enregistrement ne se fait pas dans des conditions parfaites (c'est-à-dire une « salle sourde »), et par conséquent nous devons inclure un facteur fuzz. L'analyse du facteur Fuzz doit être prise au sérieux et, dans un système réel, le programme doit avoir la possibilité de définir ce paramètre en fonction des conditions d'enregistrement.

Pour faciliter la recherche audio, cette signature devient la clé d'une table de hachage. La valeur correspondante est l'heure à laquelle cet ensemble de fréquences est apparu dans la chanson, ainsi que l'ID de la chanson (titre de la chanson et artiste). Voici un exemple de la manière dont ces enregistrements peuvent apparaître dans la base de données.

Si nous exécutons toute une bibliothèque de chansons à travers ce processus d'identification musicale, nous pouvons créer une base de données avec une empreinte digitale complète de chaque chanson de la bibliothèque.

L'algorithme musical : identification de la chanson

Pour identifier une chanson en cours de lecture dans le club, nous enregistrons la chanson avec notre téléphone et exécutons l'enregistrement via le même processus d'empreinte audio que ci-dessus. Ensuite, nous pouvons commencer à rechercher dans la base de données les balises de hachage correspondantes.

En l'occurrence, de nombreuses balises de hachage correspondront à l'identifiant musical de plusieurs chansons. Par exemple, il se peut qu'un morceau de la chanson A sonne exactement comme un morceau de la chanson E. Bien sûr, ce n'est pas surprenant - les musiciens ont toujours "emprunté" des riffs et des riffs les uns aux autres, et de nos jours les producteurs échantillonnent d'autres chansons le temps. Chaque fois que nous faisons correspondre une balise de hachage, le nombre de correspondances possibles diminue, mais il est probable que cette seule information ne réduira pas la correspondance à une seule chanson. Il y a donc une autre chose que nous devons vérifier avec notre algorithme de reconnaissance musicale, et c'est le timing.

L'échantillon que nous avons enregistré dans le club peut provenir de n'importe quel point de la chanson, nous ne pouvons donc pas simplement faire correspondre l'horodatage du hachage correspondant avec l'horodatage de notre échantillon. Cependant, avec plusieurs hachages correspondants, nous pouvons analyser le timing relatif des correspondances, et donc augmenter notre certitude.

Par exemple, si vous regardez dans le tableau ci-dessus, vous verrez que la balise de hachage 30 51 99 121 195 correspond à la fois à la chanson A et à la chanson E. Si, une seconde plus tard, nous correspondons au hachage 34 57 95 111 200 , c'est un de plus correspondent à la chanson A, mais dans ce cas, nous savons que les hachages et les différences de temps correspondent.

 // Class that represents specific moment in a song private class DataPoint { private int time; private int songId; public DataPoint(int songId, int time) { this.songId = songId; this.time = time; } public int getTime() { return time; } public int getSongId() { return songId; } }

Prenons i 1 et i 2 comme moments dans la chanson enregistrée, et j 1 et j 2 comme moments dans la chanson de la base de données. On peut dire que l'on a deux matches avec décalage horaire si :

<span style=font-family : TimesNewRoman ;> RecordedHash(i 1 ) = SongInDBHash(j 1 ) AND RecordedHash(i 2 ) = SongInDBHash(j 2 ) </span>

<span style=font-family : TimesNewRoman ;>ET</span>

<span style=font-family : TimesNewRoman ;> abs(i 1 - i 2 ) = abs (j 1 - j 2 ) </span>

Cela nous donne la possibilité d'enregistrer la chanson depuis le début, le milieu ou la fin.

Enfin, il est peu probable que chaque instant de la chanson que nous enregistrons dans le club corresponde à chaque instant correspondant de la même chanson dans notre bibliothèque, enregistrée en studio. L'enregistrement comprendra beaucoup de bruit qui introduira une erreur dans les matchs. Ainsi, au lieu d'essayer d'éliminer toutes les chansons sauf la bonne de notre liste de correspondances, à la toute fin, nous trions toutes les chansons correspondantes par ordre décroissant de probabilité, et notre préférée est la première chanson du classement.

Du haut jusqu'en bas

Pour répondre à la question "Comment fonctionne Shazam ?" voici un aperçu de l'ensemble du processus de reconnaissance et de correspondance de la musique, de haut en bas :

Pour ce type de système, la base de données peut devenir assez énorme, il est donc important d'utiliser une sorte de base de données évolutive. Il n'y a pas de besoin particulier de relations, et le modèle de données finit par être assez simple, c'est donc un bon cas pour utiliser une sorte de base de données NoSQL.

Comment fonctionne Shazam ? Maintenant tu sais

Ce type de logiciel de reconnaissance de chansons peut être utilisé pour trouver les similitudes entre les chansons. Maintenant que vous comprenez comment fonctionne Shazam, vous pouvez voir comment cela peut avoir des applications au-delà du simple Shazaming de cette chanson nostalgique diffusée sur la radio du taxi. Par exemple, cela peut aider à identifier le plagiat dans la musique, ou à découvrir qui a été l'inspiration initiale de certains pionniers du blues, du jazz, du rock, de la pop ou de tout autre genre. Peut-être qu'une bonne expérience serait de remplir la base de données d'échantillons de chansons avec la musique classique de Bach, Beethoven, Vivaldi, Wagner, Chopin et Mozart et d'essayer de trouver les similitudes entre les chansons. On pourrait penser que même Bob Dylan, Elvis Presley et Robert Johnson étaient des plagiaires !

Mais nous ne pouvons toujours pas les condamner, car la musique n'est qu'une vague que nous entendons, mémorisons et répétons dans nos têtes, où elle évolue et change jusqu'à ce que nous l'enregistrions en studio et la transmettions au prochain grand génie musical.