Path: utzoo!attcan!uunet!husc6!bbn!mit-eddie!bloom-beacon!gatech!purdue!decwrl!ucbvax!HPLABS.HP.COM!holland%hplwdh
From: holland%hplwdh@HPLABS.HP.COM (Bill Holland)
Newsgroups: comp.windows.news
Subject: Re: Scaling bitmapped images - help wanted
Message-ID: <8805121624.AA04172@hplwdh.HPL.HP.COM>
Date: 13 May 88 04:43:17 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The Internet
Lines: 49

> >I have worked out some algorithms for doing the scaling, but they
> >are either too slow, or not able to handle scaling by fractional
> >amounts.  I have not been able to find any literature on the
> >subject, either in the Sun manuals, or elsewhere.  I am sure there
> >must be something, because in PostScript you can just say
> >"x y scale". 
>
>The quick and dirty way is to skip pixels or use pixels more than once 
>while building a destination image from the source image. This works 
>for any ratio of sizes.
>
>An error variable is kept based on the ratio of the src & dst sizes.
>
>This technique works well in software and in hardware. By well I mean 
>my personal judgement of the speed of the operation versus the quality
>of the resulting image.  The Sun NeWS port uses this technique in software,
>and the Parallax NeWS port has this function in hardware and in software.
>
>The only type of image it will look terrible on are CAD images.

Literature does exist on the subject.  The general problem is changing
the sample rate of a sampled function to a new rate.  The theoretically
correct method is to reconstruct the original sampled function at the new
sample points.  That produces the desired scaled (re-sampled) output.

A good textbook on the subject is "Multirate Digital Signal Processing",
by Ronald E. Crochiere and Lawrence R. Rabiner (Prentice-Hall, 1983).
This book contains a readable description of the problems involved,
followed by a theoretical treatment of their solutions, and some
practical examples.

However, that book does not deal with the specific problem of scaling
two-dimensional images.  Various papers in such journals as the ACM
Siggraph Proceedings have dealt with this in years past.  Ampex and
Lucasfilm (among others) have their own implementations of image
scaling algorithms, and have found extensions of those algorithms to
provide image translation and rotation as well.

In general, such algorithms produce good looking output when dealing
with gray scale images (images with intensity quantized to multiple
bits), that don't have a lot of jaggies.  That's just saying that the
output can be only as good as the original output:  if the original
image is quantized to one bit intensity levels, or contains aliasing
errors such as jaggies, the defects in the original image are likely
to be worse in the scaled output image.  This problem only gets worse
if the output image must be quantized to one bit.  There the best bet
is to regenerate the image, if that's possible.

- Bill