1 Introduction

In this paper, we propose a novel Multi-population genetic algorithm (MPGA) for accurate and efficient detection of multiple perfect/partial ellipses in noisy images. The capability the algorithm provides is genuinely useful for many real-world image processing applications, such as object detection and pattern recognition, scene characterization and event detection, etc.

Similar to the Island Model of genetic algorithms, we evolve a number of separate subpopulations that cluster around potential local optima. Communications between these subpopulations are governed by a clustering mechanism, which is closely interwoven with the local evolutionary processes of each subpopulation. In addition, the MPGA uses two complementary measures of fitness, which contribute to the diversity of the subpopulations. This algorithm also uses a special constructive form of mutation, which considerably enhances the probability of creating fitter individuals (from the original ones). These improvements in technique result in a robust and efficient algorithm, which performs very well on images with multiple ellipses, imperfect ellipses, and those containing significant levels of noise. Our experiments confirm that, and show that MPGA has clear advantages over the widely used randomized Hough transform (RHT) [18], as well as the sharing GA (SGA) [10].

Section 2 provides the reader with some necessary background material as well as a discussion between related techniques. In Sect. 3, the new algorithm is explained in detail. Section 4 presents and analyzes the experimental results with a comparison of MPGA, RHT and SGA. Section 5 concludes the paper and summarizes planned future work.

2 Background

This section provides a review of previous research work on the detection of primitive geometric shapes, as well as on multi-modal search and optimization.

2.1 Geometric primitive detection

There exist various techniques for detecting geometric primitives. In [19], short straight lines are extracted first, using a fast line extraction algorithm. The arc segments are then formed from these straight lines using a least-square algorithm. Finally, the arc segments are merged and used to calculate ellipse/circle parameters, using a least-square ellipse fitting algorithm.

Ke et al. [20] uses a Tabu search technique. Tabu search uses a tabu list (short-term memory), which keeps track of recent solutions, to prevent the search from becoming trapped in a local minimum. At each iteration, a number of new solutions around the current solution are generated. Among them, the best solution that is not tabu, or that is tabu but satisfies certain so-called aspiration conditions is set as the current solution. The search stops when a certain termination criterion is satisfied.

The Upwrite method [21] uses a spot algorithm to compute local models of pixels within a small resolution radius r. If r is small enough, the data in the neighborhood can be modeled with a straight line. The set of local models positioned along the same geometric primitive are then grouped together. Finally, each geometric feature is characterized by Zernike moments as: lines, circles, ellipses or other.

The Hough transform (HT) is one of the most widely used techniques for the detection of various geometric shapes [8]. It works by representing a geometric shape by a set of appropriate parameters, then accumulating bins in the quantized parameter space. Peaks in the bins provide the best indication of where shapes may be. Obviously, since the parameters are quantized into discrete bins, the intervals of the bins directly affect the accuracy of the results and the computational effort. For fine quantization of the space, the algorithm returns more accurate results, while suffering from large memory loads and expensive computation—especially in high-dimensional feature spaces. Hence, the SHT is most commonly used in 2D or 3D feature spaces and is unsuitable for higher dimensional spaces.

One of the fastest and most widely used variant of the Hough transform is the RHT proposed by Xu et al. [18]. In the RHT, a bin represents a candidate shape, rather than a set of quantized parameters, as in the SHT. However, like the SHT, the RHT goes through an accumulation process for the bins. The bin with the highest score represents the best approximation of an actual shape in the target image. McLaughlin’s work [13] shows that RHT produces improvements in accuracy and computational complexity, as well as a reduction in the number of false positives (non existent ellipses), when compared with the original HT and number of its improved variants.

Many HT-based methods have been developed. They improve on the efficiency of the HT by exploiting geometric characteristics of the ellipses, such as slope [5, 22, 24] and symmetry [7, 9], or by using intelligent means of dimensionality reduction [5, 7, 9, 22–24].

In [5] and [22], pairs of points on the ellipse are used to form lines that intersect at the center of the ellipse. Then, the semi-axis ratio and orientation of the ellipse are found, through a process that employs two 2D accumulators. Finally, the parameters of the major and minor axes of the ellipse are computed, using the set of four parameters found previously.

Cheng and Liu [24] use three points on an ellipse to locate the centre of the ellipse, with a mechanism similar to that used in [5] and [22], above. Then, they use an accumulator, similar to that used by the RHT, with bins representing candidate ellipses. However, they improve the efficiency of the RHT by applying the transform to a restricted sub-set of points, selected by a labeling algorithm.

Ho et al. [7] and Lei et al. [9] use properties of geometric symmetry of ellipses to calculate some parameters of an ellipse, such as the co-ordinates of the center, followed by the computation of the remaining parameters, such as the lengths of the major and minor axes.

Xie and Ji [23] use the two endpoints of the major axis and a third point on the ellipse to calculate various possible lengths for the minor axis, and then use a 1D accumulator to identify the most likely length of the minor axis.

The genetic algorithm (GA) is another interesting way for extracting ellipses. As early as 1992, Roth et al. [15] proposed a way of extracting geometric shapes using Genetic Algorithms. Since then, a number of GA-based techniques have been developed for the purpose of detecting specific geometric shapes such as straight lines [2], ellipses [10–12, 14, 25], and polygons [10–12].

Inspired by natural evolution, a GA encodes a potential solution as a chromosome, and evolves a population of chromosomes iteratively, until a satisfactory solution is found. A GA performs a parallel beam search, which may be viewed as a combination of a hill climber and a random searcher.

Kasemir and Betzler [25] combine a modified version of the Hough transform (HT) with a GA to detect ellipses of limited eccentricity. The HT identifies the best set of candidates, with a preset ellipse center. The GA searches a 2D space of ellipse centers, to locate the best center. As the authors state, given a population of size N, each iteration of the GA’s main loop, requires N runs of the HT. Therefore, this specific algorithm has very high computational demands.

Yin [26] adopts a hybrid scheme, which consists of a GA phase, and a local search phase. During the GA phase, a number of candidates with fitness values above a certain threshold are fed into the next phase. During the local search phase, a heuristic is used to produce the best set of candidate solutions, starting from the set of GA-generated candidates.

Lutton et al. [10] uses a SGA, first introduced by Goldberg et al. [3], to detect geometric primitives. We will explain the SGA, in some detail, in the next section.

Procter et al. [14] made an interesting comparison between GA and RHT. These two techniques have the following features in common:

  • Representation of geometric shapes using minimal sets of parameters.

  • Random sampling of image data.

  • Sequential extraction of multiple shapes.

Their experiments clearly demonstrate that GA-based techniques return superior results to those produced by RHT methods when a high level of noise is present in the image, but RHT methods are more attractive for relatively noise-fee images.

Indeed, for an elliptical curve with length L pixels in an image with a total of A pixels, the probability of locating this curve from a single sample is

$$P = \frac{{C^{n}_{L}}}{{C^{n}_{A}}}$$
(1)

where n is the dimensionality of the geometric shape and Cy X is the unordered selection of y pixels from the complete pixel set X.

With the same probability P, for each sampling and the same number of samples (say N), RHT gets N independent chances of detection when exploring the search space sequentially. In contrast, a GA explores the search space in parallel (using a population with size M), while guiding the search towards promising areas within N/M generations. Moreover, unlike the RHT, which locates peaks in the fitness surface after an exhaustive search of the space, a GA generates new improved individuals from existing ones, mainly through crossover and mutation. The RHT executes a blind sequential search, while a GA is able to search the space iteratively with feedback and in parallel. Hence, GA based algorithms have inherent strengths which, if properly used, can make them a better approach than any RHT based algorithm.

Of course, if there is only a small amount of noise in the image (L ≈ A and P ≈ 1), RHT will converge quickly, since each sampling has a high probability of locating the target shape. However, in cases where there is a lot of noise, multiple ellipses, or partial ellipses with some noise, RHT tends to overlook small elliptical curves, since Cn L decreases dramatically with a small L, which leads to an extremely small P. In this case, a GA-based algorithm is likely to converge faster, and exhibit more robustness as well as accuracy than the RHT. This conclusion matches the experimental results of Procter et al. [14] and is further supported by our own experiments (see Sect. 4).

In summary, the core of an HT-based technique is a polling process, which is equivalent to a blind sequential search of the search space. On the other hand, the core of a GA-based technique is a parallel semi-directed search of the search space. This inherent difference between these two approaches is at the root of their widely differing performances, as exhibited in our own experiments.

2.2 Multi-modal optimization

Roth and Levine [27] have shown that extracting a single geometric primitive is an optimization problem. Extracting multiple geometric primitives, therefore, falls into the category of multi-modal optimization, where several optima are sought.

An intuitive solution is to extract the primitives sequentially, as in [2, 14, 15], via appropriate ways of search. This entails removing detected primitives from the image, one at a time, and iterating, until there are no more candidates left in the image. Obviously this approach does not make good usage of GA’s implicit power of parallelism and suffers from high computational redundancy.

A standard GA, however, drives the population towards a single global optimum. In the presence of multiple optima, the final winner is obtained randomly. Moreover, when there are both perfect and imperfect candidates, the latter, being locally optimum, will most likely be replaced with better individuals during evolution, and eventually ignored.

