1CSE152, Spr 06 Intro Computer VisionEdge Detection, Lines, Hough TransformIntroduction to Computer VisionCSE 152Lecture 10CSE152, Spr 06 Intro Computer VisionAnnouncements• Assignment 2 on tracking due Tuesday, May 9.• Midterm: Thursday, May 11.• Manmohan will be out of town next week. No office hour on Monday• Special office hour today, 7:00 - 9:00 PM in EBU-3B 4109 CSE152, Spr 06 Intro Computer VisionLast LectureCSE152, Spr 06 Intro Computer VisionMedian filters : examplefilters have width 5 : CSE152, Spr 06 Intro Computer VisionEdgesCSE152, Spr 06 Intro Computer VisionEdge is Where Change Occurs: 1-D• Change is measured by derivative in 1DSmoothed EdgeFirst DerivativeSecond DerivativeIdeal Edge• Biggest change, derivative has maximum magnitude• Or 2nd derivative is zero.2CSE152, Spr 06 Intro Computer VisionNumerical Derivativesf(x)xX0X0+hX0-hTake Taylor series expansion of f(x) about x0f(x) = f(x0)+f’(x0)(x-x0) + ½ f’’(x0)(x-x0)2 + …Consider Samples taken at increments of h and first two terms, we havef(x0+h) = f(x0)+f’(x0)h+ ½ f’’(x0)h2f(x0-h) = f(x0)-f’(x0)h+ ½ f’’(x0)h2Subtracting and adding f(x0+h) and f(x0-h) respectively yields20002)()(2)()(''2)()()('0000hhxfxfhxfxfhhxfhxfxf−−++−=−−+=CSE152, Spr 06 Intro Computer Vision2D Edge Detection: Canny1. Filter out noise– Use a 2D Gaussian Filter.2. Take a derivative– Compute the magnitude of the gradient:22Gradient theis ,),(yxyxJJJyJxJJJJ+=∇⎟⎟⎠⎞⎜⎜⎝⎛∂∂∂∂==∇GIJ *=CSE152, Spr 06 Intro Computer VisionThe scale of the smoothing filter affects derivative estimates1 pixel3 pixels7 pixelsCSE152, Spr 06 Intro Computer VisionWe wish to mark points along the curve where the magnitude is biggest.We can do this by looking for a maximum along a slice normal to the curve(non-maximum suppression). These points should form a curve. There arethen two algorithmic issues: at which point is the maximum, and where is thenext one?Magnitude ofGradientCSE152, Spr 06 Intro Computer VisionNon-maximum suppressionFor every pixel in the image (e.g., q) we have an estimate of edge direction and edge normal (shown at q)CSE152, Spr 06 Intro Computer VisionNon-maximum suppressionUsing normal at q, find two points p and r on adjacent rows (or columns).We have a maximum if the value is larger than those at both p and at r. Interpolate to get values.3CSE152, Spr 06 Intro Computer VisionAssume the marked point is an edge point. Then we construct the tangent to the edge curve (which is normal to the gradient at that point) and use this to predict the next points (here either r or s). Non-maximum suppressionPredicting the next edge pointCSE152, Spr 06 Intro Computer VisionLinking using Hysteresis Tresholding• Track edge points by starting at point where gradient magnitude > τhigh.• Follow edge in direction orthogonal to gradient.• Stop when gradient magnitude < τlow.• i.e., use a high threshold to start edge curves and a low threshold to continue them.τhighτlow|∇I|CSE152, Spr 06 Intro Computer VisionInput imageCSE152, Spr 06 Intro Computer VisionT=15T=5HysteresisTh=15 Tl= 5HysteresisthresholdingSingleThresholdCSE152, Spr 06 Intro Computer Vision CSE152, Spr 06 Intro Computer Visionfine scalehigh threshold4CSE152, Spr 06 Intro Computer Visioncoarse scale,High thresholdCSE152, Spr 06 Intro Computer VisioncoarsescaleLow highthresholdCSE152, Spr 06 Intro Computer VisionWhy is Canny so DominantStill widely used after 20 years.1. Theory is nice (but end result same,).2. Details good (magnitude of gradient, non-max suppression).3. Hysteresis an important heuristic.4. Code was distributed.CSE152, Spr 06 Intro Computer Vision• Segment linked edge chains into curve features (e.g., line segments).• Group unlinked or unrelated edges into lines (or curves in general).• Accurately fitting parametric curves (e.g., lines) to grouped edge points.What to do with edges?CSE152, Spr 06 Intro Computer VisionHough Transform[ Patented 1962 ]Finding lines in an imageOption 1:• Search for the line at every possible position/orientation• What is the cost of this operation?Option 2:• Use a voting scheme: Hough transform5Finding lines in an imageConnection between image (x,y) and Hough (m,b) spaces• A line in the image corresponds to a point in Hough space• To go from image space to Hough space:– given a set of points (x,y), find all (m,b) such that y = mx + bxymbm0b0image space Hough spaceFinding lines in an imageConnection between image (x,y) and Hough (m,b) spaces• A line in the image corresponds to a point in Hough space• To go from image space to Hough space:– given a set of points (x,y), find all (m,b) such that y = mx + b• What does a point (x0, y0) in the image space map to?xymbimage space Hough space– A: the solutions of b = -x0m + y0– this is a line in Hough spacex0y0Hough transform algorithmTypically use a different parameterization• d is the perpendicular distance from the line to the origin• θ is the angle this perpendicular makes with the x axis•Why?Hough transform algorithmTypically use a different parameterization• d is the perpendicular distance from the line to the origin• θ is the angle this perpendicular makes with the x axis•Why?Basic Hough transform algorithm1. Initialize H[d, θ]=0 ; H is called accumulator array2. for each edge point I[x,y] in the imagefor θ = 0 to 180 H[d, θ] += 13. Find the value(s) of (d, θ) where H[d, θ] is maximum4. The detected line in the image is given byWhat’s the running time (measured in # votes)? ExtensionsExtension 1: Use the image gradient1. same2. for each edge point I[x,y] in the imagecompute unique (d, θ) based on image gradient at (x,y)H[d, θ] += 13. same4. sameWhat’s the running time measured in votes?Extension 2• give more votes for stronger edgesExtension 3• change the sampling of (d, θ) to give more/less resolutionExtension 4• The same procedure can be used with circles, squares, or any other shapeExtensionsExtension 1: Use the image gradient1. same2. for each edge point I[x,y] in the imagecompute unique (d, θ) based on image gradient at (x,y)H[d, θ] += 13. same4. sameWhat’s the running time measured in votes?Extension 2• give more votes for stronger edgesExtension 3• change the sampling of (d, θ) to give more/less resolutionExtension 4• The same procedure can be used with circles, squares, or any other shape6CSE152, Spr 06 Intro Computer VisionHough