Feature Extraction

Image Interpretation
- N x M matrix I(i, j)
  - Nature & distribution of light sources
  - Shape of structures
  - Reflectance properties of surfaces
  - Position of camera
  - Properties of lens & CCD array
- Feature extracton
  - Discard redundant information in images
    - Reflectance & light conditions
  - Preserve useful information in images
    - Structures & camera pose

Salient Features

Interpret images using edge & corner data.

Cheap to compute
Small storage requirement
Invariant to changes in lighting
Provide strong clues to vision processing

Featureless Region

Smooth variation of intensities.

Edge

Intensity discontinuity in one direction.

Corner

Intensity discontinuity in two directions.

Edge Detection

1D Edge Detection

Look for maxima & minima in $$I'(x)$$.

$$ \frac{d I(x)}{dx} = I'(x) = \lim_{\Delta x \to 0} \frac{I(x + \Delta x) - I(x)}{\Delta x}

Convolve $$I(x)$$ with Gaussian kernel, obtain smoothed signal $$S(x)$$
Compute $$S'(x)$$
1. Kernel [1/2 0 -1/2]
Find maxima & minima of $$S'(x)$$
Thresholding to mark edges

Reduce Noise

Smooth the image by Gaussian filter first.

$$ g_{\sigma}(x) = \frac{1}{\sigma \sqrt{2 \pi}} e^{-\frac{x^2}{2 \sigma^2}}

Calculating Derivative of Smoothed Signal

Reduce the convolutions from twice to once by using the derivative theorem of convolution:

$$ S'(x) = \frac{d}{dx} (g{\sigma}(x) * I(x)) = g'{\sigma} * I(x)

Edge Detection

Find three points, solve for f(x)
Locate max/min by solving f'(x) = 0
Apply thresholding

2D Edge Deteciton

Gaussian filter:

$$ G_{\sigma}(x, y) = \frac{1}{2 \pi \sigma^2} e^{-\frac{x^2 + y^2}{2 \sigma^2}}

$$ S(x, y) = G{\sigma}(x, y) * I(x, y) \ \Delta S = \Delta (G{\sigma} I) = \begin{bmatrix} \frac{\partial (G_{\sigma} I)}{\partial x} \ \frac{\partial (G{\sigma} * I)}{\partial y} \end{bmatrix} = \begin{bmatrix} \frac{\partial G{\sigma}}{\partial x} I \ \frac{\partial G_{\sigma}}{\partial y} I \end{bmatrix}

Canny Edge Detection

Convolve $$I(x, y)$$ with Gaussian kernel, obtain smoothed signal $$S(x, y)$$
Compute $$\Delta S$$
Non-maximal suppression
1. Locate edgels (edge elements) where $$| \Delta S |$$ is greater than local values in directions $$\pm \Delta S$$
Thresholding on $$| \Delta S |$$ to retain strong edgels
Hysteresis: revive weak edgels
1. If they span the gaps between some strong edgels

Outputs a list of edgel positions with strength $$| \Delta S |$$ & orientation $$\frac{\Delta S}{| \Delta S |}$$.

Multi-Scale Edge Detection

Smaller $$\sigma$$
- Modest smoothing, edges at a fine scale
Larger $$\sigma$$
- More smoothing, suppressing finer details

Corner Detection

Aperture Problem

Only motions normal to an edge are observed when viewing a moving edge
Corner displacements are not ambiguous, useful for tracking in image sequences & matching in stereo pairs

Cross Correlation

Corner characterized by an intensity discontinuity in two directions, which is detecting using cross correlation.

$$ P(x, y) \bigotimes I(x, y) = \sum^n{u=-n} \sum^n{v=-n} P(u, v) I(x + u, y + v)

Difference with convolution
- Not associative
- Correlation used for pattern matching, convolution used for filtering
- Same if mask is symmetric

Normalized Cross Correlation

To handle the differences caused by lighting conditions.

$$ NCC(x, y) = \sum^n{u=-n} \sum^n{v=-n} \frac{(P(u, v) - \overline{P})}{\sqrt{\sum^n{u=-n} \sum^n{v=-n} (P(u, v) - \overline{P})^2}} \frac{(I(x+u, y+v) - \overline{I})}{\sqrt{\sum^n{u=-n} \sum^n{v=-n} (I(x+u, y+v) - \overline{I})^2}}

$$ NCC(x, y) = \frac{P - \overline{P}}{| P - \overline{P} |} \cdot \frac{I - \overline{I}}{| I - \overline{I} |} = cos \theta

Output
- 1: perfect match
- -1: perfect mismatch

Harris Corner Detection

Examine the max & min changes in intensity at each pixel.

Compute $$I_x$$ and $$I_y$$ at each pixel $$I(x, y)$$
Form & smooth images of $$I_x^2$$, $$I_y^2$$, and $$I_xI_y$$
Form image of cornerness function $$R$$
Locate local maxima in image of $$R$$ as corners
Achieve sub-pixel accuracy using quadratic approximation
Threshold corners

Change in intensity in direction n:

$$ I_n(x, y) = \Delta I(x, y) \cdot \frac{n}{| n |} = \Delta I(x, y)^T \frac{n}{\sqrt{n^Tn}}\ \Delta I = \begin{bmatrix} \frac{\partial I}{\partial x} \ \frac{\partial I}{\partial y} \end{bmatrix}

To find the min/max changes, calculate squared change in intensity around (x, y) in direction n:

$$ C_n(x, y) = I_n^2 = I_n^T I_n = \frac{n^T \Delta I \Delta I^T n}{n^T n} = \frac{n^T An}{n^T n}\ A = \Delta I \Delta I^T = \begin{bmatrix} I_x^2 & I_x I_y \ I_x I_y & I_y^2 \end{bmatrix}

By elementary eigenvector theory:

$$ \lambda_1 \le C_n(x, y) \le \lambda_2

where $$\lambda_1$$ & $$\lambda_2$$ are the min & max eigenvalues of $$A$$.

$$\lambda_1 \approx \lambda_2 \approx 0$$
- Smooth variation in intensity (featureless region)
$$\lambda_1 \approx 0$$, $$\lambda_2$$ large
- Intensity discontinuity in one direction (edge)
  - $$u_1$$: eigenvector to $$\lambda_1$$, direction along the edge
  - $$u_2$$: eigenvector to $$\lambda_2$$, direction normal to the edge
$$\lambda_1$$ & $$\lambda_2$$ large & distinct
- Intensity discontinuity in two directions (corner)

To avoid computing eigenvalues, calculate cornerness function $$R$$ for thresholding:

$$ R = \lambda_1 \lambda_2 - \kappa(\lambda_1 + \lambda_2)^2\ \lambda_1 \lambda_2 = det(A)\ \lambda_1 + \lambda_2 = trace(A)

where the tunable sensitivity parameter $$\kappa = 0.04$$. The smaller the value is, the more likely to detect sharp corners.

Then approximate local maxima via quadratic approximation.

Apply smoothing on $$A$$ so that $$det(A)$$ won't always be 0. Also apply smoothing to lessen the effect of noise (but might smooth away the corner features).

$$ A = \sum_u \sum_v w(u, v) \begin{bmatrix} I_x(u, v)^2 & I_x(u, v) I_y(u, v) \ I_x(u, v) I_y(u, v) & I_y(u, v)^2 \end{bmatrix}

Implementation Details

Truncated Summations

Kernels truncated s.t. samples less than $$\frac{1}{k}$$ of the peak value are discarded.

Decompose 2D Convolution

Decompose 2D convolution into two 2D ones. Saves $$\frac{(2n+1)^2}{2 * (2n+1)}$$ computational complexity, where $$2n+1$$ is the width/height of kernel.

$$ G{\sigma}(x, y) * I(x, y) = g{\sigma}(x) [g_{\sigma}(y) I(x, y)]

$$ Make sure the coefficients of the truncated Gaussian kernel sum to unity:

$$ \sum^n{u=-n} g{\sigma}(u) = 1

References

UMD Class Notes - Correlation and Convolution

Feature Extraction