Revision 2a09d6af008ccd3cbb27d4d663f5fcaecfee0e36 (click the page title to view the current version)
Changes from 2a09d6af008ccd3cbb27d4d663f5fcaecfee0e36 to current
---
title: Lecture: Corner Detection
categories: lecture
---
# 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 derivates of $I$,
+ 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](https://youtu.be/HW4IamyQnzw)
**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[k]*D\{h(x)\}$$
$$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
