10.1 Introduction

The location of round objects is important in many areas of image analysis, but it is especially important in industrial applications such as automatic inspection and assembly. In the food industry alone, a sizable proportion of products are round—biscuits, cakes, pizzas, pies, oranges, and so on (Davies, 1984c). In the automotive industry many circular components are used—washers, wheels, pistons, heads of bolts, and so on—while round holes of various sizes appear in such items as casings and cylinder blocks. In addition, buttons and many other everyday objects are round. All these manufactured parts need to be checked, assembled, inspected, and measured with high precision. Finally, objects can frequently be located by their holes, so finding round holes or features is part of a larger problem. Since round picture objects form a special category of their own, efficient algorithms should be available for analyzing digital images containing them. This chapter addresses some aspects of this problem.

An earlier chapter showed how objects may be found and identified using algorithms that involve boundary tracking (Table 10.1). Unfortunately, such algorithms are insufficiently robust in many applications; for example, they tend to be muddled by artifacts such as shadows and noise. This chapter shows that the Hough transform (HT) technique is able to overcome many ofthese problems. It is found to be particularly good at dealing with all sorts of difficulties, including quite severe occlusions. It achieves this capability not by adding robustness but by having robustness built in as an integral part of the technique.

Table 10.1 Procedure for finding objects using (r, θ) boundary graphs

This procedure is not sufficiently robust with many types of real data (e.g., in the presence of noise, distortions in product shape, etc). In fact, it is quite common to find the tracking procedure veering off and tracking around shadows or other artifacts.

The application of the HT to circle detection is perhaps the most straightforward use of the technique. However, several enhancements and adaptations can be applied in order to improve the accuracy and speed of operation, and in addition to make the method work efficiently when detecting circles with a range of sizes. We will examine these modifications following a description of the basic HT techniques.

10.2 Hough-based Schemes for Circular Object Detection

In the original HT method for finding circles (Duda and Hart, 1972), the intensity gradient is first estimated at all locations in the image and is then thresholded to give the positions of significant edges. Then the positions of all possible center locations—namely, all points a distance R away from every edge pixel—are accumulated in parameter space, R being the anticipated circle radius. Parameter space can be a general storage area, but when looking for circles it is convenient to make it congruent to image space; in that case, possible circle centers are accumulated in a new plane of image space. Finally, parameter space is searched for peaks that correspond to the centers of circular objects. Since edges have nonzero width and noise will always interfere with the process of peak location, accurate center location requires the use of suitable averaging procedures (Davies, 1984c; Brown, 1984).

This approach requires that a large number of points be accumulated in parameter space, and so a revised form of the method has now become standard. In this approach, locally available edge orientation information at each edge pixel is used to enable the exact positions of circle centers to be estimated (Kimme et al., 1975). This is achieved by moving a distance R along the edge normal at each edge location. Thus, the number of points accumulated is equal to the number of edge pixels in the image.¹ This represents a significant saving in computational load. For this saving to be possible, the edge detection operator that is employed must be highly accurate. Fortunately, the Sobel operator is able to estimate edge orientation to 1° and is very simple to apply (Chapter 5). Thus, the revised form of the transform is viable in practice.

As was seen in Chapter 5, once the Sobel convolution masks have been applied, the local components of intensity gradient g_x and g_y are available, and the magnitude and orientation of the local intensity gradient vector can be computed using the formulas:

     (10.1)

and

     (10.2)

Use of the arctan operation is not necessary when estimating center location coordinates (x_c, y_c) since the trigonometric functions can be made to cancel out:

     (10.3)

     (10.4)

the values of cos θ and sin θ being given by:

     (10.5)

     (10.6)

In addition, the usual edge thinning and edge linking operations—which normally require considerable amounts of processing—can be avoided if a little extra smoothing of the cluster of candidate center points can be tolerated (Davies, 1984c) (Table 10.2). Thus, this Hough-based approach can be a very efficient one for

Table 10.2 A Hough-based procedure for locating circular objects

This procedure is particularly robust. It is largely unaffected by shadows, image noise, shape distortions, and product defects. Note that stages 1-3 of the procedure are identical to stages 1-3 in Table 10.1. However, in the Hough-based method, computation can be saved, and accuracy actually increased, by omitting stages 2 and 3.

locating the centers of circular objects, virtually all the superfluous operations having been eliminated, leaving only edge detection, location of candidate center points, and center point averaging to be carried out. It is also relevant that the method is highly robust in that if part of the boundary of an object is obscured or distorted, the object center is still located accurately. Some remarkable instances of this can be seen in Figs. 10.1 and 10.2. The reason for this useful property is clear from Fig. 10.3.

