Vor kurzem hat BI.ZONE an der HighLoad ++ Konferenz teilgenommen. Es ist klar, dass wir dort angekommen sind, um nicht nur auf die Stände anderer Leute zu starren, sondern etwas Interessantes mitgebracht haben. Mitarbeiter aus verschiedenen Abteilungen des Unternehmens bereiteten Aufgaben für die Konferenzgäste vor, für deren Lösung wir Preise verliehen. Eine Aufgabe von Golang war die Erkennung von Geräuschen. Wir haben ihre Autorin gebeten, von ihr zu erzählen.
Erklärung des Problems
In unserer Aufgabe müssen wir eine bestimmte Anzahl von Titeln indizieren und lernen, wie die ursprüngliche Komposition anhand ihres Samples in der Datenbank gesucht wird. In diesem Fall ist das Sample möglicherweise verrauscht, auf einem schlechten Mikrofon aufgenommen und hat möglicherweise eine andere Frequenz. Der größte Teil des Codes wurde bereits für den Teilnehmer geschrieben, er muss lediglich die Fingerabdruckfunktion implementieren, mit der der Fingerabdruck vom Track entfernt wird.
Wie man einen Ton aufnimmt
Es ist klar, dass jede Spur eine mechanische Welle ist, die analoger Natur ist. Wellen in der Physik haben zwei Eigenschaften: Frequenz und Amplitude. In Bezug auf Schallwellen können wir der Einfachheit halber annehmen, dass die Amplitude die Lautstärke und die Frequenz die Tonhöhe ist, obwohl hohe Töne für eine Person mit derselben Amplitude lauter erscheinen.
Das heißt, aus der Sicht der Physik wird jede Komposition durch eine kontinuierliche Funktion beschrieben, was bedeutet, dass jedes beliebige kleine Stück des Songs eine unendliche Menge an Informationen enthält (obwohl es sich bei dieser Art von Post-Punk wahrscheinlich um ein wenig Information in den Tracks handelt weniger). Aus diesem Grund kann das analoge Signal nicht gespeichert werden, Sie müssen sich mit seiner Digitalisierung befassen. Der Hauptansatz zur Digitalisierung von Analogsignalen ist die Pulscodemodulation, die in diesem Abschnitt erörtert wird. PCM besteht aus drei Stufen: Diskretisierung, Quantisierung und Codierung. Lassen Sie uns kurz analysieren, was auf jedem von ihnen passiert.
Diskretisierung
Wir haben also eine Funktion der Amplitude gegen die Zeit. Wenn jemand eine Frage hat, wo ist die Frequenz, dann ist sie hinter den Kurven des Funktionsgraphen verborgen. Sie ist noch nicht sichtbar, aber später werden wir sie herausziehen. Da es sich um ein analoges Signal handelt, ist die Funktion kontinuierlich und für alle möglichen Argumente definiert (jede reelle Zahl von Null bis zum Ende der Spur). Das heißt, wir kennen den Wert der Funktion zu jedem Zeitpunkt und wir haben viele Momente. Wir brauchen offensichtlich nicht so viel, nehmen Sie einfach eine diskrete Teilmenge. Dazu speichern wir den Signalwert in einem festen kleinen Intervall. Es sollte klein genug sein, damit wir den Unterschied nicht mit dem Ohr hören, aber groß genug, um nicht zu viel zu sparen, da dies auch unerwünscht ist.
Tatsächlich wird beim Digitalisieren nicht das Intervall eingestellt, sondern die Frequenz, die als "Abtastfrequenz" bezeichnet wird. Abhängig von den Aufgaben kann die Abtastfrequenz bei Telefonen zwischen 8 kHz und bei professionellen Audiogeräten zwischen mehreren tausend kHz liegen. Musik für das normale Hören außerhalb von Aufnahmestudios wird normalerweise mit einer Frequenz von 44,1 kHz oder 48 kHz gespeichert.
Quantisierung
Dank der Diskretisierung haben wir jetzt eine Reihe von Punkten anstelle eines kontinuierlichen Funktionsgraphen, aber wir können immer noch nicht damit arbeiten, wir müssen den Klang noch mehr verderben. Die Anfangsfunktion der Amplitude gegen die Zeit verglich die Kontinuumsamplitude mit der Kontinuumszeit. Im Laufe der Zeit haben wir es herausgefunden, und jetzt müssen wir uns etwas mit der Amplitude einfallen lassen, weil die aktuellen Werte zu chaotisch über die reellen Zahlen verstreut sind, als dass wir sie problemlos speichern könnten. Zum Beispiel gibt es unter ihnen sicherlich irrationale, die wir auf keine Weise ohne Rundung speichern können.
Quantisierung ist ein Prozess, bei dem Amplituden auf Werte aus einer vorgewählten Menge gerundet werden. Natürlich wollen wir, dass die Anzahl der Amplituden eine Zweierpotenz ist. Für normale Audiospuren wird eine 16-Bit-Quantisierung verwendet, dh die Anzahl der Amplituden beträgt 65.536 (2 bis 16 Grad). Professionelle Tonaufnahmen können mit größerer Genauigkeit durchgeführt werden, aber nur wenige Menschen können die 16-Bit-Quantisierung von der 24-Bit-Quantisierung unterscheiden. Also nehmen wir die Potenz von zwei, nehmen ein paar ganzzahlige Amplituden und nennen sie Quantisierungsstufen. Dann kann man sagen, dass das Signal über 65.536 Pegel quantisiert ist (klingt maßgeblich, oder?). Jede Amplitude wird auf einen der Pegel gerundet, sodass Sie ihren Wert letztendlich in 16 Bit speichern können. Nach Gehör ist eine solche Aufzeichnung nicht von analogem Dauerton zu unterscheiden.
Zur Veranschaulichung können Sie das folgende Bild sehen oder Ihre eigenen Bilder in Python erstellen (der Code ist noch niedriger). Oben rechts in der Abbildung sind fünf Quantisierungsstufen dargestellt. Das heißt, die Spur hat nur fünf Lautstärkestufen.
Einige Beispieleimport numpy as np import matplotlib.pyplot as plt import math as m def f(x): return m.sin(x) q = 1/2
Codierung
In der Codierungsphase speichern wir die Ergebnisse der vorherigen Schritte in einer verständlichen Form. Alle Aktionen davor werden normalerweise von speziellen Geräten ausgeführt. Wir möchten jedoch eine Datei auf dem Computer oder ein Array im Speicher haben, in dem Amplituden auftreten. Dementsprechend werden in diesem Stadium die Signale der Geräte in eine Reihe von Zahlen umgewandelt, die wir in Zukunft als PCM (Pulscodemodulation) bezeichnen werden. Seine Indizes sind die bedingte Zeit (Intervallindex nach der Abtastung), und die Amplituden werden darin gespeichert und in der Quantisierungsstufe auf ganze Zahlen gerundet.
Fourier-Transformation
Ursprünglich hatten wir eine mechanische Welle und den Wunsch, sie zu digitalisieren, aber jetzt haben wir ein digitalisiertes Signal und den Wunsch, Frequenzen daraus zu gewinnen. Das Gewünschte kann mit der Fourier-Transformation erreicht werden. Nur für den Fall, werde ich seinen angewandten Wert in diesem Problem nacherzählen. Mit der Fourier-Transformation können Sie jede Funktion in die Summe von Sinus und Cosinus zerlegen. Das interessiert uns, denn bei Sinus- und Kosinuswellen geht es um Schwingungen, und bei Schall geht es um Schwingungen. Das heißt, mit der Fourier-Transformation können Sie die Komponenten einer komplexen Schwingung ermitteln und deren Amplitude und Frequenz ermitteln, indem Sie sich nur ansehen, welche Koeffizienten vor den Sinus- und Sinus- (oder Cosinus-) Argumenten stehen. Zum Beispiel gibt es eine solche Welle.
Die WelleTatsächlich wissen wir, dass es durch die Funktion 10sin (3x) + sin (x) + 4sin (4x) + 20sin (2x) definiert ist, aber das ist es jetzt, und die reale Schallwelle besteht aus einer Vielzahl solcher Ausdrücke, und das möchten wir können arbeite damit. Lassen Sie uns diese Funktion also mit dem
FourierScope- Programm durch die Fourier-Transformation
führen und das Amplitudenspektrum betrachten.
AmplitudenspektrumSo sehen die vier Sinusse aus. Es ist leicht zu erkennen, dass der Graph den Koeffizienten der Sinusse und ihrer Argumente entspricht.
Es sollte klargestellt werden, dass es sich in der Tat um eine Demonstration der Leistung nicht der Fourier-Transformation selbst, sondern ihrer diskreten Version handelte, die für Signale geeignet ist, die eine Pulscodemodulation mit all ihren Diskretisierungen und Quantisierungen durchlaufen. Es wäre überflüssig, einen Algorithmus für die diskrete Fouriertransformation vorzulegen, also stimmen wir nur der Tatsache zu, dass es so etwas wie die DFT und ihre Modifikation, die schnelle Fouriertransformation (FFT), gibt. In diesem Fall lautet die angewandte Bedeutung der FFT wie folgt: Der Algorithmus empfängt ein Stück PCM am Eingang und gibt ein Array mit den Amplituden aus, und die Frequenzbereiche sind die Indizes. Es handelt sich um Frequenzbereiche, nicht nur um Frequenzen, da die Umwandlung diskret ist. In der Tat war es naiv zu erwarten, dass Sie das Signal im gesamten Artikel vergröbern und dann nur Frequenzen ohne Probleme und Ungenauigkeiten erhalten können. Tatsächlich ist der Frequenzbereich eine ganze Reihe von Frequenzen, die die FFT nicht voneinander unterscheiden kann.
Es ist erwähnenswert, dass FFTs häufig falsch geschrieben werden, wenn ein Algorithmus aus Büchern und Artikeln neu geschrieben wird. Im Folgenden finden Sie einen genaueren Code für die Arbeit mit FFT, genau das, was wir von den Teilnehmern an ihrer Lösung erwartet haben.
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... }
Dank moderner Technologie können Sie eine schnelle Fourier-Transformation in nur wenigen Zeilen schreiben. FFT wird für Segmente der Größe fftWindowSize verwendet und gibt ein Array komplexer Zahlen zurück, die wir in Zukunft für den Fingerabdruck verwenden werden.
Im Allgemeinen ist die Fourier-Transformation die dünnste Stelle im gesamten Problem. Erstens ist die Behältergröße $ \ frac {Frequenz \ Abtastrate} {Größe \ Fenster} $. Dementsprechend kann man das Fenster vergrößern und mehr Frequenzen erhalten, was zwar nett ist, aber natürlich negative Konsequenzen hat. Die Zunahme der Fenstergröße führt dazu, dass wir PCM in großen Abständen analysieren und Geräusche von kurzer Dauer verlieren. Unter verschiedenen Umständen kann dies das Programm wiederholt verschlechtern, wenn kurze Sounds Teil der Komposition waren, oder es kann sich verbessern, wenn es nur um Geräusche handelt. Oder vielleicht gar nichts beeinflussen. In solch einer schwierigen Situation muss der Programmierer entschlossen handeln: Nehmen Sie eine gute Zahl, wie z. B. 2 ^ 9 $ oder 2 ^ {10} $, und versuchen Sie, sich nicht um die Feinheiten zu kümmern, bei denen dies nicht erforderlich ist. Genug, um das Problem zu lösen, aber in einer ernsthaften Anwendung müssen Sie immer noch ein Hamming-Fenster und vieles mehr verwenden, um darüber nachzudenken.
Fingerabdruck
Die Aufgabe besteht darin, zu lernen, wie ein Hash erstellt werden kann, der auf eine Spur abgebildet werden kann und der gegenüber Änderungen unempfindlich ist und die Frequenzen und Amplituden der Komposition aufweist. Sie können sehr unterschiedlich sein: ein wenig Rauschen, eine Verschiebung aller Frequenzen, das parallele Abspielen eines anderen Songs und so weiter. Sie müssen auch berücksichtigen, dass die Datenbank gleichzeitig viele ähnliche Spuren enthalten kann, die voneinander unterschieden werden müssen. Oder vielleicht sind alle Tracks unterschiedlich, und das Problem wird nicht darin bestehen, herauszufinden, welcher besser geeignet ist, sondern zu verstehen, dass nicht einer geeignet ist. Generell gibt es einen gewissen Spielraum für Kreativität.
Sie können einen Ausdruck auf verschiedene Arten erstellen. Nehmen wir an, Sie erstellen einen Hash in Form einer Liste mit mehreren verschiedenen Indikatoren. Darunter können zum Beispiel die durchschnittliche Anzahl von Null-Signal-Durchgängen, BPM, durchschnittliche Frequenzwerte sein. Ich habe dies in früheren Versionen von
Musicbrainz getan, und die Probleme dieses Ansatzes sind
hier geschrieben. Sie können auch abstraktere Konzepte wie den Rhythmus in Betracht ziehen und die Spur mit dem EM-Algorithmus analysieren (
Artikel ). Im Allgemeinen völlige Meinungsfreiheit. Leider haben die meisten vorgeschlagenen Algorithmen anscheinend keine öffentliche Implementierung, so dass es nicht funktioniert, sie nur zu nehmen und zu vergleichen.
Die Mainstream-Implementierung wird in
diesem Artikel beschrieben. Besonders schön ist, dass Sie diesen Algorithmus in mehreren Zeilen implementieren können. Zum Beispiel wird im ursprünglichen Artikel vorgeschlagen, die Frequenzen in 6 Intervalle zu unterteilen, die maximale Amplitude in jedem zu finden, den Durchschnitt aller sechs zu bilden und die über dem Durchschnitt liegenden Fächer zu speichern, aber viele andere Implementierungen sind möglich.
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) }
Die obige Funktion implementiert den Fingerabdruck-Algorithmus. Am Ende wird ein Array von Frequenzen (oder besser Bins) an die Funktion "hash ()" übergeben, die ein Array von mehreren Zahlen in eine Zahl umwandeln soll. Sie können dies auf jede geeignete Weise tun, Sie können sogar versuchen, md5 zu verwenden (obwohl dies eine schlechte Idee ist).
Über das Testen
Es wurden mehrere Testfälle vorbereitet:- Normaler Vortest mit einer Spur. Das Original und das Muster stimmten vollständig überein.
- Ein weiterer Vortest mit zwei Spuren. Die Originale stimmten mit den Mustern überein.
- Eine etwas größere Anzahl von Titeln wird indiziert, alle werden abwechselnd durchsucht.
- Es wird eine große Anzahl von Spuren geladen, nach denen gesucht wird, jedoch nach einem Downsampling.
- Die Tracks werden nach dem Downsampling indiziert, die Originale werden durchsucht.
- Indizierte mehrere ähnliche Titel, suchte nach einem ähnlichen, aber nicht in der Datenbank.
- Es werden mehrere Titel indiziert, nach denen gesucht wird, jedoch mit Rauschen.
Einige interessante Links
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/