Briefing

Corners and Feature Points

• What are distinctive points in the image?
• Distinctive points can (to some extent) be matched in two different images.

Corners in Mathematical Terms

• Luminance (colour) is a function \(I(x,y)\) in the co-ordinates \(x\) and \(y\)
• Corners are sharp changes in colour/luminance.
• Sharp changes are large values in the derivatives of \(I\),
  • i.e. a large gradient \(\nabla I(x,y)\)

Differentiation

• Sampled signal \(f[x]\).
  • The derivative is only defined on continuous functions \(f(x)\).
• Reconstruct the original signal.
  • Assume that it is bandwidth limited.
• Consider the Discrete Fourier Transform
  • Gives a Frequency Domain representation
  • The signal represented as a sum of sine waves.
  • Nyquist tells us that we can reconstruct the signal perfectly if it is sampled at twice the highest non-zero frequency. (At least two samples per wave.)
• Let \(T\) be sampling period
  • \(\omega_s=\frac{2\pi}{T}\) is the sampling frequency
• Ideal reconstruction filter
  • Frequency domain \(H(\omega)=1\) between \(\pm\pi/T\)
  • Time domain \[h(x)=\frac{\sin(\pi x/T)}{\pi x/T}\]
• Apply filter
  • Multiply in frequency domain
  • Convolve in time domain
• Reconstructed function: \(f(x) = f[x]* h(x)\)
  • Assuming bandwidth limited signal, \(\omega_n(f)<\pi/T\)
• The reconstructed function can be differentiated.

Convolution

\[f[x]*h(x) = \sum_{k=-\infty}^{\infty} f[k]h(x-k)\]

• Note the convolution of a sampled signal and a continuous one
• Demo

Note OpenCV uses correlation instead of convolution. Conceptually this is different, but in practice, the only effect is to mirror the filter.

Differentiation of the reconstructed signal

\[D\{f(x)\} = D\{f[x]*h(x)\}\]

\[D\{f(x)\} = D\{\sum_{k=-\infty}^{\infty} f[k]h(x-k)\}\]

Both convolution and derivation are linear operators

\[D\{f(x)\} = \sum_{k=-\infty}^{\infty} f[k]D\{h(x-k)\}\]

This is a convolution with the derivative of \(h\).

\[D\{f(x)\} = f[x]*D\{h(x)\}\]

Resampling

Now, we can sample this signal to get

\[S\{f'(x)\} = S\{f(x)*D\{h(x)\} = f[x]*S\{h'(x)\} = f[x]*h'[x]\]

• In other words, the derivative a sampled signal is a convolution with \(h'[x]\).
• Unfortunately, \(h[x]\) has infinite extent, so this is not practical.
• Truncations would also leave artifacts

Possible approximations

Gaussian

\[g(x) = \frac{1}{\sqrt{2\pi}\sigma}\exp\frac{-x^2}{2\sigma^2}\]

\[g'(x) = \frac{x}{\sigma^2\sqrt{2\pi}\sigma}\exp\frac{-x^2}{2\sigma^2}\]

Also infinite extent, need to trunctate.

Differences

\[h'[x] = ½[1,-1]\]

\[h[x]=½[1,1]\]

Note This filter takes the plain difference between adjacent pixels, and is therefore extremely susceptible to noise. The larger filters have a blurring effect as well as differentiating, by depending on a larger window.

Sobel

\[h[x] = [1,\sqrt{2},1]/(2+\sqrt2)\]

\[h'[x] = [1,0,-1]/3\]

Sobel without constant factors

\[h[x] = [1,2,1]\]

\[h'[x] = [1,0,-1]\]

Going to 2D

\[D_x\{I(x,y)\} = I[x,y]*D_x\{h(x,y)\} = I[x,y]*D_x\{h(x)\}*h(y)\]

The last equality holds for separable filters only. The ideal sync and suggested approximations are separable.

\[I_x[x,y] = I[x,y]*g'[x]*g[y] = \sum_{k=-\omega/2}^{k=\omega/2} \sum_{l=-\omega/2}^{l=\omega/2} I[k,l]g'[x-k]g[y-l]\]

Corner Detection

\[\nabla I(x,y)= [ I_x, I_y ]^T\]

• Feature point: \(I_x\) and \(I_y\) are large
• Horizontal edge: \(I_x\) is small, \(I_y\) is large
• Vertical edge: \(I_y\) is small, \(I_x\) is large
• Is both \(I_x\) and \(I_y\) large a guarantee for a feature point?
• No, we could have a diagonal edge.
  • We nead a measure which is rotationally invariant.
• No, it could be a textured surface - every pixel is a corner
  • We need to look at a window \(W(\mathbf{x})\) around the pixel \(W(\mathbf{x})\)
• No, small variation could be due to random noise

\[G(\mathbf{x}) = \sum_{\mathbf{\tilde x}\in W(\mathbf{x})} \nabla I(\mathbf{\tilde x}) \nabla I^T(\mathbf{\tilde x})\]

\[G = \begin{bmatrix} \sum I_x^2 & \sum I_xI_y \\ \sum I_xI_y & \sum I_y^2 \end{bmatrix} \]

• If this matrix is non-singular we have a corner (or texture)
  • If \(I_x=0\) or \(I_y=0\) we get a singular matrix
  • We also get a singular matrix if one of the derivatives vanish in some rotation of the image
• If both the singular values (eigenvalues) are non-zero, then the matrix is non-singular
• Consider the following heuristic \[C(G)=||G|| + k\mathsf{tr}^2(G)=\lambda_1\lambda_2 + k(\lambda_1+\lambda_2)\] where \(k\) is a constant scalar and \(\lambda_1\) the eigenvalues
• If \(k\) is small, both eigenvalues must be large to make \(C(G)\) large
• If \(k\) is large, one large eigenvalue suffices

The Harris Corner Detector uses \(C(G)\) as its heuristic.

The Laplacian

The Laplacian is commonly used in image processing, even if I have not seen it as often in the machine vision literature. The idea is to use the second order derivative, \[\nabla^2I(x,y)\] This is commonly approximated by one of the filters \[\begin{bmatrix} 0 & 1 & 0 \\ 1 & -4 & 1 \\ 0 & 1 & 0 \end{bmatrix} \quad\text{or}\quad \begin{bmatrix} 1 & 1 & 1 \\ 1 & -8 & 1 \\ 1 & 1 & 1 \end{bmatrix} \] To avoid the problems of the small window size, we typically combine the Laplacian with a blurring filter, usually a Gaussian. Thus we compute \[ E = L*G*I\] where \(I\) is the image, \(L\) the Laplacian, and \(G\) the Gaussian. Because of the associativity of linear operations, we have \[ E = L*(G*I)=(L*G)*I\] In other words, we can precaulcualte the Laplacian of Gaussian (LoG) filter \(L*G\) as one filter.

Debrief