Figure 10.1 Location of broken and overlapping biscuits, showing the robustness of the center location technique. Accuracy is indicated by the black dots, which are each within 1/2 pixel of the radial distance from the center.

Figure 10.2 Location of a biscuit with a distortion, showing a chocolate-coated biscuit with excess chocolate on one edge. Note that the computed center has not been “pulled” sideways by the protuberances. For clarity, the black dots are marked 2 pixels outside the normal radial distance.

Figure 10.3 Robustness of the Hough transform when locating the center of a circular object. The circular part of the boundary gives candidate center points that focus on the true center, whereas the irregular broken boundary gives candidate center points at random positions.

This technique is so efficient that it takes slightly less time to perform the actual Hough transform part of the calculation than to evaluate and threshold the intensity gradient over the whole image. Part of the reason for these relative timings is that the edge detector operates within a 3 × 3 neighborhood and necessitates some 12 pixel accesses, four multiplications, eight additions, two subtractions, and an operation for evaluating the square root of sum of squares (equation (10.1)). As seen in Chapter 5, the latter type of operation is commonly approximated by taking a sum or maximum of absolute magnitudes of the component intensity gradients, in order to estimate the magnitude of the local intensity gradient vector:

     (10.7)

or

     (10.8)

However, this type of shortcut is not advisable in the present context, since an accurate value for the magnitude of this vector is required in order to compute the position of the corresponding candidate center location with sufficient precision. However, lookup tables provide a viable way around this problem.

Overall, the dictates of accuracy imply that candidate center location requires significant computation. However, substantial increases in speed are still possible by software means alone, as will be seen later in the chapter. Meanwhile, we consider the problems that arise when images contain circles of many different radii, or for one reason or another radii are not known in advance.

10.3 The Problem of Unknown Circle Radius

In a number of situations circle radius is initially unknown. One such situation is where a number of circles of various sizes are being sought—as in the case of coins, or different types of washers. Another is where the circle size is variable—as for food products such as biscuits—so that some tolerance must be built into the system. In general, all circular objects have to be found and their radii measured. In such cases, the standard technique is to accumulate candidate center points simultaneously in a number of parameter planes in a suitably augmented parameter space, each plane corresponding to one possible radius value. The centers of the peaks detected in parameter space give not only the location of each circle in two dimensions but also its radius. Although this scheme is entirely viable in principle, there are several problems in practice:

To some extent this is to be expected, since the augmented scheme enables more objects to be detected directly in the original image.

We will shortly show that problems (2) and (3) may largely be eliminated by using just one parameter plane to store all the information for locating circles of different radii, that is, accumulating not just one point per edge pixel but a whole line of points along the direction of the edge normal in this one plane. In practice, the line need not be extended indefinitely in either direction but only over the restricted range of radii over which circular objects or holes might be expected.

Even with this restriction, a large number of points are being accumulated in a single parameter plane, and it might initially be thought that this would lead to such a proliferation of points that almost any “blob” shape would lead to a peak in parameter space might be interpreted as a circle center. However, this is not so, and significant peaks normally result only from genuine circles and some closely related shapes.

To understand the situation, consider how a sizable peak can arise at a particular position in parameter space. This can happen only when a large number of radial vectors from this position meet the boundary of the object normally. In the absence of discontinuities in the boundary, a contiguous set of boundary points can be normal to radius vectors only if they lie on the arc of a circle. (Indeed, a circle could be defined as a locus of points that are normal to the radius vector and that form a thin connected line.) If a limited number of discontinuities are permitted in the boundary, it may be deduced that shapes like that of a fan² will also be detected using this scheme. Since it is in any case useful to have a scheme that can detect such shapes, the main problem is that there will be some ambiguity in interpretation—that is, does peak P in parameter space arise from a circle or a fan? In practice, it is quite straightforward to distinguish between such shapes with relatively little additional computation; the really important problem is to cut down the amount of computation needed to key into the initially unstructured image data. It is often a good strategy to prescreen the image to eliminate most of it from further detailed consideration and then to analyze the remaining data with tools having much greater discrimination. This two-stage template matching procedure frequently leads to significant savings in computation (VanderBrug and Rosenfeld, 1977; Davies, 1988i).

