Pitch Detection: avoiding frequency doubling / halving

I am working on a tuning app. I have so far tried 3 different libraries with a number of different algorithms. However, when I compare to other tuner apps, I seem to be getting frequency doubling on certain notes with certain instruments. Sometimes frequency halving depending on other factors. I have tried adjusting the buffer size (size of array of samples) and also the sampling frequency.

Algorithms include: Auto-Correlation, YINFFT, Dynamic Wavelet.

Is there sometimes a need to filter the signal before hitting the algorithm?

• you seem to describe a common problem known as octave errors – ederwander Aug 14 '14 at 12:40

okay, this is answer Part 2. doing it as a separate answer because, as soon as there are LaTeX equations put in, the simultaneous rendering and typing get very slow.

so my questions (1) and (2) were meant to lead you to make a couple of basic conclusions that can help in understanding the source of the Octave Problem and, with such understanding, maybe craft code that can avoid some (maybe not all) of the octave errors.

about (1), the issue is, we hear stuff with our ears and brain (and as such we hear a "pitch" of a tone that is most often associated with the fundamental frequency $f_0$) but the Pitch Detection Algorithm (PDA) is not hearing anything but is doing math and making logical decision that it is programmed to do. so, mathematically, if a tone is judged to be periodic with fundamental frequency of 440 Hz, it is just as well a tone of 220 Hz or 146.67 Hz or 110 Hz or 88 Hz or 55 Hz. it is actually just as periodic with those fundamentals (and the periods associated with those fundamentals) as it is at 440 Hz.

so then, how do we choose which one. since these are all periods that are integer multiples of the same root period (1/440 second), we normally choose the smallest such period that satisfies the conditions of periodicity.

so then, what's the problem? seems like we have a well-defined rule: "choose the smallest value of $T$ that satisfies $x(t) \approx x(t+T)$."

problem 1: satisfying $x(t) \approx x(t+T)$ is the same as satisfying $x(t) - x(t+T) \approx 0$. how do you determine that? because this difference can be either positive or negative, then, to be consistent we try to pick $T$ to minimize something like

$$Q(T) \triangleq \int_{-\infty}^{+\infty} |x(t)-x(t+T)|^p w(t-t_0) \ dt$$

$w(t-t_0)$ is a window function centered at $t_0$ (the portion of the tone of current interest) and $p$ is some power. if $p=1$, then we have the Average Magnitude Difference Function (AMDF) and if $p=2$, we have the Average Squared Difference Function (ASDF), which i prefer for a number of nice mathematical reasons.

so when we say "$x(t) \approx x(t+T)$", we are also saying "$Q(T)$ is small". how small? and how small is necessary to say that $T$ is a potential period? that is a "thresholding problem" (the bane of many a DSP algorithm because of the ungraceful failures that occur when the threshold is not met). now, the way we sometimes get around threshold problems is to use a reasonably loose and inclusive threshold and get lots of pitch candidates (of which only one is the candidate you will ultimately choose). two criteria to pick one candidate over another is (a) which candidate has the shortest period (so we pick $T$ over $2T$) and (b) which candidate has the lowest $Q(T)$? but these two criteria do not always agree. so then which candidate do you choose? that is what IP, patents, and trade secrets are made of so i will go no further with that.

problem 2: this has to do with question (2) of the previous answer. Adamski, you almost got it right, but i would say that "but with a very slightly deeper tone" is off-the-mark. what if the 220 Hz added to the 440 Hz is 80 dB down (instead of 60 dB as i originally posed the question)? no one would hear any difference at all. yet, mathematically, it is a periodic function with period 1/220 second and not quite one of period 1/440 second. if you always choose the mathematically truest and bestest period, a little bit of inaudible sub-harmonic will screw you. so, somehow, you need to bias or prefer period candidates that are shorter over the longer periods that may fit better, mathematically. how to do that is also stuff that secret sauce is made of, so i am going no further with that.

problem 3: jitter or jumping around in pitch selection. usually, when you hear an octave error, it isn't that the pitch of whole note was judged to be an octave off (high or low) but that, while most of the note had the correct pitch assigned, as the note evolves in time (with changing timbre), some small snippet of that note jumps up or down an octave and, if that drives a synthesizer, will sound quite annoying. so, somehow, you need to put in a little hysteresis and make the pitch you select at earlier times be a little "sticky" and preferred, so that when there is suddenly a single frame that concludes that another candidate an octave high or low is the pitch, you can stick with the pitch you already have chosen for earlier frames. a clean way of doing that is also stuff of which commercial solutions are made, so i won't tell you exactly how to do that.

so, even though i didn't spell out a solution (i will if you pay me), i have hopefully pointed you in the right direction for you to figure it out with a little creative thinking.

so Adamski, what you have here is what we call "the Octave Problem" and is well-known and oft discussed with people who work on the pitch detection problem.

first, some definitions. given a quasi-periodic signal, $x(t)$, where

$$x(t) \approx x(t+T)$$

in some local region where $t \approx t_0$, we normally define "pitch", measured in octaves as the base-2 logarithm of the local fundamental frequency, $f_0$, of a note relative to some reference frequency $f_R$. "pitch" is always about an interval, which means it's expressed relative to something.

$$p = p_R + \log_2 \left( \frac{f_0}{f_R} \right)$$

the local fundamental frequency is the reciprocal of the local period

$$f_0 \triangleq \frac{1}{T}$$

