Grundsätzliche Funktionsweise von Musikerkennungssoftware

[Schneider-Huetter]

Danke, hatte das gleiche gestern auch noch entdeckt : Informationsdienst Wissenschaft

Die "spektrale Flachheit" dürfte so wie ich das verstehe einfach eine statistische Auswertung der von der FFT erzeugten Spektren sein ( Standardabweichung... ).
Das erzeugte Spektrum teilt man ca. alle 10ms in mehrere Bänder auf, berechnet jeweils die "spektrale Flachheit" und legt diese in der Datenbank ab.

3 min = 180s
180s / 0,01s = 18000
18000 Samples * 16 Bänder * 8 Byte (Double) = 2250 kByte

Wenn man es so machen würde hätte man einen Fingerabdruck mit knapp 2,2 MByte je Durchschnitts-Popsong , beim Fraunhofer-Institut wird aber von 2-4 kByte / min gesprochen.
Es scheint, ich habe da irgendeinen Denkfehler begangen. Oder wird die Flachheit über die ganze Songlänge berechnet, dann müsste man aber wieder den ganzen Song aufnehmen - kann also auch nicht sein!

[Tonic1024]

wenn du eine eindeutige erkennung des Titels innerhalb weniger Takte erkennen kannst, brauchst du auch nur die Takte, die charakteristisch sind für diesen titel. Ausserdem ist es eine Art Statistik - so wie ich es verstanden habe - so dass du tatsächlich nur den mittleren Wert ermitteln musst.

Wie Hagen schon sagte, Wenn du genau einen festen Wert suchst musst du auch genau einen Start und Endpunkt festlegen. Das geht aber schon nicht, weil ein Titel nicht immer gleich lang ist. (Single, Album-Version, Sowiso-Mix, Datensalat aus irgendeiner Tauschbörse). Aus diesem Grund darf es nur einen annäherungswert geben, der aber immernoch eindeutig genug sein muss, um einen Titel noch zu identifizieren. Dies wird wohl über die Frequenzbänder realisiert. Für jedes Frequenzband wird eine Zahl zwischen 0 und 1 ermittelt. Wenn ein Titel in - sagen wir mal - 4 Frequenzbändern gleiche Werte hat, ist es sehr wahrscheinlich, das dies der gesuchte Titel ist. steigt die Zahl der übereinstimmungen, steigt die Wahrscheinlichkeit.

Mathematische Grundlagen kann ich dir leider nicht liefern. Nur zur FFT hab ich was gefunden.

FFT-Mathematisch und Code (Java)


[EDIT]Wenn du Stücke von 0,01s länge verwendest (woher stammt denn die Zahl?) wirst du kaum die Charakteristik einer Melodie/eines Rythmuses erkennen können, oder [/EDIT]

MfG

Tonic

[Schneider-Huetter]

Zitat:

Für jedes Frequenzband wird eine Zahl zwischen 0 und 1 ermittelt. Wenn ein Titel in - sagen wir mal - 4 Frequenzbändern gleiche Werte hat, ist es sehr wahrscheinlich, das dies der gesuchte Titel ist. steigt die Zahl der übereinstimmungen, steigt die Wahrscheinlichkeit.

Das ist mir prinzipiell klar, nur komme ich dann eben wie oben erläutert zu einem "riesigen" Fingerabdruck und bei tausenden Titeln wird es schwierig so große Datenmengen innerhalb des Abtastintervalls zu durchsuchen.

Zitat:

Wenn du Stücke von 0,01s länge verwendest (woher stammt denn die Zahl?) wirst du kaum die Charakteristik einer Melodie/eines Rythmuses erkennen können, oder

Die Zahl habe ich daher, dass man sagt, dass der Mensch eine Latenz ( z.B. bei einem Synthesizer, Midi-Keyboard an Soundkarte... ) von <= 10ms nicht mehr Wahrnimmt. Also habe ich mir überlegt, dass sich auch die wesentlichen Merkmale eines Songs ( Frequenz, Rhythmik... ) in diesem Zeitraum zumindest nicht signifikant verändern können. Also eigentlich hab ich keine Ahnung, ob 10ms ein guter Wert ist , aber wenn man noch kleinere Intervalle verwendet wird der Abdruck ja noch größer.

[Robert Marquardt]

