The HAM problem

Complexity of HAM

While I was tinkering with my code to render Amiga HAM images, one challenge was finding good images. So I considered generating them myself, but this is not as easy as it sounds. Building an image with a colour palette requires Colour quantisation, but HAM is a little bit trickier.

When selecting your palette for a classical colour palette image, like for an instance a GIF image, you want to have one representative for each colour cluster. In a HAM image you have two choices for each pixel: select a close colour in the palette, or derive the colour from the previous pixel.

Another way to describe the problem is that of a robot that needs to follow a path in 3 dimensional space, the robot is only allowed to either move along one of the axis (Manhattan norm) or to teleport to one of P arbitrary points. The goal is to select the teleport points and to plan a path of the robot: either move along one axis or teleport, so that its path is a close as possible to the points in the original path (the image to encode).

The position along each axis is discrete, for each there are P possibilities. There are also P teleportation points (palette entries) each with P3 possible values. So the total number of palettes is 𝐂 (P3, P). For each point in the path, there are 4 × P choices (1 teleport and 3 moves). So the number of possibles paths of length N is (4 × P)N. Clearly the total solution space is pretty big: 𝐂 (P3, P) × (4 × P)N. For a classical HAM file, N = 320 × 400 and R = 24, which is around 3.17 × 10231235 possibilities, so an exhaustive search is not a reasonable approach.

If the problem would only be that of finding a path, without the colour-table jumps, some linear programming would do the trick, but here, the selection of the path and the selection of the colour table are deeply connected…

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.