Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/5/84; site umich.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!gamma!epsilon!mb2c!umich!tom
From: tom@umich.UUCP (Tom Libert)
Newsgroups: net.graphics,net.works,net.text
Subject: Digitized images on bilevel displays (e.g. laser printers)
Message-ID: <427@umich.UUCP>
Date: Tue, 28-Jan-86 09:46:18 EST
Article-I.D.: umich.427
Posted: Tue Jan 28 09:46:18 1986
Date-Received: Thu, 30-Jan-86 04:46:54 EST
Distribution: net
Organization: University of Michigan, EECS Dept., Ann Arbor, MI
Lines: 45
Xref: watmath net.graphics:1423 net.works:1246 net.text:912

We've been experimenting with different techniques for displaying
digitized images (5-8 bits/pixel) on bilevel displays (e.g. laser
printers, bitmapped terminals).  So far we've implemented ordered
dither, constrained average, a form of minimized average error
(Floyd-Steinberg algorithm), and various halftone approximation
techniques (spirals, asymmetric dots).  We've also used the
equalized histogram technique to spread contrast over the
entire range prior to applying the above algorithms.  In addition,
we've implemented a "rubber sheet" algorithm for scaling images
to any desired size.

An excellent survey article was written by J. F. Jarvis, C. N.
Judice, and W. H. Ninke.  The article, entitled "A survey of
Techniques for the Display of Continuous Tone Pictures on
Bilevel Displays," appeared in Computer Graphics and Image
Processing 5, pp. 13-40, 1976.  These topics are also treated to
some extent in "Fundamentals of Interactive Computer Graphics" by
Foley and Van Dam, and in "Principles of Interactive Computer
Graphics" by Newman and Sproull.

Of the various techniques, ordered dither is the most efficient
computationally, and produces surprisingly good results considering
the simplicity of the method.  The only drawback is the appearance
of a regular pattern in regions of constant intensity.  The
minimized average error techniques (which include the Floyd-Steinberg
algorithm) produce very nice pictures without regular subpatterns,
but tuning the black and white thresholds to obtain a pleasing
result requires somewhat more work.  The constrained average technique
is good for accentuating details, but is probably best used for
improving the appearance of digitized text and line drawings rather
than digitized photographs.

According to Jarvis et al., minimized average error should use at
least 12 neighboring cells for the average error computation, but
Floyd-Steinberg uses fewer than that (although error terms are
propagated).  Has anyone compared these techniques?  Are there any
other techniques which are worth trying?  I'm interested in comparing notes
with other people who are working with these algorithms.

Ultimately, we will provide the ability to incorporate digitized images
within TeX documents, probably using \special.

				Tom Libert
				U of Michigan, EECS
				...ihnp4!umich!tom