Detectors and Descriptors Detectors and Descriptors Notes Administrivia HW2 is out and students are encouraged to start early. Last Time – Gradients Image gradients treat the image as a function of x and y. ∇ f = [ ∂ f ∂ x , 0 ] \nabla f = [\frac{\partial f}{\partial x}, 0] ∇ f = [ ∂ x ∂ f , 0 ] ∇ f = [ 0 , ∂ f ∂ y ] \nabla f = [0, \frac{\partial f}{\partial y}] ∇ f = [ 0 , ∂ y ∂ f ] ∇ f = [ ∂ f ∂ x , ∂ f ∂ y ] \nabla f = [\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}] ∇ f = [ ∂ x ∂ f , ∂ y ∂ f ] Image gradients help find edges and corners. Filters Smoothing Filters remove noise and typically sum to 1.Derivative Filters find edges and typically sum to 0.Motivation The goal is to find corners and features in images. Desirables for Descriptor Repeatable: Should find the same features even with distortion.Saliency: Each feature should be distinctive.Compactness: Shouldn’t just be all the pixels.Locality: Should only depend on local image data.Basic Idea Edge: No change along the edge direction.Corner: Significant change in all directions.Flat Region: No change in all directions.A significant intensity change should be visible with a small window or any shift. Error (Sum of Squares) for u,v offset is given by the equation: E ( u , v ) = ∑ ( x , y ) ∈ W ( I [ x + u , y + v ] − I [ x , y ] ) 2 E(u, v) = \sum_{(x,y) \in W} (I[x + u, y + v] - I[x, y])^2 E ( u , v ) = ∑ ( x , y ) ∈ W ( I [ x + u , y + v ] − I [ x , y ] ) 2 Taylor Series Taylor Series is used to linearize a function: f ( x + d ) ≈ f ( x ) + ∂ f ∂ x d f(x + d) \approx f(x) + \frac{\partial f}{\partial x} d f ( x + d ) ≈ f ( x ) + ∂ x ∂ f d Applying Taylor series to images, treating them as functions of x and y: I ( x + u , y + v ) ≈ I ( x , y ) + I < e m > x u + I < / e m > y v I(x + u, y + v) \approx I(x, y) + I<em>x u + I</em>y v I ( x + u , y + v ) ≈ I ( x , y ) + I < e m > xu + I < / e m > y v I < e m > x I<em>x I < e m > x I < / e m > y I</em>y I < / e m > y Using Taylor series expansion to approximate the error function:E ( u , v ) = ∑ < e m > ( x , y ) ∈ W ( I [ x + u , y + v ] − I [ x , y ] ) 2 ≈ ∑ < / e m > ( x , y ) ∈ W ( I [ x , y ] + I < e m > x u + I < / e m > y v − I [ x , y ] ) 2 E(u, v) = \sum<em>{(x,y) \in W} (I[x + u, y + v] - I[x, y])^2 \approx \sum</em>{(x,y) \in W} (I[x, y] + I<em>x u + I</em>y v - I[x, y])^2 E ( u , v ) = ∑ < e m > ( x , y ) ∈ W ( I [ x + u , y + v ] − I [ x , y ] ) 2 ≈ ∑ < / e m > ( x , y ) ∈ W ( I [ x , y ] + I < e m > xu + I < / e m > y v − I [ x , y ] ) 2 = ∑ < e m > ( x , y ) ∈ W ( I < / e m > x u + I y v ) 2 = \sum<em>{(x,y) \in W} (I</em>x u + I_y v)^2 = ∑ < e m > ( x , y ) ∈ W ( I < / e m > xu + I y v ) 2 = ∑ < e m > ( x , y ) ∈ W I < / e m > x 2 u 2 + 2 I < e m > x I < / e m > y u v + I y 2 v 2 = \sum<em>{(x,y) \in W} I</em>x^2 u^2 + 2I<em>x I</em>y uv + I_y^2 v^2 = ∑ < e m > ( x , y ) ∈ W I < / e m > x 2 u 2 + 2 I < e m > x I < / e m > y uv + I y 2 v 2 By linearizing the image, E(u, v) can be approximated with a quadratic function of u and v: E ( u , v ) ≈ [ u , v ] M [ u , v ] T E(u, v) \approx [u, v] M [u, v]^T E ( u , v ) ≈ [ u , v ] M [ u , v ] T Where M is the second moment matrix:M = [ ∑ < e m > x , y ∈ W I < / e m > x 2 a m p ; ∑ < e m > x , y ∈ W I < / e m > x I < e m > y ∑ < / e m > x , y ∈ W I < e m > x I < / e m > y a m p ; ∑ < e m > x , y ∈ W I < / e m > y 2 ] M = \begin{bmatrix} \sum<em>{x,y \in W} I</em>x^2 & \sum<em>{x,y \in W} I</em>x I<em>y \ \sum</em>{x,y \in W} I<em>x I</em>y & \sum<em>{x,y \in W} I</em>y^2 \end{bmatrix} M = [ ∑ < e m > x , y ∈ W I < / e m > x 2 am p ; ∑ < e m > x , y ∈ W I < / e m > x I < e m > y ∑ < / e m > x , y ∈ W I < e m > x I < / e m > y am p ; ∑ < e m > x , y ∈ W I < / e m > y 2 ] Intuitively What is M? Approximation:M ≈ [ a a m p ; 0 0 a m p ; b ] M \approx \begin{bmatrix} a & 0 \ 0 & b \end{bmatrix} M ≈ [ a am p ; 0 0 am p ; b ] gradients are either vertical or horizontal at a pixel (so I < e m > x I < / e m > y = 0 I<em>x I</em>y = 0 I < e m > x I < / e m > y = 0 Cases:a, b both small: flat one big, other small: edge a, b both big: corner If the image is rotated by a rotation θ \theta θ V − 1 [ a a m p ; 0 0 a m p ; b ] V V^{-1} \begin{bmatrix} a & 0 \ 0 & b \end{bmatrix} V V − 1 [ a am p ; 0 0 am p ; b ] V Eigenvalues and M Matrix Given M, can decompose it into eigenvectors V and eigenvalues λ < e m > 1 , λ < / e m > 2 \lambda<em>1, \lambda</em>2 λ < e m > 1 , λ < / e m > 2 M = V − 1 [ λ < e m > 1 0 0 λ < / e m > 2 ] V M = V^{-1} \begin{bmatrix} \lambda<em>1 & 0 \ 0 & \lambda</em>2 \end{bmatrix} V M = V − 1 [ λ < e m > 1 0 0 λ < / e m > 2 ] V Compute quantity R from MR = d e t ( M ) − α t r a c e ( M ) 2 = λ < e m > 1 λ < / e m > 2 − α ( λ < e m > 1 + λ < / e m > 2 ) 2 R = det(M) - \alpha trace(M)^2 = \lambda<em>1 \lambda</em>2 - \alpha (\lambda<em>1 + \lambda</em>2)^2 R = d e t ( M ) − α t r a ce ( M ) 2 = λ < e m > 1 λ < / e m > 2 − α ( λ < e m > 1 + λ < / e m > 2 ) 2 α \alpha α R and Corner/Edge/Flat Detection R tells us whether we’re at a corner, edge, or flat region:R >> 0: corner (λ < e m > 1 ≈ λ < / e m > 2 ≫ 0 \lambda<em>1 \approx \lambda</em>2 \gg 0 λ < e m > 1 ≈ λ < / e m > 2 ≫ 0 R << 0: edge (λ < e m > 1 ≫ λ < / e m > 2 ≫ 0 \lambda<em>1 \gg \lambda</em>2 \gg 0 λ < e m > 1 ≫ λ < / e m > 2 ≫ 0 λ < e m > 2 ≫ λ < / e m > 1 ≫ 0 \lambda<em>2 \gg \lambda</em>1 \gg 0 λ < e m > 2 ≫ λ < / e m > 1 ≫ 0 |R| ≈ 0: flat (λ < e m > 1 , λ < / e m > 2 ≈ 0 \lambda<em>1, \lambda</em>2 \approx 0 λ < e m > 1 , λ < / e m > 2 ≈ 0 What You Need To Know Need to be able to take derivatives of the image. Need to be able to compute the entries of M at every pixel. Should know that some properties of M indicate whether a pixel is a corner or not. In Practice: Harris Corner Detection Compute partial derivatives I < e m > x I<em>x I < e m > x I < / e m > y I</em>y I < / e m > y Compute M at each pixel, using Gaussian weighting w:M = ∑ < e m > x , y ∈ W w ( x , y ) [ I < / e m > x 2 a m p ; I < e m > x I < / e m > y I < e m > x I < / e m > y a m p ; I y 2 ] M = \sum<em>{x,y \in W} w(x, y) \begin{bmatrix} I</em>x^2 & I<em>x I</em>y \ I<em>x I</em>y & I_y^2 \end{bmatrix} M = ∑ < e m > x , y ∈ W w ( x , y ) [ I < / e m > x 2 am p ; I < e m > x I < / e m > y I < e m > x I < / e m > y am p ; I y 2 ] Compute response function R:R = d e t ( M ) − α t r a c e ( M ) 2 = λ < e m > 1 λ < / e m > 2 − α ( λ < e m > 1 + λ < / e m > 2 ) 2 R = det(M) - \alpha trace(M)^2 = \lambda<em>1 \lambda</em>2 - \alpha (\lambda<em>1 + \lambda</em>2)^2 R = d e t ( M ) − α t r a ce ( M ) 2 = λ < e m > 1 λ < / e m > 2 − α ( λ < e m > 1 + λ < / e m > 2 ) 2 Threshold R. Take only local maxima (non-maxima suppression). Desirable Properties If detectors are repeatable, they should be:Invariant to some things: image is transformed and corners remain the same. Equivariant with some things: image is transformed and corners transform with it. Affine Intensity Change Partially invariant to affine intensity changes: I < e m > n e w = a I < / e m > o l d + b I<em>{new} = aI</em>{old} + b I < e m > n e w = a I < / e m > o l d + b M only depends on derivatives, so b is irrelevant. But a scales derivatives and there’s a threshold. Image Translation Equivariant with translation because convolution is translation equivariant. Image Scaling Not equivariant with scaling. Key Idea: Scale Space Try different scales to handle image scaling. Blob Detection Find maxima and minima of blob filter response in scale and space. Gaussian Derivatives First Derivative∂ ∂ x g \frac{\partial}{\partial x} g ∂ x ∂ g ∂ ∂ y g \frac{\partial}{\partial y} g ∂ y ∂ g Second Derivative∂ 2 ∂ x 2 g \frac{\partial^2}{\partial x^2} g ∂ x 2 ∂ 2 g ∂ 2 ∂ y 2 g \frac{\partial^2}{\partial y^2} g ∂ y 2 ∂ 2 g Laplacian of Gaussian (LoG) ∇ 2 = ∂ 2 ∂ x 2 g + ∂ 2 ∂ y 2 g \nabla^2 = \frac{\partial^2}{\partial x^2} g + \frac{\partial^2}{\partial y^2} g ∇ 2 = ∂ x 2 ∂ 2 g + ∂ y 2 ∂ 2 g Scale the Laplacian of Gaussian if you want to compare across sigmas:∇ n o r m 2 = σ 2 ( ∂ 2 ∂ x 2 g + ∂ 2 ∂ y 2 g ) \nabla_{norm}^2 = \sigma^2 (\frac{\partial^2}{\partial x^2} g + \frac{\partial^2}{\partial y^2} g) ∇ n or m 2 = σ 2 ( ∂ x 2 ∂ 2 g + ∂ y 2 ∂ 2 g ) Edge Detection with LoG Edge = Zero-crossing f ∗ ∂ 2 ∂ x 2 g f * \frac{\partial^2}{\partial x^2} g f ∗ ∂ x 2 ∂ 2 g Scale Selection Characteristic scale of a blob is the scale that produces the maximum response. Scale-space blob detector Convolve image with scale-normalized Laplacian at several scales. Find maxima of squared Laplacian response in scale-space. Finding Maxima Point i,j is maxima (minima if you flip sign) in image I if it’s bigger than all neighbors.
for y in range(i-1, i+1+1):
for x in range(j-1, j+1+1):
if y == i and x == j: continue
I[y, x] < I[i, j]
Scale Space Blue lines are image-space neighbors. Red lines are the scale-space neighbors. Finding Maxima in Scale Space 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 in 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
I[y, x, c] < I[i, j, k]
Approximating the Laplacian with a Difference of Gaussians ( L a p l a c i a n ) ≈ ( D i f f e r e n c e o f G a u s s i a n s ) (Laplacian) \approx (Difference \ of \ Gaussians) ( L a pl a c ian ) ≈ ( D i f f er e n ce o f G a u ss ian s ) ( ∂ 2 ∂ x 2 g + ∂ 2 ∂ y 2 g ) ≈ ( 1 2 π σ < e m > 1 2 e − x 2 + y 2 2 σ < / e m > 1 2 − 1 2 π σ < e m > 2 2 e − x 2 + y 2 2 σ < / e m > 2 2 ) (\frac{\partial^2}{\partial x^2}g + \frac{\partial^2}{\partial y^2}g) \approx (\frac{1}{\sqrt{2\pi\sigma<em>1^2}}e^{-\frac{x^2+y^2}{2\sigma</em>1^2}} - \frac{1}{\sqrt{2\pi\sigma<em>2^2}}e^{-\frac{x^2+y^2}{2\sigma</em>2^2}}) ( ∂ x 2 ∂ 2 g + ∂ y 2 ∂ 2 g ) ≈ ( 2 π σ < e m > 1 2 1 e − 2 σ < / e m > 1 2 x 2 + y 2 − 2 π σ < e m > 2 2 1 e − 2 σ < / e m > 2 2 x 2 + y 2 ) Problem 1: How do we deal with scales? Try them all! Why is this efficient? 1 + 1/4 + 1/16 + 1/64 + 1/4^i … = 4/3 Vast majority of effort is in the first and second scales Problem 2 – Describing Features Once we’ve found a corner/blobs, we can’t just use the image nearby.
What about:Scale? Rotation? Additive light? Handling Scale Given characteristic scale (maximum Laplacian response), we can just rescale image. Handling Rotation Given window, can compute “dominant orientation” and then rotate image. SIFT Features SIFT features at characteristic scales and dominant orientations. SIFT Descriptors Compute gradients. Build histogram (4x4 in practice). Gradients ignore global illumination changes. Gaussian weighting: smooth response Normalization: reduces illumination effects Clamping Tons of more stuff Properties of SIFT Can handle: up to ~60 degree out-of-plane rotation, changes of illumination Fast, efficient, code available (but was patented) Feature Descriptors 128D vector x Think of feature as some non-linear filter that maps pixels to 128D feature 2nd Nearest Neighbor Trick Given a feature xq, nearest neighbor to x is a good match, but distances can’t be thresholded. Instead, find nearest neighbor (x1NN) and second nearest neighbor (x2NN). This ratio is a good test for matches:r = x < e m > q − x < / e m > 1 N N x < e m > q − x < / e m > 2 N N r = \frac{x<em>q - x</em>{1NN}}{x<em>q - x</em>{2NN}} r = x < e m > q − x < / e m > 2 N N x < e m > q − x < / e m > 1 N N