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