Fast resampling - which algorithm?

DSP, Plugin and Host development discussion.
Post Reply New Topic
RELATED
PRODUCTS

Post

AUTO-ADMIN: Non-MP3, WAV, OGG, SoundCloud, YouTube, Vimeo, Twitter and Facebook links in this post have been protected automatically. Once the member reaches 5 posts the links will function as normal.
Hi
I am looking for a fast and good quality algorithm for upsampling and downsampling by integer values (2x to be specific - should be enough). I started with a very simple one, from here: http://www.nicholson.com/rhn/dsp.html (http://www.nicholson.com/rhn/dsp.html), but it's not very fast when using a 4k window length, even if I pre-compute the coefficients. This is my first project dealing with audio, so my understanding of all this is still rather basic. Can anyone point me in the right direction?

Post

if that sinc interpolation is too slow, make the impulse response shorter
if you don't like that, then you can try with a high-order IIR filter, say butterworth or something, but it won't be so elegant
It doesn't matter how it sounds..
..as long as it has BASS and it's LOUD!

irc.libera.chat >>> #kvr

Post

There's a couple of nice, easy to read papers on this:

The Quest For The Perfect Resampler (Laurent de Soras): http://www.mp3-tech.org/programmer/docs/resampler.pdf
Polynomial interpolators: http://www.student.oulu.fi/~oniemita/dsp/deip.pdf

