Wie funktioniert Shazam?

Aus dem Englischen „How does Shazam work“ - mit freundlicher Genehmigung von Christophe Kalenzaga. Übersetzung ins Deutsche: Kai Noack

Vorwort des Autors

Hast du dich schon mal gefragt, wie Shazam funktioniert? Ich hatte mir diese Frage vor ein paar Jahren gestellt und einen Forschungsartikel gelesen, den der Mitbegründer von Shazam, Avery Li-Chun Wang, geschrieben hat. Mein Ziel war es, die Magie hinter Shazam zu verstehen. Die kurze Antwort auf die Frage heißt „Audio-Fingerabdruck“, doch was zum Teufel ist das?

Abbildung 1
Shazam Logo
Abbildung 1: Shazam Logo

Als ich Student war, habe ich nie einen Kurs in Signalverarbeitung besucht. Um Shazam wirklich zu verstehen (und nicht nur eine vage Idee davon zu haben), musste ich bei Null beginnen und mich mit den Grundlagen befassen. Dieser Artikel ist eine Zusammenfassung meiner Recherchen, um Verfahren zur Songerkennung zu verstehen.

Ich werde mit den Grundlagen der Musiktheorie beginnen, die Signalverarbeitung vorstellen und mit den Mechanismen hinter Shazam abschließen. Du brauchst keinerlei Kenntnisse, um diesen Artikel zu verstehen. Da es sich jedoch um Informatik und Mathematik handelt, ist es von Vorteil, ein wenig Fachwissen zu haben (besonders für die letzten Kapitel). Wenn du bereits weißt, was die Wörter "Oktaven", "Frequenzen", "Sampling" und "spektrale Lecks" bedeuten, kannst du die ersten Kapitel überspringen.

Tipp: Es ist ein etwas längerer Artikel, du kannst jedoch jedes Kapitel separat - also zu verschiedenen Zeiten - lesen.

Musik und Physik

Ein Ton ist eine Schwingung, die sich durch Luft (oder Wasser) ausbreitet und von den Ohren entschlüsselt werden kann. Wenn wir zum Beispiel einen Song mit einem Smartphone hören, erzeugen die Kopfhörer Vibrationen, die sich durch die Luft fortpflanzen, bis sie unsere Ohren erreichen. Das Licht ist auch eine Schwingung, aber wir können sie nicht hören, weil unsere Ohren solch eine "Lichtschwingung" nicht entschlüsseln können (aber unsere Augen können dies).

Man kann eine Schwingung durch sinusförmige Wellenformen modellieren. In diesem Kapitel werden wir sehen, wie Musik physikalisch/technisch beschrieben werden kann.

Reine Töne im Gegensatz zu echten Klängen

Ein reiner Ton ist ein Ton mit einer sinusförmigen Wellenform. Eine Sinuswelle ist gekennzeichnet durch:

  • Ihre Häufigkeit: die Anzahl der Zyklen pro Sekunde. Ihre Einheit ist Hertz (Hz), zum Beispiel 100 Hz = 100 Zyklen pro Sekunde.
  • Ihre Amplitude (in Bezug auf die Lautstärke für Töne): die Größe jedes Zyklus.

Diese Eigenschaften werden vom menschlichen Ohr entschlüsselt, um einen Ton wahrzunehmen. Der Mensch kann reine Töne von 20 Hz bis 20.000 Hz (für beste Ohren) hören, jedoch nimmt dieser hörbare Bereich mit zunehmendem Alter ab. Im Vergleich dazu besteht das Licht, das wir sehen, aus Sinuswellen von 4·1014 Hz bis 7,9·1014 Hz.

Du kannst den Hörbereich deiner Ohren mit Youtube-Videos wie dem folgenden überprüfen, das alle reinen Töne von 20 Hz bis 20 kHz wiedergibt. Wahrscheinlich hörst du nichts über 16 kHz.

Die menschliche Wahrnehmung der Lautstärke hängt von der Frequenz des reinen Tons ab. Zum Beispiel ist ein reiner Ton bei der Amplitude 10 der Frequenz 30 Hz leiser als ein reiner Ton bei der Amplitude 10 der Frequenz 1000 Hz. Menschliche Ohren folgen einem psychoakustischen Modell (für Interessierte ein Artikel auf Wikipedia mit weiteren Informationen: Psychoakustik).

Hinweis: Diese spaßige Tatsache wird am Ende des Artikels interessante Konsequenzen haben.

Abbildung 2
Reine Sinuswelle der Frequenz 20 Hz
Abbildung 2: Reine Sinuswelle der Frequenz 20 Hz

Reine Sinuswell bei 20 Hz

In dieser Abbildung sehen wir die Darstellung einer reinen Sinuswelle der Frequenz 20 Hz und der Amplitude 1.

Reine Töne gibt es natürlich nicht, aber jeder Klang in unserer Welt ist die Summe mehrerer reiner Töne bei verschiedenen Amplituden.

Abbildung 3
Komplexe Welle von 20 Hz und Oberwellen
Abbildung 3: Komplexe Welle von 20 Hz und Oberwellen

Zusammensetzung von Sinuswellen

In dieser Abbildung siehst du die Darstellung eines realistischeren Klanges, der aus mehreren Sinuswellen besteht:

  • eine reine Sinuswelle der Frequenz 20Hz und der Amplitude 1
  • eine reine Sinuswelle der Frequenz 40Hz und der Amplitude 2
  • eine reine Sinuswelle der Frequenz 80Hz und der Amplitude 1,5
  • eine reine Sinuswelle der Frequenz 160Hz und Amplitude 1

Ein echter Klang kann aus Tausenden von reinen Tönen bestehen.

Musiknoten

Abbildung 4
Simple Musikpartition
Abbildung 4: Simple Musikpartition

Eine Musikpartition ist eine Reihe von Noten, die zu einem bestimmten Zeitpunkt ausgeführt werden. Diese Noten haben auch eine Dauer und eine Lautstärke.

Die Noten sind in Oktaven unterteilt. In den meisten westlichen Ländern ist eine Oktave ein Satz von 8 Noten (A, B, C, D, E, F, G in den meisten englischsprachigen Ländern und Do, Re, Mi, Fa, Sol, La, Si in den meisten lateinischen Ländern westlichen Ländern) mit folgender Eigenschaft:

  • Die Frequenz einer Note in einer Oktave verdoppelt sich in der nächsten Oktave. Zum Beispiel ist die Frequenz von A4 (A in der vierten Oktave) bei 440 Hz gleich der doppelten Frequenz von A3 (A in der dritten Oktave) bei 220 Hz und 4 mal der Frequenz von A2 (A in der zweiten Oktave) bei 110 Hz.

Viele Instrumente liefern mehr als 8 Noten nach Oktaven, diese Noten heißen Halbton (engl. „semitone/halfstep“).

Abbildung 5
Oktaven
Abbildung 5: Oktaven

Für die 4. Oktave (oder die 3. Oktave in lateinischen Ländern) haben die Noten folgende Häufigkeit:

  • C4 (oder Do3) = 261,63 Hz
  • D4 (oder Re3) = 293,67 Hz
  • E4 (oder Mi3) = 329,63 Hz
  • F4 (oder Fa3) = 349,23 Hz
  • G4 (oder Sol3) = 392 Hz
  • A4 (oder La3) = 440 Hz
  • B4 (oder Si3) = 493,88 Hz

Obwohl es vielleicht seltsam ist, ist die Frequenzempfindlichkeit der Ohren logarithmisch. Das bedeutet, dass menschliche Ohren:

  • zwischen 32,70 Hz und 61,74 Hz (1. Oktave)
  • oder zwischen 261,63 Hz und 466,16 Hz (4. Oktave)
  • oder zwischen 2093 Hz und 3951,07 Hz (7. Oktave)

in der Lage sind, die gleiche Anzahl an Noten zu erkennen.

Zur Information: Die A4/La3 bei 440 Hz ist eine Standardreferenz für die Kalibrierung von akustischen Geräten und Musikinstrumenten.

Timbre (Klangfarbe)

Die gleiche Note klingt nicht genau gleich, wenn sie von einer Gitarre, einem Klavier, einer Geige oder einem menschlichen Sänger gespielt wird. Der Grund ist, dass jedes Instrument seine eigene Timbre (Klangfarbe) für eine bestimmte Note hat.

Für jedes Instrument ist der erzeugte Klang eine Vielzahl von Frequenzen, die wie eine bestimmte Note klingen (der wissenschaftliche Ausdruck für eine Musiknote ist die Tonhöhe bzw. Pitch). Dieser Klang hat eine Grundfrequenz (die niedrigste Frequenz) und mehrere Obertöne (jede Frequenz höher als die Grundfrequenz).

Die meisten Instrumente erzeugen (nahezu) harmonische Klänge. Bei diesen Instrumenten sind die Obertöne ein Vielfaches der Grundfrequenz, die Oberwellen genannt werden. Zum Beispiel ist die Zusammensetzung der reinen Töne A2 (Grundton), A4 und A6 harmonisch, während die Zusammensetzung der reinen Töne A2, B3, F5 unharmonisch ist.

Viele Schlaginstrumente (wie Becken oder Schlagzeug) erzeugen unharmonische Klänge.

Hinweis: Die Tonhöhe (die wahrgenommene Musiknote) ist in dem von einem Instrument wiedergegebenen Klang möglicherweise nicht vorhanden. Wenn beispielsweise ein Instrument einen Klang mit den reinen Tönen A4, A6 und A8 spielt, interpretiert das menschliche Gehirn den resultierenden Klang mit einer A2-Note. Diese Note/Tonhöhe ist ein A2, während die niedrigste Tonfrequenz A4 ist (diese Tatsache wird als fehlende Grundfrequenz bezeichnet).

Spektrogramm

Ein Musikstück wird von mehreren Instrumenten und Sängern gespielt. Alle diese Instrumente erzeugen eine Kombination von Sinuswellen mit mehreren Frequenzen und die Gesamtsumme ist eine noch größere Kombination von Sinuswellen.

Es ist möglich, Musik mit einem Spektrogramm zu sehen. Meistens ist ein Spektrogramm ein 3-dimensionaler Graph, in dem:

  • die horizontale Achse (x-Achse) die Zeit ist,
  • die vertikale Achse (y-Achse) die Frequenz des reinen Tons ist.
  • Die dritte Dimension wird durch eine Farbe beschrieben und repräsentiert die Amplitude einer Frequenz zu einer bestimmten Zeit.

Hier ist zum Beispiel ein Klang eines Klaviers, das eine C4-Note spielt (deren Grundfrequenz 261,63 Hz ist)

Und hier ist das dazugehörige Spektrogramm:

Abbildung 6
Piano Spektrogramm
Abbildung 6: Piano Spektrogramm

Die Farbe repräsentiert die Amplitude in dB (wir werden in einem nächsten Kapitel sehen, was es bedeutet).

Tipp: Wer mit Spektrogrammen herumspielen möchte, der kann den Spectrum Analyzer nutzen oder ein Live-Spektrogramm mit seinem Mikrofon im Chrome Music Lab erzeugen.

Wie wir bereits im vorigen Kapitel erwähnt haben, gibt es, obwohl die gespielte Note ein C4 ist, andere Frequenzen als 261 Hz in dieser Aufnahme: die Obertöne. Interessant ist, dass die anderen Frequenzen ein Vielfaches der ersten sind: Das Klavier ist ein Beispiel für ein harmonisches Instrument.

Eine andere interessante Tatsache ist, dass die Intensität der Frequenzen sich mit der Zeit ändert. Dies ist eine weitere Besonderheit eines jeden Instruments, das es einzigartig macht. Wenn wir denselben Musiker nehmen und sein Klavier mit einem anderen austauschst, wird sich die Entwicklung der Frequenzen nicht gleich verhalten und der resultierende Klang wird sich leicht unterscheiden, da jeder Musiker/jedes Instrument seinen eigenen Stil hat. Technisch gesehen verändern diese Entwicklungen der Frequenzen die Hüllkurve des Tonsignals (welches ein Teil des Timbres ist).

