v
`
`%
`
`
`
`-P.
`
`
`
`
`
`; %Sec0ndEditi0n
`
`
`
`%i
`
`% Apple1051
`U.S. Pat. 6,470,399
`
`Apple 1051
`U.S. Pat. 6,470,399
`
`

`
`PRINCIPLES AND PRACTICE
`
`James
`
`Foley
`
`The George Washington University
`
`Andries van Dam
`Brown University
`
`Steven K. Feiner
`Columbia ‘University
`
`
`
`Brown University
`
`_
`
`A V
`
`V
`
`ADDISON‘-WESLEY PUBLISHING CMPANYr '
`Reading, Massachusetts 0 Menlo Park, California ‘¢"Ne"v\'/ ‘York
`Don Mills, Ontario 0 Wokingharn, England 0 Amsterdam 9 Bonn
`Sydney 0 Singapore 0 Tokyo 9 Madrid 9 San Juan‘ ’
`‘
`‘
`
`~'
`
`
`
`SECONDA EDITION
`
` omputer Grahics
`
`

`
`P
`
`Sponsoringpligditorz Keith, Vwollman
`1 Production ’/Supervisor: Bette J. Aaronson
`..Copy5 Editor: Difipfé.
`‘
`Text Designer: I-Ierb__Caswell
`Technical Art Consultant: Joseph K. Vetere
`Illustrators: C&C Associates,
`T
`Cover Designer: Marshall Henrichs
`Manufacturing Manager: Roy Logan
`
`2
`
`This book is in the Addison-Wesley Systems Programming-Series L
`Consulting editors: IBM Editorial Board
`
`-Library of Congress Cataloging-in-Publication Data
`Computer graphics: principles and practice/James D. Foley .
`al.].——2nd ed«.
`_
`-
`-
`.
`p.cm.
`\
`Includes bibliographical references. p
`ISBN 0-201-12ll0~7 .
`
`.
`
`. [et
`
`1. Computer graphics.
`T385.C587 1990 .
`006.6~—dc20
`
`I. Foley, James D., 1942-.
`
`89-3528 1
`CIP
`
`Cover.’ “Dutch Interior,” after Vermeer, by J..Wal,lace, M. Cohen, and
`(Copyright © 1987 Cornell University, Program of Computer Graphics.)
`
`Greenberg, Cornell University
`
`‘ Many of the designations used by. mafnufacture"rs-Gland sellers to distinguish their products are claimed as
`trademarks. Where those designations '=appearv in this book, and*Addison—‘Wesley was aware of a trademar
`claim, the designations have been printed _in*init_ial caps or all caps.
`.
`-‘
`
`The programs and applications presented in this book have been included for their instructional value. They are
`not guaranteed for any particular purpose. The publisher and the author do‘ not offer any warranties or
`representations, nor dothey accept any liabilities with respect to the programs or applications.
`
`
`
`Copyright © 1990 by Addison—Wesley Publishing Company, Inc.
`
`All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted,
`in any form or by any rn"e_ansv,— ele“ctronic,*r'nechanica‘l;7 pho,tocopy‘ing,‘recording,‘ or otherwise, without the prior
`- written permission of the publisher. Printed in the.»United. States of America.
`
`ABCDEFGHILDO-943210‘ '_
`
`

`
`
`
`
`
`..LI’.4.‘....._..L._.;;="~
`
`3
`
`l
`
`!
`
`
`
`13
` Achromatic
`and
` Colored Light
`
`
`
`
`
`
`
`The growth of raster graphics has made color and gray scale an integral part of
`contemporary computer graphics. Color is an immensely complex subject, one that draws
`on concepts and results from physics,_physiology, psychology, art, and graphic design.
`Many researchers’ careers have been fruitfully devoted to developing theories, measurement
`techniques, and standards for color. In this chapter, we introduce some of the areas of color
`that are most relevant to computer graphics.
`The color of an object depends not only on the object itself, but also on the light source -
`illuminating it, on the color of the surrounding ‘area, and on the human visual system.
`Furthermore, some objects reflect light (wall, desk, paper), whereas others also transmit
`light (cellophane, glass). When a surface that reflects only pure blue light is illuminated
`with pure red light, it appears black. Similarly, a pure green light viewed through glass that
`transmits only pure red will alsoappear black. We postpone some“ of these issues by
`starting our discussion with achromatic sensations—that is, those described as black, gray,
`and white.
`
`13.1 ACHROVLMATIC LIGHT
`
`Achromatic light is what we see on a black-and-white television set or display monitor. An
`observer of achromatic light normally experiences none of the sensations we associate with
`red, blue, yellow, and so on. Quantity of light is the only attribute of achromatic light.
`Quantity of light can be discussed in the physics sense of energy, in which case the terms
`intensity and luminance are used, or in the psychological sense of perceived intensity, in
`which case the term brightness is used. As we shall discuss shortly, these two concepts are
`
`563
`
`
`
`
`
`
`
`
`
`
`
`w.\\.~.:.r;<<a\.«a,a».\\1I)‘xs~i.l'\I»‘$)i~*§l71«z.w.=»v.‘x;.v.a-.xa,:r«,v»<cg:m~xl;
`
`

