Number-theoretic interpretation and construction of a digital circle.(English)Zbl 1143.68614
Summary: This paper presents a new interpretation of a digital circle in terms of the distribution of square numbers in discrete intervals. The number-theoretic analysis that leads to many important properties of a digital circle succinctly captures the original perspectives of digital calculus and digital geometry for its visualization and characterization. To demonstrate the capability and efficacy of the proposed method, two simple algorithms for the construction of digital circles, based on simple number-theoretic concepts, have been reported. Both the algorithms require only a few primitive operations and are completely devoid of any floating-point computation. To speed up the computation, especially for circular arcs of high radii, a hybridized version of these two algorithms has been given. Experimental results have been furnished to elucidate the analytical power and algorithmic efficiency of the proposed approach. It has been also shown, how and why, for sufficiently high radius, the number-theoretic technique can expedite a circle construction algorithm.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 11Y50 | Computer solution of Diophantine equations |
| 11H55 | Quadratic forms (reduction theory, extreme forms, etc.) |
| 11D09 | Quadratic and bilinear Diophantine equations |
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
Cite
Full Text:DOI
References:
| [1] | Aken, J. R.V.; Novak, M., Curve-drawing algorithms for raster display, ACM Transactions on Graphics, 4, 2, 147-169 (1985) |
| [2] | Badler, N. I., Disk generators for a raster display device, Computer Graphics and Image Processing, 6, 589-593 (1977) |
| [3] | Bhowmick, P.; Bhattacharya, B. B., Approximation of digital circles by regular polygons, (Proc. Intl. Conf. Advances in Pattern Recognition, ICAPR. Proc. Intl. Conf. Advances in Pattern Recognition, ICAPR, LNCS, vol. 3686 (2005), Springer: Springer Berlin), 257-267 |
| [4] | Biswas, S. N.; Chaudhuri, B. B., On the generation of discrete circular objects and their properties, Computer Vision, Graphics, and Image Processing, 32, 2, 158-170 (1985) |
| [5] | Blinn, J. F., How many ways can you draw a circle?, IEEE Computer Graphics and Applications, 7, 8, 39-44 (1987) |
| [6] | Bresenham, J. E., A linear algorithm for incremental digital display of circular arcs, Communications of the ACM, 20, 2, 100-106 (1977) ·Zbl 0342.68058 |
| [7] | Bresenham, J. E., Run length slice algorithm for incremental lines, (Earnshaw, R. A., Fundamental Algorithms for Computer Graphics. Fundamental Algorithms for Computer Graphics, NATO ASI Series, vol. F17 (1985), Springer-Verlag: Springer-Verlag New York), 59-104 |
| [8] | 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, 527-532 (1995) ·Zbl 0853.68151 |
| [9] | Chattopadhyay, S.; Das, P. P.; Ghosh-Dastidar, D., Reconstruction of a digital circle, Pattern Recognition, 27, 12, 1663-1676 (1994) |
| [10] | Chen, T. C.; Chung, K. L., An efficient randomized algorithm for detecting circles, Computer Vision and Image Understanding, 83, 2, 172-191 (2001) ·Zbl 0995.68099 |
| [11] | Chiu, S. H.; Liaw, J. J., An effective voting method for circle detection, Pattern Recognition Letters, 26, 2, 121-133 (2005) |
| [12] | Chung, W. L., On circle generation algorithms, Computer Graphics and Image Processing, 6, 196-198 (1977) |
| [13] | Coeurjolly, D.; Gérard, Y.; Reveillès, J.-P.; Tougne, L., An elementary algorithm for digital arc segmentation, Discrete Applied Mathematics, 139, 31-50 (2004) ·Zbl 1077.68107 |
| [14] | Danielsson, P. E., Comments on circle generator for display devices, Computer Graphics and Image Processing, 7, 2, 300-301 (1978) |
| [15] | Davies, E. R., A high speed algorithm for circular object detection, Pattern Recognition Letters, 6, 323-333 (1987) |
| [16] | Davies, E. R., A hybrid sequential-parallel approach to accurate circle centre location, Pattern Recognition Letters, 7, 279-290 (1988) |
| [17] | Doros, M., Algorithms for generation of discrete circles, rings, and disks, Computer Graphics and Image Processing, 10, 366-371 (1979) |
| [18] | Doros, M., On some properties of the generation of discrete circular arcs on a square grid, Computer Vision, Graphics, and Image Processing, 28, 3, 377-383 (1984) |
| [19] | Field, D., Algorithms for drawing anti-aliased circles and ellipses, Computer Vision, Graphics, and Image Processing, 33, 1, 1-15 (1986) |
| [20] | Foley, J. D.; Dam, A.v.; Feiner, S. K.; Hughes, J. F., Computer Graphics — Principles and Practice (1993), Addison-Wesley: Addison-Wesley Reading, Mass. |
| [21] | Freeman, H., On the encoding of arbitrary geometric configurations, IRE Transactions on Electronic Computers, EC-10, 260-268 (1961) |
| [22] | Haralick, R. M., A measure for circularity of digital figures, IEEE Transactions on Systems, Man & Cybernetics, 4, 394-396 (1974) ·Zbl 0277.68063 |
| [23] | Ho, C. T.; Chen, L. H., A fast ellipse/circle detector using geometric symmetry, Pattern Recognition, 28, 1, 117-124 (1995) |
| [24] | Horn, B. K.P., Circle generators for display devices, Computer Graphics and Image Processing, 5, 2, 280-288 (1976) |
| [25] | P.I. Hosur, K.-K. Ma, A novel scheme for progressive polygon approximation of shape contours, in: Proc. IEEE 3rd Workshop on Multimedia Signal Processing, 1999, pp. 309-314; P.I. Hosur, K.-K. Ma, A novel scheme for progressive polygon approximation of shape contours, in: Proc. IEEE 3rd Workshop on Multimedia Signal Processing, 1999, pp. 309-314 |
| [26] | Hsu, S. Y.; Chow, L. R.; Liu, C. H., A new approach for the generation of circles, Computer Graphics Forum, 12, 2, 105-109 (1993) |
| [27] | Kim, H. S.; Kim, J. H., A two-step circle detection algorithm from the intersecting chords, Pattern Recognition Letters, 22, 6-7, 787-798 (2001) ·Zbl 1010.68892 |
| [28] | Klette, R.; Rosenfeld, A., (Digital Geometry: Geometric Methods for Digital Picture Analysis. Digital Geometry: Geometric Methods for Digital Picture Analysis, Morgan Kaufmann Series in Computer Graphics and Geometric Modeling (2004), Morgan Kaufmann: Morgan Kaufmann San Francisco) ·Zbl 1064.68090 |
| [29] | Klette, R.; Rosenfeld, A., Digital straightness: A review, Discrete Applied Mathematics, 139, 1-3, 197-230 (2004) ·Zbl 1093.68656 |
| [30] | Kulpa, Z., A note on “circle generator for display devices”, Computer Graphics and Image Processing, 9, January, 102-103 (1979) |
| [31] | Kulpa, Z.; Kruse, B., Algorithms for circular propagation in discrete images, Computer Vision, Graphics, and Image Processing, 24, 3, 305-328 (1983) |
| [32] | Langsam, Y.; Augenstein, M. J.; Tenenbaum, A. M., Data Structures Using C and C++ (2000), Prentice-Hall of India: Prentice-Hall of India New Delhi ·Zbl 0872.68027 |
| [33] | Mcllroy, M. D., Best approximate circles on integer grids, ACM Transactions on Graphics, 2, 4, 237-263 (1983) ·Zbl 0584.65005 |
| [34] | Mignosi, F., On the number of factors of Sturmian words, Theoretical Computer Science, 82, 1, 71-84 (1991) ·Zbl 0728.68093 |
| [35] | Nagy, B., Characterization of digital circles in triangular grid, Pattern Recognition Letters, 25, 11, 1231-1242 (2004) |
| [36] | Nakamura, A.; Aizawa, K., Digital circles, Computer Vision, Graphics, and Image Processing, 26, 2, 242-255 (1984) |
| [37] | Pitteway, M. L.V., Algorithm for drawing ellipses or hyperbolae with a digital plotter, The Computer Journal, 10, 3, 282-289 (1967) ·Zbl 0148.40105 |
| [38] | Pitteway, M. L.V., Integer circles, etc. — some further thoughts, Computer Graphics and Image Processing, 3, 262-265 (1974) |
| [39] | Pla, F., Recognition of partial circular shapes from segmented contours, Computer Vision and Image Understanding, 63, 2, 334-343 (1996) |
| [40] | P.L. Rosin, G.A.W. West, Detection of circular arcs in images, in: Proc. 4th. Alvey Vision Conf., Manchester, 1988, pp. 259-263; P.L. Rosin, G.A.W. West, Detection of circular arcs in images, in: Proc. 4th. Alvey Vision Conf., Manchester, 1988, pp. 259-263 |
| [41] | Shanks, D., Solved and Unsolved Problems in Number Theory (1993), AMS Chelsea Publishing: AMS Chelsea Publishing New York ·Zbl 0997.11503 |
| [42] | Shimizu, K., Algorithm for generating a digital circle on a triangular grid, Computer Graphics and Image Processing, 15, 4, 401-402 (1981) |
| [43] | Suenaga, Y.; Kamae, T.; Kobayashi, T., A high speed algorithm for the generation of straight lines and circular arcs, IEEE Transactions on Computers, 28, 728-736 (1979) ·Zbl 0422.68054 |
| [44] | 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, 362-370 (1989) |
| [45] | Worring, M.; Smeulders, A. W.M., Digitized circular arcs: Characterization and parameter estimation, IEEE Transactions on PAMI, 17, 6, 587-598 (1995) |
| [46] | Wright, W. E., Parallelization of Bresenham’s line and circle algorithms, IEEE Computer Graphics and Applications, 10, 5, 60-67 (1990) |
| [47] | Wu, X.; Rokne, J. G., Double-step incremental generation of lines and circles, Computer Vision, Graphics, and Image Processing, 37, 3, 331-344 (1987) |
| [48] | Yao, C.; Rokne, J. G., Hybrid scan-conversion of circles, IEEE Transactions on Visualization and Computer Graphics, 1, 4, 311-318 (1995) |
| [49] | Yuen, P. C.; Feng, G. C., A novel method for parameter estimation of digital arc, Pattern Recognition Letters, 17, 9, 929-938 (1996) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
