From ahg@k.cc.purdue.edu.UUCP Wed Oct 26 14:55:41 1988
Path: leah!bingvaxu!sunybcs!rutgers!mailrus!purdue!i.cc.purdue.edu!k.cc.purdue.edu!ahg
From: ahg@k.cc.purdue.edu (Allen Braunsdorf)
Newsgroups: comp.sys.amiga
Subject: HAM Register Selection (was Re: Sculpt-4D Upgrade)
Summary: Use modified median cut algorithm
Keywords: distance squared  median cut
Message-ID: <2720@k.cc.purdue.edu>
Date: 26 Oct 88 18:55:41 GMT
References: <4779@louie.udel.EDU> <297@celia.UUCP> <2832@sugar.uu.net> <1121@leah.Albany.Edu> <2862@sugar.uu.net>
Reply-To: ahg@k.cc.purdue.edu.UUCP (Allen Braunsdorf)
Distribution: usa
Organization: 3-D Computer Graphics From Hell
Lines: 72

In article <2862@sugar.uu.net> peter@sugar.uu.net (Peter da Silva) writes:
>In article <1121@leah.Albany.Edu>, rsb584@leah.Albany.Edu (Raymond S Brand) writes:
>> 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:
>
[Goes on to threshold distance formula and then do some HAM and selection stuff]

Admittedly, I haven't read all the followups to this, but here's a very
brief description of the algorithm I use.  The output is >really< sharp!

1.  Generate a histogram.  This histogram should contain a count for each
possible color.  That makes 16 x 16 x 16 = 4096 cells.  In each cell, put the
sum of the "diminished distance formula" calculated for every point of that
color in the image but not in the first column.

	The diminished distance formula at a point is found from the color
	of that pixel and the pixel to its left.  Let dr, dg, and db be the
	absolute value of the difference between the red, green, and blue
	components of the two points respectively.  The dimished distance is
	then the sum of the squares of the two lowest deltas.  This will
	give a number in the range (0, 450).

The histogram will then contain numbers that will fit in a ULONG.

2.  Median cut this histogram into sixteen bricks as described in Paul
Heckbert's classic article (SIGGRAPH '83).

3.  Optimize register 0.  Find which of the register values found in step 2
will give the lowest mean dimished distance from the pixels in the first
column.  Put this in register 0, the order of the other registers doesn't
matter, but I sort them.

4.  Convert the image.  For each pixel, find the closest register color (using
the ordinary distance formula).  Then find the dimished distance between this
pixel and the one to its left (or register 0 if in the first column).  If
the register distance is lower than the neighbor dimished distance, use that
register to render this pixel, else use HAM.  This will use HAM in the case of
a tie.

This algorithm >can< be coded in a very efficient manner.  It can also be a
major waste if implemented poorly!  Be careful out there! :-)

If there is a set of registers that will display the picture properly, this
algorithm will find it.  If there is not, the approximation is very close.

Yes, I've coded this, I use it, and I love it.  It is part of a general
image resampler that I am writing for the Amiga.  It will convert IFF pictures
of any size (aspect ratio, number of colors) (well, within the limits of the
format, of course) to any other size (aspect ratio, number of colors).  I am
using it to convert "real pictures" (512 x 512 x 24 bits) that I coded in
IFF(!) into Amiga interlaced, overscanned, HAM pictures (also in IFF, natch).
I hope to have this program all done by the end of the year.  I could
probably get it done sooner with some effort, but so far nobody (except me)
has been thrilled by it, so I left it half-baked on the back burner.
Think it's marketable?  If so, be >sure< to get in touch with me! :-)

Responses to this article in this newsgroup might miss me, as I do not read it
regularly.  Try mail or comp.graphics instead.

Allen Braunsdorf			WORK	k.cc.purdue.edu!ahg
General Consultant			SCHOOL	ei.ecn.purdue.edu!braunsdo
Purdue University Computing Center	HOME	ee.ecn.purdue.edu!gawk!akb