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: