ewhac@well.UUCP (Leo 'Bols Ewhac' Schwab) (07/12/88)
[ Maybe I should write an automatic line-eater line generator... ] Hi there. After some helpful suggestions from this group, I've started playing around with the Floyd-Steinberg image quantization algorithm. You know, the one where you distribute the quantization error to neighboring pixels. However, I've run into a weird snag. Occasionally, depending on the Phase of The Moon, it translates black pixels into grey ones. Needless to say, this is The Wrong Thing. After considering a number of possible problems, it struck me that perhaps I'm not dealing with overflow and underflow correctly. Consider the following scenario: Suppose we have two monochromatic pixels side by side with the following intensities (0 == black, 1 == white): +-----+-----+ | .51 | .02 | Threshold is .5 +-----+-----+ So Floyd and Steinberg come along, see the .51 pixel, and quantize it to 1.0. By the rules of the algorithm, the pixel immediately to the right gets 3/8 of the quantization error. This leaves us with: +-----+-----+ | 1.0 |-.16 | ((.51 - 1.0) * 3 / 8) + .02 == -.16 +-----+-----+ Now clearly, -.16 is out of range for the value of a pixel; it's too black. So my question is this: What do I do with this pixel when it comes time to process it? Do I pretend like there's no problem, and treat it like all the other pixels (doesn't seem right, since this negative pixel will suck the brightness out of the neighboring pixel when I process it)? Do I I truncate its value to the valid range (also seems wrong, since I'm tossing part of the error out the window)? If I do truncate it, when should I do it: when I encounter the errant pixel and process it; or while I'm distributing the error to it, thus "preventing the problem in the first place"? Thanks in advance. _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_ Leo L. Schwab -- The Guy in The Cape INET: well!ewhac@ucbvax.Berkeley.EDU \_ -_ Recumbent Bikes: UUCP: pacbell > !{well,unicom}!ewhac O----^o The Only Way To Fly. hplabs / (pronounced "AE-wack") "Hmm, you're right. Air is made up of suspended meat loaf." -- Josh Siegel
sclafani@jumbo.dec.com (Michael Sclafani) (07/13/88)
In article <6506@well.UUCP>, ewhac@well.UUCP (Leo 'Bols Ewhac' Schwab) writes: > However, I've run into a weird snag. Occasionally, depending on the > Phase of The Moon, it translates black pixels into grey ones. This sounds like a common implementation problem: if you don't handle the error terms properly, your error terms will accumulate and grow, whiting out the image. Make sure that the sum of the computed error terms equals the actual error. It's easy to get this wrong if you use bit-shifts for division or aren't careful about rounding. > After considering a number of possible > problems, it struck me that perhaps I'm not dealing with overflow and > underflow correctly. [ example of negative pixel value deleted ] > Now clearly, -.16 is out of range for the value of a pixel; it's too > black. > > So my question is this: What do I do with this pixel when it comes > time to process it? Do I pretend like there's no problem, and treat it like > all the other pixels (doesn't seem right, since this negative pixel will > suck the brightness out of the neighboring pixel when I process it)? But is _is_ right. You've taken a pixel which is "gray", and set it to "white". To compensate, other pixels must be made darker. Since the adjacent pixel would already have been "black", the negative error term will propagate through the image. Consider a one-dimensional image (all of the error propagates to the right): +-----+-----+-----+ | .51 | .02 | .51 | (.51 - 1.0) + .02 == -.47 +-----+-----+-----+ +-----+-----+-----+ | 1.0 | 0.0 | .51 | (-.47 - 0.0) + .51 == .04 +-----+-----+-----+ +-----+-----+-----+ | 1.0 | 0.0 | 0.0 | +.04 +-----+-----+-----+ The average intensity of the region has been maintained _because_ of the propagation of negative values. The range of legal pixel values doubles from [ 0.0 , 1.0 ] to [ -0.5 , 1.5 ]. In the example you gave, you used 3/8 to determine the horizontal error term. I believe that is different from the technique that Floyd and Steinberg actually used, with the error split in four directions, not just three: +-----+-----+-----+ | | x | 7/16| +-----+-----+-----+ | 3/16| 5/16| 1/16| +-----+-----+-----+ This method introduces fewer artifacts than the (3/8 3/8 2/8) technique. I think Steinberg posted on this newsgroup, stating that alternating directions on scan lines (left to right on odd, right to left on even) will produce even better results. I've seen an implementation which does this, and it's true. Michael Sclafani \\\ Digital Equipment Corporation sclafani@src.dec.com \\\ Systems Research Center, Palo Alto, CA
aden@versatc.UUCP (Michael Aden) (07/15/88)
In article <13172@jumbo.dec.com> sclafani@jumbo.dec.com (Michael Sclafani) writes: >In article <6506@well.UUCP>, ewhac@well.UUCP (Leo 'Bols Ewhac' Schwab) writes: ... lots of error conversation here... >I think Steinberg posted on this newsgroup, stating that alternating >directions on scan lines (left to right on odd, right to left on even) >will produce even better results. I've seen an implementation which does >this, and it's true. There is a relatively new book on digital halftoning which discusses Floyd-Steinberg error terms, as well as a half-dozen others which cover this topic fairly effectively. The book is _Digital Halftoning_, by Robert Ulichney, (c)1987 MIT Press. Serpentine treatment of raster gets pretty much a full chapter near the end of the book (the book goes generally from worst-case to best-case rasterization, hence serpentining's later position). The problem with Floyd-Steinberg (and all the others) when used on scanlines is a tendency towards "worm tracks", a propagation of error in a coherent direction. While serpentine helps this, even better would be error propagation along a non-trivial path, which leads us back to the Peano curve discussion of a few months back. I never saw a discussion of how to do those fast. Anybody have any hints they'd like to share? (I'll keep my eyes open this time -> 8-) ) BTW, I'd like to do this on an 8000x8000 image, so efficiency is kind of important. Michael Aden Versatec, Inc. {pyramid,vsi1,uunet}!versatc!aden
dbeck@unix.SRI.COM (Douglas K. Beck) (07/17/88)
There is a later paper by Ulnichy that describes methods for modifying the FS dither, using a random perturbation of the threshold for each pixel, and distributing the error on a randomized basis between the next adjacent pixel and the pixel directly beneath the object pixel. It gives smoother looking images, albeit noisy than any other implementation of the FS scheme that I have tried. ...doug beck dbeck@unix.sri.com
jbm@eos.UUCP (Jeffrey Mulligan) (07/19/88)
From article <252@versatc.UUCP>, by aden@versatc.UUCP (Michael Aden): [stuff deleted] ... > The problem with Floyd-Steinberg (and all the others) when used on scanlines > is a tendency towards "worm tracks", a propagation of error in a coherent direction. > While serpentine helps this, even better would be error propagation along > a non-trivial path, which leads us back to the Peano curve discussion of a few months > back. I never saw a discussion of how to do those fast. You might be interested in: Koenderink, J.J., and Van Doorn, A.J., "New type of raster scan preserves the topology of the image." Proc. IEEE, v.67, no. 19, pp. 1465-1466, Oct. 1979. -- Jeff Mulligan (jbm@aurora.arc.nasa.gov) NASA/Ames Research Ctr., Mail Stop 239-3, Moffet Field CA, 94035 (415) 694-6290
ma_jns@ux63.bath.ac.uk (Spackman) (07/19/88)
2N 11776: 19 Jul 88 John Spackman
(Message # 2: 11776 bytes, New)
Via: uk.ac.bath.maths; 19 Jul 88 10:41 BST
Received: from chroma by mordell.maths.bath.AC.UK id aa29121;
19 Jul 88 10:35 BST
Date: Tue, 19 Jul 88 10:33:28 BST
From: John Spackman <jns@uk.ac.bath.maths>
To: ma_jns@uk.ac.bath.ux63
The following shell archive contains various C code for
mappings between Cartesian and Peano co-ordinates. The
Peano co-ordinate of a point in a 2^n side square is the
position along the connected, filling Peano curve ( Hilbert
here ). The mappings are achieved with simple bit shifts
for speed, iterating 'n' times for a '2^n' side square.
I have used this curve to order error propagation (c.g.
Floyd Steinberg), passing the whole error incurred by quan-
tisation at one pixel to the Peano-next pixel. Other graph-
ical applications include run-length images ALONG THE CURVE,
which is comparable to quad encoding.
The code may be adapted to generate curves in n-space,
e.g. 3-space for look up table algorithms.
John Spackman, Maths Sciences
University of Bath, Claverton Down, Bath, Avon, BA2 7AY, England.
#------------- cut here -------------- cut here -----------
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of archive 1 (of 1)."
# Contents: peano_routines.h peano_routines.c example.c makefile
#
# An example showing how to use the mappings is given in "example.c",
# which you should make with the makfile. For example, try :-
# Level (>0) ? 1 'Square of 2^level side
# Direction : Across in [0,1] & From in [0,3] ? 'Direction & Origin of curve
# 'Output ..
# 0 th peano point AT [ X = 0, Y = 0 ]
# [ X = 0, Y = 0 ] AT 0 th peano point
# 1 th peano point AT [ X = 1, Y = 0 ]
# [ X = 1, Y = 0 ] AT 1 th peano point
# 2 th peano point AT [ X = 1, Y = 1 ]
# [ X = 1, Y = 1 ] AT 2 th peano point
# 3 th peano point AT [ X = 0, Y = 1 ]
# ... etc.
if test -f 'peano_routines.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'peano_routines.h'\"
else
echo shar: Extracting \"'peano_routines.h'\"
sed "s/^X//" >'peano_routines.h' <<'END_OF_FILE'
Xstruct traverse
X{
X int accross, from;
X};
X
Xstruct record
X{
X int moreton, peano;
X struct traverse next;
X};
X
Xstruct path
X{
X struct record quad[4];
X};
X
Xstruct curve
X{
X struct path dimension[2];
X};
X
Xtypedef struct traverse TRAVERSE;
Xtypedef struct record RECORD;
Xtypedef struct path PATH;
Xtypedef struct curve CURVE;
END_OF_FILE
fi
if test -f 'peano_routines.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'peano_routines.c'\"
else
echo shar: Extracting \"'peano_routines.c'\"
sed "s/^X//" >'peano_routines.c' <<'END_OF_FILE'
X#include "peano_routines.h"
X
Xchar copy_right[] = "\
X +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ \n\
X | | | | | | | | | | | | | | | | \n\
X | +---+ | | +---+ | | +---+ | | +---+ | \n\
X | | | | | | | | \n\
X +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ \n\
X | | | | | | | | \n\
X +---+ +-----------+ +---+ +---+ +-----------+ +---+ \n\
X | | | | \n\
X | +-------+ +-------+ | | +-------+ +-------+ | \n\
X | | | | | | | | | | | | \n\
X +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ \n\
X | | | | \n\
X +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ \n\
X | | | | | | | | | | | | \n\
X | +-------+ +-------+ +---+ +-------+ +-------+ | \n\
X | | \n\
X +---+ +-------+ +-------+ +-------+ +-------+ +---+ \n\
X | | | | | | | | | | \n\
X +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ \n\
X | | | | | | \n\
X | +---+ | +---+ +---+ +---+ +---+ | +---+ | \n\
X | | | | | | | | | | | | | | \n\
X +---+ +---+ | +-------+ +-------+ | +---+ +---+ \n\
X | | \n\
X +---+ +---+ | +-------+ +-------+ | +---+ +---+ \n\
X | | | | | | | | | | | | | | \n\
X | +---+ | +---+ +---+ +---+ +---+ | +---+ | \n\
X | | | | | | \n\
X +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ \n\
X | | | | | | | | | | \n\
X >>--+ +-------+ +-------+ +-------+ +-------+ +-->> \n\
X \n\
X ###### @1988 John Spackman, \n\
X ## ## The University of Bath,\n\
X ## ## #### #### ##### #### Claverton Down, \n\
X ##### ## ## ## ## ## ## ## Bath, \n\
X ## ###### ##### ## ## ## ## Avon, \n\
X ## ## ## ## ## ## ## ## BA2 7AY, \n\
X #### #### ### ## ## ## #### England. \n\
X \n\
X #### \n\
X ## ## \n\
X ## ## ## ## ### ## ## #### ##### \n\
X ## ## ## ### ## ## ## ## ## ## \n\
X ## ## ## ## ## ## ## ###### #### \n\
X ## ## ## ## ## #### ## ## \n\
X #### ### ## #### ## #### ##### \n\
X\n";
X
Xstatic CURVE pattern;
Xstatic int level, power;
X
Xinit(degree)
Xint degree;
X{
X PATH *x = &(pattern.dimension[0]);
X PATH *y = &(pattern.dimension[1]);
X
X x->quad[0].moreton = 0;
X x->quad[0].peano = 0;
X x->quad[0].next.accross = 1;
X x->quad[0].next.from = 0;
X x->quad[1].moreton = 2;
X x->quad[1].peano = 3;
X x->quad[1].next.accross = 0;
X x->quad[1].next.from = 0;
X x->quad[2].moreton = 3;
X x->quad[2].peano = 1;
X x->quad[2].next.accross = 0;
X x->quad[2].next.from = 0;
X x->quad[3].moreton = 1;
X x->quad[3].peano = 2;
X x->quad[3].next.accross = 1;
X x->quad[3].next.from = 3;
X
X y->quad[0].moreton = 0;
X y->quad[0].peano = 0;
X y->quad[0].next.accross = 0;
X y->quad[0].next.from = 0;
X y->quad[1].moreton = 1;
X y->quad[1].peano = 1;
X y->quad[1].next.accross = 1;
X y->quad[1].next.from = 0;
X y->quad[2].moreton = 3;
X y->quad[2].peano = 3;
X y->quad[2].next.accross = 1;
X y->quad[2].next.from = 0;
X y->quad[3].moreton = 2;
X y->quad[3].peano = 2;
X y->quad[3].next.accross = 0;
X y->quad[3].next.from = 3;
X
X level = degree;
X power = degree*2;
X
X}
X
Xint from_peano(peano,direction)
Xint peano;
XTRAVERSE direction; /* Position along Peano curve */
X{
X int bits = power;
X int from = direction.from;
X int peano_quad;
X int result = 0;
X RECORD use;
X
X while (bits)
X {
X bits -= 2;
X peano_quad = (peano>>bits)&3;
X use = pattern.dimension[direction.accross].quad[peano_quad];
X direction = use.next;
X result |= ((from^use.moreton)<<bits);
X from ^= direction.from;
X }
X
X return result;
X}
X
Xint to_peano(moreton,direction)
Xint moreton;
XTRAVERSE direction; /* Position along Peano curve */
X{
X int bits = power;
X int from = direction.from;
X int moreton_quad, peano_quad;
X int result = 0;
X RECORD use;
X
X while (bits)
X {
X bits -= 2;
X moreton_quad = (moreton>>bits)&3;
X peano_quad =
X pattern.dimension[direction.accross].quad[from^moreton_quad].peano;
X
X use = pattern.dimension[direction.accross].quad[peano_quad];
X direction = use.next;
X result |= (peano_quad<<bits);
X from ^= direction.from;
X }
X
X return result;
X}
X
Xcoord(moreton,x,y)
Xint moreton;
Xint *x, *y;
X{
X int bits = 1;
X *x = 0;
X *y =0;
X
X while (moreton)
X {
X if (moreton&1) *x |= bits;
X moreton >>= 1;
X if (moreton&1) *y |= bits;
X moreton >>= 1;
X bits <<= 1;
X }
X return;
X}
X
Xint combine(x,y)
Xint x, y;
X{
X int result =0;
X int bits = 1;
X
X while (x || y)
X {
X if (x&1) result |= bits;
X x >>=1;
X bits <<=1;
X if (y&1) result |= bits;
X y >>=1;
X bits <<=1;
X }
X return result;
X}
END_OF_FILE
fi
if test -f 'example.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'example.c'\"
else
echo shar: Extracting \"'example.c'\"
sed "s/^X//" >'example.c' <<'END_OF_FILE'
X#include <stdio.h>
X#include "peano_routines.h"
X
Xextern char copy_right[];
X
Xmain()
X{
X TRAVERSE direct;
X int moreton, peano, x, y;
X int i, top, level;
X int entered;
X
X printf(copy_right);
X
X do
X { do
X { printf("Level (>0) ? ");
X entered = scanf("%d", &level);
X while (getchar()!='\n') continue;
X }
X while (level <=0 || entered<1);
X
X init(level);
X top = 1<<(level*2);
X
X do
X { printf("Direction : Across in [0,1] & From in [0,3] ? ");
X entered = scanf("%d%d", &(direct.accross), &(direct.from) );
X while (getchar()!='\n') continue;
X }
X while (direct.accross < 0 || direct.accross > 1 ||
X direct.from < 0 || direct.from > 3 ||
X entered<2);
X
X for (i=0; i<top; i++)
X { moreton = from_peano(i,direct);
X coord(moreton,&x,&y);
X printf("%d th peano point AT [ X = %d, Y = %d ]\n",i,x,y);
X moreton = combine(x,y);
X peano = to_peano(moreton,direct);
X printf("\t[ X = %d, Y = %d ] AT %d th peano point\n",x,y,peano);
X }
X
X }
X while (level);
X
X}
END_OF_FILE
fi
if test -f 'makefile' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'makefile'\"
else
echo shar: Extracting \"'makefile'\"
sed "s/^X//" >'makefile' <<'END_OF_FILE'
X# Makefile for peano routines
X
XSDIR= .
XODIR= .
XRDIR= .
XBACKUP_DIR= /tmp
X
X# C Source
X
XSRCS= $(SDIR)/example.c $(SDIR)/peano_routines.c
X
X# Object Code
X
XOBJS= $(ODIR)/example.o $(ODIR)/peano_routines.o
X
X# Runs
X
XRUNS= $(RDIR)/example
X
X# Executable files to be created
X
Xall: example
X
X# Compile commands
X
Xexample: example.o peano_routines.o
X cc -g -o example example.o peano_routines.o
Xexample.o:
X cc -g -c $(SDIR)/example.c
X
Xpeano_routines.o: peano_routines.h
X cc -g -c $(SDIR)/peano_routines.c
X
X# Lint command
X
Xlint: $(SRCS)
X lint $(SRCS)
X
X# Remove unnecessary files
X
Xclean:
X rm -f $(ODIR)/core $(ODIR)/a.out $(ODIR)/*.o $(SDIR)/*~
END_OF_FILE
filou@bearcat.rutgers.edu (Lou Steinberg) (07/22/88)
In article <252@versatc.UUCP> aden@versatc.UUCP (Michael Aden) writes: > The problem with Floyd-Steinberg (and all the others) when used on scanlines > is a tendency towards "worm tracks", a propagation of error in a coherent direction. I don't believe the problem is "propagation of error in a coherent direction" so much as *lack* of propagation in a coherent direction. To state it more clearly (but less poetically :-), the problem is the existence of two pixels placed such that no error propagates between them, even indirectly. For instance, in raster scan Floyd-Steinberg, using our original 4-neighbor method, no error propagates from a pixel to the pixel one line below and two pixels back, so that when the first pixel turns on there is no way for this to inhibit the other pixel from firing. In a region of constant low brightness, however, the errors tend to build up more or less uniformly, so if the first pixel is on, chances are good the second pixel, not being inhibited, will be on as well, leading to worm tracks at this "knight's move" (one down and two back) orientation. With a serpentine scan, there is no such pattern of points that do not have at least an indirect error propagation path, and worm tracks are not a problem. There are other artifacts, such as apparent lines where a stable pattern (e.g. a checkerboard) suddenly breaks down or where two patterns meet out of phase (e.g. two checkerboards, one shifted a row down). (As a point of credit, the serpentine scan was first suggested by John Roach, one of our grad students, but as far as I know was rediscovered independently by Ulichney, and I think Ulichney was the first to publish it.) > While serpentine helps this, even better would be error propagation along > a non-trivial path, which leads us back to the Peano curve discussion of a few months > back. I never saw a discussion of how to do those fast. Anybody have any hints > they'd like to share? The idea of propagating error along a Peano curve scan path was suggested by Witten and Neal of the University of Calgary in the May 82 Computer Graphics and Applications ("Using Peano Curves for Bilevel Display of Continuous Tone Images"). They only propagate the error forward along the scan, rather than also off to the sides as in error diffusion, and the result is (to my biased eye) not as good. (They had apparently never heard of our method when they published the paper.) I've never seen anyone try a peano curve with error off to the sides. It sounds a bit messy, and I'm dubious that the results would be much better than serpentine scan, but I'd be interested to hear if anyone tries it. Witten and Neal do not actually cover the whole image with one peano curve - they cover a box (e.g. 64x64), and replicate that over the image. Probably you could pre-compute the peano path in the form of a list of offsets (+/- 1 or unchanged for x and y) that take you from one point to the next within the box, so that the extra cost of the scan would not add that much to the whole cost per pixel - and would perhaps be even faster than standard Floyd/Steinberg, since you would not have to compute the fractional errors. On the other hand, if the individual bits of the bi-level version of the picture are packed up into bytes, accessing them in peano order may be pretty expensive. -- Lou Steinberg uucp: {pretty much any major site}!rutgers!aramis.rutgers.edu!lou arpa: lou@aramis.rutgers.edu