Trying to understand oversampling

[plusfer]

I'm trying to understand oversampling, this is a basic test, but doen't work.

What I'm doing wrong?
The filter works ok, but the harmonic bounces back in the nyquist.

Code: Select all

    double in1 = inSample; 
    double in2 = 0.0; 
    //double in2 = (lastinput + inSample) / 2.0; lastinput = in1;

    in1 = upsampler.process (in1); // a fir filter
    in1 = in1 + (in1*in1*0.5);
    in1 = downsampler.process (in1); // the same fir filter, but other instance

    in2 = upsampler.process (in2);
    in2 = in2 + (in2*in2*0.5);
    in2 = downsampler.process (in2);

    outputSample = in1;

[stratum]

Just do a linear interpolation for the missing samples and filter with windowed sinc. Thats the simplest upsampling operation that makes intuitive sense while in theory (and in practice if the filter is good enough) you could also set missing samples to zero.

For downsampling just filter (lp, windowed sinc) and throw every n-1 samples and pick one.

Thats the basic idea. One probably could do countless variations of it.

[squaresine]

It sounds like you are just filtering without actually padding the signal with zeros first. The low pass filter is used to remove phantom images from the upsampled signal. The images are created because you pad the signal with zeros, creating a signal n times longer than before.

You have to do the opposite when downsampling, called decimating, where you remove samples. You have to filter prior to decimating so that the frequencies above the higher nyquist are removed.

It would be useful if you expanded on what the functions in your code do.

[avasopht]

This is oversampling (applied to images).



That pure black line is a synthesized line. Those sharp edges are aliasing, because the sudden change from white to black introduces additional frequencies (yes images have a frequency spectrum too!).

In order to create the smooth anti-aliased line you render the line at a higher resolution and then downsample with an anti-aliasing filter. An image blur is a low pass filter, and an anti-aliasing filter is a low pass designed to offer optimal low pass filtering.

That is not what you have done.

[matt42]

Looks like you're code is OK. I can't say for sure as it's short on detail.
What you seem to be doing is:

1: upsample with zero padding
2: upsamplerProcess()
3: Low order wave shaping (2nd order)
4: downsamplerProcess()
5: decimation of every other sample

This could be perfect, or totally shit. The secret sauce is steps 2 and 4.

upsamplerProcess and downsamplerProcess need to be low pass filters set to the original nyquist frequency, (half the original sample rate in other words). These lowpass filters need to be high enough order to wipe out all, or most of the content above their cutoff. A cheap filter will not attenuate enough and you will have aliasing.

[plusfer]

Ok, I get it work,
The filter cutoff must be at 0.25 instead 0.5
The problem is that i need a lot of taps to remove some aliasing (with a x^2 input signal) .
To get 4x os, the filter cutoff at 0.125.
I think this is not the right way to do it.

Thanks guys

[aciddose]

It should look like this:

Code: Select all

upsample(input)
for (int i = 0; i < upsample.oversamples; i++) {
upsample[i] = process(upsample[i]);
}
output = downsample(upsample);

[aciddose]

For example with zero-padding:

Code: Select all

template <typename T, int N>
struct zeropad_t
{
	operator()(T input, T *buffer, int oversamples)
	{
		buffer[0] = input;
		for (int i = 1; i < oversamples; i++) {
			buffer[i] = T(0.0);
		}
	}
};

template <typename T, typename F, int N>
struct oversampler_t
{
	enum constants
	{
		oversamples = N,
	};

	void operator()(T input)
	{
		filter(input, buffer, oversamples);
	}

	T &operator[](int i)
	{
		return buffer[i];
	}

	smart_array<T, N> buffer;
	F<T> filter;
};

[matt42]

Ok, I get it work,
The filter cutoff must be at 0.25 instead 0.5
The problem is that i need a lot of taps to remove some aliasing (with a x^2 input signal) .
To get 4x os, the filter cutoff at 0.125.
I think this is not the right way to do it.

Thanks guys

Yes, but you can optimise if you know every other input sample for x2 or 3 out of 4 samples for x4 are 0. Likewise you can also optimise for the down sampling as you only need to calculate taps that fall on the output sample that will be saved after decimation. Plus these type of FIR filters are well suited for SSE optimisatons also. So the cost can be much less than you initially envision.

[plusfer]

Thanks matt42 and acciddose!

Ok, There is another way instead zero stuffing?
I tried with linear interpolation, delaying 1 sample

Code: Select all

double in2 = (delayed + in1) * 0.5; // in1 is the real sample, in2 is the new oversampled sample

but I don't noticed better results than in2 = 0

[JCJR]

Hi plusfer

I am not expert on this (or anything else)-- If you repeat-sample or linear interpolate before anti-alias filtering, those act like lowpass filters. They will lowpass filter a fair amount in the top octave at the original samplerate. I think it could lower the requirements needed for acceptable anti-alias filtering compared to zero-stuffing, but if you want "as flat as possible" into the top octave it could be a problem.

Some applications do not need "ruler flat right up to nyquist" however. Depends on the application.

Sometimes people will use quick'n'dirty resampling techniques which have built-in too much high frequency rolloff, and then try to boost up those losses with a bandpass or elliptical filter so that the HF loss is not so bad. The "fixup" filter trying to straighten up the rolloff caused by the quick'n'dirty resampling.

