I played with Beamlets a while (actually an age!) ago and had lots of fun, I’ve always wanted to do a blog recording some of my experiences and some of the seamingly win-win of Wavelet approaches.

Beamlets are a line detecting algorithm in similar vein to the Hough Transform, but with quite different qualities. Whereas Hough Tranforms are organised in a parameter space, Beamlets are organised into a dyadic structure similar to their famous brother … The Wavelet Transform. In the case of Beamlets, dyadic roughly means a recursive partitioning of a square (not necessarily, but best explained with a square in mind) into four smaller squares. In these squares, line paths (called beams) are then generated by sampling around the square’s border, connecting up each sample point to every other sample point in that square. You end up with a whole bunch of lines that arrange themselves into pretty patterns like this:

Here we start with the biggest square (top left) split that into four squares (top right: lines are blue, sampling points are red) repeat (bottom left) and repeat again (bottom right). This is called a four level pyramid.

The transform is then completed by overlaying this on to your image for analysis, and integrating along each path:

T(b) is the eventual intensity for beam b. To spot the best beams you then either threshold or take the maximum in each dyadic square.

The first key point is that even though there’s lots of connected lines you are actually limiting the combinatorial explosion of connecting every point in the image with every other point, so the algorithm has excellent $O(n ^2)$ complexity . The second key point, you can also, for free, approximate non-straight lines by connecting together beams at different pyramid levels and angles. This means there is the capacity to “approximately” detect arbitrary curves by looking for specific collections of beams, say ones that follow an intense wiggly path like in the image below:

So there’s the win-win … less computation more flexibility!

The thresholding is a bit arbitrary, I also developed a technique for doing this in a greedy way, so that pixels could only belong to the threshold of an individual line (we called this Maxbeam2). This worked out really nicely, and we applied it to some lines at various noise levels and managed to detect not only the lines but the side lobes resulting from generating the lines with a Gaussian (see below the first image is the series of lines the second image is the profile of lines with multi-pixel thickness (1st, 3rd, 4th and 5th from the left))

I finished this work a while ago and circumstances took me away from this research. I’m sure more stuff has been done with them since, but it’s a lovely idea and one day I’d like to do some more work with them. I’d like to think that there could be a general probabilistic line detecting approach, that could utilise Beamlets, but it would do away with the integrate and threshold in favour of a more grounded probabilistic framework. You could build up a function for lineyness which might rely on human subjective assessment of what a line is, because pure intensity isn’t everything…

Thanks to Jim and Simon