Various methods have been used to enhance the diversity within a GA. Most of them fall into two broad categories: genetic operator-based techniques and population-based techniques. Sharing [3, 10] and Crowding [28] are examples of operator-based techniques, which use special genetic operators to reduce genetic drift. On the other hand, the multinational GA [29] and the forking GA [30] preserve diversity by explicitly manipulating a group of subpopulations, which are evolved independently, with little-to-no interbreeding between the subpopulations.

The SGA [3, 10] maintains the diversity of the population by scaling up the fitness of local optima, so that they would stand out. In this scheme, fitness is shared among similar individuals, and hence, the fitness of those individuals with many neighbors is decreased. Thus, population diversity is maintained by encouraging the exploration of less crowded regions of the fitness surface.

Unfortunately, Sharing is based on the assumption that the neighborhoods of local optima are less crowded than the neighborhood of the global optimum and therefore, the fitness of local optima will be enhanced by sharing. This assumption is not valid for the application of primitive extraction, as imperfect primitives may attract many neighbors with a high probability P, as long as they contain a sufficiently large number of pixels [refer to Eq. (1)]. This will deflect the search from exploring potentially promising areas, and will, often, result in missed candidates.

Figure 1 provides a concrete example. After running the SGA, to convergence, with a population size of 100, the individual at the center of the densest subpopulation is represented in Fig. 1b by an overlaid grey ellipse. Naturally, the left ellipse will attract more individuals around it since it is larger, while it corresponds to a local optimum (with suboptimal fitness). If the sharing function is applied, the fitness of the suboptimal individual will be shared with the rest of its dense neighborhood, resulting an even worse fitness than before. Therefore, sharing in this example defeats the purpose of the exercise.

Fig. 1
figure 1

Global and Local Optima. a a large imperfect ellipse (left) and a much smaller perfect ellipse (right). b Locally optimum candidate ellipse overlaid on top of left ellipse

Full size image

Furthermore, Smith et al. [16] highlighted the fact that the computation of the distance of an individual to any/all other individuals in a population has a time complexity of O(N2), where N is the size of the population.

Another issue associated with the SGA technique is that it runs an overall population of fixed size, with a number of variable-sized niches centered around different optima. Without a priori knowledge about the actual number of optima, it will be hard to estimate the appropriate size of the overall population, which, if too small, would result in missed potential optima, due to limited resources.

Unlike the SGA, the other school of GA variants, including the multinational GA [29] and the forking GA [30], maintain a variable number of fixed-sized subpopulations, with the number depending on the number of optima present. Therefore, every potential optimum is assured the same amount of computational resources, during exploration.

Taking into account the nature of the application, we developed and tested a new multiple-population GA, with the following key features:

  • A bi-objective fitness evaluation mechanism, which effectively enhances the diversity of the GA population.

  • Interwoven clustering and evolution processes, which maintain convergence of each sub-population towards the original local optimum (about which the cluster had been formed).

  • A specially designed mutation operator, which is effective in generating fitter candidate ellipses.

Experiments show that this algorithm works well with presence of multiple perfect/imperfect ellipses and high noise.

3 The multi-population genetic algorithm

The overall operation of the MPGA is presented graphically in Fig. 2.

Fig. 2
figure 2

Summary flow chart of MPGA Algorithm

Full size image

Initially, a single population is created by creating a number of chromosomes whose genes (see Sect. 3.2) are randomly selected from the set of foreground pixels in the image. The population is then evaluated and ranked using both fitness terms. A clustering technique divides the chromosomes into a number of clusters (or subpopulations), if necessary. From that moment on, all the subpopulations are evolved, in parallel. If one of them converges on an optimal chromosome, the whole subpopulation and corresponding ellipse in the image are removed. This has a positive side effect of accelerating the search process, since the search space is shrunk. The program, as a whole, terminates when all (full and partial) ellipses are found, or when a pre-set maximum number of generations is reached.

The following sections elaborate the details of key steps in our algorithm, starting with an introduction to elliptic geometry and concluding with evolution.

3.1 Ellipse geometry

Chromosomes, in the MPGA, are no more than candidate ellipses, and hence understanding the geometry of ellipses is essential to understanding chromosomal representation. The ellipse equation can be written as:

$$ax^{2} + 2hxy + by^{2} + 2gx + 2fy + 1 = 0$$
(2)

Assuming we have five distinct points on the perimeter of an ellipse, we can solve five linear equations to obtain a, h, b, g and f. Hence, the geometric parameters (the long and short radii of an ellipse, the co-ordinates of the center and the orientation with respect to the X axis) for an ellipse are computed, by substituting the values of a, h, b, g and f into a set of five equations, listed in [14].

3.2 Representation and initialization

