Concordia University's DEC LAB: Research at the DEC LAB

Concordia DEC Lab about us . courses . students . . publications . events . people . contact us

Fast and Robust GA-Based Ellipse Detection (cont'd)

4.2 Real World Images

Large, carefully constructed databases of synthetic images (600, in our case) provide the bases for comprehensive tests, which also provide 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 those databases, 50 images, are selected at random, and then used for the purpose of 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).

Fig. 15(a) shows a typical handwritten character with elliptical curves detected.

Fig. 15 A Typical Handwritten Character (Number 9): Detected Ellipses Overlaid in Thick Grey Line - SGA Failed to Detect a Single Ellipse (a) Original Image (b) Ellipses Detected by MPGA (c) Ellipses Detected by RHT (d) Ellipses Detected by SGA

Table 4 Parameter Values Ellipses Detected in Fig. 15

In Table 4 we can see that MPGA is slower than RHT. As discussed in section 1, when the image is relatively simple and 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. 15(c) shows, and generally, in pattern recognition, accuracy of detection is of a higher priority than speed of processing.

The extremely fast speed with MPGA for this kind of images is mainly due to our local mutation operator, which guarantees to locate a cell, no matter what pixel is selected as the seed.

Fig. 16 A Typical Image of Cells taken through a Microscope (at 40x) - SGA Failed to Detect a Single Ellipse (a) Original Image (b) Pre-processed Image (c) Ellipses Detected by MPGA (d) Ellipses Detected by RHT (e) Ellipses Detected by SGA

Table 5 Parameter Values Ellipses Detected in Fig. 16

Fig. 16(a) is a typical microscopic image of cells. Here, MPGA shows its obvious advantage over RHT and SGA in both accuracy and speed. Although RHT approximates most of the cells (8/10), it suffers from large misplacement (see cells labeled: a, b and c in Fig. 16(d)) and long running times; SGA only detects one cell in this case.

The extremely fast speed with MPGA for this kind of images is mainly due to our local mutation operator, which guarantees to locate a cell, no matter what pixel is selected as the seed.

Fig. 17 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

Table 6 Parameter Values Ellipses Detected in Fig. 17

Fig. 17 is a typical image of a road sign. 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.

Table 7 gives out the overall performance for real world images:

Table 7 Performance of MPGA, SGA, and RHT 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 false positive rate.

There are some false positives (6.9048%) for MPGA as well, because for some polygons, the algorithm may sometimes approximate them with ellipses. One possible solution is to detect low dimensional shapes first (such as lines), and remove these from the image, before detecting circles and ellipses. This way, the process can be both made more efficient and more accurate.

5. Conclusions and Future Work

This paper presents a new GA, one which uses (a) multiple-populations and an elaborate process of evolutionclustering to (b) efficiently and accurately detect (c) 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 implementing the new algorithm performed, generally speaking, more efficiently and more accurately than both RHT and SGA. However, this does not mean that there is no room for improvements.

We intend to improve the MPGA by getting to:

1. Detect (and remove) lines and polygons, first, so that any complicated images can be analyzed within a reasonable period of time;

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 experimented with, successfully, but only tested using mathematically-defined fitness surfaces.

6. Acknowledgments

Any one who wishes to receive a copy of the image databases or the program can send an e-mail to: kharma@ece.concordia.ca .

References

1. D.H. Ballard, "Generalizing the Hough Transform to Detect Arbitrary Shapes", Pattern Recognition, Vol. 13, No. 2, 1981, pp. 111-122

2. Samarjit Chakraborty and Kalyanmoy Deb, "Analytic Curve Detection from a Noisy Binary Edge Map Using Genetic Algorithm", PPSN, 1998, pp. 129-138

3. D. E. Goldberg and J. Richardson, "Genetic algorithms with sharing for multimodal function optimization," Proceeding of the 2nd Int. Conference on Genetic Algorithms, J. J. Grefenstette, Ed. Hillsdale, NJ: Lawrence Erlbaum, 1987, pp. 41-49

4. W. E. L. Grimson and D. P. Huttenlocher, "On the sensitivity of the Hough transform for object recognition", IEEE Trans. Pattern Anal. Machine Intelli., Vol. 12, No. 3, March 1990, pp. 255-274

5. N. Guil and E. L. Zapata, "Lower order circle and ellipse Hough Transform", Pattern Recognition, Vol.30, No.10, 1997, pp.1729-1744

6. Hearn and M. P. Baker, Computer Graphics C Version, D., Prentice Hall, Inc., 1997.

7. Chun-TA HO and Ling-Hwei Chen, "A Fast Ellipse/Circle Detector Using Geometric Symmetry", Pattern Recognition, Vol. 28, No.1, 1995, pp. 117-124

8. P.V.C. Hough, "Machine Analysis of Bubble Chamber Pictures", International Conference on High Energy Accelerators and Instrumentation, CERN, 1959

9. Yiwu Lei, Kok Cheong Wong, "Ellipse detection based on symmetry", Pattern Recognition Letters, Vol. 20, No. 1, January 1999, pp. 41-47

10. Evelyne Lutton and Patrice Martinez, "A Genetic Algorithm for the Detection of 2D Geometric Primitives in Images", Proceedings of the 12th International Conference on Pattern Recognition, Jerusalem, Israel, 9-13 October 1994, Vol. 1, pp. 526-528

11. Tomas Mainzer, "Genetic Algorithm for traffic sign detection", Applied Electronic 2002

12. Tomas Mainzer, "Genetic Algorithm for Shape Detection", Technical Report no. DCSE/TR-2002-06, University of West Bohemia, 2002

13. Robert A. McLaughlin, "Randomized Hough Transform: Improved ellipse detection with comparison", Pattern Recognition Letters, Vol. 19, No. 3-4, March 1998, pp. 299-305

14. S Procter and J Illingworth, "A Comparison of the Randomized Hough Transform and a Genetic Algorithm for Ellipse Detection", Pattern Recognition in Practice IV: multiple paradigms, comparative studies and hybrid systems, edited by E Gelsema and L Kanal, Elsevier Science Ltd., pp. 449-460

15. G. Roth and M. D. Levine. "Geometric primitive extraction using a genetic algorithm", IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 16, No. 9, September 1994, pp. 901-905

16. R. E. Smith, S. Forrest and A. S. Perelson, "Searching for diverse, cooperative populations with genetic algorithms", TCGA Report No. 92002, The University of Alabama, Dept. of Engineering Mechanics, 1992.

17. William H. Press et Al., Numerical Recipes in C, The Art of Scientific Computing Second Edition, Cambridge University Press, 1992, Chapter 2, pp. 43-50

18. Lei Xu, E.Oja, & P.Kultanen, "A New Curve Detection Method: Randomized Hough Transform (RHT)", Pattern Recognition Letters, Vol. 11, No. 5, May 1990, pp. 331-338