### Guillermo Sapiro of Duke university - Guy Tel-Zur

```Hough Transform
Omri Zorea and Alon Lipnik
Group #11
Introduction
 Technique to find imperfect instances of object within a certain class of shapes.

(i.e. lines, cycles, ellipses, parabolas etc.).
 Use in image analysis, computer vision and digital image processing.
 Was invented by Richard Duda and Peter Hart in 1972 (patent of Paul Hough, 1962).
1. Aerial photo
detecting
2. X-Y plane
transform
Hough Transform
3. Hough plane
Hough Transform
 Find lines in picture (y = -mx + b).
 Match dots on the picture to lines and match line to a dot.
 The slope (m) can goes to infinity (unbounded domain)  polar coordinates.
Hough Transform
 Detect arbitrary shapes in picture.
 Each point in Image space is now a sinusoid:
ρ = x cosθ + y sinθ
 For each edge point on image it compute his gradient and know
which shape is it.
Hough Transform
Hough Transform
 Detect arbitrary shapes in picture.
 Accumulator matrix - find lines with maximum points.
 determines Threshold values in matrix.
 the values are the points-density of shape.
Hough Transform
Parallel Algorithm
 The image is divided into rows with
the same number of columns.
 PVM is a programming tool used for
the message routing, data
 Complexity of O(m*n^2).
m – different theta values.
nxn – image size
(* Algorithm LARPBS – linear array
reconfigurable pipeline bus system)
Hough Transform
Parallel Algorithm
Speed Up:
 Check on 4, 8, 16 and 32 processors.
 Two different algorithms.
 Image density range 5% - 15%.
Hough Transform
Parallel Algorithm
Efficiency:
 Image density range from 5% to 25%.
 Check on 4, 8, 12, 16 and 32 processors (process 0 is
the master).
 Trade-Off (processors and image density).
Hough Transform
References
 Parallel algorithms for Hough Transform, Fevzi Oktay Ozbek :
http://preserve.lehigh.edu/cgi/viewcontent.cgi?article=1073&context=etd
 A fast efficient parallel HT algorithm on LARPBS: