4. Image Processing

Question 1

What is image processing / filtering? Why is it done?

Answer 1

It is converting one image into a different one according to some algorithm

• Reduce noise (smartphones always have noise)
• Fill-in missing information (like in bayer grid using demosaicing)
• extracting image features (edges, corners)

Question 2

What are images mathematically?

Answer 2

It is a function that converts (a, b) (c, d) -> [0, m]

Where a, b, c, d are dimensions of the image (start, end of row/column) and m is the max value of the result (like 0-255 in grayscale)

[0, m]3 for color images (r,g,b)

Question 3

What are the properties of linear filters?

Answer 3

• homogenety: if you amplify image and then apply the filter, it will be the same like if you first apply the filter and then amplify.
• additivity: applying a filter to an image computes like a sum of two images is the same like applying the filter to each separately and then summing them
• superposition: combination of the two

Question 4

How can linear filters be done using vector-matrix operations?

Answer 4

We first convert an image-matrix into one vector of all values (1x200000) and then multiplying it with a matrix 2000000x2000000.
This is very expensive for just a simple linear filter
Problems with shifting image for a few pixels to one side and then performing the filter will result in a different image compared to filtering and then shifting. (shift-invariance)

Convolution is better

Question 5

What is convolution? How is it performed?

Answer 5

It is a way to perform a linear filter on the image.
We have a filter (kernel). We perform a sliding window over the whole image and multiply each number in the image with the OPOSITE filter value.

f*g

Question 6

What are the properties of convolution?

Answer 6

• can be represented as matrix-vector product
• linear
• associative
• commutative
• shift-invariant: if we shift pixels, the convoluted image will be the same

Question 7

What is correlation?

Answer 7

It is similar to convolution but we do not mirror the filter (we multiply the pixels with the kernel on the EXACT position)

Question 8

What are the properties of noise-pixel? What could be the cause of those noise-pixels?

Answer 8

A single pixel that is the noise is an outlier of its neighbours (has much lower or higher intensity).

• Light fluctuations (more photons go to one sensor-cell compared to other ones), sensor noise (sending voltage levels around), quantization effects (continuous object is quantized on a finite grid, with a finite (integer) intensity)…

Question 9

How to deal with noise using linear filters?

Answer 9

• Average filter: we use a 3x3 filter of 1/9 values (sum to 1) and the resulting pixel intensity is the average of its neighbours. This is also called a box filter.
• Gaussian filter: weighted average -> weights nearby pixels more than distant ones

Question 10

What is a box filter?

Answer 10

It is a linear filter that calculates the pixel intensity as an average of its neighbors. It usually has the box-like looking artifacts.

Question 11

What is a gaussian filter?

Answer 11

Essentially it is a linear filter that weights nearby pixels more than the distant ones, according to the gaussian distribution. We basically take one gaussian distribution for x-axis and one gaussian distribution for y-axis.

This technique removes the box-artifacts from the box filter and makes the filter more smooth.

Question 12

How to make box filter and gaussian filter more efficient?

Answer 12

Since they are separable (can be represented as a convolution of two 1D filters) -> gaussian as a horizontal+vertical guassian 1D filter, and box filter as average of vertical+horizontal.

This of it as passing through the image two times, ones for all verticals and once for all horizontal pixels.

This way, instead of having 9 parameters (for 3x3 kernel), we have only 6.

Question 13

How to deal with boundaries in convolution?

Answer 13

Since convolution reduces the image size (for 3x3 filter, it reduces the size by 2 pixels), we need to add some padding to the original image before the convolution. How to choose the padding?

• Leave them as 0 (black pixels): this introduces dark edges in the blurred image
• Wrap: pretend that the image is infinite and the next pixel goes around to the other side. n pixel becomes 1, n+1 becomes 2…
• Clamp: just extend the last pixel how much we need
• Mirror: similar to wrap, just n becomes n-1, n+1 becomes n-2…

Wrap method have a higher chance of introducing artifacts, but deciding is a matter of use cases and what images we have

Question 14

How to remove noise but while preserving edges?

Answer 14

