Image Filtering

Correlation and Convolution

Definition

Def Image Filtering Image filtering is an transformation such that compute the function value of local neighbourhood at each pixel.

Definition

Def Linear Filters Linear filtering is the filtering method in which the value of output pixel is linear combinations of the neighbouring input pixels.

Correlation Filtering

Given the averaging window size is :We can generalize to allow different weights: where is a non-uniform weights. We write this as .

e.g. $$\begin{bmatrix}1 & 1 & 1 \ 1 &1 & 1 \ 1 & 1 & 1\end{bmatrix}\otimes \begin{bmatrix}

1 & 2 \ 3 & 4 \end{bmatrix} = \begin{bmatrix}10 & 10 \ 10 & 10 \end{bmatrix}$$

Convolution Filtering

Convolution filtering is the filtering method in which the output is the correlation of the input image with a flipped kernel. The kernel is flipped in both dimensions: We write this as .

e.g.

Remark

As its name suggests, convolution filtering is the convolution of the kernels, in the function sense.

Separable Kernel

A kernel is separable if it can be written as the outer product of two vectors: And hence the convolution can be computed in two steps:

e.g.

Lemma

Suppose we have singular value decomposition of a kernel matrix : Then is separable if all singular values except the largest (first) one are zeroes. In such case, we have .

Proposition

The time complexity of filtering an image with an kernel is . If the kernel is separable, the time complexity can be reduced to .

Image Smoothing

Salt and Pepper Noise

Salt and pepper noise is random occurrences of black and white pixels.

Definition

Def Impulse Noise Impulse noise is random occurrences of white pixels, sometimes, it is also referred to as a special case of salt and pepper noise.

Definition

Def Gaussian Noise Variations in intensity drawn from a Gaussian normal distribution.

Definition

Def Gaussian Filtering Gaussian filter is a specific filter such that the kernel in correlation filter is a 2D gaussian function. The variance of the Gaussian function determines extent of smoothing.

Proposition

Prop

• Gaussian filter is linear.
• Gaussian filter is isotropic, i.e. it smooths the image in all directions equally.
• A Gaussian filter convolves with itself gives another Gaussian. Concretely, convolving two times with Gaussian kernel of width is equivalent to convolving once with a Gaussian kernel of width .
• Gaussian filter is separable, i.e. it can be decomposed into two 1D filters.

Definition

Def Median Filter Median filter replaces centre pixel by median within window. It is good for removing salt-and-pepper (impulse) noise.

Proposition

Prop Median filter is non-linear.

Definition

Def Bilateral Filter The bilateral filter combines domain filtering and range filtering. The domain filter is a Gaussian filter spatially, and the range filter is a Gaussian filter in intensity space. Intuitively, pixels that are closer together spatially, or with similar intensities (or colors) have a higher influence on each other. The output at pixel of the filtered image is given by: where is the neighbourhood of pixel , is the spatial Gaussian filter, is the intensity Gaussian filter, and is the normalization factor. Consequently, the bilateral filter can preserve edges while smoothing the image:

Proposition

Prop Bilateral filter is non-linear. The Bilateral filter is a generalization of the Gaussian filter, specifically, it reduces to the Gaussian filter when .

Definition

Def Sharpening Filter The sharpening filter kernel is

Edge Detectors

Definition

Def Sobel Filter The Sobel filter is a discrete differentiation operator, computing an approximation of the gradient of the image intensity function. It is implemented as a convolution of the image with Sobel kernel matrices in horizontal and vertical directions. The Sobel kernel matrices are given by: The edge strength is given by the gradient magnitude: The gradient direction (orientation of edge normal) is given by: where and are the gradient components in the and directions respectively.

Proposition

Prop Sobel filter is a linear filter.

Algorithm

Algorithm Canny Edge Detector

1. Filter image with derivative of Gaussian.
2. Find magnitude and orientation of gradient.
3. Non-maximum suppression: thin wide “ridges” down to single pixel width.
4. Apply double threshold to determine potential edges.

Corner Detection

Definition

Def Flat Region We say that a region is flat if it has an isotropic structure.

Definition

Def Edge Region We say that a region is an edge if it has a linear structure.

Definition

Def Corner Region We say that a region is a corner if it has a bi-directional structure.

Algorithm

Algorithm Harris Corner Detector The measure of change of intensity for the shift : where is the window function and is a matrix computed from image derivatives, called the auto-correlation matrix:The cornerness score with empirical constant is then given by Thus the algorithm is by

1. Compute matrix for each image window to get their cornerness scores.
2. Find points whose surrounding window gave large corner response ( threshold). The convention is is positive for corners, negative for edges, and small for flat regions.
3. Take the points of local maxima, i.e. perform non-maximum suppression.

import numpy as np
 
detM = Ix2 * Iy2 - Ixy ** 2
traceM = Ix2 + Iy2
R = detM - k * traceM ** 2
 
threshold = thresh * R.max()
corners = np.where(R > threshold)
coordinates = np.array(corners).T

Proposition

Prop Harris corner detector is rotationally invariant, but not scale invariant. Proof Suppose is some rotation matrix. Then before rotating, After rotating, we have:

SIFT Feature Detector

Definition

Def Interest Points Interest points are local maxima in both position and scale in an image.