Hello,

This post is related to and inspired by elden's topic on pitch and formant shifting

http://puredata.hurleur.com/sujet-6614-upsampling-audio-signals-using-automatable-sampling-frequency

but I do not want to clutter that thread too much with my experiment results so therefore started this new thread on pitch tracking, a subtopic of time domain pitch shifting.

ACF (autocorrelation function) and SDF (squared difference function) are used a lot in time domain pitch tracking or fundamental period identification. In Pd, I was trying how autocorrelation looks like. I also constructed another function, of which I don't even know if it has a name. For the moment, I'll call it IPPASS: 'instantaneous power of phase aligned signal segment'. It can be considered a modification or extension of autocorrelation. It seems to me that IPPASS might be useful in pitch detection, as it can much better indicate periodicity in case of missing fundamental. However, I'm not yet sure how to make it work in practical implementation, if it is possible at all.

In attached patch IPPASS02.pd, ACF and IPPASS functions are plotted for a synthesized test signal with variable harmonic recipe. The concept of period detection with ACF is, to make harmonics line up so together they peak at the fundamental interval. In addition to that, IPPASS employs periodic amplitude modulations in the signal.

By no means these functions are rock solid true/false indicators. The 'art of peak picking' is another aspect of pitch tracking. Read Philip McLeod and Geoff Wyvill on ACF, SDF and the art of peak picking:

http://miracle.otago.ac.nz/tartini/papers/A_Smarter_Way_to_Find_Pitch.pdf

Katja

http://www.pdpatchrepo.info/hurleur/IPPASS02.pd

Hello again

I just checked out your patch and I'm pretty amazed! what do you plan to do with this step ahead in pitch tracking?

Elden, it may be a step ahead, but only if the problems with blockwise processing can be overcome, and at the moment I'm not even sure if that is possible for IPPASS. For autocorrelation, Philip McLeod has developed a solution as described in his thesis and in mentioned article.

So what is exactly the problem with blockwise processing here?

When performing autocorrelation via frequency domain (the only option which is efficient enough), it is a bit similar to convolution, but with the signal itself as the kernel, and without time-reversing that kernel. It is pointwise complex multiplication of the coefficients with themselves, and because the phases become zero anyway it boils down to squaring the real and imaginary coefficients and summing them pointwise. The power spectrum, simple as that. However, the operation suffers from the usual spectral leakage and the output is not at all so beautiful. Except when the input spans an integer number of fundamental periods in the signal and you overlap them, like I've done in the demo patch to illustrate the ideal case.

Normally when convolution is performed via frequency domain, boundary effects can be relieved by windowing the input for the FFT, and windowing the output of IFFT again. The signal must have at least four times overlap in that case.

But in the case of autocorrelation or IPPASS, the signal segments are returned as symmetric zero-phase segments by the IFFT. Overlapping these segments make no sense, except in the case of (again) an input signal which harmonizes with the FFT framesize. So you have to process and interpret the output frames individually, not as a stream.

It's funny: with an autocorrelation performed on a stream in time domain, like a convolution but with reversed time direction, it doesn't matter so much when the kernel is not an integer number of periods. I have tried this in a Pd patch using [FIR~], see attached [autocorrelation3.pd]. In that case, only the kernel is windowed (rectangular) and not the signal stream.

McLeod's brilliant solution for autocorrelation can not be applied to the IPPASS case, unfortunately. IPPASS uses the amplitude spectrum, not the power spectrum.

Katja

http://www.pdpatchrepo.info/hurleur/autocorrelation3.pd

The previous post delved into the problems with IPPASS before even explaining what it is and how it could be used. So here's the background theory:

Periodic signals with more than one harmonic by definition show periodic amplitude modulation. These modulations are annoying when you want to build an attack detector based on a sudden rise in amplitude. How to distinguish a periodic amplitude modulation from a real attack, a new sound? This is normally done by 'masking' the amplitude modulations. When building a fast attack detector for external [slicerec~] I've been scrutinizing amplitude modulations for hours, to see how they behave. Instantaneous amplitudes can be computed from an analytic signal.

