Introduction

Question 1

What is computer vision?

Answer 1

Computer vision is the study that has as goal to create software that can interpret images and give back information about what the image represents.

Question 2

What is an image mathematically speaking?

Answer 2

An image is a function I(x,y) that gives back the intensity at position (x,y).

I: R² -> R, where R usually is a value in a discrete range e.g., [0, 255].

Question 3

Name at least six uses of computer vision.

Answer 3

Optical Image Recognition (OCR) - Used to read characters from an image
Facial recognition - Used in cameras with smile shutters and to unlock your phone
Object recognition - Detect objects in images, can be used to detect theft in stores
3D modelling - Convert images into 3D models
Motion capture - Project images onto moving entities (Davy Jones in Pirates of the Caribbean)
Structure from motion - Turns a series of 2D images into 3D images
Smart cars - Computer vision is used in car collision detection systems
Sports - Detect who’s first at the finish line
Vision based interaction - Computer vision is used in the Wii controller and in Kinect
Security / Surveillance - Computer vision is used by security cameras to detect thieves
Medical imaging - Computer vision and augmented reality can help surgeons operate

Question 4

Define a color image as a vector-valued function.

Answer 4

I(x,y) = [ r(x,y) g(x,y) b(x,y) ]

Question 5

What is noise in an image mathematically speaking?

Answer 5

Noise is just like an image, a function, η(x,y). An image with noise can be defined as the sum of noise and the original image.

I’(x,y) = I(x,y) + η(x,y)

Question 6

What is salt and pepper noise?

Answer 6

Salt and pepper noise as a function returns black and white pixels at random positions. The noise is sparsely distributed.

Question 7

What is impulse noise?

Answer 7

Impulse noise as a function returns white pixels at random positions.

Question 8

What is Gaussian noise?

Answer 8

Gaussian noise as a function returns intensities that are picked from a normal distribution.

Question 9

What makes computer vision difficult?

Answer 9

