Wie funktioniert Shazam eigentlich?

• Musikerkennung funktioniert, indem die vom Mikrofon aufgenommenen Luftschwingungen in eine Wellenform umgewandelt und anschließend zu einem Spektrogramm sowie einer kleinen Zahl starker Frequenzspitzen komprimiert werden, um daraus den Fingerabdruck eines Songs zu bilden
• Da sich die rohe Wellenform je nach Lautstärke und Wiedergabeumgebung leicht verändert, ist sie als Identifikationsmerkmal schwer zu nutzen; erst durch Anwendung der FFT auf kurze Abschnitte wird die Frequenzstruktur über die Zeit sichtbar und ein stabiler Vergleich möglich
• Die verbleibenden Peaks werden nicht als einzelne Punkte genutzt, sondern als Paare aus anchor und target zone zu Hashes verbunden; diese Kombinationen dienen als hinreichend spezifische Fingerprint-Hashes, um bestimmte Aufnahmen zu unterscheiden
• Für die Suche wird nicht Song für Song verglichen, sondern eine hash-first-Struktur verwendet, die Hashes direkt als Schlüssel nachschlägt; am Ende wird zur höheren Zuverlässigkeit zusätzlich geprüft, ob auch die Zeitabstände der passenden Hashes übereinstimmen
• Serverbasierte Großdatenbanken und On-Device-Ansätze unterscheiden sich in Größe und Einschränkungen, aber der Kern bleibt gleich: Der Großteil der Informationen wird verworfen, nur Landmark-Peaks bleiben erhalten, damit selbst kurze und verrauschte Clips schnell dem richtigen Song zugeordnet werden können

---

Den Klang rückwärts entschlüsseln

• Das Mikrofon eines Smartphones misst Luftschwingungen mit einer extrem dünnen Membran und speichert sie als Zahlenreihe, die den Luftdruck über die Zeit abbildet — die Wellenform
  • Auch das Trommelfell im Ohr empfängt dieselben Druckwellen, aber das Smartphone behandelt sie nicht als Klang an sich, sondern als Zahlenfolge
  • Eingehender Ton wird zehntausende Male pro Sekunde abgetastet, meist mit 44.100 Hz
• Allein mit der rohen Wellenform ist ein Song schwer zu identifizieren; derselbe Song ergibt bei lauterer Wiedergabe eine völlig andere Wellenform, und verschiedene Songs können ähnliche Wellenformen erzeugen
  • Auch bei unterschiedlicher Wiedergabeumgebung kann sich die Wellenform desselben Songs ändern, weshalb sie als Identifikationskriterium ungeeignet ist
• Um dieses Problem zu verringern, muss die Wellenform in kleine Abschnitte zerlegt und darauf die FFT angewendet werden, damit sichtbar wird, welche Frequenzen zu jedem Zeitpunkt enthalten sind
  • Als Frage formuliert entspricht das: „Welche reinen Töne müsste man addieren, um dieses kurze Klangstück wiederherzustellen?“
  • Stapelt man die Ergebnisse der einzelnen Abschnitte nebeneinander, entsteht ein Spektrogramm mit Zeitachse, Frequenzachse und Helligkeitsachse
• Die FFT nutzt aus, dass sich selbst komplexe Wellenformen als Summe von Sinuswellen mit unterschiedlichen Frequenzen, Amplituden und Phasen darstellen lassen
  • Gibt man zum Beispiel 1.024 Samples hinein, erhält man ein Spektrum zurück, das zeigt, wie viel Energie in jeder Frequenz steckt
  • Für jeden Frequenz-Bin werden alle Samples mit einer Sinuswelle dieser Frequenz multipliziert und aufsummiert; ist die Frequenz im echten Signal vorhanden, wird die Summe groß, andernfalls hebt sie sich auf
• Der entscheidende Vorteil der FFT ist die Geschwindigkeit: Eine naive Zerlegung würde pro Abschnitt Millionen Rechenoperationen benötigen, die FFT reduziert das mithilfe mathematischer Symmetrien auf ungefähr n log n
  • Dadurch ist sie schnell genug, um auch auf dem Smartphone hunderte Male pro Sekunde zu laufen
  • Das Gerät schiebt dieses Fenster fortlaufend über das Audiosignal, wendet auf jeden Abschnitt die FFT an und baut aus den Ergebnissen das Spektrogramm auf
• Ein einfaches Beispiel mit einem synthetischen Ton aus nur einer reinen Frequenz hilft beim Verständnis, echte Musik ist aber deutlich komplexer
  • Speist man echte Musik oder Summen über das Mikrofon ein, wirkt das Spektrogramm sehr viel unruhiger, aber die FFT legt darin trotzdem in Echtzeit Struktur frei
  • Im Browser-Beispiel wird das gesamte Audio innerhalb des Browsers verarbeitet und weder aufgezeichnet noch nach außen übertragen

