# Quickly finding rough lines in sets of points

In a particular class of detectors, our data comes out as pairs of points in two dimensions, and we want to string these points into lines.

The data is noisy, and is binned in one direction but not in the other. We can't guarantee a hit in every bin even when each detector element is working, so there may be skips.

Our current analysis chain looks like

1. Adjust hits for the calibration of individual detector elements
2. Find clusters
3. Rough fit lines to the clusters
4. Connect up clusters into longer line-like structures
5. ...

This question concerns step (3).

We've been using a Hough transform for that step and it works well, but as we try to scale up from the test-bed to simulation of a full-scale project it becomes unacceptably slow.

I'm looking for a faster way.

For those who might care the actual use case here is a Liquid Argon Time-Projection Chamber

• We also did a recursive Hough Transform method for path tracking through Multi-Wire Proportional Chambers at FermiLab. Erik Kangas' senior thesis has all the details. I think this is still the best way to do it. Commented Dec 4, 2011 at 4:02
• Did you mean "...pairs on point..." or "...pairs of points..." in the first sentence? Commented Dec 5, 2011 at 14:54

There is a probabilistic version of Hough transform (PHT) that is faster. As described by Bradski & Kaehler in their OpenCV book:

The idea is that the peak is going to be high enough anyhow, then hitting it only a fraction of time will be enough to find it.

The OpenCV library presents an implementation for the PHT.

There are other alternatives. It's not difficult to create a distributed version of the Hough transform. Just break your point set into smaller chunks and use the MapReduce framework to sum up all the accumulators. Other idea is to perform a coarse version of Hough transform using a parameter space with low resolution. Pick your best candidates and run a finer iteration using a parameter space presenting a higher resolution. Maybe this is the idea behind the Gandalf's FHT.

• The PHT was proposed in: Matas, J. and Galambos, C. and Kittler, J.V., Robust Detection of Lines Using the Progressive Probabilistic Hough Transform. CVIU 78 1, pp 119-137 (2000).
– TH.
Commented Feb 10, 2012 at 15:12
• The course then fine procedure can be generalized to multiple steps which is what Gandalf does. Commented Feb 10, 2012 at 18:40
• BTW--In the time since I asked this question, a colleague has added a module using the progressive probabilistic version of the transform to our code. This came with several associated changes so it is hard to characterize exactly what difference it made, but it is part of a package that sped up a couple of steps of the analysis considerably. So, I'm going to accept this as the "winning" advice. Commented Sep 7, 2013 at 13:50

I colleague has found the Fast Hough Transform in the Gandalf library, which looks very promising but may be a lot of work to integrate, so I am looking for other approaches.

The Gandalf implementation is interesting: they evaluation the accumulator space in a recursive way as if traversing a quad- or oct-tree. Regions without much density are thrown out as they go.