A more significant problem arises because of errors in the measurement of local edge orientation. As stated earlier, edge detection operators such as the Sobel introduce an inherent inaccuracy of about 1 ^°. Image noise typically adds a further 1 ^° error, and for objects of radius 60 pixels the result is an overall uncertainty of about 2 pixels in the estimation of center location. This makes the scheme slightly less specific in its capability for detecting objects. In particular, edge pixels can now be accepted when their orientations are not exactly normal to the radius vector, and an inaccurate position will be accumulated in parameter space as a possible center point. Thus, the method may occasionally accept cams or other objects with a spiral boundary as potential circles.

Overall, the scheme is likely to accept the following object shapes during its prescreening stage, and the need for a further discrimination stage will be highly application-dependent:

If occlusions and breakages can be assumed to be small, then it will be safe to apply a threshold on peak size at, say, 70% of that expected from the smallest circle.³ In that case, it will be necessary to consider only whether the peaks arise from objects of types (1), (2), or (3). If, as usually happens, objects of types (2) or (3) are known not to be present, the method is immediately a very reliable detector of circles of arbitrary size. Sometimes specific rigorous tests for objects of types (2) and (3) will still be needed. They may readily be distinguished, for example, with the aid of corner detectors or from their radial intensity histograms (see Chapter 14 and 22).

Next, note that the information on radial distance has been lost by accumulating all votes in a single parameter plane. Hence, a further stage of analysis is needed to measure (or classify) object radius. This is so even if a stage of disambiguation is no longer required to confirm that the object is of the desired type. This extra stage of analysis normally involves negligible additional computation because the search space has been narrowed down so severely by the initial circle location procedure (see Figs. 10.4-10.6). The radial histogram technique already referred to can be used to measure the radius: in addition it can be used to perform a final object inspection function (see Chapter 22).

Figure 10.4 (a) Simultaneous location of coins and a key with the modified Hough scheme: the various radii range from 10 to 17 pixels; (b) transform used to compute the centers indicated in (a). Detection efficiency is unimpaired by partial occlusions, shape distortions, and glints. However, displacements of some centers are apparent. In particular, one coin (top left) has only two arcs showing. The fact that one of these is distorted, giving a lower curvature, leads to a displacement ofthe computed center. The shape distortions are due to rather uneven illumination.

Figure 10.5 (a) Accurate simultaneous detection of a lens cap and a wing nut when radii are assumed to range from 4 to 17 pixels; (b) response in parameter space that arises with such a range of radii: note the overlap of the transforms from the lens cap and the bracket; (c) hole detection in the image of (a) when radii are assumed to fall in the range -26 to -9 pixels (negative radii are used since holes are taken to be objects of negative contrast). Clearly, in this image a smaller range of negative radii could have been employed.

Figure 10.6 (a) Simultaneous detection of four (approximately) equiangular spirals and a circle of similar size (16 pixels radius), for assumed range of radii 9 to 22; (b) transform of (a). In the spiral with the largest step, the step size is about 6 pixels, and detection is possible only if some displacement of the center is acceptable. In such cases, the center is effectively the point on the evolute of the shape in parameter space that happens to have the maximum value. Note that cams frequently have shapes similar to those of the spirals shown here.

10.4 The Problem of Accurate Center Location

The previous section analyzed the problem of how to cope efficiently with images containing circles of unknown or variable size. This section examines how circle centers may be located with high (preferably subpixel) accuracy. This problem is relevant because the alternative of increased resolution would entail the processing of many more pixels. Hence, attaining a high degree of accuracy with images of low or moderate resolution will provide an advantage.

There are several causes of inaccuracy in locating the centers of circles using the HT: (1) natural edge width may add errors to any estimates of the location of the center (this applies whether or not a thinning algorithm is employed to thin the edge, for such algorithms themselves impose a degree of inaccuracy even when noise is unimportant); (2) image noise may cause the radial position of the edge to become modified; (3) image noise may cause variation in the estimates of local edge orientation; (4) the object itself may be distorted, in which case the most accurate and robust estimate of the circle center is required (i.e., the algorithm should be able to ignore the distortion and take a useful average from the remainder of the boundary); (5) the object may appear distorted because of inadequacies in the method of illumination; and (6) the Sobel or other edge orientation operator will have a significant inherent inaccuracy of its own (typically 1°—see Chapter 5), which then leads to inaccuracy in estimating center location.

