Wie funktioniert Shazam? Musikerkennungsalgorithmen, Fingerabdrücke und Verarbeitung

Sie hören ein bekanntes Lied im Club oder Restaurant. Du hast dieses Lied vor langer Zeit tausendmal gehört, und die Sentimentalität des Liedes berührt wirklich dein Herz. Sie möchten es morgen unbedingt hören, aber Sie können sich nicht an seinen Namen erinnern! Glücklicherweise haben Sie in unserer erstaunlichen futuristischen Welt ein Telefon mit installierter Musikerkennungssoftware, und Sie sind gerettet. Sie können sich entspannen, denn die Software hat Ihnen den Namen des Liedes mitgeteilt, und Sie wissen, dass Sie es immer wieder hören können, bis es ein Teil von Ihnen wird … oder Sie es satt haben.

Mobile Technologien, zusammen mit den enormen Fortschritten in der Audiosignalverarbeitung, haben uns Algorithmusentwicklern die Möglichkeit gegeben, Musikerkennungsprogramme zu erstellen. Eine der beliebtesten Musikerkennungs-Apps ist Shazam. Wenn Sie 20 Sekunden eines Songs aufnehmen, egal ob Intro, Strophe oder Refrain, erstellt es einen Fingerabdruck für das aufgenommene Sample, konsultiert die Datenbank und verwendet seinen Musikerkennungsalgorithmus, um Ihnen genau zu sagen, welches Lied Sie gerade hören .

Aber wie funktioniert Shazam? Der Algorithmus von Shazam wurde 2003 von seinem Erfinder Avery Li-Chung Wang der Welt vorgestellt. In diesem Artikel gehen wir auf die Grundlagen des Musikerkennungsalgorithmus von Shazam ein.

Analog zu Digital - Abtasten eines Signals

Was ist eigentlich Schall? Ist es eine Art mystisches Material, das wir nicht berühren können, das uns aber ins Ohr fliegt und uns Dinge hören lässt?

Natürlich ist dies nicht ganz der Fall. Wir wissen, dass Schall in Wirklichkeit eine Schwingung ist, die sich als mechanische Druck- und Verschiebungswelle durch ein Medium wie Luft oder Wasser ausbreitet. Wenn diese Schwingung unsere Ohren erreicht, insbesondere das Trommelfell, bewegt sie kleine Knochen, die die Schwingung weiter zu kleinen Haarzellen tief in unserem Innenohr übertragen. Schließlich erzeugen die kleinen Haarzellen elektrische Impulse, die über den Hörnerv an unser Gehirn weitergeleitet werden.

Aufnahmegeräte ahmen diesen Prozess ziemlich genau nach, indem sie den Druck der Schallwelle nutzen, um sie in ein elektrisches Signal umzuwandeln. Eine eigentliche Schallwelle in Luft ist ein kontinuierliches Drucksignal. In einem Mikrofon übersetzt die erste elektrische Komponente, die auf dieses Signal trifft, es in ein analoges Spannungssignal – wiederum kontinuierlich. Dieses kontinuierliche Signal ist in der digitalen Welt nicht so nützlich, daher muss es, bevor es verarbeitet werden kann, in ein diskretes Signal übersetzt werden, das digital gespeichert werden kann. Dazu wird ein digitaler Wert erfasst, der die Amplitude des Signals darstellt.

Die Umwandlung beinhaltet eine Quantisierung der Eingabe und führt notwendigerweise einen kleinen Fehlerbetrag ein. Anstelle einer einzelnen Umwandlung führt ein Analog-Digital-Wandler daher viele Umwandlungen an sehr kleinen Teilen des Signals durch – ein Prozess, der als Sampling bekannt ist

