Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!decwrl!shelby!neon!egret.Stanford.EDU!espie
From: espie@egret.Stanford.EDU (Marc Espie)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: xxx to HAM algorithm
Message-ID: <1991Jan24.232529.4055@Neon.Stanford.EDU>
Date: 24 Jan 91 23:25:29 GMT
References: <1991Jan23.170826.6194@uni-paderborn.de> <1257@pdxgate.UUCP>
Sender: news@Neon.Stanford.EDU (USENET News System)
Organization: LIENS, ENS, 45 rue d'Ulm, Paris (France)
Lines: 50

This wouldn't be the most accurate algorithm, but this is what I'd try.

- choosing the color palette.

There is a known algorithm for reducing the number of colors in an image.
Represent your color as points in three-d space (x=red, y=blue, z=green),
start with a possible reduced palette (gray shades would be ok).
Group the points of the image in clusters: for each point in the image, find the
nearest color in the palette (``euclidean'' distance).
Replace each color in the palette by the average of its cluster.
This process converges, fairly fast, to a good color palette approximating
your image.

- building the ham image.

Use dynamic programming. You have to build a line, each point can have
4096 colors. But the colors the next point can take only depend of
the color of the preceding point.
Associate a cost to each possible beginning of line, for instance add
the distances between computed points and reference points.
Now, the cost of a given point in a given color will be the best possible
cost for any beginning of line with that point at the end with that value.

What you have to build is an array of size 320x4096(point/color) holding:
- the cost of the point in the given color.
- the color the preceding point should have for attaining that cost.
In the end, you just have to take the best cost at the end of line,
and retrace back the corresponding best line. For your choice of the palette,
what you get is the best possible line for the given cost.

For a naive approach, you generate your array till point #i, then you
compute the costs for point #i+1. For each couple (point #i/color)
compute cost for (point #i+1/new color), where the new color can be
attained from (point #i/color). Keep only the best cost for each
(point #i+1/color).
For a given line, it will take about time on the order of 4096x64x320. 
Gross isn't it ?

You can trim that down, using the peculiarities of ham.
Try a first pass with only your 16 palette colors
(time on the order of 16x16x320, small!).
What have you then ? An already good best cost for some (point/color), 
which you know you can achieve.
When you build the whole array with 4096 colors, you can discard 
point/colors where you find only greater costs. I don't know
how much that reduces the number of point/colors to consider
(a difficult problem, you have to take the choice of the palette into account),
but I think the algorithm would then be significantly faster.

	Marc