[Ch10] The Hough and Distance Transform

10.1 The Hough transform

Goal : To find lines in imgs

 

(1) Basic approach

Suppose a point (x, y) → Consider all pairs (a,b) which satisfy y = ax+b → Plot them into 'accummulator array'

• The dots in transform : places where there are maximum intersections of lines : at each dot three lines intersect
• The coordinates of dots : (a, b) = (1,0) and (1, -1)
• The lines : y = 1*x + 0 and y = 1*x + (-1)
• ⇔ The strongest lines in the img in that they contain the greatest # of points

(2) Another parameterization of lines to find vertical lines 

• r : perpendicular distance from the line to the origin
• θ : angle of the lines's perpendicular to the x-axis (ex. vertical lines : θ = 0)
• (p, q) = (rcosθ, rsinθ)
• the gradient of the line's perpendicular : tanθ
• the gradient of the line : -1/tanθ = -cosθ/sinθ = (y-q)/(x-p)

Choose a discrete set of values of θ → Compute r = xcosθ + ysinθ for each θ → Plot the result

• (r, θ) : the highest values in the array will correspond to strongest lines in the img

• The accumulator array : # of times each value of (r, θ) appears in the table 
• The largest values occur at (r, θ)  = (2, 0) and (3, 90)
• The lines : xcos0 + ysin0 = 2 (or x =2) and xcos90 + ysin90 = 3 (or y = 3)

 

10.2 Implementing the Hough transform in Matlab

 

10.3 The distance transform 

Goal : To find the distance of every pixel from a region R (computationally efficient) 

 

Standard Euclidean distance : (computationally inefficient if R is large)

 

Basic steps of the distance transform

 

Generalized the above tranfom by using "mask"

 

Two pass distance transform (faster)

 

 

Implementing the distance transform in Matlab

 

Application to skeletonization