Evidently, it is necessary to minimize the effects of all these potential sources of error. In applying the HT, it is usual to remember that all possible center locations that could have given rise to the currently observed edge pixel should be accumulated in parameter space. Thus, we should accumulate in parameter space not a single candidate center point corresponding to the given edge pixel, but a point spread function (PSF) that may be approximated by a Gaussian error function. This will generally have different radial and transverse standard deviations. The radial standard deviation will commonly be 1 pixel—corresponding to the expected width of the edge—whereas the transverse standard deviation will frequently be at least 2 pixels, and for objects of moderate (60 pixels) radius the intrinsic orientation accuracy of the edge detection operator contributes at least 1 pixel to this standard deviation.

It would be convenient if the PSF arising from each edge pixel were isotropic. Then errors could initially be ignored and an isotropic error function could be convolved with the entire contents of parameter space, thus saving computation. However, this is not possible if the PSF is anisotropic, since the information on how to apply the local error function is lost during the process of accumulation.

When the center need only be estimated to within 1 pixel, these considerations hardly matter. However, when locating center coordinates to within 0.1 pixel, each PSF will have to contain 100 points, all of which will have to be accumulated in a parameter space of much increased spatial resolution, or its equivalent,⁴ if the required accuracy is to be attained. However, a technique is available that can cut down on the computation, without significant loss of accuracy, as will be seen below.

10.4.1 Obtaining a Method for Reducing Computational Load

The HT scheme outlined here for accurately locating circle centers is a completely parallel approach. Every edge pixel is examined independently, and only when this process is completed is a center looked for. Since there is no obvious means of improving the underlying Hough scheme, a sequential approach appears to be required if computation is to be saved. Unfortunately, sequential methods are often less robust than parallel methods. For example, an edge tracking procedure can falter and go wandering off, following shadows and other artifacts around the image. In the current application, if a sequential scheme is to be successful in the sense of being fast, accurate, and robust, it must be subtly designed and retain some of the features of the original parallel approach. The situation is now explored in more detail.

First, note that most of the inaccuracy in calculating the position of the center arises from transverse rather than radial errors. Sometimes transverse errors can fragment the peak that appears in the region of the center, thereby necessitating a

considerable amount of computation to locate the real peak accurately. Thus, it is reasonable to concentrate on eliminating transverse errors.

This immediately leads to the following strategy: find a point D in the region of the center and use it to obtain a better approximation A to the center by moving from the current edge pixel P a distance equal to the expected radius r in the direction of D (Fig. 10.7). Then repeat the process one edge pixel at a time until all edge pixels have been taken into account. Although intuition indicates that this strategy will lead to a good final approximation to the center, the situation is quite complex. There are two important questions:

1. Is the process guaranteed to converge?

2. How accurate is the final result?

Figure 10.7 Arrangement for obtaining improved center approximation.

There is a small range of boundary pixels for which the method described here gives a location A that is worse than the initial approximation D (see Fig. 10.8). However, this does not mean that our intuition is totally wrong, and theory confirms the usefulness of the approach when d is small (d « r). Figure 10.9 shows a set of graphs that map out the loci of points forming second approximations to the center positions for initial approximations at various distances d from the center. In each graph the locus is that obtained on moving around the periphery of the circle. Generally, for small d it is seen that the second approximation is on average a significantly better approximation than the initial approximation. Theory shows that for small d the mean result will be an improvement by a factor close to 1.6 (the limiting value as d → 0is π/2 (Davies, 1988e)). In order to prove this result, it is first necessary to show that as d approaches zero, the shape of the locus becomes a circle whose center is halfway between the original approximation D and the center C, and whose radius is d/2 (Fig. 10.9).

Figure 10.8 Boundary points that lead to a worse approximation.

Figure 10.9 Loci obtained for various starting approximations: (a) d = 0.17r;(b) d = 0.32r; (c) d = 0.50r;(d) d = 0.68r.

At first, an improvement factor of only ∼ 1.6 seems rather insignificant—until it is remembered that it should be obtainable for every circle boundary pixel. Since there are typically 200 to 400 such pixels (e.g., for r 50), the overall improvement

can in principle be virtually infinite. (Limitations on the actual accuracy are discussed later in this chapter.) However, to maximize the gain in accuracy, the order in which the algorithm processes boundary pixels should be randomized. (If this were not done, two adjacent pixels might often appear consecutively, the second giving negligible additional improvement in center location.)

10.5 Overcoming the Speed Problem

The previous section studied how the accuracy of the HT circle detection scheme could be improved substantially, with modest additional computational cost. This section examines how circle detection may be carried out with significant improvement in speed. There is a definite tradeoff between speed and accuracy, so that greater speed inevitably implies lower accuracy. However, at least the method to be adopted permits graceful degradation to take place.

