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\),
  • 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

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