Weniger ist der stärkere Fingerabdruck

• Das System speichert nicht das komplette Spektrogramm, sondern behält nur die größten Peaks und komprimiert es zu einer spärlichen Punktmenge
  • Schwache Signale werden verworfen, sodass nur akustisch wichtige Landmarken übrig bleiben
• Der Grund für dieses radikale Weglassen ist, dass das Speichern und Durchsuchen des vollständigen Spektrogramms selbst für Computer viel zu langsam wäre
  • Je höher der Schwellenwert, desto mehr verschwinden schwache Signale und desto stärker bleiben nur die großen Peaks erhalten
• Diese Methode erhöht die Rauschrobustheit
  • Hintergrundgeräusche fügen dem gesamten Spektrogramm zwar Energie auf niedrigem Niveau hinzu, erzeugen aber meist nicht die stärksten Peaks in einem bestimmten Bereich
  • Die verbleibenden Landmarken sind die dominanten Frequenzen, die sich gegen das Rauschen durchsetzen
• Dafür schneidet dieses Fingerabdruckverfahren schlechter ab, wenn man ein Lied selbst einsingt
  • Selbst bei sehr gutem Gesang ist die Wahrscheinlichkeit hoch, dass andere Hashes als beim Original entstehen
  • Deshalb verarbeiten neuere Machine-Learning-basierte Systeme Summen und Gesang eher anhand der Melodie als anhand exakter Frequenzen

Punkte verbinden und Hashes bilden

• Ein einzelner Punkt hat zu wenig Unterscheidungskraft, aber die Kombination aus zwei Punkten ist deutlich weniger zufällig und eignet sich daher besser als Fingerprint-Hash
  • Beispielsweise kann ein einzelnes 1.200 Hz zu einem bestimmten Zeitpunkt in tausenden Songs vorkommen, aber die Kombination aus 1.200 Hz und 2.400 Hz nach 0,3 Sekunden ist viel spezifischer
• Der Algorithmus nimmt jeden Peak der Reihe nach als anchor, definiert rechts davon eine target zone mit Zeit- und Frequenzbereich und paart ihn mit allen Peaks darin
  • Aus jedem Paar wird aus den beiden Frequenzen und der Zeitdifferenz — also insgesamt drei Zahlen — ein kurzer Hash gebildet
• Ein Hash funktioniert als kurzer Code, der bei gleichem Input immer dasselbe Ergebnis liefert und schon bei kleinen Änderungen des Inputs einen völlig anderen Wert erzeugt
  • Systeme nach Shazam-Art haben zwar Mechanismen für kleine Abweichungen, grundsätzlich werden die Hashes aber aus exakten Frequenzen und Zeitpunkten gebildet
• Dadurch wirkt dieser Hash weniger wie der Fingerabdruck eines Songs allgemein als vielmehr wie der einer bestimmten Aufnahme
  • Deshalb sind Coverversionen oder Remixe schwerer zu erkennen
• Selbst aus einem einzigen Song von drei Minuten Länge lassen sich tausende solcher Fingerprint-Hashes erzeugen, und die Datenbank speichert sie alle
  • Das Smartphone bringt nur eine kleine Zahl von Hashes aus einem 5-Sekunden-Clip mit, während die Datenbank Millionen von Hashes aus einer gewaltigen Zahl von Songs in den Abgleich einbringt

Das exakte Match finden

• Jeder Hash dient gewissermaßen als Adresse, und das System schlägt für jeden Hash aus dem Clip direkt in einer riesigen Tabelle nach, welche Songs diesen Hash enthalten
  • Statt Songs einzeln zu durchsuchen, wird der Hash selbst als Schlüssel verwendet
• Ein intuitiver song-first-Ansatz müsste jeden Song einzeln prüfen und die Überschneidungen der Hashes vergleichen, was mit wachsender Songzahl immer langsamer wird
  • Im Text wird dies als O(N)-Zeit beschrieben
  • An einer Beispiel-Datenbank und einer Liste von Clip-Hashes wird diese Ineffizienz veranschaulicht
• Computer können das umdrehen und den hash-first-Ansatz verwenden
  • Für jeden Hash wird direkt gefragt: „Welche Songs enthalten diesen Hash?“
  • Das wird mit dem Index am Ende eines Buches verglichen: Statt alle Seiten erneut zu lesen, springt man direkt zum Eintrag eines bestimmten Wortes
• Dieser Ansatz macht den Lookup nahezu O(1)
  • Ob es 100 Songs oder 100 Millionen sind, die Verarbeitung dauert ungefähr ähnlich lang
  • Da die Zahl möglicher Hashes sehr groß ist, liegen selbst bei Millionen Songs meist nur wenige Einträge unter derselben Adresse
