How to get the fundamental frequency using Harmonic Product Spectrum?

Question

I'm trying to get the pitch from the microphone input. First I have decomposed the signal from time domain to frequency domain through FFT. I have applied Hamming window to the signal before performing FFT. Then I get the complex results of FFT. Then I passed the results to Harmonic product spectrum, where the results get downsampled and then multiplied the downsampled peaks and gave a value as a complex number. Then what should I do to get the fundamental frequency?

    public float[] HarmonicProductSpectrum(Complex[] data)
    {
        Complex[] hps2 = Downsample(data, 2);
        Complex[] hps3 = Downsample(data, 3);
        Complex[] hps4 = Downsample(data, 4);
        Complex[] hps5 = Downsample(data, 5);
        float[] array = new float[hps5.Length];

        for (int i = 0; i < array.Length; i++)
        {
            checked
            {
                array[i] = data[i].X * hps2[i].X * hps3[i].X * hps4[i].X * hps5[i].X;
            }
        }
        return array;
    }

    public Complex[] Downsample(Complex[] data, int n)
    {
        Complex[] array = new Complex[Convert.ToInt32(Math.Ceiling(data.Length * 1.0 / n))];
        for (int i = 0; i < array.Length; i++)
        {
            array[i].X = data[i * n].X;
        }
        return array;
    } 

I have tried to get the magnitude using,

    magnitude[i] = (float)Math.Sqrt(array[i] * array[i] + (data[i].Y * data[i].Y));  

inside the for loop in HarmonicProductSpectrum method. Then tried to get the maximum bin using,

        float max_mag = float.MinValue;
        float max_index = -1;

        for (int i = 0; i < array.Length / 2; i++)
            if (magnitude[i] > max_mag)
            {
                max_mag = magnitude[i];
                max_index = i;
            }

and then I tried to get the frequency using,

    var frequency = max_index * 44100 / 1024;

But I was getting garbage values like 1248.926, 1205,859, 2454.785 for the A4 note (440 Hz) and those values don't look like harmonics of A4.

A help would be greatly appreciated.

Answer 1

To get a pitch estimate, you have to divide your sumed bin frequency estimate by the downsampling ratio used for that sum.

Added: You should also sum the magnitudes (abs()), not take the magnitude of the complex sum.

But the harmonic product spectrum algorithm (HPS), especially when using only integer ratios of downsampling, doesn't usually provide better pitch estimation resolution. Instead, it provides a more robust rough pitch estimate (less likely to be fooled by a harmonic) than using a single bare FFT magnitude peak for sequential overtone rich timbres that have weak or missing fundamental spectral content.

If you know how to downsample a spectrum by fractional ratios (using interpolation, etc.), you can try finer grained downsampling to get a better pitch estimate out of HPS. Or you can use an HPS result to inform you of a narrower frequency range in which to search using another pitch or frequency estimation method.

Answer 2

I implemented harmonic product spectrum in Python to make sure your data and algorithm were working nicely.

Here’s what I see when applying harmonic product spectrum to the full dataset, Hamming-windowed, with 5 downsample–multiply stages:

This is just the bottom kilohertz, but the spectrum is pretty much dead above 1 KHz.

If I chunk up the long audio clip into 8192-sample chunks (with 4096-sample 50% overlap) and Hamming-window each chunk and run HPS on it, this is the matrix of HPS. This is kind of a movie of the HPS spectrum over the entire dataset. The fundamental frequency seems to be quite stable.

The full source code is here—there’s a lot of code that helps chunk the data and visualize the output of HPS running on the chunks, but the core HPS function, starting at def hps(…, is short. But it has a couple of tricks in it.

Given the strange frequencies that you’re finding the peak at, it could be that you’re operating on the full spectrum, from 0 to 44.1 KHz? You want to only keep the “positive” frequencies, i.e., from 0 to 22.05 KHz, and apply the HPS algorithm (downsample–multiply) on that.

But assuming you start out with a positive-frequency-only spectrum, take its magnitude properly, it looks like you should get reasonable results. Try to save out the output of your HarmonicProductSpectrum to see if it’s anything like the above.

Again, the full source code is at https://gist.github.com/fasiha/957035272009eb1c9eb370936a6af2eb. (There I try out another couple of spectral estimator, Welch’s method from Scipy and my port of the Blackman-Tukey spectral estimator. I’m not sure if you are set on implementing HPS or if you would consider other pitch estimators, so I’m leaving the Welch/Blackman-Tukey results there.)

---

Original I wrote this as a comment but had to keep revising it because it was confusing so here’s it as a mini-answer.

Based on my brief reading of this intro to HPS, I don’t think you’re taking the magnitudes correctly after you find the four decimated responses.

You want:

array[i] = sqrt(data[i] * Complex.conjugate(data[i]) *
                hps2[i] * Complex.conjugate(hps2[i]) *
                hps3[i] * Complex.conjugate(hps3[i]) *
                hps4[i] * Complex.conjugate(hps4[i]) *
                hps5[i] * Complex.conjugate(hps5[i])).X;

This uses the sqrt(x * Complex.conjugate(x)) trick to find x’s magnitude, and then multiplies all 5 magnitudes.

(Actually, it moves the sqrt outside the product, so you only do one sqrt, saves some time, but gives the same result. So maybe that’s another trick.)

Final trick: it takes that result’s real part because sometimes due to float accuracy issues, a tiny imaginary component, like 1e-15, survives.

After you do this, array should contain just real floats, and you can apply the max-bin-finding.

---

If there’s no Conjugate method, then the old-fashioned way should work:

public float mag2(Complex c) { return c.X * c.X + c.Y * c.Y; }

// in HarmonicProductSpectrum 
array[i] = sqrt(mag2(data[i]) * mag2(hps2[i]) * mag2(hps3[i]) * mag2(hps4[i]) * mag2(hps5[i]));

There’s algebraic flaws with the two approaches you suggested in the comments below, but the above should be correct. I’m not sure what C# does when you assign a Complex to a float—maybe it uses the real component? I’d have thought that’d be a compiler error, but with the above code, you’re doing the right thing with the complex data, and only assigning a float to array[i].