Das Nyquist-Shannon-Theorem sagt uns, welche Abtastrate notwendig ist, um eine bestimmte Frequenz in einem kontinuierlichen Signal zu erfassen. Um insbesondere alle Frequenzen zu erfassen, die ein Mensch in einem Audiosignal hören kann, müssen wir das Signal mit einer Frequenz abtasten, die doppelt so hoch ist wie der menschliche Hörbereich. Das menschliche Ohr kann Frequenzen etwa zwischen 20 Hz und 20.000 Hz wahrnehmen. Daher wird Audio meist mit einer Abtastrate von 44.100 Hz aufgezeichnet. Dies ist die Abtastrate von Compact Discs und auch die am häufigsten verwendete Rate bei MPEG-1-Audio (VCD, SVCD, MP3). (Diese spezifische Rate wurde ursprünglich von Sony gewählt, weil sie auf modifizierten Videogeräten aufgezeichnet werden konnte, die entweder mit 25 Bildern pro Sekunde (PAL) oder 30 Bildern pro Sekunde (unter Verwendung eines NTSC-Monochrom-Videorecorders) liefen und die für notwendig erachtete Bandbreite von 20.000 Hz abdecken zu professionellen analogen Aufnahmegeräten der damaligen Zeit passen.) Wenn Sie also die Frequenz des aufzunehmenden Samples auswählen, werden Sie wahrscheinlich 44.100 Hz wählen wollen.

Aufnahme - Ton aufnehmen

Das Aufnehmen eines gesampelten Audiosignals ist einfach. Da moderne Soundkarten bereits mit Analog-Digital-Wandlern ausgestattet sind, wählen Sie einfach eine Programmiersprache aus, finden Sie eine geeignete Bibliothek, stellen Sie die Frequenz des Samples, die Anzahl der Kanäle (normalerweise Mono oder Stereo), die Sample-Größe (z. B. 16-Bit-Samples) ein ). Öffnen Sie dann die Leitung von Ihrer Soundkarte wie jeden Eingangsstrom und schreiben Sie in ein Byte-Array. So geht das in 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();

Lesen Sie einfach die Daten aus TargetDataLine . (In diesem Beispiel ist das running Flag eine globale Variable, die von einem anderen Thread gestoppt wird – zum Beispiel, wenn wir eine GUI mit der STOP-Schaltfläche haben.)

 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); }

Zeitbereich und Frequenzbereich

Was wir in diesem Byte-Array haben, ist ein im Zeitbereich aufgezeichnetes Signal. Das Zeitbereichssignal repräsentiert die Amplitudenänderung des Signals über die Zeit.

In den frühen 1800er Jahren machte Jean-Baptiste Joseph Fourier die bemerkenswerte Entdeckung, dass jedes Signal im Zeitbereich der Summe einer (möglicherweise unendlichen) Anzahl einfacher Sinussignale entspricht, da jede Sinuskomponente eine bestimmte Frequenz, Amplitude, und Phase. Die Reihe von Sinuskurven, die zusammen das ursprüngliche Zeitbereichssignal bilden, ist als seine Fourier-Reihe bekannt.

Mit anderen Worten, es ist möglich, jedes Zeitbereichssignal darzustellen, indem einfach der Satz von Frequenzen, Amplituden und Phasen angegeben wird, die jeder Sinuskurve entsprechen, aus der das Signal besteht. Diese Darstellung des Signals ist als Frequenzbereich bekannt. In gewisser Weise fungiert der Frequenzbereich als eine Art Fingerabdruck oder Signatur für das Zeitbereichssignal und liefert eine statische Darstellung eines dynamischen Signals.

Die folgende Animation demonstriert die Fourier-Reihe einer 1-Hz-Rechteckwelle und wie aus sinusförmigen Komponenten eine (annähernde) Rechteckwelle erzeugt werden kann. Das Signal ist oben im Zeitbereich und unten im Frequenzbereich dargestellt.

Die Analyse eines Signals im Frequenzbereich vereinfacht vieles ungemein. Es ist bequemer in der Welt der digitalen Signalverarbeitung, da der Ingenieur das Spektrum (die Darstellung des Signals im Frequenzbereich) untersuchen und feststellen kann, welche Frequenzen vorhanden sind und welche fehlen. Danach kann man filtern, einige Frequenzen erhöhen oder verringern oder einfach den genauen Ton aus den gegebenen Frequenzen erkennen.