• Es reicht jedoch nicht, einfach denselben Hash zu teilen; die letzte Prüfung erfolgt über die Zeitabstände
  • Wenn im Clip etwa 17403C und 19A998 im Abstand von 1,2 Sekunden auftreten, dann müssen dieselben beiden Hashes im Kandidatensong ebenfalls 1,2 Sekunden auseinanderliegen
  • Erst wenn die Zeitdifferenzen der passenden Hashes zusammenpassen und es davon genügend viele gibt, entsteht ein Match mit hoher Zuverlässigkeit
• Das gesamte System ist auf Aufgaben zugeschnitten, die Computer besonders gut beherrschen
  • Im Mittelpunkt stehen Zahlenvergleiche und Adress-Lookups
  • Deshalb lässt sich selbst gegen Millionen Songs die gesamte Suche in deutlich weniger als 1 Sekunde abschließen

Modernere Ansätze

• Viele Song-Erkennungsdienste wie Shazam senden den Audioclip an einen Server und führen das Matching dort gegen eine große Fingerprint-Datenbank durch
  • Diese Architektur wird genutzt, weil die Datenbank sehr groß ist, sich laufend verändert und die Suche erhebliche Rechenressourcen benötigt
• Im Gegensatz dazu laufen Apples On-Device-Erkennung und Googles Now Playing auf Pixel-Geräten vollständig lokal auf dem Smartphone
  • Sie verwenden kleinere, kuratierte Datenbanken und optimierte Modelle
  • Statt vollständiger Abdeckung priorisieren sie Geschwindigkeit und nutzen teils ausgefeiltere Machine-Learning-Ansätze, die robuster gegenüber Rauschen und Audioveränderungen sind
• On-Device-Ansätze sind schneller und funktionieren auch ohne Internetverbindung, haben aber die Einschränkung, dass die Datenbank erkennbarer Songs deutlich kleiner ist
  • Neue Songs werden in der Regel auch langsamer berücksichtigt
  • Wenn ein Standortwechsel erkannt wird, müssen unter Umständen neue Daten nachgeladen werden
• Regionale Unterschiede bei populären Songs beeinflussen ebenfalls die Zusammensetzung solcher On-Device-Datenbanken
  • Hits in Japan können andere sein als Hits in den USA
• Ob das Matching auf dem Server oder direkt auf dem Gerät stattfindet, die Kerntechnik bleibt gleich
  • Wenn der Großteil der Informationen verworfen und nur wenige Landmark-Peaks beibehalten werden, wird selbst ein 5-Sekunden-Clip aus einem lauten Café zu einer präzisen Menge von Koordinaten, die unter Millionen Songs genau einen identifizieren kann
  • Der Kern der Erkennung besteht weniger darin, möglichst viel zu hören, sondern darin, präzise zu verwerfen, was ignoriert werden kann

Zugrunde liegende Arbeit

• Große Teile des Textes basieren auf Avery Wangs Paper von 2003, An Industrial-Strength Audio Search Algorithm
  • Wer tiefer in Signalverarbeitung und Systemdesign einsteigen will, findet dort den direkten Ausgangspunkt
• Der Gesamtprozess verläuft von der Transformation der Wellenform über die Peak-Auswahl, Hashes aus Peak-Paaren, Lookup per invertiertem Index bis zur Prüfung der zeitlichen Ausrichtung
  • Zusammengenommen ermöglichen diese Schritte die schnelle Identifikation eines Songs selbst aus kurzen und verrauschten Clips

[GN⁺]

Hacker-News-Kommentare

• Es lohnt sich, sich zusätzlich das Material zu Shazam anzusehen. Es gibt das Originalpapier: https://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf, und wenn man wirklich interessiert ist, lohnt sich auch der YouTube-Vortrag des Autors. Unter https://news.ycombinator.com/item?id=18069968 gibt es einen Beitrag eines Shazam-Mitarbeiters, unter https://news.ycombinator.com/item?id=38538996 eine vom Mitgründer bestätigte Erklärung, und unter https://news.ycombinator.com/item?id=41127726 eine in Go nachgebaute Version des Algorithmus. Am Ende ist bei ML oft der Wert der Daten größer als der des eigentlichen Codes.

• Meine jüngste Vermutung geht eher dahin, dass das gar nicht unbedingt so sein muss. Bei Popmusik hat es meist gut funktioniert, aber ich habe während der Pausen bei Eiskunstlaufwettbewerben mehrfach ziemlich gute Synth-Musik mit Shazam ausprobiert, und kein einziges Mal wurde etwas korrekt erkannt. Es könnte sein, dass es noch unveröffentlichte Tracks oder extrem nischige Musik waren, aber es sieht auch so aus, als hätte Shazam einfach deutlich versagt.

