Image processing and computer vision Chapter 5: Hough transform Hough transform vo.b
Image processing and computer vision Chapter 5: Hough transform Hough transform v0.b 1
<Introduction Line detection I circle detection I irregular shape detection Overview What is the problem? a method to fit a line for a set of features Why traditional methods are poor? Need a different formulation for different line types(i.e. line, curve cIrcle How to do it? We will discuss the basic algorithm for lines circles ellipse We will extend it to any line types Using the Generalized Hough transform e http:/en.wikipedia.org/wiki/houghtransform Lecture notes by Instructor S Narasimhan Hough transform vo.b
Introduction | Line detection | circle detection | irregular shape detection Overview • What is the problem? – A method to fit a line for a set of features. • Why traditional methods are poor? – Need a different formulation for different line types (i.e., line, curve, circle…) • How to do it? – We will discuss the basic algorithm for lines, circles, ellipse. • We will extend it to any line types. – Using the Generalized Hough transform • Ref – http://en.wikipedia.org/wiki/Hough_transform – Lecture notes by Instructor: S. Narasimhan Hough transform v0.b 2
<Introduction Line detection I circle detection I irregular shape detection The problem Fit a curve, line, circle or ellipse to a set of edge points Traditⅰona| method (x2y) y=mx+c Energy minimization by Calculus. Features are found by edge detection ★☆ Fit a curve a circle an ellipse nx.-C or a line which has minimum y distances from the edges Hough transform vo.b
Introduction | Line detection | circle detection | irregular shape detection The problem • Fit a curve , line, circle or ellipse to a set of edge points. • Traditional method – Energy minimization by Calculus. Features are found by edge detection • Fit a curve, a circle, an ellipse or a line which has minimum distances from the edges. Hough transform v0.b 3 y = mx+c y mx c i − i − ( , ) i i x y y x
<Introduction Line detection I circle detection I irregular shape detection Least squares energy minimization (seehttp://mathworld.wolframcom/leastsquarEsfittinghtml) Given: Many(i,yi)pairs (x2y) y=mx+c Find: Parameters(m, c) ☆ Minimize: Average square distance: ★☆ (y2-mx-c)2 y nx.-c E N Using aE aE 0 y=mx am C ∑(x1-x)y-y) Note ∑y∑ ∑(x-x N Hough transfor
Introduction | Line detection | circle detection | irregular shape detection Least Squares energy minimization (see http://mathworld.wolfram.com/LeastSquaresFitting.html) Hough transform v0.b 4 y = mx+c y mx c i − i − ( , ) i i x y y x Given: Many pairs Find: Parameters Minimize: Average square distance: Using: Note: ( , ) i i x y (m,c) − − = i i i N y mx c E 2 ( ) 0 & = 0 = c E m E c = y − m x − − − = i i i i i x x x x y y m 2 ( ) ( )( ) N y y i i = N x x i i =
<Introduction Line detection I circle detection I irregular shape detection Curve Fitting Find polynomial: y=f(x)=ax+bx+cx+d that best fits the given points(,y) ☆ ★ Minimize 1S[-(ax3+bx2+cx1+)/2 N Using OE aE aE aE 0 0 0 a ab ad Note: f()is LINEAR in the parameters(a, b, C,d) Hough transform vo.b
Introduction | Line detection | circle detection | irregular shape detection Curve Fitting Hough transform v0.b 5 y x Find Polynomial: that best fits the given points Minimize: Using: Note: is LINEAR in the parameters (a, b, c, d) ( , ) i i x y y = f x = ax + bx + cx + d 3 2 ( ) − + + + i yi axi bxi cxi d N 3 2 2 [ ( )] 1 0 , 0 , 0 , = 0 = = = d E c E b E a E f (x)
Introduction (Line detectioN circle detection I irregular shape detection Line detection using Hough transform For straight line detection (a very efficient method) Hough transform vo.b 6
Introduction | Line detection | circle detection | irregular shape detection Line detection using Hough transform For straight line detection (a very efficient method) Hough transform v0.b 6
Introduction (Line detectioN circle detection I irregular shape detection Reason to use Hough transform Why the previous energy minimization method is too complicated? Because Different formulations for different types(line, circle, ellipse etc. Hough is the same method for all types Hough transform is more suitable for computers Hough transform vo.b
Introduction | Line detection | circle detection | irregular shape detection Reason to use Hough transform • Why the previous energy minimization method is too complicated? Because: – Different formulations for different types (line, circle, ellipse etc.) – Hough is the same method for all types. – Hough transform is more suitable for computers. Hough transform v0.b 7
Introduction (Line detectioN circle detection I irregular shape detection Example To find the line y=mx+c) y=2X+10 m=-2,C=10 Assume you don t know the line formula But have three points passing through the line X=1,y=8 (1,8) X=2,y=6 Line 34) y=mx+C X=3y=4 Hough transform vo.b 8
Introduction | Line detection | circle detection | irregular shape detection Example • To find the line (y=mx+c) – y=-2x+10 – m=-2, c=10 • Assume you don’t know the line formula – But have three points passing through the line – X=1, y=8 – X=2, y=6 – X=3,y=4 Hough transform v0.b 8 x y (1,8) (2,6) (3,4) Line y=mx+c
Introduction (Line detectioN circle detection I irregular shape detection Change of variables (x, y)>(m, c) y=mx+C m=(y-c)/ m=(-1/x)c+y/x m=G*C+D, where G=-1/, D=y/ Procedure: find(m, c from points xi, yi) 1 Find the line for(m, c)as variables(not x, y as variables 2)For each point xi, yi), plot line in(m, c) space Give a range of m values(e g-10,0, 10. etc, at least 2 values Find c value for each m value plot line 3)The cutting point of lines in m-c space is the solution for(m, c) Hough transform vo.b
Introduction | Line detection | circle detection | irregular shape detection Change of variables (x,y)→(m,c) • y=mx+c • m=(y-c)/x • m=(-1/x)c+y/x • m=G*c+D, where G=-1/x, D=y/x • Procedure: find (m,c) from points (xi,yi) – 1)Find the line for (m,c) as variables (not x,y as variables) – 2)For each point (xi,yi), plot line in (m,c) space • Give a range of m values (e.g -10,0,10. etc, at least 2 values) • Find c value for each m value, plot line – 3) The cutting point of lines in m-c space is the solution for (m,c) Hough transform v0.b 9
Introduction Line detection I circle detection I irregular shape detection Exercise 1: Derivation exercise Exercise 1: y=px+g, where p is the gradient of the line, q is the vertical-axis cutting point Rearrange the equation in p, g space. Le p=(U)q+(v). Find U, V in terms of x, y Answer: Hough transform vo.b
Introduction | Line detection | circle detection | irregular shape detection Hough transform v0.b 10 Exercise 1 :Derivation exercise • Exercise 1:y=px+q, where p is the gradient of the line, q is the vertical-axis cutting point. Rearrange the equation in p,q space. I.e. p=(U)q+(V). Find U,V in terms of x,y • Answer: