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.
[Edit: snipped for brevity, but available here]
It uses a number of tricks used previously here:
- Using a blur to push the final score up a bit
- 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.
The two programs used to generate this won't actually fit in the space allowable on Stack Exchange posts, but they are on github: https://github.com/str4w/starrynight/tree/StackExchange
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.
|Roy Lichtenstein, 1992, Bedroom at Arles|
|Bedroom At Arles, generated by optmization process|
|Roy Lichtenstein, 1965, Brushstrokes|
|Brushstrokes, generated by optimization|