Download Presentation
## Scales and Descriptors

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Scales and Descriptors**EECS 442 – David Fouhey Fall 2019, University of Michigan http://web.eecs.umich.edu/~fouhey/teaching/EECS442_F19/**Administrivia**• HW1 due tonight (modulo late days) • HW2 out tonight • Collaborate • Read the syllabus for what’s allowed**Recap: Motivation**1: find corners+features Image credit: M. Brown**Last Time**Image gradients – treat image like function of x,y – gives edges, corners, etc. Figure credit: S.Seitz**“flat” region:no change in all directions**“edge”:no change along the edge direction “corner”:significant change in all directions Last Time – Corner Detection Can localize the location, or any shift → big intensity change. Diagram credit: S.Lazebnik**Corner Detection**By doing a taylor expansion of the image, the second moment matrix tells us how quickly the image changes and in which directions. Can compute at each pixel Directions Amounts**Putting Together The Eigenvalues**“Edge” R < 0 “Corner”R > 0 α: constant (0.04 to 0.06) |R| small “Edge” R < 0 “Flat” region Slide credit: S.Lazebnik; Note: this refers to visualization ellipses, not original M ellipse. Other slides on the internet may vary**In Practice**• Compute partial derivatives Ix, Iy per pixel • Compute M at each pixel, using Gaussian weighting w C.Harris and M.Stephens. “A Combined Corner and Edge Detector.” Proceedings of the 4th Alvey Vision Conference: pages 147—151, 1988. Slide credit: S.Lazebnik**In Practice**• Compute partial derivatives Ix, Iy per pixel • Compute M at each pixel, using Gaussian weighting w • Compute response function R C.Harris and M.Stephens. “A Combined Corner and Edge Detector.” Proceedings of the 4th Alvey Vision Conference: pages 147—151, 1988. Slide credit: S.Lazebnik**Computing R**Slide credit: S.Lazebnik**Computing R**Slide credit: S.Lazebnik**In Practice**• Compute partial derivatives Ix, Iy per pixel • Compute M at each pixel, using Gaussian weighting w • Compute response function R • Threshold R C.Harris and M.Stephens. “A Combined Corner and Edge Detector.” Proceedings of the 4th Alvey Vision Conference: pages 147—151, 1988. Slide credit: S.Lazebnik**Thresholded R**Slide credit: S.Lazebnik**In Practice**• Compute partial derivatives Ix, Iy per pixel • Compute M at each pixel, using Gaussian weighting w • Compute response function R • Threshold R • Take only local maxima (called non-maxima suppression) C.Harris and M.Stephens. “A Combined Corner and Edge Detector.” Proceedings of the 4th Alvey Vision Conference: pages 147—151, 1988. Slide credit: S.Lazebnik**Thresholded**Slide credit: S.Lazebnik**Final Results**Slide credit: S.Lazebnik**Desirable Properties**If our detectors are repeatable, they should be: • Invariant to some things: image is transformed and corners remain the same • Covariant/equivariant with some things: image is transformed and corners transform with it. Slide credit: S.Lazebnik**Recall Motivating Problem**Images may be different in lighting and geometry**R**R x(image coordinate) x(image coordinate) Affine Intensity Change M only depends on derivatives, so b is irrelevant But a scales derivatives and there’s a threshold threshold Partially invariant to affine intensity changes Slide credit: S.Lazebnik**Image Translation**All done with convolution. Convolution is translation equivariant. Equivariant with translation Slide credit: S.Lazebnik**Image Rotation**Rotations just cause the corner rotation matrix to change. Eigenvalues remain the same. Equivariant with rotation Slide credit: S.Lazebnik**Image Scaling**Corner One pixel can become many pixels and vice-versa. Not equivariant with scaling How do we fix this? Slide credit: S.Lazebnik**Recap: Motivation**1: find corners+features 2: match based on local image data How? Image credit: M. Brown**Today**• Fixing scaling by making detectors in both location and scale • Enabling matching between features by describing regions**Key Idea: Scale**Left to right: each image is half-sized Upsampled with big pixels below 1/2 1/2 1/2 Note: I’m also slightly blurring to prevent aliasing (https://en.wikipedia.org/wiki/Aliasing)**Key Idea: Scale**Left to right: each image is half-sized If I apply a KxK filter, how much of the original image does it see in each image? 1/2 1/2 1/2 Note: I’m also slightly blurring to prevent aliasing (https://en.wikipedia.org/wiki/Aliasing)**Solution to Scales**Try them all! Harris Detection Harris Detection Harris Detection Harris Detection See: Multi-Image Matching using Multi-Scale Oriented Patches, Brown et al. CVPR 2005**Aside: This Trick is Common**Given a 50x16 person detector, how do I detect: (a) 250x80 (b) 150x48 (c) 100x32 (d) 25x8 people? Sample people from image**Aside: This Trick is Common**Detecting all the people The red box is a fixed size Sample people from image**Aside: This Trick is Common**Detecting all the people The red box is a fixed size Sample people from image**Aside: This Trick is Common**Detecting all the people The red box is a fixed size Sample people from image**Blob Detection**Another detector (has some nice properties) Minima Maxima Find maxima and minima of blob filter response in scale and space Slide credit: N. Snavely**Gaussian Derivatives**2ndDeriv 1stDeriv Gaussian**Laplacian of Gaussian**+ Slight detail: for technical reasons, you need to scale the Laplacian.**Edge Detection with Laplacian**Edge Laplacian Of Gaussian Edge = Zero-crossing Figure credit: S. Seitz**Blob Detection with Laplacian**Edge: zero-crossing Blob: superposition of zero-crossing Remember: can scale signal or filter maximum Figure credit: S. Lazebnik**Scale Selection**Given binary circle and Laplacian filter of scale σ, we can compute the response as a function of the scale. Radius: 8 R: 0.02 R: 2.9 R: 1.8**Characteristic Scale**Characteristic scale of a blob is the scale that produces the maximum response Image Abs. Response Slide credit: S. Lazebnik. For more, see: T. Lindeberg (1998). "Feature detection with automatic scale selection."International Journal of Computer Vision30 (2): pp 77--116.**Scale-space blob detector**• Convolve image with scale-normalized Laplacian at several scales Slide credit: S. Lazebnik**Scale-space blob detector: Example**Slide credit: S. Lazebnik**Scale-space blob detector: Example**Slide credit: S. Lazebnik**Scale-space blob detector**• Convolve image with scale-normalized Laplacian at several scales • Find maxima of squared Laplacian response in scale-space Slide credit: S. Lazebnik**Finding Maxima**Point i,j is maxima (minima if you flip sign) in image I if: for y=range(i-1,i+1+1): for x in range(j-1,j+1+1): if y == i and x== j: continue #below has to be true I[y,x] < I[i,j]**Scale Space**Red lines are the scale-space neighbors Radius: 8 R: 0.02 R: 2.9 R: 1.8**Scale Space**Blue lines are image-space neighbors (should be just one pixel over but you should get the point) Radius: 8 R: 0.02 R: 2.9 R: 1.8**Finding Maxima**Suppose I[:,:,k] is image at scale k. Point i,j,k is maxima (minima if you flip sign) in image I if: for y=range(i-1,i+1+1): for x in range(j-1,j+1+1): for c in range(k-1,k+1+1): if y == i and x== j and c==k: continue #below has to be true I[y,x,c] < I[i,j,k]**Scale-space blob detector: Example**Slide credit: S. Lazebnik**Efficient implementation**• Approximating the Laplacian with a difference of Gaussians: (Laplacian) (Difference of Gaussians) Slide credit: S. Lazebnik**Efficient implementation**David G. Lowe. "Distinctive image features from scale-invariant keypoints.”IJCV 60 (2), pp. 91-110, 2004. Slide credit: S. Lazebnik**Problem 1 Solved**• How do we deal with scales: try them all • Why is this efficient? Vast majority of effort is in the first and second scales