Um eine erste Vorstellung vom Musik-Fingerabdruck-Algorithmus von Shazam zu bekommen, können wir das obige Spektrogramm betrachten und erkennen, dass einige Frequenzen (die niedrigsten) wichtiger sind als andere. Was, wenn man nur die stärksten behalten würde?

Digitalisierung

Sofern man kein Schallplatten-Liebhaber bist, wird man zum Musikhören wahrscheinlich eine digitale Datei verwenden (MP3, Apple Lossless, OGG, Audio-CD, was auch immer). Doch wenn Musiker ihre Musik erzeugen, ist sie analog (also nicht mit Bits dargestellt). Die Musik wird digitalisiert, um von elektronischen Geräten (wie Computern, Smartphones, MP3-Playern, CD-Playern ...) gelesen und abgespielt zu werden. In diesem Kapitel werden wir sehen, wie man von einem analogen zu einem digitalen Klang übergeht. Zu wissen, wie digitale Musik erzeugt wird, wird uns helfen, sie in den nächsten Kapiteln zu analysieren und zu verändern.

Sampling (Abtastung)

Analoge Signale sind kontinuierliche Signale, das heißt, wenn man eine Sekunde eines analogen Signals nimmt, kann man diese Sekunde in x Teile zerlegen (setze für x die größte Zahl ein, die du dir vorstellen kannst!), die einen Bruchteil der Sekunde dauern. In der digitalen Welt kann man es sich nicht leisten, unendlich viele Informationen zu speichern. Man benötigt eine Mindesteinheit, z. B. 1 Millisekunde. Während dieser Zeiteinheit kann sich der Ton nicht ändern, daher muss diese Einheit kurz genug sein, damit der digitale Song wie der analoge klingt und klein genug sein, um den Speicherplatz für die Speicherung der Musik nicht zu überschreiten.

Denken wir zum Beispiel an eine bekannten Song. Nun stellen wir uns vor, dass sich der Klang des Songs nur alle 2 Sekunden ändert - dies würde dann nicht mehr wie ein Song klingen. Technisch gesprochen wurde der Sound durch einen Alias verändert. Um sicher zu stellen, dass der Song vernünftig klingt, kann man eine sehr kleine Einheit wie eine Nano-Sekunde (10^{-9} s) wählen. Diesmal würde der Song großartig klingen, aber wir haben nicht genug Speicherplatz auf unserem Rekorder, um sie abzuspeichern, schade.

Dieses Problem wird Sampling genannt.

Die Standardzeiteinheit für digitale Musik beträgt 44100 Einheiten pro Sekunde bzw. Samples pro Sekunde. Aber woher kommen diese 44,1 kHz? Nun, irgendein Typ dachte, 44100 Einheiten pro Sekunde wären eine schöne Zahl ... Spaß beiseite.

Im ersten Kapitel haben wir gesagt, dass Menschen Klänge von 20 Hz bis 20 kHz hören können. Ein Satz von Nyquist und Shannon besagt, dass man, wenn man ein Signal von 0 Hz bis 20 kHz digitalisieren will, mindestens 40 000 Abtastungen pro Sekunde benötigt. Die Hauptidee ist, dass ein Sinuswellensignal mit einer Frequenz F mindestens 2 Punkte pro Zyklus benötigt, um identifiziert werden zu können. Wenn die Frequenz des Samplings mindestens doppelt so hoch ist wie die Frequenz des Signals, erhält man mindestens 2 Punkte pro Zyklus des Originalsignals.

Lasst uns versuchen, das mit Hilfe eines Bildes zu verstehen. Schauen wir ein Beispiel eines guten Samplings an:

Abbildung 7
Digitalisierung einer Sinuswelle von 20 Hz (Sampling)
Abbildung 7: Digitalisierung einer Sinuswelle von 20 Hz (Sampling)

In dieser Abbildung wird ein Ton bei 20 Hz mit einer Abtastrate (Sampling-Rate) von 40 Hz digitalisiert:

  • die blaue Kurve repräsentiert den Ton bei 20 Hz,
  • die roten Kreuze stellen den gesampelten Ton dar, das heißt, dass jede 1/40 Sekunde die blaue Kurve mit einem roten Kreuz markiert wird,
  • die grüne Linie ist eine Interpolation des gesampelten Tons.

Obwohl sie weder die gleiche Form, noch die gleiche Amplitude hat, bleibt die Frequenz des abgetasteten Signals die gleiche.

Hier ist ein Beispiel für schlechtes Sampling:

Abbildung 8
Unterabtastung einer Sinuswelle (Under Sampling)
Abbildung 8: Unterabtastung einer Sinuswelle (Under Sampling)

In dieser Abbildung wird ein Ton bei 20 Hz mit einer Abtastrate von 30 Hz digitalisiert. Diesmal ist die Frequenz des abgetasteten Signals nicht identisch mit dem ursprünglichen Signal: es sind nur 10 Hz. Wenn man genau hinschaut, kann man sehen, dass ein Zyklus im gesampelten/abgetasteten Signal zwei Zyklen im ursprünglichen Signal darstellt. Diesen Fall nennt man eine Unterabtastung (englisch "under sampling").

Dieser Fall zeigt auch noch etwas anderes: Wenn man ein Signal zwischen 0 Hz und 20 kHz digitalisieren möchte, muss man vor dem Samping/der Abtastung die Frequenzen über 20 kHz vom Signal entfernen. Andernfalls werden diese Frequenzen in Frequenzen zwischen 0 Hz und 20 kHz umgewandelt und fügen unerwünschte Klänge hinzu (dies wird Aliasing genannt).

Zusammenfassend: Wenn man eine gute Musikkonvertierung von analog zu digital erreichen möchte, muss man die analoge Musik mindestens 40.000 Mal pro Sekunde aufnehmen. HIFI-Unternehmen wie Sony wählten in den 1980er Jahren 44,1 kHz, weil es über 40.000 Hz lag und mit den Videostandards NTSC und PAL kompatibel war. Es existieren auch andere Audio-Standards wie 48 kHz (Blueray), 96 kHz und 192 kHz, doch wenn man kein Experte oder Audiophiler ist, hört man wahrscheinlich 44,1 kHz Musik.

Anmerkung 1: Der Satz von Nyquist-Shannon ist umfangreicher als das, was wir gesagt haben. Du kannst hier nachlesen, wenn du mehr darüber wissen möchtest.

Anmerkung 2: Die Frequenz der Abtastrate muss exakt dem Zweifachen der Frequenz des zu digitalisierenden Signals entsprechen, da man im schlimmsten Fall ein konstant digitalisiertes Signal erhalten würde.

Quantisierung

Wir haben gesehen, wie man die Frequenzen von analoger Musik digitalisiert, aber was ist mit der Lautstärke der Musik? Die Lautstärke ist ein relatives Maß: Für die gleiche Lautstärke innerhalb des Signals gilt, wenn man die Lautsprecher lauter macht, dann wird der Klang (** die Lautstärke) höher sein. Die Lautstärke misst die Variation zwischen dem niedrigsten und dem höchsten Pegel des Sounds innerhalb eines Songs.

Auch bei der Lautstärke tritt das Problem auf: Wie kann man von einer kontinuierlichen Welt (mit unendlichen Variationen an Lautstärken) übergehen zu einer diskreten Welt?

Stellen wir uns einen Song mit nur 4 Zuständen für die Lautstärke vor: Kein Ton, leiser Ton, hoher Ton und volle Leistung. Sogar das beste Lied der Welt wird unerträglich. Was wir uns gerade vorgestellt haben, war eine 4-stufige Quantisierung.

Hier ist ein Beispiel für eine geringe Quantisierung eines Audiosignals:

Abbildung 9
Beispiel einer 8-Stufen-Quantisierung
Abbildung 9: Beispiel einer 8-Stufen-Quantisierung

Diese Abbildung zeigt eine 8-Stufen-Quantisierung. Wie man sehen kann, ist der resultierende Klang (in Rot) sehr verändert. Der Unterschied zwischen dem echten Klang und dem quantisierten Klang wird Quantisierungsfehler oder Quantisierungsrauschen genannt. Diese 8-Stufen-Quantisierung wird auch als 3-Bit-Quantisierung bezeichnet, da man nur 3 Bits benötigt, um die 8 verschiedenen Stufen (8 = 2³) zu implementieren.

Hier ist das gleiche Signal mit einer 64-Stufen-Quantisierung (6-Bits-Quantisierung):

Abbildung 10
Beispiel einer 64-Stufen-Quantisierung
Abbildung 10: Beispiel einer 64-Stufen-Quantisierung

Obwohl der resultierende Klang immer noch verändert wird, sieht er eher wie der ursprüngliche Klang aus (und klingt auch so).

Glücklicherweise haben Menschen keine besonders empfindlichen Ohren. Die Standardquantisierung ist auf 16 Bits codiert, was 65536 Stufen bedeutet. Mit einer Quantisierung von 16 Bits ist das Quantisierungsrauschen für menschliche Ohren niedrig genug.

Anmerkung 1: Im Studio beträgt die von Profis verwendete Quantisierung 24 Bit, das heißt es gibt 2^24 = 16 Millionen mögliche Variationen der Lautstärke zwischen dem tiefsten Punkt und dem höchsten Punkt der Audiospur.

Anmerkung2: Wir haben in den Beispielen einige Annäherungen bezüglich der Anzahl der Quantisierungsstufen gemacht.

Pulse-Code-Modulation

PCM oder "Pulse-Code-Modulation" ist ein Standard, der digitale Signale darstellt. PCM wird von Compact Discs und den meisten elektronischen Geräten verwendet. Wenn wir zum Beispiel eine MP3-Datei mit einem Computer, Smartphone oder Tablet hören, wird die MP3-Datei automatisch in ein PCM-Signal umgewandelt und dann an die Kopfhörer gesendet.

Ein PCM-Stream ist ein Strom von organisierten Bits. Es kann aus mehreren Kanälen bestehen. Zum Beispiel hat eine Stereo-Musik 2 Kanäle.

In einem Stream wird die Amplitude des Signals in Samples aufgeteilt. Die Anzahl der Samples pro Sekunde entspricht der Abtastrate (Sampling-Rate) der Musik. Zum Beispiel wird eine 44,1 kHz-gesampelte Musik 44.100 Samples pro Sekunde haben. Jeder Abtastwert gibt die (quantisierte) Amplitude des Klangs des entsprechenden Bruchteils von Sekunden an.

Es gibt mehrere PCM-Formate, aber das am Häufigsten im Audiobereich verwendete ist das (lineare) PCM 44,1 kHz, 16-Bit-Tiefe Stereo-Format. Dieses Format hat 44.100 Samples pro Sekunde an Musik. Jedes Beispiel dauert 4 Bytes:

  • 2 Bytes (16 bits) für die Intensität (von -32.768 bis 32.767) des linken Kanals
  • 2 Bytes (16 bits) für die Intensität (von -32.768 bis 32.767) des rechten Kanals
Abbildung 11
Pulse-Code-Modulation (PCM)
Abbildung 11: Pulse-Code-Modulation (PCM)

In einem PCM mit 44,1 kHz 16-Bit-Tiefe Stereo-Format hat man 44.100 Samples wie das oben abgebildete für jede Sekunde Musik.

Vom digitalen Klang zu den Frequenzen

