linux.conf.au 2007 hackfest notes

With the help of the folks here from OzLabs, I coordinated the linux.conf.au hackfest. I thought it'd be neat to post a few notes on the questions, as well as some approaches that we liked.

If you're interested in taking a look before we've spoiled all of the answers, the hackfest questions are up here.

The answers shown here are by no means the outright best way to solve the problems presented, but should be a decent starting point. There may be better answers around - in fact, if you have a suggestion, feel free to email me. However, the judges' decisions on the hackfest prizes are final.

Because this will be a fair bit of content, I'll split up the discussion over a number posts, each covering a couple of questions.

Finally, kudos to the participants of this year's hackfest, we had some great entries. Hope to see you all next time!

1. Jail Break

This one could be solved by a touch of googling. The core of the answer looks something like:

        mkdir(TEMP_DIR, 0755);
        chroot(TEMP_DIR);
        for (x = 0; x < 1024; x++)
                chdir("..");

        chroot(".");

However, some folks took the googling thing a little too far, and also included other functionality, like starting a shell in the broken-out environment, instead of writing to /tmp/escaped.txt. So, for my first piece of advice for the aspiring hackfest entrant: read the question.

2. Finding circles

Write a program to find the position of circles in an image.

Your program should take one command-line argument, the filename of the input image. The output of your program will be the coordinates of circles found in the image, one circle per line, in the format

<x-coordinate>,<y-coordinate>

For example:

[jk@pokey hackfest]$ ./find-circles input.png
331,79
399,204
367,133
579,44
212,237
206,416
516,144
292,409
161,438

Coordinates are relative to the top-left corner of the image.

The input file will be in png format, greyscale, with 8 bits per pixel. We suggest you use a support library to read your image data; if your submission is in C, you can use read-png.c as an example of using libpng, or include it as part of your entry.

Sample images

The following images are representative of the input images we will test your program with. Each of these images contains 30 circles; the final images may contain varying numbers of circles. Click on the image for the full-size version.

no noise	1% noise	4% noise	32% noise	64% noise

You may assume the following:

• All of the circles are fully contained within the image
• The circles don't overlap (however, they may be touching).

Updates

The circles we test with may be a different size than the sample images, but you can assume that all circles in a single input image are the same size.

We will test your program on a set of images, with a total of 100 circles. One point is given for each correctly found circle (within a tolerance of ±2 pixels in both axes). Points will be deducted for reporting spurious circles.

One "classic" approach to finding circles is to use a Hough Transform. To do this:

1. Threshold to produce a binary image.
2. Remove noise, for example, using an open-close operation.
3. Perform edge-detection, so you have a set of circle outlines, rather than solid circles.
4. Allocate a 3D accumulator array (ie, width × height × possible radii).
5. For each white pixel in the image, and each possible radius r, count it as a 'vote' (in the accumulator array) for a circle centered on all points r-distance from the pixel.
6. Find maxima in the accumulator array. Coordinates of the maxima correspond to the centres of the circles.

The disadvantage of this approach is that it takes a lot of time to code, and the hackfest only runs for 3 hours (the advantage being that you get to make pretty graphs like this).

So, we can do a couple of things to side-step some of the tricky stuff. These really highlight the 'hack' part of 'hackfest':

• Instead of edge-detecting, just count each white pixel as a vote for a set of circles from 0 to r distance away. The accumulator gets a little messy, but it should still work
• Because we're now counting so many points, and not relying on edge detection (which really seems to suffer from a noisy image), don't worry about removing noise, it should all average out in the end, right?
• The thresholding doesn't need to be a separate step, just do an "if (pixel > threshold)" when walking through the image.

So, I'd probably end up coding something like this: (it may look like python, but it's pseudocode)

        for y in 0..rows:
                for x in 0..cols:
                        if image[y][x] > threshold:
                                increment_accumulator(accum, x, y, radius)

where increment_accumulator(accum, x, y, r) increments the accumulator values at all points which lie within a circle of radius r centered at (x,y). That can be repeated for possible radii.

Impressively, this is the basic gist of the entries we got. Even more impressively, one of the submissions managed to find 9 of the 10 circles in this image:

Pretty freakin' cool, huh?