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