Circle Packing - brute force approach

Earlier this year, as part of my degree, I carried out a project that involved measuring the fractal dimension, and packing densities of various systems. I thought I'd have a play around with something along similar lines, circle packing.

There are many subtle and interesting and above all intelligent ways of packing circles into spaces, but this is not one of them. I decided to take a brute force approach. This is the structure my algorithm took:

• Pick a random point, if it is within any circles that already exist find a new point
• Increase the radius of that point until it overlaps with either the edge of the scene, or another circle on the scene.
• Draw the circle

This is as far as I can tell, both the simplest approach and the slowest. Lets take a look at the results, click the image to run the application. An interesting idea is to draw a line between each circle when they collide. This forms a kind of node based structure between circles, creating a network where larger circles hold more power in the network. I wonder if you could create a page ranking system based on something like this...?

Benoit Mandelbrot - Fractals and the art of roughness

A personal hero of mine talks about fractals.



I enjoyed his quote at the end and found it quite relevant to a lot of the work I do on this blog:

"Bottomless wonders spring from simple rules... repeated without end"

Computer Vision and the Hough Transform

I was working on computer vision yesterday and went to my girlfriend's graduation ceremony today so haven't had a chance to upload. I decided to take another look at computer vision - and in this case a slightly more intelligent one than previously. The method I took a look at is known as the Hough transform. I think that the simplest and most effective way to explain how the Hough Transform works is using a bullet pointed list, but before I begin you should know that it is used to extract information about shape features from an image. In this case a line / all the lines present in an image.

• We start with an image in which we want to detect lines:

• First of all apply a Canny Line Detector to the image isolating edge pixels:

• At this stage, to reduce computation required in the next stage I decided to sample edge pixels instead of using all of them. The results for s=0.2 and s=0.9 are shown below:

• Then, for every possible pair of sampled edge pixels, calculate the angle of the line between it, as well as the distance to the origin. Plot a cumulative bitmap graph of angle against distance. The way I did this was to increase the pixel value in that location each time a distance/angle occurred. Recall that a line can be defined by an angle and distance to an origin. The resulting bitmap is known as the Hough Transform:

• By increasing contrast and playing around with thresholds in the Hough transform it is clear that 8 distinct regions are visible, we know that the detector has done its job as there are 8 lines in the original image:

• Remember that each point provides us with data about the line angle and distance from the origin, so lets use the flash API to draw some lines:

• As you can see the result isn't too bad at all, we get 8 lines, although they are a bit diffuse. The next step is to look into grouping algorithms to only pick single pixel points from the final hough transforms for each lines. In this version of the program a line is drawn for each pixel, which results in an angle and position range for each line. Pretty close though.

So thats how a Hough transform works for line detection. Just for fun, heres a real time hough transform on a webcam stream. Just click the image below to launch it.