One way to overcome the speed problem described in Section 10.2 is to sample the image data; another is to attempt to use a more rudimentary type of edge detection operator; and a third is to try to invent a totally new strategy for center location.

Sampling the image data tends to mean looking at, say, every third or fourth line, to obtain a speed increase by a factor of three or so. However, improvements beyond this are unlikely, for we would then be looking at much less of the boundary of the object and the method would tend to lose its robustness. An overall improvement in speed by more than an order of magnitude appears to be unattainable.

Using a more rudimentary edge detection operator would necessarily give much lower accuracy. For example, the Roberts cross operator (Roberts, 1965) could be used, but then the angular accuracy would drop by a factor of five or so (Abdou and Pratt, 1979), and in addition the effects of noise would increase markedly so that the operator would achieve nowhere near its intrinsic accuracy. With the Roberts cross operator, noise in any one of the four pixels in the neighborhood will make estimation of orientation totally erroneous, thereby invalidating the whole strategy of the center finding algorithm.

In this scenario Davies (1987) attempted to find a new strategy that would have some chance of maintaining the accuracy and robustness of the original approach, while improving speed by at least an order of magnitude. In particular, it would be useful to aim for improvement by a factor of three by sampling and by another factor of three by employing a very small neighborhood. By opting for a 2-element neighborhood, the capability of estimating edge orientation is lost. However, this approach still permits an alternative strategy based on bisecting horizontal and vertical chords of a circle. This approach requires two passes over the image to determine the center position fully. A similar amount of computation is needed as for a single application of a 4-element neighborhood edge detector, so it should be possible to gain the desired factor of three in speed relative to a Sobel operator via the reduced neighborhood size. Finally, the overall technique involves much less computation, the divisions, multiplications, and square root calculations being replaced by 2-element averaging operations, thereby giving a further gain in speed. Thus, the gain obtained by using this approach could be appreciably over an order of magnitude.

10.5.3 Experimental Results

Tests (Davies, 1987l) with the image in Fig. 10.10 showed that gains in speed of more than 25 can be obtained, with values of α down to less than 0.1 (i.e., every tenth horizontal and vertical line scanned). To obtain the same accuracy and reliability with smaller objects, a larger value of α was needed. This can be viewed as keeping the number of samples per object roughly constant. The maximum gain in speed was then by a factor of about 10. The results for broken circular products (Fig. 10.11 and 10.12) are self-explanatory; they indicate the limits to which the method can be taken and confirm that it is straightforward to set the algorithm up by eye. An outline of the complete algorithm is given in Fig. 10.14.

Figure 10.10 Successful object location using the chord bisection algorithm for the same initial image, using successive step sizes of 2, 4, and 8 pixels. The black dots show the positions of the horizontal and vertical chord bisectors, and the white dot shows the position found for the center.

Figure 10.11 Successful location of a broken object using the chord bisection algorithm: only about one-quarter of the ideal boundary is missing.

Figure 10.12 A test on overlapping and broken biscuits: the overlapping objects are successfully located, albeit with some difficulty, but there is no chance of finding the center of the broken biscuit since over one-half of the ideal boundary is missing.

Figure 10.14 Outline of the fast center-finding algorithm.

Figure 10.13 shows the effect of adjusting the threshold in the 2-element edge detector. The result of setting it too low is seen in Fig. 10.13a. Here the surface texture of the object has triggered the edge detector, and the chord midpoints give rise to a series of false estimates of the center coordinates. Figure 10.13b shows the result of setting the threshold at too high a level, so that the number of estimates of center coordinates is reduced and sensitivity suffers. The images in Fig. 10.10 were obtained with the threshold adjusted intuitively, but its value is nevertheless close to the optimum. However, a more rigorous approach can be taken by optimizing a suitable criterion function. There are two obvious functions: (1) the number of accurate center predictions n; and (2) the speed-sensitivity product. The speed-sensitivity product can be written in the form , where T is the execution time (the reason for the square root being as in Section 10.4.2). The two methods of optimization make little difference in the example of Fig. 10.13. However, had there

Figure 10.13 Effect of misadjustment of the gradient threshold: (a) effect of setting the threshold too low, so that surface texture muddles the algorithm; (b) loss of sensitivity on setting the threshold too high.

been a strong regular texture on the object, the situation would have been rather different.

10.6 Concluding Remarks

