# Hough Transform Using Hpc

Essay by siddhant9892 • September 25, 2016 • Research Paper • 7,090 Words (29 Pages) • 1,041 Views

**Page 1 of 29**

GPU accelerated hough transformation for HLT application

Siddhant Mohanty1,2 and Peter Hristov1

- 1 CERN, CH-1211, Geneve 23, Switzerland
- 2 Department of Computer Science, VNIT, Nagpur, India 440010

E-mail: siddhant9892@gmail.com,Peter.Hristov@cern.ch

ABSTRACT.

Hough transform has been carried out using graphic processor both for circular and linear trajectories, the latter being obtained through conformal mapping. As expected in CPU, the circular track model takes longer time as compared to the linear hough transform. However, both the methods takes nearly same time on GPU and about 60 times faster than the corresponding CPU implementation.

1. Introduction

ALICE (A Large Hadron Collider Experiment) is a general purpose detector, being used at CERN, LHC to study nucleus-nucleus and proton-proton collisions at diﬀerent centre of mass energies [1]. The task of the ALICE High level trigger (HLT) is to select the events of interest using various fast track reconstruction algorithms. A fast track-reconstruction algorithm for the Time Projection Chamber of ALICE detector (see appendix A for a detail description of ALICE TPC) has been discussed in Ref. [2] based on linear Hough Transform (HT). In this work, we try to implement similar HT using graphic processor unit (GPU). We consider both circular and linear HT (for detail on HT, see appendix B).

The circle equation with center at a and b and radius r passing through the origin

(x − a)2 + (y − b)2 = r2 | (1) | |||

can be written in the parametric form given by, | ||||

2 | ||||

k = | sin(φ − φ0) | (2) | ||

R |

p

where k = 1/r is the radius of curvature, R = x2 + y2, φ0 is the azimuthal angle at (0, 0) and

φ = tan−1 | y | . | (3) | |

x |

The above circle equation (Eq.1) can be transformed into a straight line through conformal mapping with the prescription,

u = | x | , | v = | y | (4) | |

x2 + y2 | x2 + y2 |

If r is fixed by the relation | ||||||

r2 = a2 + b2 | (5) | |||||

the following straight line is obtained, | ||||||

1 | a | |||||

v = | − | u. | (6) | |||

2b | b |

Both Eq.6 and Eq.2 can be used for hough transformation.

Cicular Trajectory | |||||||||||||||||||||||

250 | Conformal Mapping | ||||||||||||||||||||||

200 | |||||||||||||||||||||||

150 | 0.01 | ||||||||||||||||||||||

100 | |||||||||||||||||||||||

50 | |||||||||||||||||||||||

(cm)0 | 0.005 | ||||||||||||||||||||||

y | |||||||||||||||||||||||

-50 | v | 0 | |||||||||||||||||||||

-100 | |||||||||||||||||||||||

-150 | -0.005 | ||||||||||||||||||||||

-200 | |||||||||||||||||||||||

-250 | -0.01 | ||||||||||||||||||||||

-200 | -100 | 0 | 100 | 200 | |||||||||||||||||||

x (cm) | |||||||||||||||||||||||

-0.01 -0.005 | 0 | 0.0050.01 | |||||||||||||||||||||

u |

Figure 1. The x-y coordinates for 100 circular tracks.The clock-wise curved tracks are for pos-itive charged particles and anti-clockwise curved tracks are for neg-ative particles.

Figure 2. The corresponding confromally mapped linear tracks in u-v plane.

In the following, we have simulated curve trajectories in the x-y plane to mimic the transverse trajectories in a Time Projection Chamber(TPC) of ALICE detector. The inner radius R is fixed at 84.5cm and the outer radius is fixed at 246.6cm. The initial azimuthal angle φ0 is randomly chosen from 0 ≤ φ0 ≤ 2π, and the transverse momentum is chosen randomly between 0.5 ≤ |pT | ≤ 1GeV. The curvature k is determined from the relation,

...

...