AllRGB March 2014
Generate images that use all 16,777,216 RGB colors exactly once.
Efficiently create AllRGB images that target an input image. The input must be 4096x4096px. The output will also be 4096x4096px and will contain all 16,777,216 distinct RGB values once and only once.
See allrgb.com for details on the concept.
Links: GitHub
Algorithm
An octree is used to spatially represent the RGB colors. The octree is only 9 levels deep from root to leaf (inclusive). Each node in the octree stores a count for how many colors in its subtree are still available to be used. The octree is stored in a flat array, as it is a complete octree. Children indexes are computed as:
8 * i + 1 + x
...where i is the current index and x specifies the xth (0 - 7) child. To find a color in the octree, use a single bit from each of R, G and B to form a 3-bit number representing the next child node to visit. Repeat this process from the most significant to the least significant bits.
For example, if RGB = (27, 89, 233)...
12345678
R: 00011011
G: 01011001
B: 11101001
001, 011, 001, 110, 111, 000, 100, 111 => 1, 3, 1, 6, 7, 0, 4, 7
When encountering a node with a value of zero (meaning no colors are available in that space), visit a different child instead to find as similar of a color as possible. But don't just pick a random other child, pick one that will minimize error, especially in the green channel. A lookup table is used for this purpose.
LOOKUP = [
[0, 1, 4, 5, 2, 3, 6, 7],
[1, 0, 5, 4, 3, 2, 7, 6],
[2, 3, 6, 7, 0, 1, 4, 5],
[3, 2, 7, 6, 1, 0, 5, 4],
[4, 5, 0, 1, 6, 7, 2, 3],
[5, 4, 1, 0, 7, 6, 3, 2],
[6, 7, 2, 3, 4, 5, 0, 1],
[7, 6, 3, 2, 5, 4, 1, 0],
]
Optionally, if some areas of the image are more important than others, such as a face, let those pixels pick their colors first - give them priority. This was not done in the sample image. The pixels in the sample were simply ordered randomly.