We represent chromosomes with a minimal set of points on the shape’s perimeters, as in [15]. Specifically for ellipses, each chromosome contains five genes, each of which is a point with its horizontal and vertical coordinates.

There are, in the literature, alternative ways of chromosomal encoding. For example, Mainzer [11, 12] represents an ellipse directly using its five geometric parameters, i.e., major/minor axes, center, and orientation. While Lutton et al. [10] encode an ellipse using the center O; a point on its perimeter P; and rotation angle a. They claim that their representation is preferable to Roth’s representation, as the latter allows for redundancy, since different chromosomes (with different sets of five points) may refer to the same ellipse.

Nevertheless, the encoding of ellipses via their geometric parameters is problematic, as this does not guarantee the actual existence of the corresponding candidate ellipse. Unlike the minimal point-set representation, which uses five pixels on the perimeter of an ellipse (or elliptic curve), and only deals with real points on real curves, the parameter-based technique will spend at least part of their time evaluating non-existent ellipses.

We allow for phenotype duplicates, while ignoring the redundancy problem identified by Mainzer. A chromosome with a good genotype (i.e., one with five points, all lying on an actual ellipse) does not necessarily have optimum fitness. This is due to the digital displacement error of pixels. Redundancy enhances the possibility of obtaining new fitter chromosomes via (a) crossover of phenotypically close parents or (b) mutation of a highly fit chromosome.

The MPGA creates an initial population of 40 chromosomes. The five points comprising each new chromosome are selected, at random, from the set of foreground (or black) pixels in the target image.

3.3 Fitness evaluation

Most of the reported work in this area, such as [10–12], evaluates the fitness of a chromosome by, essentially, counting the number of black pixels in the target image that coincide with the perimeter of the candidate ellipse.

To enhance the robustness of the matching function, Mainzer [11, 12] distinguishes pixels lying near the perimeter of an ideal ellipse from those far from it, and assigns a penalty to the latter. Mainzer defines fitness S of a given candidate ellipse as

$$S = \sum\limits_{x,y}{\left({\mathop{{\text{MAX}}}\limits_{\forall i,j}} (E(x + i,y + j) - \frac{1}{c}(|i| + |j|))\right)}$$
(3)

Where E(x+i, y+j) is a function that returns 1 if there exists a foreground pixel (x+i, y+j) co-incident with, or close to a pixel (x,y) on the candidate ellipse. Otherwise the function returns 0. i and j are the horizontal and vertical displacements, respectively, between the two pixels. c is a constant determined by the nature of the image. Finally, MAX returns a maximal value over all combinations of i and j. The maximum is obtained whenever E(x+i, y+j) returns 1 and the second-term 1/c(|i|+|j|) returns a minimum. Equivalently, MAX looks for an appropriate pixel (x+i, y+j) that is closest to (x, y).

Lutton et al. [10] use a Chamfer distance map with each pixel assigned a grey value indicating its distance to the nearest contour point. This distance map is computed from the original image using two morphological masks. Like Mainzer, they also punish points not exactly on the perimeter of a candidate ellipse, using a displacement factor. The manual tuning of the two distance parameters in the mask requires extra preparatory work, before the algorithm can be used.

Lutton et al. [10] also introduced another fitness term that counts effective contour pixels “to favor bigger primitives”. However, bigger primitives are not necessarily better ones; and the extent to which an actual pattern matches a candidate shape has nothing to with the pattern’s absolute length or size.

In order to detect full as well as partial multiple ellipses with varying types and degrees of imperfections, we propose a bi-objective scheme, i.e., the fitness of a chromosome is measured in two terms: Similarity and Distance.

3.3.1 Similarity (S)

How much the actual pixels match the perimeter of an ideal complete ellipse. S is defined as:

