12
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Matt Knepley
    Commented Dec 4, 2011 at 4:02
  • 1
    $\begingroup$ Did you mean "...pairs on point..." or "...pairs of points..." in the first sentence? $\endgroup$
    – Bill Barth
    Commented Dec 5, 2011 at 14:54

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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). $\endgroup$
    – TH.
    Commented Feb 10, 2012 at 15:12
  • $\begingroup$ The course then fine procedure can be generalized to multiple steps which is what Gandalf does. $\endgroup$
    – dmckee --- ex-moderator kitten
    Commented Feb 10, 2012 at 18:40
  • $\begingroup$ 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. $\endgroup$
    – dmckee --- ex-moderator kitten
    Commented Sep 7, 2013 at 13:50
5
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.