Real Polygonal Covers of Digital Discs - Some Theories and Experiments

• Autorzy: Bhowmick P. , Bhattacharya Bhargab.B.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

digital disc; digital circle; polygonal approximation; digital geometry

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 3-4
• Strony: 487--505
• Opis fizyczny: Bibliogr. 60 poz., wykr.

Twórcy

autor

Bhowmick P.

autor

Bhattacharya Bhargab.B.

• Computer Science & Engineering Department Indian Institute of Technology, Kharagpur, India [e-mail],

Bibliografia

• [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] Aken, J. R. V., Novak, M.: Curve-drawing algorithms for raster display, ACM Trans. Graphics, 4(2), 1985, 147-169.
• [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] Andres, E., Jacob, M.: The Discrete Analytical Hyperspheres, IEEE Trans. Visualization and Computer Graphics, 3(1), 1997, 75-86.
• [6] Baird, H. S.: Model-based image matching using location, MIT Press, 1985, Distinguished Dissertation Series.
• [7] Berg, M. D., Kreveld, M. V., Overmars, M., Schwarzkopf, O.: Computational Geometry Algorithms and Applications, Springer-Verlag, Berlin, 2000.
• [8] Bhowmick, P., Bhattacharya, B. B.: Approximate FingerprintMatching Using Kd-tree, Proc. 17th Intl. Conf. Pattern Recognition (ICPR), IEEE CS Press, 1, 2004.
• [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] Bhowmick, P., Bhattacharya, B. B.: Approximate Matching of Digital Point Sets Using a Novel Angular Tree, IEEE Trans. PAMI (doi.ieeecomputersociety.org/10.1109/TPAMI.2007.70812), 2007.
• [11] Blinn, J. F.: How many ways can you draw a circle?, IEEE Computer Graphics and Applications, 7(8), 1987, 39-44.
• [12] Bresenham, J. E.: A Linear Algorithm for Incremental Digital Display of Circular Arcs, Communications of the ACM, 20(2), 1977, 100-106.
• [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] Chan, Y. T., Thomas, S. M.: Cramer-Rao Lower Bounds for Estimation of a Circular Arc Center and Its Radius, Graphical Models and Image Processing, 57(6), 1995, 527-532.
• [15] Chen, T. C., Chung, K. L.: An Efficient Randomized Algorithm for Detecting Circles, Computer Vision and Image Understanding, 83(2), 2001, 172-191.
• [16] Chiu, S. H., Liaw, J. J.: An effective voting method for circle detection, Pattern Recognition Letters, 26(2), 2005, 121-133.
• [17] Coeurjolly, D., Gérard, Y., Reveillès, J.-P., Tougne, L.: An elementary algorithm for digital arc segmentation, Discrete Applied Mathematics, 139, 2004, 31-50.
• [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] Davies, E. R.: A High Speed Algorithm for Circular Object Detection, Pattern Recognition Letters, 6, 1987, 323-333.
• [21] Davies, E. R.: A Hybrid Sequential-Parallel Approach to Accurate Circle Centre Location, Pattern Recognition Letters, 7, 1988, 279-290.
• [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] Eric, W., Grimson, L.: Object Recognition by Computer: The Role of Geometric Constraints, MIT Press, 1990.
• [25] Field, D.: Algorithms for Drawing Anti-Aliased Circles and Ellipses, Computer Vision, Graphics, and Image Processing, 33(1), 1986, 1-15.
• [26] Foley, J. D., Dam, A. v., Feiner, S. K., Hughes, J. F.: Computer Graphics - Principles and Practice, Addison-Wesley, Reading (Mass.), 1993.
• [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] Hoffmann, F., Kriegel, K., Wenk, C.: An applied point pattern matching problem: Comparing 2D patterns of protein spots, Discrete Applied Mathematics, 93, 1999, 75-88.
• [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] Jain, A. K., Hong, L., Bolle, R.: On-Line Fingerprint Verification, IEEE Trans. PAMI, 19, 1997, 302-313.
• [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] Kim, H. S., Kim, J. H.: A two-step circle detection algorithm from the intersecting chords, Pattern Recognition Letters, 22(6-7), 2001, 787-798.
• [37] Klette, R., Rosenfeld, A.: Digital Geometry: Geometric Methods for Digital Picture Analysis, Morgan Kaufmann, San Francisco, 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] Luo, X., Tian, J., Wu, Y.: A Minutia Matching algorithm in Fingerprint Verification, Proc. 15th Intl. Conf. Pattern Recognition (ICPR), IEEE CS Press, 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] Maltoni, D., Maio, D., Jain, A. K., Prabhakar, S.: Handbook of Fingerprint Recognition, Springer-Verlag, New York, 2003.
• [43] Mcllroy, M. D.: Best approximate circles on integer grids, ACM Trans. Graphics, 2(4), 1983, 237-263.
• [44] Mount, D., Netanyahu, N., Lemoigne, J.: Improved algorithms for robust point pattern matching and applications to image registration, Proc. 14th Annual ACM Symposium on Computational Geometry, 1998.
• [45] Nagy, B.: Characterization of digital circles in triangular grid, Pattern Recognition Letters, 25(11), 2004, 1231-1242.
• [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] Pla, F.: Recognition of Partial Circular Shapes from Segmented Contours, Computer Vision and Image Understanding, 63(2), 1996, 334-343.
• [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] Suenaga, Y., Kamae, T., Kobayashi, T.: A High Speed Algorithm for the Generation of Straight Lines and Circular Arcs, IEEE Trans. Comput., 28, 1979, 728-736.
• [54] Thomas, S. M., Chan, Y. T.: A Simple Approach for the Estimation of Circular Arc Center and Its Radius, Computer Vision, Graphics, and Image Processing, 45(3), 1989, 362-370.
• [55] Wegstein, J. H.: An Automated Fingerprint Identification System, US Govt. Publication,Washington, 1982.
• [56] Worring, M., Smeulders, A. W. M.: Digitized Circular Arcs: Characterization and Parameter Estimation, IEEE Trans. PAMI, 17(6), 1995, 587-598.
• [57] Wright, W. E.: Parallelization of Bresenham's line and circle algorithms, IEEE Computer Graphics and Applications, 10(5), 1990, 60-67.
• [58] Wu, X., Rokne, J. G.: Double-Step Incremental Generation of Lines and Circles, Computer Vision, Graphics, and Image Processing, 37(3), 1987, 331-344.
• [59] Yao, C., Rokne, J. G.: Hybrid Scan-Conversion of Circles, IEEE Trans. Visualization and Computer Graphics, 1(4), 1995, 311-318.
• [60] Yuen, P. C., Feng, G. C.: A Novel Method for Parameter Estimation of Digital Arc, Pattern Recognition Letters, 17(9), 1996, 929-938.