Art?

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.

[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.

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.

Roy Lichtenstein, 1992, Bedroom at Arles

Bedroom At Arles, generated by optmization process

Roy Lichtenstein, 1965, Brushstrokes

Brushstrokes, generated by optimization

Heartbeat to Midi, take 3

This project actually finished up sometime in 2013... but due to various forms of procrastination, it is getting written up now.  There is now a project page at http://foulab.org/en/user/strawdog/HeartBeat, complete with a link to video of the device in action. You may want to go there directly.

So in the last post, we had a heartbeat monitoring device that worked quite well, but the beats coming out of it were too irregular to be aesthetically pleasing as music.  We had some debate amongst ourselves about whether this interbeat variability was real, or an effect of the circuitry triggering at slightly different parts of the waveform on each cycle.  In the end, it does not matter.  The rhythm has to be smoothed out for the project to work as intended.

At this point, the problem really became a software one. 

Basically, the heart beat device software has a fast interrupt service routine that captures, as accurately as possible, the heartbeat pulse timing.  This is used to adjust the interbeat delay.  The main loop then emits a beat whenever this delay has expired from the last time a beat was emitted.   The actual calculations are performed in relatively idle times between these two events.

Testing showed that the main loop was nearly always taking less than a millisecond, so the Arduino's speed did not seem to be a critical factor.

My first attempts used various kinds of smoothing on the interbeat delay.  However, even with this, there was audible variability over the short term.  I also tried rejecting outlier observations and a few other nonlinear tricks, but audible problems remained (although simple outlier rejection remains in the final result to avoid "double beats").

Eventually I realized that the human ear wants stability in the pulses.  So I chose a new strategy.  The heart beat rate must fall on one of a set of stable rates, and, it must not change back and forth between these rates too rapidly.  Arbitrarily, I chose multiples of 5bpm.  There is also hysteresis in the changing between these rates.  To change from one rate to another, the computed interbeat delay is averaged over the last 12 beats and must move more than 80% of the way to the next bpm rate before the switch is made.

Two LED's were placed on the box - one to indicate detection of the heartbeat, and one to indicate the output of the note.  First tests were very promising - so a model two was made, using an Arduino Nano instead of a Diecimila, and a 9V instead of AA batteries conserved some space, so the whole thing fit in an Altoids tin.