1st and 2nd order derivatives in 1D © 1992–2008 R. C. Gonzalez & R. E. Woods ∂f∂x= f '(x) = f (x + 1) − f (x)∂2f∂x2=∂f '∂x= f '(x) − f '(x − 1)= f (x + 1) − f (x) − f (x) − f (x − 1)[ ]= f (x + 1) + f (x − 1) − 2 f (x)First derivative forward difference implementation: Second derivative backwards difference implementation:1st and 2nd order derivatives © 1992–2008 R. C. Gonzalez & R. E. Woods • Ramp edge • 1st derivative is non-zero along the entire ramp • 2nd derivative non-zero only at onset and end • Most image edges are ramps rather than step edges • 1st order derivatives produce thicker edges1st and 2nd order derivatives © 1992–2008 R. C. Gonzalez & R. E. Woods • Step edge • Second derivative produces a double edge response • The sign of the second order derivative can be used to locate edges1st and 2nd order derivatives © 1992–2008 R. C. Gonzalez & R. E. Woods • Noise • The 2nd derivative response is much stronger than the 1st derivative response • Line (roof edge) • 2nd derivative response is again stronger than the 1st derivative responsePoint detection • We know that second order derivatives have a stronger response to isolated points • What second order derivative operator can we use?Point detection • We know that second order derivatives have a stronger response to isolated points • In 2D this implies using the Laplacian ∇2f (x, y) =∂2f∂x2+∂2f∂y2∂2f∂x2= f (x + 1, y) + f (x − 1, y) − 2 f (x, y)∂2f∂y2= f (x, y + 1) + f (x, y − 1) − 2 f (x, y)∇2f (x, y) =f (x + 1, y) + f (x − 1, y) +f (x, y + 1) + f (x, y − 1) − 4 f (x, y)Implementations of the Laplacian • A single summary measure of second order derivatives – The analytic equation is isotropic – The implementations are rotationally invariant only in increments such as 45o or 90o ∇2f =∂2f∂x2+∂2f∂y2© 1992–2008 R. C. Gonzalez & R. E. WoodsPoint detection with the Laplacian • We can simply apply a threshold to the output of the Laplacian filter g(x, y) =1 if ∇2f (x, y) ≥ T0 otherwise© 1992–2008 R. C. Gonzalez & R. E. WoodsBlob detection • Isolated points are almost always due to noise; therefore, point detection is a contrived problem • However, detecting blobs is a real problem • Scale is what mattersLaplacian of Gaussian (LoG) © 1992–2008 R. C. Gonzalez & R. E. Woods • Blobs in real images have various spatial extents – This is their scale • The Laplacian defined before has no concept of scale – It only looks for points at the smallest possible scale • We can create a new operator by convolving the Laplacian with a GaussianLaplacian of Gaussian (LoG) ∂2G(x, y)∂x2=∂2∂x2e−x2+ y22σ2=∂∂x−xσ2e−x2+ y22σ2=x2σ4−1σ2e−x2+ y22σ2∂2G(x, y)∂y2=y2σ4−1σ2e−x2+ y22σ2∇2G(x, y) =x2σ4+y2σ4−2σ2e−x2+ y22σ2∇2G(x, y) =∂2G(x, y)∂x2+∂2G(x, y)∂y2© 1992–2008 R. C. Gonzalez & R. E. WoodsDiscrete Laplacian of Gaussian • Can use the usual (6σ+1)2 mask size • We make sure the elements of the mask sum to zero. Why? • We could also first convolve the image with a Gaussian, then a 3x3 Laplacian mask © 1992–2008 R. C. Gonzalez & R. E. WoodsBlob detection with LoG • Choose a Gaussian with "σ=10 • The resulting LoG operator will have strongest response for the bottom left blob because σ matches the scale of this blob bestLine detection • We saw that lines (roof edges) also have a strong response to second order derivatives – One possibility is to use the Laplacian – Have to make sure we take into account the double-edge response • For instance, we can take the absolute value of the Laplacian © 1992–2008 R. C. Gonzalez & R. E. WoodsLine detection - oriented filters • An even stronger response can be obtained with a directional second derivative that matches the orientation of the lines we are seeking • We can employ multiple line detection filters and take the maximum response © 1992–2008 R. C. Gonzalez & R. E. WoodsLine detection and the issue of scale • The same issue of scale we saw with points/blobs concerns all structures in images including lines • Line detection filters can have two scales: one in the direction perpendicular to the line and one in the tangential direction – Perpendicular direction: This can be a 1D Laplacian of Gaussian with σ chosen to reflect the expected width of the lines we are seeking – Tangential direction: Kernels elongated in the tangential direction provide more robustness to noise • This can be a Gaussian or a box filter • How wide should this Gaussian or box be?Edge models • Edges form the boundaries between distinct regions in an image hence they are important for segmentation • Edge models are useful for designing optimal edge detectors Step edge Ramp edge Roof edge(line) © 1992–2008 R. C. Gonzalez & R. E. WoodsStep and Ramp edge detection • Two typical ways to find step and ramp edges. Look for: – Pixels with large (in absolute value) first order derivatives – Zero-crossings of second derivatives © 1992–2008 R. C. Gonzalez & R. E. WoodsImage gradient • The gradient • Magnitude of the gradient – Large around edges • Orientation of the gradient – Perpendicular to the orientation of the boundary between two regions ∇f =∂f∂x∂f∂yM (x, y) =∂f∂x2+∂f∂y2α(x, y) = tan−1∂f ∂y∂f ∂xImage gradient example • Using the filters: 0 1 ∇f =∂f∂x∂f∂y=−22-1 0 1 -1 0 1 -1 0 1 -1 -1 -1 0 0 0 1 1 1 df/dx df/dy M = 2 2α= −450© 1992–2008 R. C. Gonzalez & R. E. WoodsGradient operators • Different ways to implement the computation for df/dx and df/dy • Sobel masks have slightly better noise-suppression than the Prewitt masks • None of these have any control over scale © 1992–2008 R. C. Gonzalez & R. E. WoodsGradient magnitude • Derivatives implemented using Sobel masks • Directionality • Too much detail M (x, y)