Using non-linear filter called median filter. Similar to average but instead of average, we take the median of neighbors (sort and take the middle). This preserves high jumps between the edge but kinda blurs the image.

Question 15

What are morphological filters?

Answer 15

They are the filters that usually only apply to binary images. There are two types:
- Dilation: If there is at least one 1 in the image part of the filter, it results in 1. Has the foreground-expanding feature
- Erosion: Results in 1 only if all image pixels of the kernel are 1. If there is at least one 0, it results in 0.

This can be generalized for grayscale images

Question 16

What are image pyramids? What is the general process?

Answer 16

It is representing one image at multiple scales (resolutions). It essentially creates multiple versions of the image with the lower resolutions so that there is a smaller search space to find an object. When it is found on the smaller image, then this info is propagated onto the bigger images and the object is pinpointed on the original image.

Question 17

What are gaussian pyramids?

Answer 17

It is a pyramid where first we apply the gaussian filter and then do downsampling (take every 2nd pixel both row-wise and column-wise)

Question 18

Why do we have to apply gaussian filter before downsampling in gaussian pyramid?

Answer 18

Because high frequencies (sharp edges, sharp color transitions) can’t be represented anymore.

We can experience aliasing: smaller objects might appear bigger in the downsampled image.

Question 19

What is aliasing in the context of pyramids?

Answer 19

They appear when we don’t do any gaussian filtering before the downsampling in gaussian pyramids. This might cause that some small objects appear bigger in the low-resolution images (downsampled images). Also, it might introduce some patterns that badly represent the image.

Question 20

What is edge detection and why do we need it? What are edges?

Answer 20

It is finding edges of objects in the image. Edges are basically lines that represent the object. We need it because humans can recognize objects only with their drawings/edges, so we can assume we can also find objects easier using their edges in image processing.

Edges are fast changes of intensity of pixels in the image (big color contrast).

Question 21

What are the goals of edge detection?

Answer 21

• Good detection: the result corresponds to the edge of the object, not some noise
• Good localization: Edge is near the true edge of the object
• Single response: One line per edge

Question 22

How to detect an edge in 1D? A line of the image?

Answer 22

The idea is that the edges correspond to fast changes (derivative is large)

1. Apply gaussian smoothing
2. Calculate the derivative of this curve
3. Find local optimas of the curve but above some preset threshold (don’t care about low changes)

Question 23

How to compute derivative of the 1D image-lines for edge detection?

Answer 23

• We can compute the 1st derivative and find local optimums. This can be implemented as linear filter 1 -1 but the derivative will be computed in between the cells (even number of kernel-cells)
• It can also be implemented using 1/2 * 1 0 -1 filter and it is better because we don’t have to shift the image, derivative is calculated at the center of the pixels
• We can calculate the 2nd derivative and find zero crossings (not just where the derivative is 0, but it crosses the y=0 line)

Question 24

How can we simplify edge detection when having a gaussian smoothing and an edge-detection filtering?

Answer 24

By applying the edge-detection filter to the gaussian filter first, and then applying this to the image. It reduces the computation. This world because of the associative attribute of convolution.

Question 25

Why the 1st derivative might be problematic in the real-world images?

Answer 25

Because small variations in pixel intensity will lead to big derivatives. Problem: where is the threshold of the 1st derivative?

Question 26

How to detect either vertical of horizontal edges in 2D images?

Answer 26

Similarly to 1D. We compute the partial derivatives in both x and y direction. It is approximated using linear filters: x-direction: 1 0 -1 1/6 * 1 0 -1 1 0 -1 y-direction: 1 1 1 1/6 * 0 0 0 -1 -1 -1 This combines the edge detection with smoothing (box-filter) but there is a problem of box filter: we get box artifacts in our image (bad smoothing) We can use the Sobel filter (use gaussian smoothing with edge detection). Idea is gaussian filter: pixels closer influence more than the further away ones. x-direction: 1 0 -1 1/8 * 2 0 -2 1 0 -1 y-direction: 1 2 1 1/8 * 0 0 0 -1 -2 -1

Question 27

What filter was used in this image?

Answer 27

