Edge DetectionCS / ECE 181BThursday, April 22, 2004 Edge detection Linear filtering Laplacian of the Gaussian filterEdge Detection• Edge detection is a local area operator that seeks to findsignificant, meaningful changes in image intensity (color?)that correspond to– Boundaries of objects and patterns– Texture– Changes in object color or brightness– Highlights– Occlusions– Etc.Useful Mathematics Funcs.Rxxxxx()=<=> 00000Uxxxx()=<=> 0012010()xxxx=<=> 001000RampStep ImpulsedxddxdxddxThe bad news• Unfortunately, it’s very hard to tell significant edges frombogus edges!– Noise is a big problem!• An edge detector is basically a high-frequency filter, sincesharp intensity changes are high-frequency events• But image noise is also high-frequency, so edge detectorstend to accentuate noise!• Some things to do:– Smooth before edge detection (hoping to get rid of noise but notedges!)– Look for edges at multiple scales (pyramids!)– Use an adaptive edge thresholdCaveats• In reality, low light levels and random noise lead to highfluctuations in individual pixel values, leading to badestimations.Edge 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– Simple and computationally cheap edge detectors– Etc., etc., etc…..• 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 problemEdge detection• The bottom line:– It doesn’t work!– At least, now 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 computervision program– We have to learn to live with imperfectionEdge detectors• Gradient-based edge detectors– Approximate a spatial derivative– X and Y directions, or at various orientations– Fundamentally high-pass (accentuates noise)• Roberts, Sobel, Prewitt, Canny….• Laplacian and other band-pass edge detectorsDigital Implementations• 1st order operator - 1x2 or 2x1 mask– simple– unbalanced (forward differencing)– sensitive to noiseEij,Eij+1,ExEEij ij +1, ,Eij,Eij, +1EyEEij ij +,,1Another Implementation•1st order operator - 2x2 mask– simple– unbalanced (forward differencing)– more resistive to noiseExEE EEij ij ij ij + ++ + +1211 1 1(( ) ( )),, ,,Eij,Eij+1,Eij++11,Eij, +1Eij,Eij+1,Eij++11,Eij, +1EyEE EEij ij ij ij + ++ + +1211 1 1(( ) ( )),,,,Robert’s detector• Compute the X- and Y- derivativesusing the above masks• Compute the magnitude of thegradient• Compute the gradient direction-11-11ExEyObservation in 2D• 2D 1st order edge operator– A magnitude– A direction, but ... Edge direction: iso-brightness direction Gradient direction: largest brightness change directionmagnitudeExEydirectionEyEx=+=()()tan ( )221(, )tan ( )ExEyo>=>=000001(,)tan ( ) ExEyoo>>>>= 00000901(,)tan ( )ExEyo=<<= 0000901Gradient vs. Iso-brightness dirsMore Edge detectors• Sobel detector• Prewitt detector10-120-210-1121000-1-2-1GxGy|G| = Gx2 + Gy2G = atan Gy/Gx10-110-110-1111000-1-1-1GxGyLenaVertical edgesHorizontal edgesOriginalEdge magnitudeEdge detectors: second order operators• Laplacian detectorsEdge detectors are not limited to 3x3 kernels22111112211222211 11224ExExExEE EEEEEEyEEELaplacianExEyEEEE Eij i ji j ij ij i jij ij ijij ij iji j i j ij ij ij  =  + ++ ++++ + + +  + ,,,, , ,,,,,,,,,,, ,()():Eij +11,Eij1,Eij11,Eij,Eij+1,Eij++11,Eij, +1Eij, 1Eij+ 11,-411112nd order operator (cont.)• Zero-crossing– if pixel > t and one of its neighbor < -t, or– if pixel<-t and one of its neighbor > tSmoothing 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 withan appropriate sigma.– Gaussians are separable==good for implementation.Multiple ScalesMultiple ScalesMultiple Scales12342222ZC1ZC2ZC3ZC4OriginalimageCombinedzerocrossingmapsGaussiansmoothingLaplacian Zero crossingmapsGexy=+1222222  =+22222xy = ++242222112222Gxyexy ()Laplacian of the Gaussian (LOG)• Smooth with the Gaussian + Laplacian + zero-crossingdetector==gives edges• Equivalent to convolving the image with the Laplacian ofthe Gaussian kernel.– Note: differentiation is linear and shift invariant.– Convolution is associative.• Can be well approximated by the Difference of theGaussians (DoG)• Marr-Hildreth operator.Multiple Scalesfine scalecoarse scaleOther popular edge detectors• Canny edge detector– Formulate the problem as an optimization problem– What is the criteria of good edge detection? Good detection– Low probability of misses– Low probability of false alarms Good localization– Closeness of marked edge points to true edge points Single response criteria–Not too many strong responses of a single edge in a smallneighborhood• Beyond the scope of this course…read the handout foradditional information.Canny edge detectorSummary• Convolution (correlation) defines a shift-invariant linear filter• The Fourier transform is a linear operation that exposes the spatialfrequency composition of an image• Sampling and aliasing are directly related to spatial frequency issues– E.g., image pyramids• Correlation can be viewed as template matching (or pattern matching)• If the template is a gradient/derivative operator, correlation implementsedge detection• Edge detection by itself doesn’t work very well, although it can beuseful if its limitations are understood– Noise, missing edges, complex scenes,