I try to find about the delay between two audio files using Cross Correlation in Java. I've already done this algorithm so far that i get a idea about how many samples is the delay.

  • FFT x1 -> Zero Padding to length: x1.length() + x2.length()
  • FFT x2 -> Zero Padding to length: x1.length() + x2.length()
  • X3 = FFT{x1} multiply FFT{2}*
  • x3 = IFFT{X3}

To validate my results, i use octave. So i can see that my result is in generally correct, but the position of my graph isn't correct.

For testing i use the same files, so that this represent auto correlation function. In octave graph the maximum correlation is in the center of output vector, which seems to be right. -> so the delay is 0, because same files

Auto Correlation Function Octave In my version, the graph is at the beginning and the end.

Auto Correlation Function Java So if i use two different signals, in octave the maximum correlation moves left/right from center. In my algorithm its going from beginning to middle or end to middle.

So it seems my graph is calculated correct, because the peak moves the amount of samples that is the difference between the files. But the position isnt correct.

It looks like i have to modify my output vector: left half <-> right half

Any ideas whats my problem ?

Edit:

public void execFastCrossCorrelation() throws FFTException
{
    // the used block size is N(x1) + N(x2)
    int blockSize = (x1.length+x2.length-1);

    // create & calc FFT with zero padding & get result

    // FFT x1
    FFT f1 = new FFT(x1, blockSize, 44100);
    f1.execFFT();
    Complex[] c1 = f1.getOutputData();

    // FFT x2
    FFT f2 = new FFT(x2, blockSize, 44100);
    f2.execFFT();
    Complex[] c2 = f2.getOutputData();

    // create output for cross correlation by using fast convolution : c3 = c1 multiply c2*
    Complex[] c3 = new Complex[c1.length];
    for(int i=0; i<c1.length;i++)
    {
        c3[i] = c1[i].multiply(c2[i].conjugate());
    }

    // create & calc IFFT  & get result
    IFFT f3 = new IFFT(c3, c3.length, 44100);
    f3.execIFFT();
    Complex[] corrResult = f3.getOutputData();

// search the maximum corrleation coefficient and his index
    double maxVal = 0;
    int maxIndex = 0;

    for(int i=0; i<corrResult.length;i++)
    {
        if(corrResult[i].abs() > maxVal)
        {
            maxVal = corrResult[i].abs();
            maxIndex = i;
        }
    }

So FFT class is done by using apache-commons-math3. Simply use the input vecotr and create a FFT for the given blockSize (rounded up/down to power of two and zero padded if necessary).

Edit:

So now i tried to flip the output (means left halft -> right half and right half -> left half)

The result matches the version of octave.

Auto Correlation in Java flipped

If i try this with different files, its also working like in octave, means the maximum is moving from the center to left/right. That means that my idea that the output vector has to be "mirrored" seems to be right. Do you have any idea why?

  • 1
    Any code maybe? It's hard to debug it without seeing it. One guess is that maybe java is automatically doing some kind of fftshift operation. – jojek May 13 '14 at 15:21
  • I added some code in my originally post. – christopo May 13 '14 at 15:30
  • I added another picture with the flipped output array. – christopo May 13 '14 at 15:56
  • Like I said above, most probably this function is automatically shifting FFT. Can you post the magnitude spectrum of some known signal for both octave and your program? Simple abs of FFT. If it is shifted then you have your answer. – jojek May 13 '14 at 16:01
  • I believe that error might be in your class FFT - presume that's not the original one coming from apache-commons-math3. – jojek May 13 '14 at 18:40

A real (non-complex) time-domain input will always give a FFT that is duplicated (mirrored)

Some implementations will perform a shift to put the DC (frequency=0Hz) term at index 0. Otherwise you will find the DC term halfway through the array.

  • Sorry, why the downvote? The graphs look centred except for extra whitespace at the end. – Andrew Gallasch Feb 27 '15 at 14:53

FFT by default puts negative frequncies after positive frequencies. It happens due to properties of FFT. You may google Cooley-Tukye algorithm and learn about butterfly operation for more details. Seems, one of your library performs automatic shift of output samples, while the other does not. Check library documentation for this information.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.