Dither Source

In article <5237@hubcap.clemson.edu> jcocon%hazel.cs.clemson.edu@hubcap.clemson.edu writes:
|Has any work been done on displaying 256 grey shades on a monitor with
|greater than two grey shades (i.e. black and white + some number of greys)?
|It seems that an extension to dither would be a good place to start.  So
|far as I know, rounding is the norm in hardware (yuck!  a good dither looks
|better than some 16 grey renderings I've seen!).

This program is short, so I though I'd just post it.  It uses the PXM file
format libraries I posted earlier, but the algorithm is easily separated
from the file format details.  This program dithers to n levels of grey,
default 2, and creates output in the range 0..255 from similar input.

------------------------------------------------------------------------
/*
 * 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