Davies: Computer Vision, 5th edition: Solutions to selected problems 19
© E. R. Davies 2017
found by moving inwards from every edge point and accumulating a point in parameter
space at a distance equal to R; then peaks in parameter space correspond to circle centres
or centres of whole circles of which only parts may be visible in the image.
(b) To locate straight edges, each edge segment in the image is extended and the distance
from the origin is measured, together with the direction of the edge normal. Then a
point ( , ) is accumulated in , parameter space. When all such points have been
accumulated, peaks are found, and each one is taken to correspond to a line in the original
(c) When a square object is present, this will give four peaks in parameter space, and
these will be at predictable positions: specifically, one pair will have the same 1, and
the other pair will have equal = 2 = 1 ± 90°, and the peaks will actually fall at the
(d) (i) If parts of some sides of the square were occluded, this would not matter, as the
Hough transform peak positions would still reveal the presence of the square. (ii) If one
side of the square were missing, there would be enough information to confirm the
presence of an occluded square and to work out its size; if another side were missing
things would get more difficult; we then have to ask questions as to whether these sides
(e) It is crucial to this type of algorithm to have edge detectors that are capable of
Davies: Computer Vision, 5th edition: Solutions to selected problems 20
10.4
(a) The Hough transform is valuable because it is inherently robust against noise, defects
and occlusions. Description of the Hough transform for circle detection is bookwork (see
(b) A Hough transform is merely a parameter space in which data is accumulated, so an
accumulating histogram is simply a 1-D Hough transform. The problem will this approach
is that the two 1-D transforms are disconnected and independent, and it is not known
which solution of the one corresponds to a solution of the other. Thus the Hough
(c) In this case take the ends of the chord as being (x1, y) and (x2, y), and the length of the
chord as d:
Assuming that the circle radius is known to be R, Pythagoras’ theorem gives:
This is in many ways a cleaner method than (b), and doesn’t depend on relating 1-D
transforms in the x and y directions, which could be tedious in complex images with many
edge points. Thus it could well be faster, in spite of the need for square root computations.
It could also be more robust. The sign ambiguity is far less ambiguous than that inherent
in method (b), and would be coped with easily by the Hough transform voting technique.
Davies: Computer Vision, 5th edition: Solutions to selected problems 22
10.10
10.11
When several identical equally orientated ellipses appear in the image, centres will be