Die diskrete Fourier-Transformation

Wir müssen also einen Weg finden, unser Signal vom Zeitbereich in den Frequenzbereich umzuwandeln. Hier rufen wir die diskrete Fourier-Transformation (DFT) zu Hilfe. Die DFT ist eine mathematische Methode zur Durchführung einer Fourier-Analyse an einem diskreten (abgetasteten) Signal. Es wandelt eine endliche Liste von gleichmäßig beabstandeten Abtastwerten einer Funktion in die Liste von Koeffizienten einer endlichen Kombination von komplexen Sinuskurven um, die nach ihren Frequenzen geordnet sind, indem berücksichtigt wird, ob diese Sinuskurven mit der gleichen Rate abgetastet wurden.

Einer der beliebtesten numerischen Algorithmen zur Berechnung von DFT ist die schnelle Fourier-Transformation (FFT). Die mit Abstand am häufigsten verwendete Variante der FFT ist der Cooley-Tukey-Algorithmus. Dies ist ein Teile-und-Herrsche-Algorithmus, der eine DFT rekursiv in viele kleinere DFTs unterteilt. Während die Auswertung einer DFT direkt O( n 2 ) Operationen erfordert, wird bei einer Cooley-Tukey FFT das gleiche Ergebnis in O( n log n ) Operationen berechnet.

Es ist nicht schwer, eine geeignete Bibliothek für FFT zu finden. Hier sind einige davon:

• C – FFTW
• C++ – EigenFFT
• Java – JTransform
• Python – NumPy
• Ruby – Ruby-FFTW3 (Schnittstelle zu FFTW)

Unten sehen Sie ein Beispiel einer in Java geschriebenen FFT-Funktion. (FFT verwendet komplexe Zahlen als Eingabe. Um die Beziehung zwischen komplexen Zahlen und trigonometrischen Funktionen zu verstehen, lesen Sie etwas über Eulers Formel.)

 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; }

Und hier ist ein Beispiel für ein Signal vor und nach der FFT-Analyse:

Musikerkennung: Fingerabdruck eines Songs

Ein unglücklicher Nebeneffekt der FFT ist, dass wir sehr viele Informationen über das Timing verlieren. (Obwohl dies theoretisch vermieden werden kann, sind die Mehrkosten für die Leistung enorm.) Bei einem dreiminütigen Song sehen wir alle Frequenzen und ihre Größenordnungen, aber wir haben keine Ahnung, wann sie in dem Song auftauchten. Aber das ist die Schlüsselinformation, die den Song zu dem macht, was er ist! Irgendwie müssen wir wissen, zu welchem ​​Zeitpunkt jede Frequenz aufgetreten ist.

Aus diesem Grund führen wir eine Art gleitendes Fenster oder einen Datenblock ein und transformieren nur diesen Teil der Informationen. Die Größe jedes Chunks kann auf verschiedene Arten bestimmt werden. Wenn wir beispielsweise den Ton in Stereo mit 16-Bit-Samples bei 44.100 Hz aufnehmen, entspricht eine Sekunde dieses Tons 44.100 Samples * 2 Bytes * 2 Kanälen ≈ 176 kB. Wenn wir 4 kB für die Größe eines Chunks auswählen, müssen wir in jeder Sekunde des Songs 44 Datenblöcke analysieren. Das ist eine ausreichend hohe Dichte für die detaillierte Analyse, die für die Audioidentifikation erforderlich ist.

Nun zurück zur Programmierung:

 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); }

In der inneren Schleife setzen wir die Zeitbereichsdaten (die Samples) in eine komplexe Zahl mit dem Imaginärteil 0. In der äußeren Schleife iterieren wir durch alle Chunks und führen an jedem eine FFT-Analyse durch.