Although the Hough technique has been found to be effective and highly robust against occlusions, noise, and other artifacts, it incurs considerable storage and computation—especially if it is required to locate circles of unknown radius or if high accuracy is required. Techniques have been described whereby the latter two problems can be tackled much more efficiently. In addition, a method has been described for markedly reducing the computational load involved in circle detection. The general circle location scheme is a type of HT, but although the other two methods are related to the HT, they are distinct methods that draw on the HT for inspiration. As a result, they are rather less robust, although the degree of robustness is quite apparent and there is little risk of applying them when their use would be inappropriate. As remarked earlier, the HT achieves robustness as an integral part of its design. This is also true of the other techniques described, for which considerable care has been taken to include robustness as an intrinsic part of the design rather than as an afterthought.

As in the case of line detection, a trend running through the design of circle detection schemes is the deliberate splitting of algorithms into two or more stages. This consideration is useful for keying into the relevant parts of an image prior to finely discriminating one type of object or feature from another, or prior to measuring dimensions or other characteristics accurately. The concept can be taken further, in that all the algorithms discussed in this chapter have improved their efficiency by searching first for edge features in the image. The concept of two-stage template matching is therefore deep-seated in the methodology of the subject and is developed further in later chapters—notably those on ellipse and corner detection. Although two-stage template matching is a standard means of increasing efficiency (VanderBrug and Rosenfeld, 1977; Davies, 1988i), it is not at all obvious that it is always possible to increase efficiency by this means. It appears to be in the nature of the subject that ingenuity is needed to discover ways of achieving this efficiency.

10.7 Bibliographical and Historical Notes

The Hough transform was developed in 1962 and first applied to circle detection by Duda and Hart (1972). However, the now standard HT technique, which makes use of edge orientation information to reduce computation, only emerged three years later (Kimme et al., 1975). Davies’ work on circle detection for automated inspection required real-time implementation and also high accuracy. This spurred the development of the three main techniques described in Sections 10.3-10.5 of this chapter (Davies, 1987l, 1988b,e). In addition, Davies has considered the effect of noise on edge orientation computations, showing in particular their effect in reducing the accuracy of center location (Davies, 1987k).

Yuen, et al. (1989) reviewed various existing methods for circle detection using the HT. In general, their results confirmed the efficiency of the method of Section 10.3 for unknown circle radius, although they found that the two-stage process involved can sometimes lead to slight loss of robustness. It appears that this problem can be reduced in some cases by using a modified version of the algorithm of Gerig and Klein (1986). Note that the Gerig and Klein approach is itself a two-stage procedure: it is discussed in detail in the next chapter. More recently, Pan et al. (1995) have increased the speed of computation of the HT by prior grouping of edge pixels into arcs, for an underground pipe inspection application.

The two-stage template matching technique and related approaches for increasing search efficiency in digital images were known by 1977 (Nagel and Rosenfeld, 1972; Rosenfeld and VanderBrug, 1977; VanderBrug and Rosenfeld, 1977) and have undergone further development since then—especially in relation to particular applications such as those described in this chapter (Davies, 1988i).

Most recently, Atherton and Kerbyson (1999) (see also Kerbyson and Atherton, 1995) showed how to find circles of arbitrary radius in a single parameter space using the novel procedure of coding radius as a phase parameter and then performing accumulation with the resulting phase-coded annular kernel. Using this approach, they attained higher accuracy with noisy images. Goulermas and Liatsis (1998) showed how the Hough transform could be fine-tuned for the detection of fuzzy circular objects such as overlapping bubbles by using genetic algorithms. In effect, genetic algorithms are able to sample the solution space with very high efficiency and hand over cleaner data to the following Hough transform. Toennies et al. (2002) showed how the Hough transform can be used to localize the irises of human eyes for real-time applications, one advantage of the transform being its capability for coping with partial occlusion—a factor that is often quite serious with regard to the iris.

10.8 Problems

(b) A new method is suggested for circle location which involves scanning the image both horizontally and vertically. In each case, the midpoints of chords are determined and their x or y coordinates are accumulated in separate 1-D histograms. Show that these can be regarded as simple types of Hough transform, from which the positions of circles can be deduced. Discuss whether any problems would arise with this approach; consider also whether it would lead to any advantages relative to the standard Hough transform for circle detection.

(c) A further method is suggested for circle location. This again involves scanning the image horizontally, but in this case, for every chord that is found, an estimate is immediately made of the two points at which the center could lie, and votes are placed at those locations. Work out the geometry of this method, and determine whether it is faster than the method outlined in (b). Determine whether the method has any disadvantages compared with the method in (b).