Viewpoint - It’s difficult for computer vision algorithms to deal with objects seen from an unfamiliar angle.
Illumination - Light in different levels of brightness and from different angles can complicate the detection of features.
Scale - The distance between the camera and object can make the same object to be of different sizes.
Motion - Moving objects or cameras can complicate matters.
Intra class variation - The object you are looking for may appear in different colors or shapes (there are many car types for example).
Occlusion - There may be objects in front of the objects you are trying to identify.
Background clutter - The object you are looking for might disappear in the background if they look very similar (lack of contrast.
Local ambiguity - A feature may be present in multiple objects in an image.

Question 10

What does sigma determine in the context of Guassian noise?

Answer 10

Sigma is the factor that gets multiplied with the Guassian kernel, a larger sigma value will result in more visible noise in the resulting image.

Question 11

What does sigma determine in the context of a Guassian smoothening filter?

Answer 11

Sigma determines the standard deviation of the kernel, a larger sigma value will result in more blur in the resulting image.

Question 12

Why are non-uniform Gaussian kernels preferred over uniform kernels when smoothening images?

Answer 12

When using a Gaussian kernel, the center pixel and most nearby pixels will contribute the most to the average. This will result in a smoother looking average or blur.

Question 13

Give an example of a Gaussian kernel.

Answer 13

[ 1 2 1
2 4 2 * 1/16
1 2 1 ]

Question 14

What is a linear operator?

Answer 14

An operator is linear if two properties hold:

Additivity: H( f1 + f2 ) = H( f1 ) + H( f2 )
Multiplicative scaling: H( a * f1 ) = a * H( f1 )

Question 15

What’s the difference between cross-correlation (G = H ⊗ F) and convolution (G = H * F)?

Answer 15

Convolution is very similar to cross-correlation, but in convolution the kernel will get flipped by 180 degrees.

Question 16

Would convolution and cross-correlation produce different results when using a box or Gaussian filter?

Answer 16

No, the results will be identical in this case. It does however matter when you’re dealing with derivatives.

Question 17

Name some mathematical properties of convolution.

Answer 17

Linear and shift invariant (filter behaves the same as long as the values are the same, location does not matter)
Commutative: f * g = g * f
Associative: (f * g) * h = f * (g * h)
Identity: f * e = f
Differentiation: d/dx (f * g) = df/dx * g

Question 18

If you have an image that has NxN pixels and a non-separable kernel with a size of WxW, what’s the time complexity of convolution?

Now suppose the kernel is separable, what would the time complexity be?

Answer 18

Non-separable: O(N^2 * W^2)
Separable: O(2 * W * N^2)

Why?

Consider that H is our kernel, which gets split up in a column vector C and row vector R:

H = C * R

Instead of one convolution we could now do two:

G = H * F = (C * R) * F = C * (R * F)

Each convolution has a complexity of W * N * N. Because we do two convolutions, R * F and C * (R * F), the complexity will be:

2 * W * N^2

Question 19

Imagine that you have to convolve an image using a kernel that aligns its top right cell with the top left cell of the image, how does this affect the output image compared to when the center cell of the kernel aligns with the top left cell of the image?

Answer 19

This is known as “full” convolution and will produce an image that is larger than the original.

“same” convolution (center cell first) results in an image of the same size as the original.

“valid” convolution (top left cell first) results in an image that is smaller than the original.

Question 20

When convolving, in order to deal with the boundaries, you might have to add an edge around the image. Name some methods to deal with the boundaries.

Answer 20

Clip filter - make the edges black. [ leaches in black in the resulting image :/ ]
Wrap around - top left pixel is bottom right pixel and so forth. [ even worse :( ]
Copy edge - replicates the adjacent pixels. [ pretty good :) ]
Reflect - mirror the pixels adjacent. [ best method :D ]

Question 21

What does the following image filter do?

[ 0 0 0
0 1 0
0 0 0 ]

Answer 21

It gives back the original image.

Question 22

What does the following image filter do?

[ 0 0 0
0 0 1
0 0 0 ]

Answer 22

It gives back the image, but it is shifted to the left by one pixel.

Question 23

What does the following image filter do?

[ 1 1 1
1 1 1 * 1/9
1 1 1 ]

Answer 23

It gives back a blurred version of the image.

Question 24

What does the following image filter do?

[ 0 0 0 [ 1 1 1
0 2 0 - 1/9 * 1 1 1
0 0 0 ] 1 1 1 ]

Answer 24

It gives back a sharpened version of the image.

image + (image - blurred_image)

Question 25

What non-linear filter could be used to remove salt and pepper noise?

Answer 25

A median filter could be used for this which iterates through the pixels, sorts the pixels around the current pixel and replaces the current pixel in the output image with the median.

Question 26

What are the four causes of edges in images?

Answer 26

Edges come from rapid changes in intensity in the image, the causes are the following four:

Surface normal discontinuity - changes in shape.
Depth discontinuity - for example, contrast between the object and background.
Illumination discontinuity - shadows.
Surface color discontinuity - changes in color.

Question 27

Formula for gradient direction.

Answer 27

Ø = arctan( df/dy / df/dx )

Question 28

Formula for gradient magnitude.

Answer 28

|| ∇f || = sqrt ( (df/dx)^2 + (df/dy)^2 )

Question 29

Define the Sobel operator.

Answer 29

[ -1 0 1 [ 1 2 1

• 2 0 2 * 1/8 0 0 0 * 1/8
• 1 0 1 ] -1 -2 -1 ]Sx Sy

+ Reduces noise the same time as it differentiates.
+ Center pixels contribute more.

Question 30

Define the Prewitt operator.

Answer 30

[ -1 0 1 [ 1 1 1

• 1 0 1 0 0 0
• 1 0 1 ] -1 -1 -1 ]Sx Sy

Question 31

Define Roberts operator.

Answer 31

[ 0 1 [ 1 0
-1 0 ] 0 -1 ]

Sx Sy

Question 32

Define a Laplacian operator.

Answer 32

[ 0 -1 0 [ -1 -1 -1
-1 4 -1 -1 8 -1
0 -1 0 ] -1 -1 -1 ]

Two examples of Laplacian operators.

• Sensitive to noise.
  + Calculates the 2nd derivative in one pass.

Question 33

How does the canny edge operator work?

Answer 33

1. Filter the image using the derivative of a Gaussian.
2. Find the magnitude and orientation of the gradients.
3. Non maximum suppression: Thin the multi-pixel wide ridges down to a single pixel width.
4. Linking and thresholding: Define a low and high threshold, use the high threshold to start an edge and the low threshold to continue them.

Question 34

What is Hough transform used for and on what principle is it built?

Answer 34

Hough transform is used to find lines from a set of edge pixels. It is based on the principle of voting.

Question 35

What does a line in image space correspond to in Hough space?

Answer 35

A line in image space corresponds to a point in Hough space.

Question 36

What does a point in image space correspond to in Hough space?

Answer 36

A point in image space corresponds to a line in Hough space.

y = mx + b => b = -xm + y

Question 37

What is the equation used to represent points from image space in Hough space? Why do we represent lines in this form? What is the result in Hough space?

Answer 37

Hesse normal form:

d = x * cos(Ø) + y * sin(Ø)

d: the perpendicular distance from the line to the origin.
Ø: angle that the perpendicular makes with the x-axis.

This is a way of dealing with infinite slopes, 0 < Ø < π.

The result in Hough space is a sinusoid segment.

Question 38

Define the basic Hough transform algorithm.

Answer 38

1. Intialize the accumulator array H[d, Ø] = 0.
2. For each edge point E(x,y) in the image:
   For Ø = 0 to 180:
   d = x * cos(Ø) - y * sin(Ø)
   H[d, Ø] += 1
3. Find the values (d, Ø) where H[d, Ø] is maximum.
4. The detected line in the image is given by: d = x * cos(Ø) - y * sin(Ø)

Question 39

Define the principle steps of SIFT.

Answer 39

1. Scale space peak selection (find potential features):

Blur the image a bunch of times by applying a Gaussian filter to the image with different but increasing sigma values (sigma determines the variance of the normal distribution in the kernel). The blurred images are stored in a stack and the Difference of Gaussian (DoG) between each two consecutive blurred images (subtract them from each other). DoG is a fast approximation of the NLoG operator (Normalized Laplacian of Guassian).

Extract the extrema by sliding a 3x3x3 window over the DoGs and store the largest value in the window.

2. Key point localization (get rid of the weak extrema):

Remove the extrema that don’t meet a chosen threshold to obtain the actual feature points.

3. Orientation assignment:

Calculate the X and Y gradient using Sobel or a similar method. Once the gradients are calculated, the angle of each pixel in the features can be calculated using: v = arctan( dI/dy / dI/dx ). Each feature can be assigned a principle orientation, by selecting the most frequent angle in the feature.

4. Key point descriptor (create a signature of the feature):

Create signatures of the points by splitting the feature up in four quadrants, create a frequency array of the angles for each quadrant and concatenate the arrays. This big multidimensional is the descriptor that is used in matching.