Recently I became altogether too interested in a code golf problem that was posted on stackexchange. The problem was to develop a program to draw Van Gogh's starry night using a program of maximum length 1024 bytes. The winning programs used existing image compression algorithms, which makes logical sense, but was somehow aesthetically unsatisfying. The originator reposted a challenge to come up with an optimization based approach, that beat the existing non-off-the-shelf compression approach. The problem is particularly interesting to me because I like algorithms for drawing. The above image is the result I came up with. The original, of course, looks like this:
This took a long time. I chipped away at it for a while, got distracted, poked at it periodically - these optimizations take a long time to run - but finally managed to beat the existing top score for non-off the shelf compression. Here's what I said on Stack Exchange, and then a bit more detail on a few points.
Everybody has probably forgotten about this problem by now, except me....
This problem interested me far too much, especially as it quickly became apparent that approaches using image compression algorithms were definitely in the lead, but yet somehow unsatisfying from an aesthetic standpoint. Approaches based on optimizing a set of drawing primitives were somehow more pleasing from a code aesthetic point of view, but seemed blocked just above the 5000 score.
Nneoneo's method that did not use an off the shelf image compression beats the 5000 mark, but does so by encoding a tiny image and upscaling it.
Here is a program that uses drawing primitives only, is generated automatically by an optimization method, and manages to get a score of 4749.88.
Cramming raw bytes into python code (which is not as simple as suggested earlier in this thread, more characters need to be escaped than just backslashes and nulls, dig into the code here for details).
Compressing the color space into two dimensions. Fascinatingly, this particular starry night image is nearly a plane in RGB space.
As a first primitive, I place a horizon line, splitting the image into two different colored blocks. Afterwards, as a basic primitive I used a circle dragged between two points. This looked vaguely like a brushstroke to me, but was possible to express in 7 bytes. For the search process, I used a guided pattern search. It proceeds by alternately adding a primitive, and optimizing its parameters. The primitive is added on the point where the blurred signed error is highest. The parameters are optimized by exhaustive line optimization over a small domain, one after the other. Forty to fifty primitives are added, and optimized individually. Then, the list of primitives is pruned down to size by throwing away the primitives that help the score the least.
This still does not beat nneoneo's score. To beat that score, a second stage optimization was required, which goes again through the process of adding primitives at each of several filtering levels, and throwing primitives away to trim the generated program down to size.
What was really interesting to me was the idea of applying this to other images. I applied it to a couple of other images, and provide further details and animation of the primitives being drawn in my blog here.
starrynight is run first, followed by stage2optimization. The resulting program is also there, in the same directory.
Here's a video of the primitives being drawn. The blur - which improves the score by nearly 600 points(!) - is faded in at the end.
While the code golf aspect of this was kind of fun, I also got interested in the drawing process. I applied it to two other images - both by Roy Lichtenstein. Bedroom at Arles seemed somehow appropriate since it was an interpretation Lichtenstein made of a Van Gogh. And Brushstrokes - besides being quintessential - seemed also somehow on point. Here are the results - the colors may be a bit off as the script still compresses the color space into a plane, which doesn't really apply in general.
No comments:
Post a Comment