x-direction 2D edge detection, because we detect differences in x direction (we detect when white is left and black is right, and vice versa). That means we get vertical edges, but horizontal ones are bad.

Question 28

How can we detect edges in 2D images? Explain the whole Canny process

Answer 28

1. We have an image and we apply gaussian filter to reduce the noise. 2. Compute partial derivatives of the image (x and y direction) using Sobel filters. With the Sobel filters, we also have the gaussian filtering. This results in two images: horizontal and vertical edge detection 3. Calculate the gradient magnitude (combining the Ix and Iy from the step 2 into one image). This results in an image with edge detection. 4. We can apply some thresholding to only have high gradient magnitudes. Consider the hysteresis to have edges connect. 5. Thinning: performing the non-maximum suppression. This process improves the localization: only takes pixels which are the local maximums along the gradient direction. It makes the edges thin

Question 29

What are Sobel filters?

Answer 29

They are convolutional filters that approximate partial derivatives. They also perform gaussian smoothing in opposite direction of the edge detection. They are used in edge detection and x-direction filter detects vertical edges.

Question 29

Under what assumptions is Canny the best algorithm for edge detection?

Answer 29

- We only use linear filters - The noise is iid (independent identically distributed)

Question 30

What is hysteresis?

Answer 30

When doing edge detection and we perform thresholding, we will see that edges are dashed lines, they stop and continue etc. This is due to high threshold but if we put the threshold down, we might introduce fake edges / noise. To fix this, we can use hysteresis. There are two thresholds. 1. is the high threshold that should detect true edges only. The second is a bit lower and pixels that pass the second but not the first one are kept only if some noughboring pixels passed the 1. threshold. Do this iteratively

Question 31

What is non-maximum suppression?

Answer 31

When we have computed the magnitudes of the gradient and we performed some thresholding (optionally), multiple pixels along the edge can pass the threshold (thick edge). To make this edge thin (perform better localization), we do the non-maximum suppression. It basically checks if pixel is local maximum along the gradient direction. For each pixel, the largest gradient is calculated. Pixels p and r are taken along the direction of the gradient that intersect the next row or the next column (pixel row/column) and we check if the selected pixel is bigger than both of them. If it is, we keep it and if not, we remove it. The p and r are approximated using linear interpolation (averaging 2 pixels that p/r are in between)

Question 32

How does a 1st derivative linear filter look like and how does the 2nd in 1D?

Answer 32

1 -1 1 -2 1

Question 33

How to do edge detection using second derivative? How about smoothing?

Answer 33

Idea is to find zero crossings of the second derivative. The second derivative can be approximated using linear filter 1 -2 1. In 2D, this is 0 1 0 1 -4 1 0 1 0 or 1 1 1 1 -8 1 1 1 1 To perform second derivative with gaussian smoothing, we use Laplacian of Gaussian (LoG) which is just a convolution of gaussian filter and laplacian filter. The LoG in 2D has a mexian hat shape and can be approximated using DoG (difference of gaussians)

Question 34

How can LoG be approximated?

Answer 34

Laplacian of Gaussian can be approximated using DoG (difference of gaussians). Ususlly signa1 = 1.6 sigma2 and when we subtract the functions, we get the LoG.

Question 35

Explain the Laplacian pyramid.

Answer 35

1. We compute the Gaussian pyramid. Then, each layer of gaussian pyramid we expand (each pixels is copied 4 times). This means that we have a high resolution image of the information from the lower resolution. To get the Laplacian pyramid, we have to subtract the gaussian layer with the expanded Gi+1 layer. This will result in Li layer of laplacian pyramid. What this represents is what information is lost when we went from Gi to Gi+1. At the lower levels of the pyramid, the high-frequency information is lost (represented in the laplacian pyramid) and as we move upwards, we get lower and lower frequency information (in laplacian pyramid). We can reconstruct the original image using the laplacian pyramid since the top-most image is the copy of Gn = Ln. We can reverse the process.

Question 36

What is the application of the Laplacian pyramid?

Answer 36

Image sharpening. For example, if we want to make the edges crisper, we can multiply some of the laplacian layers with some constant (like 1.1) and reconstruct the image. This should make those details more visible.