Unlock document.
This document is partially blurred.
Unlock all pages and 1 million more documents.
Get Access
Davies: Computer Vision, 5th edition: Solutions to selected problems 23
11.1
(a) The Hough transform operates by taking a parameter space (often congruent to image
space), clearing it, accumulating votes to build up evidence that particular sets of
parameter values are significant and represent objects in the image, and analysing the
parameter space to locate significant peaks representing objects in the image, and finally
(b) It is said that the Hough transform only leads to hypotheses about the presence of
objects in images, and that they should all be checked independently before making a final
Davies: Computer Vision, 5th edition: Solutions to selected problems 27
(c) This problem uses the standard maximal clique method which is bookwork (see the
main text in Chapter 11). Detecting the blade from its four corners is a straightforward
(d) When overlaps occur, some of the blade will be missing and there will be ambiguity
in either of the above cases if either two corners are missing or one hole is missing. In
extreme cases we need all the features we can get. So consider all the corners and holes
equally as point features. This gives seven features in the ideal case, both in the template
and in the image, so the match graph has 49 feature assignments. However, symmetry
11.10
(a, b) (i) A standard if tedious solution to the maximal clique problem (Fig. 11.S7a):
note the extra compatibilities caused by the fact that distance AE = DE.
(ii) A much simpler solution (Fig. 11.S7b).
In fact (iv) is rather nice, as it is only necessary to include exactly the right feature
associations in the match graph. Hence we get a fully general solution with less effort than
the standard solution (i).
(c) As a result, (iv) is faster than (i), though (ii) and a fortiori (iii) are very fast. On the
(d) The time taken to build a match graph is proportional to MN where M is the number
of features on an ideal object that are actually used and N is the number of points in the
image that are actually used. Hence the respective build times are basically: 6 6, 4 4,
2 2, 6 6, the first case having a lot more extraneous small cliques which require
additional build time (trivial). Let’s assume that the time taken to find a maximal clique of
Davies: Computer Vision, 5th edition: Solutions to selected problems 28
© E. R. Davies 2017
Fig. 11.S7. For reasons of clarity, not all compatibility lines are shown in this figure: in (a) a
good many lines have been omitted, and in (d) only the main maximal clique is shown. (b)
and (c) are complete.
11.11
(a) Numbering the image features in forward raster scan order as 1, 2, 3, 4, 5, 6, and the
template features as A, B, C, D in the same order as those in the first object in the image,
Davies: Computer Vision, 5th edition: Solutions to selected problems 29
© E. R. Davies 2017
A1–B2–C3–D4; A2–B1; B3–C2; C4–D3; D1–A4; A3–C1; B4–D2; A5–C6; A6–C5.
The 4-element maximal clique wins over the first six 2-element cliques, leaving the
last two 2-element maximal cliques, which constitute equally probable solutions at this
level.
Thus we have an almost certain 4-feature object, and a possible 2-feature object
which is partly occluded or defective and which may be either way around.
(b) If the objects have an axis of symmetry, we will get more compatibilities, as the two
features B, C related by symmetry cannot be distinguished. The final result is that the two
objects each have twice as many maximal clique solutions:
In addition, the size of the match graph goes down from 4 6 to 3 6, saving storage
and computation, and arriving at only the meaningful answers.
(c) For the case where there are three sizes of hole, the extraneous 2-element cliques will
mostly not arise, the only one that will remain will be D1–A4. Thus the final solutions
are:
(d) However, if the further matching strategy is employed, the equal sized holes in the
image are features 1, 4, 5, and the equal holes in the template are A and D. This means
that we get just the following subset of compatibilities:
Both the 3-element cliques represent the same object, but there is only one clique to
represent the occluded object. Thus the technique locates both the objects, in spite of the
occlusion, though some means must be adopted for choosing between the two solutions
for the same object.
Davies: Computer Vision, 5th edition: Solutions to selected problems 30
(e) An optimal object identification strategy is one which uses all possible information to
prevent unnecessary compatibilities from getting into the match graph and thus
complicating clique finding. However, as indicated above, cutting down the information
11.12
(a) The first stage in carrying out the maximal clique technique is to draw a match graph
showing how the object (feature points 1–4 in the image) matches to a template (feature
points A–D). Feature pairs are considered to see if they are the same distance apart in the
two cases: if so a compatibility line is drawn between the appropriate combination, A1
and B2, but also between A2 and B1, as these are the same distance and the object could
(b) The basic algorithm will not distinguish between widgets that are normally presented
from those that are upside down, as it is only looking for evidence arising from distances
(c) If the camera used to view the widgets is accidentally jarred and then reset at a
different height, the inter-feature distances will mostly not match the ideal template.
However, we can make a list of inter-feature distances in the image and the template, and
make them match by scaling. We can then run the maximum clique algorithm. This will
(d) If the camera is set at an unknown angle to the vertical, examination of a circular
