Wie Shazam Songs erkennt

Inhaltsverzeichnis

Audio-Fingerprinting hat Avery Li-Chun Wang, einer der Shazam-Gründer, zuerst 2003 in einem Whitepaper präsentiert. Darin stellt er einen Algorithmus zur Identifizierung von Musiktiteln mittels kurzer Aufnahmen von Mobiltelefonen vor. Im Jahr 2000 war ein Mobiltelefon tatsächlich nur ein mobiles Telefon und in jeder Beziehung weit vom späteren Smartphone entfernt. Mikrofonqualität, Signalverarbeitungsmöglichkeiten im Gerät und die Übertragungsqualität von GSM waren nur einige der technischen Hürden, die seinerzeit als unüberwindbar galten. Einer der Gründer und früherer CEO Chris Barton erzählt das unterhaltsam in einem Video.

Empfohlener redaktioneller Inhalt

Mit Ihrer Zustimmmung wird hier ein externes YouTube-Video (Google Ireland Limited) geladen.

YouTube-Video immer laden YouTube-Video jetzt laden

Ich bin damit einverstanden, dass mir externe Inhalte angezeigt werden. Damit können personenbezogene Daten an Drittplattformen (Google Ireland Limited) übermittelt werden. Mehr dazu in unserer Datenschutzerklärung.

Shazam hielt trotz aller Bedenken an der Idee fest und engagierte Li-Chun Wang, der die Aufgabe zunächst selbst für unmöglich hielt. Dann kann ihm jedoch die Idee für einen raffinierten neuen Algorithmus, der das Problem bereits ein Jahr später lösen sollte. 2001 nutzte man diesen mit einem Anruf, heute verwendet man eine App.

Das Prinzip des Algorithmus ist einfach: Er bestimmt die charakteristischen Audioeigenschaften der Probe – ihren Audiofingerabdruck – und sucht damit nach Übereinstimmungen in einer Datenbank, die Audiofingerabdrücke der Originalmusikstücke enthält. Shazam hat zwar nicht alle Aspekte des Audio-Fingerprinting neu erfunden, jedoch das Problem gelöst, mit stark verrauschten Aufnahmen und geringen Datenraten bei der Datenbankabfrage zurechtzukommen.

Shazam hat die Details seines Algorithmus nie komplett veröffentlicht. Anhand des Prinzips haben aber einige Hobbyentwickler eigene Varianten des Algorithmus nachimplementiert, anhand derer man gut erkennt, wie auch Shazams Original funktionieren muss.

Höhe und Stärke des Tons entscheidend

Ein Musikstück lässt sich als eine Tonfolge beschreiben, wobei ein Ton durch seine Höhe (Frequenz) und Stärke (Amplitude) definiert ist. Shazam versucht, die Musik daran zu erkennen, und ignoriert weitere Tonparameter wie Dauer und Klangfarbe. Für die Suche in der Musikdatenbank braucht Shazam einen Audiofingerabdruck, der den Song eindeutig identifiziert. Das geht im Prinzip mit einer Reihe von Paaren (Tupel) von Frequenz (Tonhöhe) und Lautstärke (Tonstärke). In welchem zeitlichen Abstand (Tonfolge) diese hörbar sind, zeichnet den Song eindeutig aus.

Ein Audiosignal liegt auf dem Smartphone oder PC zunächst aber nur als Reihe von vielen Tausend Samples vor. Die geben den Luftdruck beziehungsweise die Membranauslenkung an, die vom Mikrofon alle 0,02 ms gemessen wurde. Die Frequenzen lassen sich daran aber nicht direkt ablesen. Zur Bestimmung der enthaltenen Frequenzen nutzt man eine Fourier-Transformation, die ein Audiosignal als Frequenzen und Amplituden innerhalb eines kurzen Zeitfensters darstellt. Für digitalisierte Audiosignale gibt es die effizient berechenbare Variante der Diskreten Fourier-Transformation.

Auch in der schnellen Version, der "Fast Fourier Transform" (FFT), ist die Frequenzanalyse ein rechenintensiver Prozess, der es daher nahelegt, die Menge der zu verarbeitenden Daten möglichst zu reduzieren. Bei einem digitalisierten Audiosignal kann dies durch Zusammenmischen der Stereokanäle (falls das Handy mehr als Mono aufnimmt) und sogenanntes "Downsampling" erfolgen, also die Zusammenfassung aufeinanderfolgender Samples. Wie Shazam das genau macht, verraten sie nicht, die Diagramme im Whitepaper lassen aber auf einen Wert von 4 schließen. Mit dem reduziert Shazam das Audiosignal auf circa 5 kHz und damit die Datenmenge auf ein Viertel.

