Introduction Line detection I circle detection I irregular shape detection c to Example 1 m(set a range) found 18 y=mx+C,(original) 8 m 6}o.53OO 1/×)c+y/ 10 26 points Procedures 14 1)m=G*C+D, where G=-1/×1D=y/ 2)plot lines in(m, c) space G=(1/×)、D=/xi) For(x1,y1)=( m C ound =0,→C(=8 found 10,→c( found): blue line Repeat )=(2,6)and 3 Cutting point of the 3 lines Each point(xi, yi) C)=(-2,10) ives a line Cutting point So the line is y=-2X+10(done!) space is the solution )=(-2,10) ougn transom w. y=-2×+1 11
Introduction | Line detection | circle detection | irregular shape detection Hough transform v0.b 11 x y G D m(set a range) c to be found 1 8 -1 8 -10 18 0 8 10 -2 2 6 -0.50 3.00 -10 26 0 6 10 -14 3 4 -0.3 1.3 -10 34 0 4 10 -26 -15 -10 -5 0 5 10 15 -40 -20 0 20 40 Series1 Series2 Series3 Cutting point of the 3 lines: (m,c)=(-2,10) So the line is y=-2x+10 (done!) Example 1 y=mx+c , (original) m=(y-c)/x m=(-1/x)c+y/x Procedures 1) m=G*c+D, where G=-1/x, D=y/x 2) plot lines in (m,c) space G=(-1/xi), D= (yi/xi) For (x1,y1)=(1,8), m=-2, → c (=10 found) m=0, → c (=8 found) m=10, → c (=-2 found):blue line Repeat for (xi,yi)=(2,6) and (3,4). Each point (xi,yi) gives a line Cutting point in (m,c) space is the solution. (m,c)=(-2,10) y=-2x+10 (x,y) points c m
Introduction Line detection I circle detection I irregular shape detection Exercise 2, Excel example Their corresponding points Given 3 points find the line formula lines in(m, c) space X=1,y=9 Give values of m X=3,y=15 X=5,y=21 find values in c, plot line y=mx+c, original) G d m( c to be found m=(y-c)/ =(-1/x)c+y/x Procedures 1)m=G*C+D, where G=-1/x, D=y/X 2)plot lines in(m, c)space For(x1,y1)=(1,9) m=10.→c? m=10,→c? Cutting point in(m, c)space is the solution Hough transform vO. b 12
Introduction | Line detection | circle detection | irregular shape detection Exercise 2, Excel example • Given 3 points find the line formula – X=1, y=9 – X=3, y=15 – X=5, y=21 • y=mx+c , (original) • m=(y-c)/x • m=(-1/x)c+y/x • Procedures • 1) m=G*c+D, where G=-1/x, D=y/x • 2) plot lines in (m,c) space – m=(-1/xi)*c+(yi/xi) – For (x1,y1)=(1,9), • m=-10, → c ?____ • m=0, → c ?____ • m=10, → c ?____ – Repeat for (xi,yi)=(3,15) and (5,21). – Each point (xi,yi) gives a line • Cutting point in (m,c) space is the solution. x y G D m(set a range) c to be found 1 9 3 15 5 21 Hough transform v0.b 12 points Their corresponding lines in (m,c) space: Give 3 values of m find values in c, plot line
Introduction (Line detectioN circle detection I irregular shape detection Reason to use polar coordinates Why the previous method (x, y space to(m, c) space is still not ideal? Because Different formulations for different types(line, circle, ellipse etc): For straight lines(m, c) space is ok but not extendable, so use polar coordinates (r e)space for lines, circle or ellipse Hough transform is very suitable for computer implementation Hough transform vo.b 13
Introduction | Line detection | circle detection | irregular shape detection Reason to use polar coordinates • Why the previous method (x,y) space to (m,c) space is still not ideal? Because: – Different formulations for different types (line, circle, ellipse etc): For straight lines (m,c) space is ok but not extendable, so use polar coordinates (r, ) space for lines, circle or ellipse. • Hough transform is very suitable for computer implementation. Hough transform v0.b 13
Introduction (Line detectioN circle detection I irregular shape detection How to apply hough transform to line detection using polar coordinates r 0) space It is easily extendable to circle and ellipse a line can be represented in this way ☆= Edge point coS(8 x sin(o)(sin(0) 6=angle ☆ ☆ Hough transform vo.b 14
Introduction | Line detection | circle detection | irregular shape detection How to apply Hough transform to line detection using polar coordinates (r, ) space. It is easily extendable to circle and ellipse • A line can be represented in this way. . sin( ) sin( ) cos( ) r dist angle r y x = = + = − Hough transform v0.b 14 =Edge point y x r
Introduction (Line detectioN circle detection I irregular shape detection Representation y=mx tc changes coS(6 coS(8 from x, y to(, a) hence yi sin(6 sin(6 Sn(6) sin(6 space sor=sin(O)y+cos(O)x A test line can be represented by r Dist=the perpendicular line from origin to the test line 0(Angle)=between the perpendicular Note line and the horizontal axis ☆= Edge point PerpendiculaR 太 Line of the test line Test line 0 Hough transform vO. b 15
Introduction | Line detection | circle detection | irregular shape detection Representation changes from (x,y) to (r, ) space • A test line can be represented by – r (Dist)= the perpendicular line from origin to the test line – (Angle)= between the perpendicular line and the horizontal axis i i i i r y x r y x r m c y m x c so sin( ) cos( ) , sin( ) sin( ) cos( ) ,hence sin( ) , sin( ) cos( ) = + + = − = = − = + Hough transform v0.b 15 Test line Perpendicular Line of the test line Note: =Edge point y x r