Generating colour maps with spacefilling curves
07 January 2010After my post about my Quixotic quest to draw a portrait of the Hilbert curve, Chris Mueller pointed me to some fascinating related work he had done generating colour maps of images. Chris's method was to extract the colours from an image, sort them in natural order, and then draw the pixels out onto a Hilbert curve. The results are pretty, but have a blotchiness that demonstrates the poor clustering properties of a natural order sort nicely. If you've read my previous post (you have, haven't you?), you'll be immediately struck by the idea that we can improve this by sorting the pixels in order of the 3d Hilbert curve traversal of the RGB colour cube (you were, weren't you?). This would give us near optimal clustering, keeping similar colours together and eliminating the blotchiness. If we have a Hilbertorder sorting of the pixels, we can also project this onto other traversals of the pixels of the destination image. Using the ZigZag curve I introduced in the previous post produces a very nice result too, showing that the order in which the RGB cube is traversed is more important than the destination map.
In the images below, natural is a naturalorder colour sort projected onto a Hilbert curve (Chris's method), hilbert is a Hilbertcurve order colour sort projected onto a Hilbert curve, and zigzag is a Hilbertcurve order colour sort projected onto a ZigZag curve. I've used the same images Chris used to make comparison with his other interesting visualisations easy.
natural

hilbert

zigzag

natural

hilbert

zigzag

natural

hilbert

zigzag

natural

hilbert

zigzag

natural

hilbert

zigzag

The images are from the Flickr Creative Commons collection. The tiger image is © David Blaikie. The girl image is © Bruce Tuten. The still life is © DeusXFlorida. The beach image is © Hamed Saber. The tent image is © drusbi.
The code
I've updated the scurve project (where I'm collecting algorithms and visualisation tools related to spacefilling curves) to include a "colormap" tool to generate colour maps. The images above were can be generated using commands of the following form:
colormap s 128 c [colour traversal] m [map] src destination
There are a lot of other striking permutations and combinations to explore  the colour traversal and destination map can be any of the spacefilling curves supported by scurve.