From peter@sugar.uu.net Wed Oct 19 07:08:31 1988
Path: leah!bingvaxu!sunybcs!rutgers!mit-eddie!killer!texbell!sugar!peter
From: peter@sugar.uu.net (Peter da Silva)
Newsgroups: comp.sys.amiga
Subject: Re: Sculpt-4D Upgrade
Message-ID: <2862@sugar.uu.net>
Date: 19 Oct 88 11:08:31 GMT
References: <4779@louie.udel.EDU> <297@celia.UUCP> <2832@sugar.uu.net> <1121@leah.Albany.Edu>
Distribution: usa
Organization: Sugar Land Unix - Houston, TX
Lines: 60

In article <1121@leah.Albany.Edu>, rsb584@leah.Albany.Edu (Raymond S Brand) writes:
> In article <2855@sugar.uu.net>, peter@sugar.uu.net (Peter da Silva) writes:
> > And thirdly, they never seem to try propogating the HAM error backwards,
> > even though this might produce better results...

> This is easy to say, and sometimes easy to see, but it isn't easy to do for
> the general case.

Handling HAM at all isn't that easy to do for the general case... but people
still do it.

> If erradicating this defect is that important to you, devise and
> publish an algorithm/code that when given an X by Y image D bits deep, will
> output an X by Y HAM image and color table such that the "HAM shadows" are
> minimized for the image.

Well, the outline is conceptually easy. If you're handling HAM at all you have
some sort of function that will tell you the distance between seperate colors
so I'm going to take that as a given.

The simplest algorithm would be to alternate the error propogation on a
scanline basis, the way nroff does to prevent rivers of whitespace in one
or the other margin. A better algorithm would be:

Pass 1:
	Initialise all tracked colors and counts to 0.
	Scan:
		When dist(color(this pixel), color(next pixel)) > thresh
			If it's within thresh of a tracked color, inc
				its count, go on.
			Else add it to the tracked color list.
	Allocate top 16 tracked colors as true colors.
	
This is already more than most existing programs do, because they all seem to
allocate true colors on the fly while generating the image, or let you
do it manually. This of course assumes you HAVE a deeper bitmap to work
from. As an experiment you could also try allocate the top 8 as true colors
and then allocate the next 8 from the remaining colors unless a HAM change
will put it within thresh...

Pass 2:
	Scan:
		When dist(color(this pixel), color(next pixel)) > thresh
			If a single HAM change can make it within
				thresh, do it
			Else If it's within thresh of a true color, assign
				that color.
			Else if a single HAM change from LAST pixel will
				put THIS pixel within thresh of NEXT
				pixel, do it.
			Repeat for double HAM change, if intermediate
				HAM color is within thresh.
			Repeat for triple HAM change, if intermediate
				HAM color is within thresh.
			Else If a true color is within a HAM change of new
				color, use that as the new color.
			Else fall back on existing algorithm.
-- 
		Peter da Silva  `-_-'  peter@sugar.uu.net
		 Have you hugged  U  your wolf today?