---
title: Lecture: Corner Detection
categories: lecture
---

# Briefing

## Corners and Feature Points

![Universitetsområdet i Ålesund](Images/ntnuaes1.jpg)

![Universitetsområdet i Ålesund (ny vinkel)](Images/ntnuaes2.jpg)

+ 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$,
    + 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 to 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)

### 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)\}$$

### 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]$$

**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]$$

## Harris Feature Detector

# Debrief