`
`564 .
`
`iAchromatic and Colored Light.
`
`related but are not the same. It is useful to associate a scalar with different intensity levels,
`defining,0 as black and 1 as white; intensity levels between 0 and 1 represent different grays.
`A black-and-white television can produce many different intensities at a single pixel
`position. Line printers, pen plotters, and electrostatic plotters produce only two levels: the
`white (or light gray) of the paper and the black (or dark gray) of the ink or toner deposited
`on the paper. Certain techniques, discussed in later sections, allow such inherently bilevel
`‘devices to produce additional intensity levels.
`
`1 3.1.1 Selecting .|ntensities——Gamma Correction
`
`Suppose we want to display 256 different -intensities. Which 256 intensity levels should we
`use? We surely do not want 128 in the range of 0 to 0.1 and 128 more in the range of 0.9 to"
`1.0, since the transition from 0.1 to 0.9 would certainly appear discontinuous. We might
`initially distribute the levels evenly over the range 0 to 1, but this choice. ignores an
`important characteristic of the eye: that it is sensitive to ratios of intensity levels rather than
`to absolute values of intensity. That is, we.perceive the intensities 0.10 and 0.1 1 as differing
`just as much as the intensities 0.50 and 0.55, (This nonlinearity is easy to observe; Cycle
`through the settings on a three-way 50—l00——150-watt lightbulb; you will see that the step
`from 50 to 100 seems much greater than the step from 100 to 150.) On a brightness (that is,
`perceived intensity) scale, the differences between intensities of 0. 10 and 0.11 and between _
`intensities of 0.50 and 0.55 are equal. Therefore, the intensity levels should be spaced
`logarithmically rather than linearly, to achieve equal steps in brightness.
`To find 256 intensities starting with the lowest attainable intensity I0 and going to a
`maximum intensity of 1.0, with each intensity r times higher than the preceding intensity,
`we use the following relations:
`'
`
`1, = 10,1, = r10, 1, = r1, = r210, 13 = r1, = r310,
`
`.
`
`.
`
`.,1,5, = r255I.,'= 1.
`
`(13.1)
`
`Therefore,
`
`_
`
`r =.(1/1,)1'355,1,. = M1,’, = (1/1,)i/255 1, = 1,<-255-M55 .
`and in general for n + 1 intensities,
`
`for 0 s, ,- s 255,
`\/
`
`(13.2)
`
`r = (1/I0)“,
`
`= I0‘"‘J7’”
`
`for 0 .<_ j _<_ n.
`
`_
`
`'
`
`(13.3)
`
`With just four intensities (n = 3) and an 10 of 31; (an unrealistically large value chosen for
`illustration only), Eq. (13.3) tells us that r = 2, yielding intensity values 01%, }, 7%-, and 1.
`The minimum attainable intensity In for a CRT is anywhere from about2—(1,5up tofgof the
`maximum intensity of 1.0. Therefore, typical values of 10 are between"0.005 and 0.025.
`The minimum is not 0, because of light reflection from the phosphor within the CRT. The
`ratio between the maximum and mimimum intensities is called the dynamic range. The
`exact value for_a specific CRT can be found by displaying a square of white on a field of
`black and measuring the two intensities with a photometer. This measurement is taken in a
`completely darkened room, so that reflected ambient light does not affect the intensities.
`With an IQ of 0.02, corresponding to a dynamic range of 50, Eq. (13.2) yields r =
`1.0154595 .
`.
`., and the first few and last two intensities of the 256 intensities from Eq.
`(13.1) are 0.0200, 0.0203, 0.0206, 0.0209, 0.0213, 0.0216, .
`.
`., 0.9848, 1.0000.
`vs
`
`

`
`13.1
`
`-
`
`‘
`
`Achromatic Light
`
`565
`
`Displaying the intensities defined by Eq. (13.1) _on a CRT is a tricky process, and
`recording them. on film is even more diflicult, because of the nonlinearities. in the CRT and
`film. For instance, the intensity of light output by a phosphor is related to the number of
`‘-(
`electrons. N in the beam by
`
`(13.4)
`1-
`V
`‘
`1=I;Nv‘
`for constants k and 7. The value of 'y is in the range 2.2 to 2.5 for most CRTs. The number
`of electrons N is proportional -to the control—grid voltage, which is in turn proportional to
`the value V specified for the pixel. Therefore, for some other constant K,
`
`I = Kw, or V = (1)K)1'v.
`
`_
`
`V
`
`.
`
`(13.5)
`
`Now, given a desired intensity I, we first determine the nearest by searching through a
`table of_the available intensities as calculated from Eq. (13.1) or from’ its equivalent:
`j = R0UND(log,(I/10)).
`,
`'
`(13.6)
`
`After j is found, we calculate
`
`R
`
`Ij '—“j rjlo.
`(13.7)
`The next step is to determine the pixel value
`needed to create the intensitylij-, by using Eq.
`( 1 3 . 5):
`
`l/j=.R0UND((I,;/[Q1/V);
`
`.
`
`(13.8)
`
`is placed in the appropriate -pixels. If there
`If the raster display has nolook-up table, then
`is a look-up table, then j_is placed in the pixel and
`is placed in entry j of the table.
`The values of K, 7, and I0 depend on the CRT in use, so in practice thelook-up table is
`loaded by a method based on actual measurement of intensities [CATM79; COWA83;
`HALL89]. Use of the look-up table in this general manner is called gamma correction, so
`named forhthe exponent in
`(13.4). If the display has hardware gamma correction, then
`rather‘ than
`is placed in either the ‘refreshpbuifer or 1ook—up_tablex.r
`V Without the use of ratio-based intensity values and gamma correction, quantization
`errors "(from approximating a true intensity value with a displayable intensity value) will be
`more conspicuous near black than near white. ‘For instance, with 4 bits and ‘hence 16‘
`intensities, a quantization round-off error of as much) as E = 0.031 is possible.‘ This is 50
`percent of intensity value 3%, and only 3 percent of intensity value 1.0. Using the ratio-based
`intensities and gammacorrection, the maximum quantization error as a percentage of I
`brightness (perceived intensity) is constant.
`A natural question is, “How many intensities are enough?” By “enough,”Zwe mean.
`the number needed to reproduce a continuous-tone black-and-white image such: that the
`reproduction appears to be continuous. This appearance is achieved when the ratio r is 1.01
`or less (below this ratio,
`the eye cannot distinguish between intensities Ij and 11-“)
`[WYSZ82, p. 569]. Thus, the appropriate value for n, the number of intensity ‘levels, is
`found by equating r to 1.01 in Eq. (13.3):
`R
`
`r = (1/I0)1’“
`
`or
`
`1.01 = (1/I0)1’’‘.
`
`.
`
`(13.9) V
`
`

`
`566
`
`Achromatic and Colored Light
`
`TABLE 13.1 DYNAMIC RANGE (1/I0) AND NUMBER OF REQUIRED INTENSITIES,
`
`n = logw1(1/I0) FOR SEVERAL DISPLAY MEDIA
`Display media Number of intensities, n
`Typical dynamic range.
`CRT
`50~200
`400-530
`
`
`
`465
`100
`Photographic prints
`700
`1000
`Photographic slides
`465
`100 V
`Coated paper printed in B/W*
`Coated paper printed in color
`50
`.
`400
`
`Newsprint printed in B/W
`10
`234
`
`'
`
`*B/W = black and white.
`
`2
`
`Solving for n gives
`
`n = log1_o1(l/I0),
`
`_
`
`(13.10)
`
`gwhere 1/10 is the dynamic range of the device.
`The dynamic range 1/10 for several display media, and the corresponding n, which is the
`number of intensity levels needed to maintain r = 1.01 and at the same time to use the full
`dynamic range, are shown in Table 13.1. These are theoretical values, assuming perfect
`reproduction processes. In practice, slight blurring due to ink bleeding and small amounts
`of random noise in the reproduction decreases n considerably for print media. For instahce,
`Fig. 13.1 shows a continuous—tone photograph; and the succeeding five Figs. 13.2 to 13.6
`reproduce the same photograph at 4, 8, 16, 32, and 64 intensity levels. With four and eight
`levels,
`the transitions or contours between one intensity level and the next are quite
`conspicuous, because the ‘ratio r between successive intensities is considerably greater that
`the ideal 1.01. Contouring is barely detectable with 64 levels, and for_ these particular
`
`
`
`Fig. 13.1 A continuous—tone photo—
`graph.
`
`Fig. 13.2 A continuous—tone photo-
`graph reproduced with four intensity
`levels. (Courtesy of Alan Paeth, Uni-
`versity of Waterloo Computer Graph-
`ics Lab.)
`
`
`
`

`
`13.1
`
`Achromatic Light
`
`567
`
`
`
`
`
`Fig. 13.3 A continuous—tone photo-
`graph reproduced with eight intensity
`levels. (Courtesy of Alan Paeth, Uni-
`versity of Waterloo Computer Graph—
`ics Lab.)
`
`Fig. 13.4 A continuous—tone photo-
`graph reproduced” with 16 intensity
`levels. (Courtesy of Alan Paeth, Uni-
`versity of Waterloo Computer Graph—
`ics Lab.)
`
`
`
`Fig. 13.5 A continuous—tone photo-
`graph reproduced with 32 intensity
`levels. (Courtesy of Alan Paeth, Uni-
`versity of Waterloo Computer Graph—
`ics Lab.)
`
`
`
`Fig. 13.6 A continuous—tone photo-
`graph reproduced with 64 intensity
`levels. Differences from the picture in ‘
`Fig. 13.5 are quite subtle. (Courtesy
`of Alan Paeth, University of Waterloo
`Computer Graphics Lab.)
`
`images disappears with 64. This suggests that 64 intensity levels is the absolute minimum
`needed for contour-free printing of continuous-tone black-and-white images on paper such
`as is used in this book. For a well—adjusted CRT in a perfectly black room, however, the
`higher dynamic range means that many more levels are demanded.
`
`

`
`
`
`‘
`
`568
`
`Achromatic and Colored Light
`
`J
`
`I
`.0
`9
`0.0.9 0
`
`‘.o.vvo00000v0.0.0.9
`
`\
`
`Fig. 13.7 Enlarged halftone pattern. Dot sizes vary inverselywith intensity original
`photograph. (Courtesy of Alan Paeth, University of Waterloo Computer Graphics Lab.)
`
`13.1.2 Halftone Approximation
`
`_Many displays and hardcopy devices are bilevel——they produce just, two intensity
`levels~——and even 2- or 3-bit-per—pixel raster displays produce fewer intensity levels than we
`might desire. How can we expand the range of available intensities? The answer lies in the
`‘spatial integration that our eyes perform. If we view a very small area from a sufiiciently
`large viewing distance, our eyes average fine detail within the small area and record only the
`overall intensity of the area.
`This phenomenon is exploited in printing black-and-white photographs in newspapers,
`magazines, and books, in a technique called halftoning (also called clustered-dot ordered
`dither‘ in computer graphics). Each small resolution unit is imprinted with a circle of black
`ink whose area is proportional to the blackness 1 - I (where I = intensity) of thearea in the
`original photograph. Figure 13.7 shows part of aahalftone pattern, greatly enlarged.” Note
`that the pattern makes a 45° angle with the horizontal, called the screen angle. Newspaper
`halftones use 60 to 80 variable-sized circles per inch, whereas halftones in magazines and
`books use 150 to'200 per inch.
`
`
`
`_ five different intensity levels at the cost of halving the spatial resolution along each axis. The
`patterns shown in Fig. 13.8 can be used to fill the 2’ X 2 areas with the number of “on”.
`pixels that is proportional to the desired intensity. Figure 13.9 shows a face digitized as a
`.351 X 351 image array and displayed with 2 X 2 patterns.
`An n‘ ‘X n group of bilevel pixels can provide n2 + 1 intensity levels. In general, there is
`a tradeoff between spatial resolution and intensity resolution. The use of a 3 X 3 pattern
`
`
`‘The “ordered dither” contrasts with “random dither,” an infrequently used technique.
`
`“* ""-'.~T>.<''*’r,“'.”-;‘»S<*1“.°=''
`
`‘
`
`

`
`13.1
`
`Achromatic Light
`
`569‘
`
`
`
`Fig. 1 3.8 Five intensity levels approximated with four 2 X 2 ditlier patterns.
`
`cuts spatial resolution by one—third on each axis, but provides 10 intensity levels. Of course,
`the tradeoff choices are limited-by our visual acuity (about
`1 minute of arc in normal
`lighting), the distance from which the image is viewed, and the dots-per-inch resolution of
`the graphics device.
`C
`One possible set of patterns for the 3 X 3 case is shown in Fig. 13.10. Note that these
`1-
`patterns can be represented by the dither matrix
`A
`
`6
`
`1
`5
`
`8
`
`0
`2
`
`4
`
`3 .
`7
`
`(13.11)
`
`.
`
`To display an intensity I, we turn on all pixels whose values are less than I.
`’
`The n X n pixel patterns used to approximate the halftones must be designed not to
`introduce visual artifacts in _an area of identical intensity values. For instance, if the pattern
`in Fig. 13. ll were used, rather than the one in Fig. 13.10, horizontal lines would appear in
`any large area of the image of intensity 3. Second, the patterns must form a growth sequence
`so that any pixel intensified for intensity level j is also intensified for"all_levels k > j. This
`minimizes the differences in the patterns for successive intensity levels, thereby minimizing
`the contouring effects. Third, thepatterns must grow outward from the center, to create the
`effect of increasing dot size. Fourth, for hardcopy devices such as laser printers and film
`recorders that are poor at reproducing isolated “on” pixels, all pixels that are “on” for a
`
`
`
`\
`
`Fig. 13.9 A continuous-tone photograph, digitized to a resolution of 351 X 351 and
`displayed using the 2 X 2 patterns of Fig. 13.8. (Courtesy of Alan Paeth, University of
`Waterloo Computer Graphics Lab.)
`
`
`
`

`
`570
`
`Achromatic and Colored Light
`
`
`
`Fig, 13.10 Ten intensity levels approximated with 3 X 3 dither patterns.
`
`particular intensity must be adjacent to other “on” pixels; a pattern such as that in Fig.
`13.12 is not acceptable. This is the meaning of the term clustered—dot in “clustered-dot
`ordered dither.” Holladay [HOLL80] has developed a widely used method for defining
`dither matrices for clustered-dot ordered dither. For high-quality reproduction of images, n ’
`must be 8 to 10, theoretically allowing 65 to 101 intensity levels. To achieve an effect
`equivalent to the 150-circle-per-inch printing screen, we thus require a resolution of from
`150 X 8 = 1200 up to 150 X 10 = 1500 pixels per inch. High-quality film recorders can
`attain this resolution, but cannot actually show all the intensity levels because patterns made
`up of single black or white pixels may disappear.
`1
`.
`.
`Halftone approximation is not limited to bilevel displays. Consider a display with 2 bits
`per pixel and hence four intensity levels. The halftone technique can be usednto increase the ‘
`number of intensity levels. If we use a 2 X 2 pattern, we have a total of 4 pixels at our
`disposal, each of which can take on three values besides black; this allows us to display 4 X
`- 3 + 1 = 13 intensities. One possible set of growth sequence patterns in this situation is
`shown in Fig. 13.13.
`Unlike a laser printer, a CRT display is quite able to display individual dots. Hence, the N
`clustering requirement on the patterns’ discussed previously can be relaxed and dispersed-dot
`ordered dither can be used. There are many possible dither matrices: Bayer [BAYE73] has
`developed dither matrices that minimize the texture introduced into the displayed images.
`For the 2 X 2 case, the dither matrix, called D9’, is
`
`(13.12i
`
`D<2> = [0 2].
`
`
`
`Fig. 13.11 A 3 X 3 dither pattern inappropriate for halftoning.
`
`

`
`
`
`Achromatic Light
`
`571
`
`Fig. 1 3.12 Part of a 4 X 4 ordered dither dot pattern in which several of the patterns
`have single, nonadjacent dots. Such disconnected patterns are unacceptable for
`halftoning on laser printers and for printing presses.
`
`This represents the set of patterns of Figure 13.8.
`Larger dither matrices can be found using a recurrence relation [JUDI74] to compute A
`De") from D""’. With U“) defined as an n X n matrix of ls, that is,
`
`U"‘)=
`
`v
`
`1
`
`1
`
`1
`
`i
`
`1
`
`1
`
`1
`
`i
`
`1
`
`1
`
`i
`
`1
`
`1
`
`i Q.
`
`,
`
`1
`
`(13.13)
`
`the recurrence relation is
`
`Dm, = 4DW2> + D?,gLIW2>
`4DW2> + D‘123U‘"’2’
`
`4D"”2’+,DE?1’U"”2’_
`4DW2> + D<fi>UW2>
`
`'
`
`(13 14)
`‘
`
`s
`
`Applying this relation to D“) produces
`
`D‘4?=
`
`0
`
`12
`3
`15
`
`8
`
`4
`11
`7
`
`2
`
`14
`I
`13
`
`10
`
`6
`9
`5
`
`.
`
`(13.15)
`
`I The techniques presented thus far have assumed that the image array being shown is smaller
`than the display device’s pixel array, so that multiple display pixels can be-, used for one
`
`
`
`
`I I
`3 E
`2
`4
`5
`ye
`
`3
`
`Fig. 13.13 Dither patterns for intensity levels 0 to 13 approximated using 2 X 2
`patterns of pixels, with 2 bits (four intensity levels) per pixel. The intensities of the
`individual pixels sum to the intensity level for each pattern.
`
`...._
`
`
`
`

`
`:4
`
`
`
`..._........._..,...--.......__................._._.§"£i
`
`572
`
`Achromatic and Colored Light
`
`image pixel. What if the image and display device arrays are the same size? A simple
`adaptation of the ordered-dither (either clustered-dot or dispersed-dot) approach can‘ be
`used. Whether or not to intensify the pixel atpoint (x, y) depends on the desired intensity
`S(x, y) at that point and on the dither matrix. To display the point at (x, y), we cogxpute
`i = x modulo n’,
`j = y modulo :1.
`
`(13.16)
`
`'
`
`Then, if
`
`S(x, y) > D9‘),
`
`(13.17)
`
`1 pixel in the image array
`the point at (x, y) is intensified; otherwise, it is not. That is,
`controls 1 pixel in the display array. Notice that large areas of fixed image intensity are
`displayed exactly as when the image-array size is less than the display-array size, so the
`effect of equal image and display arrays is apparent only in areas where intensity varies.
`Figure 13. l4(a) is a face digitized at 512 X 512 and shown on a 512 X 512 bilevel
`display using D“). Compare this bilevel result to the multilevel pictures shown earlier in this
`section. Further pictures displayed by means of ordered dither appear in [JARV76a;
`JARV76b; ULIC87], where more ways to display continuous-tone images on bilevel
`displays are described.
`'
`Error dzfiitsion, another way to handle the case when the imagexagnd display. array sizes
`are equal, was developed by Floyd and Steinberg [FLOY75]; its visual results are often
`satisfactory. The error (i.e.,
`the- difference between the exact pixel Value and the
`approximated value actually displayed) is added to the values of the four image-array pixels
`to the right of and below the pixel’ in question: 116 of the error to the pixel to the right, to
`the pixel below and to the left, {(7 to the pixel immediately below, aI1d”1lgtO the pixel below
`
`
`
`(a)
`
`
`
`1
`
`A
`
`(6) i.
`
`Fig. 13.14 A continuous-tone photograph reproduced with (a) D‘‘’’ ordered dither, and
`(b) Floyd—Steinberg error diffusion. (Courtesy of Alan Paeth, University of Waterloo
`Computer Graphics Lab.) 1
`
`E"':w*?"’W’!"“""*‘*1""*7*~~r~r'~?“":“""—1”"'
`
`'~"=r"*‘ " '“ "
`
`

`
`13.1
`
`I
`
`Achromatic Light
`
`573
`
`and to the right. This has the effect of spreading, or diffusing-, the error over several pixels in
`the image array. Figure 13.14(b) was created using this method.
`Given a picture S to be displayed in the intensity matrix I, the modified values in S and
`the displayed values in I are computed as follows:
`
`K := Approximate(S[x, y]);
`I[x, y] := K;
`error := S[x, y] - K;
`
`{Approximate S to nearest displayable intensity.}
`{Draw the pixel at (x, y).}
`{Error term}
`A
`
`I {Step 1: spread T76-of error into the pixel to the right, at (x + 1, y).}
`S[x +1, y] := S[x + l, y]. + 7 * error /16;
`
`‘ {Step 2: spread 33% of error into pixel below and to the left.}
`S[x -1, y - 1] := S[x - 1, y - 1] + 3 * error,/16;
`
`{Step 3: spread $7 of error into pixel below.}
`S[x, yX- 1] := S[x, y-- 1] + 5 * error /16;
`{Step 4: spread
`of error below and to the right.}
`S[x +1, y - 1] := S[x¢+1=, y -1]+ error /16
`
`To avoid ‘introducing visual artifacts into the displayed image, we must ensure that the four
`errors sum exactly to error; no roundoif errors can be allowed. This can "be done by
`calculating the step 4 error term _as error minus the error terms from the first three steps.
`The function Approximateretums the displayable intensity value closest to the actual pixel
`value. For a bilevel display, the value of S is simply rounded "to O or 1.
`'
`’
`.
`{Even better results can be obtained by alternately scanning left to right and right to left;
`on a right-to-left scan, the left——right directions for""e*rrors.in* steps 1, 2, and 4 arereversed.
`For adetailed discussion of this and other error-dilfusion methods, see [ULIC87]. Other
`approaches are discussed in [KNUT87].
`'
`’ Suppose the size of the image array is less‘ than the size of the display array, the number
`of intensities in the image and display are equal, and we wish tordisplay the image at the size
`of the display array. A simple case of this is an 8-bit-per-pixel, 512 X 5112 image and an
`8-bit-per-pixel,‘ 1024 X 1024 display. If we simply replicate image pixels horizontally and
`vertically in "the display array, the replicated pixels on the display will form squares that are
`quite obvious to the eye. To avoid this problem, we can interpolate intensities to calculate
`the pixel values. For instance, if an image S is to be displayed at double resolution, then the
`intensities I to display (with Jr = 2x’ and y = 2y’) are
`
`I[x. y] ’
`
`:= Six’, y’];,
`
`I[x + 1, y]
`
`'
`
`:= -%(S[x', y'] + S[x’ + 1, y']);
`
`‘ I[x, y + 1}
`
`:= §(s[x', y'] + S[x’, y’ + 1]);
`
`I[x + 1, y.+ l]:= ri(S[x’, y’] + S[x’ + 1, y'] + S[x’, y’- + 1] + S[x’ + 1, y’ + 1]).
`
`See Section 117.4 for a discussion of two-pass scaling transformations of images, and
`Section 3.17 for a description of the filtering and image-reconstruction techniques that are
`applicable to this problem.
`
`
`
`
`
`
`g?
`
`5.
`
`% +
`
`5.