January 2019
1. Compulsory Question
a. Give a brief definition of each of the following terms. i. hyper-column
ii. inpainting
7CCSMCVI
[4 marks]
Answer
i) A hyper-column = a region of primary visual cortex (V1) that con-
tains neurons covering the full range of RF types for a single spatial location
ii) inpainting = the filling-in of missing or corrupted parts of an image
Marking scheme
2 marks for each correct definition.
b. Below are shown a convolution mask, H and an image I. 011 0121
H=1 1 0 I=1 2 0 0
011 1011
What is the result of the convolution of mask H with image I? The
result should be an image that is the same size as I. Answer
2651
4 4 4 5
[4 marks]
2441
Marking scheme
4 marks. Partial marks are possible for partially correct answers.
Page 2
SEE NEXT PAGE
—— SOLUTIONS ——
January 2019 7CCSMCVI
c. In order to locate green regions of the image it has been decided to model the response properties of a green on/red off (G+/R-) colour- opponent retinal ganglion cell. A simple difference of Gaussians model is to be used. Write a MATLAB function R = GonRoff(I) that will calculate the response of a G+/R- cell at all locations in the image I. Assume I is a colour image in RGB format and that you can call a function g=gaussian(sigma,d) that returns a d-by-d pixel Gaussian filter with standard deviation sigma. Use a Gaussian with standard deviation 2 for the centre, and a Gaussian with standard deviation 3 for the surround.
Answer
function R = GonRoff(I)
onFilter=gaussian(2,10);
offFilter=gaussian(3,15);
R=conv2(I(:,:,2),onFilter,’same’)…
-conv2(I(:,:,1),offFilter,’same’);
Marking scheme
[5 marks]
1 marks for knowing how to access red and green channels of image, 2 marks for knowing that colour channels should be convolved with Gaussians of the correct size, 2 marks for knowing result is difference between convolutions.
Page 3
SEE NEXT PAGE
—— SOLUTIONS ——
—— SOLUTIONS ——
January 2019 7CCSMCVI
d. For feature-based methods for solving the correspondence problem, briefly explain what is meant by a “detector” and a “descriptor”
[4 marks]
Answer
The detector is the method used to locate image features (or interest points) which are suitable for matching.
The descriptor is an array of feature values associated with each inter- est point. These descriptors are compared to determine which points match.
Marking scheme
2 marks for each correct definition.
e. For each of the following images identify the “Gestalt Law” that ac- counts for the observed grouping of the image elements.
i. ii.
Answer
i) continuity ii) connectivity
Marking scheme
2 marks for each correct answer.
[4 marks]
Page 4
SEE NEXT PAGE
January 2019 7CCSMCVI
f. Some object recognition methods (like template matching) employ a “global” representation of the object to be recognised, whereas other methods (like bag-of-words) use “local” representations. Briefly com- pare the advantages and disadvantages of global and local representa- tions.
Answer
Global • Advantages:
can distinguish similar objects
• Disadvantages:
intollerant to viewpoint, occlusion, within class variation
Local • Advantages:
tollerant to viewpoint, occlusion, within class variation, illu-
mination
• Disadvantages:
can’t distinguish objects consisting of the same features in different spatial arrangements.
can’t deal with too much clutter.
Marking scheme 4 marks.
[4 marks]
Page 5
SEE NEXT PAGE
—— SOLUTIONS ——
January 2019 7CCSMCVI 2.
a. Derive the equation for the pinhole camera model of image formation relating the coordinates of a 3D point P(y,z) to the coordinates of its image P’(y’,f’). Note that in the pinhole camera model, the image plane is located at distance f’ from the optical centre.
Answer
A cross-sectional diagram showing how a camera forms an image (P’ ) of a point (P):
From similar triangles:
y′ =y =⇒ y′=z′y z′z z
substituting z′ = f′ gives: y′ = f′y z
Marking scheme
2 marks for correct equation. 2 marks for derivation.
b. Hence, write in matrix form the equation relating the image coordi- nates (x’,y’,z’) to the world coordinates (x,y,z), where both sets of coordinates are measured relative to the optical centre of the camera.
Answer
x
z′ 0 0 1 0 Marking scheme
[4 marks]
[3 marks]
x′ 1000 ′ y
f y′ = z 0 1 0 0 z
Page 6
SEE NEXT PAGE
—— SOLUTIONS ——
1
January 2019 7CCSMCVI
3 marks.
c. A digital camera has an image plane at distance f′ = 20mm from its optical centre. The CCD array is 12mm by 12mm and is divided into 800 by 600 pixels. Calculate the magnification factors (α and β) for this camera.
Answer
Pixel size in x and y directions is:
sx = 12 = 0.015 mm/pixel, 800
Magnification factor = f′ . s
Hence, α=f′ = 20 =1333.3, sx 0.015
Marking scheme 4 marks.
[4 marks]
sy = 12 = 0.02 mm/pixel. 600
β=f′ = 20 =1000 sy 0.02
d. Using the answers to questions 2.b and 2.c determine the location at which point P appears in the image, when P has coordinates (50,50,500) mm relative to the camera reference frame and the optical axis inter- sects the image plane at pixel coordinates (400,300).
Answer
1
1 0010010
v= 1 500
0 1000 3000 1 0
50
0 =400.0
Marking scheme
x
y
v = 0 β oy 0 1 0 0
[4 marks]
u α0o1000
x
z z
1
u 1333.3 0 4001 0 0
50
0 533.3
500
1 10010010 1
Page 7
SEE NEXT PAGE
—— SOLUTIONS ——
January 2019 7CCSMCVI
4 marks. Full marks can be obtained for the correct method, even if the answer to part c is wrong.
e. Briefly compare the mechanisms used for sampling the image in a
camera and in an eye.
Answer Camera:
[6 marks]
• Has sensing elements sensitive to three wavelengths (RGB).
• Sensing elements occur in a fixed ratio across the whole image
plane.
• The sampling density is uniform across the whole image plane.
Eye:
• Has sensing elements sensitive to four wavelengths (RGBW).
• Sensing elements occur in a variable ratios across the image plane
(cone density highest at fovea, rod density highest outside fovea).
• The sampling density is non-uniform across the image plane (density
is highest at the fovea).
Marking scheme
1 mark for each point.
f. Give a brief explanation of what is meant by quantisation and pixeli-
sation in the context of digital image formation.
[4 marks]
Answer
Quantization is the process of representing light intensity (which can
take values from a continuous range) using a finite number of discrete values (by rounding the intensity to the nearest value).
Pixelisation is the process of representing light intensity (which is a continuous function of space) at a finite set discrete locations in a grid (by averaging the intensity within each each grid location, or pixel).
Page 8
SEE NEXT PAGE
—— SOLUTIONS ——
January 2019 7CCSMCVI
Marking scheme
2 marks for each correct definition.
Page 9
SEE NEXT PAGE
—— SOLUTIONS ——
—— SOLUTIONS ——
January 2019 7CCSMCVI 3. BelowisshownaLaplacianmask(L)andanumericalapproximation(G)
to a Gaussian function.
−1 −1 −1 0.01 0.08 0.01
L= −1 8 −1 G= 0.08 0.64 0.08
−1 −1 −1 0.01 0.08 0.01
a. Write down a mathematical expression describing the effect of con-
volving an image I with L. Answer
δ2I δ2I I′ =I∗L≈−δx2 +δy2
Marking scheme 3 marks.
b. Using L and G calculate a 3 by 3 Laplacian of Gaussian (or LoG) mask. [5 marks]
[3 marks]
Answer
Marking scheme 5 marks
−0.72 −0.18 −0.72
LoG = −0.18 4.76 −0.18
−0.72 −0.18 −0.72
Page 10
SEE NEXT PAGE
—— SOLUTIONS ——
January 2019 7CCSMCVI c. What advantage does a LoG mask have over a Laplacian for edge
detection?
[3 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 3 marks.
d. A method for locating straight edges is the Hough transform. Write pseudo-code for the Hough transform for straight lines.
[6 marks]
Answer
1. Initialise all elements in the accumulator array with a value of zero. 2. For each “edge” pixel
3. For each value of θ
4. Calculate the corresponding value of r (where r = ycos(θ)−
xsin(θ))
5. Increment by one the value stored in the accumulator ar-
ray nearest to the coordinates (θ, r) 6. Repeat from Step 3 for all θ.
7. Repeat from Step 2 for all pixels. Marking scheme
6 marks.
Page 11
SEE NEXT PAGE
January 2019 7CCSMCVI e. The array below shows intensity values in a 3-by-3 pixel binary image:
100
I = 0 1 0
001
Perform the Hough transform for straight lines on this image. Parame- terise a straight line using the equation r = ycos(θ)−xsin(θ), round r to the nearest integer and use the following values for θ: [0,45,90,135]. Use the top left corner of the image as the origin.
Answer
Initialise the accumulator array to:
r40000
30000
20000
10000
00000
−10000
−20000
−30000
−40000
0 45 90 135
θ
For pixel at (0,0), the following lines are possible:
θ=0, r=0cos(0)−0sin(0)=0 θ=45, r=0cos(45)−0sin(45)=0 θ=90, r=0cos(90)−0sin(90)=0
θ = 135, r = 0cos(135) − 0sin(135) = 0
[8 marks]
Page 12
SEE NEXT PAGE
—— SOLUTIONS ——
—— SOLUTIONS ——
January 2019
Update accumulator array:
r40000
30000
20000
10000
01111
−10000
−20000
−30000
−40000
0 45 90 135
θ
For pixel at (1,1), the following lines are possible:
θ=0, r=1cos(0)−1sin(0)=1
θ=45, r=1cos(45)−1sin(45)=0
θ = 90, r = 1cos(90) − 1sin(90) = −1
θ = 135, r = 1cos(135) − 1sin(135) = −1.414 ≈ −1 Update accumulator array:
r40000
30000
20000
11000
01211
−10011
−20000
−30000
−40000
0 45 90 135
θ For pixel at (2,2), the following lines are possible:
7CCSMCVI
θ=0, r=2cos(0)−2sin(0)=2 Page 13
SEE NEXT PAGE
January 2019
θ=45, r=2cos(45)−2sin(45)=0
θ = 90, r = 2cos(90) − 2sin(90) = −2
θ = 135, r = 2cos(135) − 2sin(135) = −2.828 ≈ −3 Update accumulator array:
7CCSMCVI
r40000
30000
21000
11000
01311
−10011
−20010
−30001
−40000
0 45 90 135
θ
Marking scheme
1 mark for correctly initialising the accumulator array. 2 marks for correctly calculating the θ and r values for each of the 3 points. 1 mark for correctly updating the accumulator array.
Page 14
SEE NEXT PAGE
—— SOLUTIONS ——
January 2019 7CCSMCVI 4.
a. Briefly define what is meant by image segmentation in computer vision. [3 marks]
Answer
Segmentation is the process of partitioning the pixels in an image into different groups that correspond to different objects or features.
Marking scheme 3 marks.
b. One method of image segmentation is clustering. Write pseudo-code
for the k-means clustering algorithm.
Answer
1. Randomly choose k points to act as cluster centres
[6 marks]
2. For each data point
3. Calculate its similarity to each cluster centre
4. Allocate the data point to the closest cluster centre
5. Repeat from step 2 for each data point 6. For each cluster centre
7. Calculate its new position as the mean position its ele-
ments
8. Repeat from step 6 for each cluster centre
9. Repeat from step 2 until the cluster centres are unchanged
Marking scheme
6 marks. 1 For describing the initialisation; 2 for describing the updat- ing of the allocation of point to centres (steps 2-5); 2 for describing the re-estimation of the cluster centres (steps 6-8); 1 for describing when to stop.
Page 15
SEE NEXT PAGE
—— SOLUTIONS ——
—— SOLUTIONS ——
January 2019 7CCSMCVI c. The RGB channels for a 3-by-3 pixel colour image are shown below.
5 1010 101510 153025
R=102010G=1020 5B=151510
5 30 30 5 10 10 15 5 10
Apply the k-means clustering algorithm to this image in order assign each pixel to a region based purely on its colour. Assume that (i) the method used to assess similarity is the sum of absolute differences (SAD), (ii) there are two clusters, and the cluster centres are initially assigned the following RGB values: (10, 10, 10) and (30, 20, 10).
[6 marks]
Answer Calculate distance of each data point to each cluster centre:
distance from (10, 10, 10):
distance from (30, 20, 10):
10 25 15
5 25 5
15 25 20 40 45 45
35 15 35
45 15 10 Allocate each data point to closest cluster centre:
Calculate new cluster centres as mean of elements belonging to that cluster:
c1 =[(5,10,15)+(10,15,30)+(10,10,25)+(10,10,15)+(10,5,10)+ (5, 5, 15)]/6 = (8.333, 9.167, 18.333)
c2 =[(20,20,15)+(30,10,5)+(30,10,10)]/3=(26.667,13.333,10.0) Calculate distance of each data point to each cluster centre:
distance from (8.333, 9.167, 18.333):
Page 16
7.5000 19.1667 9.1667
5.8333 25.8333 14.1667
10.8333 35.8333 30.8333 SEE NEXT PAGE
111
1 2 1
122
January 2019
distance from (26.667, 13.333, 10.0):
7CCSMCVI
30.0000 38.3333 35.0000
25.0000 18.3333 25.0000
35.0000 11.6667 6.6667 111
Allocate each data point to closest cluster centre: 1 2 1
122 Allocation is unchanged, so cluster centres are also unchanged and
algorithm has converged.
Marking scheme
2 marks for correct method of assigning points to initial clusters, 2 marks for correct method of re-calculating cluster centres, 1 mark for recalculating distances and assignments, 1 mark for knowing stopping criteria.
d. For each of the nine pixels of the image defined in question 4.c write down the feature vectors that would be used to perform image seg- mentation using k-means clustering based on both colour and location information.
Answer
(5,10,15,1,1) (10,15,30,2,1) (10,10,25,3,1)
(10,10,15,1,2) (20,20,15,2,2) (10,5,10,3,2)
(5,5,15,1,3) (30,10,5,2,3) (30,10,10,3,3) Marking scheme
4 marks
[4 marks]
Page 17
SEE NEXT PAGE
—— SOLUTIONS ——
—— SOLUTIONS ——
January 2019 7CCSMCVI
e. Name three alternative, region-based, algorithms that could be used to segment the image using both colour and location information.
Answer
region growing region merging split and merge
Marking scheme 2 marks each.
[6 marks]
Page 18
SEE NEXT PAGE
—— SOLUTIONS ——
January 2019 7CCSMCVI 5.
a. Explain why the stereo correspondence problem is an ill-posed problem, and describe three constraints, or priors, that can be used to help solve
it.
[7 marks]
Answer
An ill-posed problem has multiple solutions (or no solution).
In the stereo correspondence problem a location in one image can often match the appearance of multiple locations in the other image (or no locations if that location is occluded in the second image).
A prior is any additional source of information that can help reduce the number of possible solutions, and hence, help infer the correct corresponding location.
For the stereo correspondence problem, priors that are often used are:
• epipolar constraint (corresponding points lie along the epipolar line)
• maximum disparity (range of possible matches reduced by knowl-
edge 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
occlusion)
Marking scheme
3 marks for knowing what ill-posed means, and how this is relevant to the correspondence problem. 4 marks for knowing what a prior is and defining three priors relevant to solving the video correspondence problem.
Page 19
SEE NEXT PAGE
January 2019 7CCSMCVI
b. 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.
c. A stereo pair of images were processed to identify interest points. The following table shows the locations of the interest points and the corresponding feature vectors.
Left Image
Interest Coordinates Feature
Point Vector
Right Image
Interest Coordinates Feature
Point Vector
L1 L2 L3 L4
(145,234) (23,134) (231,345) (231,34)
(2, 3, 0, 1) (3, 4, 1, 3) (1, 2, 4, 2) (0, 1, 3, 0)
R1 (45,345)
R2 (112,76)
R3 (68,219)
(2, 3, 2, 2) (1, 2, 1, 0) (1, 5, 4, 1)
For interest point L3 in the left image find the best matching interest point in the right image, using sum of absolute differences (SAD) as the similarity measure.
[4 marks]
Answer
Calculating the SAD between (1, 2, 4, 2) and each of the feature vectors extracted from the right image:
Page 20
SEE NEXT PAGE
—— SOLUTIONS ——
January 2019 7CCSMCVI
For R1: 4
For R2: 5
For R3: 4
So both R1 and R3 are the best matching interest points.
Marking scheme 4 marks.
d. Given that the left and right images described in question 5.c were taken using two identical cameras that were mounted so as to have coplanar image planes, such that the right camera was displaced a distance of 400mm along the x-axis of the left one, determine the depth of the 3D point P that is seen at coordinates (231,345) in the left image. Assume that for both cameras the focal length is 30mm, and the pixel size of the camera is 0.1mm/pixel.
[6 marks]
Answer
Because the cameras are coplanar with collinear x-axes, corresponding points will have the same y-coordinates (the epipolar constraint), so of the two best matches found in 5.c, R1 must be the corresponding point.
For coplanar cameras, depth
Therefore, depth is
Z= fB xL − xR
30 × 400 = 645mm 0.1×(231−45)
Page 21
SEE NEXT PAGE
—— SOLUTIONS ——
—— SOLUTIONS ——
January 2019 7CCSMCVI
Marking scheme
2 marks for using the epipolar constraint, 2 marks for the correct equation, 2 marks for the correct application of the equation.
e. Give two reasons why the recovery of depth information can be useful for object recognition.
[4 marks]
Answer
Depth between objects provides a cue for segmentation, and hence,
helps solve the problem of mid-level vision and so indirectly solve the object recognition problem.
Depth within an object provides information about the shape of an object, and hence, helps solve the problem of high-level vision and so directly solve the object recognition problem.
Marking scheme
2 marks for each correct answer.
Page 22
SEE NEXT PAGE
January 2019 7CCSMCVI 6.
a. A successful object recognition system needs to be sensitive to differ- ences between images that are relevant to distinguishing one object (or category of object) from another, but needs to be insensitive (or tolerant) to other differences that are not relevant to object identity or category. List five causes of image changes that are not relevant to object recognition.
Answer
• viewpoint (scale, rotation, translation) • lighting
• non-rigid deformations
• within category variations
• clutter/occlusion Marking scheme
1 mark each
b. Describe the sliding window technique of object recognition, and briefly explain how this method achieves tolerance to differences between im- ages that are not relevant to object identity or category.
[5 marks]
Answer
Image patches are selected from the image and each patch is presented to a classifier to determine if it contains the object.
Tolerance is achieved by:
1) using a classifier that has been trained to recognise the object de- spite changes in appearance
2) choosing image patches of different shapes and sizes that are resized before being input to the classifier
[5 marks]
Page 23
SEE NEXT PAGE
—— SOLUTIONS ——
January 2019 7CCSMCVI
Marking scheme
2 marks for correctly describing the method. 3 marks for describing tolerance.
Below are shown three 4-by-4 pixel binary image patches, labelled A to C. White pixels have a value of one, black pixels have a value of zero.
ABC
Page 24
SEE NEXT PAGE
—— SOLUTIONS ——
January 2019 7CCSMCVI
c. A number of standard metrics can be used to compare two image patches. Write down the formulae for comparing two patches, A and B, using:
i. cross-correlation Answer
cross-correlation = i,j A(i, j)B(i, j)
Marking scheme
2 marks.
ii. sum of absolute differences
Answer
sum of absolute differences =
[2 marks]
Marking scheme
2 marks.
iii. correlation coefficient
Answer
correlation coefficient =
Marking scheme 2 marks.
[2 marks]
∥A(i, j) − B(i, j)∥ i,j
[2 marks]
(A(i,j )−A ̄)(B (i,j )−B ̄ )
√i,j √ i,j(A(i,j)−A ̄)2
i,j(B(i,j)−B ̄)2
Page 25
SEE NEXT PAGE
—— SOLUTIONS ——
—— SOLUTIONS ——
January 2019 7CCSMCVI d. For each pair of image patches (i.e., A & B, A & C, and B & C)
calculate the:
i. Cross-correlation
Answer
A and B=2 A and C=3 B and C=2
Marking scheme
2 marks.
ii. Correlation coefficient
Answer
A and B=-0.0667 A and C=0.3133 B and C=0.0348
Marking scheme 2 marks.
[2 marks]
[2 marks]
e. For each images patch (A, B, and C) draw the intensity histogram. [2 marks]
Answer
A: 0=10, 1=6 B: 0=10, 1=6 C: 0=11, 1=5
Marking scheme 2 marks.
Page 26
SEE NEXT PAGE
—— SOLUTIONS ——
January 2019 7CCSMCVI f. The similarity between image patches A, B and C is to be compared
using:
i. Cross-correlation
ii. Correlation coefficient
iii. Comparison of intensity histograms
For each of these methods, write down which pair of image patches are found to be most similar to each other.
[3 marks]
Answer
(i) Cross-correlation: most similar are A and C
(ii) Correlation coefficient: most similar are A and C
(iii) Comparison of intensity histograms: most similar are A and B
Marking scheme
1 mark for each answer.
Page 27
FINAL PAGE