11Edge Detectionl Why Detect Edges?u Information reductionl Replace image by a cartoon in which objects and surface markings are outlined ⇒ create line drawing descriptionl These are the most informative parts of the imageu Biological plausibilityl Initial stages of mammalian vision systems involve detection of edges and local featuresu Applicationsl Object recognition, stereo, texture analysis, motion analysis, image enhancement, image compression2What Causes Image Intensity Changes?l Many types of physical events cause intensity changesu Surface reflectance discontinuity - change in the fraction of light incident on the surface that is reflected to vieweru Illumination discontinuity - shadowu Surface orientation (normal) discontinuityu Depth discontinuity - at occluding contour, where surface orientation is perpendicular to line of sight3What type of real-world edge is this contrast border?4Need global information too25What Does an Edge Look Like?l Stepl Rampl Roofl Line (bar)67fine scalehigh threshold8coarse scale,high threshold39coarsescalelowthreshold10Edge Detectors in the HVSl Sum activity from an array of oriented simple cellsComplexSimple (border)11Orientation Columns in V1l A “hypercolum” = complete set of orientations12Craik-O’Brien-Cornsweet Illusion413Koffka Ring14Luminance Differences Affect our Perceptionsl Artists use the technique of “equiluminance” to blur outlines and suggest motion. We cannot perceive the edges of objects where object and background have the same luminance. If parts of a painting are equiluminant, their positions become ambiguous. They may seem to shift position or to floatl Equiluminant colors have special properties, e.g., they can make a painting appear unstable 15Equiluminant Colorsl An object that can be seen by both subdivisions of the visual system will be perceived accurately. But if the two subdivisions are not balanced in their response to an object, itmay look peculiar.l For example, an object defined by equiluminant colors can be seen by the What system but is invisible (or poorly seen) by the Where system. It may seem flat, it may seem to shift position, or it may seem to float ambiguously because there is too little luminance contrast to provide adequate information about its three-dimensional shape, its location in space, or its motion (or lack of it).l Conversely, something defined by very low contrast contours is seen by the Where system but not the What system and may seem to have depth and spatial organization but no clear shape. 16Detail from Richard Anuszkiewicz’s Plus Reversed, 1960The red and blue seem to move around because they are equiluminant517Edge Detection Goalsl Good detection: Low false alarm rate and low false dismissal rate ⇒ maximize signal-to-noise (S/N) ratiol Good localization: Mark point closest to “center” of true edge ⇒ minimize distance between marked point and centerl Uniqueness: Only one response to a single edgel Good property measurement: Orientation, contrast, etc.18Edge Operator Propertiesl Shift invariant (translation invariant, position invariant)u If g(x,y) = Op[f(x,y)] then g(x-a, y-b) = Op[f(x-a, y-b)]l Isotropic (rotation invariant) vs. non-isotropicl Derivative order (if differentiation-based method)l Linear vs. non-linearu Op[a f1(x,y) + b f2(x,y)] = a Op[f1(x,y)] + b Op[f2(x,y)]= a g1(x,y) + b g2(x,y)l Scale (operator neighborhood size)u g(x,y) = Op[f(x+a, y+b), ∀ -k < a, b < k ]l Convolution (linear and shift-invariant)19Edge and Local Feature Detection Methodsl Gradient-based edge detectionl Edge detection by function fittingl Second derivative edge detectorsl Edge linking and the construction of the chain graph201D Edge Detectionl An ideal edge is a step functionxI(x)xI′(x)6211D Edge Detectionl The first derivative of I(x) has a peak at the edgel The second derivative of I(x) has a zero crossing at the edgexI′′(x)221D Edge Detectionl More realistically, image edges are blurred and the regions that meet at those edges have noise or variations in intensityu Blur - high first derivatives near edgesu Noise - high first derivatives within regions that meet at edgesxI(x)xI′(x)23Edge Detection in 2Dl Let I(x,y) be the image intensity function. It has derivatives in all directionsu ∂I(x, y)/∂x = lim I(x+∆x, y) - I(x, y) / ∆x ≈ I(u+1, v) - I(u,v)u Gradient of I(x, y) is a vector ∇∇∇∇I(x, y) = [∂I/∂x, ∂I/∂y]Tspecifying the direction of greatest rate of change in intensity (i.e., perpendicular to the edge’s direction)u From gradient can determine the direction in which the first derivative is highest, and the magnitude of the first derivative in that directionu Magnitude = [(∂ I/∂x)2 + (∂I/∂y)2]1/2u Direction = tan-1 (∂I/∂y)/(∂I/∂x)24Computing First Derivativel To compute first derivative in direction θ, calculate from linear combination of derivatives from any twonon-collinear directions x = x′cos θ - y′sin θy = x′sin θ + y′cos θ ∂I/∂x′ = ∂I/∂x ∂x/∂x′ + ∂I/∂y ∂y/∂y′= ∂I/∂x cos θ + ∂I/∂y sin θ∂I/∂y′ = -∂I/∂x sin θ + ∂I/∂y cos θ (∂I/∂x′)2+ (∂I/∂y′)2= (∂I/∂x)2+ (∂I/∂y)2 So, sum of squares of first derivative is isotropic, non-linear Similarly, all derivatives of odd ordcrraised to an even power are isotropicyxx′y′θ725Gradientl Gradient = [∂I/∂x, ∂I/∂y]Tl What direction is first derivative a maximum?u Set ∂/∂θ (∂I/∂x′) = 0, and solve for θ⇒ ∂/∂θ (∂I/∂x cos θ + ∂I/∂y sin θ) = 0⇒ θ = tan-1(∂I/∂y / ∂I/∂x)l Gradient direction is perpendicular to “edge direction”l Gradient magnitude is isotropic22∂∂+∂∂=∇yIxII26Edge Detection in 2Dl With a digital image, the partial derivatives are replaced by finite differences:u ∆xI = I(u+1, v) - I(u, v)u ∆yI = I(u, v) - I(u, v+1)l An alternative (Sobel)u ∆sobel_XI = I(u+1, v+1) + 2I(u+1, v) + I(u+1, v-1) - I(u-1, v+1) - 2I(u-1, v) - I(u-1, v-1)u ∆sobel_YI = I(u-1, v-1) + 2I(u, v-1) + I(u+1, v-1) - I(u-1, v+1) - 2I(u, v+1) - I(u+1, v+1)l Roberts’s “Cross”u ∆+I = I(u, v) - I(u+1, v-1)u ∆-I = I(u, v-1) - I(u+1, v)1 00 -10 -11 0uv27Gradient Operator Examplel I = 0 0 0 1 2 3 4 4 4 8 8 8 3 3 3l ∆x= -1 1l ∆xI = * 0 0 1 1 1 1 0 0 4 0 0 -5 0 0830Directional Edge Operatorsl Kirsch 8-direction masksl Gradient