When models of human vision adequately measure
the relative quality of candidate halftonings of an
image, the problem of halftoning the image becomes
equivalent to the search problem of finding a halftone
that optimizes the quality metric.
Because of the vast number of possible
halftones, and the complexity of image quality measures,
this principled approach has usually been put aside in
favor of fast algorithms that seem to perform well.
We find that the principled approach can lead
to a range of useful halftoning algorithms, as we trade off
speed for quality by varying the complexity of the
quality measure and the thoroughness of the search.
High quality halftones can be obtained reasonably quickly,
for example, by using as a measure the vector length of
the error image filtered by a contrast sensitivity function,
and, as the search procedure, the sequential adjustment
of individual pixels to improve the quality measure.
If computational resources permit, simulated annealing can
find nearly optimal solutions.
The problem of halftoning a gray scale image is the problem of
finding a binary image which appears as similar as possible
to the gray scale image.
This problem can be broken down into two parts:
first, we must find a measure which captures the "similarity"
of two images; then, after we have done this, we must
be able to find the binary image which maximizes this
"similarity."
In order to be useful, a measure of similarity between two images must incorporate our knowledge of the human visual system. To illustrate the importance of this, we first consider a simple metric that does not do this, namely the familiar root-mean-square (RMS) error. At this point, we .nr 99 \n(.s .nr 98 \n(.f .rm 11 .as 11 "introduce some notation: let .ps 14 .ft 2 .ft 1 .ds 12 "g .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .ds 12 \x'0'\f2\s14\*(12\s\n(99\f\n(98\x'9u' .as 11 \*(12 .ps \n(99 .ft \n(98 .as 11 " represent the value of the .ps \n(99 .ft \n(98 \*(11 .nr 99 \n(.s .nr 98 \n(.f .rm 11 .as 11 "gray-level image .ps 14 .ft 2 .ft 3 .ds 12 "g .ds 12 \f3\*(12\f2 .ft 2 .ds 12 \x'0'\f2\s14\*(12\s\n(99\f\n(98 .as 11 \*(12 .ps \n(99 .ft \n(98 .as 11 " at the .ps 14 .ft 2 .ds 12 "i .ds 12 \x'0'\f2\s14\*(12\|\s\n(99\f\n(98 .as 11 \*(12 .ps \n(99 .ft \n(98 .as 11 "th pixel (we use the single index .ps 14 .ft 2 .ds 12 "i .ds 12 \x'0'\f2\s14\*(12\|\s\n(99\f\n(98 .as 11 \*(12 .ps \n(99 .ft \n(98 .as 11 " .ps \n(99 .ft \n(98 \*(11 to represent the two dimensions of spatial position to simplify .nr 99 \n(.s .nr 98 \n(.f .rm 11 .as 11 "the following expressions). Similarly, let .ps 14 .ft 2 .ft 1 .ds 12 "h .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .ds 12 \x'0'\f2\s14\*(12\s\n(99\f\n(98\x'9u' .as 11 \*(12 .ps \n(99 .ft \n(98 .as 11 " represent the .ps \n(99 .ft \n(98 \*(11 quantized value of the corresponding pixel in the output .nr 99 \n(.s .nr 98 \n(.f .rm 11 .as 11 "halftone image .ps 14 .ft 2 .ft 3 .ds 12 "h .ds 12 \f3\*(12\f2 .ft 2 .ds 12 \x'0'\f2\s14\*(12\s\n(99\f\n(98 .as 11 \*(12 .ps \n(99 .ft \n(98 .as 11 ". We assume that .ps 14 .ft 2 .ds 12 "\(mi .ds 13 "\f11\fP .as 12 "\*(13 .ds 13 "\| .as 12 "\*(13 .ds 13 "\(<= .as 12 "\*(13 .ds 13 "\| .as 12 "\*(13 .ft 1 .ds 13 "g .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 12 "\*(13 .ds 13 "\(<= .as 12 "\*(13 .ds 13 "\| .as 12 "\*(13 .ds 13 "\f11\fP .as 12 "\*(13 .ds 12 \x'0'\f2\s14\*(12\s\n(99\f\n(98\x'9u' .as 11 \*(12 .ps \n(99 .ft \n(98 .as 11 ", .ps \n(99 .ft \n(98 \*(11 .nr 99 \n(.s .nr 98 \n(.f .rm 11 .as 11 "and .ps 14 .ft 2 .ft 1 .ds 12 "h .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .ds 13 "\| .as 12 "\*(13 .ds 13 "\(eq .as 12 "\*(13 .ds 13 "\| .as 12 "\*(13 .ds 13 "\(+- .as 12 "\*(13 .ds 13 "\f11\fP .as 12 "\*(13 .ds 12 \x'0'\f2\s14\*(12\s\n(99\f\n(98\x'9u' .as 11 \*(12 .ps \n(99 .ft \n(98 .as 11 ". We define .ps 14 .ft 2 .ft 1 .ds 12 "e .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .ds 12 \x'0'\f2\s14\*(12\s\n(99\f\n(98\x'9u' .as 11 \*(12 .ps \n(99 .ft \n(98 .as 11 " to be the .ps \n(99 .ft \n(98 \*(11 .ul local error: .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ft 1 .ds 11 "e .ds 11 \f1\*(11\f2 .ft 2 .ds 12 "i .as 11 \v'24u'\s-3\*(12\s+3\|\v'-24u' .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "h .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(mi .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "g .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 ". .as 11 "\*(12 .ds 11 \x'0'\f2\s14\*(11\s\n(99\f\n(98\x'9u' .nr 11 \w'\*(11' .nr MK 0 .if 108>\n(.v .ne 108u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "The total squared error, .ps 14 .ft 2 .ds 13 "\(*c .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", is simply: .ps \n(99 .ft \n(98 \*(12 .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ds 11 "\(*c .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .ds 12 \k(97\*(12 .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 13 "i .nr 12 \w'\s14\*(12' .nr 14 \n(12 .nr 13 \w'\s11\*(13' .if \n(13>\n(14 .nr 14 \n(13 .ds 14 \v'90u'\h'\n(14u-\n(13u/2u'\s11\*(13\s14\h'-\n(14u-\n(13u/2u'\v'-90u'\ \h'\n(14u-\n(12u/2u'\*(12\h'\n(14u-\n(12u/2u'\ .as 11 "\*(14 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "e .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .ds 14 "\f12\fP .as 13 \| .nr 13 \w'\s11\*(13' .ds 14 \|\*(14 .nr 14 \w'\s11\*(14' .nr 15 \n(14 .if \n(13>\n(15 .nr 15 \n(13 .as 12 \v'24u'\s11\*(13\h'-\n(13u'\v'-57u'\ \s11\*(14\h'-\n(14u+\n(15u'\s14\v'33u' .as 11 "\*(12 .ds 12 "\f1,\fP .as 11 "\*(12 .ds 11 \x'0'\f2\s14\*(11\s\n(99\f\n(98\x'75u' .nr 11 \w'\*(11' .nr MK 1 .if 189>\n(.v .ne 189u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN .EQ I (1) .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ds 11 \h'|\n(97u' .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(mi .as 11 "\*(12 .ds 12 "\f12\fP .as 11 "\*(12 .ds 12 "\| .as 11 "\*(12 .ds 12 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 13 "i .nr 12 \w'\s14\*(12' .nr 14 \n(12 .nr 13 \w'\s11\*(13' .if \n(13>\n(14 .nr 14 \n(13 .ds 14 \v'90u'\h'\n(14u-\n(13u/2u'\s11\*(13\s14\h'-\n(14u-\n(13u/2u'\v'-90u'\ \h'\n(14u-\n(12u/2u'\*(12\h'\n(14u-\n(12u/2u'\ .as 11 "\*(14 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "h .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\| .as 11 "\*(12 .ft 1 .ds 12 "g .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(pl .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 13 "i .nr 12 \w'\s14\*(12' .nr 14 \n(12 .nr 13 \w'\s11\*(13' .if \n(13>\n(14 .nr 14 \n(13 .ds 14 \v'90u'\h'\n(14u-\n(13u/2u'\s11\*(13\s14\h'-\n(14u-\n(13u/2u'\v'-90u'\ \h'\n(14u-\n(12u/2u'\*(12\h'\n(14u-\n(12u/2u'\ .as 11 "\*(14 .ds 12 "\| .ds 13 "\f11\fP .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 13 "\(pl .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ft 1 .ds 13 "g .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .ds 15 "\f12\fP .as 14 \| .nr 14 \w'\s11\*(14' .ds 15 \|\*(15 .nr 15 \w'\s11\*(15' .nr 16 \n(15 .if \n(14>\n(16 .nr 16 \n(14 .as 13 \v'24u'\s11\*(14\h'-\n(14u'\v'-57u'\ \s11\*(15\h'-\n(15u+\n(16u'\s14\v'33u' .as 12 "\*(13 .ds 13 "\| .as 12 "\*(13 .ds 12 \|\v'-4u'\b'\(lt\(lb'\v'4u'\*(12\|\v'-4u'\b'\(rt\(rb'\v'4u' .as 11 "\*(12 .ds 12 ". .as 11 "\*(12 .ds 11 \x'0'\x'0-23u'\f2\s14\*(11\s\n(99\f\n(98\x'75u' .nr 11 \w'\*(11' .nr MK 1 .if 212>\n(.v .ne 212u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN To obtain the RMS error, we divide this quantity by the number of pixels and take the square root. Because this is a monotonic .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "transformation of .ps 14 .ft 2 .ds 13 "\(*c .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", any halftone image .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " which minimizes the RMS error .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "must also minimize .ps 14 .ft 2 .ds 13 "\(*c .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ". .ps \n(99 .ft \n(98 \*(12 .br .sv 3.5i .os .nr PS 10 .nr VS 12 .RT Figure 1: a) Original "lenna" test image. b) Result of independent pixel quantization against a fixed threshold. This image has minimal RMS error, but is a poor visual representation. .nr PS 12 .nr VS 14 .PP .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "We can see how to choose .ps 14 .ft 2 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " to minimize .ps 14 .ft 2 .ds 13 "\(*c .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " by inspection of equation (1); .ps \n(99 .ft \n(98 \*(12 the second sum is a constant whose value depends only on the input image. .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "(Note that .ps 14 .ft 2 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .ds 15 "\f12\fP .as 14 \| .nr 14 \w'\s11\*(14' .ds 15 \|\*(15 .nr 15 \w'\s11\*(15' .nr 16 \n(15 .if \n(14>\n(16 .nr 16 \n(14 .as 13 \v'24u'\s11\*(14\h'-\n(14u'\v'-57u'\ \s11\*(15\h'-\n(15u+\n(16u'\s14\v'33u' .ds 14 "\| .as 13 "\*(14 .ds 14 "\(eq .as 13 "\*(14 .ds 14 "\| .as 13 "\*(14 .ds 14 "\f11\fP .as 13 "\*(14 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", since .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .ps 14 .ft 2 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 14 "\| .as 13 "\*(14 .ds 14 "\(eq .as 13 "\*(14 .ds 14 "\| .as 13 "\*(14 .ds 14 "\(+- .as 13 "\*(14 .ds 14 "\f11\fP .as 13 "\*(14 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ".) Now if the product .ps 14 .ft 2 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ft 1 .ds 14 "g .ds 14 \f1\*(14\f2 .ft 2 .ds 15 "i .as 14 \v'24u'\s-3\*(15\s+3\|\v'-24u' .as 13 "\*(14 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " is positive, then .ps \n(99 .ft \n(98 \*(12 the corresponding term in the first sum acts to decrease the value .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "of .ps 14 .ft 2 .ds 13 "\(*c .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", while if it is negative then .ps 14 .ft 2 .ds 13 "\(*c .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " is increased. Therefore .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "we minimize .ps 14 .ft 2 .ds 13 "\(*c .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " by choosing .ps 14 .ft 2 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " to have the same sign as .ps 14 .ft 2 .ft 1 .ds 13 "g .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", i.e. .ps \n(99 .ft \n(98 \*(12 .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ft 1 .ds 11 "h .ds 11 \f1\*(11\f2 .ft 2 .ds 12 "i .as 11 \v'24u'\s-3\*(12\s+3\|\v'-24u' .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .ds 12 \k(97\*(12 .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f11\fP .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f1if\fP .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "g .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(>= .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f10\fP .as 11 "\*(12 .ds 12 "\f1,\fP .as 11 "\*(12 .ds 11 \x'0'\f2\s14\*(11\s\n(99\f\n(98\x'9u' .nr 11 \w'\*(11' .nr MK 1 .if 108>\n(.v .ne 108u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ds 11 \h'|\n(97u' .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(mi .as 11 "\*(12 .ds 12 "\f11\fP .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f1if\fP .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "g .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "< .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f10\fP .as 11 "\*(12 .ds 12 ". .as 11 "\*(12 .ds 11 \x'0'\f2\s14\*(11\s\n(99\f\n(98\x'9u' .nr 11 \w'\*(11' .nr MK 1 .if 108>\n(.v .ne 108u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN This rule applies a fixed threshold to each image pixel. The result obtained when this procedure is applied to the "lenna" test image is shown in figure 1(b). It is obvious that this image is not a very good representation of the original. Edges and lines are key elements in visual perception; the image in figure 1(b) has obliterated many edges while introducing strong false contours at the "zero crossings." .PP A number of halftoning algorithms have been developed that produce results which are visually superior to the simple threshold procedure we have just considered; a good summary can be found in the recent book\*([.1\*(.] by Ulichney. Most of the methods commonly in use, however, were not derived from first principles of vision, but rather are clever algorithms that are computed easily and produce visually pleasing results. .NH 1 THEORETICAL FRAMEWORK .PP We begin by noting that all errors are not equally visible. The contrast sensitivity function\*([.2\*(.] (CSF) describes the detectability of sinusoidal signals on a uniform background, and can be used to predict the visibility of near-threshold quantization errors produced when we are halftoning a uniform gray region. While this simple model for the visibility of errors may not be completely accurate for regions where the target image is .ul not uniform,\*([.3\*(.] it is nevertheless a good starting point. The contrast sensitivity function (CSF) describes the visibility of signals as a function of spatial frequency; for each spatial frequency and orientation, the sensitivity is defined to be the reciprocal of the contrast of the weakest signal that can be seen. Obviously, we are not concerned with errors which cannot be seen; therefore it makes sense to consider, .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "instead of the raw error .ps 14 .ft 2 .ft 1 .ds 13 "e .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", the error filtered to weight .ps \n(99 .ft \n(98 \*(12 frequencies according to their detectability. We now consider the space domain representation of the CSF. The CSF can be represented in the space domain by a linear shift invariant filter; the detectability of the quantization error can be estimated from the degree to which it excites this filter. The CSF itself only specifies the amplitude spectrum of the filter; to uniquely determine the filter we assume that it introduces no spatial phase shifts. .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "We will use the symbols .ps 14 .ft 2 .ft 1 .ds 13 "f .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " to refer to the value of this .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "filtered error at the .ps 14 .ft 2 .ds 13 "i .ds 13 \x'0'\f2\s14\*(13\|\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 "th pixel. We also introduce .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .ps 14 .ft 2 .ft 1 .ds 13 "w .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .ds 15 "\f1,\fP .as 14 "\|\*(15 .ds 15 "\| .as 14 "\*(15 .ds 15 "\^j .as 14 "\*(15 .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " to represent the filter weight with which the error from .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "the .ps 14 .ft 2 .ds 13 "\^j .ds 13 \x'0'\f2\s14\*(13\|\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 "th pixel, .ps 14 .ft 2 .ft 1 .ds 13 "e .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "\^j .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", contributes to .ps 14 .ft 2 .ft 1 .ds 13 "f .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ": .ps \n(99 .ft \n(98 \*(12 .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ft 1 .ds 11 "f .ds 11 \f1\*(11\f2 .ft 2 .ds 12 "i .as 11 \v'24u'\s-3\*(12\s+3\|\v'-24u' .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 13 "\^j .nr 12 \w'\s14\*(12' .nr 14 \n(12 .nr 13 \w'\s11\*(13' .if \n(13>\n(14 .nr 14 \n(13 .ds 14 \v'90u'\h'\n(14u-\n(13u/2u'\s11\*(13\s14\h'-\n(14u-\n(13u/2u'\v'-90u'\ \h'\n(14u-\n(12u/2u'\*(12\h'\n(14u-\n(12u/2u'\ .as 11 "\*(14 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "w .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .ds 14 "\f1,\fP .as 13 "\|\*(14 .ds 14 "\| .as 13 "\*(14 .ds 14 "\^j .as 13 "\*(14 .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "e .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "\^j .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 ". .as 11 "\*(12 .ds 11 \x'0'\f2\s14\*(11\s\n(99\f\n(98\x'75u' .nr 11 \w'\*(11' .nr MK 0 .if 174>\n(.v .ne 174u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "Our choice of a zero-phase filter together with shift invariance imply symmetry: .ps 14 .ft 2 .ft 1 .ds 13 "w .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .ds 15 "\f1,\fP .as 14 "\|\*(15 .ds 15 "\| .as 14 "\*(15 .ds 15 "\^j .as 14 "\*(15 .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 14 "\| .as 13 "\*(14 .ds 14 "\(eq .as 13 "\*(14 .ds 14 "\| .as 13 "\*(14 .ft 1 .ds 14 "w .ds 14 \f1\*(14\f2 .ft 2 .ds 15 "\^j .ds 16 "\f1,\fP .as 15 "\|\*(16 .ds 16 "\| .as 15 "\*(16 .ds 16 "i .as 15 "\*(16 .as 14 \v'24u'\s-3\*(15\s+3\|\v'-24u' .as 13 "\*(14 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ". .ps \n(99 .ft \n(98 \*(12 The shift invariance assumption is that .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ft 1 .ds 11 "w .ds 11 \f1\*(11\f2 .ft 2 .ds 12 "i .ds 13 "\f1,\fP .as 12 "\|\*(13 .ds 13 "\| .as 12 "\*(13 .ds 13 "\^j .as 12 "\*(13 .as 11 \v'24u'\s-3\*(12\s+3\|\v'-24u' .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "w .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "k .ds 14 "\f1,\fP .as 13 "\|\*(14 .ds 14 "\| .as 13 "\*(14 .ds 14 "l .as 13 "\*(14 .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "iff .ds 12 \f1\*(12\f2 .ft 2 .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "p .ds 12 \f1\*(12\f2 .ft 2 .nr 12 \w'\s14\*(12' .nr 10 0u .if \n(ct>1 .nr 10 \n(10+\s14.25m\s0 .nr 14 \s14.1m\s0 .if \n(ct>1 .nr 14 \s14.15m\s0 .ds 13 \v'-.4m'\s11\(->\s0\v'.4m' .nr 13 \w'\s14\*(13' .nr 14 0 .as 12 \h'-\n(12u-\n(13u/2u+\n(14u'\v'0-\n(10u'\*(13\v'\n(10u'\h'-\n(13u+\n(12u/2u-\n(14u' .ds 13 "i .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\| .as 11 "\*(12 .ds 12 "\(mi .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "p .ds 12 \f1\*(12\f2 .ft 2 .nr 12 \w'\s14\*(12' .nr 10 0u .if \n(ct>1 .nr 10 \n(10+\s14.25m\s0 .nr 14 \s14.1m\s0 .if \n(ct>1 .nr 14 \s14.15m\s0 .ds 13 \v'-.4m'\s11\(->\s0\v'.4m' .nr 13 \w'\s14\*(13' .nr 14 0 .as 12 \h'-\n(12u-\n(13u/2u+\n(14u'\v'0-\n(10u'\*(13\v'\n(10u'\h'-\n(13u+\n(12u/2u-\n(14u' .ds 13 "\^j .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "p .ds 12 \f1\*(12\f2 .ft 2 .nr 12 \w'\s14\*(12' .nr 10 0u .if \n(ct>1 .nr 10 \n(10+\s14.25m\s0 .nr 14 \s14.1m\s0 .if \n(ct>1 .nr 14 \s14.15m\s0 .ds 13 \v'-.4m'\s11\(->\s0\v'.4m' .nr 13 \w'\s14\*(13' .nr 14 0 .as 12 \h'-\n(12u-\n(13u/2u+\n(14u'\v'0-\n(10u'\*(13\v'\n(10u'\h'-\n(13u+\n(12u/2u-\n(14u' .ds 13 "k .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\| .as 11 "\*(12 .ds 12 "\(mi .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "p .ds 12 \f1\*(12\f2 .ft 2 .nr 12 \w'\s14\*(12' .nr 10 0u .if \n(ct>1 .nr 10 \n(10+\s14.25m\s0 .nr 14 \s14.1m\s0 .if \n(ct>1 .nr 14 \s14.15m\s0 .ds 13 \v'-.4m'\s11\(->\s0\v'.4m' .nr 13 \w'\s14\*(13' .nr 14 0 .as 12 \h'-\n(12u-\n(13u/2u+\n(14u'\v'0-\n(10u'\*(13\v'\n(10u'\h'-\n(13u+\n(12u/2u-\n(14u' .ds 13 "l .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\f1,\fP .as 11 "\*(12 .ds 11 \x'0'\f2\s14\*(11\s\n(99\f\n(98\x'9u' .nr 11 \w'\*(11' .nr MK 0 .if 120>\n(.v .ne 120u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "where .ps 14 .ft 2 .ft 1 .ds 13 "p .ds 13 \f1\*(13\f2 .ft 2 .nr 13 \w'\s14\*(13' .nr 10 0u .if \n(ct>1 .nr 10 \n(10+\s14.25m\s0 .nr 15 \s14.1m\s0 .if \n(ct>1 .nr 15 \s14.15m\s0 .ds 14 \v'-.4m'\s11\(->\s0\v'.4m' .nr 14 \w'\s14\*(14' .nr 15 0 .as 13 \h'-\n(13u-\n(14u/2u+\n(15u'\v'0-\n(10u'\*(14\v'\n(10u'\h'-\n(14u+\n(13u/2u-\n(15u' .ds 14 "i .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " is a vector representing the position of the .ps 14 .ft 2 .ds 13 "i .ds 13 \x'0'\f2\s14\*(13\|\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 "th pixel. .ps \n(99 .ft \n(98 \*(12 Shift invariance is not required for the following discussion, however. .PP At this point, we must make an assumption about how errors at different parts of the image combine to determine the overall quality of the halftoned representation. For mathematical simplicity, we assume that the combined detectability of the filtered errors is described by the squared Euclidean norm of the vector whose components are the values of the filtered error: We seek the halftoned image which minimizes the total squared .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "filtered error. At this point we will redefine the symbol .ps 14 .ft 2 .ds 13 "\(*c .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " (which we .ps \n(99 .ft \n(98 \*(12 introduced previously to represent the squared norm of the vector of raw errors) to be the squared norm of the vector of .ul filtered errors: .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ds 11 "\(*c .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 13 "i .nr 12 \w'\s14\*(12' .nr 14 \n(12 .nr 13 \w'\s11\*(13' .if \n(13>\n(14 .nr 14 \n(13 .ds 14 \v'90u'\h'\n(14u-\n(13u/2u'\s11\*(13\s14\h'-\n(14u-\n(13u/2u'\v'-90u'\ \h'\n(14u-\n(12u/2u'\*(12\h'\n(14u-\n(12u/2u'\ .as 11 "\*(14 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "f .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .ds 14 "\f12\fP .as 13 \| .nr 13 \w'\s11\*(13' .ds 14 \|\*(14 .nr 14 \w'\s11\*(14' .nr 15 \n(14 .if \n(13>\n(15 .nr 15 \n(13 .as 12 \v'24u'\s11\*(13\h'-\n(13u'\v'-57u'\ \s11\*(14\h'-\n(14u+\n(15u'\s14\v'33u' .as 11 "\*(12 .ds 11 \x'0'\f2\s14\*(11\s\n(99\f\n(98\x'75u' .nr 11 \w'\*(11' .nr MK 0 .if 189>\n(.v .ne 189u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN In this paper, we consider methods that can be specified by three rules: 1) a rule for selecting or generating an initial image; 2) a rule for the sequential selection of image pixels to be revised; 3) a rule for the adjustment of the halftone values at the visited locations. .PP At this point we introduce a bit of additional notation. .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "Let .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 14 "n .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " be the candidate halftone image after .ps 14 .ft 2 .ds 13 "n .ds 13 \x'0'\f2\s14\*(13\|\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " pixels have been .ps \n(99 .ft \n(98 \*(12 examined. .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "Let .ps 14 .ft 2 .ds 13 "k .ds 13 \x'0'\f2\s14\*(13\|\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " be the index of the .ps 14 .ft 2 .ds 13 "n .ds 13 \x'0'\f2\s14\*(13\|\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 "th pixel visited. .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "We define .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 14 "n .ds 15 "\(pl .as 14 \| .nr 14 \w'\s11\*(14' .ds 15 \|\*(15 .nr 15 \w'\s11\*(15' .nr 16 \n(15 .if \n(14>\n(16 .nr 16 \n(14 .as 13 \v'24u'\s11\*(14\h'-\n(14u'\v'-57u'\ \s11\*(15\h'-\n(15u+\n(16u'\s14\v'33u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " to be .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 14 "n .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " with .ps 14 .ft 2 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " set to +1 and .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 14 "n .ds 15 "\(mi .as 14 \| .nr 14 \w'\s11\*(14' .ds 15 \|\*(15 .nr 15 \w'\s11\*(15' .nr 16 \n(15 .if \n(14>\n(16 .nr 16 \n(14 .as 13 \v'24u'\s11\*(14\h'-\n(14u'\v'-57u'\ \s11\*(15\h'-\n(15u+\n(16u'\s14\v'33u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " to be .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 14 "n .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " with .ps 14 .ft 2 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " set to -1. .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "We use our chosen rule to obtain .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 14 "\f10\fP .as 13 \v'24u'\s-3\*(14\s+3\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 "; we use our scanning rule .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "to obtain a pixel index .ps 14 .ft 2 .ds 13 "k .ds 13 \x'0'\f2\s14\*(13\|\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " from the iteration count .ps 14 .ft 2 .ds 13 "n .ds 13 \x'0'\f2\s14\*(13\|\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ". .ps \n(99 .ft \n(98 \*(12 In the following sections we consider various rules for obtaining .nr 99 \n(.s .nr 98 \n(.f .rm 12 .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 14 "n .ds 15 "\(pl .as 14 "\|\*(15 .ds 15 "\f11\fP .as 14 "\*(15 .as 13 \v'24u'\s-3\*(14\s+3\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " given .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 14 "n .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ". .ps \n(99 .ft \n(98 \*(12 .NH 2 Strict Descent .PP .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "A simple method for reducing .ps 14 .ft 2 .ds 13 "\(*c .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " is to start .ps \n(99 .ft \n(98 \*(12 from some initial quantized image, and sequentially consider individual pixels in the quantized image, changing them if the change reduces .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "the total error .ps 14 .ft 2 .ds 13 "\(*c .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ". .ps \n(99 .ft \n(98 \*(12 We refer to this method as strict descent because the total error decreases monotonically. .PP .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "Consider the effect of the state of .ps 14 .ft 2 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", the quantized .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "value at the .ps 14 .ft 2 .ds 13 "k .ds 13 \x'0'\f2\s14\*(13\|\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 "th pixel, on the total error .ps 14 .ft 2 .ds 13 "\(*c .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ". .ps \n(99 .ft \n(98 \*(12 We begin by rewriting the expression for the filtered .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "error to make explicit the dependence on .ps 14 .ft 2 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ": .ps \n(99 .ft \n(98 \*(12 .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ft 1 .ds 11 "f .ds 11 \f1\*(11\f2 .ft 2 .ds 12 "i .as 11 \v'24u'\s-3\*(12\s+3\|\v'-24u' .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .ds 13 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 14 "\^j .ds 15 "\(!= .as 14 "\|\*(15 .ds 15 "k .as 14 "\*(15 .nr 13 \w'\s14\*(13' .nr 15 \n(13 .nr 14 \w'\s11\*(14' .if \n(14>\n(15 .nr 15 \n(14 .ds 15 \v'90u'\h'\n(15u-\n(14u/2u'\s11\*(14\s14\h'-\n(15u-\n(14u/2u'\v'-90u'\ \h'\n(15u-\n(13u/2u'\*(13\h'\n(15u-\n(13u/2u'\ .ds 13 "\ .as 15 "\*(13 .ft 1 .ds 13 "w .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .ds 16 "\f1,\fP .as 14 "\|\*(16 .ds 16 "\| .as 14 "\*(16 .ds 16 "\^j .as 14 "\*(16 .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 15 "\*(13 .ds 13 "\ .as 15 "\*(13 .ft 1 .ds 13 "e .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "\^j .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 15 "\*(13 .as 12 "\*(15 .ds 13 "\ .as 12 "\*(13 .ds 12 \|\v'36u'\b'\(lt\(bv\(lb'\v'-36u'\*(12\|\v'36u'\b'\(rt\(bv\(rb'\v'-36u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(pl .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "w .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .ds 14 "\f1,\fP .as 13 "\|\*(14 .ds 14 "\| .as 13 "\*(14 .ds 14 "k .as 13 "\*(14 .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .ds 13 "\| .as 12 "\*(13 .ds 13 "\f1(\fP .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 12 "\*(13 .ds 13 "\| .as 12 "\*(13 .ds 13 "\(mi .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ft 1 .ds 13 "g .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 12 "\*(13 .ds 13 "\| .as 12 "\*(13 .ds 13 "\f1)\fP .as 12 "\*(13 .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 ". .as 11 "\*(12 .ds 11 \x'0'\x'0-24u'\f2\s14\*(11\s\n(99\f\n(98\x'114u' .nr 11 \w'\*(11' .nr MK 0 .if 252>\n(.v .ne 252u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN Now, .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ds 11 "\(*c .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .ds 12 \k(97\*(12 .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 13 "i .nr 12 \w'\s14\*(12' .nr 14 \n(12 .nr 13 \w'\s11\*(13' .if \n(13>\n(14 .nr 14 \n(13 .ds 14 \v'90u'\h'\n(14u-\n(13u/2u'\s11\*(13\s14\h'-\n(14u-\n(13u/2u'\v'-90u'\ \h'\n(14u-\n(12u/2u'\*(12\h'\n(14u-\n(12u/2u'\ .as 11 "\*(14 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "f .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .ds 14 "\f12\fP .as 13 \| .nr 13 \w'\s11\*(13' .ds 14 \|\*(14 .nr 14 \w'\s11\*(14' .nr 15 \n(14 .if \n(13>\n(15 .nr 15 \n(13 .as 12 \v'24u'\s11\*(13\h'-\n(13u'\v'-57u'\ \s11\*(14\h'-\n(14u+\n(15u'\s14\v'33u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f1,\fP .as 11 "\*(12 .ds 11 \x'0'\f2\s14\*(11\s\n(99\f\n(98\x'75u' .nr 11 \w'\*(11' .nr MK 1 .if 189>\n(.v .ne 189u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ds 11 \h'|\n(97u' .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 13 "i .nr 12 \w'\s14\*(12' .nr 14 \n(12 .nr 13 \w'\s11\*(13' .if \n(13>\n(14 .nr 14 \n(13 .ds 14 \v'90u'\h'\n(14u-\n(13u/2u'\s11\*(13\s14\h'-\n(14u-\n(13u/2u'\v'-90u'\ \h'\n(14u-\n(12u/2u'\*(12\h'\n(14u-\n(12u/2u'\ .as 11 "\*(14 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .ds 13 "\ .ds 14 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 15 "\^j .ds 16 "\(!= .as 15 "\|\*(16 .ds 16 "k .as 15 "\*(16 .nr 14 \w'\s14\*(14' .nr 16 \n(14 .nr 15 \w'\s11\*(15' .if \n(15>\n(16 .nr 16 \n(15 .ds 16 \v'90u'\h'\n(16u-\n(15u/2u'\s11\*(15\s14\h'-\n(16u-\n(15u/2u'\v'-90u'\ \h'\n(16u-\n(14u/2u'\*(14\h'\n(16u-\n(14u/2u'\ .ds 14 "\ .as 16 "\*(14 .ft 1 .ds 14 "w .ds 14 \f1\*(14\f2 .ft 2 .ds 15 "i .ds 17 "\f1,\fP .as 15 "\|\*(17 .ds 17 "\| .as 15 "\*(17 .ds 17 "\^j .as 15 "\*(17 .as 14 \v'24u'\s-3\*(15\s+3\|\v'-24u' .as 16 "\*(14 .ds 14 "\ .as 16 "\*(14 .ft 1 .ds 14 "e .ds 14 \f1\*(14\f2 .ft 2 .ds 15 "\^j .as 14 \v'24u'\s-3\*(15\s+3\|\v'-24u' .as 16 "\*(14 .as 13 "\*(16 .ds 14 "\ .as 13 "\*(14 .ds 13 \|\v'36u'\b'\(lt\(bv\(lb'\v'-36u'\*(13\|\v'36u'\b'\(rt\(bv\(rb'\v'-36u' .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 13 "\(pl .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ft 1 .ds 13 "w .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .ds 15 "\f1,\fP .as 14 "\|\*(15 .ds 15 "\| .as 14 "\*(15 .ds 15 "k .as 14 "\*(15 .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 14 "\| .as 13 "\*(14 .ds 14 "\f1(\fP .as 13 "\*(14 .ds 14 "\ .as 13 "\*(14 .ft 1 .ds 14 "h .ds 14 \f1\*(14\f2 .ft 2 .ds 15 "k .as 14 \v'24u'\s-3\*(15\s+3\|\v'-24u' .as 13 "\*(14 .ds 14 "\| .as 13 "\*(14 .ds 14 "\(mi .as 13 "\*(14 .ds 14 "\ .as 13 "\*(14 .ft 1 .ds 14 "g .ds 14 \f1\*(14\f2 .ft 2 .ds 15 "k .as 14 \v'24u'\s-3\*(15\s+3\|\v'-24u' .as 13 "\*(14 .ds 14 "\| .as 13 "\*(14 .ds 14 "\f1)\fP .as 13 "\*(14 .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 12 \|\v'36u'\b'\(lc\(bv\(lf'\v'-36u'\*(12\|\v'36u'\b'\(rc\(bv\(rf'\v'-36u' .ds 13 "\f12\fP .as 12 \v'-69u'\s-3\*(13\s+3\v'69u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 ". .as 11 "\*(12 .ds 11 \x'0'\x'0-24u'\f2\s14\*(11\s\n(99\f\n(98\x'114u' .nr 11 \w'\*(11' .nr MK 1 .if 252>\n(.v .ne 252u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN By expanding the square twice, and collecting all terms which do .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "not depend on the value of .ps 14 .ft 2 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " into a constant .ps 14 .ft 2 .ft 1 .ds 13 "C .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", we obtain .ps \n(99 .ft \n(98 \*(12 .EQ I (2) .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ds 11 "\(*c .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 13 "i .nr 12 \w'\s14\*(12' .nr 14 \n(12 .nr 13 \w'\s11\*(13' .if \n(13>\n(14 .nr 14 \n(13 .ds 14 \v'90u'\h'\n(14u-\n(13u/2u'\s11\*(13\s14\h'-\n(14u-\n(13u/2u'\v'-90u'\ \h'\n(14u-\n(12u/2u'\*(12\h'\n(14u-\n(12u/2u'\ .as 11 "\*(14 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f12\fP .ds 13 "\| .as 12 "\*(13 .ft 1 .ds 13 "w .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .ds 15 "\f1,\fP .as 14 "\|\*(15 .ds 15 "\| .as 14 "\*(15 .ds 15 "k .as 14 "\*(15 .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 12 "\*(13 .ds 13 "\| .as 12 "\*(13 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 12 "\*(13 .ds 13 "\ .ds 14 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 15 "\^j .ds 16 "\(!= .as 15 "\|\*(16 .ds 16 "k .as 15 "\*(16 .nr 14 \w'\s14\*(14' .nr 16 \n(14 .nr 15 \w'\s11\*(15' .if \n(15>\n(16 .nr 16 \n(15 .ds 16 \v'90u'\h'\n(16u-\n(15u/2u'\s11\*(15\s14\h'-\n(16u-\n(15u/2u'\v'-90u'\ \h'\n(16u-\n(14u/2u'\*(14\h'\n(16u-\n(14u/2u'\ .ds 14 "\ .as 16 "\*(14 .ft 1 .ds 14 "w .ds 14 \f1\*(14\f2 .ft 2 .ds 15 "i .ds 17 "\f1,\fP .as 15 "\|\*(17 .ds 17 "\| .as 15 "\*(17 .ds 17 "\^j .as 15 "\*(17 .as 14 \v'24u'\s-3\*(15\s+3\|\v'-24u' .as 16 "\*(14 .ds 14 "\ .as 16 "\*(14 .ft 1 .ds 14 "e .ds 14 \f1\*(14\f2 .ft 2 .ds 15 "\^j .as 14 \v'24u'\s-3\*(15\s+3\|\v'-24u' .as 16 "\*(14 .as 13 "\*(16 .ds 14 "\ .as 13 "\*(14 .ds 13 \|\v'36u'\b'\(lt\(bv\(lb'\v'-36u'\*(13\|\v'36u'\b'\(rt\(bv\(rb'\v'-36u' .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 13 "\(mi .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 13 "\f12\fP .as 12 "\*(13 .ds 13 "\| .as 12 "\*(13 .ft 1 .ds 13 "w .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .ds 15 "\f1,\fP .as 14 "\|\*(15 .ds 15 "\| .as 14 "\*(15 .ds 15 "k .as 14 "\*(15 .ds 15 "\f12\fP .as 14 \| .nr 14 \w'\s11\*(14' .ds 15 \|\*(15 .nr 15 \w'\s11\*(15' .nr 16 \n(15 .if \n(14>\n(16 .nr 16 \n(14 .as 13 \v'24u'\s11\*(14\h'-\n(14u'\v'-57u'\ \s11\*(15\h'-\n(15u+\n(16u'\s14\v'33u' .as 12 "\*(13 .ds 13 "\| .as 12 "\*(13 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 12 "\*(13 .ds 13 "\| .as 12 "\*(13 .ft 1 .ds 13 "g .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 13 "\(pl .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ft 1 .ds 13 "C .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 12 \|\v'36u'\b'\(lc\(bv\(lf'\v'-36u'\*(12\|\v'36u'\b'\(rc\(bv\(rf'\v'-36u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f1,\fP .as 11 "\*(12 .ds 11 \x'0'\x'0-24u'\f2\s14\*(11\s\n(99\f\n(98\x'114u' .nr 11 \w'\*(11' .nr MK 0 .if 252>\n(.v .ne 252u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN where .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ft 1 .ds 11 "C .ds 11 \f1\*(11\f2 .ft 2 .ds 12 "i .as 11 \v'24u'\s-3\*(12\s+3\|\v'-24u' .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .ds 13 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 14 "\^j .ds 15 "\(!= .as 14 "\|\*(15 .ds 15 "k .as 14 "\*(15 .nr 13 \w'\s14\*(13' .nr 15 \n(13 .nr 14 \w'\s11\*(14' .if \n(14>\n(15 .nr 15 \n(14 .ds 15 \v'90u'\h'\n(15u-\n(14u/2u'\s11\*(14\s14\h'-\n(15u-\n(14u/2u'\v'-90u'\ \h'\n(15u-\n(13u/2u'\*(13\h'\n(15u-\n(13u/2u'\ .ds 13 "\ .as 15 "\*(13 .ft 1 .ds 13 "w .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .ds 16 "\f1,\fP .as 14 "\|\*(16 .ds 16 "\| .as 14 "\*(16 .ds 16 "\^j .as 14 "\*(16 .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 15 "\*(13 .ds 13 "\ .as 15 "\*(13 .ft 1 .ds 13 "e .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "\^j .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 15 "\*(13 .as 12 "\*(15 .ds 13 "\ .as 12 "\*(13 .ds 12 \|\v'36u'\b'\(lt\(bv\(lb'\v'-36u'\*(12\|\v'36u'\b'\(rt\(bv\(rb'\v'-36u' .ds 13 "\f12\fP .as 12 \v'-69u'\s-3\*(13\s+3\v'69u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(mi .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f12\fP .as 11 "\*(12 .ds 12 "\| .as 11 "\*(12 .ft 1 .ds 12 "w .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .ds 14 "\f1,\fP .as 13 "\|\*(14 .ds 14 "\| .as 13 "\*(14 .ds 14 "k .as 13 "\*(14 .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\| .as 11 "\*(12 .ft 1 .ds 12 "g .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "k .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\| .as 11 "\*(12 .ds 12 "\ .ds 13 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 14 "\^j .ds 15 "\(!= .as 14 "\|\*(15 .ds 15 "k .as 14 "\*(15 .nr 13 \w'\s14\*(13' .nr 15 \n(13 .nr 14 \w'\s11\*(14' .if \n(14>\n(15 .nr 15 \n(14 .ds 15 \v'90u'\h'\n(15u-\n(14u/2u'\s11\*(14\s14\h'-\n(15u-\n(14u/2u'\v'-90u'\ \h'\n(15u-\n(13u/2u'\*(13\h'\n(15u-\n(13u/2u'\ .ds 13 "\ .as 15 "\*(13 .ft 1 .ds 13 "w .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .ds 16 "\f1,\fP .as 14 "\|\*(16 .ds 16 "\| .as 14 "\*(16 .ds 16 "\^j .as 14 "\*(16 .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 15 "\*(13 .ds 13 "\ .as 15 "\*(13 .ft 1 .ds 13 "e .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "\^j .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 15 "\*(13 .as 12 "\*(15 .ds 13 "\ .as 12 "\*(13 .ds 12 \|\v'36u'\b'\(lt\(bv\(lb'\v'-36u'\*(12\|\v'36u'\b'\(rt\(bv\(rb'\v'-36u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(pl .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "w .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .ds 14 "\f1,\fP .as 13 "\|\*(14 .ds 14 "\| .as 13 "\*(14 .ds 14 "k .as 13 "\*(14 .ds 14 "\f12\fP .as 13 \| .nr 13 \w'\s11\*(13' .ds 14 \|\*(14 .nr 14 \w'\s11\*(14' .nr 15 \n(14 .if \n(13>\n(15 .nr 15 \n(13 .as 12 \v'24u'\s11\*(13\h'-\n(13u'\v'-57u'\ \s11\*(14\h'-\n(14u+\n(15u'\s14\v'33u' .as 11 "\*(12 .ds 12 "\| .as 11 "\*(12 .ds 12 "\f1(\fP .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f11\fP .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(pl .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "g .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "k .ds 14 "\f12\fP .as 13 \| .nr 13 \w'\s11\*(13' .ds 14 \|\*(14 .nr 14 \w'\s11\*(14' .nr 15 \n(14 .if \n(13>\n(15 .nr 15 \n(13 .as 12 \v'24u'\s11\*(13\h'-\n(13u'\v'-57u'\ \s11\*(14\h'-\n(14u+\n(15u'\s14\v'33u' .as 11 "\*(12 .ds 12 "\| .as 11 "\*(12 .ds 12 "\f1)\fP .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 ". .as 11 "\*(12 .ds 11 \x'0'\x'0-24u'\f2\s14\*(11\s\n(99\f\n(98\x'114u' .nr 11 \w'\*(11' .nr MK 0 .if 252>\n(.v .ne 252u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN .PP To find .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "the value for .ps 14 .ft 2 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " which .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "minimizes .ps 14 .ft 2 .ds 13 "\(*c .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", we .ps \n(99 .ft \n(98 \*(12 consider the .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "values of .ps 14 .ft 2 .ds 13 "\(*c .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " for the images .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 14 "n .ds 15 "\(pl .as 14 \| .nr 14 \w'\s11\*(14' .ds 15 \|\*(15 .nr 15 \w'\s11\*(15' .nr 16 \n(15 .if \n(14>\n(16 .nr 16 \n(14 .as 13 \v'24u'\s11\*(14\h'-\n(14u'\v'-57u'\ \s11\*(15\h'-\n(15u+\n(16u'\s14\v'33u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " and .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 14 "n .ds 15 "\(mi .as 14 \| .nr 14 \w'\s11\*(14' .ds 15 \|\*(15 .nr 15 \w'\s11\*(15' .nr 16 \n(15 .if \n(14>\n(16 .nr 16 \n(14 .as 13 \v'24u'\s11\*(14\h'-\n(14u'\v'-57u'\ \s11\*(15\h'-\n(15u+\n(16u'\s14\v'33u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", corresponding to .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "the two possible states of .ps 14 .ft 2 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ". .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "Let .ps 14 .ft 2 .ds 13 "\(*c .ds 14 "\(pl .as 13 \v'-33u'\s-3\*(14\s+3\v'33u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " be the total error associated with the halftone .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 14 "n .ds 15 "\(pl .as 14 \| .nr 14 \w'\s11\*(14' .ds 15 \|\*(15 .nr 15 \w'\s11\*(15' .nr 16 \n(15 .if \n(14>\n(16 .nr 16 \n(14 .as 13 \v'24u'\s11\*(14\h'-\n(14u'\v'-57u'\ \s11\*(15\h'-\n(15u+\n(16u'\s14\v'33u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "and let .ps 14 .ft 2 .ds 13 "\(*c .ds 14 "\(mi .as 13 \v'-33u'\s-3\*(14\s+3\v'33u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " be the total error associated with the halftone .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 14 "n .ds 15 "\(mi .as 14 \| .nr 14 \w'\s11\*(14' .ds 15 \|\*(15 .nr 15 \w'\s11\*(15' .nr 16 \n(15 .if \n(14>\n(16 .nr 16 \n(14 .as 13 \v'24u'\s11\*(14\h'-\n(14u'\v'-57u'\ \s11\*(15\h'-\n(15u+\n(16u'\s14\v'33u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ". .ps \n(99 .ft \n(98 \*(12 Our rule says that we will pick the image with the lower associated total error: .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ft 3 .ds 11 "h .ds 11 \f3\*(11\f2 .ft 2 .ds 12 "n .ds 13 "\(pl .as 12 "\|\*(13 .ds 13 "\f11\fP .as 12 "\*(13 .as 11 \v'24u'\s-3\*(12\s+3\v'-24u' .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 3 .ds 12 "h .ds 12 \f3\*(12\f2 .ft 2 .ds 13 "n .ds 14 "\(pl .as 13 \| .nr 13 \w'\s11\*(13' .ds 14 \|\*(14 .nr 14 \w'\s11\*(14' .nr 15 \n(14 .if \n(13>\n(15 .nr 15 \n(13 .as 12 \v'24u'\s11\*(13\h'-\n(13u'\v'-57u'\ \s11\*(14\h'-\n(14u+\n(15u'\s14\v'33u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "iff .ds 12 \f1\*(12\f2 .ft 2 .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(*c .ds 13 "\(pl .as 12 \v'-33u'\s-3\*(13\s+3\v'33u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(mi .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(*c .ds 13 "\(mi .as 12 \v'-33u'\s-3\*(13\s+3\v'33u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "< .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f10\fP .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 11 \x'0'\f2\s14\*(11\s\n(99\f\n(98\x'9u' .nr 11 \w'\*(11' .nr MK 0 .if 123>\n(.v .ne 123u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN The remainder of this section is devoted to the evaluation of this difference. .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "Expressions for .ps 14 .ft 2 .ds 13 "\(*c .ds 14 "\(pl .as 13 \v'-33u'\s-3\*(14\s+3\v'33u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " and .ps 14 .ft 2 .ds 13 "\(*c .ds 14 "\(mi .as 13 \v'-33u'\s-3\*(14\s+3\v'33u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " are obtained from equation (2) by .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "substituting the appropriate value of .ps 14 .ft 2 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ". We then take the difference: .ps \n(99 .ft \n(98 \*(12 .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ds 11 "\(*c .ds 12 "\(pl .as 11 \v'-33u'\s-3\*(12\s+3\v'33u' .ds 12 "\ .as 11 "\*(12 .ds 12 "\(mi .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(*c .ds 13 "\(mi .as 12 \v'-33u'\s-3\*(13\s+3\v'33u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .ds 12 \k(97\*(12 .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f14\fP .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 13 "i .nr 12 \w'\s14\*(12' .nr 14 \n(12 .nr 13 \w'\s11\*(13' .if \n(13>\n(14 .nr 14 \n(13 .ds 14 \v'90u'\h'\n(14u-\n(13u/2u'\s11\*(13\s14\h'-\n(14u-\n(13u/2u'\v'-90u'\ \h'\n(14u-\n(12u/2u'\*(12\h'\n(14u-\n(12u/2u'\ .as 11 "\*(14 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "w .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .ds 14 "\f1,\fP .as 13 "\|\*(14 .ds 14 "\| .as 13 "\*(14 .ds 14 "k .as 13 "\*(14 .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .ds 13 "\ .ds 14 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 15 "\^j .ds 16 "\(!= .as 15 "\|\*(16 .ds 16 "k .as 15 "\*(16 .nr 14 \w'\s14\*(14' .nr 16 \n(14 .nr 15 \w'\s11\*(15' .if \n(15>\n(16 .nr 16 \n(15 .ds 16 \v'90u'\h'\n(16u-\n(15u/2u'\s11\*(15\s14\h'-\n(16u-\n(15u/2u'\v'-90u'\ \h'\n(16u-\n(14u/2u'\*(14\h'\n(16u-\n(14u/2u'\ .ds 14 "\ .as 16 "\*(14 .ft 1 .ds 14 "w .ds 14 \f1\*(14\f2 .ft 2 .ds 15 "i .ds 17 "\f1,\fP .as 15 "\|\*(17 .ds 17 "\| .as 15 "\*(17 .ds 17 "\^j .as 15 "\*(17 .as 14 \v'24u'\s-3\*(15\s+3\|\v'-24u' .as 16 "\*(14 .ds 14 "\ .as 16 "\*(14 .ft 1 .ds 14 "e .ds 14 \f1\*(14\f2 .ft 2 .ds 15 "\^j .as 14 \v'24u'\s-3\*(15\s+3\|\v'-24u' .as 16 "\*(14 .as 13 "\*(16 .ds 14 "\ .as 13 "\*(14 .ds 13 \|\v'36u'\b'\(lt\(bv\(lb'\v'-36u'\*(13\|\v'36u'\b'\(rt\(bv\(rb'\v'-36u' .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 13 "\(mi .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ft 1 .ds 13 "w .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .ds 15 "\f1,\fP .as 14 "\|\*(15 .ds 15 "\| .as 14 "\*(15 .ds 15 "k .as 14 "\*(15 .ds 15 "\f12\fP .as 14 \| .nr 14 \w'\s11\*(14' .ds 15 \|\*(15 .nr 15 \w'\s11\*(15' .nr 16 \n(15 .if \n(14>\n(16 .nr 16 \n(14 .as 13 \v'24u'\s11\*(14\h'-\n(14u'\v'-57u'\ \s11\*(15\h'-\n(15u+\n(16u'\s14\v'33u' .as 12 "\*(13 .ds 13 "\| .as 12 "\*(13 .ft 1 .ds 13 "g .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 12 \|\v'36u'\b'\(lc\(bv\(lf'\v'-36u'\*(12\|\v'36u'\b'\(rc\(bv\(rf'\v'-36u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f1,\fP .as 11 "\*(12 .ds 11 \x'0'\x'0-24u'\f2\s14\*(11\s\n(99\f\n(98\x'114u' .nr 11 \w'\*(11' .nr MK 1 .if 252>\n(.v .ne 252u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ds 11 \h'|\n(97u' .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f14\fP .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 13 "i .nr 12 \w'\s14\*(12' .nr 14 \n(12 .nr 13 \w'\s11\*(13' .if \n(13>\n(14 .nr 14 \n(13 .ds 14 \v'90u'\h'\n(14u-\n(13u/2u'\s11\*(13\s14\h'-\n(14u-\n(13u/2u'\v'-90u'\ \h'\n(14u-\n(12u/2u'\*(12\h'\n(14u-\n(12u/2u'\ .as 11 "\*(14 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "w .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .ds 14 "\f1,\fP .as 13 "\|\*(14 .ds 14 "\| .as 13 "\*(14 .ds 14 "k .as 13 "\*(14 .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\ .ds 13 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 14 "\^j .ds 15 "\(!= .as 14 "\|\*(15 .ds 15 "k .as 14 "\*(15 .nr 13 \w'\s14\*(13' .nr 15 \n(13 .nr 14 \w'\s11\*(14' .if \n(14>\n(15 .nr 15 \n(14 .ds 15 \v'90u'\h'\n(15u-\n(14u/2u'\s11\*(14\s14\h'-\n(15u-\n(14u/2u'\v'-90u'\ \h'\n(15u-\n(13u/2u'\*(13\h'\n(15u-\n(13u/2u'\ .ds 13 "\ .as 15 "\*(13 .ft 1 .ds 13 "w .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .ds 16 "\f1,\fP .as 14 "\|\*(16 .ds 16 "\| .as 14 "\*(16 .ds 16 "\^j .as 14 "\*(16 .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 15 "\*(13 .ds 13 "\ .as 15 "\*(13 .ft 1 .ds 13 "e .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "\^j .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 15 "\*(13 .as 12 "\*(15 .ds 13 "\ .as 12 "\*(13 .ds 12 \|\v'36u'\b'\(lt\(bv\(lb'\v'-36u'\*(12\|\v'36u'\b'\(rt\(bv\(rb'\v'-36u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(mi .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f14\fP .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "g .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "k .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 13 "i .nr 12 \w'\s14\*(12' .nr 14 \n(12 .nr 13 \w'\s11\*(13' .if \n(13>\n(14 .nr 14 \n(13 .ds 14 \v'90u'\h'\n(14u-\n(13u/2u'\s11\*(13\s14\h'-\n(14u-\n(13u/2u'\v'-90u'\ \h'\n(14u-\n(12u/2u'\*(12\h'\n(14u-\n(12u/2u'\ .as 11 "\*(14 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "w .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .ds 14 "\f1,\fP .as 13 "\|\*(14 .ds 14 "\| .as 13 "\*(14 .ds 14 "k .as 13 "\*(14 .ds 14 "\f12\fP .as 13 \| .nr 13 \w'\s11\*(13' .ds 14 \|\*(14 .nr 14 \w'\s11\*(14' .nr 15 \n(14 .if \n(13>\n(15 .nr 15 \n(13 .as 12 \v'24u'\s11\*(13\h'-\n(13u'\v'-57u'\ \s11\*(14\h'-\n(14u+\n(15u'\s14\v'33u' .as 11 "\*(12 .ds 12 "\f1,\fP .as 11 "\*(12 .ds 11 \x'0'\x'0-24u'\f2\s14\*(11\s\n(99\f\n(98\x'114u' .nr 11 \w'\*(11' .nr MK 1 .if 252>\n(.v .ne 252u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN .EQ I (3) .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ds 11 \h'|\n(97u' .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f14\fP .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 13 "i .nr 12 \w'\s14\*(12' .nr 14 \n(12 .nr 13 \w'\s11\*(13' .if \n(13>\n(14 .nr 14 \n(13 .ds 14 \v'90u'\h'\n(14u-\n(13u/2u'\s11\*(13\s14\h'-\n(14u-\n(13u/2u'\v'-90u'\ \h'\n(14u-\n(12u/2u'\*(12\h'\n(14u-\n(12u/2u'\ .as 11 "\*(14 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "w .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .ds 14 "\f1,\fP .as 13 "\|\*(14 .ds 14 "\| .as 13 "\*(14 .ds 14 "k .as 13 "\*(14 .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\ .ds 13 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 14 "\^j .nr 13 \w'\s14\*(13' .nr 15 \n(13 .nr 14 \w'\s11\*(14' .if \n(14>\n(15 .nr 15 \n(14 .ds 15 \v'90u'\h'\n(15u-\n(14u/2u'\s11\*(14\s14\h'-\n(15u-\n(14u/2u'\v'-90u'\ \h'\n(15u-\n(13u/2u'\*(13\h'\n(15u-\n(13u/2u'\ .ds 13 "\ .as 15 "\*(13 .ft 1 .ds 13 "w .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .ds 16 "\f1,\fP .as 14 "\|\*(16 .ds 16 "\| .as 14 "\*(16 .ds 16 "\^j .as 14 "\*(16 .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 15 "\*(13 .ds 13 "\ .as 15 "\*(13 .ft 1 .ds 13 "e .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "\^j .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 15 "\*(13 .as 12 "\*(15 .ds 13 "\ .as 12 "\*(13 .ds 13 "\(mi .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ft 1 .ds 13 "w .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .ds 15 "\f1,\fP .as 14 "\|\*(15 .ds 15 "\| .as 14 "\*(15 .ds 15 "k .as 14 "\*(15 .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 12 "\*(13 .ds 13 "\| .as 12 "\*(13 .ft 1 .ds 13 "e .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 12 \|\v'36u'\b'\(lt\(bv\(lb'\v'-36u'\*(12\|\v'36u'\b'\(rt\(bv\(rb'\v'-36u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(mi .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f14\fP .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "g .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "k .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 13 "i .nr 12 \w'\s14\*(12' .nr 14 \n(12 .nr 13 \w'\s11\*(13' .if \n(13>\n(14 .nr 14 \n(13 .ds 14 \v'90u'\h'\n(14u-\n(13u/2u'\s11\*(13\s14\h'-\n(14u-\n(13u/2u'\v'-90u'\ \h'\n(14u-\n(12u/2u'\*(12\h'\n(14u-\n(12u/2u'\ .as 11 "\*(14 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "w .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .ds 14 "\f1,\fP .as 13 "\|\*(14 .ds 14 "\| .as 13 "\*(14 .ds 14 "k .as 13 "\*(14 .ds 14 "\f12\fP .as 13 \| .nr 13 \w'\s11\*(13' .ds 14 \|\*(14 .nr 14 \w'\s11\*(14' .nr 15 \n(14 .if \n(13>\n(15 .nr 15 \n(13 .as 12 \v'24u'\s11\*(13\h'-\n(13u'\v'-57u'\ \s11\*(14\h'-\n(14u+\n(15u'\s14\v'33u' .as 11 "\*(12 .ds 12 ". .as 11 "\*(12 .ds 11 \x'0'\x'0-24u'\f2\s14\*(11\s\n(99\f\n(98\x'114u' .nr 11 \w'\*(11' .nr MK 1 .if 252>\n(.v .ne 252u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "The error at the pixel in question, .ps 14 .ft 2 .ft 1 .ds 13 "e .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", represents the error based on the .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "previous value of .ps 14 .ft 2 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ". .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "At this point we assume that we have normalized .ps 14 .ft 2 .ft 3 .ds 13 "W .ds 13 \f3\*(13\f2 .ft 2 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " so that .ps 14 .ft 2 .ft 1 .ds 13 "w .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "i .ds 15 "\f1,\fP .as 14 "\|\*(15 .ds 15 "\| .as 14 "\*(15 .ds 15 "k .as 14 "\*(15 .ds 15 "\f12\fP .as 14 \| .nr 14 \w'\s11\*(14' .ds 15 \|\*(15 .nr 15 \w'\s11\*(15' .nr 16 \n(15 .if \n(14>\n(16 .nr 16 \n(14 .as 13 \v'24u'\s11\*(14\h'-\n(14u'\v'-57u'\ \s11\*(15\h'-\n(15u+\n(16u'\s14\v'33u' .ds 14 "\ .as 13 "\*(14 .ds 14 "\(eq .as 13 "\*(14 .ds 14 "\ .as 13 "\*(14 .ds 14 "\f11\fP .as 13 "\*(14 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ". .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "We also introduce the filter .ps 14 .ft 2 .ft 3 .ds 13 "Z .ds 13 \f3\*(13\f2 .ft 2 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", where we define .ps \n(99 .ft \n(98 \*(12 .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ft 1 .ds 11 "z .ds 11 \f1\*(11\f2 .ft 2 .ds 12 "k .ds 13 "\f1,\fP .as 12 "\|\*(13 .ds 13 "\| .as 12 "\*(13 .ds 13 "\^j .as 12 "\*(13 .as 11 \v'24u'\s-3\*(12\s+3\|\v'-24u' .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 13 "i .nr 12 \w'\s14\*(12' .nr 14 \n(12 .nr 13 \w'\s11\*(13' .if \n(13>\n(14 .nr 14 \n(13 .ds 14 \v'90u'\h'\n(14u-\n(13u/2u'\s11\*(13\s14\h'-\n(14u-\n(13u/2u'\v'-90u'\ \h'\n(14u-\n(12u/2u'\*(12\h'\n(14u-\n(12u/2u'\ .as 11 "\*(14 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "w .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .ds 14 "\f1,\fP .as 13 "\|\*(14 .ds 14 "\| .as 13 "\*(14 .ds 14 "k .as 13 "\*(14 .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "w .ds 12 \f1\*(12\f2 .ft 2 .ds 13 "i .ds 14 "\f1,\fP .as 13 "\|\*(14 .ds 14 "\| .as 13 "\*(14 .ds 14 "\^j .as 13 "\*(14 .as 12 \v'24u'\s-3\*(13\s+3\|\v'-24u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 ". .as 11 "\*(12 .ds 11 \x'0'\f2\s14\*(11\s\n(99\f\n(98\x'75u' .nr 11 \w'\*(11' .nr MK 0 .if 174>\n(.v .ne 174u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "If .ps 14 .ft 2 .ft 3 .ds 13 "W .ds 13 \f3\*(13\f2 .ft 2 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " is symmetrical, applying the filter .ps 14 .ft 2 .ft 3 .ds 13 "Z .ds 13 \f3\*(13\f2 .ft 2 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " is equivalent to applying .ps 14 .ft 2 .ft 3 .ds 13 "W .ds 13 \f3\*(13\f2 .ft 2 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " .ps \n(99 .ft \n(98 \*(12 twice. Equation (3) can then be rewritten as .EQ I (4) .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ds 11 "\(*c .ds 12 "\(pl .as 11 \v'-33u'\s-3\*(12\s+3\v'33u' .ds 12 "\ .as 11 "\*(12 .ds 12 "\(mi .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(*c .ds 13 "\(mi .as 12 \v'-33u'\s-3\*(13\s+3\v'33u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .ds 12 \k(97\*(12 .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f14\fP .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .ds 13 "\ .as 12 "\*(13 .ds 13 \s14\v'.3m'\s+5\(*S\s-5\v'-.3m'\s14 .ds 14 "\^j .nr 13 \w'\s14\*(13' .nr 15 \n(13 .nr 14 \w'\s11\*(14' .if \n(14>\n(15 .nr 15 \n(14 .ds 15 \v'90u'\h'\n(15u-\n(14u/2u'\s11\*(14\s14\h'-\n(15u-\n(14u/2u'\v'-90u'\ \h'\n(15u-\n(13u/2u'\*(13\h'\n(15u-\n(13u/2u'\ .as 12 "\*(15 .ds 13 "\ .as 12 "\*(13 .ft 1 .ds 13 "z .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .ds 15 "\f1,\fP .as 14 "\|\*(15 .ds 15 "\| .as 14 "\*(15 .ds 15 "\^j .as 14 "\*(15 .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ft 1 .ds 13 "e .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "\^j .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 13 "\(mi .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ft 1 .ds 13 "e .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 13 "\(mi .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ft 1 .ds 13 "g .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 13 "\ .as 12 "\*(13 .ds 12 \|\v'36u'\b'\(lt\(bv\(lb'\v'-36u'\*(12\|\v'36u'\b'\(rt\(bv\(rb'\v'-36u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 ". .as 11 "\*(12 .ds 11 \x'0'\x'0-24u'\f2\s14\*(11\s\n(99\f\n(98\x'114u' .nr 11 \w'\*(11' .nr MK 1 .if 252>\n(.v .ne 252u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN .PP For computational efficiency, we maintain images of both the raw .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "error .ps 14 .ft 2 .ft 3 .ds 13 "e .ds 13 \f3\*(13\f2 .ft 2 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " and the error filtered by .ps 14 .ft 2 .ft 3 .ds 13 "Z .ds 13 \f3\*(13\f2 .ft 2 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ". When these are precomputed, .ps \n(99 .ft \n(98 \*(12 the evaluation of equation (4) involves only two subtractions. .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "If we change the value of .ps 14 .ft 2 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", we must then update the value of .ps 14 .ft 2 .ft 1 .ds 13 "e .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "and update the image of the error filtered by .ps 14 .ft 2 .ft 3 .ds 13 "Z .ds 13 \f3\*(13\f2 .ft 2 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " in the neighborhood of .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "the .ps 14 .ft 2 .ds 13 "k .ds 13 \x'0'\f2\s14\*(13\|\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 "th pixel. .ps \n(99 .ft \n(98 \*(12 .br .sv 3i .os .nr PS 10 .nr VS 12 .RT Figure 2: A gray scale ramped, halftoned using the strict descent algorithm described in the text. The image was divided into 8 strips, each of which was processed using a differently sized Gaussian filter for the error. The filter standard deviations vary from 0.2 pixels (left) to 1.6 pixels (right), in linear steps of 0.2. .nr PS 12 .nr VS 14 .PP When the error filter has a finite impulse response, the only errors which can affect the state of a given pixel are those which lie .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "within the support of the filter .ps 14 .ft 2 .ft 3 .ds 13 "Z .ds 13 \f3\*(13\f2 .ft 2 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", centered at the pixel in question. .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "If N pixels are within the support of .ps 14 .ft 2 .ft 3 .ds 13 "Z .ds 13 \f3\*(13\f2 .ft 2 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", then any gray level .ps \n(99 .ft \n(98 \*(12 less than (2/N-1) will be rendered as black, regardless of the precise .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "nature of .ps 14 .ft 2 .ft 3 .ds 13 "Z .ds 13 \f3\*(13\f2 .ft 2 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ". .ps \n(99 .ft \n(98 \*(12 This clipping effect has been noted previously,\*([.4\*(.] and is illustrated graphically in figure 2, where a gray scale ramp has been halftoned in strips of varying filter size. In this example we used a circularly symmetric Gaussian filter sampled and truncated to a 5 x 5 array of weights; the Gaussian standard deviation varied from 0.2 pixels at the extreme left to 1.6 pixels at the extreme right. The figure illustrates how as the filter size is reduced, more and more of the gray levels near black or white are represented as solid regions of white or black. Figure 2 also illustrates that the resulting textures do not depend strongly on the filter size for the larger filter sizes; this allows us latitude in matching the error filter to the human CSF (which will depend on viewing distance). .NH 2 Simulated Annealing .PP Unfortunately, the strict descent method described above .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "can only find a local minimum of the error .ps 14 .ft 2 .ds 13 "\(*c .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ". In general, .ps \n(99 .ft \n(98 \*(12 the particular local minimum which is found depends upon the initial image and the order in which the pixels are reconsidered. In an attempt to find the global minimum, we have used simulated annealing\*([.4\*(.] as our optimization method. As in the strict descent method, pixels in the halftone image are considered for possible change one at a time, and we generate a sequence that visits each pixel arbitrarily many times. .br .sv 5i .os .nr PS 10 .nr VS 12 .RT Figure 3: Mean error as a function of number of iterations at four different fixed temperatures. .nr PS 12 .nr VS 14 .RT .PP .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "Let .ps 14 .ft 2 .ds 13 "k .ds 13 \x'0'\f2\s14\*(13\|\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " be the index of the pixel selected on iteration .ps 14 .ft 2 .ds 13 "n .ds 13 \x'0'\f2\s14\*(13\|\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "and let .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 14 "n .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " be the candidate halftone image at the beginning of .ps \n(99 .ft \n(98 \*(12 the iteration. .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "We define .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 14 "n .ds 15 "\(pl .as 14 \| .nr 14 \w'\s11\*(14' .ds 15 \|\*(15 .nr 15 \w'\s11\*(15' .nr 16 \n(15 .if \n(14>\n(16 .nr 16 \n(14 .as 13 \v'24u'\s11\*(14\h'-\n(14u'\v'-57u'\ \s11\*(15\h'-\n(15u+\n(16u'\s14\v'33u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " to be .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 14 "n .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " with .ps 14 .ft 2 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " set to +1 and .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 14 "n .ds 15 "\(mi .as 14 \| .nr 14 \w'\s11\*(14' .ds 15 \|\*(15 .nr 15 \w'\s11\*(15' .nr 16 \n(15 .if \n(14>\n(16 .nr 16 \n(14 .as 13 \v'24u'\s11\*(14\h'-\n(14u'\v'-57u'\ \s11\*(15\h'-\n(15u+\n(16u'\s14\v'33u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " to be .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 14 "n .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " with .ps 14 .ft 2 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " set to -1. .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "We define .ps 14 .ft 2 .ds 13 "\(*c .ds 14 "\(pl .as 13 \v'-33u'\s-3\*(14\s+3\v'33u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " and .ps 14 .ft 2 .ds 13 "\(*c .ds 14 "\(mi .as 13 \v'-33u'\s-3\*(14\s+3\v'33u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " to be the corresponding values of the total .ps \n(99 .ft \n(98 \*(12 error, as in the previous section. .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "We then set .ps 14 .ft 2 .ft 1 .ds 13 "h .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "k .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " equal to 1 with a probability given by .ps \n(99 .ft \n(98 \*(12 .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ft 1 .ds 11 "Pr .ds 11 \f1\*(11\f2 .ft 2 .ds 12 "\f1(\fP .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 3 .ds 12 "h .ds 12 \f3\*(12\f2 .ft 2 .ds 13 "n .ds 14 "\(pl .as 13 "\|\*(14 .ds 14 "\f11\fP .as 13 "\*(14 .as 12 \v'24u'\s-3\*(13\s+3\v'-24u' .as 11 "\*(12 .ds 12 "\| .as 11 "\*(12 .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 3 .ds 12 "h .ds 12 \f3\*(12\f2 .ft 2 .ds 13 "n .ds 14 "\(pl .as 13 \| .nr 13 \w'\s11\*(13' .ds 14 \|\*(14 .nr 14 \w'\s11\*(14' .nr 15 \n(14 .if \n(13>\n(15 .nr 15 \n(13 .as 12 \v'24u'\s11\*(13\h'-\n(13u'\v'-57u'\ \s11\*(14\h'-\n(14u+\n(15u'\s14\v'33u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f1)\fP .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f1exp\fP .ds 13 "\f1(\fP .as 12 "\*(13 .ds 13 "\(mi .ds 14 "\(*c .ds 15 "\(pl .as 14 \v'-33u'\s-3\*(15\s+3\v'33u' .as 13 "\*(14 .ds 14 "\(sl .as 13 "\*(14 .ft 1 .ds 14 "T .ds 14 \f1\*(14\f2 .ft 2 .ds 15 "n .as 14 \v'24u'\s-3\*(15\s+3\|\v'-24u' .as 13 "\*(14 .as 12 "\*(13 .ds 13 "\f1)\fP .as 12 "\*(13 .ds 13 "\f1exp\fP .ds 14 "\f1(\fP .as 13 "\*(14 .ds 14 "\(mi .ds 15 "\(*c .ds 16 "\(pl .as 15 \v'-33u'\s-3\*(16\s+3\v'33u' .as 14 "\*(15 .ds 15 "\(sl .as 14 "\*(15 .ft 1 .ds 15 "T .ds 15 \f1\*(15\f2 .ft 2 .ds 16 "n .as 15 \v'24u'\s-3\*(16\s+3\|\v'-24u' .as 14 "\*(15 .as 13 "\*(14 .ds 14 "\f1)\fP .as 13 "\*(14 .ds 14 "\ .as 13 "\*(14 .ds 14 "\(pl .as 13 "\*(14 .ds 14 "\ .as 13 "\*(14 .ds 14 "\f1exp\fP .as 13 "\*(14 .ds 14 "\f1(\fP .as 13 "\*(14 .ds 14 "\(mi .ds 15 "\(*c .ds 16 "\(mi .as 15 \v'-33u'\s-3\*(16\s+3\v'33u' .as 14 "\*(15 .ds 15 "\(sl .as 14 "\*(15 .ft 1 .ds 15 "T .ds 15 \f1\*(15\f2 .ft 2 .ds 16 "n .as 15 \v'24u'\s-3\*(16\s+3\|\v'-24u' .as 14 "\*(15 .as 13 "\*(14 .ds 14 "\f1)\fP .as 13 "\*(14 .nr 12 \w'\s14\*(12' .nr 13 \w'\s14\*(13' .nr 14 \n(12 .if \n(13>\n(14 .nr 14 \n(13 .nr 14 \n(14+\s14.5m\s0 .ds 12 \v'75u'\h'\n(14u-\n(13u/2u'\*(13\ \h'-\n(13u-\n(12u/2u'\v'-147u'\*(12\ \h'-\n(14u-\n(12u/2u+.1m'\v'48u'\l'\n(14u-.2m'\h'.1m'\v'24u' .as 11 "\*(12 .ds 12 ". .as 11 "\*(12 .ds 11 \x'0'\x'0-72u'\f2\s14\*(11\s\n(99\f\n(98\x'84u' .nr 11 \w'\*(11' .nr MK 0 .if 270>\n(.v .ne 270u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "The temperature parameter .ps 14 .ft 2 .ft 1 .ds 13 "T .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "n .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " is positive, so the state having the .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "smaller value of .ps 14 .ft 2 .ds 13 "\(*c .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " has the higher probability. .ps \n(99 .ft \n(98 \*(12 As the temperature becomes large, the two states are chosen with nearly equal frequency. .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "If we define .ps 14 .ft 2 .ds 13 "\(*D .ds 14 "\(*c .as 13 "\*(14 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " to be the difference between the .ps \n(99 .ft \n(98 \*(12 the two energies, .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ds 11 "\(*D .ds 12 "\(*c .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(*c .ds 13 "\(pl .as 12 \v'-33u'\s-3\*(13\s+3\v'33u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(mi .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(*c .ds 13 "\(mi .as 12 \v'-33u'\s-3\*(13\s+3\v'33u' .as 11 "\*(12 .ds 12 "\| .as 11 "\*(12 .ds 12 "\f1,\fP .as 11 "\*(12 .ds 11 \x'0'\f2\s14\*(11\s\n(99\f\n(98 .nr 11 \w'\*(11' .nr MK 0 .if 99>\n(.v .ne 99u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN the rule can be stated .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "in terms of the probability that the succeeding state will be .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 14 "n .ds 15 "\(pl .as 14 \| .nr 14 \w'\s11\*(14' .ds 15 \|\*(15 .nr 15 \w'\s11\*(15' .nr 16 \n(15 .if \n(14>\n(16 .nr 16 \n(14 .as 13 \v'24u'\s11\*(14\h'-\n(14u'\v'-57u'\ \s11\*(15\h'-\n(15u+\n(16u'\s14\v'33u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ": .ps \n(99 .ft \n(98 \*(12 .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ft 1 .ds 11 "Pr .ds 11 \f1\*(11\f2 .ft 2 .ds 12 "\| .as 11 "\*(12 .ds 12 "\f1(\fP .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 3 .ds 12 "h .ds 12 \f3\*(12\f2 .ft 2 .ds 13 "n .ds 14 "\(pl .as 13 "\|\*(14 .ds 14 "\f11\fP .as 13 "\*(14 .as 12 \v'24u'\s-3\*(13\s+3\v'-24u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 3 .ds 12 "h .ds 12 \f3\*(12\f2 .ft 2 .ds 13 "n .ds 14 "\(pl .as 13 \| .nr 13 \w'\s11\*(13' .ds 14 \|\*(14 .nr 14 \w'\s11\*(14' .nr 15 \n(14 .if \n(13>\n(15 .nr 15 \n(13 .as 12 \v'24u'\s11\*(13\h'-\n(13u'\v'-57u'\ \s11\*(14\h'-\n(14u+\n(15u'\s14\v'33u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f1)\fP .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f1exp\fP .ds 13 "\f1(\fP .as 12 "\*(13 .ds 13 "\(mi .ds 14 "\(*D .ds 15 "\(*c .as 14 "\*(15 .as 13 "\*(14 .ds 14 "\(sl .as 13 "\*(14 .ft 1 .ds 14 "T .ds 14 \f1\*(14\f2 .ft 2 .ds 15 "n .as 14 \v'24u'\s-3\*(15\s+3\|\v'-24u' .as 13 "\*(14 .as 12 "\*(13 .ds 13 "\f1)\fP .as 12 "\*(13 .ds 13 "\f11\fP .ds 14 "\(pl .as 13 "\*(14 .ds 14 "\f1exp\fP .as 13 "\*(14 .ds 14 "\f1(\fP .as 13 "\*(14 .ds 14 "\(mi .ds 15 "\(*D .ds 16 "\(*c .as 15 "\*(16 .as 14 "\*(15 .ds 15 "\(sl .as 14 "\*(15 .ft 1 .ds 15 "T .ds 15 \f1\*(15\f2 .ft 2 .ds 16 "n .as 15 \v'24u'\s-3\*(16\s+3\|\v'-24u' .as 14 "\*(15 .as 13 "\*(14 .ds 14 "\f1)\fP .as 13 "\*(14 .nr 12 \w'\s14\*(12' .nr 13 \w'\s14\*(13' .nr 14 \n(12 .if \n(13>\n(14 .nr 14 \n(13 .nr 14 \n(14+\s14.5m\s0 .ds 12 \v'60u'\h'\n(14u-\n(13u/2u'\*(13\ \h'-\n(13u-\n(12u/2u'\v'-132u'\*(12\ \h'-\n(14u-\n(12u/2u+.1m'\v'48u'\l'\n(14u-.2m'\h'.1m'\v'24u' .as 11 "\*(12 .ds 11 \x'0'\x'0-57u'\f2\s14\*(11\s\n(99\f\n(98\x'69u' .nr 11 \w'\*(11' .nr MK 0 .if 240>\n(.v .ne 240u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN As the temperature approaches zero, so does the probability that the poor state is chosen, and the rule approaches the deterministic rule of section 2.1: .EQ I .nr 99 \n(.s .nr 98 \n(.f .ps 14 .ft 2 .ft 3 .ds 11 "h .ds 11 \f3\*(11\f2 .ft 2 .ds 12 "n .ds 13 "\(pl .as 12 "\|\*(13 .ds 13 "\f11\fP .as 12 "\*(13 .as 11 \v'24u'\s-3\*(12\s+3\v'-24u' .ds 12 "\ .as 11 "\*(12 .ds 12 "\(eq .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 3 .ds 12 "h .ds 12 \f3\*(12\f2 .ft 2 .ds 13 "n .ds 14 "\(pl .as 13 \| .nr 13 \w'\s11\*(13' .ds 14 \|\*(14 .nr 14 \w'\s11\*(14' .nr 15 \n(14 .if \n(13>\n(15 .nr 15 \n(13 .as 12 \v'24u'\s11\*(13\h'-\n(13u'\v'-57u'\ \s11\*(14\h'-\n(14u+\n(15u'\s14\v'33u' .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ft 1 .ds 12 "iff .ds 12 \f1\*(12\f2 .ft 2 .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\(*D .ds 13 "\(*c .as 12 "\*(13 .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "< .as 11 "\*(12 .ds 12 "\ .as 11 "\*(12 .ds 12 "\f10\fP\f1.\fP .as 11 "\*(12 .ds 11 \x'0'\f2\s14\*(11\s\n(99\f\n(98\x'9u' .nr 11 \w'\*(11' .nr MK 0 .if 123>\n(.v .ne 123u .rn 11 10 \*(10 .ps \n(99 .ft \n(98 .EN This deterministic rule always improves the energy at every step but almost always stops at a local rather than a global optimum. .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "Annealing schedules which slowly reduce .ps 14 .ft 2 .ft 1 .ds 13 "T .ds 13 \f1\*(13\f2 .ft 2 .ds 14 "n .as 13 \v'24u'\s-3\*(14\s+3\|\v'-24u' .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98\x'9u' .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " as a function of .ps 14 .ft 2 .ds 13 "n .ds 13 \x'0'\f2\s14\*(13\|\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " .ps \n(99 .ft \n(98 \*(12 can have a good chance of finding the optimal halftone, but they can be very slow. .PP Good annealing schedules can be estimated from an examination of what happens to the average error when the algorithm is run at a fixed temperature, as shown in figure 3. The figure shows the average error as a function of number iterations for 4 different temperatures. For a given temperature, the average error decreases until it reaches an asymptotic value which corresponds to the "thermal" noise in the system. The higher temperature processes reach their asymptotic values more quickly, but these values are higher than those ultimately reached by the lower temperature processes. Note that the curve in figure 3 corresponding to a temperature of 0.025 has not reached equilibrium after 100000 iterations over the entire image. The data in figure 3 were generated by a process halftoning a uniform input of zeroes, for which the optimal halftone is known to be a perfectly regular checkerboard. The log of the error for the checkerboard has a value of approximately -4, which is quite a bit lower than the best curve in figure 3. .NH 1 RESULTS .PP .nr 99 \n(.s .nr 98 \n(.f .rm 12 .as 12 "We have defined a metric .ps 14 .ft 2 .ds 13 "\(*c .ds 14 "\| .as 13 "\*(14 .ds 14 "\f1(\fP .as 13 "\*(14 .ds 14 "\| .as 13 "\*(14 .ft 3 .ds 14 "g .ds 14 \f3\*(14\f2 .ft 2 .as 13 "\*(14 .ds 14 "\| .as 13 "\*(14 .ds 14 "\f1,\fP .as 13 "\*(14 .ds 14 "\| .as 13 "\*(14 .ft 3 .ds 14 "h .ds 14 \f3\*(14\f2 .ft 2 .as 13 "\*(14 .ds 14 "\| .as 13 "\*(14 .ds 14 "\f1)\fP .as 13 "\*(14 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ", which describes how close a halftone .ps \n(99 .ft \n(98 \*(12 .nr 99 \n(.s .nr 98 \n(.f .rm 12 .ps 14 .ft 2 .ft 3 .ds 13 "h .ds 13 \f3\*(13\f2 .ft 2 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 " comes to perceptually simulating a continuous tone image .ps 14 .ft 2 .ft 3 .ds 13 "g .ds 13 \f3\*(13\f2 .ft 2 .ds 13 \x'0'\f2\s14\*(13\s\n(99\f\n(98 .as 12 \*(13 .ps \n(99 .ft \n(98 .as 12 ". .ps \n(99 .ft \n(98 \*(12 The new algorithms we have presented seek to minimize this error metric. In this framework, one can evaluate the performance of various algorithms by comparing the generated error values. .PP In order to apply our algorithms, the filter to be applied to the error must first be determined. In our simulations, we have approximated the contrast sensitivity function with a Gaussian. The optimal standard deviation will depend on the final viewing distance, but, as we have seen, the textures which are produced in uniform regions do not depend strongly on the filter size for standard deviations above one pixel. .PP Once the error filter has been determined, two other free parameters must be determined. First, an initial state of the image must be chosen. We have obtained good results by starting with a random array of light and dark pixels; other choices we have investigated include locally quantizing the image with a fixed threshold (as in figure 1), or using an image obtained from another halftoning algorithm, or using a constant image. Secondly, the order in which the points are visited must be specified. We have tried three different scanning patterns, one in which the points are sampled randomly, and two deterministic scanning patterns. One of these deterministic scans was a traditional left-to-right top-to-bottom raster; the other was a "scattered" scan in which the two low order bits of the iteration counter determined the quadrant of the point, the next two bits selected the quadrant-within-the-quadrant, and so on recursively. .PP Our investigations for the case of strict descent have produced the following observations: first, the use of a raster scan produces oscillation in the output with the consequence of more iterations being required to reach equilibrium. The scattered scan pattern produces rapid convergence, but if the initial image is not random the scattered scan method produces regular textures similar to those produced by ordered dither. These are eliminated if the initial halftone is random. Random scanning seems to produce the best results of all, but more iterations are require to insure that all pixels have been visited. Images produced using all of these methods are shown for comparison in figure 4. .NH 1 Existing methods .PP Among existing halftoning methods, there can be observed a tradeoff between speed and simplicity and the quality of the final image. .ul Ordered dither\*([.1\*(.] is one of the simplest methods. In this method, each pixel in the input image is compared against a position-dependent threshold, with the result of the comparison determining the state of the corresponding output pixel. The quality of the final image is greatly affected by the choice of the individual thresholds; Bayer\*([.5\*(.] has demonstrated a construction for obtaining well-balanced micro patterns. The biggest advantage of this method is its speed and simplicity. Since the operations carried out at a given pixel are independent of the values of all other pixels, the algorithm is eminently suited to implementation on a parallel machine. .PP At the other end of the spectrum is .ul error diffusion,\*([.6\*(.] introduced by Floyd and Steinberg. In error diffusion, as each pixel is quantized the quantization error is "diffused" or spread to neighboring pixels which have yet to be quantized. When these pixels are eventually quantized, their final output values are chosen so as to compensate for previous quantization errors, as well as the desired value at the point itself. This method produces high-quality halftones and is particularly good at reproducing sharp edges. Because of its inherently serial nature, however, a parallel implementation is impossible. .PP Knuth\*([.7\*(.] has introduced a hybrid method he calls .ul dot diffusion. In this method, small groups of pixels are quantized independently (as in ordered dither), but within each group quantization errors are shared between neighbors. This method obtains results nearly as good as those produced by error diffusion using an algorithm for which a parallel implementation exists. .PP Of the methods described above, it is generally agreed that error diffusion produces the best results. We might ask, however, is this in fact the best we can do? The serial nature of the algorithm means that the errors get propagated in the direction the image is scanned, which can result in subtle artifacts. From an aesthetic standpoint, we would prefer an algorithm in which the errors are diffused isotropically in all directions. It seems intuitively clear that the pattern of errors will depend somehow on the weights with which the errors are spread to nearby pixels, but there are no recipes telling how to choose the weights to obtain a particular error spectrum. .PP These problems have been addressed by recent work\*([.4,8,9,10\*(.] applying the theory of neural networks to the problem of halftoning. The development presented above is similar to that followed by these earlier efforts. Our approach differs, however, in that we have eliminated the intermediate image in the Hopfield network which is subjected to a nonlinearity in order to produce the final halftone image. In our method the pixels are processed sequentially, whereas when the intermediate image is used it is updated in parallel, or "lock-step" fashion. We believe that this difference produces faster convergence for our method in the strict descent case. .PP In figure 5, we present a comparison of the present method with the most popular competitor, error diffusion. The particular implementation of the error diffusion used the weights given in Newman and Sproull's text,\*([.11\*(.] and used a serpentine raster which processed alternate scan lines in alternate directions. .NH 1 DISCUSSION .PP Unlike error diffusion, the present method produces halftones which possess uniform textural properties at all gray levels. This is not the case for the error diffusion algorithm, as can be seen in figure 5, where the error diffusion image shows the formation of regular patterns at gray levels producing dot densities of 25%, 50% and 75%. Regular patterns such as these can interact with nonlinearities in the output device (such as ink spread in a printer dot) to produce artifactual distortions in the tone scale. While output nonlinearities will also distort images processed using the algorithm described in this paper, the uniformity of the halftone texture with changes in gray level will prevent the introduction of false contours by the artifacts, making the method robust with respect to failings of the output device. .PP In our development, we used the contrast sensitivity function to filter the error in order to assess the quality of a candidate halftone. A more refined version might use a more accurate representation of the CSF, but when the image is to be viewed from a variety of distances this may produce little improvement. One aspect of visual sensitivity which probably can be exploited is the oblique effect, which describes the fact that humans have greater sensitivity for signals oriented either vertically or horizontally than for oblique signals.\*([.12\*(.] .PP All approaches based on the CSF presuppose that the quantization errors will be near threshold. For the case where the halftoning noise will be visible (as is commonly the case when presenting halftone images on cathode-ray tube displays), minimum detectability of the error may not be the most appropriate criterion. Since the ultimate goal is communication of the information in the original image, what is really desired is a halftoning noise which can be perceptually disassociated from the underlying image; we would like to produce a halftone in which the noise is seen as a transparent veil overlying an uncorrupted percept of the original image. While these ideas have not been fully developed, we believe that the present method, by making explicit the relationship between the design of the error filter and the resulting error spectrum, will make it easy to design adaptive schemes which tailor the quantization noise to the picture content. .PP Other investigators have recently considered similar approaches, but instead of flipping the states of individual pixels they considered instead the effects of exchanging the values of adjacent pixels having different states, i.e. "moving" the white pixels around. We note that every such exchange can in principle be generated by the sequential setting and clearing of the individual pixels, although this scenario often involves an improbable intermediate state having a high error value. Nonetheless, as long as a method has a nonzero probability of reaching all possible states, it will approach the global optimum given enough time to do so. Conversely, if only a fraction of the states can be reached, as in the case when only exchanges are allowed, then it is extremely unlikely that the global optimum will be in the space of images which will be considered. One group following this approach\*([.13\*(.] began by setting the total number of white pixels in accordance with the D.C. value of the image; it can be seen from the tone scale compression in figure 2, however, that the optimal image will not have this property if it has unequal areas of values near white and black. Fixing the number of white pixels in the image is equivalent to giving an infinite weight to the value of the CSF at zero frequency. We note that by using a Gaussian error filter in our work, we have already given a disproportionate weight to the low frequency terms, since the CSF is actually bandpass in nature. .PP Lastly, we must mention one final point which is something of an embarrassment. In the early stages of this work, we were primarily concerned with improving on the results produced by error diffusion, and paid little attention to ordered dither. When we later included ordered dither in our comparisons, we were surprised to find that it produced lower numerical values of the filtered error than either error diffusion or the method presented here, in spite of the fact that the images produced by ordered dither were the least visually pleasing. We interpret this fact to reflect the inadequacy of a simple circularly symmetric filter as a model of the human visual system; in future work, we plan to develop a refined version of the algorithm which uses an array of oriented filters, which we think will be sensitive to the structured artifacts in the ordered dither images, and will give the images rankings which are more in line with perceptual judgements. .NH 1 CONCLUSIONS .PP In this work we have tried to demonstrate how one could design a halftoning algorithm based on a computational model of the human visual system. The particular model which we have considered here is only a first stab at the problem, but it serves to illustrate some of the principles which we hope to use to extend to more complex models. In particular, we hope to extend the method to exploit the visual system's relatively poor resolution (both in space and time) to chromatic variation. .NH 1 ACKNOWLEDGEMENTS .PP This work was supported by NASA RTOP 506-7151. .PP .]< .ds [F 1 .]- .ds [A Ulichney, Robert .ds [T Digital Halftoning .ds [I MIT Press .ds [C Cambridge, Mass. .ds [D 1987 .nr [T 0 .nr [A 0 .nr [O 0 .][ 2 book .ds [F 2 .]- .ds [A Cambell, F. W. .as [A " and Robson, J. G. .ds [T Application of Fourier analysis to the visibility of gratings .ds [J J. Physiol. (Lond.) .ds [V 197 .ds [P 551-566 .nr [P 1 .ds [D 1968 .nr [T 0 .nr [A 1 .nr [O 0 .][ 1 journal-article .ds [F 3 .]- .ds [A Ahumada, A. J. Jr. .ds [D 1987 .ds [T Putting the noise of the visual system back in the picture .ds [J J. Opt. Soc. Am. A .ds [V 4 .ds [P 2372-2378 .nr [P 1 .nr [T 0 .nr [A 1 .nr [O 0 .][ 1 journal-article .ds [F 4 .]- .ds [A Carnevali, P. .as [A ", Coletti, L. .as [A ", and Patarnello, S. .ds [T Image Processing by Simulated Annealing .ds [J IBM J. Res. Develop. .ds [V 29 .ds [P 569-579 .nr [P 1 .ds [D 1985 .nr [T 0 .nr [A 1 .nr [O 0 .][ 1 journal-article .ds [F 5 .]- .ds [A Bayer, B. E. .ds [T An optimum method for two-level rendition of continuous-tone pictures .ds [J Conference Record of the Intl. Conf. on Communications .ds [P 26-11 - 26-15 .nr [P 1 .ds [D 1973 .nr [T 0 .nr [A 1 .nr [O 0 .][ 1 journal-article .ds [F 6 .]- .ds [A Floyd, R. .as [A " and Steinberg, L. .ds [T An adaptive algorithm for spatial gray scale .ds [J SID 1975 Symp. Dig. Tech. Papers .ds [P 36 .nr [P 0 .ds [D 1975 .nr [T 0 .nr [A 1 .nr [O 0 .][ 1 journal-article .ds [F 7 .]- .ds [A Knuth, Donald E. .ds [T Digital halftones by dot diffusion .ds [J ACM Trans. Graphics .ds [V 6 .ds [P 245-273 .nr [P 1 .ds [D 1987 .nr [T 0 .nr [A 1 .nr [O 0 .][ 1 journal-article .ds [F 8 .]- .ds [A Anastassiou, D. .ds [T Neural net based digital halftoning of images .ds [J Proc. IEEE Symp. Circuits & Systems .ds [P 507-510 .nr [P 1 .ds [D 1988 .nr [T 0 .nr [A 1 .nr [O 0 .][ 1 journal-article .ds [F 9 .]- .ds [A Ling, Daniel T. .as [A " and Just, Dieter .ds [T Neural Networks for Halftoning of Color Images .ds [J IBM Research Report .ds [V RC 16588 .ds [D 1991 .nr [T 0 .nr [A 0 .nr [O 0 .][ 1 journal-article .ds [F 10 .]- .ds [A Sullivan, J. .as [A ", Ray, L. .as [A ", and Miller, R. .ds [T Design of minimum visual modulation halftone patterns .ds [J IEEE Trans. Systems Man Cybernetics .ds [V 21 .ds [P 33-38 .nr [P 1 .ds [D 1991 .nr [T 0 .nr [A 1 .nr [O 0 .][ 1 journal-article .ds [F 11 .]- .ds [A Newman, William M. .as [A " and Sproull, Robert F. .ds [T Principles of interactive computer graphics .ds [D 1979 .ds [I McGraw-Hill .ds [C New York, NY .nr [T 0 .nr [A 1 .nr [O 0 .][ 2 book .ds [F 12 .]- .ds [A Olzak, L. A. .as [A " and Thomas, J. P. .ds [T Seeing spatial patterns .ds [E K. R. Boff, L. Kaufman, J. P. Thomas .ds [B Handbook of perception and human performance .ds [D 1986 .ds [P 7.1-7.56 .nr [P 1 .nr [T 0 .nr [A 1 .nr [O 0 .][ 3 article-in-book .ds [F 13 .]- .ds [A Analoui, M. .as [A " and Allebach, J. P. .ds [T Model-based halftoning by direct binary search .ds [J Proc. SPIE Conference on Human Vision, Visual Processing and Digital Display III .ds [P paper 1666-09 .nr [P 1 .ds [D 1992 .nr [T 0 .nr [A 1 .nr [O 0 .][ 1 journal-article .]> .bp .sv 8.3i .os .nr PS 10 .nr VS 12 .RT Figure 4: Comparison of output images from the 0 temperature (strict descent) process for three different scanning patterns and two different initial images. Images in the left column were started with a thresholded version of the image, while those in the right column were started with noise. Top row: raster scan; middle row: scattered scan; bottom row: random scan. .nr PS 12 .nr VS 14 .bp .sv 8.3i .os .nr PS 10 .nr VS 12 .RT Figure 5: Comparison of output images from the 0 temperature (strict descent) process with images processed by error diffusion. Top row: originals; middle row: error diffusion; bottom row: strict descent. The images in the bottom row were produced with random initial images and a random scanning pattern. The error filter had a standard deviation of 0.8 pixels. .nr PS 12 .nr VS 14 .bp