So beginnt typischerweise ein Märchen - und mein Blog - nur das dieser kein Märchen ist und noch weniger das Projekt, um das es sich hier dreht.
Alles begann ende Oktober letzten Jahres mit einem Artikel über Chromium Os und einem Nebensatz der so etwa wie folgt war: "... die Anwendungen sind dabei nicht auf dem Computer sondern im Internet...". Dabei ist mir in den Sinn gekommen, dass es doch toll wäre, wenn ich von überall meine Musik höre könnte ohne, dass ich diese wirklich bei mir haben muss und sogar auf sie zugreifen könnte, wenn ich nicht an meinem eigenen PC sitzen würde. So entstand eine Internetseite die als einzige Aufgabe hatte einen Musik-Player darzustellen die kurz darauf auf den mehr oder weniger guten Namen "My-Musix" getauft wurde.
Da ich das Projekt nicht nur für mich zugänglich machen wollte musste ich mir überlegen wie ich Duplikate vermeiden konnte. Ein Verfahren das auf MD5-Werten, auf Länge oder ID3-Informationen arbeitet schied von vornherein aus - wieso sage ich jetzt aber nicht ;-)
Mein erster Schritt ging dahin, dass ich Wavelab öffnete und mich die Kurve anschaute. Wenn ich mir dann zwei Kurven gleicher Lieder unterschiedlicher Qualität (ich verwendete mp3-codierte Lieder) ansah, war zu sehen, dass diese logischerweise eine sehr hohe Ähnlichkeit aufwiesen.
Mein Schnellschuss war "etwas weniger" performant/praktikabel. Ich erzeugte zwei Bilder gleicher Dimensionen und streckte den durch die Kurve erzeugten Bereich auf diese Größe - anschließend berechnete ich wie weit diese Deckungsgleich zueinander waren. Das war nicht nur Langsam - auch wenn ich die Bilder nicht wirklich zeichnete - sondern war für mich unvorstellbar, wie ich das auf eventuell tausende Lieder anwenden soll oder gar, wie ich das in einer Datenbank darstellen könnte.
Also entschied ich mich dafür, weiter Wavelab anzustarren. Dabei ist mir dann das vorher eher ignorierte Level-&Spectrum-Meter aufgefallen. Die dann folgende Idee auf das Level einzugehen verwarf ich innerhalb weniger Minuten, da leider manche Lieder in unterschiedlicher Lautstärke aufgenommen sind.
Da die Frequenzen in einem Lied aber immer gleich sind, konzentrierte ich mich auf die Frequenzen und wie man diese aus dem PCM-Stream lesen kann.
Fouriertransformation ist hier das Stichwort.
Mein erster Ansatz mit Frequenzen beschränkte sich darauf, die Frequenz mit der maximalen Intensität zu bestimmen. Dies war in einer Datenbank relativ leicht darstellbar hatte aber eine hohe Ungenauigkeit zur Folge. Daher entschloss ich mich jeden betrachteten Moment in Bereiche einzuteilen. Es nach Höhne, Mitten und Bässen
zu unterscheiden macht Sinn. Da sich nach meinem Verständnis der charakteristische Bereich eines Lieds in den Mitten befindet, beschloss ich den Frequenzbereich von etwa 100-3500Hz zu wählen - mit diesem Spektrum decke ich den gesamten Bereich der Mitten, sowie einen Teil der Bässe und Höhen ab. Dieses Spektrum teile ich in vier Bereiche (ursprünglich fünf) ein:
100Hz - 400Hz - 900Hz - 2000Hz - 3500Hz
Daraus folgt, dass ich für mein untersuchtes Lied eine Menge von Untersuchten Teilabschnitten habe und zu diesen jeweils vier Frequenzen.
Diese vier Frequenzen bilden für den gewählten Zeitabschnitt das für mich relevante Merkmal. Da der dritte Frequenzbereich sowohl drei als auch vier Stellen betragen kann, füge ich im Falle von drei Stellen eine führende 0 an
Hier ein kleines Beispiel:
100-400Hz: "187"
400-900Hz: "691"
900-2000Hz: "0982"
2000-3500Hz: "2893"
Zusammengehängt: "18769109822893"
Da es ab jetzt um die Implementierung geht, hier ein kleiner aber wichtiger Hinweis:
Der Methode die die Fouriertransformation durchführt, werden n-Elemente übergeben und gibt n/2-Elemente zurück.
Wenn ich einen Zeitraum von 1/10Sekunde betrachten möchte und die Samplerate des PCM-Streams 44.1 kHz beträgt hätte ich 4410 Elemente zu übergeben. In meinem Fall führe ich eine
FFT durch, die 2^n Elemente erwartet - naheliegend ist hier für n=4096 zu wählen.
Grob gerundet komme ich auf die Bereiche 10-40-85-185-330.
Übersetzt man das eben beschriebene in Java erhält man diese Klasse:
import java.io.File;
import java.io.IOException;
import javax.sound.sampled.AudioFormat;
import javax.sound.sampled.AudioInputStream;
import javax.sound.sampled.AudioSystem;
import javax.sound.sampled.UnsupportedAudioFileException;
import com.mymusix.euphony.symphony.math.FastFourierTransform;
public class Anna{
public final int FFT_AMOUNT = 4096; // Anzahl an Elemente für die FFT (2^n)
private int MAX_LENGTH = 330; // Maximaler Wert der Frequenzbereiches (Entspricht bei FFT_AMOUNT 4096 einer Frequenz von etwa 3500Hz)
private File wavFile;
private long[] result;
/**
*
* @param f muss eine PCM/WAV-Datei sein
* @author kirchrath
*/
public Anna(File f)
{
this.wavFile = f;
this.action();
}
public long[] getResult()
{
return this.result;
}
public String toString()
{
if (this.result == null)
{
return super.toString();
}
else
{
StringBuilder sb = new StringBuilder();
for(long l : this.result)
{
sb.append(l).append("|");
}
return sb.toString();
}
}
private void action()
{
try {
WAVE wavData = this.getWAVEFromFile(wavFile);
byte[] bs = wavData.getBytestream();
byte[] ba = new byte[bs.length];
System.arraycopy(bs, 0, ba, 0, bs.length);
float[] signal = this.preprocessing(ba);
int max = signal.length/FFT_AMOUNT;
long[] hashcodes = new long[max];
int start = 0;
int i = 0;
int c = 0;
// -FFT_AMOUNT da signal noch mindestens so viele Elemente ab aktueller Position beinhalten muss
while(i<signal.length-FFT_AMOUNT)
{
/**
* Datensatz für FFT erzeugen
*/
float[] internal = new float[FFT_AMOUNT];
System.arraycopy(signal, i, internal, start, FFT_AMOUNT);
/**
* FFT Initialisieren und durchführen
* Ich arbeite hier auf float Werte, da komplexe Zahlen in Java
* einen Wrapper benötigen und dies die Geschwindigkeit / den
* Speicher zu stark beinflusst
*/
FastFourierTransform fft = new FastFourierTransform();
FFTR result = new FFTR(fft.fftMag(internal));
// Das Ergebnis dem internen Ergebnisarray hinzugügen und i & c entsprechend erhöhen
hashcodes[c] = result.hash();
i = i + FFT_AMOUNT;
c++;
if(c==max) break;
}
// Dem Klassenergebnis das internet Ergebnisarray zuweisen.
this.result = hashcodes;
} catch (IOException e) {
e.printStackTrace();
} catch (UnsupportedAudioFileException e) {
e.printStackTrace();
}
}
private float[] preprocessing(byte[] bs)
{
/**
* 1. Wandel alle bytes entsprechend in ein float um
* 2. wenn das signal in stereo ist, in mono umwandeln
*/
float[] signal = new float[bs.length / (4)];
int i = 0;
int c = 0;
while(i<signal.length)
{
float[] internal = new float[2];
for(int k=0; k<internal.length; k++)
{
int a = c++;
int b = c++;
byte[] buffer = new byte[]{0,0,bs[b],bs[a]};
internal[k] = this.convertByteArrayToInt(buffer);
internal[k] = (32768 - internal[k])*-1;
if(internal[k]<0)
{
internal[k] = (32768 + internal[k])*-1;
}else
{
internal[k] = (32768 - internal[k]);
}
internal[k] = internal[k] -1;
}
if( (internal[0]<0 && internal[1]>0) || (internal[0]>0 && internal[1]<0))
{
signal[i] = (internal[0] + internal[1]);
}
else
{
signal[i] = (internal[0] + internal[1]) / 2;
}
i++;
}
return signal;
}
/**
*
* @param f PCM/WAV Datei
* @return privates Wrapper-Object
* @throws UnsupportedAudioFileException
* @throws IOException
*/
private WAVE getWAVEFromFile(File f) throws UnsupportedAudioFileException, IOException
{
AudioInputStream aIS = AudioSystem.getAudioInputStream(f);
AudioFormat format = aIS.getFormat();
int x = (int) (aIS.getFrameLength() * format.getFrameSize());
byte[] abs = new byte[x];
aIS.read(abs);
return new WAVE(format, abs);
}
/**
* Methode zum convertieren eines byte-Arrays in einen int
* http://www.tutorials.de/forum/java/228129-konvertierung-von-integer-byte-array.html#post1188505
* @param buffer ein byte-Array der länge 4
* @return
*/
private int convertByteArrayToInt(byte[] buffer) {
if (buffer.length != 4) {
throw new IllegalArgumentException("buffer length must be 4 bytes!");
}
int
value = (0xFF & buffer[0]) << 24 ;
value |= (0xFF & buffer[1]) << 16;
value |= (0xFF & buffer[2]) << 8;
value |= (0xFF & buffer[3]);
return value;
}
/**
* Wrapperklasse für PCM/WAV-Input
* @author kirchrath
*
*/
private class WAVE
{
private AudioFormat af;
private byte[] bytestream;
public WAVE(AudioFormat format, byte[] abs) {
af = format;
bytestream = abs;
}
@SuppressWarnings("unused")
public AudioFormat getAudioformat() {
return af;
}
public byte[] getBytestream() {
return bytestream;
}
}
/**
* FFT-Response Wrapperklasse
* Erzeugt den Wert (hash) zum Untersuchten Abschnitt
* @author kirchrath
*
*/
private class FFTR{
// Auf Welche Zahl soll gerundet werden?
private final int precision = 2;
float[] fftr;
FFTR(float[] fftr)
{
this.fftr = fftr;
}
/**
*
* @return Aktueller Wert aus maxima der bereiche 10-40-85-185-330
*/
public long hash()
{
float[] buffers = new float[4];
long[] fqs = new long[4];
for(int i=0; i<fftr.length && i < MAX_LENGTH; i++)
{
int index;
if (i >= 10)
{
if (i<40)
{
index = 0;
}else if(i<85)
{
index = 1;
}else if(i<185)
{
index = 2;
}else
{
index = 3;
}
if (buffers[index] < fftr[i])
{
buffers[index] = fftr[i];
fqs[index] = i;
}
}
}
long p1 = (fqs[0] - (fqs[0] % precision));
long p2 = (fqs[1] - (fqs[1] % precision));
long p3 = (fqs[2] - (fqs[2] % precision));
long p4 = (fqs[3] - (fqs[3] % precision));
// Konkatenation der einzelen Teilmaxima
return p4 * 10000000 + p3* 10000 + p2 * 100 + p1;
}
}
public static void main(String[] args)
{
File f = new File("./99c8fa7dd27164116a12616ef33f37d7.wav");
Anna a = new Anna(f);
System.out.println(a);
}
}
Lasse ich diese Klasse für zwei Lieder die Codes ausgeben bekomme ich diese (gekürzte) Liste:
2360945212 0000000000
1841144610 0000000000
2561144610 1860924614
2561144610 2400964612
2421144610 1841144610
2941144610 2561144610
3121144610 2561144610
2081144410 2421144610
2081844622 2241144610
2080924622 3121144610
2081844622 2081144622
3001084622 2081844622
3001084622 2081844622
2441084622 3001084622
2441084622 3001084622
2441084622 2441084622
2441084622 2441084622
2081084610 2441084622
2081084610 2441084622
2081084610 2441084610
2081084610 2081844610
2441544610 2081084610
2441544610 2081084610
2181505410 2441084610
3141825418 2441544610
2001825436 2441544610
2001825436 2181825410
2200925418 3141825418
Diese beiden Listen müssen jetzt verglichen werden. Vergleiche ich jetzt einfach immer das linke mit dem rechten Element in einer Zeile, habe ich vier Zeilen in denen der linke und rechte Wert gleich sind. Prozentual sind das etwa 14%. Würde eines der Lieder mit ein paar Sekunden Versatz anfangen (Stille am Anfang), würde die Übereinstimmung um vieles geringer ausfallen. Erzeuge ich an einer Liste einen Versatz, kann sich die Übereinstimmung auch verbessern:
xxxxxxxxxx 0000000000
xxxxxxxxxx 0000000000
xxxxxxxxxx 1860924614
2360945212 2400964612
1841144610 1841144610
2561144610 2561144610
2561144610 2561144610
2421144610 2421144610
2941144610 2241144610
3121144610 3121144610
2081144410 2081144622
2081844622 2081844622
2080924622 2081844622
2081844622 3001084622
3001084622 3001084622
3001084622 2441084622
2441084622 2441084622
2441084622 2441084622
2441084622 2441084622
2441084622 2441084610
2081084610 2081844610
2081084610 2081084610
2081084610 2081084610
2081084610 2441084610
2441544610 2441544610
2441544610 2441544610
2181505410 2181825410
3141825418 3141825418
2001825436 2001825436
2200925418
Beachtet man nur die Zeilen in denen eine Zahl größer 0 steht, habe ich 25 Zeilen in denen 17 gleich sind.
Auf diese Weise verglich ich die Codes der Lieder, bis ich letzten Sommer auf einen
Blog stieß, der genau das gleiche Thema behandelte und eine simple Lösung für dieses Problem zeigte.
Jeder Wert einer Zeile eines Lieds ist mit einem Zeitpunkt verknüpft (Index). Diesen Wert sucht man in den Werten eines anderen Lieds und subtrahiert die Indexwerte. Die Differenzen sind Zählerindizes die entsprechend erhöht werden.
Der Betrag des Zählerindex mit dem größten Wert ist die Trefferquote - dividiert durch die Anzahl der Werte unsere Werteliste bekommt man die prozentuale Übereinstimmung der verglichenen Lieder.
Für gewöhnlich greift man aber nicht auf die Codes eines einzelnen Liedes zu, sondern auf eine Menge von Liedern.
Hier müssen die Codes zusätzlich noch mit einem Lied verknüpft werden und die Zählerindizes abhängig von dem Lied erzeugt werden.
Da die webservicesseitige Implementierung einen Fehler aufweist, gibt es vorerst die ursprüngliche PHP-Implementierung.
$this->fingerprint ist eine Zeichenkette von Codes die mit einem senkrechten Strich miteinander verbunden sind. $this->lenght ist die Länge des Liedes. Dadurch schränke ich die Ergebnisse bereits etwas ein.
$size = (int) round((int) $this->length, -1);
$time = array($size - 20, $size, $size+20);
$hashcodes = explode('|', $this->fingerprint);
$hashcode_count = count($hashcodes);
$sql = 'SELECT songid, time, hashcode FROM mm_music.hashcodes WHERE tracklength IN :length AND hashcode IN :hashcodes';
$query = DB::query(Database::SELECT, $sql, FALSE)->param(':length', $time)->param(':hashcodes', $hashcodes);
$query = $query->execute()->as_array();
$hashtable = array();
foreach($query as $row)
{
$code = $row['hashcode'];
$songid = $row['songid'];
$time = $row['time'];
if ( ! isset( $hashtable[$code] ))
{
$hashtable[$code] = array();
}
$hashtable[$code][] = (object) array
(
'time' => $time,
'song' => $songid
);
}
$songs = array();
for($i = 0; $i<$hashcode_count; $i++)
{
$hash = $hashcodes[$i];
$time = $i;
if (isset($hashtable[$hash]))
{
$elms = $hashtable[$hash];
foreach ($elms as $elm)
{
$timedif = $time - $elm->time;
if ( ! isset($songs[$elm->song]))
{
$songs[$elm->song] = array();
$songs[$elm->song]['timestamps'] = array();
$songs[$elm->song]['max'] = 1;
}
if ( ! isset($songs[$elm->song]['timestamps'][$timedif]))
{
$songs[$elm->song]['timestamps'][$timedif] = 1;
}
else
{
$songs[$elm->song]['timestamps'][$timedif] = $songs[$elm->song]['timestamps'][$timedif] + 1;
if ($songs[$elm->song]['max'] < $songs[$elm->song]['timestamps'][$timedif])
{
$songs[$elm->song]['max'] = $songs[$elm->song]['timestamps'][$timedif];
}
}
}
}
}
$results = array();
foreach ($songs as $key => $value)
{
$precision = $value['max'] / $hashcode_count;
if ($precision > 0.1)
{
$results[$key] = (object) array();
$results[$key]->precision = $precision;
$this->num++;
}
}
uasort($results, function($a, $b){
if ($a->precision == $b->precision) {
return 0;
}
return ($a->precision > $b->precision) ? -1 : 1;
});
// Verkleinere das Array auf die ersten 10 Einträge - mehr sollen dem Benutzer nicht angezeigt werden
if ($this->num > 10)
{
$r_tmp = array();
$c = 0;
foreach($results as $key => $value)
{
if ($c >=10)
{
break;
}
$r_tmp[$key] = $value;
$c++;
}
$results = $r_tmp;
}
In Kürze werde ich die hier vorgestellten Codes auf
Sourceforge veröffentlichen.