Das Ergebnis der Fourier-Transformation ist ein Spektrogramm des Musikstücks mit einem dreidimensionalen Bezug von Tonhöhe, Lautstärke und Zeit. Man stellt das als zweidimensionale Heatmap dar, mit der Zeit als x-Achse, der Tonhöhe als y-Achse und Farben für die Pixel zwischen Blau (leise) und Rot (laut).

Die Datenmenge ist so jedoch viel zu groß, um damit eine Datenbank abzufragen. Shazam filtert daher nur besonders laute Töne (Peaks) heraus und achtet dabei auf eine möglichst gleichmäßige Verteilung dieser Peaks über die Dauer des Musikstücks. Shazam sagt zu seiner Definition eines besonders lauten Tons nichts. Die Nachahmergemeinschaft im Netz ist sich aber einig, dass dabei die Charakteristik des menschlichen Gehörs zu berücksichtigen ist, die tiefe Töne leiser und hohe lauter empfinden lässt. Das weiß auch die Musikindustrie und hebt die Lautstärken tiefer Töne dementsprechend an. Zur Bestimmung der signifikantesten Töne dient daher ein frequenzabhängiger Schwellwertfilter. Der berücksichtigt zusätzlich die Eigenschaft vieler Musikstücke, zu Beginn und am Ende deutlich leiser zu sein als in der Mitte.

Constellation Map erstellen

Überträgt man die Peaks in ein eigenes Diagramm, ähnelt es einer Sternkarte, weshalb das Whitepaper sie auch als "Constellation Map" bezeichnet. Eine Constellation Map repräsentiert zeitlich gleichmäßig verteilt die signifikantesten Töne eines Musikstücks. Wendet man den Algorithmus auf eine kurze Aufnahme an, berechnet er auch dafür eine Constellation Map.

Trotzdem ist es keine gute Idee, die Constellation Maps von Millionen Musikstücken nach einer Übereinstimmung mit der Map einer Probe zu durchsuchen. Ausgehend von 30 Peaks pro Sekunde könnte die Suche nach einer Probe von 10 Sekunden Länge in 1 Million Musikstücken von durchschnittlich 3 Minuten Länge rund 1,5 Billionen Operationen erfordern (30 × 10 × 30 × 10 × 1.000.000 × 3 × 60) – ohne dabei mögliche Verfälschungen der Probe zu berücksichtigen.

Eine effiziente Suche ist das Problem – die Lösung dafür ist der eigentliche Clou des Algorithmus. Sie basiert auf der Idee, anstelle einzelner Peaks gleich mehrere auf einmal zu suchen. Dazu unterteilt Shazam eine Constellation Map in sogenannte "Target Zones" und legt für jede einen Peak als Ankerpunkt fest. Dann kombiniert es den Frequenzwert von jedem Peak einer Target Zone mit dem Frequenzwert des zugeordneten Ankerpunkts sowie der zeitlichen Differenz zwischen beiden Peaks. Das Ergebnis ist eine Bitfolge (Hashkey), die Shazam zusammen mit der zeitlichen Position des Ankerpunkts in eine Datenbank schreibt. Hashkeys und Zeitmarken einer Constellation Map ergeben zusammen den Audiofingerabdruck des Musikstücks oder der Probe.

Definition der Target Zones unbekannt

Die Methode zur Definition der Target Zones beschreibt Shazam leider nicht. Implementierungen von Nachahmern im Netz fassen dazu beispielsweise jeden n-ten Peak mit den darauffolgenden m Peaks zusammen und verwenden dabei Werte von 1 bis 5 für n und 5 bis 7 für m.

Die Größe der Hashkeys beträgt 32 Bit: jeweils 9 Bit für die beiden Peaks und 14 Bit für deren Zeitdifferenz. Damit lassen sich 512 (2^9) verschiedene Frequenzen unterscheiden, die bei einer zeitlichen Auflösung von 1 Millisekunde maximal rund 16 Sekunden ((2^14)/1000) Abstand haben dürfen. Musikstücke wie ASAP von John Cage sind damit raus, für populäre Musik ist dieser Wert jedoch ausreichend.

Für eine Constellation Map mit 30 Peaks pro Sekunde und Target Zones mit 5 Peaks ergeben sich für den Audiofingerabdruck eines Musikstücks von 3 Minuten Länge 27.000 Werte (30 × 5 × 3 × 60) bei maximaler Überlappung der Target Zones (wenn man jeden Peak auch mal als Ankerpunkt wählt). Legt man beispielsweise nur jeden dritten Peak als Ankerpunkt fest, reduziert sich die Größe auf 9000 Werte. Multipliziert man weiter mit einer realistischen Anzahl von 50 Millionen Songs in einer Musikdatenbank für Audiofingerabdrücke, ergeben sich auch für den kleineren Wert immerhin 450 Milliarden Hashkeys, unter denen es Redundanzen geben muss, da sich mit Hashkeys von 32 Bit nur rund 4 Milliarden Werte unterscheiden lassen. Tatsächlich kann derselbe Hashkey in mehreren Songs vorkommen. Der Key wird dann mehrfach in die Datenbank geschrieben, jeweils verknüpft mit einer Song-ID und der Position des Hashkeys in genau diesem Musikstück.

