Filtering

Cross-Correlation and Convolution

Cross-Correlation and Convolution are basic operations that we perform to extract information from images. Both these operations are Linear Shift Invariant (LSI) systems.

For a system to be linear, Op(A+B) = Op(A) + Op(B) where Op is the operation performed and A and B are the sets of pixels to be processed. In a linear operation, we replace every pixel with a linear combination of its neighbors.

For a system to be shift invariant, if g(x) = w(x) * f(x), then w(x) * f(x-x0) = g(x-x0), where w(x) is the filter/operation and f(x) is the original signal. This means that we perform the same operation at every point in the image.

Convolution is also commutative ($f*g=g*f$) and associative ($f*(g*h)=(f*g)*h$).

Cross-Correlation is computed as:

$g(x,y) = \sum_{s=-a}^a\sum_{t=-b}^b w(s,t)f(x+s, y+t)$

and convolution is computed as:

$g(x,y) = \sum_{s=-a}^a\sum_{t=-b}^b w(s,t)f(x-s, y-t)$

The operations (cross-correlation and convolution) are the same if the kernel is symmetric.
This is because (in theory) convolution rotates the kernel by 180 degrees.
However, when we implement convolution, we do not do this.

Handling Boundaries

While applying filters/operations to pixels, we may not be able to directly operate on the boundary pixels. We can do one of the following:

• Do not operate on the boundary pixels

• Pad with 0s

  
• Pad with the nearby pixel values
• Repeat the pixel values in a cyclic manner

Image Smoothing

Image Smoothing aims to suppress noise in an image.

Smoothing, however, also blurs sharp edges, causing loss of information/detail.

Smoothing is implemented using filters.

Sidenote: Noise is high-frequency. Smoothing using low-pass filters helps reduce noise.
On the other hand, using gradient operators (i.e. derivatives) will amplify noise.

Linear Filters

Linear filtering is a kind of filtering where the output pixel is obtained by a linear combination of the pixels in the neighborhood of the input pixel. Some common linear filters are discussed below:

Box Filtering (Mean Filtering)

Box filtering replaces each pixel with the average of its neighborhood pixel values.

For a 3x3 neighborhood, the box filter would be: $\frac{1}{9}\begin{bmatrix}1 & 1 & 1\\1 & 1 & 1\\1 & 1 & 1\\\end{bmatrix}$

Mean filtering reduces noise but causes blurring and thereby loss of information such as sharp edges.

Gaussian Filtering

Gaussian filtering uses a weighted average instead of a simple average i.e. it replaces each pixel with a weighted average of its neighborhood pixel values.

More weight is given to the central pixels and the weights decrease as we move away from the center. (Pixels farther than $3\sigma$ from the center have negligible influence).

It is known as the Gaussian filter because the matrix coefficients follow a Gaussian distribution.

Commonly used Gaussian filters:

$\frac{1}{10}\begin{bmatrix}1 & 1 & 1\\1 & 2 & 1\\1 & 1 & 1\\\end{bmatrix}, \frac{1}{16}\begin{bmatrix}1 & 2 & 1\\2 & 4 & 2\\1 & 2 & 1\\\end{bmatrix}$

Note that we divide by the sum of the matrix elements to ensure that it is normalized. (We did the same for the box filter too!).

Gaussian filter is the only filter that is both circularly symmetric and separable.

Separability of the Gaussian Filter

Using the Gaussian filter as is can be computationally expensive.

The Gaussian filter is, however, separable. This means that the filter can be expressed as a product of two 1D vectors (one column vector and one row vector). This allows us to first convolve each row of our image with a 1D filter and then convolve each column of our image with the other 1D filter. This gives the same results but is computationally efficient.

$G(x,y;\sigma)=\frac{1}{2\pi\sigma^2}e^{-\frac{(x^2+y^2)}{2\sigma^2}}$ can be expressed as $(\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{x^2}{2\sigma^2}})(\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{y^2}{2\sigma^2}})$ i.e. $G(x;\sigma)G(y;\sigma)$

The mxn filter requires mxn multiplications and the sum. Separating the filter into two 1D filters only requires m+n multiplications. Ex. a 11x11 filter would require 121 multiplications, whereas running it with two 1D filters would need 11+11=22 multiplications.

Note that increasing the value of $\sigma$ will increase the blurring.

Non-Linear Filters

Median Filtering

In median filtering, each pixel is replaced by the median of its neighboring pixel values. Median filtering is not linear and is therefore not an LSI system.

Median filtering is, however, excellent at noise removal (for salt-and-pepper noise i.e. impulse noise) and doesn't cause much blurring (thereby reducing loss of information such as sharp edges)! When it comes to salt-and-pepper noise, Gaussian filtering will simply blur the noise and won't be able to remove it.

Median filtering is also robust to outliers unlike Gaussian filtering (this is because a single outlier could drastically impact the mean but not the median).

A disadvantage of median filtering (using a rectangular neighborhood) is the damaging of thin lines and sharp corners (corners get rounded). To prevent this, we must choose a different-shaped neighborhood.

Also, it can be computationally expensive if not implemented in an efficient manner. (This is because we have to calculate the median for every set of pixels as the window slides over the image, and to do that, we have to sort every time).

Additionally, the outcome depends on the window size (since we replace a pixel with the median of all the pixel values in the window area).

Bilateral Filtering

Bilateral filter is a non-linear filter. It reduces noise and preserves sharp edges.

To perform bilateral filtering, we replace each pixel with a weighted average of similar and nearby pixel values.

No averaging is done at edges.

The NL-Means (non-local means) filter is an improvement over bilateral filtering.