Da werden vermutlich sehr viel laengere Abschnitte verwendet. Eher 100 ms oder mehr statt 10 ms.
Es werden offensichtlich 16 Floating-Point Werte berechnet, die den Fingerabdruck dieses Abschnitss bestimmen.
Wenn man jetzt noch mit ein paar Ueberlappungen rechnet, dann sollte man nicht mehr als 1 bis 2 KByte an Daten zur Suche erhalten.

Es wundert mich nicht das das ausreicht. Ein Gesicht kann man auch erkennbar in 32x32 Pixeln ablegen.

[Schneider-Huetter]

Ich habe im Delphi-Forum ein Musikerkennungsprogramm entdeckt, werde dort auch mal nachfragen, wie die Fingerabdrücke bei diesem Programm aufgebaut sind.

[Tonic1024]

Okay... Aber wenn du einen Titel hast mit 120 BPM (normale Geschwindigkeit, RMB und Black Musik ist viel langsamer) dann sind das 2 Schläge pro Sekunde, richtig?

Um also die Geschwindigkeit deines Titels abschätzen zu können brauchst du mindestens 2 Schläge. Das würde ich als unteres Limit der Grundlage deiner Berechnung annehmen um überhaupt ein (nicht unwichtiges) Kriterium ermitteln zu können.

Dazu, glaube ich, hast du zwei Fehler in deinem Denkansatz. Warum zerteilst du die Songs in so kleine Stücke, bis sie quasi beliebig austauschbar sind? Es geht doch darum einen Wiedererkennungswert in dem Titel zu kategorisieren. Das markanteste an einem Titel sind doch die Melodie und der Rhythmus. Eine Melodie ist minimal 16 Takte lang - eher 32 oder noch mehr. (Bin Hobby-Produzent, daher kenne ich das) beim 4/4 Takt (angenommen 120 BPM) sind 4 Schläge a 0,5 sek ein Takt. 16 Takte entspricht 8 Sekunden - das wäre schon eher eintönig anzuhören, aber wohl genug um einen gewissen Wiedererkennungswert (für Menschen) zu beinhalten.

Die Schlagworte "Query by Humming" sollten dich auf eine Art "Reverse Engeneering" bei Musik bringen, in der das so angewendet wird. Du hast quasi die Noten deines Titels im Klartext. Wenn du weisst wie MIDI-Files aufgebaut sind, weisst du auch wieviel Musik auf kleinstem Raum Platz hat (in KB gerechnet)

Dein Zweiter Fehler (meiner Meinung nach) liegt darin von 3 Min auszugehen. Du brauchst eigentlich nur eine makante Stelle von dem Titel - nicht den ganzen Titel. Der Titel wird innerhalb von 10 sekunden erkannt stand irgendwo. Das bedeutet zwar nicht, das die ersten 10 Sekunden deines Titels ausreichen. Ich denke da an Bolero zum Beispiel. Der würde in den ersten 10 Sekunden wohl nur Nullen produzieren (auch irgendwie Markant, oder? ). Aber du brauchst sicherlich nicht den ganzen Titel. Dazu musst du wissen, dass ein Titel - das kannst du auch im Radio nachvollziehen - aus nur 3-4 Sequenzen besteht. Intro und Outro - klar... Dann den Hauptteil mit wiederkehrendem Refrain und ggf. einen "Ruhigen Part" (oder ein Gitarrensolo, etc), der im oder am Ende des Hauptteils vor dem Outro kommt.

also hat ein Titel von 3 min länge 2 min "Inhalt", der sich die meisste Zeit wiederholt (die Melodie des Textes ist ja i.d.R. gleich, und der Refrain sowiso). Darin besteht die Charakteristik eines Songs. Ich denke dort hätte ich versucht den Ansatz für so eine Fingerabdruck-Software zu suchen.

Lange Rede - garkein Sinn... Mit diesen Grundlagen solltest du sicherlich eine ganz andere Größe berechnet bekommen...


[Edit]

Zitat von Robert Marquardt:

Es wundert mich nicht das das ausreicht. Ein Gesicht kann man auch erkennbar in 32x32 Pixeln ablegen.

Schönes Beispiel
[/Edit]

[Schneider-Huetter]

Zitat:

Du brauchst eigentlich nur eine makante Stelle von dem Titel - nicht den ganzen Titel

Klingt eigentlich vernünftig, ich sehe da aber 2 Probleme:

1. ist es wahrscheinlich nicht so einfach diese markanten Stellen mit einem Programm herauszufinden. Da wäre wohl eine ziemlich ausgeklügelte Ähnlichkeitserkennung notwendig (um z.B den Refrain zu erkennen).

2. was ist, wenn man nur nuch den Schluss eines Titels hört und trotzdem gerne den Titel wüsste. Ich denke, dass auch bei wenig markanten Stellen eine sichere Erkennung möglich ist ( siehe das Programm aus dem Delphi-Forum )

Zitat:

Warum zerteilst du die Songs in so kleine Stücke, bis sie quasi beliebig austauschbar sind?

Da hast du wahrscheinlich recht, 10ms sind wohl "etwas" zu kurz!

[Tonic1024]

Markant ist unter Anderem (oder vor allem) der Rhythmus. Der Zieht sich durch den ganzen Titel auch die melodie zieht sich in offensichtlicher Form oder Hintergründig (z.B. als Baseline) durch den ganzen Titel. Und grade darum macht es mehr als nur Sinn die unterschiedlichen Frequenzbereiche einzeln zu betrachetn.

Kennst du das Gefühl, dass dich ein Musiktitel mehr anspricht als ein Anderer, oder dass zwei völlig unterschiedliche Titel dir irgendwie gleichermaßen in die Beine gehen? Dafür sind u.A. Rhythmusfolgen und Frequenzen verantwortlich, die eher unterschwellig zu dir gelangen. Es würde jetzt zu Weit führen das hier auszubreiten. Aber diese Tatsache machen sich Produzenten zu Nutze um immer die gleiche Zielgruppe wieder aufs Neue zu gewinnen. ABBA klingt eben wie ABBA und alls was so ähnlich klingt, klingt wie ABBA und nicht wie was Eigenes. *schwafel*

Wie dem auch sei, sowas kann man messen. Und den Refrain (oder einen X-beliebigen anderen markanten Teil eines Songs) kann man relativ leicht identifizieren. Nichts anderes wird gemacht bei manchen komprimierungsverfahren. Tritt eine Sequenz mehrfach auf ist die Information darin redundant und ein Verweis, dass an der Stelle wieder der Teil "von vorhin" kommt, reicht aus. Um wieder den Weg in die Informatik zu lenken: Wenn du an Drei Stellen ein Objekt benötigst reicht ein Objekt und drei Pointer darauf. Diverse Komprimierungsverfahren arbeiten nach diesem Prinzip.

Mit markantem Teil muss ja nicht ein Teil gemeint sein, den der Mensch als markant empfindet, sondern eine sich ständig wiederholende Sequenz. Was ich also sagen will: Auch wenn du es nicht hörst (oder nur unterbewusst siehe mein 2. Absatz) ist es trotzdem da. Und dieser Umstand reicht aus um es zu errechnen und abzulegen zu können.

Nehmen wir als Beispiel ein Techno-Stück und betrachten wir nur den unteren Frequenzbereich. Was sehen wir? Wir sehen ein rhytmisches Pulsieren im Abstand von exakt 0,46784 Sekunden Da dieser Impuls eine Bandbreite von meinetwegen 200Hz (oder was auch immer) hat ermitteln wir ihn auch in zwei Weiteren von unseren 16 Frequenzbereichen Der Impuls selbst besteht aus weiteren Frequenzen. Einmal aus einer niedrigen Trägerfrequenz (das dumpfe Bummern, dass wir hören) und aufmodulierten "Klangfrequenzen". Schliesslich klingt die Basedrum von Queen nicht wie die von Scooter oder eben ABBA, auch wenn sie vielleicht alle die gleiche Trägerfrequenz haben. Wir haben also allerhand Anhaltspunkte, die wir in irgendeiner Form mathematisch aufarbeiten können. Wenn wir das für alle 16 Frequenzbänder tun, bekommt man schon ein recht aussagekräftiges Bild würde ich mal sagen.

Ich rede zuviel...

Ich hoffe der Umstand ist klar geworden.

BTW: Ich sage nicht, dass AudioID es so macht.

Nochwas: Auch so eine Software wird natürlich ihre Grenzen haben. 10 Sekunden Stille bei Bolero - um das noch einmal aufzugreifen - werden relativ ähnliche Werte bringen wie 10s Stille in einem Klassik-Stück. Ist jetzt ein überzogenes Beispiel, sicher. Aber ich denke es wird klar was ich meine.