• Das ist natürlich dieselbe Art von Technik, die auch für ACR bei Fernsehern verwendet wird. Dass Shazam online einen viel besseren Ruf hat, liegt aber wohl daran, dass dort die Absicht und Zustimmung der Nutzer respektiert werden. Wenn man im TV-Bereich etwas Ähnliches umsetzen würde, ohne dass die Daten nur in den Anzeigenverkauf fließen, könnte daraus vielleicht eine Form entstehen, die Verbrauchern tatsächlich nützt.

  • Wenn dieser Nutzen am Ende nur darin besteht, den Titel der gerade laufenden Show oder des Films anzuzeigen, ist das dann nicht ohnehin kaum etwas anderes als die Informationen, die schon beim Drücken der Pausentaste erscheinen?

• Dieser Beitrag ist wahrscheinlich eine der besten visuellen Erklärungen des ursprünglichen Audio-Fingerprinting-Algorithmus aus dem Shazam-Papier von 2003. Allerdings kann ich mir vorstellen, dass man inzwischen irgendwann auf ein ML-Modell umgestiegen ist.

• Es gibt einen Algorithmus namens DTW (dynamic time warping), der oft übersehen wird. Mein Gefühl sagt mir, dass so etwas bei Shazam zumindest in gewissem Maß verwendet wurde.

  • Ich habe früher bei der Verfolgung von Bots auf einer bestimmten Social-Media-Seite DTW eingesetzt. Bots neigen dazu, sich im Schwarm zu verhalten, und DTW eignet sich gut dafür, verzögerte, sich wiederholende Handlungen weich aufeinander abzubilden.

• Dasselbe Recording zu erkennen ist nicht besonders schwierig. Wenn es dieselbe Aufnahme ist, lassen sich Akkordfolge und Timing exakt reproduzieren, und solche Erkennungstechniken gab es schon weit mehr als zehn Jahre. Dagegen ist es viel schwieriger, bei Coverversionen denselben Song über verschiedene Aufnahmen hinweg zu erkennen. Audible Magic behauptet unter https://www.audiblemagic.com/2024/02/07/identifying-cover-songs-live-performances-ai-clones-and-more/, sogar verschiedene Live-Versionen oder Parodien desselben Songs erkennen zu können, was natürlich ein Ansatz mit AI und mehr Rechenaufwand ist.

  • Die Formulierung „nicht schwierig“ lässt sehr viel aus. Auf gesellschaftlicher Ebene wirkt das vielleicht wie eine längst gelöste und einfache Technik, aber wenn man einzelnen Entwicklern sagt, sie sollen ohne Nachschlagen selbst etwas bauen, würden das in der Praxis wohl nicht viele schaffen.
  • Zumindest ist das eine Geschichte, die über 20 Jahre zurückreicht. Ich erinnere mich noch daran, bei einer Beratung für Gracenote gesehen zu haben, wie das dort funktioniert.
  • Sollte man dann nicht einfach die Timing-Informationen entfernen?

• Ich dachte schon: nicht schon wieder dieses Thema, aber dann sah ich, dass es SCP war. Diese Domain wirkt etwas dubios. Eine vollständigere Analyse als der Beitrag von CameronMacLeod aus dem Jahr 2022 ist https://news.ycombinator.com/item?id=38531428, und der Slate-Artikel von 2009 ist https://news.ycombinator.com/item?id=893353.

  • Ich weiß in diesem Kontext nicht genau, wofür SCP steht. An secure copy, woran ich sonst denke, passt hier überhaupt nicht. Trotzdem danke für die Links; die Frage aus dem Titel hat mich schon lange vage interessiert, aber ich habe mich nie ernsthaft damit beschäftigt, also werde ich wohl alle drei lesen.
  • Die interaktiven Elemente dieses Beitrags sind trotzdem ziemlich cool.

• Das sollte ich meiner Projektliste hinzufügen. Das Dinosaur Game, aber so, dass man nicht mit einer Taste springt, sondern mit einem Kikeriki.

• Ich frage mich, ob es eine Möglichkeit gibt, zu verhindern, dass Apps wie Shazam etwas erkennen. Vielleicht durch Beimischen von Rauschen oder mit anderen Methoden.

  • Solange das Rauschen bei bestimmten dominanten Frequenzen nicht lauter ist als das Original, dürfte das schwierig sein. Im Beitrag gibt es auch ein Beispiel dafür: Der Algorithmus behält für schnelle Abfragen im Grunde nur die Frequenzspitzen und verwirft fast alles andere.
  • Produzenten oder DJs lösen dieses Problem normalerweise, indem sie etwas einfach gar nicht veröffentlichen oder erst sehr viel später.

• Ich habe das 1986 auf einem Apple ][c als Wissenschaftsprojekt ausprobiert.