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)