(1) PAPER TITLE A multi-population genetic algorithm for robust and fast ellipse detection (2) AUTHORS Jie Yao Department of Electrical and Computer Engineering Concordia University, 1455 Blvd. de Maisonneuve O Montreal, QC, Canada, H3G1M8 j_yao@ece.concordia.ca (450)670-6018 Nawwaf Kharma Department of Electrical and Computer Engineering Concordia University, 1455 Blvd. de Maisonneuve O Montreal, QC, Canada, H3G1M8 kharma@ece.concordia.ca (514)848-2424 ext 7063 Peter Grogono Computer Science Department Concordia University, 1455 Blvd. de Maisonneuve O Montreal, QC, Canada, H3G1M8 grogono@cs.concordia.ca (514)848-2424 ext 3012 (3) CORRESPONDING AUTHOR Jie Yao (4) ABSTRACT This paper discusses a novel and effective technique for extracting multiple ellipses from an image, using a genetic algorithm with multiple populations (MPGA). MPGA evolves a number of subpopulations in parallel, each of which is clustered around an actual or perceived ellipse in the target image. The technique uses both evolution and clustering to direct the search for ellipses: full or partial. MPGA is explained in detail, and compared with both the widely used randomized Hough transform (RHT) and the sharing genetic algorithm (SGA). In thorough and fair experimental tests, using both synthetic and real-world images, MPGA exhibits solid advantages over RHT and SGA in terms of accuracy of recognition even in the presence of noise or/and multiple imperfect ellipses in an image and speed of computation. (5) CRITERIA (A) The result was patented as an invention in the past, is an improvement over a patented invention, or would qualify today as a patentable new invention. (B) The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal. (F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered. (6) STATEMENT ON WHY THESE CRITERIA ARE SATISFIED (A) The result was patented as an invention in the past, is an improvement over a patented invention, or would qualify today as a patentable new invention. I. The Hough Transform (HT), initially used in machine analysis of bubble chamber photographs, was patented in 1962 [1]. Following that Duda and Hart invented a generalized Hough Transform [2], which is universally used today to extract geometric shapes from digital images. II. The standard Hough Transform (SHT) is known to suffer from high memory load and computational cost. Hence it is most commonly used in 2-dimensional spaces, such as straight lines, and is unsuitable for higher dimensional spaces, such as ellipses. We use a novel form of Genetic Algorithm (GA), called multi-population based GA (MPGA), to detect ellipses effectively and efficiently. This approach yields an innovative enhancement over classic HT based techniques. III. We believe that our algorithm is patentable in the sense that it adopts a new bi-objective mechanism and a specially designed mutation operator, both of which enhance the performance of the algorithm dramatically. Up to our knowledge, they are new inventions that have not existed in the literature so far. (B) The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal. (F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered. I. In 1990, Xu et al. proposed a Randomized Hough Transform (RHT)[3]. By carrying out a new polling process different from that of the SHT, it mitigates the pitfalls of the latter and extends its applicability to high dimensional spaces. Deemed as a milestone of the HT family, the RHT has been the most popular and the fattest variant of HT since its invention. Its core mechanism is still adopted by various HT based techniques today. II. Due to its inherent limitation, the RHT tends to suffer from coarse approximation of boundaries, ignorance of smaller or weaker candidates, as well as high false positive rates. Our MPGA effectively overcomes these disadvantages. It was thoroughly tested and compared to the RHT on a large number of synthetic and real-world images. It has been demonstrated solidly that MPGA outperforms RHT in terms of efficiency, accuracy and robustness in the detection of multiple, potentially deformed and full/partial ellipses in noisy images. [1] Hough and P.V.C., Methods and Means for Recognizing Complex Patterns, U.S. Patent 3,069,654, 1962. [2] Duda, R. O. and P. E. Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures," Comm. ACM, Vol. 15, pp. 11-15, 1972. [3] L. Xu, E. Oja, and P. Kultanen. Anew curve detection method: Randomized Hough Transform (RHT). Pattern Recognition Letters, 11:331-338, 5 1990. (7) CITATION Yao, J., Kharma, N., and Grogono, P, "A multi-population genetic algorithm for robust and fast ellipse detection", Pattern Analysis & Applications, Volume 8, Issue 1 - 2, Sep 2005, pp. 149-162. (8) STATEMENT ON PRIZE MONEY Any prize money, if any, is to be divided equally among the co-authors (9) STATEMENT ON WHY THIS ENTRY IS THE BEST Geometric shape extraction/detection plays an important role in many real world image processing applications, such as object recognition, video surveillance, scene characterization and event detection, as well as medical imaging. Unlike detection of straight lines, detection of ellipses is a challenging problem because it is characterized by five geometric parameters and hence computationally demanding. The Hough Transform and its extensions are the best known classical geometric shape detection approaches. Although there have been a great variety of HT based techniques that intend to enhance the performance of the algorithms, they still have unavoidable drawbacks and their performance degrades substantially in the presence of multiple/deformed ellipses or high level of noise. Our MPGA is superior to the most popular HT based technique - RHT in that the former effectively overcomes the drawbacks of the latter and exhibits superior performance over it. From the paper, it can be seen that when the number of ellipses or the level of noise increases in the synthetic images, the detection accuracy of MPGA maintains on an almost perfect level, whereas the accuracy of RHT decreases dramatically. However, MPGA is faster than RHT and the disparity in their average CPU time becomes more and more manifest. Further, in the experiments with real-world images, MPGA achieved a much higher accuracy (92.761%) than RHT (64.387%) and a lower false positive rate (6.9048%) than RHT (18.633%), with the average CPU running time at a fraction of RHT. MPGA is also compared with another ellipse detection approach that adopts a sharing GA. Similarly, it outperforms the latter. The MPGA itself is easily extensible to detection of other geometric primitives.