Wir wissen jetzt, wie man von einem analogen zu einem digitalen Sound kommt. Aber wie bekommt man die Frequenzen in ein digitales Signal hinein? Dieses Kapitel ist sehr wichtig, da der Fingerabdruck-Algorithmus von Shazam nur mit Frequenzen arbeitet.

Für analoge (und daher kontinuierliche) Signale gibt es eine Transformation, die als kontinuierliche Fourier-Transformation bezeichnet wird. Diese Funktion transformiert eine Funktion der Zeit in eine Funktion von Frequenzen. Mit anderen Worten, wenn man die Fourier-Transformation auf einen Klang anwendet, wird sie uns die Frequenzen (und deren Intensitäten) innerhalb dieses Klanges wiedergeben.

Aber es gibt 2 Probleme:

  • Wir beschäftigen uns mit digitalen Klängen und daher mit endlichen (keine kontinuierlichen) Klängen.
  • Um die Frequenzen innerhalb einer Musik besser zu erkennen, müssen wir die Fourier-Transformation auf kleine Teile des Audiosignals in voller Länge anwenden, wie 0,1 Sekunden-Teile, sodass wir wissen, welche die Frequenzen für jedes 0,1 Sekunden-Teil einer Audiospur sind.

Glücklicherweise gibt es eine andere mathematische Funktion, die Diskrete Fourier-Transform (DFT), die mit gewissen Einschränkungen funktioniert.

Anmerkung: Die Fourier-Transformation muss nur auf einen Kanal angewendet werden, das heißt, wenn man einen Stereo-Song hat, muss man ihn in einen Mono-Song umwandeln.

Diskrete Fourier-Transform

Die DFT (Diskrete Fourier-Transform) gilt für diskrete Signale und ergibt ein diskretes Spektrum (die Frequenzen innerhalb des Signals).

Hier ist die magische Formel, um ein digitales Signal in Frequenzen umzuwandeln (wir erklären sie weiter unten):

$$ X(n) = \sum_{k=0}^{N-1}{x[k]e^{-j(2 \pi kn/N)}} $$

Erklären wir die Elemente dieser Formel:

  • N ist die Größe des Fensters: die Anzahl der Samples, aus denen das Signal besteht (wir werden im nächsten Kapitel über Fenster sprechen).
  • X(n) steht für das n-te Band der Frequenzen ("frequency bins")
  • x(k) ist das k-te Sample des Audiosignals

Zum Beispiel muss diese Formel für ein Audiosignal mit einem 4096-Sample-Fenster 4096 mal angewendet werden:

  • 1 Mal für n = 0, um das 0. Band der Frequenzen zu berechnen
  • 1 Mal für n = 1, um das 1. Band der Frequenzen zu berechnen
  • 1 Mal für n = 2, um das 2. Band der Frequenzen zu berechnen

Wie du vielleicht bemerkt hast, sagen wir „Band von Frequenzen“ und nicht „Frequenz“. Der Grund hierfür ist, dass die DFT ein diskretes Spektrum ergibt. Ein Band von Frequenzen ist die kleinste Frequenz-Einheit, die die DFT berechnen kann. Die Größe des Bandes (Spektral-/Spektrumauflösung oder Frequenzauflösung genannt) ist gleich der Abtastrate des Signals geteilt durch die Größe des Fensters (N). In unserem Beispiel beträgt die Frequenzauflösung bei einem 4096-Sample-Fenster und einer Standard-Audio-Abtastrate von 44,1 kHz 10,77 Hz (außer dem 0. Band, das speziell ist):

  • das 0. Band repräsentiert die Frequenzen zwischen 0 Hz bis 5,38 Hz
  • das 1. Band repräsentiert die Frequenzen zwischen 5,38 Hz bis 16,15 Hz
  • das 2. Band repräsentiert die Frequenzen zwischen 16,15 Hz bis 26,92 Hz
  • das 3. Band repräsentiert die Frequenzen zwischen 26,92 Hz bis 37,68 Hz

Das bedeutet, dass die DFT zwei Frequenzen, die näher als 10,77 Hz beieinander sind, nicht trennen kann. Zum Beispiel landen Noten mit 27 Hz, 32 Hz und 37 Hz im selben Band. Wenn die Note bei 37 Hz sehr stark ist, weiß man nur, dass das 3. Band stark ist. Dies ist problematisch für die Trennung (Dissoziation) von Noten in den untersten Oktaven. Zum Beispiel:

  • eine A1 (oder La -1) ist bei 55 Hz wohingegen eine B1 (oder Si -1) bei 58,27 Hz ist sowie eine G1 (oder Sol -1) bei 49 Hz.
  • die erste Note eines Standard-88-Tasten-Klaviers ist eine A0 bei 27,5 Hz, gefolgt von einer A#0 bei 29,14 Hz.

Man kann die Frequenzauflösung verbessern, indem man die Fenstergröße erhöht, aber das bedeutet, dass man die schnellen Frequenz-/Notenänderungen in der Musik verliert:

  • Ein Audiosignal hat eine Abtastrate von 44,1 kHz
  • Das Fenster zu vergrößern bedeutet, mehr Samples zu nehmen und somit die Zeit zu erhöhen, die das Fenster benötigt.
  • Bei 4.096 Samples beträgt die Fensterdauer 0,1 Sekunden und die Frequenzauflösung 10,7 Hz: Man kann eine Änderung alle 0,1 Sekunden feststellen.
  • Bei 16.384 Samples beträgt die Fensterdauer 0,37 Sekunden und die Frequenzauflösung liegt bei 2,7 Hz: Man kann alle 0,37 Sekunden eine Änderung feststellen.

Eine weitere Besonderheit für ein Audiosignal ist, dass wir nur die Hälfte der von der DFT berechneten Bänder benötigen. Im vorherigen Beispiel ist die Band-Definition 10,7 Hz, das bedeutet, dass das 2047. Band die Frequenzen von 21902,9 Hz bis 21913,6 Hz wiedergibt. Aber:

  • Das 2048. Band gibt die gleiche Information wie das 0. Band
  • Das 2049. Band gibt die gleiche Information wie das 1. Band
  • Das X+2048. Band gibt die gleiche Information wie das X. Band
  • ...

Wenn du wissen möchtest, warum die Band-Auflösung der Abtastrate (Sampling Rate) dividiert durch die Fenstergröße entspricht oder warum diese Formel so bizarr ist, kannst du auf dieser sehr guten Webseite einen 5-teiligen Artikel über die Fourier-Transform lesen (speziell Teil 4 und Teil 5), der Artikel ist für Anfänger geeignet.

Fensterfunktion

Wenn man die Frequenz eines 1-Sekunden-Klangs für jeden 0,1-Sekunden-Teil erhalten möchte, so muss man die Fourier-Transformation für den ersten 0,1-Sekunden-Teil anwenden, für den zweiten 0,1-Sekunden-Teil anwenden, für den dritten 0,1-Sekunden-Teil anwenden …

Das Problem

Auf diese Weise wendet man implizit eine (rechteckige) Fensterfunktion an:

  • Für die ersten 0,1 Sekunden wendet man die Fourier-Transformation auf das volle 1-Sekunden-Signal an, multipliziert mit einer Funktion, die 1 zwischen 0,0 und 0,1 Sekunden entspricht, und 0 für den Rest
  • Für die zweiten 0,1 Sekunden wendet man die Fourier-Transformation auf das volle Signal einer Sekunde an, multipliziert mit einer Funktion, die 1 zwischen 0,1 und 0,2 Sekunden entspricht, und 0 für den Rest
  • Für die dritten 0,1 Sekunden wendet man die Fourier-Transformation auf das volle Signal einer Sekunde an, multipliziert mit einer Funktion, die 1 zwischen 0,2 und 0,3 Sekunden entspricht, und 0 für den Rest

Hier ist ein visuelles Beispiel der Fensterfunktion, die auf ein digitales (gesampeltes) Audiosignal angewendet wird, um den ersten 0,01-Sekunden-Teil zu erhalten:

Abbildung 12
Rechteckige Fensterfunktion 1
Abbildung 12: Rechteckige Fensterfunktion 1

In dieser Abbildung muss man, um die Frequenzen für den ersten 0,01-Sekunden-Teil zu erhalten, das abgetastete Audiosignal (blau) mit der Fensterfunktion (grün) multiplizieren.

Abbildung 13
Rechteckige Fensterfunktion 2
Abbildung 13: Rechteckige Fensterfunktion 2

In dieser Abbildung muss man, um die Frequenzen für den zweiten 0,01-Sekunden-Teil zu erhalten, das abgetastete Audiosignal (blau) mit der Fensterfunktion (grün) multiplizieren.

Durch "Fenstern" des Audiosignals multipliziert man das Signal audio(t) mit einer Fensterfunktion fenster(t). Diese Fensterfunktion erzeugt spektrale Lecks. Spektrale Lecks bedeutet das Auftreten neuer Frequenzen, die nicht innerhalb des Audiosignals existieren. Die Stärke der realen Frequenzen wird auf andere Frequenzen übertragen.

Hier ist eine nicht-formale (und sehr leichte) mathematische Erklärung. Angenommen, wir möchten einen Teil des vollständigen Audiosignals berechnen. Wir multiplizieren das Audiosignal mit einer Fensterfunktion, die den Klang nur für den gewünschten Teil durchlässt:

$$ audioabschnitt(t) = vollesaudio(t) · fenster(t) $$

Wenn man versucht, die Frequenzen des Audioteils zu ermitteln, wendet man die Fourier-Transformation auf das Signal an:

$$ Fourier( audioabschnitt(t) ) = Fourier( vollesaudio(t) · fenster(t) ) $$

Nach dem Faltungstheorem (das Zeichen * stellt den Faltungsoperator dar und · den Multiplikationsoperator):

$$ Fourier( vollesaudio(t) · fenster(t) ) = Fourier( vollesauto(t) ) * Fourier( fenster(t) )

$$ → Fourier( audioabschnitt(t) ) = Fourier( vollesaudio(t) ) * Fourier( fenster(t) ) $$

Die Frequenzen von audioabschnitt(t) hängen von der gewählten Fensterfunktion fenster() ab.

Wir gehen nicht weiter ins Detail, da höhere Mathematik erforderlich wäre.

Wenn du mehr wissen möchtest, schau dir diesen Link auf Seite 29 an. Das Kapitel "the truncate effects" ("Die abgeschnittenen Effekte") zeigt den mathematischen Effekt, wenn man ein rechteckiges Fenster auf ein Signal anwendet. Beachte, dass das Zerschneiden eines Audiosignals in kleine Teile, um die Frequenzen jedes Teils zu analysieren, spektrale Lecks erzeugt.

Verschiedene Arten von Fenstern

Man kann spektrale Lecks nicht vermeiden, aber man kann mit der Wahl der richtigen Fensterfunktion beeinflussen, wie sich die Lecks verhalten: Statt einer rechteckigen Fensterfunktion kann man ein dreieckiges Fenster, ein Parzen-Fenster, ein Blackman-Fenster, ein Hamming-Fenster usw. wählen.

Das rechteckige Fenster ist das am einfachsten zu verwendende Fenster (weil man das Audiosignal nur in kleine Teile schneiden muss), aber für die Analyse der wichtigsten Frequenzen in einem Signal ist es möglicherweise nicht die beste Art von Fenster. Schauen wir uns 3 Arten von Fenstern an: Rechteckige, Hamming-Fenster und Blackman-Fenster. Um den Effekt der drei Fenster zu analysieren, verwenden wir das folgende Audiosignal, bestehend aus:

  • Eine Frequenz von 40 Hz mit einer Amplitude von 2
  • Eine Frequenz von 160 Hz mit einer Amplitude von 0,5
  • Eine Frequenz von 320 Hz mit einer Amplitude von 8
  • Eine Frequenz von 640 Hz mit einer Amplitude von 1
  • Eine Frequenz von 1000 Hz mit einer Amplitude von 1
  • Eine Frequenz von 1225 Hz mit einer Amplitude von 0,25
  • Eine Frequenz von 1400 Hz mit einer Amplitude von 0,125
  • Eine Frequenz von 2000 Hz mit einer Amplitude von 0,125
  • Eine Frequenz von 2500 Hz mit einer Amplitude von 1,5

