—— SOLUTIONS ——
January 2017
1. Compulsory Question
a. Give a brief definition of each of the following terms. i. computer vision
ii. down-sampling iii. transduction
7CCSMCVI
Answer
i) computer vision = extracting information about the world from im-
ages.
iii) down-sampling = reducing the sampling rate, or resolution, of an image
(iv) transduction = the transformation of one form of energy to an- other
Marking scheme
2 marks for each correct definition.
[6 marks]
Page 2
SEE NEXT PAGE
January 2017 7CCSMCVI b. The array below shows the intensity values in a 3-by-3 pixel greyscale
image.
Filtered image
Marking scheme
6 12 58
—— SOLUTIONS ——
=
5 11 21
I=1 6 9
398
Calculate the 2-by-2 pixel image that would result if this image was
convolved with a 2-by-2 pixel box mask (or mean filter).
Answer
A 2-by-2 pixel box mask =
1/4 1/4
(5+11+1+6)/4 (11+21+6+9)/4
(1+6+3+9)/4 (6+9+9+8)/4
23/4 47/4 19/4 32/4
5.75 11.75 4.75 8
=
Assuming output, like original image, should also be in integer format:
=
[5 marks]
Filtered image =
1/4 1/4
2 marks for knowing a correctly normalised box mask. 2 marks for correctly applying convolution to the image. 1 mark for realising that image format is integer and result should be rounded.
Page 3
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI
c. Define a MATLAB function B = binarize(I, t) that will convert an image, I, to a binary image, B, by applying a threshold of t.
Answer
Marking scheme 4 marks.
d. The binary image that results from applying a threshold of 8 to image I, as defined in question 1.b, is:
011
B = 0 0 1
010
Write down the new binary image that results from performing dilation
on B, assuming each pixel has 4 neighbours (horizontal and vertical). [4 marks]
Answer
Marking scheme 4 marks.
111
0 1 1
111
[4 marks]
function B = binarize(I, t)
B=I;
B(B>t)=1;
B(B<=t);
Page 4
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI e. Describe briefly in words, or using pseudo-code, each step required to
create:
i. a Gaussian image pyramid,
ii. a Laplacian image pyramid.
Answer (i)
• For each level in the pyramid
convolve current image with Gaussian mask subsample convolved image (this is pyramid image)
Marking scheme
3 marks. (ii)
[6 marks]
• For each level in the pyramid
convolve current image with Gaussian mask
subtract the smoothed image from the previous image (this is
pyramid image)
subsample convolved image
Marking scheme 3 marks.
Page 5
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI 2. The arrays below show the values of the red, green and blue pixels in a
Bayer masked image.
R=G=B=
a. Calculate the RGB values for the pixel at coordinates (2,2) in the demosaiced image using bi-linear interpolation.
[4 marks]
Answer (a)
R(2,2)= R(1,1)+R(3,1)+R(1,3)+R(3,3) = 0.2+0.3+0.4+0.3 =0.3 44
G(2,2)= G(2,1)+G(1,2)+G(3,2)+G(2,3) = 0.7+0.1+0.6+0.8 =0.55 44
B(2,2)=0.2 as given. Marking scheme
4 marks.
0.2
0.3
0.4
0.3
0.7
0.6
0.1
0.6
0.8
0.9
0.4
0.1
0.2
0.3
0.4
0.6
Page 6
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI
b. Calculate the RGB values for the pixel at coordinates (2,2) in the de- mosaiced image using edge-directed interpolation. Assume that pixels at coordinates (1,1), (1,3), and (3,1) all have green values of 0.5.
[5 marks] At(2,2)∆H=∥0.6−0.1∥=0.5,∆V =∥0.7−0.8∥=0.1
Answer Therefore,
G(2,2)= G(2,1)+G(2,3) = 0.7+0.8 =0.75 22
At(3,3)∆H=∥0.8−0.9∥=0.1,∆V =∥0.6−0.1∥=0.5 Therefore,
G(3,3)= G(2,3)+G(4,3) = 0.8+0.9 =0.85 22
R(2, 2) = G(2, 2) × 1 R(1, 1) + R(3, 1) + R(1, 3) + R(3, 3) 4 G(1,1) G(3,1) G(1,3) G(3,3)
1 0.2 0.3 0.4 0.3 R(2,2)=0.75×4 0.5+0.5+0.5+0.85 =0.4037
B(2,2)=0.2 as given. Marking scheme
5 marks.
Page 7
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI
c. The pinhole camera model of image formation relates the coordinates of a 3D point P with coordinates (X,Y,Z) relative to the camera refer- ence frame to the coordinates of its image p=(x,y,z) via the following equation:
fXfY (x,y,z)= Z,Z,f
Given that two identical cameras are mounted so as to have coplanar image planes, such that one camera (the right one) is displaced dis- tance B along the x-axis of the other (the left one), derive an equation for the depth of a 3D point P visible in both cameras.
Answer
For left camera:
For right camera:
fXL fYL (xL,yL)= Z ,Z
f(X −B) fY (xR,yR)= L ,L
[6 marks]
(xR,yR)= Z ,Z RR
LL fXR fYR
Because the x-axes of the camera are collinear, yL = yR, also be- cause the image planes are coplanar ZL = ZR. Furthermore, the X-coordinates of the 3D point in the right camera is related to its position in the left camera by: XR = XL − B.
Hence,
Subtracting x-coordinates:
ZZ LL
xL − xR = fXL − f(XL − B) ZL ZL
Hence,
Marking scheme 6 marks.
ZL= fB xL − xR
(=ZR)
Page 8
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI
d. Describe five constraints that might be applied in trying to determine the locations of the points in the left and right image that correspond to the same point in 3D space.
[10 marks]
Answer
epipolar constraint (corresponding points lie along the epipolar line)
maximum disparity (extent of search reduced by knowledge of baseline and minimum depth)
continuity (disparity varies smoothly assuming continuous surfaces) uniqueness (one-to-one matches assuming surfaces are approximately perpendicular to camera and no occlusion)
ordering (points occur in same order in each image assuming no oc- clusion)
[similarity (locations should have similar features)]
Marking scheme
2 marks for each correct definition.
Page 9
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017
3. a. The array below shows a Laplacian mask, L.
−1 −1 −1
L=−1 8 −1
7CCSMCVI
−1 −1 −1
Write down a mathematical expression describing the effect of con-
volving an image I with L. Answer
I′ =I∗L≈−δ2I +δ2I δx2 δy2
Marking scheme 2 marks.
[2 marks]
b. Write down the mask that approximates the following directional deriva- tive: − δ2
δy2 Answer
[2 marks]
−1 δ2 −δy2 ≈ 2
−1 Marking scheme
2 marks.
Page 10
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI
c. Use the following formula for a 2D Gaussian to calculate a 3-by-3 pixel numerical approximation to a Gaussian with standard deviation of 0.5 pixels, rounding values to two decimal places.
Answer Gaussian mask
Answer
LoG = −0.12 4.72 −0.12
−0.74 −0.12 −0.74 Marking scheme
1 (x2 +y2) G(x, y) = 2πσ2 exp − 2σ2
0.01 0.09 0.01
= 0.09 0.64 0.09
0.01 0.09 0.01
[3 marks]
Marking scheme
1 mark each for the 3 different values.
d. Using the Laplacian defined in question 3.a and the Gaussian calculated in answer to question 3.c calculate a 3-by-3 pixel Laplacian of Gaussian (or LoG) mask.
[5 marks]
−0.74 −0.12 −0.74
2 marks for knowing that L and G need to be convolved together. 1 mark each for the 3 different values.
Page 11
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI
e. What advantage does a LoG mask have over a Laplacian for edge
detection?
[2 marks]
Answer
The Laplacian is sensitive to noise as well as other intensity-level dis- continuities.
The Gaussian is a smoothing mask that suppress noise.
The combination of the two produces a mask that is sensitive to intensity-level discontinuities that are image features rather than noise.
Marking scheme 2 marks.
f. An alternative method of performing edge detection is to simulate the responses of orientation tuned neurons in primary visual cortex (V1). Name the mathematical function that is used to model the receptive fields of cortical simple cells, and write down the equation for this function.
[4 marks]
Answer
The Gabor function.
x′2+γ2y′2
Gabor(x, y) = exp − 2σ2 cos(2πx′f + ψ)
Marking scheme
2 marks for name. 2 marks for equation.
Page 12
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI g. Describe how the responses of V1 simple cells can be modelled using
convolution.
[4 marks]
Answer
Convolving the image with a Gabor mask will simulate the response
of all simple cells selective for the same parameters across all hyper- columns.
Repeating the convolution with Gabor masks with different parameters (e.g. orientation, spatial frequency, phase, aspect ratio) will simulate the responses of all different types of V1 simple cell.
Marking scheme 4 marks.
Page 13
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI h. Describe how the responses of V1 complex cells could be modelled
using convolution.
[3 marks]
Answer
A complex cell can be modelled by combining the outputs of two or more simple cells.
For example, the response from a quadrature pair of Gabor functions (two Gabors with a phase difference of π/2) can be used as input to a model of a complex cell. These inputs need to be combined by taking the square-root of the sum of the squares of the two inputs. Alternatively, the half-wave rectified response from four Gabor func- tions differing in phase by π/2 can be used as input to a model of a complex cell. These inputs are combined by squaring and taking the sum.
Hence, complex cell responses can be modelled by performing mul- tiple convolutions with different Gabor masks to simulate simple cell responses (as described in the answer to the previous question), and subsequently combining (as described above) those responses for Ga- bor masks with identical parameters except with different phases.
Marking scheme 3 marks.
Page 14
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI 4. a. Briefly describe the role of mid-level vision.
[1 mark]
Answer
To group together image elements that belong together, and to seg- ment them from all other image elements.
Marking scheme 1 mark.
b. Below are four simple images. For each image identify the “Gestalt Law” that accounts for the observed grouping of the image elements.
i. ii. iii.
iv.
Answer
(i) closure
(ii) proximity
(iii) similarity
(iv) common region
Marking scheme
2 marks for each correct answer.
[8 marks]
Page 15
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI c. One method of image segmentation is region growing. Write pseudo-
code for the region growing algorithm.
Answer
1. While not all pixels have been assigned a region label
[5 marks]
2. Choose an unlabelled pixel at random
3. Assign chosen pixel the next unused region label
4. For all neighbouring pixels which haven’t been assigned a label
4.1 Calculate similarity to chosen pixel
4.2 For each pixel within the similarity threshold
4.2.1 Give that pixel the same region label as the chosen pixel
4.2.2 Make that pixel the chosen pixel and repeat from step 4
5. Repeat from step 1
Marking scheme 5 marks.
Page 16
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI d. The array below shows 3 element long feature vectors for each pixel in
a 2-by-3 pixel image, IF .
(20, 10, 5) (10, 20, 15)
I = (15,5,5) (5,5,20)
F (15, 15, 15) (20, 15, 10)
Apply the region growing algorithm to image IF in order to assign each pixel to a region. Assume that (i) the method used to assess similarity is the sum of absolute differences (SAD), (ii) the criterion for deciding if elements are similar is that the SAD is less than 12, (iii) the seed pixel is the top-left corner, (iv) pixels have horizontal, vertical and diagonal neighbours.
[6 marks]
Answer
Label top-left pixel 1. Calculate SAD values for pixels neighbouring the top-left pixel:
(20,10,5) : 1 30 → (10,20,15)
10 ↓ 35 ↘
(15,5,5) : 1 (5,5,20)
(15, 15, 15) (20, 15, 10)
Calculate SAD values to unlabelled pixels from the middle-left pixel:
(20, 10, 5) : 1 (10, 20, 15)
↗ 30
(15,5,5) : 1 25 → (5,5,20)
20 ↓ ↘ 20
(15, 15, 15) (20, 15, 10)
Page 17
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI
Region 1 cannot grow further. Choose another seed pixel: top-right:
1 (10,20,15) : 2
25 ↓
1 (5,5,20)
(15, 15, 15) (20, 15, 10)
Region 2 cannot grow further. Choose another seed pixel: bottom-left:
12
1 (5,5,20)
25 ↗
(15,15,15) : 3 10 → (20,15,10) : 3
Calculate SAD values to unlabelled pixels from right-bottom-right pixel:
11
1 (5,5,20)
35 ↑
(15,15,15) : 3 (20,15,10) : 3
Region 3 cannot grow further. Last pixel has no unlabelled neighbours.
12
So final region labels: 1 4
Marking scheme 6 marks.
33
Page 18
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI
e. An alternative method of image segmentation is Normalised Cuts. Write pseudo-code for the Normalised Cuts algorithm for image seg- mentation.
[5 marks]
Answer
1. Form a graph such that each vertex represents an image element
and each edge, epq represents the similarity between the connected elements (p and q)
2. Partition the graph into two sets of vertices A and B
3. Calculate:
Where:
Ncut(A,B) = cut(A,B) + assoc(A, V )
cut(A, B) = p∈A,q∈B
cut(A,B) assoc(B, V )
epq epq
assoc(A, V ) = p∈A,q∈V
4. Repeat from step 2 for every possible combination of nodes in A and B
5. Cut the edges between the sets A and B for which Ncut(A,B) is minimum
6. Repeat from step 2 for all subgraphs until minimum value of Ncut(A,B) exceeds a threshold for each subgraph or maximum num- ber of segments have been reached.
Marking scheme 5 marks.
Page 19
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI
5. a. Briefly describe the methodology used in correlation-based and feature- based methods of solving the stereo correspondence problem.
[4 marks]
Answer
Correlation-based methods attempt to establish a correspondence by
matching image intensities between windows of pixels extracted from both images.
Feature-based methods attempt to establish a correspondence by match- ing image descriptors extracted from around a sparse sets of image locations (usually corners) in each image .
Marking scheme
2 marks for correct description.
Page 20
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI b. The two arrays below show the intensity values for each pixel in a
stereo pair of 5-by-3 pixel images.
Ileft = Iright =
Calculate the similarity of the pixel at coordinates (2,2) in Ileft, to locations in Iright, and hence, calculate the disparity at that point. Assume that (i) a 3-by-3 pixel window is used, (ii) similarity is measured using the Sum of Absolute Differences (SAD), (iii) that corresponding points will occur along corresponding scan lines (i.e., on the same row in both images), (iv) disparity is calculated as the translation from right to left.
40
60
40
20
50
10
50
80
80
30
70
10
70
60
90
20
70
70
20
50
30
20
50
10
50
50
70
40
80
70
Answer SAD =
Hence, best match is at location (3,2) in the right image. Disparity is left-right = (2,2)-(3,2) = (-1,0).
Marking scheme 4 marks.
[4 marks]
310
250
180
290
290
Page 21
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI c. Write down the equation that defines the measure R used by the Harris
corner detector. Answer
[4 marks]
R = I x2 I y2 − ( I x I y ) 2 − k I x2 + I y2 2
Marking scheme 4 marks.
Page 22
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI d. The two arrays below show the derivatives of the image intensities in
the x and y directions for a small 3-by-3 pixel image.
Ix = Iy =
Calculate the measure R of the Harris corner detector at each pixel, assuming (i) a value of k=0.05, (ii) that products of derivatives are summed over an equally weighted, 3-by-3 pixel, window around each pixel, padding with zeros when necessary.
1
0
−2
0
−1
0
0
−3
1
2
1
−3
0
0
0
0
−2
1
Answer
I x2 =
Hence,
Ix2 = Iy2 = IxIy =
[4 marks]
1
0
4
0
1
0
0
9
1
4
1
9
0
0
0
0
4
1
2
0
6
0
0
0
0
6
1
2
6
5
11
16
15
10
11
11
5
14
10
9
19
15
4
5
5
2
8
6
8
15
13
6
7
7
I y2 = I x I y = R = I x2 I y2 − ( I x I y ) 2 − k I x2 + I y2 2
3.55
0
2.75
15.00
17.75
11.00
−5.80
−6.80
−6.80
R=
Marking scheme 4 marks.
Page 23
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI
e. For the Harris corner detector, describe what type of image feature will give rise to the following values of R.
(i) R ≈ 0
(ii) R < 0
(iii) R > 0.
Answer
(i) R ≈ 0 occurs where intensity values are unchanging
(ii) R < 0 occurs at edges (iii) R > 0 occurs at corners.
Marking scheme
2 for each correct answer.
[6 marks]
f. Briefly explain what role the Harris corner detector might play in solving the stereo correspondence problem.
[3 marks]
Answer
The Harris corner detector can be used to locate interest points in both
images which will be matched, i.e., it can be used as a detector in a feature-based method of solving the stereo correspondence problem.
Marking scheme 3 marks.
Page 24
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI
6. a. A simple object recognition system encodes objects using 4-element feature vectors. Four objects from two different classes (A and B) are encoded as follows:
i. a nearest mean classifier, Answer
Object Class 1 A 2 A 3 B 4 B
Feature Vector (2, 2, 0, 1) (3, 3, 1, 1) (1, 2, 3, 2) (2, 1, 3, 0)
A new object, of unknown class, has a feature vector (1, 1, 1, 1). Using Euclidean distance as the similarity measure, determine the classifica- tion of the new object using:
Prototype of class B = 1+2, 2+1, 3+3, 2+0, = (1.5,1.5,3,1) 2222
Distance of new object from prototypes: FromprototypeofclassA:(1−2.5)2 +(1−2.5)2 +(1−0.5)2 +(1−1)2 = 2.18
FromprototypeofclassB:(1−1.5)2 +(1−1.5)2 +(1−3)2 +(1−1)2 = 2.12
Hence, new object is class B.
Marking scheme 5 marks.
[5 marks] Prototype of class A = 2+3, 2+3, 0+1, 1+1 = (2.5,2.5,0.5,1)
2222
Page 25
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017
ii. a nearest neighbour classifier,
7CCSMCVI
[5 marks]
Distance to (2,2,2,2)
Answer
Distance of new object
from exemplars:
Obj.
1
2
3
Class
Features
(1−2)2 +(1−2)2 +(1−0)2 +(1−1)2 = 1.73
(1−3)2 +(1−3)2 +(1−1)2 +(1−1)2 = 2.83
(1−1)2 +(1−2)2 +(1−3)2 +(1−2)2 = 2.45
(1−2)2 +(1−1)2 +(1−3)2 +(1−0)2 = 2.45 object 1.
5 marks.
iii. a k-nearest neighbour classifier, with k=3.
[4 marks]
Answer
The three closest exemplars are 1, 3, and 4.
Object 1 is in class A;
Objects 2 and 3 are in class B.
The majority are class B, so the new object is classified as B.
Marking scheme 4 marks.
4 The
A (2,3,0,1)
A (3,3,1,1)
B (1,2,3,2)
B (2,1,3,0)
closest exemplar is
Since object 1 is of class A, the new object is also class A.
Marking scheme
Page 26
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI
b. Describe briefly in words, or using pseudo-code, each step required to train a bag-of-words object recognition system, and then apply it to classifying a new image.
[6 marks]
Answer Training:
• Extract local feature descriptors around all chosen interest points in all training images.
• Apply k-means clustering to feature descriptors in order to generate a codeword dictionary.
• Remove codewords from dictionary that occur in most training im- ages.
Classifying:
• Encode new image using a histogram showing the frequency of appearance of each codeword in that image.
• Compare histogram to those generated for each training image to find best match.
Marking scheme 6 marks.
Page 27
SEE NEXT PAGE
—— SOLUTIONS ——
January 2017 7CCSMCVI
c. In a simple bag-of-words object recognition system classes are repre- sented by histograms showing the number of occurrences of 4 “code- words”. The number of occurrences of the codewords in two training images are given below:
ClassA = (2, 3.5, 0.5, 2)
ClassB = (0.5, 0.75, 3.5, 1)
A new image is encoded as follows:
New = (2, 1, 2, 1)
Determine the training image that best matches the new image by finding the cosine of the angle between the codeword vectors.
[5 marks]
(i.e., the normalised cross-
Answer
Similarity = cos(θ) = √ i √
A(i)N(i)
i A(i)2 i N(i)2
correlation).
Similarity between New and ClassA is:
(2×2)+(3.5×1)+(0.5×2)+(2×1)
√22 +3.52 +0.52 +22√22 +12 +22 +12 =0.733
Similarity between New and ClassB is:
(0.5×2)+(0.75×1)+(3.5×2)+(1×1)
√0.52 +0.752 +3.52 +12√22 +12 +22 +12 =0.822
Hence, the new image is most similar to Class B. Marking scheme
5 marks.
Page 28
FINAL PAGE