Récemment, BI.ZONE a participé à la conférence HighLoad ++. Il est clair que nous y sommes arrivés non seulement pour regarder les stands des autres, mais aussi pour apporter quelque chose d'intéressant. Des employés de différents services de l'entreprise ont préparé des tâches pour les invités de la conférence, pour la solution desquels nous avons offert des prix. L'une des tâches de Golang était consacrée à la reconnaissance sonore. Nous avons demandé à son auteur de parler d'elle.
Énoncé du problème
Dans notre tâche, nous devons indexer un certain nombre de pistes et apprendre à rechercher dans la base de données la composition originale par son échantillon. Dans ce cas, l'échantillon peut très bien être bruyant, enregistré sur un mauvais micro, il peut avoir une fréquence différente. La plupart du code a déjà été écrit pour le participant, il n'a qu'à implémenter la fonction d'empreinte digitale, qui supprime l'empreinte digitale de la piste.
Comment enregistrer un son
Il est clair que toute piste est une onde mécanique de nature analogique. Les ondes en physique ont deux caractéristiques: la fréquence et l'amplitude. En ce qui concerne les ondes sonores, pour simplifier, nous pouvons supposer que l'amplitude est le volume et la fréquence est la hauteur, bien qu'en fait les sons aigus semblent plus forts pour une personne de même amplitude.
Autrement dit, du point de vue de la physique, chaque composition est décrite par une fonction continue, ce qui signifie que tout morceau arbitrairement petit de la chanson contiendra une quantité infinie d'informations (bien que s'il s'agit d'une sorte de post-punk, alors il y aura probablement un peu d'informations dans les pistes moins). Pour cette raison, le signal analogique ne peut pas être enregistré, vous devrez gérer sa numérisation. La principale approche de la numérisation des signaux analogiques est la modulation par impulsions codées, qui sera discutée dans cette section. Le PCM se compose de trois étapes: discrétisation, quantification et codage. Analysons brièvement ce qui se passe sur chacun d'eux.
Discrétisation
Nous avons donc une fonction de l'amplitude en fonction du temps. Si quelqu'un a une question, où est la fréquence, elle est cachée derrière les courbes du graphique de fonction. Elle n'est pas encore visible, mais plus tard nous la retirerons. Puisqu'il s'agit d'un signal analogique, la fonction est continue et définie sur l'ensemble des arguments possibles (tout nombre réel de zéro à la fin de la piste). Autrement dit, nous connaissons la valeur de la fonction à tout moment, et nous avons beaucoup de moments. Nous n'avons évidemment pas besoin de tant de choses, alors prenez simplement un sous-ensemble discret. Pour ce faire, nous allons enregistrer la valeur du signal à un petit intervalle fixe. Il doit être suffisamment petit pour que nous n'entendions pas la différence à l'oreille, mais suffisamment grand pour ne pas économiser trop, car cela est également indésirable.
En fait, lors de la numérisation, ce n'est pas l'intervalle qui est défini, mais la fréquence, qui est appelée la "fréquence d'échantillonnage". Selon les tâches, la fréquence d'échantillonnage peut aller de 8 kHz dans les téléphones à plusieurs milliers de kHz dans les équipements audio professionnels. La musique pour une écoute ordinaire en dehors des studios d'enregistrement est généralement stockée à une fréquence de 44,1 kHz ou 48 kHz.
Quantification
Grâce à la discrétisation, nous avons maintenant un tas de points au lieu d'un graphique continu de la fonction, mais nous ne pouvons toujours pas travailler avec, nous devons encore plus gâcher le son. La fonction initiale de l'amplitude en fonction du temps a comparé l'amplitude du continuum au temps du continuum. Au fil du temps, nous l'avons compris, et maintenant nous devons trouver quelque chose avec une amplitude, car ses valeurs actuelles sont dispersées à travers l'ensemble de nombres réels trop chaotiques pour que nous puissions les enregistrer sans problème. Par exemple, parmi eux, bien sûr, il y en a des irrationnels que nous ne pouvons pas enregistrer de quelque manière que ce soit sans arrondir.
La quantification est un processus au cours duquel nous arrondissons les amplitudes aux valeurs d'un ensemble présélectionné. Bien sûr, nous voulons que le nombre d'amplitudes soit une puissance de deux. Pour les pistes audio ordinaires, une quantification 16 bits est utilisée, c'est-à-dire que le nombre d'amplitudes sera de 65 536 (2 à 16 degrés). L'enregistrement sonore professionnel peut être effectué avec une plus grande précision, mais peu de personnes à l'oreille peuvent distinguer la quantification 16 bits de 24 bits. Donc, nous prenons la puissance de deux, prenons un tas d'amplitudes entières et les appelons niveaux de quantification. Ensuite, il sera possible de dire que le signal est quantifié sur 65 536 niveaux (sons faisant autorité, non?). Chaque amplitude est arrondie à l'un des niveaux, ce qui vous permet finalement de stocker sa valeur sur 16 bits, et à l'oreille un tel enregistrement est indiscernable du son continu analogique.
À titre d'illustration, vous pouvez voir l'image ci-dessous, ou générer vos propres images en Python (le code est encore plus bas). Le coin supérieur droit de l'illustration montre cinq niveaux de quantification. Autrement dit, la piste n'aura que cinq niveaux de volume.
Quelques exemplesimport numpy as np import matplotlib.pyplot as plt import math as m def f(x): return m.sin(x) q = 1/2
Codage
Au stade du codage, nous enregistrons les résultats des étapes précédentes sous une forme compréhensible. Toutes les actions avant cela sont généralement effectuées par un équipement spécialisé, mais nous voulons avoir un fichier sur l'ordinateur ou un tableau en mémoire où il y aura des amplitudes. En conséquence, à ce stade, les signaux de l'équipement sont convertis en un tableau de nombres, que nous appellerons PCM (modulation de code d'impulsion) à l'avenir. Ses indices sont du temps conditionnel (indice d'intervalle après échantillonnage), et les amplitudes y sont stockées, arrondies à des entiers au stade de la quantification.
Transformation de Fourier
Initialement, nous avions une onde mécanique et un désir de le numériser, mais maintenant nous avons un signal numérisé et un désir d'en obtenir des fréquences. Le résultat souhaité peut être atteint en utilisant la transformée de Fourier. Au cas où, je reviendrai sur sa valeur appliquée dans ce problème. La transformée de Fourier vous permet de prendre n'importe quelle fonction et de la décomposer en la somme des sinus et cosinus. Nous nous intéressons à cela, car les sinusoïdes et les ondes cosinus sont des vibrations et le son des vibrations. C'est-à-dire qu'en utilisant la transformée de Fourier, vous pouvez obtenir les composants d'une oscillation complexe, découvrir leur amplitude et leur fréquence, simplement en regardant quels coefficients sont devant les arguments sinus et sinus (ou cosinus). Par exemple, il y a une telle vague.
La vagueEn fait, nous savons qu'elle est définie par la fonction 10sin (3x) + sin (x) + 4sin (4x) + 20sin (2x), mais c'est maintenant, et la véritable onde sonore se compose d'une myriade de tels termes, et nous aimerions pouvoir travailler avec elle.
Exécutons donc cette fonction à travers la transformée de Fourier en utilisant le programme
FourierScope et examinons le spectre d'amplitude.
Spectre d'amplitudeVoici à quoi ressemblent les quatre sinus. Il est facile de voir que le graphique correspond aux coefficients des sinus et à leurs arguments.
Il convient de préciser qu'il s'agissait en fait d'une démonstration de la puissance non pas de la transformée de Fourier elle-même, mais de sa version discrète, adaptée aux signaux qui passaient par la modulation impulsionnelle avec toutes ses discrétisations et quantifications. Il serait superflu de présenter un algorithme pour la transformée de Fourier discrète, alors accordons-nous simplement sur le fait qu'il existe une chose appelée DFT, ainsi que sa modification, la transformée de Fourier rapide (FFT). Dans ce cas, la signification appliquée de la FFT est la suivante: l'algorithme reçoit un morceau de PCM à l'entrée et donne un tableau contenant les amplitudes, et les tranches de fréquence sont les indices. Il s'agit de corbeilles de fréquences, pas seulement de fréquences, car la conversion est discrète. En fait, il était naïf de s'attendre à ce que vous puissiez grossir le signal tout au long de l'article, puis obtenir simplement des fréquences sans problèmes et inexactitudes. En fait, le bac de fréquence est tout un tas de fréquences que la FFT ne peut pas distinguer les unes des autres.
Il convient de noter que les FFT sont souvent mal orthographiées lors de la réécriture d'un algorithme à partir de livres et d'articles. Vous trouverez ci-dessous un code plus correct pour travailler avec FFT, ce qui est exactement ce que nous attendions des participants à leur solution.
import "github.com/mjibson/go-dsp/fft" ... blocksCount := len(pcm) / fftWindowSize for i := 0; i < blocksCount; i++ { complexArray := fft.FFTReal(pcm[i*fftWindowSize : i*fftWindowSize+fftWindowSize]) // use complexArray... }
La technologie moderne vous permet d'écrire une transformée de Fourier rapide en quelques lignes seulement. La FFT est utilisée pour les segments de taille fftWindowSize et renvoie un tableau de nombres complexes, que nous utiliserons à l'avenir pour les empreintes digitales.
En général, la transformée de Fourier est l'endroit le plus fin de tout le problème. Tout d'abord, la taille du bac est $ \ frac {fréquence \ échantillonnage} {taille \ fenêtre} $. En conséquence, vous pouvez agrandir la fenêtre et obtenir plus de fréquences, ce qui est bien, mais a bien sûr des conséquences négatives. L'augmentation de la taille de la fenêtre conduit au fait que nous analysons le PCM à de grands intervalles et perdons des sons de courte durée. Dans différentes circonstances, cela peut aggraver le programme à plusieurs reprises si des sons courts faisaient partie de la composition, ou il peut s’améliorer si ce ne sont que des bruits. Ou peut-être n'affecte rien du tout. Dans une situation aussi difficile, le programmeur doit agir de manière décisive: prenez un bon nombre, comme $ 2 ^ 9 $ ou $ 2 ^ {10} $, et essayez de ne pas vous embêter avec les subtilités où cela n'est pas nécessaire. Assez pour résoudre le problème, mais dans une application sérieuse, vous devez toujours utiliser une fenêtre de Hamming et bien plus encore.
Empreinte digitale
La tâche consiste à apprendre à avoir un hachage qui peut être mappé sur une piste et qui est insensible aux changements, ayant les fréquences et les amplitudes de la composition. Ils peuvent être très différents: un peu de bruit, un décalage de toutes les fréquences, jouer une autre chanson en parallèle, etc. Vous devez également considérer que la base de données peut contenir simultanément de nombreuses pistes similaires qui doivent être distinguées les unes des autres. Ou peut-être que toutes les pistes seront différentes, et le problème ne sera pas de déterminer laquelle convient le mieux, mais de comprendre que personne ne convient. En général, il y a une certaine marge de créativité.
Vous pouvez prendre une impression de différentes manières. Disons faire un hachage sous la forme d'une liste de plusieurs indicateurs différents. Parmi eux, il peut y avoir, par exemple, le nombre moyen de passages à signal nul, le BPM, les valeurs de fréquence moyennes. Je l'ai fait dans les versions précédentes de
Musicbrainz , et les problèmes de cette approche sont écrits
ici . Et vous pouvez envisager des concepts plus abstraits, tels que le rythme, en analysant la piste à l'aide de l'algorithme EM (
article ). En général, une totale liberté d'expression. Malheureusement, la plupart des algorithmes proposés n'ont apparemment pas d'implémentation publique, donc les prendre et les comparer ne fonctionnera pas.
La mise en œuvre générale est décrite dans
cet article. Il est particulièrement agréable de pouvoir implémenter cet algorithme sur plusieurs lignes. Par exemple, dans l'article d'origine, il est proposé de diviser les fréquences en 6 intervalles, de trouver l'amplitude maximale dans chacune, de prendre la moyenne des six et de sauvegarder les bins qui sont supérieurs à la moyenne, mais de nombreuses autres implémentations sont possibles.
var freqBins = [...]int16{40, 80, 120, 180, 300} func getKeyPoints(frame []freq_domain) int { highScores := make([]float64, len(freqBins)) recordPoints := make([]uint, len(freqBins)) for bin := freqBins[0]; bin < freqBins[len(freqBins)-1]; bin++ { magnitude := frame[bin] binIdx := 0 for freqBins[binIdx] < bin { binIdx++ } if magnitude > highScores[binIdx] { highScores[binIdx] = magnitude recordPoints[binIdx] = (uint)(bin) } } return hash(recordPoints) }
La fonction ci-dessus implémente l'algorithme d'empreinte digitale. À la fin, un tableau de fréquences (ou plutôt des cases) est passé à la fonction `hash ()`, qui devrait transformer un tableau de plusieurs nombres en un seul nombre. Vous pouvez le faire de n'importe quelle manière appropriée, vous pouvez même essayer d'utiliser md5 (bien que ce soit une mauvaise idée).
À propos des tests
Plusieurs cas de test ont été préparés:- Prétest normal avec une piste. L'original et l'échantillon coïncident complètement.
- Un autre prétest avec deux pistes. Les originaux coïncidaient avec les échantillons.
- Un nombre légèrement plus grand de pistes sont indexées, toutes sont recherchées alternativement.
- Un grand nombre de pistes sont chargées, elles sont recherchées, mais après sous-échantillonnage.
- Les pistes sont indexées après le sous-échantillonnage, les pistes originales sont recherchées.
- Indexé plusieurs pistes similaires, à la recherche d'une piste similaire, mais pas dans la base de données.
- Plusieurs pistes sont indexées, elles sont recherchées, mais avec du bruit.
Quelques liens intéressants
https://metacpan.org/pod/Audio::Ofa::Utilhttps://www.researchgate.net/publication/228347102_A_Review_of_Audio_Fingerprintinghttp://www.freshmeat.net/projects/songprinthttps://link.springer.com/article/10.1007/s11265-005-4152-2https://github.com/acoustid/chromaprinthttps://laplacian.wordpress.com/2009/01/10/how-shazam-works/