In einer perfekten Welt sollte die Fourier-Transformation dieses Signals das folgende Spektrum ergeben:

Abbildung 14
Perfektes Spektrum eines Audiosignals
Abbildung 14: Perfektes Spektrum eines Audiosignals

Diese Abbildung zeigt ein Spektrum mit nur 9 vertikalen Linien (bei 40 Hz, 160 Hz, 320 Hz, 640 Hz, 1000 Hz, 1225 Hz, 1400 Hz, 2000 Hz und 2500 Hz). Die y-Achse gibt die Amplitude in Dezibel (dB) an. Das heißt, die Skala ist logarithmisch: Mit dieser Skala ist ein Klang von 60 dB 100-mal stärker als ein Klang von 40 dB und 10.000-mal stärker als ein Klang von 20 dB. Um eine Vorstellung davon zu bekommen: Wenn ein Mann in einem leisen Raum spricht, ist der von ihm erzeugte Klang 20 - 30 dB lauter (1 m von ihm entfernt) als der Klang des Raumes.

Um dieses "perfekte" Spektrum zu zeichnen, haben wir die Fourier-Transformation mit einem sehr langen Fenster angewendet: einem 10-Sekunden-Fenster. Die Verwendung eines sehr langen Fensters reduziert das spektrale Leck, aber 10 Sekunden sind zu lang, weil sich der Klang in einem echten Song viel schneller ändert. Um eine Vorstellung davon zu bekommen, wie schnell sich die Musik verändert:

Um diese schnellen Änderungen zu erfassen, muss man den Klang mithilfe von Fensterfunktionen in sehr kleine Teile "zerschneiden". Stellen wir uns vor, wir wollen die Frequenzen eines Klangs alle 1/3 Sekunden analysieren:

Abbildung 15
Typen von Fensterfunktionen (Rechteck, Hamming, Blackman)
Abbildung 15: Typen von Fensterfunktionen (Rechteck, Hamming, Blackman)

In dieser Abbildung können wir das Audiosignal mit einem der 3 Fenstertypen multiplizieren, um den Teil des Signals zwischen 0,333 und 0,666 Sekunden zu erhalten. Die Verwendung eines rechteckigen Fensters entspricht dem Zerschneiden des Signals zwischen 0,333 s und 0,666 s, während man mit Hamming- oder Blackman-Fenstern das Signal mit dem Fenstersignal multiplizieren muss.

Im Folgenden sei nun das Spektrum des vorherigen Audiosignals mit einem 4096-Sample-Fenster gezeigt:

Abbildung 16
Fourier-Transformation eines 44,1 kHz Audiosignals mit einem 4096 Fenster
Abbildung 16: Fourier-Transformation eines 44,1 kHz Audiosignals mit einem 4096 Fenster

Das Signal wird bei 44100 Hz abgetastet, so dass ein 4096-Sample-Fenster einen 93-Millisekunden-Teil (4096/44100) und eine Frequenzauflösung von 10,7 Hz darstellt.

Diese Abbildung zeigt, dass alle Fenster das reale Klangspektrum verändern. Wir sehen deutlich, dass ein Teil der Stärke der realen Frequenzen auf ihre Nachbarn übertragen wird. Das Spektrum des rechteckigen Fensters ist das schlechteste, da das spektrale Lecken viel höher ist als die zwei anderen. Dies gilt insbesondere zwischen 40 und 160 Hz. Das Blackman-Fenster gibt das nächstgelegene Spektrum vom realen Spektrum an.

Hier ist das gleiche Beispiel mit einer Fourier-Transformation eines 1024-Fensters:

Abbildung 17
Fourier-Transformation eines 44,1 kHz Audiosignals mit einem 1024 Fenster
Abbildung 17: Fourier-Transformation eines 44,1 kHz Audiosignals mit einem 1024 Fenster

Das Signal wird bei 44100 Hz abgetastet, so dass ein 1024-Sample-Fenster einen 23-Millisekunden-Teil (1024/44100) und eine Frequenzauflösung von 43 Hz darstellt.

Diesmal gibt das rechteckige Fenster das beste Spektrum. Bei den 3 Fenstern ist die Frequenz von 160 Hz durch die spektralen Lecks der Frequenzen 40 Hz und 320 Hz verdeckt. Das Blackman-Fenster zeigt das schlechteste Ergebnis mit einer Frequenz von 1225 Hz, die nahezu unsichtbar ist.

Vergleicht man beide Abbildungen, so zeigt sich, dass das spektrale Lecken (für alle Fensterfunktionen) zunimmt, wenn die Frequenzauflösung zunimmt. Der von Shazam verwendete Fingerabdruck-Algorithmus sucht nach den lautesten Frequenzen innerhalb einer Audiospur. Wegen des spektralen Lecks können wir nicht einfach die X höchsten Frequenzen nehmen. Im letzten Beispiel sind die 3 lautesten Frequenzen ungefähr 320 Hz, 277 Hz (320 - 43) und 363 Hz (320 + 43), wohingegen nur die 320 Hz-Frequenz existiert.

Welches Fenster ist das beste?

Es gibt keine "besten" oder "schlechtesten" Fenster. Jedes Fenster hat seine Besonderheiten und abhängig von dem Problem verwendet man den entsprechenden Typen.

Ein rechteckiges Fenster hat ausgezeichnete Auflösungseigenschaften für Sinusoide von vergleichbarer Stärke, aber es ist eine schlechte Wahl für Sinusoide mit unterschiedlichen Amplituden (was in einem Song der Fall ist, weil die Noten nicht die gleiche Lautstärke haben).

Fenster wie Blackman sind besser, um zu verhindern, dass spektrale Lecks von starken Frequenzen die schwachen Frequenzen verdecken. Aber diese Fenster können schlecht mit Rauschen umgehen, da ein Rauschen mehr Frequenzen verdecken wird als ein rechteckiges Fenster. Dies ist problematisch für einen Algorithmus wie Shazam, der mit Rauschen umgehen muss (zum Beispiel, wenn man Shazam für einen Song in einer Bar oder draußen im Freien benutzt, wo eine Menge Lärm vorhanden ist).

Ein Hamming-Fenster liegt zwischen diesen beiden Extremen und ist (meiner Meinung nach) eine bessere Wahl für einen Algorithmus wie Shazam.

Hier sind einige nützliche Links, um die Fensterfunktionen und das spektrale Lecken genauer zu betrachten:

Leck-Effekt (Fenster-Effekt/Leakage-Effekt)
Fensterfunktion
On the Use of Windows for Harmonic Analysis with the Discrete Fourier Transform (PDF)

Fast-Fourier-Transformation und Zeitkomplexität

Das Problem

$$ X(n) = \sum_{k=0}^{N-1}{x[k]e^{-j(2 \pi kn/N)}} $$

Wenn wir noch einmal auf die DFT-Formel schauen, können wir sehen, dass zur Berechnung eines Bandes N Additionen und N Multiplikationen erforderlich sind (wobei N die Größe des Fensters ist). Um N-Bänder zu bekommen, sind 2·N² Operationen notwendig, was sehr viel ist.

Angenommen, wir haben einen dreiminütigen Song mit 44,1 kHz und berechnen das Spektrogramm des Songs mit einem 4096-Sample-Fenster. Wir müssen 10,7 (44100/4096) DFT pro Sekunde berechnen, also 1938 DFTs für das vollständige Lied. Jede DFT benötigt \( 3,35·10^7 \) Operationen (2*4096^2). Um das Spektrogramm des Songs zu erhalten, müssen wir \( 6,5·10^10 \) Operationen durchführen.

Nehmen wir an, wir haben eine Musiksammlung von 1000 drei Minuten langen Songs, dann benötigen wir 6,5·10^13 Operationen, um die Spektrogramme Ihrer Songs zu erhalten. Selbst mit einem guten Prozessor würde es Tage bzw. Monate dauern, um das Ergebnis zu erhalten.

Zum Glück gibt es schnellere Implementierungen der DFT namens FFT (Fast Fourier Transform). Einige Implementierungen erfordern nur 1,5·N·log(N) Operationen. Für die gleiche Musiksammlung erfordert die Verwendung der FFT anstelle der DFT 340 mal weniger Additionen (1,43·10^11) und es würde nur Minuten bzw. Stunden dauern, um das Ergebnis zu erhalten.

Dieses Beispiel zeigt einen weiteren Kompromiss: Obwohl die Vergrößerung des Fensters die Frequenzauflösung verbessert, erhöht es auch die Rechenzeit. Wenn wir für die gleiche Musiksammlung das Spektrogramm mit einem 512-Sample-Fenster (Frequenzauflösung von 86 Hz) berechnen, erhalten wir das Ergebnis mit der FFT in 1,07·10^11 Operationen, etwa 1/4 mal schneller als mit einem 4096-Sample-Fenster (Frequenzauflösung von 10,77 Hz).

Diese Zeitkomplexität ist wichtig, denn wenn wir Shazam für einen Song verwenden, muss unser Smartphone das Spektrogramm des aufgezeichneten Audios berechnen und ein mobiler Prozessor ist (derzeit noch) weniger leistungsfähig als ein Desktop-Prozessor.

Downsampling

Zum Glück gibt es einen Trick, um die Frequenzauflösung beizubehalten und gleichzeitig die Fenstergröße zu reduzieren, er wird "Downsampling" genannt. Nehmen wir einen Standard-Song bei 44100 Hz, wenn wir ihn bei 11025 Hz (44100/4) umrechnen (resampeln), erhalten wir die gleiche Frequenzauflösung, egal ob wir eine FFT auf dem 44.1 kHz-Song mit einem 4096-Fenster oder eine FFT auf dem 11 kHz-Song, der umgerechnet wurde, mit einem 1024-Fenster machen. Der einzige Unterschied besteht darin, dass der neu abgetastete Song nur Frequenzen von 0 bis 5 kHz hat. Aber der wichtigste Teil eines Songs ist zwischen 0 und 5 kHz. Tatsächlich hören die meisten von uns keinen großen Unterschied zwischen einer Musik mit 11 kHz und einer Musik mit 44,1 kHz. Die wichtigsten Frequenzen befinden sich also immer noch im umgerechneten Song, was für einen Algorithmus wie Shazam wichtig ist.

Abbildung 19
Downsampling
Abbildung 19: Downsampling

