Advice on autocorrelation via FFT

Question

I have been creating an application in Java that transforms an audio signal and writes it to a midi file.

At first I tried using autocorrelation to find the fundamental frequency. However, I have been having difficulties implementing it. I resorted to finding the index of the peaks of the FFT output, finding their consecutive differences and deriving the fundamental frequency from the mode of the differences. This has given me pretty good accuracy. However, for lower notes, it is not working that great.

I was hoping that reviewing it would have helped, but no avail. Following is the output from a sample FFT and autocorrelation.

Questions are:

1. Is the autocorrelation method correct? a) Double the input and pad with zeros. b) Forward FFT. c) Take the absolute square. d) Inverse FFT.
2. Am I looking for the right peak in the graph? I am assuming it should be the first peak.
3. Do the indexes of the autocorrelation graph relate to the frequency just as the indexes of the FFT? (see computeFrequency())
4. Is there any kind of preprocessing that I am missing, etc?
5. Is autocorrelation dependent on multiple harmonics being present?
6. Are there any additional techniques that I can apply to better implement autocorrelation? Or preferred fundamental frequency finding algorithms? (I have looked a little at cepstrum and was having similar problems.)

Thanks for any help received!

This is the output of an FFT. The peak is at index 47. I am positive I have implemented the FFT correctly. Index 47 matches up to E4 with a sampling frequency of 16,384 Hz and a padded FFT length of 1024.

I know, in this case, that, choosing the highest peak will suffice. However, there are FFT's that are not this kind.

Here is the output of the Autocorrelation. The first peak is at index 25 and the second at index 50.

Here is the code for the autocorrelation.

/**
 * complexData is overlapped 50%.
 * @param complexData
 * @return
 */
private Double[] autoCorrelation(final Complex[] complexData) {
    Complex[] toFFT = doubleAndPad(complexData);

    Double[] autoCorrelationAbsolute = new Double[toFFT.length];

    FFT.fftForward(toFFT);

    for(int j = 0; j < toFFT.length; j++) {
        //Same as Complex.mult(toFFT[j], toFFT[j].conjugate()) but simpler
        double square = toFFT[j].absoluteSquare();
        toFFT[j] = new Complex(square);
    }

    //Effective inverse FFT
    //forward FFT == inverse FFT for real numbers.
    FFT.fftForward(toFFT);

    for(int i = 0; i < toFFT.length; i++) {
        autoCorrelationAbsolute[i] = toFFT[i].absolute();
    }
    return autoCorrelationAbsolute;
}

Here is the code for doubling and padding

/**
 * Returns a copy of data with the size doubled and the
 * second half set to zero.
 * @param data
 * @return
 */
private Complex[] doubleAndPad(Complex[] data) {
    Complex[] doubledData = Arrays.copyOf(data, data.length * 2);
    //Set the second half to zero
    for(int i = data.length; i < doubledData.length; i++) {
        doubledData[i] = new Complex(0);
    }
    return doubledData;
}

This is what I use to calculate the frequency.

/**
 * Computes the frequency based off of the padded FFT in autoCorrelation
 * @param bin
 * @param data
 * @return
 */
public static double computeFrequency(int bin, AudioData data) {
    return bin * data.getFormat().getSampleRate() / data.getFftLength();
}

Answer 1

Didn't check the code, but the steps you describe in 1. seems correct.
The units of the autocorrelation are time and not frequency, and it is centred around $\tau = 0$. That means that in your $-1024 \leq\tau< 1023$. So you are looking at the wrong peaks.
Now as you can see the autocorrelation doesn't produce a sharp peak which means that it is not a good measure for your case. In general, the autocorrelation doesn't work well with narrow band signals.

I would suggest you try either the MPM or the YIN methods which are based on the autocorrelation, are extremely simple to implement and from my experience yield goo results.

Answer 2

The autocorrelation function should have positive and negative values and you could find the frequency by averaging the zero crossings over the observation time.

Answer 3

even though the method for computing autocorrelation does not use the FFT, this answer deals a bit with how to not pick the "wrong" peak when the "right" peak is slightly smaller.

also take a look at this paper and look up what this author says about "tapering effect" which affects your autocorrelation results if you use the rectangularly windowed input and the FFT.

Answer 4

It seems like the distance in samples between peaks in your auto correlation output is approx. 25 ? If Fs is 16384 , then the fundamental should be close to 16384/25 = ~655hz.. That's very close to E5 (660hz).. Tbh i don't think autocorrelation using fft is necessary here. A standard autocorellation should work if it's a monophonic input.

Also to answer one of your questions, multiple harmonics are not necessary for to obtain a autocorrelation output that can be analysed for a fundamental