Sobald wir Informationen über die Frequenzbeschaffenheit des Signals haben, können wir damit beginnen, unseren digitalen Fingerabdruck des Songs zu erstellen. Dies ist der wichtigste Teil des gesamten Shazam-Audioerkennungsprozesses. Die größte Herausforderung besteht hier darin, in dem Ozean der erfassten Frequenzen zu unterscheiden, welche Frequenzen die wichtigsten sind. Intuitiv suchen wir nach den Frequenzen mit der höchsten Magnitude (allgemein Peaks genannt).

In einem Lied kann der Bereich starker Frequenzen jedoch zwischen niedrigem C - C1 (32,70 Hz) und hohem C - C8 (4.186,01 Hz) variieren. Dies ist ein riesiges Intervall, das abgedeckt werden muss. Anstatt also den gesamten Frequenzbereich auf einmal zu analysieren, können wir mehrere kleinere Intervalle auswählen, die auf der Grundlage der gemeinsamen Frequenzen wichtiger musikalischer Komponenten ausgewählt werden, und jedes einzeln analysieren. Zum Beispiel könnten wir die Intervalle verwenden, die dieser Typ für seine Implementierung des Shazam-Algorithmus gewählt hat. Dies sind 30 Hz - 40 Hz, 40 Hz - 80 Hz und 80 Hz - 120 Hz für die tiefen Töne (z. B. für Bassgitarren) und 120 Hz - 180 Hz und 180 Hz - 300 Hz für die mittleren und höheren Töne (für Gesang und die meisten anderen Instrumente).

Jetzt können wir innerhalb jedes Intervalls einfach die Frequenz mit der höchsten Magnitude identifizieren. Diese Informationen bilden eine Signatur für diesen Teil des Songs, und diese Signatur wird Teil des Fingerabdrucks des Songs als Ganzes.

 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)); }

Beachten Sie, dass wir davon ausgehen müssen, dass die Aufnahme nicht unter perfekten Bedingungen erfolgt ist (dh in einem „tauben Raum“), und wir daher einen Fuzz-Faktor einbeziehen müssen. Die Fuzz-Faktor-Analyse sollte ernst genommen werden, und in einem realen System sollte das Programm eine Option haben, um diesen Parameter basierend auf den Aufnahmebedingungen einzustellen.

Um eine einfache Audiosuche zu ermöglichen, wird diese Signatur zum Schlüssel in einer Hash-Tabelle. Der entsprechende Wert ist die Zeit, zu der diese Frequenzen im Song erschienen sind, zusammen mit der Song-ID (Songtitel und Interpret). Hier ist ein Beispiel dafür, wie diese Datensätze in der Datenbank erscheinen könnten.

Wenn wir eine ganze Bibliothek von Songs durch diesen Musikidentifizierungsprozess laufen lassen, können wir eine Datenbank mit einem vollständigen Fingerabdruck von jedem Song in der Bibliothek aufbauen.

Der Musikalgorithmus: Songidentifikation

Um einen Song zu identifizieren, der gerade im Club gespielt wird, nehmen wir den Song mit unserem Telefon auf und führen die Aufnahme durch den gleichen Audio-Fingerprinting-Prozess wie oben. Dann können wir damit beginnen, die Datenbank nach passenden Hashtags zu durchsuchen.

Zufällig entsprechen viele der Hash-Tags der Musikkennung mehrerer Songs. Zum Beispiel kann es sein, dass ein Teil des Liedes A genauso klingt wie ein Teil des Liedes E. Das ist natürlich nicht verwunderlich – Musiker haben sich schon immer Licks und Riffs voneinander „ausgeliehen“, und heutzutage sampeln Produzenten alle anderen Lieder die Zeit. Jedes Mal, wenn wir ein Hashtag abgleichen, wird die Anzahl möglicher Übereinstimmungen kleiner, aber es ist wahrscheinlich, dass diese Information allein die Übereinstimmung nicht auf einen einzelnen Song eingrenzen wird. Es gibt also noch eine Sache, die wir mit unserem Musikerkennungsalgorithmus überprüfen müssen, und das ist das Timing.