Amplitude modulations of a periodic signal often tell more about periodicity than sample values. In the case of a weak or missing fundamental and a predominant second harmonic (like it often happens with vocals or musical instruments), the waveform and the autocorrelation show two peaks of almost equal height, per period. When the phases of that signal are aligned, the amplitude modulation shows one large peak per period. So, knowing the instantaneous amplitude or power of the phase aligned signal could be particularly helpful in avoiding the infamous octave jump in analysis and pitch shifting.

In the patch from the first post in this topic, the IPPASS function was generated this way: compute the amplitude spectrum, and produce a real and imaginary signal output from this. This gives phase-aligned analytic signal segments. Then square these real and imaginary phases to get the instantaneous power. Simple! But, as mentioned earlier, it would not work on arbitrary signal input, since spectral leakage will seriously spoil the whole thing. The principle of IPPASS is there, now must follow the implementation.

Katja

Thanks very much for sharing those patches, katjav .. very inspiring..

I'd like to join in when I get up to speed on the theory

Am I correct in my understanding that [FIR~] convolving with a windowed sinc function, is equivalent to using fft and multiplying by a 'box function'?
Which is quicker depends on the block-size, I suppose?

I assume that it's the [delay 100] that 'time reverses' the kernel in the autocorrelation patch

@ Katjav:
Do I understand right, that you try to predict when amplitude modulations of two relatively similar partials cause amplitude peaks in the sum when being at equal phase - and that this causes errors in pitch tracking programs, because they are kinda "surprized" by these?

And your results are...
1.)either create an algorithm for a pitch trecking program that won't be "surprized" by these peaks or
2.)find a way to lower these peaks at calculated times in the signal so that there's no way a pitch trecker could at all be "surprized"?

(or what or why? )

@elden said:

Do I understand right, that you try to predict when amplitude modulations of two relatively similar partials cause amplitude peaks in the sum when being at equal phase - and that this causes errors in pitch tracking programs, because they are kinda "surprized" by these?

Take this harmonic recipe as an extreme example:

first harmonic (fundamental) amplitude 0.2
second harmonic amplitude 1.0

Certainly the fundamental is not so weak that you would not hear it. Yet the autocorrelation function is almost a sine wave at double the period rate. The amplitude modulation however, and IPPASS, follow the original period, so IPPASS peaks are good indicators for the pitch here.

There are also cases where it's the other way round, for example:

first harmonic amplitude 1.0
second harmonic amplitude 0.
third harmonic amplitude 0.5

This is a clarinet-like recipe. Here, the autocorrelation function has no problem to display the correct period, while IPPASS shows three equal peaks per period.

So it seems to me that each function's weak aspects are complemented by the other. If you would implement both methods simultaneously, how would you decide which one is right at any given moment? In the above mentioned examples it is simple: the method indicating the longest period is right. Whether this is a general rule can only be checked when a full implementation is built and all sorts of signals can be used for testing.

It would be great if the two methods could be efficiently combined. A phase-aligned signal can by itself replace the autocorrelation part. Autocorrelation is nothing more than phase-alignment, but without keeping the original amplitudes, as you can easily verify by setting the phases of the [osc~]'s in IPPASS02.pd to zero. The phase-aligned signal, derived from the amplitude spectrum, is even a better indicator of periodicity than autocorrelation. A zero-phase and quadrature phase signal can be produced from the same spectrum, and from these phases the instantaneous power can be directly computed. You'd have two methods for less than double price.

So why is the amplitude spectrum not generally used instead of the power spectrum? Probably because it suffers from substantial leakage coefficients, the input must be Hann-windowed. In the power spectrum instead, leakage coefficients become very small (though not absent) as they are squared. Sure you could unwindow the central region of a Hann-windowed output, but this would require an increased analysis window size, undesirable in a real time application. There you have it, the boundary problems. If this can be solved with a trick not requiring extra input samples, it would open the way to a practical IPPASS implementation.

Katja

Ok I understand that.
As long as this key of not requiring extra input samples is not found, your method is only usable uncombined with todays other methods. but a program that allows you to choose the method of pitch tracking that does the job best from case to case would not necessarily need a combination of both, but a system that could check out which to use on it's own to get the best results, am I right?

I've now produced a patch where regular unbiased autocorrelation and PASS / IPPASS are compared, using real world audio as the input. See attached IPPASS03. It turns out that PASS / IPPASS is much more stable than autocorrelation. Moreover, the peaks stand out better so octave errors will be less likely to happen with these functions.

PASS is 'phase-aligned signal segment'. It looks a bit like autocorrelation but it is derived from the amplitude spectrum instead of power spectrum.

IPPASS is 'instantaneous power of phase-aligned signal segment'. It does not look like autocorrelation, but it translates periodical amplitude modulations and peaks thereof.

The good thing about PASS / IPPASS is, they complement each other well, and once you have PASS, you get IPPASS at a bargain.

These functions receive a lo-pass filtered input signal, because the pitch-tracking process must not be crossed by noises. In a real implementation, this stuff should be done in downsampled time, as downsampling can be efficiently combined with lo-pass FIR filtering. I'm considering a factor 0.125, using one out of eight samples. This will also make the FFT stuff more cpu-friendly. When a peak representing a period is found, it's exact location must be found with sinc interpolation from the downsampled stream, effectively performing a local upsampling.

If all goes well, you'd end up with an approximate period length in nr of samples, facilitating a safe cutaway or cut&paste for time domain pitch shifting.

Katja

http://www.pdpatchrepo.info/hurleur/IPPASS03.pd

If this pitch tracking method is stable enough, it should be finding out the deepest/loudest frequencies within polyphonic material, too, right?

could you build a patch that transforms audio pitch to midi cc data for me using your stable method?
I'd really like to test midi controlled harmonic masking in the "DtblkFxS" vst! That could make me separate polyphonic into monophonic melodies without the need of melodyne.

Very inspiring. I'm gonna study your patches carefully, Katjav ! Thanx.

Today, a patch with a demo of Philip McLeod's SNAC function, Specially Normalized Auto Correlation. See attached SNAC03.pd.

The function keeps undulating even with continuous periodic input, but it turns out that peaks indicating perfect correlation are stable at magnitude 1. Little more than a single period is needed to identify period length. This is a very attractive feature for realtime applications.

Read all about SNAC in McLeod's thesis:

http://miracle.otago.ac.nz/tartini/papers/Philip_McLeod_PhD.pdf

Unfortunately, SNAC is prone to give octave errors, just like regular autocorrelation. According to McLeod's tests the octave error rate is about 4% on average. Therefore, additional methods are required to verify the octave.

I'm still in doubt which method(s) to implement. SNAC gets the analysis within shortest time. For my voice, 512 samples are sufficient. Apart from octave jumps, analysis is probably very precise. IPPASS will be able to handle missing fundamentals, but needs twice as many input samples.

Anyway, I first need to find a good downsampling FIR filter and verify how the methods behave in downsampled time.

Katja

http://www.pdpatchrepo.info/hurleur/SNAC03.pd

@elden said:

If this pitch tracking method is stable enough, it should be finding out the deepest/loudest frequencies within polyphonic material, too, right?

For what I understand now, time domain methods can only find periodicity by way of simple pattern comparison. If for example the input is 400 plus 600 Herz, autocorrelation and IPPASS peak at 200 Hz, the frequencies can not be identified separately. Therefore I assume that time domain methods are suitable for monophonic processing. Frequency domain instead, shows individual frequency peaks, but not by itself periodicity. This seems more useful for polyphonic material.

Elden, why don't you try [sigmund~] for harmonic masking? It gives all the info you need and can even work on arrays.

Katja

Hi,

