Dithering (Floyd-Steinberg) Source

/*
 * dither -- use a reduced set of grey values to represent an image
 *
 * Copyright (C) 1988 by Dale Schumacher.
 *
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose and without fee is hereby granted, provided
 * that the above copyright notice appear in all copies and that both that
 * copyright notice and this permission notice appear in supporting
 * documentation.  This software is provided "as is" without express or
 * implied warranty.
 *
 *
 * Notes:
 *
 * [1] Floyd-Steinberg dither:
 *  I should point out that the actual fractions we used were, assuming
 *  you are at X, moving left to right:
 *
 *		    X     7/16
 *	     3/16   5/16  1/16    
 *
 *  Note that the error goes to four neighbors, not three.  I think this
 *  will probably do better (at least for black and white) than the
 *  3/8-3/8-1/4 distribution, at the cost of greater processing.  I have
 *  seen the 3/8-3/8-1/4 distribution described as "our" algorithm before,
 *  but I have no idea who the credit really belongs to.

 *  Also, I should add that if you do zig-zag scanning (see my immediately
 *  previous message), it is sufficient (but not quite as good) to send
 *  half the error one pixel ahead (e.g. to the right on lines you scan
 *  left to right), and half one pixel straight down.  Again, this is for
 *  black and white;  I've not tried it with color.
 *  -- 
 *					    Lou Steinberg
 */

static char	_Program[] = "dither";
static char	_Version[] = "1.3";
static char	_Copyright[] = "Copyright 1988 by Dale Schumacher";

#include 
#include 
#include "pxm.h"

#define	DEBUG(x)	if(0)/* x */

#define	range	255		/* maximum pixel output value */

int	levels = 2;		/* number of output levels */

banner()
	{
	printf("%s v%s -- %s\n", _Program, _Version, _Copyright);
	}

usage()
	{
	fprintf(stderr,
		"usage: %s [-n levels] inpxm outpxm\n",
		_Program);
	exit(1);
	}

main(argc, argv)
	int argc;
	char *argv[];
	{
	register PX_DEF *ipx, *opx;
	FILE *f;
	register int c;
	register char *p;
	extern int optind;
	extern char *optarg;

	while((c = getopt(argc, argv, "n:V")) != EOF)
		{
		switch(c)
			{
			case 'n':
				levels = atoi(optarg);
				break;
			case 'V':
				banner();
				exit(0);
			case '?':
			default:
				usage();
			}
		}
	if((argc - optind) < 2)
		usage();
	else
		{
		ipx = px_ropen(argv[optind++]);
		opx = px_wopen(argv[optind++],
			(PXT_PIX | PXT_BIN),
			ipx->px_width, ipx->px_height, 8, NULL);
		dither(ipx, opx);
		px_close(ipx);
		px_close(opx);
		}
	exit(0);
	}

dither(ipx, opx)
	PX_DEF *ipx, *opx;
	{
	unsigned int xsize, ysize;
	unsigned int y, x;
	register int xslop, *yslop, dslop;
	register int i, j, k, t, q;
	register PX_BYTE *ibuf, *obuf;

	xsize = ipx->px_width;
	ysize = ipx->px_height;
	ibuf = px_rowalloc(xsize, ipx->px_psize);
	obuf = px_rowalloc(xsize, opx->px_psize);
	yslop = (int *) px_alloc(xsize * sizeof(int));

	t = ((range + 1) * 2) / levels;		/* threshold factor */
	q = range / (levels - 1);		/* quantization factor */
	j = (9 * range) / 32;
	for(x=0; x range)		/* quick hack to fix overflow */
				j = range;	/* which shouldn't happen :-) */
			px_wgrey(opx, obuf, x, j);
			i = i - j;
			k = (i >> 4);		/* (i / 16) */
			xslop = 7 * k;
			yslop[x] = (5 * k) + dslop;
			if(x > 0)
				yslop[x-1] += 3 * k;
			dslop = i - (15 * k);
			}
		px_wrow(opx, obuf);
		}
	}
Discuss this article in the forums
Date this article was posted to GameDev.net: 7/16/1999
(Note that this date does not necessarily correspond to the date the article was written)
See Also:
Dithering