Real Polygonal Covers of Digital Discs - Some Theories and Experiments

ABSTRACT

There are several algorithms for digitization of a real disc (circle) to derive a digital disc, and also for finding the real disc corresponding to a digital disc. However, the correspondence of a digital disc with a regular polygon in the real plane is not well studied. This paper presents some theories and related experiments on setting the correspondence from a digital disc to its polygonal cover in the real plane. For an ideal regular polygon covering a digital disc, all the grid points of the digital disc should lie on and inside the polygon, and vice versa. That an ideal regular polygon corresponding to a digital disc is possible for some of the digital discs, especially for the ones having smaller radii, is shown. Further, for a disc whose ideal regular polygon is not possible, an approximate polygon, tending to the ideal one, is possible, in which the error of approximation can be controlled by the number of vertices of the approximate polygon. These (ideal or approximate) polygonal covers of digital discs have several applications in many problems of point set pattern matching. We have reported the conditions under which an ideal regular polygon always exists corresponding to a digital disc, and the conditions under which the existence of an ideal regular polygon becomes uncertain. Experimental results have been given to demonstrate the possibilities of approximation and the trade-off in terms of error versus the number of vertices in the approximate polygon.

REFERENCES

• 1: Agarwal, P. K., Erickson, J.: Geometric range searching and its relatives, in: Advances in Discrete and Computational Geometry (B. Chazelle, J. Goodman, R. Pollack, Eds.), AMS, Providence, 1998, 1-56.
• 2: Jerry Van Aken , Mark Novak, Curve-drawing algorithms for Raster displays, ACM Transactions on Graphics (TOG), v.4 n.2, p.147-169, April 1985 [doi>10.1145/282918.282943]
• 3: Alt, H., Guibas, L. J.: Discrete Geometric Shapes: Matching, Interpolation, and Approximation--A Survey, Report B 96-11, 1996, Freie Universität, Berlin.
• 4: Andres, E.: Discrete circles, rings and spheres, Computers & Graphics, 18(5), 1994, 695-706.
• 5: Eric Andres , Marie-Andrée Jacob, The Discrete Analytical Hyperspheres, IEEE Transactions on Visualization and Computer Graphics, v.3 n.1, p.75-86, January 1997 [doi>10.1109/2945.582354]
• 6: Henry S. Baird, Model-based image matching using location, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 7: Mark de Berg , Otfried Cheong , Marc van Kreveld , Mark Overmars, Computational Geometry: Algorithms and Applications, Springer-Verlag TELOS, Santa Clara, CA, 2008
• 8: Partha Bhowmick , Bhargab B. Bhattacharya, Approximate Fingerprint Matching Using Kd-Tree, Proceedings of the Pattern Recognition, 17th International Conference on (ICPR'04) Volume 1, p.544-547, August 23-26, 2004 [doi>10.1109/ICPR.2004.181]
• 9: Bhowmick, P., Bhattacharya, B. B.: Approximation of Digital Circles by Regular Polygons, Proc. Intl. Conf. Advances in Pattern Recognition (ICAPR), 3686, Springer, Berlin, 2005.
• 10: Partha Bhowmick , Bhargab Bhattacharya, Approximate Matching of Digital Point Sets Using a Novel Angular Tree, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.31 n.5, p.769-782, May 2009 [doi>10.1109/TPAMI.2007.70812]
• 11: James Blinn, How Many Ways Can You Draw a Circle?, IEEE Computer Graphics and Applications, v.7 n.8, p.39-44, August 1987 [doi>10.1109/MCG.1987.276918]
• 12: Jack Bresenham, A linear algorithm for incremental digital display of circular arcs, Communications of the ACM, v.20 n.2, p.100-106, Feb. 1977 [doi>10.1145/359423.359432]
• 13: Bresenham, J. E.: Run length slice algorithm for incremental lines, in: Fundamental Algorithms for Computer Graphics (R. A. Earnshaw, Ed.), vol. F17 of NATO ASI Series, Springer-Verlag, NY, 1985, 59-104.
• 14: Y. T. Chan , Samuel M. Thomas, Cramer-Rao lower bounds for estimation of a circular arc center and its radius, Graphical Models and Image Processing, v.57 n.6, p.527-532, Nov. 1995 [doi>10.1006/gmip.1995.1043]
• 15: Teh-Chuan Chen , Kuo-Liang Chung, An efficient randomized algorithm for detecting circles, Computer Vision and Image Understanding, v.83 n.2, p.172-191, August 2001 [doi>10.1006/cviu.2001.0923]
• 16: Shih-Hsuan Chiu , Jiun-Jian Liaw, An effective voting method for circle detection, Pattern Recognition Letters, v.26 n.2, p.121-133, 15 January 2005 [doi>10.1016/j.patrec.2004.09.037]
• 17: D. Coeurjolly , Y. Gérard , J.-P. Reveillés , L. Tougne, An elementary algorithm for digital arc segmentation, Discrete Applied Mathematics, v.139 n.1-3, p.31-50, 30 April 2004 [doi>10.1016/j.dam.2003.08.003]
• 18: Coifman, B., Beymer, D., McLauchlan, P., Malik, J.: A Real-Time Computer Vision System for Vehicle Tracking and Traffic Surveillance, Transportation Research: Part C, 6(4), 1998, 271-288.
• 19: Danielsson, P. E.: Comments On Circle Generator for Display Devices, Computer Graphics and Image Processing, 7(2), 1978, 300-301.
• 20: E. R. Davies, A high speed algorithm for circular object location, Pattern Recognition Letters, v.6 n.5, p.323-333, December 1, 1987 [doi>10.1016/0167-8655(87)90015-8]
• 21: E. R. Davies, A hybrid sequential-parallel approach to accurate circle centre location, Pattern Recognition, v.7 n.5, p.279-290, April 1984
• 22: Doros, M.: Algorithms for Generation of Discrete Circles, Rings, and Disks, Computer Graphics and Image Processing, 10, 1979, 366-371.
• 23: Doros, M.: On Some Properties of the Generation of Discrete Circular Arcs on a Square Grid, Computer Vision, Graphics, and Image Processing, 28(3), 1984, 377-383.
• 24: W. Eric L. Grimson, Object recognition by computer: the role of geometric constraints, MIT Press, Cambridge, MA, 1991
• 25: Dan Field, Algorithms for drawing anti-aliased circles and ellipses, Computer Vision, Graphics, and Image Processing, v.33 n.1, p.1-15, Jan. 1986 [doi>10.1016/0734-189X(86)90218-5]
• 26: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics: principles and practice (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 27: Freeman, H.: On the Encoding of Arbitrary Geometric Configurations, IRE Trans. Electronic Computers, EC-10, 1961, 260-268.
• 28: Freeman, H.: Techniques for the Digital Computer Analysis of Chain-encoded Arbitrary Plane Curves, Proc. National Electronics Conf., 17, 1961.
• 29: Haralick, R. M.: A Measure for Circularity of Digital Figures, IEEE Trans. Sys., Man & Cybern., 4, 1974, 394-396.
• 30: Ho, C. T., Chen, L. H.: A fast ellipse/circle detector using geometric symmetry, Pattern Recognition, 28(1), 1995, 117-124.
• 31: F. Hoffmann , K. Kriegel , C. Wenk, An applied point pattern matching problem: comparing 2D patterns of protein spots, Discrete Applied Mathematics, v.93 n.1, p.75-88, April 15, 1999 [doi>10.1016/S0166-218X(99)00007-4]
• 32: Hosur, P. I., Ma, K.-K.: A Novel Scheme for Progressive Polygon Approximation of Shape Contours, Proc. IEEE 3rd Workshop on Multimedia Signal Processing, 1999.
• 33: Hsu, S. Y., Chow, L. R., Liu, C. H.: A new approach for the generation of circles, Computer Graphics Forum 12, 2, 1993, 105-109.
• 34: Anil Jain , Lin Hong , Ruud Bolle, On-Line Fingerprint Verification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.4, p.302-314, April 1997 [doi>10.1109/34.587996]
• 35: Jiang, X., Yau, W. Y.: Fingerprint Minutiae Matching Based on the Local and Global Structures, Proc. 15th Intl. Conf. Pattern Recognition (ICPR), IEEE CS Press, 2000.
• 36: Heung-Soo Kim , Jong-Hwan Kim, A two-step circle detection algorithm from the intersecting chords, Pattern Recognition Letters, v.22 n.6-7, p.787-798, May 2001 [doi>10.1016/S0167-8655(01)00020-4]
• 37: Reinhard Klette , Azriel Rosenfeld, Digital Geometry: Geometric Methods for Digital Picture Analysis, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 38: Kulpa, Z., Kruse, B.: Algorithms for Circular Propagation in Discrete Images, Computer Vision, Graphics, and Image Processing, 24(3), December 1983, 305-328.
• 39: Likar, B., Pernus, F.: Automatic extraction of corresponding points for the registration of medical images, Med. Phys., 26(8), 1999, 1678-1686.
• 40: A Minutia Matching Algorithm in Fingerprint Verification, Proceedings of the International Conference on Pattern Recognition, p.4833, September 03-08, 2000
• 41: Maintz, J., Viergever, M.: A survey of medical image registration, IEEE Engineering in Medicine and Biology Magazine, 2(1), 1998, 1-36.
• 42: Anil K. Jain , David Maltoni, Handbook of Fingerprint Recognition, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 43: M. D. McIlroy, Best approximate circles on integer grids, ACM Transactions on Graphics (TOG), v.2 n.4, p.237-263, October 1983 [doi>10.1145/245.246]
• 44: David M. Mount , Nathan S. Netanyahu , Jacqueline Le Moigne, Improved algorithms for robust point pattern matching and applications to image registration, Proceedings of the fourteenth annual symposium on Computational geometry, p.155-164, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276902]
• 45: Benedek Nagy, Characterization of digital circles in triangular grid, Pattern Recognition Letters, v.25 n.11, p.1231-1242, August 2004 [doi>10.1016/j.patrec.2004.04.001]
• 46: Nakamura, A., Aizawa, K.: Digital circles, Computer Vision, Graphics, and Image Processing, 26(2), 1984, 242-255.
• 47: Panek, J., Vohradsky, J.: Point pattern matching in the analysis of two-dimensional gel electropherograms, Electrophoresis, 20, 1999, 3483-3491.
• 48: Pitteway, M. L. V.: Algorithm for drawing ellipses or hyperbolae with a digital plotter, The Computer Journal, 10(3), 1967, 282-289.
• 49: Pitteway, M. L. V.: Integer circles, etc. --Some further thoughts, Computer Graphics and Image Processing, 3, 1974, 262-265.
• 50: Filiberto Pla, Recognition of partial circular shapes from segmented contours, Computer Vision and Image Understanding, v.63 n.2, p.334-343, March 1996 [doi>10.1006/cviu.1996.0023]
• 51: Rosin, P. L., West, G. A.W.: Detection of circular arcs in images, Proc. 4th. Alvey Vision Conf., Manchester, 1988.
• 52: Shimizu, K.: Algorithm for Generating a Digital Circle on a Triangular Grid, Computer Graphics and Image Processing, 15(4), 1981, 401-402.
• 53: Y. Suenaga , T. Kamae , T. Kobayashi, A High-Speed Algorithm for the Generation of Straight Lines and Circular Arcs, IEEE Transactions on Computers, v.28 n.10, p.728-736, October 1979 [doi>10.1109/TC.1979.1675240]
• 54: Samuel M. Thomas , Y. T. Chan, A simple approach for the estimation of circular arc center and its radius, Computer Vision, Graphics, and Image Processing, v.45 n.3, p.362-370, March 1989 [doi>10.1016/0734-189X(89)90088-1]
• 55: Wegstein, J. H.: An Automated Fingerprint Identification System, US Govt. Publication,Washington, 1982.
• 56: Marcel Worring , Arnold W. M. Smeulders, Digitized Circular Arcs: Characterization and Parameter Estimation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.6, p.587-598, June 1995 [doi>10.1109/34.387505]
• 57: William E. Wright, Rendering: Parallelization of Bresenham's Line and Circle Algorithms, IEEE Computer Graphics and Applications, v.10 n.5, p.60-67, September 1990 [doi>10.1109/38.59038]
• 58: Xiaolin Wu , Jon G. Rokne, Double-step incremental generation of lines and circles, Computer Vision, Graphics, and Image Processing, v.37 n.3, p.331-344, March 1987 [doi>10.1016/0734-189X(87)90041-7]
• 59: Chengfu Yao , Jon G. Rokne, Hybrid Scan-Conversion of Circles, IEEE Transactions on Visualization and Computer Graphics, v.1 n.4, p.311-318, December 1995 [doi>10.1109/2945.485618]
• 60: P. C. Yuen , G. C. Feng, A novel method for parameter estimation of digital arc, Pattern Recognition Letters, v.17 n.9, p.929-938, Aug. 1, 1996 [doi>10.1016/0167-8655(96)00050-5]

INDEX TERMS

Keywords:
digital circle, digital disc, digital geometry, polygonal approximation