Davies: Computer Vision, 5th edition: Solutions to selected problems 9
shapes, as will be seen in the following figure. Snake shapes and spirals give similar
trouble.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · 1 1 1 1 1 1 · · · · · · · · · · · · · ·
· · · 5 5 5 5 5 5 5 5 5 5 5 5 · · · · · · · · · · · · · ·
· · · 5 5 5 5 5 5 5 5 5 5 5 · · · · · · · · · · · · · · ·
· · · · 5 5 5 5 5 5 5 5 · · · · · · · 6 6 6 6 6 6 · · · ·
· · · · · · · · · · · · · · · · · · 6 6 6 6 6 6 6 6 · · ·
· · · · · · · · · · · · · · · · · 6 6 6 6 6 6 6 6 6 6 · ·
· · · · · · · · · · · · · · · · · 6 6 6 6 6 6 6 6 6 6 · ·
· · · 7 7 7 7 7 7 7 · · · · · · · 6 6 6 6 6 6 6 6 6 6 · ·
· · 7 7 7 7 7 7 7 7 · · · · · · · 6 6 6 6 6 6 6 6 6 6 · ·
(b) The solution is to accept the labels that are obtained by a single simple-minded
labelling scan, but to record all label adjacencies in a table; then to analyse the table,
noting all labels that are equivalent to each other, give the minimum (or maximum) value
to each such set; then relabel the objects.
We can also take it that the table must have diagonal entries, so we set up the table
(the one below is a minimal representation of a U, a W and an I) in the following way:
1 1 0 0 0 0
Davies: Computer Vision, 5th edition: Solutions to selected problems 10
1 1 0 0 0 0
1 1 0 0 0 0
0 0 3 0 0 3
8.5
(a) It produces a rectangular convex hull around each object.
(b) Detail of do until facility:1
8.6
(a) The following algorithm generates a rectangular convex hull around any object:
do {
finished = true;
Davies: Computer Vision, 5th edition: Solutions to selected problems 11
© E. R. Davies 2017
gaze clockwise until the first object point is reached, and move to it. The simplest way of
implementing this is via a lookup table: for a 3 3 window we only have eight neighbors,
so there are only 256 possibilities, and we can look up the direction to move in one go.
(c) To implement the convex hull algorithm, travel around the boundary clockwise with
a 2-point tester. Keep the first point fixed, then move the second point onwards until it
becomes a tangent (or just ceases to be a chord at another position); then move the first
8.7
(a) The distance function is a version of the binarized image in which each pixel is
(b) Local maxima are found by the algorithm:
(c) For Fig. 8.P1, no. of local maxima pixels is 32, and no. of boundary points is 55.
Therefore the answers (in bits) for a 256 256 image are:
8.8
(a) A distance function shows the distance from the background to every point in a
binary picture object, as indicated in the following figure:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Davies: Computer Vision, 5th edition: Solutions to selected problems 12
The number of passes required by a parallel algorithm is equal to half the maximum
width of the widest object in the image, and equals the highest value in the distance
function. The number of passes required by a sequential algorithm is just two.
(b) The sequential algorithm is:
[[ P0 = A0*255; ]]; {initialization pass only}
[[+ P0 = min(P0 – 1, P2, P3, P4, P5) + 1; +]];
(c) The local maxima are marked in the following figure:
+ + + + + + + + + + + + + + + + +
+ + + + + + + + + + + + + + + + + +
+ + 3 3 3 3 3 3 3 3 3 3 3 3 3 + + + +
The image would be reconstituted by a process of downward propagation from the
(d) The compression factor for transmitting the local maxima is:
= 1282 /(33 3
The minimized set of local maxima is:
+ + + + + + + + + + + + + + + + +
+ + + + + + + + + + + + + + + + + +
+ + 3 + + + + 3 + + + + 3 + 3 + + + +
Davies: Computer Vision, 5th edition: Solutions to selected problems 13
8.9
(a) If the local maxima were defined as in (i), very few pixels would remain labelled, and
there would be insufficient information for reproducing the original shapes. If they are
defined as in (ii), clusters of pixels will be labelled with the same values. (ii) is suitable
(c) Run-length encoding counts the numbers of pixels of the same intensity value (0
or 1) and puts out these numbers in sequence. For an image with few objects, few
8.10
(a) When propagating a distance function using a parallel algorithm, the pixels in the
object are initially given a high value, such as 255. Then, pixels adjacent to 0’s are given
(b) One pass of a 4-pass algorithm:
(c) The parallel algorithm will take a time ~N2 N/2 8 = N3 4, because it will need a
number of passes equal to at most half the width of the largest object, and each pass will
involve windows with 8 pixels apart from the centre pixel. The 2-pass sequential
algorithm will take ~N2 2 (5 2) = N2 20 operations, as there are 4 active pixels in
