# Lecture: Corner Detection

# 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.