Report

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 conversion and task scheduling. 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: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.99.8684&rep=rep1&type=pdf Guillermo Sapiro of Duke university : https://www.youtube.com/watch?v=kMK8DjdGtZo