Katjav, could you please give some articles links or whatever to help understanding the use of 'alternate' and 'unbias' array of your implementation of the unbiased autocorrelation in IPPASS03.pd ?

McLeod's thesis talks about the 'classic' zero-padded FFT autocorrelation process, which you use in the (still biased) autocorrelation implementation seen in IPPASS02.pd (no zero-padding, though), but I could't find theorical discussion about peculiar windowing and the implications of 'alternating' power spectral density.

Sorry for my noobness.

Thanx,

Nau

Nau, the patch IPPASS02.pd was a very simplified representation of methods, where only fundamental frequencies harmonizing with the FFT size were selected for the test input signal. Therefore, no zero-padding was needed to demonstrate the effects.

In IPPASS03.pd, arbitrary frequencies can be selected, or a signal from the soundcard. This is a more realistic situation, where zero-padding and/or smooth windowing is needed to get acceptable results (otherwise you have 'circular convolution' effects).

Autocorrelation with zero-padding gives an effect like known from convolution: an autocorrelated block results in a triangle. The slope makes it harder to interpret results and for that reason the inverse function of the triangle is applied. The triangle-shape autocorrelation is called 'biased', and when divided by the triangle it is called 'unbiased'. Division by very small numbers cause instability, therefore certain regions were ignored in the plot.

I've included the alternate function in frequency domain to center the autocorrelation and IPPASS functions within their frame. This is done to make a better picture, but for calculations it is unimportant, because the functions are symmetrical anyway and only one side is used for analysis. Sometimes however, a centered signal is really important, for example when you want to implement a zero-phase FIR filter as a fast convolution. In that case you need phase angles from -pi till pi, not from 0 till 2pi. Pd's fft functions do not center, but when needed you can do this yourself by alternating the FFT coefficients. I don't know literature on signal rotation and spectrum alternation, but the topic is illustrated on my blog:

http://www.katjaas.nl/FFToutput/centeredFFT.html

In the meantime I've also scrutinized [autotuned~]'s autocorrelation process. In addition to zero-padding, a Hann window is applied there. Unbiasing in this case means division by the autocorrelated Hann window and that is done indeed, but only to find the 'confidence' rate for the period peak. The location of the period peak is found from the biased autocorrelation. In practice, this seems to work well. More on [autotuned~] in this thread:

http://puredata.hurleur.com/sujet-3518-autotune

Attached is a patch with a demo of the Hann-windowed autocorrelation as it is done in [autotuned~]. (By the way, this time the output is not centered).

All taken together, there's a choice of functions and implementations for period-tracking. All these methods are easy to implement in C. From [autotuned~] I have learned that a stable period detector is not enough to make a good pitch shifter though...

Katja

http://www.pdpatchrepo.info/hurleur/HannedAutocorrelation.pd

Thank you so very much ! What a generous answer.
Quite a nice way to learn things.

Nau

Nau, your questions forced me to rethink the stuff once more so it helped me as well.

Today I've illustrated the periodic amplitude modulations and IPPASS period indicator on my blog:

http://www.katjaas.nl/ippass/ippass.html

And attached is a patch ampmod.pd where amplitude modulations are plotted on the complex plane.

Katja

http://www.pdpatchrepo.info/hurleur/ampmod.pd

hi there,

here is an article that proposes some autocorrelation scheme improvements (time domain):

http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CCwQFjAA&url=http%3A%2F%2Fwww.ircam.fr%2Fpcm%2Fcheveign%2Fpss%2F2002_JASA_YIN.pdf&ei=HxorT5aANIuc-wawut2qDg&usg=AFQjCNFv4nTmr56KIWu8pr_Ak7rYufMFBg

I didn't have time to read it seriously yet, so sorry if it's useless.
The tests are voice-oriented, but they seem to say that it could be suitable for musical sounds in general.

I stumbled over this note in the text...