Das Sample, das wir im Club aufgenommen haben, kann von jedem Punkt des Songs stammen, daher können wir den Zeitstempel des übereinstimmenden Hashs nicht einfach mit dem Zeitstempel unseres Samples abgleichen. Mit mehreren übereinstimmenden Hashes können wir jedoch das relative Timing der Übereinstimmungen analysieren und somit unsere Gewissheit erhöhen.

Wenn Sie zum Beispiel in die obige Tabelle schauen, sehen Sie, dass der Hash-Tag 30 51 99 121 195 sowohl Song A als auch Song E entspricht. Wenn wir eine Sekunde später den Hash 34 57 95 111 200 finden, ist das einer mehr Übereinstimmung mit Song A, aber in diesem Fall wissen wir, dass sowohl die Hashes als auch die Zeitunterschiede übereinstimmen.

 // 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; } }

Nehmen wir i 1 und i 2 als Momente im aufgenommenen Lied und j 1 und j 2 als Momente im Lied aus der Datenbank. Wir können sagen, dass wir zwei Spiele mit Zeitunterschied haben, wenn:

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

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

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

Dies gibt uns die Flexibilität, den Song von Anfang, Mitte oder Ende aufzunehmen.

Schließlich ist es unwahrscheinlich, dass jeder einzelne Moment des Songs, den wir im Club aufnehmen, mit jedem entsprechenden Moment desselben Songs in unserer Bibliothek übereinstimmt, der im Studio aufgenommen wurde. Die Aufnahme wird viel Rauschen enthalten, das zu Fehlern in den Spielen führen wird. Anstatt zu versuchen, alle bis auf den richtigen Song aus unserer Liste der Übereinstimmungen zu streichen, sortieren wir ganz am Ende alle übereinstimmenden Songs in absteigender Reihenfolge ihrer Wahrscheinlichkeit, und unser Favorit ist der erste Song auf der Rangliste.

Von oben nach unten

Um die Frage zu beantworten: „Wie funktioniert Shazam?“ Hier ist eine Übersicht über den gesamten Musikerkennungs- und Abgleichsprozess von oben nach unten:

Für diese Art von System kann die Datenbank ziemlich groß werden, daher ist es wichtig, eine skalierbare Datenbank zu verwenden. Es besteht keine besondere Notwendigkeit für Beziehungen, und das Datenmodell ist am Ende ziemlich einfach, also ist es ein gutes Argument für die Verwendung einer Art NoSQL-Datenbank.

Wie funktioniert Shazam? Jetzt wissen Sie

Diese Art von Liederkennungssoftware kann verwendet werden, um die Ähnlichkeiten zwischen Liedern zu finden. Jetzt, da Sie verstehen, wie Shazam funktioniert, können Sie sehen, wie dies Anwendungen haben kann, die über das einfache Shazamen dieses nostalgischen Songs hinausgehen, der im Taxiradio läuft. Zum Beispiel kann es helfen, Plagiate in der Musik zu identifizieren oder herauszufinden, wer die ursprüngliche Inspiration für einige Pioniere des Blues, Jazz, Rock, Pop oder eines anderen Genres war. Vielleicht wäre es ein gutes Experiment, die Song-Sample-Datenbank mit der klassischen Musik von Bach, Beethoven, Vivaldi, Wagner, Chopin und Mozart zu füllen und zu versuchen, die Ähnlichkeiten zwischen Songs zu finden. Man könnte meinen, sogar Bob Dylan, Elvis Presley und Robert Johnson seien Plagiatoren!

Aber wir können sie trotzdem nicht verurteilen, denn Musik ist nur eine Welle, die wir hören, speichern und in unseren Köpfen wiederholen, wo sie sich entwickelt und verändert, bis wir sie im Studio aufnehmen und an das nächste große Musikgenie weitergeben.