Die Beziehung von Zeitmarke und Musikstück erfolgt im Listenelement als Kombination beider Werte mit jeweils 32 Bit, wobei der Wert für das Musikstück eine ID ist. Mit dieser Organisation ist die Fingerabdrucktabelle in der Musikdatenbank auf maximal 2^32 Zeilen begrenzt und lässt sich mit dem Hashkey indizieren.

Datenbankabgleich

Die Suche erfolgt dann schrittweise. Zunächst befragt der Algorithmus die Datenbank nach allen Hashkeys der Probe – ihrem Audiofingerabdruck. Das Ergebnis enthält für jeden Hashkey eine Liste der Songs und der Zeitmarken, an denen der Hashkey darin vorkommt. Dem Algorithmus liegen so sämtliche Musikstücke der Musikdatenbank vor, die für einen Treffer infrage kommen.

Ob der gesuchte Song tatsächlich darunter ist, hängt davon ab, ob die Relation ein Musikstück enthält, dessen zu den Hashkeys zugeordnete Zeitmarken die gleichen relativen zeitlichen Abstände haben wie in der Probe. Eine solche Übereinstimmung findet man als Mensch leicht mittels eines Diagramms, das die Verteilung der Zeitmarken als Streufeld von Punkten darstellt, deren Koordinaten die zeitlichen Positionen in Probe und Musikstück sind. Ein Treffer ist an einer signifikanten Häufung von Punkten in Form einer diagonal verlaufenden Linie zu erkennen.

Für eine mathematische Lösung dieses Problems verwendet man üblicherweise Regressionsmethoden. Deren Berechnungsaufwand ist jedoch sehr hoch. Shazam verwendet daher ein anderes Vorgehen: Die korrespondierenden Zeitmarken von Probe und Musikstück im Diagramm lassen sich als tm = tp + ∆tp formulieren, wobei tm die Zeitmarke des Musikstücks und tp die der Probe ist. ∆tp bezeichnet die Differenz beider Zeitmarken und lässt sich mit ∆tp = tm - tp berechnen. Diese Differenzen berechnet der Algorithmus für jedes Streufelddiagramm, also für alle Songs des Suchergebnisses, und erstellt daraus jeweils ein Histogramm. Der letzte Schritt untersucht dann die Histogramme nach Ausreißern. Weist einer der Songs eine statistisch signifikante Abweichung vom Mittelwert auf, handelt es sich mit großer Wahrscheinlichkeit um das gesuchte Musikstück. Das liegt daran, dass die Zeitdifferenzen sich beim richtigen Song viel weniger unterscheiden als bei anderen Songs, die nur zufällig ein paar gleiche Hashkeys enthalten.

Suchaufwand

Für die Performance des beschriebenen Verfahrens sind zwei Faktoren maßgeblich: der Rechenaufwand zur Suche in der Fingerabdrucktabelle der Musikdatenbank und der zur Analyse der Trefferliste. Bei der Suche mit den Hashkeys einer Probe handelt es sich um einen Feldindex, und die Fingerabdrucktabelle kann aufgrund ihres kompakten Formats auch bei einer großen Anzahl von Musikstücken im Hauptspeicher liegen (in-memory). Beispielsweise belegen die Audiofingerabdrücke von 50 Millionen Songs bei angenommenen 9000 Werten pro Song und 64 Bit pro Wert rund 4 TB (50.000.000 × 9000 × 64/8). Verteilt man die Arbeit über mehrere Server ist das kein Problem.

Der Aufwand für die Suche hängt von der Dauer der Probe ab. Je länger die ist, desto mehr Hashkeys gehören dazu. Jeder Hashkey erfordert aber lediglich einen Tabellenzugriff. Bei der Analyse kommt es darauf an, die Datenmenge der Kandidaten gering zu halten. Da die Hashkeys sehr spezifisch sind, gibt es nur eine überschaubare Anzahl an Kandidaten.

Das von Shazam vorgestellte Verfahren funktioniert außerordentlich gut, wie sich mit der App leicht herausfinden lässt. Auch die frei verfügbaren Implementierungen im Netz lassen die Leistungsfähigkeit des Prinzips erkennen. Der Algorithmus ist schnell und findet zuverlässig den gesuchten Song – sofern er sich in der Musikdatenbank befindet.

Zu dieser Bedingung gibt es eine persönliche Anekdote: Shazam konnte auf einem Konzert nämlich auch eine live gespielte Version eines Songs identifizieren. Entweder haben die Musiker den Song millisekundengenau gecovert oder es war in Wirklichkeit nur Playback.