[CV] 1. Image Processing Basic: Linear Filters

Published in

jun-devpBlog

5 min readNov 9, 2020

Computer Vision (CV) consists of various research areas, such as filters, edge detection, segmentation, feature extraction & matching, object detection, 3D reconstruction and so on.
In this article, and in future, I aim to go through the fundamental ideas of all mentioned topics, but as the first step, we will start with the basics of image processing, namely the filters.

1. What is Filter?

As its name implies, the purpose of filters is to filter out some unnecessary components (in other words, the noise) or to extract some structures underlying the image.

**Figure 1. images with different level of noise (left panel) and extracted structure (edge) from the original image (right panel) from** **[1]**, **[2]**

Out of many types of filter, we will take a look at linear and non-linear filters. More specifically, our focus is on what are they, how they work, why they are beneficial. But before getting into these topics, we first need to know what is noise.

2. Noise

Noise is unwanted and unexpected signals in images. It distorts the original image by introducing a random variation of brightness, illumination or color information into the image.

Commonly known types of noise are as follows: Salt & pepper, Impulse and Gaussian noise.

**Figure 2. original and noise-introduced images. slide credit: [1], [3]**

Salt & pepper noise indicates the random occurrences of black (pepper) and white (salt) pixels across the image, meaning some randomly selected pixels are set as black or white.
In contrast, Impulse noise means the random occurrences of white pixels only.
Lastly and importantly, Gaussian noise is the most commonly observed type of noise. It introduces variations in intensity drawn from a Gaussian distribution. In other words, each pixel intensity in the image is modified by a random variable drawn from Gaussian distribution.

Fig 3 illustrates the effect of Gaussian noise. The lower panel (graphs) shows the pixel color values 𝑓(𝒙, 𝒚) in the red horizontal line in image. By comparing the two pixel-intensity graphs, one can observe the effect of Gaussian noise: The pixel-colour values behave more like a zigzag pattern and they vary around true values.

Figure 3. Illustration of the Gaussian noise. Left panel: original image with its pixel intensities in the red horizontal line. Right panel: image with additive Gaussian noise. slide credit: [1], [2], Martial Hebert

Note that the basic assumption here is that noise is “i.i.d” (independent and identically distributed)

3. Solution to reduce the noise

We want to find a way to reduce the noise in image. In other words, our goal is to reconstruct the given noise-introduced image such that the noise level in image decreases. In order to achieve the goal, two fundamental assumptions are made.

Pixels in the image are expected to be like their neighbours (having similar pixel intensity)
Noise is independent from pixel to pixel (i.i.d)

3.1 Moving Average Filter

**Figure 4. Illustration of the moving average, from [1], [3]**

Fig 4 presents how the moving average in 2D image works. Let 𝐅 denotes the given image with two noise pixels, which are marked with yellow box (black pixel in the center and white pixel in the low-left corner), and 𝐺 indicates the filtered image. The flow of moving average in Fig 4 is from left to right and from top to bottom panel.

What it does in Fig 4 is that compute the mean of 9-pixel intensities in the red box (window) of 𝐅 then place it in 𝐺. Mathematically, this process can be represented as follows:

where 2𝐤+1 denotes the window size in image 𝐅. By doing so, the isolated noise pixels (in yellow boxes) and hard borders (orange windows) in (4) of Fig 4 get smooth out.

Note that averaging yields the smoothing! We will see why this smoothing is important in filtering in the next chapter.

The topic of this article is “FILTER”, and thus, one might ask:

What is the filter of moving average in Fig 4 and Eq 1?

To answer this question, we need to know the correlation and convolution.

3.2 Correlation

Let’s start with the correlation. The mathematical definition of correlation is as follows:

**Figure 5. Definition and illustration of the correlation, from [1], [2]**

The correlation replaces each pixel of image 𝐅 by a weighted sum of its neighbours, and such weights are determined by the filter H, which is also named “kernel” or “mask”.

Doesn’t the equation in Fig 5 ring any bell?

By setting H[u,v] for all u and v as 1/(2k+1)², we obtain the Eq 1 of moving average. Therefore, we found the filter H, which is called the box filter, for moving average!

Above image illustrates the moving average with box filter when k = 1.

3.3 Convolution

Convolution is similar to the correlation, except for only one but significant difference. It flips the filter in both dimensions (right to left and bottom to top in case of 2D filter). And then it applies the correlation. In short, convolution is the combination of the filter flipping and correlation. Fig 6 illustrates this.

**Figure 6. Definition and illustration of the convolution, from [1], [2]**

3.3.1 Properties of Convolution

Here, I note some important and commonly used properties of convolution. Please take a closer look into each property and try to prove them yourself.

f ⭑ (k × g) = k × (f ⭑ g)
f ⭑ (g₁+g₂) = f ⭑ g₁+f ⭑g₂ : linearity
H[-u, -v] = H[u, v]: when flip(H) = H , then correlation = convolution by definition.
f ⭑ (k ⭑ g) = (f ⭑ k) ⭑ g : Associative
f ⭑ g = g⭑ f : Commutativity

And there are three more properties: Differentiation, Separability of 2D convolution, and most importantly the relationship between convolution and Fourier transform. We will take a deeper look into them when we learn the Gaussian filter in the next chapter.

4. Conclusion

We have gone through the definition of terms: filter and noise, the idea of very basic filter: moving average. Also the correlation and convolution with their properties. Base on them, the next chapter will deal with more advanced concepts: what is Gaussian smoothing (filtering), what is the effect of convolution in the frequency domain and what needs to be considered while filtering.