Graphics & Visualization Chapter 11 Davies Computer Vision Edition Solutions Selected Problems The Hough Transform Operates Taking

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

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

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