For a first project with audio I'd use much simpler (but less clean) algos personally - something like cubic interpolation or even linear interpolation. If you're generating looping waveform mip-maps for a wavetable synth, using FFT works too (that's the algo I used in my VST synth anyways).

Post

For 2x, "half-band poly-phase all-pass" is probably a good candidate if you don't need linear phase. Laurent de Soras has an implementation, and I think there's on in music-dsp archives too.

Post

It really depends what you are trying to achieve. Do you want to oversample the direct audio signal or just the control voltage? Or maybe just a "wet" part? These details can relax the design constraints make a huge performance difference.

Generally, both the interpolation and decimation stage from 44.1kHz to 88.2kHz is particularly demanding, especially if you want to deliver a near full-band result.

IMHO, a clever FIR half-band and SSE combination will nuke both the polynomial and allpass polyphase approach performance and quality wise (polynomials mess with the pass band and have low aliasing rejection, allpass based halfbands on the other hand come with a strong phase-distortion and aren't that fast).

The problem with the latter is that usually, one can avoid oversampling the direct signal with a differential processing approach instead (i.e. only oversample the actual "wet/processed" part). But these tricks often only work with linear phase filters. In practice, linear phase filters often make the implementation of a faster overall processing structure easier, even if the FIR required my seem slower in direct comparison.

BTW, don't do the mistake to oversee that Laurent de Soras' assumes an already oversampled input in his polynomial paper! (the paper is easy to read, but it's also easy to oversee this important sentence) Polynomials are particularly bad oversampling filters from my observations, no matter in which situations. It's easy to design very fast FIRs too if we apply the same restrictions, and we can easily avoid the inherently problematic passband behavior of polynomial interpolators.

Here's a nice introduction to resampling and FIR structures (you can also find pretty good c++ FIR implementations packed in their ScopeFIR software):
http://www.dspguru.com/dsp/faqs
Fabien from Tokyo Dawn Records

Check out my audio processors over at the Tokyo Dawn Labs!

Post

Since I'm not really a DSP guy, I wrote a decent resampling algorithm, that is very fast, but not totally aliasing-safe in all cases.

I used an hermite interpolation technique (you can find it at musicdsp.org), for lowering the pitch, and a series of different algorithms for raising the pitch that implements a simple kind of boxcar lowpass filter (the most basic one).

There are two basic operations when resampling: interpolating for non integer values (and so for lowering the pitch) and lowpassing for higher integer values.

So my method is just to choose the appropriate function in relation to the desired resampling value.

For example for incremental values lower than 1 I use the hermite interpolation functon, for values higher than 1 but lower than 2 I use an hermite interpolation combined with a little lowpass filter, for values between 2 and 4 I use a linear interpolation combined with a stronger lowpass filter, and so on. When incremental values are very high I only use the lowpass filter.
The lowpass is a boxcar average filter, that is very basic but very easy to compute. If I want to average the next 64 samples, I don't take all of them, but just some, for example a sample every two or four. This can potentially bring in some aliasing noise, but it could save a lot of CPU power, due to the reducted access to the wavetable.

I couple all those techniques by pairing the samples in a record (delphi, struct in c) that contains left and right channels, and using the inline assempler to take advantage of the SIMD extensions.

In extreme cases my method can introduce aliasing when raising the pitch (expecially with specific test with raising sines and so), but I compared the sound with other samplers and I find its behaviour more than acceptable for quality and speed.
It is also very flexible. When raising the pitch on most samplers, the CPU utilization will raise accordingly. This method can let you choose a more relaxing way to treat the different incremental values, to pair the CPU utilization on the whole keyrange.

Post

Thank you for all the replies. Perhaps I should have given more information in my original post. I am working on continuously variable vari-speed. I currently have a very basic version using simple linear interpolation and no internal upsampling at all, but the results are correct. I am currently leaning towards a sample-and-hold interpolator followed by a FIR lowpass filter using the overlap-add method. I will report back once I know if it works or not and post some code.

Post

Continuously variable vari-speed resampling is QUITE different from the 2x oversampling you specified in the original case. It is also somewhat more difficult problem, especially if you want to do it with high-quality.

That said, oversampling by an integer factor + polynomial (linear, cubic, whatever) interpolation does provide you reasonable results as long as your variable resampling factor stays "reasonably close" to 1. Exactly what is reasonably close depends on what kind of quality you want, ofcourse. :)

I wonder what you mean by sample-and-hold interpolator? I can think of couple of ways to provide quality better than the "oversample + polynomial" but sample-and-hold isn't one of them (unless you process at insane rates), so I wonder if I'm misunderstanding what you mean.

Post

Also, depending on your target platform, brute-force sinc-interpolation is quite feasible in real-time on modern desktops, as long as you don't go crazy with the kernel lengths.

Post

AUTO-ADMIN: Non-MP3, WAV, OGG, SoundCloud, YouTube, Vimeo, Twitter and Facebook links in this post have been protected automatically. Once the member reaches 5 posts the links will function as normal.
I wanted to use one of Olli Niemitalo's polynomial interpolators from his paper (http://www.student.oulu.fi/~oniemita/dsp/deip.pdf (http://www.student.oulu.fi/~oniemita/dsp/deip.pdf)) . But to get there, I need to oversample the input by at least 2x. This is why I think I can simply repeat every sample value twice (sample-and-hold) and then try to filter everything above 1/2 bandwidth. My hope is that polynomial interpolation should be faster than recalculating the kernel for every output sample.

Post

Repeating every value twice will do you little good. First of all, such doubling of samples is equivalent to upsampling with a box filter (where as linear interpolation would be equivalent to a triangular filter). This is the wrong approach, as it will have negative effects on the high-frequency contents that you probably want to preserve.

Better approach is to insert zeroes between the samples. Unlike poor filters, this will have no effect on the original bandwidth. It will mirror the original spectrum to the extended bandwidth, but you can use a regular "brick-wall" lowpass to remove this. If you using doubling or some other form of interpolation, these will have effect on the base-band, and you would then have to compensate for any high-frequency loss in the filter kernel (can be done, but you need twice the CPU, since zero-stuffing allows poly-phase filtering).

Obviously, if you don't mind "brute-force" (ie not using FFT) convolution, then using a poly-phase filter with a "huge" (around 4k is quite good, though more branches mostly cost memory only) number of branches (to eliminate the need to interpolate) gives you essentially perfect results (given sufficiently high-quality filter, ofcourse.. if you calculate 4 taps/branch polynomial filter, then obvious the results will be similar to regular cubic interpolation.. but somewhere between 16 to 32 taps is "quite reasonable" for real-time.. note that this is too short for FFT to even be useful), for roughly the cost of filtering the target (or source; whichever is higher) signal with a single branch.

Post

And on the topic, I'd like to point out that the only good reason that sinc interpolation is "easier" in integer ratios is because we would like to pre-compute a sinc table instead of evaluating the sinc function (including the sin function) over and over at arbitrary points. The integer idea gets ingrained in peoples' minds because all DSP books tell us that to SR convert by a non-integer amount, we need to use a ratio of integer upsampling and downsampling. But that's nonsense—we could do fractional sinc SRC in a single step if we want the cost of the sinc evaluations—or we can pre-compute an oversampled sinc table and evaluate the arbitrary point in it with linear interpolation (or even truncation, at the cost of a larger sinc table, depending on requirements).

https://ccrma.stanford.edu/~jos/resample/

Oh, and the best non-math explanation of sample rate conversion that I know of is here (yes, it's by me—sorry if I sound boastful, but I just don't know of one better):

http://www.earlevel.com/main/2007/07/03 ... onversion/
My audio DSP blog: earlevel.com

Post Reply

Return to “DSP and Plugin Development”