$$S = \frac{\sum\limits_{(x,y)} {\frac{E(x + i,y + j)}{d_{x,y}}}}{\# {\text{total}}}$$
(4)

Like Mainzer’s definition above, for a given point (x, y) on the candidate ellipse, the term E(x+i,y+j) returns one, if there is a point (x+i, y+j) that coincides with, or is close to (x, y); otherwise E(x+i,y+j) returns 0. The terms i and j represent the horizontal and vertical displacements, respectively, between the “ideal” pixel (x, y) and the actual pixel (x+i, y+j). #total is the total number of pixels on the candidate ellipse’s perimeter. dx,y is a distance factor (note that it is different from the fitness term distance defined later) used to punish those pixels far away from the ideal pixel (x, y). It is given by

$$d_{{x,y}} = {\text{e}}^{{\frac{{|i| + |j|}}{4}}}$$
(5)

where e is the natural logarithm base, and i and j are the same terms of i and j in Eq. 4

Figure 3 shows how an actual point (Q) is determined with respect to an ideal point (P) and how the distance factor dx,y between them is computed. The dashed arc belongs to an ideal template with center C. The solid arcs are the actual pixels in the image. If P does not coincide with any point in the image, a line is originated from C passing through P. A fast search, based on Brensenham’s algorithm [6], is initiated from P, both outward and inward, along this line, until the first actual point is reached (Q). The horizontal and vertical displacements i and j between them are used to compute dx,y as in Eq. 5.

Fig. 3
figure 3

Matching of a candidate ellipse, point by point, to potential actual ellipses in an image

Full size image

To compute S efficiently, we further assume that the ideal template is centered at the origin of co-ordinates with a horizontally aligned long axis (Fig. 4). A classic midpoint ellipse algorithm [6] is then used to traverse the perimeter of this candidate ellipse. This algorithm favors integer computation and only computes a quarter of the ellipse’s perimeter. All the other points in the remaining three quadrants are obtained from symmetry. Each computed pixel is matched to its “actual” ideal position using

$${\left[\begin{array}{c}x' \\ y' \\ 1 \\ \end{array}\right]}= {\left[\begin{array}{ccc}\cos\theta & - \sin\theta& x_{0}\\ \sin\theta&\cos\theta& y_{0}\\ 0& 0& 1 \\ \end{array}\right]}{\left[\begin{array}{c}x\\ y \\ 1 \\ \end{array}\right]}$$
(6)

Where (x, y) are the original coordinates, (x′,y′) are the transformed coordinates, and θ is the orientation. Finally, the term E(x+i,y+j) is replaced by E′(x+i,y+j), giving us the final form of the similarity equation

$$S = \frac{\sum\limits_{(x,y)}\frac{E'(x + i,y +j)}{d_{x,y}}}{\# {\text{total}}}$$
(7)
Fig. 4
figure 4

2D geometric transformation of ellipse

Full size image

3.3.2 Distance (D)

how far or close is the actual pattern to the ideal ellipse. It is defined as:

$$D = \frac{\sum\limits_{(x,y)} {d_{x,y}}}{\# {\text{eff}}}$$
(8)

The term dx,y is defined in Eq. 5 above.#eff is the total number of actual points that are successfully matched with points on the ideal ellipse.

Figure 5 and Table 1 provide an intuitive explanation of these two fitness terms. The dashed arcs are ideal templates, with the detected ellipses, drawn using solid arcs. Ellipse 1 is a perfect ellipse, with Similarity S=0.995758 and Distance D=0.010167. (Ideally, the values should be 1 and 0, respectively. However, they are as such, due to digital rounding errors). Ellipse 2 is an incomplete pattern with the lowest Similarity among the three ellipses, while its Distance is as good as ellipse 1, since all its actual points lie exactly on the ideal template. Ellipse 3 is a complete but irregular ellipse. Its Similarity value lies between those for ellipses 1 and 2, while its Distance value is greater than both, due to its irregular segment AB, which is somewhat distant from the ideal trace.

Fig. 5
figure 5

Perfect and imperfect ellipses

Full size image
Table 1 Fitness of ellipses in Fig. 5
Full size table

The bi-objective fitness scheme enhances the probability of survival of candidate ellipses that have low fitness relative to one of the two fitness terms and high fitness relative to the other term. Indeed, if only one of the two fitness terms is used, then many imperfect but promising ellipses (such as ellipse 2 or 3) will eventually be deselected, resulting in a significant reduction in population diversity.

It is also worth stressing that the detection of more than one primitive shapes, ellipse or otherwise, in an image, is in essence a multi-modal optimization problem, where several optima are present. The essential challenge of such problems is to craft algorithms that do not focus the search on any one optimum point. Instead, the algorithm should proceed to explore all areas of potential optima. Hence, measures that increase the diversity of a GA population, such as the use of two (or more) fitness terms, may well lead to a more comprehensive search and, as our results will show, more comprehensive results.

3.4 Clustering: migration, splitting, and merging

The clustering process in the MPGA algorithm involves migration, splitting, and merging. The Euclidean distance ED between a chromosome and various existing cluster centers determines whether it remains in its own cluster or migrates. ED is computed as follows: given two sets of ellipse parameters (a1, b1, x1, y1, ω1) and (a2, b2, x2, y2, ω2):

$$ED = \frac{{{\sqrt{(a_{1} - a_{2})^{2} + (b_{1} - b_{2})^{2} + (x_{1} - x_{2})^{2} + (y_{1} - y_{2})^{2} + (\omega_{1} - \omega_{2})^{2}}}}}{5}$$
(9)

a i and b i are the long- and short-axes, respectively; (x i , y i ) is the center and ω i is the orientation. When a chromosome migrates from subpopulation A to subpopulation B, it replaces the weakest chromosome in the latter, and the vacancy in the former is filled by the processes of evolution (see Sect. 3.5).

3.4.1 Migration

If the Euclidean distance between a chromosome and its own cluster centre is lower than a pre-defined threshold, this chromosome migrates to another cluster with the closest centre to it.

3.4.2 Splitting

If there is not any cluster sufficiently close to the migrating chromosome, a new cluster is created around this chromosome. This action is called splitting.

3.4.3 Merging

An empirically derived threshold is used to define the minimum allowable Euclidean distance between any two different cluster centers. As two different clusters may evolve toward the same optimum, any two clusters sufficiently close to each other are merged, by mixing all chromosomes of them and taking the fittest 50% in the new cluster. This action is called merging.

All clusters are checked periodically to see whether some of them could be merged. Merging is barred, however, for earlier generations in order to allow steady clusters formed around the optima. Splitting and migration occur whenever a new chromosome (e.g., offspring, mutated individual, etc.) should be moved.

3.5 Evolution: selection and diversification

The MPGA is a bi-objective GA, since its fitness evaluation scheme uses two fitness terms. However, it is not a typical multi-objective optimizer that seeks a set of Pareto-optimal solutions [31], which satisfy several (usually conflicting) objective functions. The two objectives used in MPGA do not conflict with each other. On the contrary, they usually reach their optima concurrently. Therefore, the evolutionary strategies used are especially tailored to meet our requirements, and are not meant as general multiple-objective optimization strategies.

3.5.1 The evolutionary process

Evolution proceeds mainly via selection and diversification. Selection eliminates those chromosomes in the population that are not very fit, focusing the search on promising areas of the fitness surface. On the other hand, diversification directs the search towards new and potentially promising areas. In MPGA, selection is realized using elitism and fitness ranking selection. Diversification is realized via crossover and mutation.

Two rank-based lists are compiled for each subpopulation: one for Similarity and the other for Distance. Elitism copies the fittest 5% of the chromosomes in each of the two lists into the next generation, without modification. Following that, the parent pairs are selected based on a probability P. If P is larger than 0.5, the parents are randomly selected from the Similarity list, otherwise they are taken from the Distance list. In both cases, rank-based selection is performed, i.e., the probability of a chromosome to be selected is proportional to its relative ranking, rather than its raw fitness, in the subpopulation. The parents are mated, and offspring are put into the new generation.

Crossover continues until the number of chromosomes in the new generation reaches 90% of the preset subpopulation size. The remaining 10% is filled by randomly creating new chromosomes as described in Sect. 3.2. This operation is equivalent to discarding the worst 10% of a subpopulation and replacing them with newly created chromosomes.

Finally, mutation is applied to the whole subpopulation with a probability of 5%. Mutation is described in Sect. 3.5.3.

As stated in Sect. 3.4, every new chromosome introduced into the next generation is tested to see if it belongs to a different (or none of the) subpopulation(s) from the subpopulation that its predecessor(s) belonged to. If that is the case, an immediate action is taken, to either move the chromosome to a different existing subpopulation, or create a new subpopulation for it. This embedding of clustering within evolution ensures that the original direction of convergence within a subpopulation is maintained, despite the possible appearance of new highly fit and potentially distracting chromosomes.

3.5.2 Crossover

Given the fact that each chromosome is defined by a set of points on the perimeter of an ellipse, we can assert that simple single point crossover is an effective method. A pivot is selected at random, and the parent chromosomes’ genes on either side of the pivot are swapped to create the offspring, as shown in Fig. 6. A possible positive effect of the crossover is shown in Fig. 7.

Fig. 6
figure 6

Result of crossing-over two chromosomes: genotypic view

Full size image
Fig. 7
figure 7

Result of crossing-over two chromosomes: phenotypic view

Full size image

3.5.3 Mutation

A standard mutation randomly selects a gene (in our case: a pixel), and reassigns it a new value. This operation is global, in the sense that the new value of the gene is picked, at random, from all foreground pixels in an image. As an alternative, we define a localized mutation operator configured specifically for our application. First, a point is randomly selected from the chromosome (P1P2P3P4P5) that we intend to mutate, as shown in Fig. 8. Starting from this point (P1), a local path r is then traversed with a trace tracking algorithm, until a preset maximum number of points, or an end/intersection point, is reached. If r is large enough, the remaining four genes Q2–Q5 are picked, at random, from it. Therefore, the original chromosome (P1P2P3P4P5) is mutated into a new one (P1Q2Q3Q4Q5), with all the genes (P1, Q2, Q3, Q4, and Q5) lying on the same curve. Clearly, as long as the starting point lies on a promising candidate, it is highly possible that the other four points will too.

Fig. 8
figure 8

Mutation operation

Full size image

In summary, a localized mutation actually replaces four genes within a chromosome, while a standard mutation replaces only one; the former randomly picks up new points on a local path originating from a selected starting point, while the latter picks up new points, indiscriminately, from the whole image. Therefore, the new localized mutation enhances the possibility of mutating an existing candidate into a fitter one.

4 Experimental results and analysis

This section compares the performances of the MPGA, SGA, and RHT algorithms, using synthetic and real-world images. To carry out a fair comparison, we use the same numerical technique for computing the geometric parameters of an ellipse (see Sect. 3.1) and the same method for computing fitness (described in Sect. 3.3). For GA-based techniques (SGA and MPGA), the same genetic operators are used (e.g., crossover and mutation).

We have two main categories of test data, which are synthetic images and real world images. Accuracy is defined as the ratio of correctly detected ellipses with respect to the total number of ellipses actually present in the target image. Over detection is reflected in the false positive (fp) statistics. All the experiments were run on an Intel Xeon 2.66 GHz w/ 512 KB of cache, 512 MB DDR RAM and running Red Hat Linux 8.0.3.2–7.

4.1 Synthetic images

The synthetic images are comprised of two sets, set A and set B. Set A is partitioned into seven collections of 50 images each, totaling 350 images. These collections are used to test the algorithms’ performances on images with different number of ellipses. The first collection contains 50 images of single ellipse, the second collection contains images of two ellipses, and so on. The last collection contains 50 images of seven ellipses.

Set B, on the other hand, is used to test the algorithms’ performance on noisy images. This set is made of five collections of 50 images each, totaling 250 images. The first, second, third, fourth and fifth collections contain images with 0, 0.5, 1, 3 and 5% salt-and-pepper noise, respectively.

The ellipses in the synthetic image database are not all full and perfectly formed ellipses; we make sure that some images in both sets have at least one partial or deformed ellipse. A typical example is presented in Fig. 9, in which there are five ellipses, two of which are malformed. The figure also shows the results of applying MPGA, RHT, and SGA to this image.

Fig. 9
figure 9

A typical image with multiple ellipses: detected ellipses overlaid in thick grey. a Original image b Ellipses detected by MPGA c Ellipses detected by RHT d Ellipses detected by SGA

Full size image

As seen in Fig. 9c, RHT misses the smallest ellipse since (in line with Eq. 1) the probability of locating it is smaller than the probability of locating the other larger ellipses. The fitness values shown in Table 2 are Similarity only because Similarity is the only measure/factor of fitness used by all these three algorithms. Uniquely and exclusively, the bi-objective scheme is part of the core mechanism of the MPGA algorithm, while RHT and SGA do not use a second fitness term.

Table 2 Parameter Values of Ellipses Detected in Fig. 9
Full size table

In reference to Table 2, MPGA returns better fitness values than RHT for ellipses 1, 2 and 3. This is because MPGA, via evolution, executes an iterative and parallel search, focused at different localities of the search space, and is able to progressively improve the fitness of the candidates; while the RHT carries out a one-shot blind search through the whole space.

Figure 10 contrasts the performance of the three algorithms in terms of accuracy as well as average CPU running time. Figure 10a shows that the accuracy of SGA decreases dramatically as the number of ellipses increase. Similarly, the accuracy of RHT also decreases gradually from 100% for one ellipse to approximately 80% for seven ellipses. In contrast, MPGA outperforms the other two algorithms by maintaining an almost perfect level of detection accuracy, and slightly dipping to around 98%, for images with seven ellipses.

Fig. 10
figure 10

Comparing the performance of RHT, SGA and MPGA on detecting multiple ellipses. a Accuracy versus number of ellipses b CPU time versus number of ellipses

Full size image

Figure 10b demonstrates the clear advantage that MPGA has over both RHT and SGA with regards to speed. It graphs the amount of CPU time used by various algorithms with 1–7 ellipses. There is almost no difference in speed for images with four or less ellipses. However, for five or more ellipses, MPGA realizes a clear and widening gap.

Figure 11a shows a typical image with 5% pepper-and-salt noise (Table 3). Ellipses detected by MPGA are shown in Fig. 11b and Table 3.

Fig. 11
figure 11

A typical noisy image with 5% salt and pepper noise: detected ellipses overlaid in thick grey. a Original image b Ellipses detected by MPGA c Ellipses detected by RHT d Ellipses detected by SGA

Full size image
Table 3 Parameter values of ellipses detected in Fig. 11
Full size table

Generally, RHT is more liable to false positives (i.e., the detection of non existing ellipses), as demonstrated in Fig. 11c.

Figure 12 shows the performance of these algorithms on noisy images. Again, MPGA shows considerable robustness in the presence of salt-and-pepper noise, while simultaneously operating faster than the other two algorithms.

Fig. 12
figure 12

Comparing the performance of RHT, SGA and MPGA on detecting ellipses in noisy images. a Accuracy versus ratio of noise b CPU time versus ratio of noise

Full size image

Many false positives are observed for RHT with high noise, as Fig. 13 shows. This fact further fortifies our claim (in Sect. 1) that RHT searches the space and accumulates votes blindly.

Fig. 13
figure 13

False positives for different noise level

Full size image

4.2 Real-world images

A large, carefully constructed database of synthetic images (600, in our case) provides the bases for comprehensive tests, which give specific feedback about potential problems with detection algorithms. Nevertheless, it is real-world images that determine the difference between a genuinely useful and purely academic novel algorithm. Hence, we have amassed three databases of intentionally different types of images: hand-written English letters, microscopic cell images and road signs. The databases are of varying size, but contain images that were collected, prior to even the design of MPGA. From each of the databases, 50 images are selected at random and used for assessing the real-world performance of MPGA, RHA, and SGA. On visual inspection, we noticed that these images contain: all kinds of combinations of perfect and deformed ellipses, noise levels, and other geometric shapes (e.g. lines, polygons).

Figure 14a shows a typical handwritten character with elliptical curves detected.

Fig. 14
figure 14

A typical handwritten character: detected elliptical curve overlaid in thick grey—SGA Failed Completely. a Original image, b Elliptical curves detected by MPGA, c Elliptical curves detected by RHT

Full size image

In Table 4, we can see that MPGA is slower than RHT. As discussed in Sect. 1, when the image is relatively simple, noise-free and does not have many overlapping patterns, RHT is expected to run faster than MPGA. However, RHT still suffers from false positives, as Fig. 14c shows.

Table 4 Parameter values of ellipses detected in Fig. 14
Full size table

Figure 15a is a typical microscopic image of cells (Table 5). Again, MPGA shows its obvious advantage over RHT and SGA in both accuracy and speed. Although RHT approximates all eight cells, it suffers from large misplacement (see cells labeled: a, b, c and d in Fig. 15d, Table 5) and long running time; SGA fails to detect even a single ellipse.

Fig. 15
figure 15

A typical image of cells taken through a microscope (at 40×)—SGA failed to detect a single ellipse a Original image b Pre-processed image c Ellipses detected by MPGA d Ellipses detected by RHT

Full size image
Table 5 Parameter values of ellipses detected in Fig. 15
Full size table

Figure 16 is a typical image of a road sign (Table 6). We can see that neither RHT nor SGA is able to detect partial ellipses, especially when there are also perfect ellipses in the image. They are generally slower than MPGA in this kind of complicated images.

Fig. 16
figure 16

A typical road sign image. a Original image b Pre-processed image c Ellipses detected by MPGA d Ellipses detected by RHT e Ellipses detected by SGA

Full size image
Table 6 Parameter values of ellipses detected in Fig. 16
Full size table

Table 7 gives out the overall performance for real-world images. From the table, we can see that SGA is almost totally ineffective with complicated real world images; it returns an average accuracy of less than 20%. RHT suffers from long computation times and high fp rate. There are some fp (6.9048%) for MPGA as well, because the algorithm may sometimes approximate polygons with ellipses. One possible solution is to detect low-dimensional shapes first (e.g., lines) and remove them from the image, before detecting circles and ellipses. This way, the process can be both made more efficient and more accurate.

Table 7 Performance of MPGA, SGA, and RHT for real-world images
Full size table

5 Conclusions and future work

This paper presents a multi-population based GA, using a novel bi-objective scheme, specially configured genetic operator (e.g., mutation), and an elaborate process of evolution-clustering, to efficiently and accurately detect multiple, potentially deformed, full and partial ellipses in noisy images. This algorithm was thoroughly tested on a large number of synthetic and three types of real-world images, and compared to the very widely used RHT and one of the best-available GA-based ellipse detection technique—SGA. Despite the conceptual complexity of the MPGA algorithm, the program is, generally speaking, more efficient and accurate than both RHT and SGA. It can be easily extended to detect other geometric primitives. However, this does not mean that there is no room for improvements.

We intend to improve the MPGA by getting to

  1. 1.

    Detect other geometric primitives (e.g., lines and polygons) in order to analyze complicated scenery;

  2. 2.

    Run without the need for prior tuning of GA parameters, such as mutation and crossover probabilities. This can be done by incorporating the ideas of Parameterless GAs, which we have already successfully experimented with, but only using mathematically defined fitness surfaces.