Gradients and edgesThe Gradient and EdgesEdge CausesEdge DetectionStep edge detection: First Derivative OperatorsSobel Edge Filtering ExampleStep 1Step 2Step 3Step 4Sobel Edge Filtering Example: ResultSobel Edge Detection: Gradient ApproximationSobelDerivative of GaussianSmoothing and DifferentiationThe Laplacian of GaussianMarr-Hildreth operatorStep edge detection: 2nd-Derivative OperatorsLaplacian of GaussianSobel vs. LoG Edge Detection: Matlab Automatic ThresholdsSlide 21Slide 22Slide 23Slide 24Remaining issuesSlide 26Slide 27Slide 28Slide 29Canny Edge DetectionEdge “Smearing”Non-Maximum Suppression: StepsExample: Non-Maximum SuppressionEdge “Streaking”Edge HysteresisExample: Canny Edge DetectionExample: Canny Edge DetectionImage PyramidsGaussian PyramidReconstructionLaplacian PyramidsLaplacian PyramidSpliningSplining (Blending)Example images from GTechOutlineMatching with Invariant FeaturesExample: Build a PanoramaHow do we build panorama?Matching with FeaturesSlide 51Slide 52Slide 53Slide 54More motivation…Corner DetectionCorner Detection: Analyzing Gradient CovarianceContentsHarris Detector: MathematicsSlide 60Slide 61Slide 62Slide 63Slide 64Harris DetectorComputer Vision : CISC 4/689Gradients and edges•Points of sharp change in an image are interesting:–change in reflectance–change in object–change in illumination–noise•Sometimes called edge points•General strategy–determine image gradient–now mark points where gradient magnitude is particularly large wrt neighbours (ideally, curves of such points).Computer Vision : CISC 4/689The Gradient and Edges•Consider image intensities as a 2-D height function I(x, y). Then the image gradient is the vector field defined by: •Definition of an edge–Line segment separating regions of contrasting intensity–Location: Where gradient magnitude is high –Direction: Orthogonal to the gradientComputer Vision : CISC 4/689Edge Causes•Depth discontinuity•Surface orientation discontinuity•Reflectance discontinuity (i.e., change in surface material properties)•Illumination discontinuity (e.g., shadow)Computer Vision : CISC 4/689Edge Detection•An edge point can be regarded as a point in an image where a discontinuity (in gradient) occurs across some line. A discontinuity may be classified as one of five types •Searching for Edges:–Filter: Smooth image–Enhance: Apply numerical derivative approximation–Detect: Threshold to find strong edges–Localize/analyze: Reject spurious edges, include weak but justified edgesGradient Discontinuity -- where the gradient of the pixel values changes across a line. This type of discontinuity can be classed as roof edges ramp edges convex edges concave edges by noting the sign of the component of the gradient perpendicular to the edge on either side of the edge. Ramp edges have the same signs in the gradient components on either side of the discontinuity, while roof edges have opposite signs in the gradient components. A Jump or Step Discontinuity -- where pixel values themselves change suddenly across some line. A Bar Discontinuity -- where pixel values rapidly increase then decrease again (or vice versa) across some line.Source: http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/MARSHALL/node28.htmlComputer Vision : CISC 4/689Step edge detection: First Derivative Operators•Method: Differentiate and find extrema•Examples–Sobel operator (Matlab: edge(I, ‘sobel’))–Prewitt, Roberts cross–Derivative of Gaussian-1-2-1000121-101-202-101Sobel x Sobel yBook uses thisformatComputer Vision : CISC 4/689Sobel Edge Filtering Example1 0 -12 0 -21 0 -10 0 2 20 0 2 20 0 2 20 0 2 2Rotate10-120-210-1Computer Vision : CISC 4/689Step 10012212222202022 0000022222020202000-100-210-110-120-210-1Computer Vision : CISC 4/689Step 20012223222202022 60000022222020202020040010-110-120-210-1Computer Vision : CISC 4/689Step 30012223230202030 6 60000022222020202020040010-110-120-210-1Computer Vision : CISC 4/689Step 40000223230202030 6 6 -60000022222020202010-220-410-110-120-210-1edgeeffectfrom zero-paddingComputer Vision : CISC 4/689Sobel Edge Filtering Example: Result68866886-80-60-80-60(pad with zeroes again, the boundary)and then we threshold…Computer Vision : CISC 4/689Sobel Edge Detection: Gradient ApproximationHorizontal diff. Vertical diff.-1-2-1000121-101-202-101Note anisotropy of edge findingComputer Vision : CISC 4/689Sobel•These can then be combined together to find the absolute magnitude of the gradient at each point and the orientation of that gradient. The gradient magnitude is given by: •an approximate magnitude is computed using: which is much faster to compute. •The angle of orientation of the edge (relative to the pixel grid) giving rise to the spatial gradient is given by: In this case, orientation 0 is taken to mean that the direction of maximum contrast from black to white runs from left to right on the image, and other angles are measured anti-clockwise from this.Computer Vision : CISC 4/689Derivative of GaussianComputer Vision : CISC 4/689Smoothing and Differentiation•Issue: noise–smooth before differentiation–two convolutions: to smooth, then differentiate?–actually, no - we can use a derivative of Gaussian filter•because differentiation is convolution, and convolution is associativeComputer Vision : CISC 4/689The Laplacian of Gaussian•Another way to detect an extremal first derivative is to look for a zero second derivative–the Laplacian•Bad idea to apply a Laplacian without smoothing–smooth with Gaussian, apply Laplacian–this is the same as filtering with a Laplacian of Gaussian filter•Now mark the zero points where there is a sufficiently large (first) derivative, and enough contrastComputer Vision : CISC 4/689Marr-Hildreth operator•The Laplacian is linear and rotationally symmetric. Thus, we search for the zero crossings of the image that is first smoothed with a Gaussian mask and then the second derivative is calculated; or we can convolve the image with the Laplacian of the Gaussian, also known as the LoG operator; •This defines the Marr-Hildreth operator. •One can also get a shape similar to G'' by taking the difference of two Gaussians having different standard deviations. A ratio of standard deviations of 1:1.6 will give a close approximation to .This is known as the DoG operator (Difference of Gaussians), or the Mexican Hat Operator. •Still sensitive to noise.Computer Vision :