Das Downsampling eines 44,1 kHz Songs auf einen 11,025 kHz Song ist nicht sehr schwierig: Ein einfacher Weg dies zu tun ist, die Samples jeweils als 4er-Gruppe zu nehmen und diese Gruppe zu nur einem Sample zu transformieren, indem man den Durchschnitt der 4 Samples bildet. Der einzige knifflige Teil ist, dass man vor dem Downsampling eines Signals die höheren Frequenzen im Sound filtern muss, um Aliasing zu vermeiden (siehe Nyquist-Shannon-Theorem). Dies kann durch Verwendung eines digitalen Tiefpassfilters („low pass filter") erfolgen.

FFT

Gehen wir zurück zur FFT. Die einfachste Implementierung der FFT ist der Radix-2-Cooley-Tukey-Algorithmus, der ein Teile-und-herrsche-Algorithmus ist. Die Idee ist, dass anstatt die Fourier-Transformation direkt auf dem N-Sample-Fenster zu berechnen, der Algorithmus wie folgt verfährt:

  • Teile das N-Sample-Fenster in 2 N/2-Sample-Fenster.
  • Berechne (rekursiv) die FFT für die 2 N/2-Sample-Fenster.
  • Berechne effizient die FFT für die N-Sample-Fenster der 2 vorherigen FFT.

Der letzte Teil kostet nur N Operationen mit einem mathematischen Trick an den Wurzeln der Einheit (die exponentiellen Terme).

Hier ist eine lesbare Version der FFT (in der Programmiersprache Python):

from cmath import *
def fft(x):
        N=len(x)
        if N==1: return x

        even=fft([x[k] for k in range(0,N,2)])
        odd= fft([x[k] for k in range(1,N,2)])

        M=N/2
        l=[ even[k] + exp(-2j*pi*k/N)*odd[k] for k in range(M) ]
        r=[ even[k] - exp(-2j*pi*k/N)*odd[k] for k in range(M) ]

        return l+r

Weitere Informationen zur FFT findet man in diesem Wikipedia-Artikel: Cooley–Tukey FFT algorithm

Shazam

Wir haben in den vorherigen Kapiteln viel Neues kennengelernt. Jetzt werden wir alles zusammenfügen und erklären, wie Shazam schnell Songs identifizieren kann (ja, endlich ist es soweit). Wir geben zunächst einen Überblick über Shazam, dann konzentrieren wir uns auf die Generierung der Audio-Fingerabdrücke und betrachten zuletzt den äußerst effizienten Audio-Suchmechanismus.

Ab jetzt wird angenommen, dass du die Kapitel zu den Noten, zur FFT und zu den Fensterfunktionen gelesen hast. Wir werden manchmal die Wörter „Frequenz“, „Band“, „Note“ oder den vollständigen Ausdruck „Band an Frequenzen“ verwenden, aber dahinter steckt das gleiche Konzept, da es sich um digitale Audiosignale handelt.

Überblick

Ein Audio-Fingerabdruck ist eine digitale Zusammenfassung, die zum Identifizieren eines Audio-Samples oder zum schnellen Auffinden ähnlicher Objekte in einer Audiodatenbank verwendet werden kann. Wenn man beispielsweise jemandem ein Lied vorsummt, erstellt man einen Fingerabdruck, weil man für das Summen die Elemente aus der Musik herausholt/extrahiert, die man für wichtig hält (und wenn man ein guter Sänger ist, wird die andere Person das Lied wiedererkennen).

Bevor wir tiefer einsteigen, soll die folgende Abbildung die vereinfachte Architektur von Shazam zeigen. Dies ist jedoch nur eine Annahme, denn Shazam legt nicht alle notwendigen Informationen für das Verfahren offen. Siehe hierzu das Paper „An Industrial-Strength Audio Search Algorithm“ des Shazam-Mitbegründers Avery Li-Chun Wang aus dem Jahr 2003.

Abbildung 20
Shazam Verfahren im Überblick
Abbildung 20: Shazam Verfahren im Überblick

Auf der Serverseite:

  • Shazam hat vorberechnete Fingerabdrücke basierend auf einer sehr großen Datenbank an Songs.
  • Alle diese Fingerabdrücke werden in eine Αudio-Fingerabdruck-Datenbank eingefügt, die immer dann aktualisiert wird, wenn ein neuer Song in die Song-Datenbank aufgenommen wird.

Auf der Clientseite:

  • Wenn ein Benutzer die Shazam App verwendet, zeichnet die App zuerst die aktuelle Musik mit dem Telefonmikrofon auf.
  • Das Telefon wendet den gleichen Fingerabdruckalgorithmus wie Shazam auf die Aufnahme an.
  • Das Telefon sendet den Fingerabdruck an Shazam.
  • Shazam überprüft, ob dieser Fingerabdruck mit einem Fingerabdruck der Shazam-Datenbank übereinstimmt.
  • Wenn kein Match gefunden wurde, dann wird der Benutzer darüber informiert, dass der Song nicht gefunden wurde.
  • Wenn ein Match gefunden wurde, sucht Shazam nach den Metadaten, die den Fingerabdrücken zugeordnet sind (Name des Musiktitels, ITunes-URL, Amazon-URL ...) und sendet sie an den Benutzer.

Die Schlüsselpunkte von Shazam sind:

  • Rausch- und fehlertolerant zu sein:
    • bezüglich schlechter Qualität, da die in einer Bar oder im Freien aufgenommene Musik meist eine schlechte Qualität hat,
    • bezüglich der Artefakte, die sich durch die Fensterfunktionen ergeben,
    • bezüglich des billigen Mikrofons des Telefons, das Rauschen/Verzerrungen erzeugt,
    • bezüglich vieler anderer physischer Dinge.
  • Fingerabdrücke müssen zeitinvariant (unveränderlich in der Zeit) sein. Das heißt, der Fingerabdruck eines vollständigen Songs muss mit einer 10-Sekunden-Aufzeichnung des Songs übereinstimmen können.
  • Der Abgleich des Fingerabdrucks muss schnell sein: Niemand möchte Minuten oder Stunden warten, um eine Antwort von Shazam zu bekommen.
  • Nur wenige „False Positives“ hervorzubringen: Niemand möchte einen falschen Song als Ergebnis erhalten.

Spektrogrammfilterung

Audio-Fingerabdrücke unterscheiden sich von standardmäßigen Computer-Fingerabdrücken wie SSHA oder MD5, da zwei verschiedene Dateien (in Bezug auf Bits), die die gleiche Musik enthalten, den gleichen Audio-Fingerabdruck haben müssen. Zum Beispiel muss ein Song in einem 256 kbit ACC-Format (iTunes) den gleichen Fingerabdruck ergeben wie in einem 256 kbit MP3 Format (Amazon) oder in einem 128 kbit WMA Format (Microsoft). Um dieses Problem zu lösen, verwenden Audio-Fingerabdruck-Algorithmen das Spektrogramm von Audiosignalen, um Fingerabdrücke zu extrahieren.

Spektrogramm erzeugen

Wir hatten bereits gesagt, dass eine FFT angewendet werden muss, um ein Spektrogramm von einem digitalen Sound zu erzeugen. Für einen Fingerabdruck-Algorithmus benötigen wir eine gute Frequenzauflösung (z. B. 10,7 Hz), um 1. Spektrumlecks* zu reduzieren und 2. die wichtigsten Noten innerhalb des Songs herauszufiltern. Gleichzeitig müssen wir die Rechenzeit so weit wie möglich reduzieren und daher die kleinstmögliche Fenstergröße verwenden. Im Paper von Shazam wird nicht erklärt, auf welche Weise man das Spektrogramm erhält, aber hier sei eine Möglichkeit gezeigt:

Auf der Serverseite (Shazam) muss der 44,1 kHz-gesampelte Sound (von CD, MP3 oder einem anderen Soundformat) von Stereo zu Mono übergehen. Wir können das tun, indem wir den Durchschnitt des linken und des rechten Lautsprechers nehmen. Vor dem Downsampling müssen wir die Frequenzen oberhalb von 5 kHz herausfiltern, um Aliasing zu vermeiden. Dann kann der Ton bei 11,025 kHz heruntergemischt (Downsampling) werden.

Auf der Clientseite (Smartphone) muss die Abtastrate des Mikrofons (Sampling rate), das den Ton aufzeichnet, bei 11,025 kHz liegen.

Dann müssen wir in beiden Fällen eine Fensterfunktion auf das Signal anwenden (wie ein Hamming 1024-Sample-Fenster, Grund hierfür siehe Kapitel Fensterfunktion) sowie die FFT für jede 1024 Samples. Auf diese Weise analysiert jede FFT 0,1 Sekunden Musik. Dies gibt uns ein Spektrogramm mit folgenden Eigenschaften:

  • von 0 Hz zu 5000 Hz,
  • mit einer Bandgröße von 10,7 Hz,
  • 512 möglichen Frequenzen,
  • einer Zeiteinheit von 0,1 Sekunden.

Filtern

An dieser Stelle haben wir das Spektrogramm des Songs. Da Shazam geräuschtolerant sein muss, werden nur die lautesten Töne beibehalten. Doch es ist noch nicht genug, nur die X stärksten Frequenzen alle 0,1 Sekunden beizubehalten. Hier sind einige Gründe:

  • Zu Beginn des Artikels hatten wir über psychoakustische Modelle gesprochen. Menschliche Ohren hören einen tiefen Ton (< 500 Hz) schlechter als einen mittleren Ton (500 Hz - 2000 Hz) oder einen hohen Ton (> 2000 Hz). Als Folge dessen werden tiefe Klänge vieler "roher" Songs künstlich erhöht, bevor sie veröffentlicht werden. Wenn man nur die stärksten Frequenzen verwenden würde, so würde man nur die tiefen Frequenzen erhalten, und wenn 2 Songs die gleiche Drum-Partition haben, kann es passieren, dass beide nach der Filterung ein sehr ähnliches Spektrogramm aufweisen, obwohl Flöten im ersten Song und Gitarren im zweiten Song spielen.
  • Wir hatten bei den Fensterfunktionen gesehen, dass, wenn man eine sehr starke Frequenz hat, andere starke Frequenzen in der Nähe des Spektrums auftreten können, obwohl sie gar nicht existieren (Spektrumleck). Man muss also einen Weg finden, nur die echten Frequenzen beizubehalten.

Hier ist eine einfache Möglichkeit, nur starke Frequenzen beizubehalten und gleichzeitig die vorgenannten Probleme zu verringern:

Schritt 1 – Für jedes FFT-Ergebnis setzt man die 512 Bänder in 6 logarithmische Bänder:

  • der sehr tiefe Klangbereich (von Band 0 bis 10)
  • der tiefe Klangbereich (von Band 10 bis 20)
  • der tiefe-mittlere Klangbereich (von Band 20 bis 40)
  • der mittlere Klangbereich (von Band 40 bis 80)
  • der mittlere-hohe Klangbereich (von Band 80 bis 160)
  • der hohe Klangbereich (von Band 160 bis 511)

Schritt 2 – Für jedes Band behält man nur das stärkste Band der Frequenzen.

Schritt 3 – Dann berechnet man den Durchschnittswert dieser 6 stärksten Bänder.

Schritt 4 – Man behält die Bänder (von den 6 Bändern), die sich über diesem Durchschnitt befinden (multipliziert mit einem Koeffizienten).

Der letzte Schritt ist äußerst wichtig, da folgende Fälle auftreten können:

  • Acapella-Musik mit Sopransängern, die nur mittlere und mittlere-hohe Frequenzen enthält.
  • Jazz-/Rap-Musik mit nur tiefen und tiefen-mittleren Frequenzen.
  • ...

Außerdem wollen wir keine schwache Frequenz in einem Band behalten, nur weil sie die stärkste innerhalb ihres Bandes ist.

Dieser Algorithmus hat jedoch eine Einschränkung. In den meisten Songs sind einige Teile sehr schwach, so zum Beispiel der Anfang oder das Ende eines Songs. Wenn man diese Teile analysiert, erhält man falsche starke Frequenzen, weil der Mittelwert (berechnet in Schritt 3) dieser Teile sehr niedrig ist. Um das zu vermeiden, kann man, anstatt den Mittelwert der 6 stärksten Bänder der aktuellen FFT zu nehmen (das entspricht nur 0,1 Sekunden des Songs), den Mittelwert der stärksten Bänder des gesamten Songs nehmen.

Fazit: Indem wir diesen Algorithmus benutzen, filtern wir das Spektrogramm des Songs und behalten die Frequenzspitzen (Peaks) im Spektrum bei, die die lautesten Noten repräsentieren. Um eine Vorstellung davon zu haben, was diese Filterung macht, sei nachstehend ein echtes Spektrogramm eines 14-Sekunden-Songs gezeigt.

Abbildung 22
Spektrogramm eines 14-Sekunden-Songs
Abbildung 22: Spektrogramm eines 14-Sekunden-Songs

Diese Abbildung stammt aus dem Shazam-Paper. In diesem Spektrogramm kann man sehen, dass einige Frequenzen stärker sind als andere. Wenn man den vorgenannten Algorithmus auf das Spektrogramm anwendet, erhält man Folgendes:

Abbildung 23
Gefiltertes Spektrogramm (Shazam)
Abbildung 23: Gefiltertes Spektrogramm (Shazam)

Diese Abbildung (siehe auch Shazam-Paper) zeigt ein gefiltertes Spektrogramm. Nur die stärksten Frequenzen aus der vorherigen Abbildung werden beibehalten. Einige Teile des Songs haben nach der Filterung keine Frequenz mehr (zum Beispiel zwischen 4 und 4,5 Sekunden).

Die Anzahl der Frequenzen im gefilterten Spektrogramm hängt von dem Koeffizienten ab, der bei Schritt 4 mit dem Mittelwert verwendet wurde. Sie hängen auch von der Anzahl der Bänder ab, die man verwendet (wir haben 6 Bänder verwendet, aber wir hätten auch eine andere Zahl wählen können).

An dieser Stelle ist die Intensität der Frequenzen nutzlos. Daher kann dieses Spektrogramm als zweispaltige Tabelle modelliert werden, bei der:

  • die erste Spalte die Frequenz in dem Spektrogramm darstellt (y-Achse)
  • die zweite Spalte die Zeit darstellt, zu der die Frequenz während des Songs auftritt (x-Achse)

Dieses gefilterte Spektrogramm ist nicht der endgültige Audio-Fingerabdruck, aber es ist bereits ein großer Teil davon. Im nächsten Kapitel erfahren wir mehr darüber.

Hinweis: Wir haben gerade einen einfachen Algorithmus kennengelernt, um das Spektrogramm zu filtern. Ein besserer Ansatz könnte darin bestehen, ein logarithmisches Gleitfenster zu verwenden und nur die stärksten Frequenzen über dem Mittelwert + der Standardabweichung (multipliziert mit einem Koeffizienten) eines sich bewegenden Teils des Songs zu behalten. Dieser Ansatz ist jedoch schwieriger zu erklären.

Fingerabdrücke speichern

Wir haben im vorigen Kapitel ein gefiltertes Spektrogramm für einen Songs erstellt. Wie können wir dieses Spektrogramm nun effizient speichern und nutzen? Darin liegt die eigentliche Stärke von Shazam. Um das Problem zu verstehen, gehen wir von einer vereinfachten Situation aus: Wir suchen nach einem Song, indem wir direkt sein gefiltertes Spektrogramm verwenden.

Einfacher Suchansatz

Vorbereitender Schritt: Wir erstellen eine Datenbank mit gefilterten Spektrogrammen für alle Songs auf unserem Computer.

Schritt 1: Wir nehmen einen 10-Sekunden-Teil eines Songs auf, der gerade auf dem Fernseher gespielt wird, und übertragen ihn auf den Computer.

Schritt 2: Wir berechnen das gefilterte Spektrogramm dieser Aufnahme.

Schritt 3: Wir vergleichen dieses "kleine" Spektrogramm mit dem "vollen" Spektrogramm jedes einzelnen Songs.

Doch wie können wir ein 10-Sekunden-Spektrogramm mit dem Spektrogramm eines 180-Sekunden-Songs vergleichen? Hier ist eine visuelle Erklärung dessen, was zu tun ist:

Abbildung 24
Vereinfachtes Spektrogramm: Song und Aufnahme
Abbildung 24: Vereinfachtes Spektrogramm: Song und Aufnahme

Visuell müssen wir das kleine Spektrogramm nehmen und mit dem Spektrogramm des vollständigen Songs Stück für Stück überlagern, um herauszufinden, ob das kleine Spektrogramm mit einem Teil des vollständigen Spektrogramms übereinstimmt.

Abbildung 25
Vereinfachtes Spektrogramm: Abgleich Song und Aufnahme
Abbildung 25: Vereinfachtes Spektrogramm: Abgleich Song und Aufnahme

Wir müssen dies für jeden Song tun, der sich in unserer Datenbank befindet, bis wir eine perfekte Übereinstimmung gefunden haben.

Abbildung 26
Vereinfachtes Spektrogramm: Übereinstimmung Song und Aufnahme
Abbildung 26: Vereinfachtes Spektrogramm: Übereinstimmung Song und Aufnahme

In der letzten Abbildung erkennen wir eine perfekte Übereinstimmung zwischen der Aufnahme und dem Ende des Songs. Sollten wir keinen Match haben, so müssten wir die Aufnahme mit einem anderen Song vergleichen, bis wir eine Übereinstimmung finden. Wenn wir keine perfekte Übereinstimmung finden, können wir zumindest die beste Übereinstimmung wählen, die sich beim Vergleich mit allen Songs ergibt, hierzu würden wir einen Schwellenwert benutzen. Als Beispiel: Wenn die beste Übereinstimmung zwischen Aufnahme und Originalsong eine 90%-ige Ähnlichkeit aufweist, können wir annehmen, dass es der richtige Song ist, weil die 10 % Abweichung wahrscheinlich auf externes Rauschen zurückzuführen sind.

Obwohl dieser einfache Ansatz gut funktioniert, erfordert er sehr viel Rechenzeit. Man muss sämtliche Möglichkeiten der Übereinstimmung zwischen der 10-Sekunden-Aufnahme und jedem einzelnen Song in der Sammlung berechnen. Angenommen, die Musik enthält durchschnittlich 3 Spitzenfrequenzen (Peaks) je 0,1 Sekunden, dann hätte das gefilterte Spektrogramm der 10-Sekunden-Aufnahme 300 Zeit-Frequenz-Punkte. Um den richtigen Song zu finden, würden wir im schlimmsten Fall 300·300·30·S = 2 700 000 · S Operationen benötigen, wobei S die Anzahl der Sekunden der Musik in unserer Sammlung meint. Wenn wir 30 000 Songs haben (ca. 7·106 Sekunden Musik), kann dieser Suchprozess sehr lange dauern. Und für Shazam wäre dies noch wesentlich aufwändiger, da dort ca. 40 Millionen Songs gespeichert sind (diese Zahl ist nur eine Vermutung, die konkrete Datenbankgröße ist nicht öffentlich).

Fragt sich nun, wie macht Shazam das so schnell und effizient?

Zielzonen

Anstatt jeden Punkt einzeln zu vergleichen, sucht man nach mehreren Punkten gleichzeitig. Im Shazam-Paper wird diese Gruppe von Punkten als Zielzone bezeichnet. Das Paper von Shazam erklärt jedoch nicht, wie man diese Zielzonen erzeugt. Trotzdem sei im Folgenden eine Möglichkeit hierfür beschrieben. Damit es leichter zu verstehen ist, werden wir die Größe der Zielzone an 5 Frequenz-Zeitpunkten festlegen.

Um sicherzustellen, dass sowohl die Aufnahme als auch der vollständige Song die gleichen Zielzonen erzeugen, benötigt man eine Ordnungsrelation zwischen den Zeit-Frequenz-Punkten in einem gefilterten Spektrogramm. Hier ist eine solche Ordnungsrelation:

  • Wenn zwei Zeit-Frequenz-Punkte die gleiche Zeit haben, steht der Zeit-Frequenz-Punkt mit der niedrigsten Frequenz vor dem anderen.
  • Wenn ein Zeit-Frequenz-Punkt eine niedrigere Zeit als ein anderer Punkt hat, dann steht er davor.

Wenn man diese Reihenfolge auf das vereinfachte Spektrogramm anwendet, das wir oben gezeigt hatten, dann erhält man Folgendes:

Abbildung 27
Spektrogramm mit Ordnungsrelation
Abbildung 27: Spektrogramm mit Ordnungsrelation

In dieser Abbildung haben wir alle Zeit-Frequenz-Punkte auf Grundlage der Ordnungsrelation markiert. Zum Beispiel:

  • Der Punkt 0 steht vor jedem anderen Punkt in dem Spektrogramm.
  • Der Punkt 2 steht nach den Punkten 0 und 1, aber vor allen anderen.

Da die Spektrogramme nun innerlich geordnet werden können, können wir dieselben Zielzonen auf verschiedenen Spektrogrammen erzeugen. Hierfür nutzen wir folgende Regel: „Um Zielzonen in einem Spektrogramm zu erzeugen, muss man für jeden Zeit-Frequenz-Punkt eine Gruppe aus diesem Punkt und aus dessen 4 darauffolgenden Punkten erstellen“. Wir erhalten damit ungefähr die gleiche Anzahl an Zielzonen wie Anzahl an Punkten. Bei den Songs und bei der Aufnahme wird diese Regel gleichermaßen angewendet.

Abbildung 28
Spektrogramm mit Zielzonen
Abbildung 28: Spektrogramm mit Zielzonen

In diesem vereinfachten Spektrogramm kann man die verschiedenen Zielzonen sehen, die vom vorherigen Algorithmus generiert wurden. Da die Zielgröße 5 ist, gehören die meisten Punkte zu 5 Zielzonen (mit Ausnahme der Punkte am Anfang und Ende des Spektrogramms).

Hinweis: Zunächst war es für mich nicht verständlich, warum wir für die Aufnahme so viele Zielzonen berechnen müssen. Wir könnten Zielzonen doch beispielsweise mit solch einer Regel erzeugen: „Für jeden Punkt, dessen Label ein Vielfaches von 5 ist, muss man eine Gruppe erstellen, die aus dieser Frequenz und den 4 Frequenzen danach besteht“. Mit dieser Regel würde die Anzahl der Zielzonen um den Faktor 5 reduziert werden - und damit auch die erforderliche Suchzeit (diese wird im nächsten Kapitel erklärt). Der einzige mögliche Grund ist, dass die Berechnung aller möglichen Zonen sowohl für die Aufnahme als auch für den Song die Rauschtoleranz stark erhöht.

Adressgenerierung

Wir haben jetzt mehrere Zielzonen, was machen wir als nächstes? Wir erstellen für jeden Punkt eine Adresse basierend auf diesen Zielzonen. Um diese Adressen zu erstellen, benötigen wir zusätzlich einen Ankerpunkt pro Zielzone. Auch hier erklärt das Shazam-Paper nicht, wie das geht. Stellen wir uns also vor, dass dieser Ankerpunkt der 3. Punkt vor der Zielzone ist. Der Anker kann beliebig sein, solange die Art und Weise wie er erzeugt wird, reproduzierbar ist (was dank unserer Ordnungsrelation möglich ist).

Abbildung 29
Spektrogramm mit Zielzonen und Ankerpunkten
Abbildung 29: Spektrogramm mit Zielzonen und Ankerpunkten

In dieser Abbildung sind 2 Zielzonen mit ihren Ankerpunkten gezeichnet. Konzentrieren wir uns auf die violette Zielzone. Die von Shazam vorgeschlagene Adressformel folgt einem:

["Frequenz des Ankers"; "Frequenz des Punktes"; "Deltazeit zwischen Anker und Punkt"].

Für die violette Zielzone:

  • die Adresse von Punkt 6 ist ["Frequenz von 3"; "Frequenz von Punkt 6"; "Deltazeit zwischen Punkt 3 und Punkt 6"], also konkret [10; 30; 1],
  • die Adresse von Punkt 7 ist [10; 20; 2].

Beide Punkte erscheinen auch in der braunen Zielzone, ihre Adressen mit dieser Zielzone sind [10; 30; 2] für Punkt 6 und [10; 20; 3] für Punkt 7.

Wir haben über „Adressen“ gesprochen. Das impliziert, dass diese Adressen mit etwas verknüpft sind. Im Falle der vollen Songs (also nur auf der Serverseite) sind diese Adressen mit dem folgenden Paar verbunden: ["absolute Zeit des Ankers im Song"; "Song-ID"]. In unserem einfachen Beispiel mit den 2 vorherigen Punkten haben wir dann das folgende Ergebnis:

[10; 30; 1] → [2; 1]

[10; 30; 2] → [2; 1]

[10; 30; 2] → [1; 1]

[10; 30; 3] → [1; 1]

Wenn man die gleiche Logik für alle Punkte aller Zielzonen aller Song-Spektrogramme anwendet, erhält man eine sehr große Tabelle mit zwei Spalten:

  • den Adressen
  • den Paaren ["Zeit des Ankers"; "Song-ID"]

Diese Tabelle ist die Audio-Fingerabdruck-Datenbank von Shazam. Wenn ein Song durchschnittlich 30 Spitzenfrequenzen pro Sekunde enthält und die Zielzone 5 ist, beträgt die Größe dieser Tabelle 5·30·S, wobei S die Anzahl der Sekunden der Musiksammlung ist.

Erinnern wir uns, wir hatten eine FFT mit 1024 Samples verwendet, das heißt, dass es nur 512 mögliche Frequenzwerte gibt. Diese Frequenzen können in 9 Bits kodiert werden (29 = 512). Unter der Annahme, dass die Deltazeit in Millisekunden liegt, wird sie niemals über 16 Sekunden liegen, da dies einen Song mit einem 16-Sekunden-Part ohne Musik (oder sehr niedrigen Sound) bedeuten würde. So kann die Deltazeit in 14 Bits kodiert werden (214 = 16384). Die Adresse kann in einer 32-Bit-Ganzzahl (Integer) codiert werden:

  • 9 Bits für die "Frequenz des Ankers"
  • 9 Bits für die "Frequenz des Punktes"
  • 14 Bits für die "Deltazeit zwischen Anker und Punkt"

Unter Verwendung derselben Logik kann das Paar ("Zeit des Ankers"; "Song-ID") in einer 64-Bit-Ganzzahl (Integer) codiert werden (32 Bit für jeden Teil).

Die Fingerabdruck-Tabelle kann als ein einfaches Array von 64-Bit-Ganzzahlen implementiert werden, wobei:

  • der Index des Arrays eine 32-Bit-Ganzzahl-Adresse ist,
  • die Liste der 64-Bit-Ganzzahlen aus allen Paaren für diese Adresse besteht.

Mit anderen Worten: Wir haben die Fingerabdruck-Tabelle in eine invertierte Suche umgewandelt, die einen Suchvorgang in O(1) ermöglicht, also eine sehr effektive Suchzeit hat.

Hinweis: Sicher hast du dich gefragt, warum wir den Ankerpunkt nicht innerhalb der Zielzone gewählt haben. Wir hätten als Ankerpunkt zum Beispiel den ersten Punkt der Zielzone wählen können. Wenn wir das jedoch getan hätten, hätten wir viele Adressen der Form [Frequenz-Anker; Frequenz-Anker; 0] erzeugt. Dadurch wären viele Paare ["Ankerzeit"; "Song-ID"] mit der Adresse [Y, Y, 0] entstanden, wobei Y die Häufigkeit (zwischen 0 und 511) angibt. Mit anderen Worten, das Nachschlagen wäre verzerrt gewesen.

Fingerabdrücke suchen und bewerten

Wir haben jetzt eine praktische Datenstruktur auf der Serverseite, wie können wir sie nun verwenden?

Suche

Um eine Suche durchzuführen, wird die Erzeugung des Fingerabdrucks direkt für die aufgenommene Audiodatei ausgeführt (auf dem Smartphone), sodass eine Adress-/Wert-Struktur erzeugt wird, die sich geringfügig auf Seiten des Wertes unterscheidet:

["Frequenz des Ankers"; "Frequenz des Punktes"; "Deltazeit zwischen dem Anker und dem Punkt"] → ["absolute Zeit des Ankers in Aufnahme"].

Diese Daten werden dann an den Shazam-Server gesendet. Wenn wir annehmen, dass 300 Zeit-Frequenz-Punkte im gefilterten Spektrogramm des 10-Sekunden-Aufnahme vorhanden sind und eine Zielzone aus 5 Punkten besteht, dann bedeutet das, dass ungefähr 1500 Daten an Shazam gesendet werden.

Jede Adresse aus der Aufnahme wird verwendet, um in der Fingerabdruck-Datenbank nach den zugehörigen Paaren ["absolute Zeit des Ankers im Song"; "Song-ID"] zu suchen. In Bezug auf die Zeit-Komplexität (unter der Annahme, dass die Fingerabdruck-Datenbank innerhalb des Speichers ist) ist die Suche proportional zur Anzahl der an Shazam gesendeten Adressen (in unserem Fall 1500). Diese Suche ergibt eine große Anzahl an Paaren, sagen wir für den Rest des Artikels, dass sie M Paare zurückgibt.

Obwohl M riesig ist, ist es viel niedriger als die Anzahl der Noten (Zeit-Frequenz-Punkte) aller Songs zusammen. Die wahre Stärke dieser Suche besteht darin, dass wir nicht suchen, ob eine Note in einem Song existiert, sondern ob 2 Noten getrennt von Deltazeit Sekunden im Song vorhanden sind. Am Ende dieses Kapitels werden wir noch mehr über diese Zeit-Komplexität sprechen.

Ergebnisfilterung

Obwohl es in dem Shazam-Paper nicht erwähnt wird, ist anzunehmen, dass der nächste Schritt die Filterung der M Suchergebnisse ist, indem nur die Paare der Songs beibehalten werden, die eine Mindestzahl von Zielzonen gemeinsam mit der Aufzeichnung haben.

Lasst uns zum Beispiel annehmen, dass unsere Suche Folgendes ergibt:

  • 100 Paare von Song 1, der 0 Zielzonen gemeinsam hat mit der Aufnahme
  • 10 Paare von Song 2, der 0 Zielzonen gemeinsam hat mit der Aufnahme
  • 50 Paare von Song 5, der 0 Zielzonen gemeinsam hat mit der Aufnahme
  • 70 Paare von Song 8, der 0 Zielzonen gemeinsam hat mit der Aufnahme
  • 83 Paare von Song 10, der 30 Zielzonen gemeinsam hat mit der Aufnahme
  • 210 Paare von Song 17, der 100 Zielzonen gemeinsam hat mit der Aufnahme
  • 4400 Paare von Song 13, der 280 Zielzonen gemeinsam hat mit der Aufnahme
  • 3500 Paare von Song 25, der 400 Zielzonen gemeinsam hat mit der Aufnahme

Unsere 10-Sekunden-Aufnahme hat (ungefähr) 300 Zielzonen. Im besten Fall:

  • Song 1 und die Aufnahme haben eine 0 % Übereinstimmung
  • Song 2 und die Aufnahme haben eine 0 % Übereinstimmung
  • Song 5 und die Aufnahme haben eine 0 % Übereinstimmung
  • Song 8 und die Aufnahme haben eine 0 % Übereinstimmung
  • Song 10 und die Aufnahme haben eine 10 % Übereinstimmung
  • Song 17 und die Aufnahme haben eine 33 % Übereinstimmung
  • Song 13 und die Aufnahme haben eine 91,7 % Übereinstimmung
  • Song 25 und die Aufnahme haben eine 100 % Übereinstimmung

Wir werden nur die Paare der Songs 13 und 25 für das Ergebnis behalten. Obwohl die Songs 1, 2, 5 und 8 mehrere Paare mit der Aufnahme gemeinsam haben, bildet keines von ihnen zusammen mit der Aufnahme mindestens eine Zielzone (von 5 Punkten). Dieser Schritt kann viele falsche Ergebnisse entfernen, da die Fingerabdruck-Datenbank von Shazam viele Paare für die gleiche Adresse hat und man leicht mit Paaren an der gleichen Adresse enden könnte, die nicht zur selben Zielzone gehören. Wenn du den Grund nicht verstehst, sieh dir das letzte Bild des vorherigen Kapitels an: Die [10; 30; 2]-Adresse wird von 2 Zeit-Frequenz-Punkten verwendet, die nicht zur selben Zielzone gehören. Wenn die Aufnahme auch eine [10; 30; 2] enthält, wird (mindestens) eines der beiden Paare im Ergebnis in diesem Schritt herausgefiltert.

Dieser Schritt kann in O(M) mit Hilfe einer Hash-Tabelle ausgeführt werden, deren Key das Paar ["Song-ID"; "absolute Zeit des Ankers im Song"] ist sowie der Häufigkeit, die es im Ergebnis erscheint:

  • Wir durchlaufen die M Ergebnisse und zählen (in der Hash-Tabelle) die Häufigkeit, die ein Paar vorhanden ist.
  • Wir entfernen alle Paare (das heißt den Key der Hash-Tabelle), die weniger als 4 Mal erscheinen (das heißt, wir entfernen alle Punkte, die keine Zielzone formen).*
  • Wir zählen die Häufigkeit X, die die Song-ID Teil eines Keys in der Hash-Tabelle ist, das heißt, wir zählen die Anzahl der vollständigen Zielzonen im Song. Da das Paar von der Suche kommt, sind diese Zielzonen ebenfalls in der Aufnahme.
  • Wir behalten nur das Ergebnis, dessen Songnummer über 300*coeff liegt (300 ist die Nummer der Zielzone der Aufnahme, diese Zahl wird aufgrund des Rauschens mit Hilfe von coeff reduziert).
  • Wir setzen die restlichen Ergebnisse in eine neue Hash-Tabelle, deren Index die Song-ID ist (diese Hashmap wird für den nächsten Schritt nützlich sein).

*Die Idee ist, nach der Zielzone zu suchen, die durch einen Ankerpunkt in einem Song erzeugt wird. Dieser Ankerpunkt kann durch die Song-ID, zu dem er gehört, und durch die absolute Zeit definiert werden. Wir haben hier eine Annäherung vorgenommen, weil man in einem Song mehrere Ankerpunkte gleichzeitig haben kann. Da es sich um ein gefiltertes Spektrogramm handelt, haben wir nicht viele Ankerpunkte gleichzeitig. Jedoch wird der Key ["Song-ID"; "absolute Zeit des Ankers im Song"] alle Zielzonen erfassen, die von diesen Zielpunkten erzeugt werden.

Hinweis: Wir haben in diesem Algorithmus 2 Hashtabellen verwendet. Wenn du nicht weißt, wie das funktioniert, denk es dir einfach als einen sehr effizienten Weg, Daten zu speichern und abzurufen. Wenn du mehr wissen willst, kannst du den Artikel über die HashMap in Java (Englisch) lesen, der eine effiziente Hash-Tabelle ist.

Zeitkohärenz

An dieser Stelle haben wir Songs gefunden, die wirklich nah an der Aufnahme sind. Aber wir müssen immer noch die Zeitkohärenz (Zusammenhang über die Zeit) zwischen den Noten der Aufnahme und diesen Songs verifizieren. Hier ist der Grund dafür:

Abbildung 30
Spektrogramm-Suche und Zeitkohärenz
Abbildung 30: Spektrogramm-Suche und Zeitkohärenz

In dieser Abbildung haben wir 2 Zielzonen, die zu 2 verschiedenen Songs gehören. Wenn wir die Zeitkohärenz nicht beachten, würden diese Zielzonen die Übereinstimmungsraten zwischen den zwei Songs erhöhen, obwohl sie nicht gleich klingen, da die Noten in diesen Zielzonen nicht in derselben Reihenfolge gespielt werden.

In diesem letzten Schritt geht es um die zeitliche Reihenfolge. Die Idee ist:

  • Wir berechnen für jeden verbleibenden Song die Noten und ihre absolute Zeitposition im Song.
  • Wir tun das Gleiche für die Aufnahme, die uns die Noten und ihre absolute Zeitposition in der Aufnahme gibt.
  • Wenn die Noten im Song und die in der Aufnahme zeitlich kohärent sind, sollten wir eine Beziehung wie diese finden: "Absolute Zeit der Note im Song = absolute Zeit der Note in der Aufnahme + Delta", wobei Delta die Anfangszeit des Teils des Songs ist, der mit der Aufnahme übereinstimmt.
  • Für jedes Lied müssen wir das Delta finden, das die Anzahl der Noten maximiert, die diese Zeitbeziehung berücksichtigen.
  • Dann wählen wir den Song aus, der die maximale Anzahl an Noten aufweist, die mit der Aufnahme zeitlich übereinstimmen.

Jetzt, wo wir eine gute Vorstellung vom Algorithmus bekommen haben, schauen wir uns an, wie wir dies technisch umsetzen können. An dieser Stelle haben wir für eine Liste von Adressen/Werten:

["Frequenz des Ankers"; "Frequenz des Punktes"; "Deltazeit zwischen dem Anker und dem Punkt"] → ["absolute Zeit des Ankers und der Aufnahme"].

Und wir haben für jeden Song eine Liste von Adressen/Werten (in der Hash-Tabelle des vorherigen Schritts gespeichert):

["Frequenz des Ankers"; "Frequenz des Punktes"; "Deltazeit zwischen dem Anker und dem Punkt"] → ["absolute Zeit des Ankers im Song"; "Song-ID"].

Der folgende Prozess muss für alle verbleibenden Songs durchgeführt werden:

  • Für jede Adresse in der Aufnahme erhalten wir den zugehörigen Wert des Songs und wir berechnen Delta = "absolute Zeit des Ankers in der Aufnahme" – "absolute Zeit des Ankers im Song" und setzen das Delta in eine "Liste von Deltas".
  • Es ist möglich, dass die Adresse in der Aufnahme mit mehreren Werten in dem Song verknüpft ist (das heißt, mehrere Punkte in verschiedenen Zielzonen des Songs). In diesem Fall berechnen wir das Delta für jeden assoziierten Wert und setzen die Deltas in die "Liste von Deltas".
  • Für jeden unterschiedlichen Deltawert in der "Liste von Deltas" zählen wir die Anzahl des Auftretens (mit anderen Worten, wir zählen für jedes Delta die Anzahl der Noten, für die gilt: "absolute Zeit der Note im Song = absolute Zeit von Note in Aufnahme + Delta").
  • Wir behalten den größten Wert (das gibt uns die maximale Anzahl von Noten, die zeitlich zwischen der Aufnahme und dem Song liegen).

Von allen Songs behalten wir den Song mit den meisten zeitkohärenten Noten. Wenn diese Kohärenz über "der Anzahl der Noten in der Aufnahme" * "ein Koeffizient" liegt, dann ist dieser Song der richtige.

Wir müssen dann nur noch nach den Metadaten des Songs ("Künstlername", "Songname", "iTunes URL", "Amazon URL", ...) mit der Song-ID suchen und das Ergebnis an den Nutzer zurückgeben.

Ein Wort über Komplexität

Diese Suche ist wirklich komplizierter als die einfache Suche, die wir zuerst kennengelernt hatten. Mal sehen, ob uns die Komplexität einen Vorteil bringt. Die erweiterte Suche ist ein schrittweiser Ansatz, der die Komplexität bei jedem Schritt reduziert.

Damit es besser zu verstehen ist, führen wir noch mal alle getroffenen Annahmen bzw. Entscheidungen auf, die wir gemacht hatten. Zudem kommen neue Annahmen hinzu, um das Problem zu vereinfachen:

  • Wir haben 512 mögliche Frequenzen.
  • Im Durchschnitt beinhaltet ein Song 30 Spitzenfrequenzen (Peaks) pro Sekunde.
  • Daher enthält eine 10-Sekunden-Aufnahme 300 Zeitfrequenz-Punkte.
  • S ist die Anzahl an Sekunden der gesamten Musiksammlung.
  • Die Größe der Zielzone ist 5 Noten.
  • Neue Annahme: Die Deltazeit zwischen einem Punkt und seinem Anker ist entweder 0 oder 10 Millisekunden.
  • Neue Annahme: Die Erzeugung von Adressen ist gleichförmig verteilt. Für jede Adresse [X, Y, T] ist die gleiche Anzahl von Paaren vorhanden, wobei X und Y eine der 512 Frequenzen sind und T entweder 0 oder 10 Millisekunden ist.

Der erste Schritt zur Suche erfordert nur 5 · 300 unitäre Suchen.

Die Größe des Ergebnisses M ist die Summe des Ergebnisses der 5 · 300 unitären Suchen:

M = (5 · 300) ·(S · 30 · 5 · 300) / (512 · 512 · 2)

Der zweite Schritt ist die Ergebnisfilterung, sie kann in M-Operationen erfolgen. Am Ende dieses Schrittes sind N Noten verteilt in Z Songs. Ohne eine statistische Analyse der Musiksammlung ist es unmöglich, den Wert von N und Z zu erhalten. N sollte niedriger sein als M, und Z sollte nur ein paar Songs darstellen, sogar bei einer riesigen Songdatenbank wie der von Shazam.

Der letzte Schritt ist die Analyse der Zeitkohärenz der Z Songs. Wir nehmen an, dass jeder Song ungefähr die gleiche Menge an Noten hat: N/Z. Im schlimmsten Fall (eine Aufnahme von einem Song, der nur eine Note enthält, die kontinuierlich gespielt wird), ist die Komplexität einer Analyse (5·300)·(N/Z).

Die Kosten der Z Songs betragen: 5·300·N.

Da N<<M, entsprechen die tatsächlichen Kosten dieser Suche:

M = (300 · 300 · 30 · S) · (5 · 5) / (512 · 512 · 2) = 67500000 / 524288 · S = 128,75 · S

Zur Erinnerung: Die Kosten der einfachen Suche waren:

300 · 300 · 30 · S = 2 700 000 · S

Diese neue Suche ist ca. 20 000 mal schneller!

Hinweis: Die wahre Komplexität hängt von der Verteilung der Frequenzen innerhalb der Songsammlung ab, aber diese einfache Kalkulation gibt uns eine gute Vorstellung von der tatsächlichen Berechnung.

Verbesserungen

Das Shazam-Paper stammt aus dem Jahr 2003 und die damit verbundenen Forschungen sind noch älter. Im Jahr 2003 wurden 64-Bit-Prozessoren auf dem Mainstream-Markt veröffentlicht.

Anstatt einen Ankerpunkt pro Zielzone zu verwenden, wie es das Papier vorschlägt (wegen der begrenzten Größe einer 32-Bit-Ganzzahl), könnte man 3 Ankerpunkte verwenden (z. B. die 3 Punkte unmittelbar vor der Zielzone) und die Adresse eines Punktes in der Zielzone in einer 64-Bit-Ganzzahl speichern. Dies würde die Suchzeit dramatisch verbessern.

In der Tat würde die Suche 4 Noten in einem Song finden, getrennt von delta_time1, delta_time2 und delta_time3 (in Sekunden), wodurch die Anzahl der Ergebnisse M sehr (sehr) niedriger wäre als die, die wir gerade berechnet haben.

Ein großer Vorteil dieser Fingerabdrucksuche ist übrigens ihre hohe Skalierbarkeit:

  • Anstatt nur 1 Fingerabdruck-Datenbank kann man D Datenbanken nutzen, von denen jede 1/D der gesamten Songsammlung enthält.
  • Man kann zur gleichen Zeit nach dem zur Aufnahme ähnlichsten Song in den D Datenbanken suchen.
  • Danach wählt man den ähnlichsten Song von diesen D Songs aus.
  • Der gesamte Prozess ist damit D mal schneller.

Kompromisse

Eine weitere interessante Diskussion ist die Rauschtoleranz bzw. Rauschrobustheit dieses Algorithmus. Hierüber könnten wir einen eigenen umfangreichen Artikel schreiben, doch an dieser Stelle es ist besser, nur ein paar Worte darüber zu verlieren.

Wenn du aufmerksam gelesen hast, hast du bemerkt, dass wir viele Schwellenwerte, Koeffizienten und feste Werte verwendet haben (wie die Abtastrate, die Dauer einer Aufnahme etc.). Wir haben auch viele Algorithmen gewählt (um ein Spektrogramm zu filtern, um ein Spektrogramm zu erzeugen usw.). Sie alle haben einen Einfluss auf den Rauschwiderstand und die Zeitkomplexität. Die wahre Herausforderung besteht darin, die richtigen Werte und Algorithmen zu finden, die:

  • den Rauschwiderstand,
  • die Zeitkomplexität und
  • die Präzision (um die Anzahl von „False Positives“ zu reduzieren)

maximieren.

Fazit

Im besten Fall verstehst du jetzt wie Shazam funktioniert. Der Autor hat viel Zeit benötigt, um die verschiedenen Themen dieses Artikels zu verstehen. Dieser Artikel macht dich vielleicht nicht zu einem Experten, doch du hast zumindest ein sehr gutes Bild von den Prozessen, die hinter Shazam stecken. Denke daran, dass Shazam nur eine von mehreren möglichen Implementierungen für Audio-Fingerabdrücke ist.

Du solltest jetzt theoretisch in der Lage sein, dein eigenes Shazam zu programmieren. Du kannst dir diesen sehr guten Artikel ansehen, der sich mehr darauf konzentriert, wie man ein vereinfachtes Shazam in Java programmiert, und weniger auf die dahinter stehenden Konzepte. Du kannst auch „Robust Landmark-Based Audio Fingerprinting“ lesen, dort geht es um eine MatLab-Implementierung von Shazam. Und selbstverständlich kannst du das Paper von Shazam-Mitbegründer Avery Li-Chun Wang hier selbst durchlesen.

Die Welt des Musikberechnens (Music Computing) ist ein sehr interessantes Feld mit praktischen Algorithmen, die wir jeden Tag benutzen, ohne es zu wissen. Obwohl Shazam nicht leicht zu verstehen ist, ist es einfacher als:

  • der Abgleich von Singen/Summen mit Songs (SoundHound ermöglicht, den gesuchten Song zu summen/singen)
  • die Spracherkennung und Sprachsynthese (implementiert von Skype, Apple "Siri" und Android "Ok Google")
  • das Prüfen, ob 2 Songs ähnlich sind (Echonest hat sich darauf spezialisiert)

Falls du Interesse hast: Es gibt einen jährlichen Wettbewerb zwischen Forschern zu diesen Themen. Er heißt MIREX-Wettbewerb. Die Algorithmen der einzelnen Teilnehmer werden dort auch veröffentlicht.

Der Autor hat in den letzten 3 Jahren ungefähr 200 Stunden damit verbracht, die Signalverarbeitungskonzepte und die Mathematik dahinter zu verstehen, er hat einen eigenen Shazam-Prototypen programmiert, Wangs Paper vollständig verstanden und sich die Prozesse erarbeitet, die das Paper nicht erklärt. Sein Beweggrund: „Ich habe diesen Artikel geschrieben, weil ich nie einen Artikel gefunden habe, der Shazam wirklich erklärt und ich wünschte, ich hätte einen Artikel im Jahr 2012 finden können, als ich mit diesem Nebenprojekt begann.“

Falls du einen Fehler im Artikel findest, so trage ihn bitte hier ein: Hinweise zum Artikel: Wie funktioniert Shazam

Fragen zum Artikel? Dann stelle sie bitte in der Mathelounge (Stichwort "shazam").

  Schreib uns deine Hinweise