MfG

Tonic

[negaH]

Oben hatte ich's schon angesprochen, allerdings kam das wohl nicht so exakt rüber.

Das Ziel ist es einen inhaltlich korrekten Fingerabdruck eines Songs zu bekommen. Dieser sollte natürlich kurz sein. Man könnte jetzt eine FFT über den gesammten Songs durchführen, nur würde das fast nichts bringen. Eine solche FFT würden den kompletten Song so betrachten als würde er zeitlich gesehen mit einem einzigsten Male abgespielt werden. Viele, sehr veschiedene Songs, würden also immer ähnliche FFT Spektren erzeugen das es keinen zeitlichen Bezug des Spektrums zum Song mehr gibt.

Deshalb meinte ich oben das man eine "3D" FFT durchführt. Man erzeugt in einem zeitlichen Raster also mehrere FFT's nacheinander. Jede dieser FFT's wird zb. auf nur 16 Frequenzbänder limitiert. Angenommen wir benutzen ein Raster von 1 Sekunde, so ergibt sich also pro Sekunde eine FFT mit 16 Realwerten. Nach 3 Minuten haben wir 16 zeitliche Frequenzbänder mit jeweils 180 Realwerten, macht 180*16 insgesammt. Nun werden diese 16 Frequenzbänder nochmals normalisiert indem man 16 DFT's, also diskrete Fourier Transformationen auf diese anwendet. Angenommen diese DFT's erzeugen aus den Bändern wiederum 16 Bänder, so ergibt das am Ende 16*16 = 256 Realwerte als Fingerabdruck. Der Vorteil bei den "horizontalen" DFT's ist das sie mit Inputdaten beliebiger Länge auf Outputdaten mit fest vorgegebener Länge arbeiten können. Das bedeutet das die "vertikalen" Frequenzband-schnitte, die ja abhängig von der Songdauer sind denoch mit den abschließenden DFT's auf eine normierte Große gemappt werden können.

Also nochmal zur Verdeutlichung:
Man zerlegt die Songs in Zeitscheiben von immer gleicher Länge und erzeugt von diesen Happen "vertikale" FFT's. Jede dieser FFT's produziert sehr wenige Frequenzspektren, zb. 16. Man hat am Ende des Songs also 16 Frequenz-spektren-spuren die nun jeweils für sich gesehen einer DFT unterworfen werden. Diese DFT erzeugt sozusagen ein Frequenzspektrum über den zeitlichen Verlauf eines Frequenzspektrums in einem Song. Im Grunde kann man so errechnen in welcher Frequenz der Takt eines Songes verläuft, sprich man ermittelt den Beat, das Spektrum verschiedener Stimmen, die Benutzung klangtypischer Instrumente usw. usw.

Wir haben nun ein 16*16 Array of Double das einen Song normalisiert und komplett beschreibt. Man erzeugt nun eine Datenbank die diese Daten als "Baumstruktur" sortiert enthalten. Nun ist es einfach mit der Suche. Man erzeugt den Fingerabdruck des aktuellen Songs. Sucht den ersten Eintrag des Fingerabdruckes -> array[0], und selektiert den Knoten der Wertmäßig am nächsten kommt. Nun geht man eine Ebene im Baum tiefer und sucht dort den Wertmäßig passenden Eintrag zum array[1] Wert, usw. usw. Dabei wird immer überprüft das dieser Vergleich keine zu starken Differenzen bildet, d.h. der Song auch wirklich in der Datenbank steht. Am ende hat man im besten Falle mit 256 Vergleichen den Song in der Datenbank gefunden.

So würde ich das Problem angehen.

Gruß Hagen

[Robert Marquardt]

Man sollte sich das Ziel vor Augen halten.
Man will erst mal nur veroeffentlichte Musikstuecke anhand eines Ausschnittes minderer Qualitaet wiedererkennen.
Ich wuerde vermuten das man einfach wie bei MP3 eine Kompression/Datenreduktion macht. Das Ziel ist die Wiedererkennung, man kann also extrem viel Information weglassen.
Man erhaelt fuer den Ausschnitt des Musikstuecks einen recht kurzen String den man nun nur in der Datenbank aller Musikstuecke (in reduzierter Form) wiederfinden muss.
Dafuer gibt es aber Standardprodukte.