In a particular class of detector 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 unacceptable 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

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

In a particular class of detector our data comes out as pairs on point 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 unacceptable slow.

I'm looking for a faster way.

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.

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

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.

In a particular class of detector 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 unacceptable 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