so if $p = p_R$ it's because the fundamental frequency $f_0$ is equal to the reference frequency $f_R$. sometimes we use A440 as the reference, most often i use MIDI note 0 as the reference and measure pitch in semitones which are $\frac{1}{12}$ octave. in the MIDI convention, middle C is MIDI note 60 and A440 is MIDI note 69. then the definition of pitch (relative to MIDI note 0) is

\begin{align} p & = 69 + 12 \log_2 \left( \frac{f_0}{440 \text{Hz}} \right) \\ & = 0 + 12 \log_2 \left( \frac{f_0}{8.1758 \text{Hz}} \right) \\ \end{align}

so when $f_0$ = 8.1758 Hz (5 octaves below middle C), the pitch is "0" and when $f_0$ is an octave above that, the pitch is "12".

alright, so the basic issue regarding the octave problem is this:

(1) given that $x(t)$ is fully periodic with period $T$, that is

$$x(t) = x(t+T) \quad \quad \forall t$$

then the same is also true that $x(t)$ is periodic with period $2T$ or $3T$ or any integer multiple of $T$. that is easy to show. the same is nearly true for quasi-periodic $x(t)$, so there are many candidates of possible periods $T$ to choose from, which one do we choose? usually the candidate period $T$ that is smaller than all the other candidate periods is the one we choose. in other words, A440 (A just above middle C) sounds like A440 with period $\frac{1}{440}$ second, but mathematically it is also periodic with period $\frac{2}{440}=\frac{1}{220}$ second, but we don't hear it as A220 (the A just below middle C).

(2) now here's the rub: suppose we add just a teeny bit of a 220 Hz waveform to our A440. but this 220 Hz waveform is, say, 60 dB lower in level than the A440. what are we going to hear and, mathematically, what is the period of this waveform?

so, your assignment for the day is to think about that and, maybe tomorrow i'll come back and tell you maybe one or two "secrets" (they belong to me, so i think i can tell them, but lacking contracting with me to develop an alg for you, i won't be too explicit) about how to deal with this, but you first have to understand the nature of the Octave Problem which you get a hint of by answering for yourself the question in (2).

stay tuned.

• great answer. thank you. will do some thinking and research! my initial thoughts to (2) would be that yes we would still here the note as A440 but with a very slightly deeper tone. – Adamski Aug 14 '14 at 20:33
• okay, back on the air. will try to do Answer part 2 now. – robert bristow-johnson Aug 18 '14 at 15:09

Simply pre-filtering is unlikely to help, unless there is coloring noise with a spectrum disjoint from your pitched signal.

Any autocorrelation based pitch estimator needs to be perceptually weighted to remove additive but inaudible levels of sub-pitch correlation, which can cause sub-pitch estimation errors. What weighting to use falls into the field of experimental human psycho-acoustics. This weighting may also be time dependent, due to pattern matching expectations and masking effects from the immediately preceding audio. There may be academic papers on this topic.

For FFT based pitch estimation of overtone rich sounds, the Harmonic Product Spectrum method looks at multiple potential overtone spacings to find a good pitch hypothesis. One can sometimes also use the overtone spacings to reject other pitch estimate hypothesis, such as pitch multiples due to a harmonic stronger than the fundamental.

You are most likely running up against the fact that some notes that you hear don't include the fundamental frequency. As an example, you play a note at 100Hz. The instrument doesn't actually produce the 100Hz. What it produces is a seris of harmonics (multiples) of the fundamental. So, you measure and find 200Hz as the loudest tone instead 100Hz.

You will need to detect the pitch as you've been doing, but detect harmonics as well and check the distance between harmonics. If they aren't multiples of your measured primary, then your true primary will be the difference between the the detected higher notes.

To stay with the example, you play a 100Hz note and detect 200Hz, 300Hz, and 400Hz. The diffence between the higher notes is 100Hz, which is not the "primary" of 200Hz you thought you had so your true primary is 100Hz.

There's a lot of information on the internet about this kind of thing. Root around and look for information on detecting suppressed fundamentals.

• it shouldn't matter that a note lacks energy at the fundamental frequency $f_0$ as long as it has sufficient energy at enough (more than one) frequencies $n \ f_0$, where $n$ are prime numbers. a pitch detection alg based on finding energy at the fundamental is a "fundamentally" flawed pitch detection alg. – robert bristow-johnson Aug 14 '14 at 14:43
• interestingly the sound that causes the issue is a steel tongue drum that sounds very close to a sine wave if hit softly. in this case it gives me 440hz when it should be 220. – Adamski Aug 14 '14 at 22:45
• Drums can be inharmonic. Does this drum produce any spectral power around 660 or 1100 Hz? – hotpaw2 Aug 16 '14 at 0:42
• @hotpaw2 - not really... it has a lot of dampening, so its sound is actually very close to a decaying sine with some low level upper harmonics. – Adamski Aug 18 '14 at 15:53

Summary autocorrelation works well. This split the signal into several frequency bands, autocorrelates each one and then sums the autocorrelation functions. The peak value of the SACF is the time period of the fundamental frequency.

• I wish it were that, but just find the peak after compute the SACF is not enough to prevent octave errors. – ederwander Aug 14 '14 at 15:01
• @ederwander is correct. the fundamental reason there are octave errors is illustrated in my first answer. i'll get to chapter 2 later this week or weekend. – robert bristow-johnson Aug 14 '14 at 15:32