[net.audio] Sample rate conversion

ken@turtlevax.UUCP (Ken Turkowski) (02/25/86)

In article <698@mprvaxa.UUCP> parker@mprvaxa.UUCP (Ross Parker) writes:
>Subject: Fast colour anti-aliasing - determining new pixel colours
>
>Does anyone out there know of a fast (or even a slow) algorithm for
>colour anti-aliasing? The actual problem is to shrink a colour
>raster image, and I need to know how to calculate the colours of the
>pixels in the new image, which (I would imagine) is similar to calculating
>pixel colours for anti-aliasing. 

In article <531@kontron.UUCP> brad@kontron.UUCP (Brad Yearwood) writes:
>Subject: Digital audio - sample rate conversion
>
>what techniques could one use to implement a clean conversion from one
>sample rate to another - either upward or downward, without converting
>back to analog and then re-digitizing at the other rate?
>
>Intuitively, I can more-or-less grasp the use of an FIR digital filter
>to interpolate in the Philips 4x "oversampling" CD playback filter
>system.  What happens if you are not resampling to a convenient integer
>multiple of the original rate?  Would a similar technique be applicable
>for increasing or decreasing the sampling by non-integer factors?
>Resampling to a decreased rate is particularly baffling.
>
>I suspect that the problem is similar (and a dimension simpler) to
>conversion of television signals from one standard to another or image
>magnification/shrinking.  If anyone is familiar with literature
>relevant to any of these areas, I would appreciate some pointers.

These two articles relate to the same computational problem:
resampling a one or two-dimensional signal.  This involves determining
the value of the signal between sample points, given certain
assumptions on the characteristics of the original signal.

The most usual assumption is based on the Sampling Theorem, and that is
that the signal is bandlimited.  Using classical signal processing
theory, then, we can reconstruct the (analog) signal by passing it
through an ideal low-pass filter.  The desired intermediate value can
be found by resampling the analog signal.

Of course, we don't have to really convert the signal to analog.  We
can approximate an ideal low pass filter by convolving the original
sampled image with an FIR or IIR digital filter.  My own preference is
to use a Lanczos-windowed sinc function (total of 3 lobes) as an FIR
filter.

The parameters of the low-pass filter are dependent on whether the
resampling is an interpolation or a decimation.  In the former case,
the cutoff frequency is set to half the sampling rate of the source,
and in the latter, it is set to half the sampling rate of the
destination.  The interpolation filter covers a fixed number of
samples, while the decimation filter covers a larger number, inversely
proportional to the size change.

Actually, rather than just one filter, we use a family of filters phase
shifted to the set of destination sample points which lie, in general,
between the source sample points.  Each of these filters should be
individually normalized, or else you'll get banding in your image or
signal.

I've implemented several of these things, both in fixed point and
floating point.  They're equivalent as far as results go, but the
fixed-point version runs faster.  The floating-point version is easier
to debug, so if this is a one-time resampling, floating-point is more
suitable.  It takes about twice as long to debug a fixed-point version,
but it is worth it if you're going to do it for more than one signal or
image.

The resampling can be done easily to integer sampling ratios.  It is
also not more difficult for rational sampling ratios; it just requires
precomputation of nm filters, where n/m is the sampling ratio.
Irrational sampling ration require the recalculation of the filter
coefficients at each point; I don't think that even commercial special
effects units like the Ampex ADO or the Quantel Mirage use irrational
sampling ratios because it's so computationally intensive.  Irrational
numbers can be easily approximated with rational numbers, anyway.

For references on digital filtering, see "Digital Signal Processing",
by Oppenhein and Schafer, or a similar title by Gold and Rader.

For fast interpolation on linear transformations of images, see the
1980 SIGGRAPH proceedings:  "3-D Transformations of Images in Scanline
Order" by Catmull and Smith, and "Synthetic Texturing using Digital
Filters" by Feibush, Levoy, and Cook.  I also recently saw an article
in IEEE's Computer Graphics and Applications magazine.

-- 
Ken Turkowski @ CIMLINC, Menlo Park, CA
UUCP: {amd,decwrl,hplabs,seismo,spar}!turtlevax!ken
ARPA: turtlevax!ken@DECWRL.DEC.COM