Data processing algorithm development for parallel architectures
Tuan Máté Nguyen (2016.09.01 - 2016.10.31)
Supervisor: Gergely Gábor Barnaföldi
Abstract: The Hough-transform is a frequent data analysis and pattern recognition task. It can be used to detect lines in noisy data or decide whether a set of points are on a single or multiple lines and if so, what are the parameters of such lines. The principle of the operation is that the incoming discretized values (bins or pixels) are mapped to lines, that in turn are drawn on an image, then select the points where the most lines intersect each other. The coordinates of these crossing points can be transformed into the slope and intersect values of the line passing through the points. If the input values have errors, we need to generalize the algorithm by drawing stripes instead of thin lines. The transformation is in itself computationally intensive, but if we’d like to process lots of data with it, it is necessary to use the most optimal and parallelized implementation possible. In this project we implemented and optimized the stripe generalized Hough-transform on CPUs, both serially and in parallel, compared different approaches and implementations, determined the scaling across multiple threads and assessed the reconstruction error.
The development was supported by the OTKA NK 106119 grant.