Edge DetectionCS / ECE 181BSection 4.2.1Wednesday, January 20, 2010Edge DetectionCS / ECE 181B®Edge detection®Linear filtering®Laplacian of the Gaussian filterTodaySection 4.2.1Wednesday, January 20, 2010Edge Detection• Edge detection is a local area operator that seeks to find significant, meaningful changes in image intensity (color?) that correspond to – Boundaries of objects and patterns– Texture– Changes in object color or brightness– Highlights– Occlusions– Etc.Wednesday, January 20, 2010Useful Mathematics Funcs.RampStep ImpulseWednesday, January 20, 2010The bad newsWednesday, January 20, 2010The bad news• Unfortunately, it’s very hard to tell significant edges from bogus edges!– Noise is a big problem!Wednesday, January 20, 2010The bad news• Unfortunately, it’s very hard to tell significant edges from bogus edges!– Noise is a big problem!• An edge detector is basically a high-frequency filter, since sharp intensity changes are high-frequency eventsWednesday, January 20, 2010The bad news• Unfortunately, it’s very hard to tell significant edges from bogus edges!– Noise is a big problem!• An edge detector is basically a high-frequency filter, since sharp intensity changes are high-frequency events• But image noise is also high-frequency, so edge detectors tend to accentuate noise!• Some things to do:– Smooth before edge detection (hoping to get rid of noise but not edges!)– Look for edges at multiple scales (pyramids!)– Use an adaptive edge thresholdWednesday, January 20, 2010Caveats• In reality, low light levels and random noise lead to high fluctuations in individual pixel values, leading to bad estimations. Wednesday, January 20, 2010Edge detection historyWednesday, January 20, 2010Edge detection history• Edge detection has a long history and a huge literature– Edge modeling: Step edges, roof edges, impulse edges…– Biological modeling: How does human vision do it?– Elegant and complex mathematical models (e.g., Canny’s)– Simple and computationally cheap edge detectors (Robert, Sobel, Prewitt..)Wednesday, January 20, 2010Edge detection history• Edge detection has a long history and a huge literature– Edge modeling: Step edges, roof edges, impulse edges…– Biological modeling: How does human vision do it?– Elegant and complex mathematical models (e.g., Canny’s)– Simple and computationally cheap edge detectors (Robert, Sobel, Prewitt..)• Typical usage:– Detect “edge points” in the image (filter then threshold)♦Edges may have magnitude and orientation– Throw away “bad” ones (isolated points)– Link edge points together to make edge segments– Merge segments into lines, corners, junctions, etc.– Interpret these higher-level features in the context of the problemWednesday, January 20, 2010Edge detectionWednesday, January 20, 2010Edge detection• The bottom line:– It is a difficult problem, usually you do not get the edges you want– At least, not how we’d like it to:♦Too many false positives (noise)♦Too many omissions (little or no local signal)Wednesday, January 20, 2010Edge detection• The bottom line:– It is a difficult problem, usually you do not get the edges you want– At least, not how we’d like it to:♦Too many false positives (noise)♦Too many omissions (little or no local signal)• Still, edge detection is often the first step in a computer vision program– We have to learn to live with imperfectionWednesday, January 20, 2010Edge detectors• First order operators: Gradient-based edge detectors– Approximate a spatial derivative– X and Y directions, or at various orientations– Fundamentally high-pass (accentuates noise)Wednesday, January 20, 2010Edge detectors• First order operators: Gradient-based edge detectors– Approximate a spatial derivative– X and Y directions, or at various orientations– Fundamentally high-pass (accentuates noise)• Second order: Laplacian and other band-pass edge detectorsWednesday, January 20, 2010Edge detectors• First order operators: Gradient-based edge detectors– Approximate a spatial derivative– X and Y directions, or at various orientations– Fundamentally high-pass (accentuates noise)• Others: Roberts, Sobel, Prewitt, Canny….• Second order: Laplacian and other band-pass edge detectorsWednesday, January 20, 2010Digital Implementations• 1st order operator - 1x2 or 2x1 mask– simple– unbalanced (forward differencing)– sensitive to noiseWednesday, January 20, 2010Another Implementation• 1st order operator - 2x2 mask– simple– unbalanced (forward differencing)– more resistive to noiseWednesday, January 20, 2010Robert’s detector• Compute the X- and Y- derivatives using the above masks• Compute the magnitude of the gradient• Compute the gradient direction-11-11ExEyWednesday, January 20, 2010Observation in 2D• 2D 1st order edge operator– A magnitude– A direction, but ...♦Edge direction: iso-brightness direction♦Gradient direction: largest brightness change direction Wednesday, January 20, 2010Gradient vs. Iso-brightness dirsWednesday, January 20, 2010More Edge detectors• Sobel detector• Prewitt detector-101-202-101-1-2-1000121GxGy|G| = Gx2 + Gy2∠G = atan Gy/Gx-101-101-101-1-1-1000111GxGyWednesday, January 20, 2010LenaOriginalWednesday, January 20, 2010LenaVertical edgesOriginalWednesday, January 20, 2010LenaVertical edgesHorizontal edgesOriginalWednesday, January 20, 2010LenaVertical edgesHorizontal edgesOriginal Edge magnitudeWednesday, January 20, 2010Edge detectors: second order operators• Laplacian detectorsEdge detectors are not limited to 3x3 kernels-41 111Wednesday, January 20, 20102nd order operator (cont.)• Zero-crossing– if pixel > t and one of its neighbor < -t, or– if pixel<-t and one of its neighbor > tWednesday, January 20, 2010Smoothing Filter• Differentiation enhances noise (as well as edges).• Smooth the image before edge detection– Helps in minimizing false positives.– Edges at different scales.• Gaussian smoothing: Why?– G * G is also a Gaussian♦Efficient multi-scale convolutions– Central limit theorem—smooth many times == Gaussian smoothing with an appropriate sigma.– Gaussians are separable==good for implementation.Wednesday, January 20, 2010Multiple ScalesOriginalimageCombinedzerocrossingmapsGaussiansmoothingLaplacianZero crossingmapsWednesday, January 20, 2010Laplacian of the Gaussian (LOG)• Smooth with the