10-14 October 2016
San Francisco Marriott Marquis
America/Los_Angeles timezone

Parallel Monte Carlo search for Hough transform

12 Oct 2016, 12:30
GG A+B (San Francisco Mariott Marquis)


San Francisco Mariott Marquis

Oral Track 5: Software Development Track 5: Software Development


Peter Hobson (Brunel University (GB))


We investigate the combination of a Monte Carlo Tree Search, hierarchical space decomposition, Hough Transform techniques and
parallel computing to the problem of line detection and shape recognition in general.

Paul Hough introduced in 1962 a method for detecting lines in binary images. Extended in the 1970s to the detection of space forms, what
came to be known as the Hough Transform (HT) has been proposed, for example, in the context of track fitting in the LHC ATLAS [1]
and CMS [2]
projects. The HT transfers the problem of line detection, for example, into one of optimization of the peak in a vote counting process
for cells which contain the possible points of candidate lines. The detection algorithm can be computationally expensive both in the demands
made upon the processor and on
memory. Proposals to improve its CPU performance have included the use of Monte Carlo algorithms and parallel computing.
However, the detection algorithm can be expensive both in
CPU and memory demands. Variations of the HT found in literature have a complexity that is least at cubic in the number of points.
In addition, background noise can reduce the HT effectiveness, and statistical techniques or the use of the Radon transform
instead have been proposed.

We present results for the practical evaluation of variations of the Hough Transform for line detection and discuss
implementations on multi-GPU and multicore architectures.


[1] N. Amram, Hough Transform Track Reconstruction in the Cathode Strip Chambers in ATLAS, PhD Thesis, Tel Aviv University, 2008 CERN-THESIS-2008-062

[2] D. Cieri et al, L1 track finding for a time multiplexed trigger, Nucl. Instrum & Meth A (2015) doi:10.1016/j.nima.2015.09.117

Secondary Keyword (Optional) Reconstruction
Primary Keyword (Mandatory) Algorithms

Primary author

Raul Cardoso Lopes (Brunel University (GB))


Dr Ivan Reid (Brunel University London (GB)) Peter Hobson (Brunel University (GB)) Dr Virginia Franqueira (University of Derby, UK)

Presentation Materials