I played with that long ago. It took some experimentation because ordinary IIR bilinear transform filters do not behave "intuitive" up high, so I just ended up tweaking, testing, tweaking, testing, until a filter combination was found that worked fairly good.

Olli Niemitalo back in 2001 wrote a really good article evaluating various quick'n'dirty approaches-- http://yehar.com/blog/wp-content/upload ... 8/deip.pdf

If I ever get around to playing with it again, awhile back aciddose mentioned lanczos interpolation. That is just a FIR lowpass filter with a sinc-windowed sinc kernel. I gather they are usually used with fairly small kernel sizes. I experimented a little with lanczos kernels up to about 17 total size (both halves of the symmetrical function). They seem to work pretty good for short kernel filtering. Would like to experiment with them some more.

So anyway, maybe a fairly short lanczos, maybe even N=3 or N=4, would do pretty good as a substitute for zero-stuffing or linear interpolation. https://en.wikipedia.org/wiki/Lanczos_algorithm

[aciddose]

Linear isn't much better than zero padding. The difference is zero padding falls off similarly to zero-order while linear is first-order. Both have "holes" or "notches" while 1st order gives 1/N amplitude for each image.

That isn't a very good slope!

That's actually very similar to an IIR filter "6 dB per octave" with the cutoff set to nyquist. Both result in some loss at high-frequency below nyquist ("in band") and both don't cut much above nyquist.

What you want to do instead is to insert windowed sinc pulses for each sample at the source rate.

A "quick and dirty" alternative is an all-pass interpolator like the following:

Code: Select all

template <typename T>
struct ap2
{
	ap2()
	{
		clear();
	}

	void clear()
	{
		for (int i = 0; i < 6; i++) {
			u[i] = 0.0f;
		}

		d[0] = 0.0f;
		d[1] = 0.0f;
	}

	// all-pass filter
	T f(const T in, T &b, const T c)
	{
		const T x = (in - b) * c;
		const T out = b + x;
		b = in + x;
		return out;
	}

	void process(const T input, T *output)
	{
		output[0] = f(f(f(input, u[0], 0.0266328f), u[1], 0.22867f), u[2], 0.59637f);
		output[1] = f(f(f(input, u[3], 0.1045800f), u[4], 0.39320f), u[5], 0.84751f);
	}

	T process(const T *input)
	{
		return (
			f(input[0], d[0],  0.150634765625f) + 
			f(input[1], d[1], -0.3925628662109375f)) * 0.5f;
	}

	T u[6];
	T d[2];
};

Similar filters can be constructed for any integer ratio (2, 3, 4, 5, ...) although the performance is not very good for such IIR filters.

You can also see the "halfband all-pass interpolators" on musicdsp here: http://www.musicdsp.org/showone.php?id=39

For better results you need to look at combinations of FIR and IIR filters. Start by producing ideal FIR filter kernels and make up for pass-band or stop-band issues with very simple IIR filters. See discussion of "polyphase FIR filters" here in the KVR DSP forum and elsewhere.

A simple interpolation like linear interpolation can work and can even be the very best solution for a particular problem, but only in very limited circumstances. In the case of non-linear processing for example it is very unlikely to provide enough stop-band attenuation for either up-sampling or down-sampling stages.

Linear interpolation combined with a two-pole filter can provide very adequate results when up-sampling the input to a linear filter, and even in specific cases for non-linear filters. You can use over-sampled linear as a very quick first stage and down-sample the result after processing with an IIR filter to reduce the pass-band roll-off as well as significantly increase both stop-band attenuation and slope.

Unfortunately such filters are a very complex topic and the best filters are always more expensive. In my opinion the biggest optimization issue for such filters is making basic trade-offs regarding acceptable levels of aliasing and other sources of error.

[earlevel]

Just do a linear interpolation for the missing samples and filter with windowed sinc. Thats the simplest upsampling operation that makes intuitive sense while in theory (and in practice if the filter is good enough) you could also set missing samples to zero.

For downsampling just filter (lp, windowed sinc) and throw every n-1 samples and pick one.

Thats the basic idea. One probably could do countless variations of it.

The rest sounds good, but about the first sentence: Linear interpolation is equivalent to zero stuffing then running through a pretty crappy low pass filter (with a triangular-shaped impulse response) that droops at the high end and has poor stop-band rejection (aliases); then you say to run that through a better lowpass filter. Why not zero stuff and go right to the good filter?

Sorry, I don't mean to cherry-pick criticism of someone's help, and certainly there are places that linear interpolation for up sampling works fine (especially stuff that's already oversampled, such as audio without a lot of high frequency content). But I don't think the linear interpolation buys you much in the way of filtering if you are going to follow it with a better filter, and it hurts passband response near the cutoff that windowed sinc won't get back.

[earlevel]

Linear isn't much better than zero padding. The difference is zero padding falls off similarly to zero-order while linear is first-order.

No, zero padding does not fall off similarly to zero-order. It doesn't fall off AT ALL. That's why we use it.

[aciddose]

Zero padding does modify the content within the pass-band and so does "fall off". It creates both pass-band and stop-band ripple.

Only an infinitely thin pulse would not create any ripple, while at the same time it would be of zero amplitude.