Path: utzoo!mnetor!uunet!husc6!mailrus!tut.cis.ohio-state.edu!uwmcsd1!ig!agate!eris!doug
From: doug@eris (Doug Merritt)
Newsgroups: comp.sys.amiga
Subject: Re: Font Smoothing Algorithm
Message-ID: <8310@agate.BERKELEY.EDU>
Date: 4 Apr 88 09:33:27 GMT
References: <6065@elroy.Jpl.Nasa.Gov>
Sender: usenet@agate.BERKELEY.EDU
Reply-To: doug@eris.berkeley.edu (Doug Merritt)
Organization: University of California, Berkeley
Lines: 73
Keywords: FFT, smoothing, maps, zoom, spatial filter, averaging, bogus Dpaint2
Summary: Low pass spatial filtering does the trick

In article <6065@elroy.Jpl.Nasa.Gov> rgd059@Mipl3.JPL.Nasa.Gov writes:
>
>Does anyone have, or know where to find, an algorithm for smoothing out
>bitmapped fonts when they are scaled up?  Specifically, I want to enlarge
>standard Amiga fonts and not get a blocky appearance.  Failing that, how
>about a general bitmap smoothing routine?

The standard conceptual model for doing this with *any* bitmap images,
including but not limited to fonts, is to do a spatial lowpass filtering
pass after the enlargement/zooming pass.  No colors or grey scales
considered here, but the model is easy to extend.

A simple pixel-duplicating enlargement preserves hard edges/lines, which
corresponds to adding extraneous high resolution details. This is obvious
once you consider that, if you enlarge by (say) a factor of two, then your
smallest resolved detail is in blocks of 2 by 2 pixels, each of which will
be either entirely black or entirely white (depending on the single pixel
that was magnified into a two by two block).

Obviously the magnified bitmap could be smoother if individual pixels
could be turned on or off as well as 2 by 2 blocks. The pixels which
*should* be another value than they actually end up being, constitute
high resolution noise...an artifact created by magnification. In
Fourier optics, different resolution scales correspond to different
spatial frequencies; high resolution noise equals high spatial frequency
noise. By analogy with acoustical spectrums, consider that the obvious
way to get rid of high frequency noise is with a low-pass filter.

So what you do is run a two-dimensional low-pass filter over the
bitmap. The "overkill" way to do this is to take the Fourier transform
of the bitmap (w/ a public domain FFT algorithm), delete the highest
frequency (note that this is the filtering step, and in general could
be a much more complex filter), and do an inverse FFT again to get your
smoothed bitmap back.

The fast, smart, easy way to do it is with a special purpose filter...
Low pass filtering corresponds to an averaging operation. If you
average each successive pair of values in a sampled one dimensional
signal (like digitized sound), you are effectively filtering out the
highest frequency component. You can do the same thing in a bitmap
by making each pixel equal to the average value of its nearest neighbors.

That's all you have to do to smooth it, but you probably will have to
map the resulting grey scale (result of averaging) into pure black and
white by thresholding (picking a grey value below which the pixel is
considered black, and above which it's considered white).

If your zoom factor is something other than a factor of two, the
algorithm still works as long as you create intermediate grey scale
pixels during enlargement, followed by a *weighted* average over the
number of pixels involved in the magnification.

Left as an exercise for the reader is the question of whether to include
diagonal neighbors in the averaging process, and if so, how much to
weight them relative to up/down/right/left neighbors.

Ta-da. You're done. Easy, right? The only reason I went into so much
detail, rather than just sketching the algorithm, is to make it clear
that this is an implementation of a clean mathematical model, not just
a hack that happens to work. Also it's a good example of why FFT's are
so indispensible with optical or imaging analysis of (almost) any sort.

As far as I can tell from the (lack of) features in this area in
commercially available Amiga software, far too few people are aware
of this stuff. For instance, Dpaint 2 does not use this method when
changing the size of brushes...it simply selectively deletes/replicates
pixels, which is often highly undesirable since it introduces a lot
of strange artifacts into many types of images.

P.S. is this a good candidate for the comp.graphics tutorial series???

	Doug Merritt		doug@eris.berkeley.edu (ucbvax!eris!doug)
			or	ucbvax!unisoft!certes!doug