Equation ͑18͒ resembles ͑with differ-
ent coefficients͒ the ‘‘narrowed autocorrelation function’’ of
Brown and Puckette ͑1989͒ that was used by Brown and
Zhang ͑1991͒ for musical F 0 estimation, and by de Cheveigne ͑1989͒ and Slaney ͑1990͒ in pitch perception models.

I don't know if this "narrowed autocorrelation function" was used by Puckette in [fiddle~] or [sigmund~] yet.

Nau

Thanks for pointing to the article, Nau. It's interesting, the YIN technique is used in STK class LentPitshift. (http://www.music.mcgill.ca/~francois/MUMT_618/Report/Report.pdf)

Today I started to try and port LentPitshift to Pd, just for evaluation purpose. Not too much progress though. First I wanted to write a flext wrapper, but did not even manage to compile the flext / STK / Pd example project 'clarinet' after a few hours of puzzling. Then tried stk2pd, very nice initiative but only for stk instruments, not stk effects, as it turned out. Anyway, if it succeeds, it gives the opportunity to check YIN and Lent's method in PD.

Katja

Edit: [lent~] was built in the end. It is here:

http://puredata.hurleur.com/sujet-6734-lent-pitch-shift-mickey-mouse

Hi Katjav,

Congratulations !
I saw the post about your [lent~] object, but couldn't test it as I am an Ubuntu 10.4 user.
And thank you for your homepage (http://www.katjaas.nl/home/home.html), very stimulating.

This pitch tracking and other pitch shifting topics do interest me for two reasons : first I'm studying Freq domain processing at the time, and these topics are very inspiring. Two, I sometimes transform my violin into a "midi controller", 'midifying' it using [sigmund~]. Of course the results are modest,and a new pitch tracking algorithm in Pd would be highly stimulating.

It would be so nice to keep only the 'YIN' part of the code and make a Pd object that could compete with [sigmund~] for mono sources. I'm no C programmer, just experienced it ten years ago, rather hovering than digging deep.
So if you think this is possible and if you wish to, it would be so nice if you could consider making it for me, and the community. I really think many Pders use [sigmund~] and [fiddle~] and would appreciate an alternative object, so your contribution would be appreciated by a lot of people ! I don't know if this is very complicated or rather straightforward, so please excuse me if I dare asking you such a work.
Of course if you think this is possible but don't want to do it, I'll try it the next months, learning something I'm not sure I want to

Thank you,

Nau

Nau, can you explain what problem you have with [sigmund~]? In my experience it is fairly accurate and it has a lot of options.

The YIN pitch tracker as implemented in LentPitShift is less accurate, and moreover it is very CPU-intensive.

From my experiments so far, it seems that Philip McLeod's SNAC method is the best time domain solution. It is fairly efficient, probably accurate and stable. Moreover, it needs no Hann windowing, therefore it can work with smaller analysis frame. Although it is not immune for octave errors, improvement may be possible with more refined peak picking algorithms as described by Paul Boersma:

http://www.fon.hum.uva.nl/paul/papers/Proceedings_1993.pdf

I'm planning to write the SNAC method in a Pd class and test it thoroughly, in preparation for a time domain pitch shifter.

So what is the advantage of an autocorrelation-based pitch tracking method, over a frequency domain method like [sigmund~]? For me, the difference would be that it's simpler. I've done frequency domain pitch tracking some time ago, and found that it is hard to find the fundamental there, if it is relatively weak. In time domain it is easier: the fundamental gives the largest peak, even if it is weaker than the second harmonic. And in case of doubt, I could compute the IPPASS, which is unambiguous in such cases.

Autocorrelation is most efficiently calculated via frequency domain. This means, it can not be more efficient than a frequency domain pitch tracking method. If SNAC turns out to work well enough, I would probably use it in downsampled time, because the signal stream has to be filtered anyway. Say your analysis frame needs to be 1024 samples at samplerate 44100, 4 times downsampling would enable an analysis of only 256 samples. Latency is still 1024 samples of course, but you could do 4 analyses 'at the price of 1', and have a new pitch indication every 256 samples.

Katja