Lineographic Interpretations of Images, with an Etch-a-sketch

A significant part of my computing degree was the individual project. I’d like to take this opportunity to talk about what I did, and hence provide a home for the project online. I’m not going to provide too many concrete details of the implementation—just outline the concept, talk about some of the challenges, and comment on the results.

Selecting the Project

I decided to propose my own project, rather than adopt one of the staff proposals. The idea being that I could choose something ‘fun’ that I would retain interest in. The initial problem is coming up with an idea which covers the criteria of a good project:

• it should require a notable amount of research, rather than just being a relatively straight-forward implementation problem
• it should be challenging enough so that it provides enough scope to demonstrate your abilities, whilst not being too difficult

I came up with a few ideas, some of which I still have intentions of pursuing. But the idea that I finally settled on seemed like it had the best scope in terms of the above criteria.

During the period that I was trying to come up with a project idea, I came across a video of an etch-a-sketch artist. I don’t recall the exact video, but there are plenty online. I was amazed at the skill and patience of the artist. The sketches take days to complete, and it made me wonder if it was the sort of thing a computer could be made to do.

Essentially this leads to the question: is a computer better at re-creating images with an etch-a-sketch than a human? Various interpretations of the word ‘better’ can be taken, but I will be looking at both the aesthetic results and the time it takes to complete the sketch.

The process of drawing an image on an etch-a-sketch is essentially that of lineography—drawing the whole image without taking your pen off the paper.

Overview

The project takes an image as its input and uses several techniques to extract features in the image before attempting to find a single path that can be used to represent the image. The path is then serialised, and passed either to an etch-a-sketch simulator, or over Bluetooth to an external device connected to a real etch-a-sketch.

Feature Extraction

A number of techniques were experimented with for feature extraction. The most promising was based on segmentation of the image—specifically, by a region-growing technique, based on the intensity of pixels.

In order to reduce ‘noise’, segments with a size below a given threshold will be absorbed by neighbouring segments.

The next stage is to come up with a path around the edge of segments. To achieve this, a technique very similar to the ‘marching squares‘ algorithm is used. The following image shows a trivial example with four segments, with paths around the segments shown as dashed lines:

Once paths have been found, the problem can be represented as a graph, and hence becomes a path-finding exercise. The graph is made up of nodes that represent the points were more than two segments meet (marked as circles on the image above) and edges between the nodes are annotated with the corresponding paths in the image. The following image shows how a graph can be constructed from our previous example:

Path Finding

The path finding problem is quite unique. Features of the problem are shared with the travelling salesman problem in that we are aiming to traverse all the edges (although the TSP actually aims to visit all the nodes). However we aren’t searching for an optimal solution—instead we are looking for an aesthetically pleasing solution.

The edges between neighbouring segments that have significantly different colours (based on their Euclidean distance) are given a higher weight, and hence are more likely to be drawn over repeatedly. This results in a darker line in the finished sketch (refer to the images below).

The general technique is to traverse the graph with priority given to edges that we want to appear darker, and then back-tracing when we get stuck, to a point that allows us to continue to unused edges.

Occasionally ‘hops’ must be taken, where two points must be joined so as to connect unconnected sections of the graph. In these cases, various alternative paths will be investigated to attempt to minimise disruption to the sketch. This usually results in a pair of smaller hops to and from a neighbouring line.

Drawing Techniques

A few techniques for drawing were experimented with. These were inspired by work done by human etch-a-sketch artists. Eventually, a hybrid technique was settled on: first to draw the outline of features in the image, and then to shade in regions based on their intensity. Shading was achieved by hatching—drawing backwards and forth over the region.

The following two images show relatively successful results being displayed on the simulator:

See the image below for a screenshot of the ‘Sketcher’ application: part of the framework developed for testing the various algorithms—referred to as ‘engines’:

Hystereis

Extensive testing with a real-life etch-a-sketch device revealed that a significant error would occur when trying to control the device programatically.

When a knob is rotated first in one direction, and then in the other, it takes a certain amount of rotation in the second direction before the pen begins to move again on the screen. This is due to tension building up in the strings within the device. I have referred to the error that this effect introduces as the ‘hysteresis’.

The effect is taken into account in the etch-a-sketch simulator so that it can be correctly accounted for when a path is being finalised. I won’t go into details here, but will mention that trying to simulate this effect in two dimensions is significantly more complicated than I was anticipating.

Nxt-A-Sketch

An extension to the project was to connect an actual etch-a-sketch to the program and draw out the sketch using stepper motors. To achieve this, a Lego NXT brick was used. A small C program was written to listen for commands via a Bluetooth channel and control the stepper motors. The images below shows how this physical connection was made:

This extension was relatively successful, and certainly made the final presentation more engaging. The device was able to recreate the sketches at a recognisable level, but would take a while to draw (about an hour)—though still significantly less time than a human artist would take. However, mechanical problems were frequently encountered with the device (likely caused by the wires slipping within the etch-a-sketch), which can be observed in the following photograph:

Conclusion

At this stage, it is important to consider whether or not the project was successful. It is difficult to achieve this objectively, but it was certainly able to create sketches far better than the average human can, and sketches can be produced much quicker than those done by artists.

However, to answer this question in a slightly more analytical way, we can compare the results of the program with sketches done by artists. Below are two such comparisons. The first shows what I would consider a successful sketch of Mario; the second, a less successful interpretation of Da Vinci’s Mona Lisa (original images from here and here):

Clearly the project has room for improvement. A more intelligent method of feature detection is required, and it would be nice if the program had some form of artistic abilities.

Having said this, I like to think that the level of sketches being produced are better than I would be able to do had I spent the time that I devoted to the project instead practicing with the device.

Tests revealed that my accounting for hysteresis was particularly successful. However, I won’t go into details here, as the tests are rather complicated to explain.

Further Information

I have essentially attempted to squash a large portion of my report into this post, so a lot of the details have been glossed over or simplified. If anyone is interested in a specific area of the project, feel free to contact me for more information.