http://allrgb.com challenges hackers to create a 4096x4096 image, using every 2^24 color once and only once.
There are many possible solutions, and I thought applying some optimization would produce interesting images. One choice is to make the image as smooth as possible.
Almost all models in physics contains so-called gradient term in its energy, which drives the system to smoother state. It is written as and it evaluates how rapidly some quantity f, be it wave function, air density, etc.., changes in space. That is, the more smoothly f changes, the lower the energy becomes. In general, lower energy state has smoother appearance. In particular, if f is constant everywhere, the gradient term is zero. In case of allrgb image, however, the pixel value can't be the same everywhere because all kinds of value must be there, thus the optimization will produce some smooth, non-trivial image. This is an interesting optimization problem.
Lets say we have an image R(x,y), G(x,y), B(x,y) where R, G, B=(0 .. 255) is the pixel value of RGB at position (x,y). The gradient term, hereafter we call it "Energy" and denote by E, is calculated as + (same for G and B), summed over all positions (x,y). In other word, it is squared color difference summed over all neighbor pixel pairs as shown below:
figure here
Since each pixel differs in color, the difference can't be zero, and minimum value is 1, when only one of R, G, B differs by 1 and the rest is the same. Or equivalently, it is minimum when the colors of neighbor pixels are also neighbors in the 256^3 RGB color space. Thus, when the all neighbor pixel pair is also neighbors in RGB space, it gives theoretical minimum. Is it possible?
First, let us consider a simpler case: We have 65536x1 image and place 256^2=65536 kinds of colors, R=(0..255), G=(0..255), and B=0, onto the image. We require that neighbor pixel pair on the image to be also neighbor in the 256^2 Red-Green color space. In this case, there are many possible solutions. The following figure shows typical example.
figure here
The solution can be visualized as a winding curve in the RG color space which consists of only 1-length segments and visits each grid once and only once. There are several names for this kind of curve. One is "self-avoiding path", because the curve never intersects with itself, otherwise a certain color appears twice or more. This kind of model is used to study the behavior of flexible polymer chains, since it consists of constant length line segments and can't cut across itself.
"Hamiltonian path" is more specific classification: it visits every point once and only once. The Hilbert curve, nicely explained here http://corte.si/posts/code/hilbert/portrait/index.html in detail, is a typical example. These are 1D lines which fills 2D plane.
Now back to the RGB case: We place 256^3 colors on a 4096^2 image. Consider four pixels shown below:
figure here
Suppose that pixel P1 and P2 is already a neighbor in RGB space, say (R,G,B) and (R+1,G,B). P3 should be a neighbor of P1 in RGB space. Since one neighbor (R+1, G,B) is already occupied, P3 should be either (R-1,G,B), (R,G+-1,B) or (R,G,B+-1). But if we set P3=(R-1,G,B), there is no way to place P4 so that it is neighbor of P2 and P3: the only valid choise is (R,G,B) but it is already occupied by P1. Thus P3 should be either (R,G+-1,B) or (R,G,B+-1). If we set P3=(R,G+1,B), The only valid choise for P4 is (R+1,G+1,B), and the 4 pixels forms a 1x1 square in the RGB space too. This is true whichever value you choose for P3. Thus the theoretical minimum of E is realized when all squares on the image also forms 1x1 square in the RGB space.
It corresponds to folding a sheet of paper consisting of 4096x4096 small squares and put it into 256^3 box. Is it possible? Unfortunately the answer is no. Unlike a 1D curve which can bend in any direction at any point, a sheet of paper can't: Imagine folding a sheet of paper into a square pillar and then trying to bend that pillar 90 degrees. You can't, because a paper can bend into only one direction.
Suppose that you have a sheet of rubber instead of paper. Then you can bend it as shown below:
Here the stretched part corresponds to a link between neighbor pixels which is "second neighbor" in the RGB space, that is, two of R,G,B values differ by 1. Thus it is expected that an optimized image has neighbor pixel color distance 1 at a large fraction of neighbors and some neighbors have 2 or longer color distances.
Using simulated annealing technique, in which one starts from high-temperature, high-energy state and gradually cools down the system to get lower energy state, I have obtained images with average squared neighbor color distance about 1.38, which indicates that many of neighbors have 2 or longer color distances.
Here are my Simulated Annealing codes:
This one is easier to read
This one is faster but unkind for source diver
