For a lesson about JITs in a colleague's compiler course I wrote a small just-in-time compiler for deterministic finite automata in Python, using PeachPy. I planned to write a complete blog post about them, but it doesn't seem to quite be happening, so below is the code. It has a few comments at least.

The idea is to show a few of the typical things a JIT can do that a static compiler can't: - switching between interpreter and compiled code - profiling to find out which part of the program are executed most commonly - deoptimization back to the interpreter - patching of existing code if new code is added

Here's the code:

(if you don't want to read anything just click this button to play around: TLDR)

Last year I had the chance to experience the choreographer William Forsythe's video installation City of Abstracts in the Folkwang museum in Essen. Here's a video of a few people in front of it:

The installation consists of an open space, a camera and a big screen. The camera films the people that are moving and standing in the space, the screen shows a distorted version of the filmed images. The distortion seems to have the following properties: people that are standing still appear only minimally distorted on the screen (for example the person on the left in the back, in the first part of the video). People that are moving across the field of view of the camera turn into diagonally stretched versions of themselves (for example the person moving from right to left at around 0:20). The head is ahead (hrm) in their direction of movement. If they then stand still, their heads stand still first, while the rest of their bodies slowly catch up, from top to bottom.

While I was standing in the museum playing around, I started to wonder how the installation worked. At first I thought it must be a fairly complicated effect, that somehow analyzed motion and did a complicated transformation. However, after some more playing, running back and forth etc. I became convinced that the program is actually quite simple. In the following I want to explain how it works and recreate the effect in Javascript.

A Miniature City

Because it is quite hard to reason about what happens in a big video, let's start by looking at a miniature version of the problem. The following is a 5x5 pixel input video where a stack of pixels first moves left, then right, and then back and forth for a bit:

Start

We want to find out how this input video has to be transformed into an output video in a way that recreates the effect of Forsythe's installation.

Above we saw that the bottom of a moving object is somehow further back in time than the top. This could mean that the output video uses older and older lines of pixels, from top to bottom. The top row of pixels would be from the current camera input, the second row from one frame back, the third row from two frames back, and so on. Let's try this for the miniature input video:

Start Pause

This seems to recreate the effect! When the stack of pixels moves left, it is transformed into a bottom left to top right diagonal, when it moves back it slowly becomes a top left to bottom right diagonal. When it stands still, the top pixels stand still first in the output, the lower pixels slowly catch up. Below you can look at the output pixel video:

Start

The Real Thing

Now that we know how the effect works, we can apply it to a real video, using a webcam. If you click Start and give permission, you can try it yourself (The webcam video is not transmitted anywhere, just shown below). The left video is the webcam output, the right video is the transformed version. If you are interested in the Javascript code, you can use the Glitch button in the top right corner to inspect (and edit) it.

The first video is directly the output of the webcam, the second video shows the "timeshifted" output as explained above. To see anything interesting happening, you need to move around in front of the webcam. Sideways motions are easiest to understand. Remember that the second video takes a while to catch up with your movements. Some fun things to try: walking across the room, slowly shaking your head, jumping, rotating your arms...

Start

Fullscreen

(Aside: I am quite impressed that it works just fine to implement this piece of video processing in Javascript and have it run relatively fluidly in a browser on a phone.)

One parameter we can play with in the above transformation is we can make the lower pixels catch up faster with the upper pixels by doing the transformation block-wise, instead of a single row of pixels at a time. If you increase the block size below, the output video will become less laggy, but on the other hand more blocky.

Relationship to Rolling Shutter

An amusing sidenote is that we can use the transformation to understand the rolling shutter effect. Rolling shutter happens when taking a picture of a fast moving object with a smartphone camera. Those cameras don't record the whole image at once, but do it line by line. And if the object moves very fast relative to the time the phone takes to record the whole image, different parts of the final image show the object at different points in time (and thus space). What the effect above does is artificially slow down the creation of a picture. Therefore we can recreate the effects that rolling shutter gives with objects that move much more slowly, for example by rotating an arm.

LIT Fischer developed his light-graphics step by step, an oscillating rhythmically-flowing, undulating movements on the screen – "heterophonics" – as he calls them. The variety of the undulating lightwaves, often brought about by minute deviations from the original program, fascinate the artist. With his light-movement studies he actually succeeds in visualizing series of musical tones, sound sequences and meditative song. Dr. Eva Karcher

I've been fascinated by the light art installations of artist Jürgen LIT Fischer since a while, e.g. "Fraktal" as part of the Tetraeder in Bottrop:

Photo CC-BY Mirek Claßen

Later I found out that LIT Fischer used to do computer art in the 1980s using Fortran and a plotter. Here are two examples:

"Mit Zwischenraum, hindurchzuschaun" ("with space between to look through"), Jürgen LIT Fischer, 1986. Aside: the title is a part of a poem by Christian Morgenstern, "Der Lattenzaun" (click through for an English translation)

"Intervalle" ("intervals"), Jürgen LIT Fischer, 1987

Dreiklang

"Dreiklang" ("triad"), Jürgen LIT Fischer, 1987

"Dreiklang", top three panels, 1987

Looking through some of the books about his exhibitions I found that one of them contained fragments of the Fortran code that he used as the basis of one of the installations:

Despite not knowing Fortran I decided to still try to port the code to Javascript (which I of course also don't really know, but at least it's easier to Google and more importantly, to run). I guessed that the Z* functions were responsible for communicating with the plotter. In particular that the ZDRAW function had to move the plotter pen somehow.

After some amount of fiddling I managed to produce the output below. I used different parameters than in the Fortran source, but reading some more about his working style, Fischer anyway played around with the parameters a lot (in fact, his final output is usually a layer of many different semi-transparent versions of the outputs of the same program, using different colors).

What we see is basically a series of sine waves, plotted at a fixed distance below each other. They all have the same frequency but the amplitude goes up from 0 to some value, and then down to 0 again. What I find cool is how simple the ingredients are: just lots of sine waves, but the result is still quite an interesting effect.

Compared to the Fortran code I changed things somewhat: I fixed the code duplication between the code that computes the upper and the lower half of the waves and I removed the extra level of loops responsible for increasing the stroke width by drawing the same line several times with a tiny offset (that's much easier in svg!). I also tried to translate the variable names from abbreviated German to English. If you want to read or modify the source code, use the Glitch button in the upper right corner!

The Discontinuity in the Middle

In the picture of the real artwork above, those waves are split up into three acrylic glass panels. In the top middle panel there is what looks like some strange discontinuity in the middle.

"Dreiklang", top middle panel, rotated

I suppose that was done intentionally, but I still wanted to try to figure out where it came from. And indeed, playing with the parameters some more, we can reproduce it:

To understand this effect, let's look at an even more exaggerated view:

I have added in red to the left the size of the amplitude of each sine wave. On the peak of every wave, the lines above bunch together, and the lines below are spread apart. The eye notices the sharp jump between the distances of the lines in the middle. The reason for that jump is the fact that the amplitudes of the stacked waves vary linearly up, and then down. But since that interpolation function is piecewise linear, it has a non-smooth part in the middle.

This is going beyond understanding the original code, but we can fix that! Instead of interpolating the amplitudes linearly, we can do it smoothly, e.g. again with a sine wave:

Interactive Version

If you want to play around with the parameter space too, here's an interactive version:

right-click and save as to download svg