Korrelation v. Audio Signalen mittels schnelle Faltung - FFT

[Christoph P. (christopo)]

Hallo zusammen,

ich möchte die Korrelation von zwei Audio-Signalen bestimmen, um mir die 
Zeitverschiebung zu ermitteln. Ich realisiere das ganze in Java. An sich 
funktioniert das schon ganz gut.

Ich habe bisher folgendes:

x1 mit Länge N1
x2 mit Länge N2

- FFT{x1} mit Zero Padding -> Länge: N1+N2-1
- FFT{x2} mit Zero Padding -> Länge: N1+N2-1
- X3 = FFT{x1} * konj. Komplex FFT {x2}
- IFFT{X3}

Danach suche ich den Index mit dem höchsten Korr. Koeffizienten und 
erhalte somit den Ort der maximalen Korrelation. Das funktioniert prima 
und ist auch stimmig.

Bspw. wenn ich eine Verzögerung von 1000 Samples einbaue, verschiebt 
sich die max. Korrelation um 1000.

Nun habe ich das ganze mit Octave überprüft und dort die Funktion 
xcorr() genutzt. Als Eingangswerte habe ich zwei mal den gleichen Vektor 
genommen, somit entspricht das der Autokorrelationsfunktion.
Bei Octave ist der maximale Korrelations-Koeffizient zentriet im 
Mittelpunkt des Ausgangsvektors (entspricht ja auch der Logik der 
Korrelation). Hingegen wenn ich dies mit meiner Realisierung probiere, 
erhalte ich ein Maximum zu beginn und zu ende des Ausgansvektors.

Dieses Problem habe ich auch wenn ich unterschiedliche Signale benutze. 
In Octave wandert das Maximum von der Mitte ausgesehen nach Links oder 
Rechts. Bei meiner Realisierung wandern die Maxima je nach dem von 
Anfang nach rechts oder vom Ende nach links.

Was mache ich falsch?

PS: Für mich sieht es so aus, als ob ich die linke Hälfte nach rechts 
schieben müsste, und die rechte hälfte nach links. Aber wieso?!

[vorticon (Gast)]

hae, warum machst du FFT? einfach xcorr(x1,x2) bestimmen und index des 
maximalen wertes suchen.

[Christoph P. (christopo)]

Der Code ist in Java und nicht in MatLab/Octave.

PS: ich habe mittlerweile herausgefunden das ich meine 
Korrelationsfunktion vertikal spiegeln muss, dann erhalte ich unter 
allen möglichen Eingaben immer ein korrektes Ergebnis. Kann mir jemand 
sagen, woran dies liegen könnte?

Mit spiegeln meine ich in dem Fall, linke Hälfte nach rechts verschieben 
und umgekehrt.

[Andreas S. (andreas) (Admin)]

Im Ergebnis der Funktion xcorr ist der Wert für die Zeitverzögerung 0 
genau in der Mitte des Vektors. Siehe 
http://www.mathworks.de/de/help/signal/ref/xcorr.html → "The output 
vector c has elements given by:".

[Operator S. (smkr)]

Das liegt am beobachteten Spektrum. Da sich dieses alle N wiederholt, 
ist es ansichtsache, was "richtig" ist.
Mir gefällt es meist so, wie es im Bild des Java ouputs ist, da bei 0 
die Leistung des Signals zu sehen ist (bei einer autokorr)

Ich habe auf die Schnelle kein besseres Bild gefunden, aber um es zu 
verdeutlichen: 
http://www.maximintegrated.com/images/appnotes/3716/3716Fig03.gif

Bei octave hast du Zone 3&4 während es bei Java Zone 2&3 ist. Wobei 
gilt: Zone 2 = Zone 4

[Andreas S. (andreas) (Admin)]

Da verwechselst du was! Hier geht es um die Korrelationsfunktion, nicht 
um das Spektrum.

[Operator S. (smkr)]

Christoph Pi schrieb:
> PS: ich habe mittlerweile herausgefunden das ich meine
> Korrelationsfunktion vertikal spiegeln muss, dann erhalte ich unter
> allen möglichen Eingaben immer ein korrektes Ergebnis. Kann mir jemand
> sagen, woran dies liegen könnte?

Ich bezog mich auf diese Frage und versuchte es anhand den Bildern 
darzustellen, weshalb beide Funktionen dasselbe sind, nur in anderer 
Darstellung.


Bei octave wird die akf folgendermassen berechnet: Es gilt immer das 
Produkt zwischen den Vektoren in vertikaler Richtung und anschliessender 
Summenbildung.

Sample 1:
[0 1 2 3 4 5]
          [0 1 2 3 4 5]
Sample 2:
  [0 1 2 3 4 5]
          [0 1 2 3 4 5]
Sample 3:
      [0 1 2 3 4 5]
          [0 1 2 3 4 5]
usw.
bis zum letzen Sample:
                    [0 1 2 3 4 5]
          [0 1 2 3 4 5]

Bei Java fängt Sample 1 so an:
[0 1 2 3 4 5]
[0 1 2 3 4 5]

  [0 1 2 3 4 5]
[0 1 2 3 4 5]

    [0 1 2 3 4 5]
[0 1 2 3 4 5]

usw. bis

          [0 1 2 3 4 5]
[0 1 2 3 4 5]

und dann
          [0 1 2 3 4 5]
  [0 1 2 3 4 5]

usw. bis

          [0 1 2 3 4 5]
          [0 1 2 3 4 5]

Rechne es dir so mal aus, kannst auch alles einsen einsetzen, dann musst 
du nur noch summieren ;-) Die akf sollte dann übrigens eine Dreieckform 
bekommen, da der Input ein Rechteck war.

[Christoph P. (christopo)]

Servus,

also das Octave das so berechnet, habe ich vermutet. Das entspricht ja 
auch der Korrelationsfunktion im Zeitbereich (laut Rechenvorschrift). Im 
übrigen habe ich diese auch schon nachgebaut, leider hat mir das zu 
lange gedauert, daher bin ich den Frequenzbereich gewechselt. Das 
Ergebnis der Berechnung im Zeitbereich war aber das gleiche wie bei 
Octave - also Signal 2 in Signal 1 von links beginnend nacheinander 
"eingeschoben".

Eine Frage, woher weisst du das "Java" es so macht? Ich benutzt die 
Apache-commons-math3 lib für die FFT/IFFT.

Ich dachte eben, das ich durch die Multiplikation der Spektren, bzw. des 
konj. komplexen Spektrums die Korrelation erhalte, die analog der 
Berechnung im Zeitbereich ist.

Liegt die Verschiebung nun an den Eigenarten der FFT/IFFT von der 
genutzten lib oder ist es prinzipiell so?