On covering a digital disc with concentric circles in \(\mathbb Z^2\).(English)Zbl 1301.68235
Summary: Digital circles and digital discs satisfy many bizarre anisotropic properties, understanding of which is essential for solving various problems in image analysis and computer graphics. In this paper we study the underlying properties ofabsentee pixels that appear while covering a digital disc with concentric digital circles. We present, for the first time, a mathematical characterization of these pixels based on number theory and digital geometry. Interestingly, the absentees occur in multitude, and we show that their count varies quadratically with the radius. The notion ofinfimum parabola andsupremum parabola has been used to derive the count of these absentees. Using thisparabolic characterization, we derive a necessary and sufficient condition for a pixel to be adisc absentee, and obtain the geometric properties of the absentees. An algorithm to locate the absentees is presented. We show that the ratio of the absentee pixels to the total number of disc pixels approaches a constant with increasing radius. Test results have been furnished to substantiate our theoretical findings.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
digital circle;digital disc;digital geometry;geometry of numbers;image analysis;number theoryCite
Full Text:DOI
References:
| [1] | Badler, N. I., Disk generators for a raster display device, Comput. Graph. Image Process., 6, 589-593 (1977) |
| [2] | Bhowmick, P.; Bhattacharya, B. B., Number-theoretic interpretation and construction of a digital circle, Discrete Appl. Math., 156, 12, 2381-2399 (2008) ·Zbl 1143.68614 |
| [3] | Bhowmick, P.; Bera, S.; Bhattacharya, B. B., Digital circularity and its applications, (Proc. 13th International Workshop on Combinatorial Image Analysis. Proc. 13th International Workshop on Combinatorial Image Analysis, IWCIA 2009. Proc. 13th International Workshop on Combinatorial Image Analysis. Proc. 13th International Workshop on Combinatorial Image Analysis, IWCIA 2009, Lect. Notes Comput. Sci., vol. 5852 (2009), Springer), 1-15 ·Zbl 1267.68259 |
| [4] | Blinn, J. F., How many ways can you draw a circle?, IEEE Comput. Graph. Appl., 7, 8, 39-44 (1987) |
| [5] | Borwein, J. M.; Borwein, P. B., Ramanujan and Pi, Sci. Am., 258, 2, 112-117 (1988) ·Zbl 0652.10019 |
| [6] | Bresenham, J. E., A linear algorithm for incremental digital display of circular arcs, Commun. 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 Adv. Stud. Inst. Ser., vol. F17 (1985), Springer-Verlag: Springer-Verlag New York), 59-104 |
| [8] | Cappell, S. E.; Shaneson, J. L., Some problems in number theory I: The circle problem (2007) |
| [9] | Chan, Y. T.; Thomas, S. M., Cramer-Rao lower bounds for estimation of a circular arc center and its radius, Graph. Models Image Process., 57, 6, 527-532 (1995) ·Zbl 0853.68151 |
| [10] | Chattopadhyay, S.; Das, P. P.; Ghosh-Dastidar, D., Reconstruction of a digital circle, Pattern Recognit., 27, 12, 1663-1676 (1994) |
| [11] | Chen, T. C.; Chung, K. L., An efficient randomized algorithm for detecting circles, Comput. Vis. Image Underst., 83, 2, 172-191 (2001) ·Zbl 0995.68099 |
| [12] | Chiu, S. H.; Liaw, J. J., An effective voting method for circle detection, Pattern Recognit. Lett., 26, 2, 121-133 (2005) |
| [13] | Chung, W. L., On circle generation algorithms, Comput. Graph. Image Process., 6, 196-198 (1977) |
| [14] | Coeurjolly, D.; Gérard, Y.; Reveillès, J.-P.; Tougne, L., An elementary algorithm for digital arc segmentation, Discrete Appl. Math., 139, 31-50 (2004) ·Zbl 1077.68107 |
| [15] | Danielsson, P. E., Comments on circle generator for display devices, Comput. Graph. Image Process., 7, 2, 300-301 (1978) |
| [16] | Davies, E. R., A high speed algorithm for circular object detection, Pattern Recognit. Lett., 6, 323-333 (1987) |
| [17] | Davies, E. R., A hybrid sequential-parallel approach to accurate circle centre location, Pattern Recognit. Lett., 7, 279-290 (1988) |
| [18] | Doros, M., Algorithms for generation of discrete circles, rings, and disks, Comput. Graph. Image Process., 10, 366-371 (1979) |
| [19] | Doros, M., On some properties of the generation of discrete circular arcs on a square grid, Comput. Vis. Graph. Image Process., 28, 3, 377-383 (1984) |
| [20] | Erdös, P., On the irrationality of certain series: Problems and results, (Baker, A., New Advances in Transcendence Theory (1988), Cambridge University Press) ·Zbl 0656.10026 |
| [21] | Foley, J. D.; van Dam, A.; Feiner, S. K.; Hughes, J. F., Computer Graphics—Principles and Practice (1993), Addison-Wesley: Addison-Wesley Reading, MA |
| [22] | Haralick, R. M., A measure for circularity of digital figures, IEEE Trans. Syst. Man Cybern., 4, 394-396 (1974) ·Zbl 0277.68063 |
| [23] | Ho, C. T.; Chen, L. H., A fast ellipse/circle detector using geometric symmetry, Pattern Recognit., 28, 1, 117-124 (1995) |
| [24] | Horn, B. K.P., Circle generators for display devices, Comput. Graph. Image Process., 5, 2, 280-288 (1976) |
| [25] | Hsu, S. Y.; Chow, L. R.; Liu, C. H., A new approach for the generation of circles, Comput. Graph. Forum, 12, 2, 105-109 (1993) |
| [26] | Kim, H. S.; Kim, J. H., A two-step circle detection algorithm from the intersecting chords, Pattern Recognit. Lett., 22, 6-7, 787-798 (2001) ·Zbl 1010.68892 |
| [27] | Klette, R.; Rosenfeld, A., Digital Geometry: Geometric Methods for Digital Picture Analysis. Digital Geometry: Geometric Methods for Digital Picture Analysis, Morgan Kaufmann Ser. Comput. Graph. Geom. Model. (2004), Morgan Kaufmann: Morgan Kaufmann San Francisco ·Zbl 1064.68090 |
| [28] | Klette, R.; Rosenfeld, A., Digital straightness: A review, Discrete Appl. Math., 139, 1-3, 197-230 (2004) ·Zbl 1093.68656 |
| [29] | Kulpa, Z., A note on “circle generator for display devices”, Comput. Graph. Image Process., 9, 102-103 (1979) |
| [30] | Kulpa, Z.; Kruse, B., Algorithms for circular propagation in discrete images, Comput. Vis. Graph. Image Process., 24, 3, 305-328 (1983) |
| [31] | Lange, L. J., An elegant continued fraction for \(π\), Am. Math. Mon., 106, 5, 456-458 (1999) ·Zbl 0986.11004 |
| [32] | Mcllroy, M. D., Best approximate circles on integer grids, ACM Trans. Graph., 2, 4, 237-263 (1983) ·Zbl 0584.65005 |
| [33] | Mignosi, F., On the number of factors of Sturmian words, Theor. Comput. Sci., 82, 1, 71-84 (1991) ·Zbl 0728.68093 |
| [34] | Nagy, B., Characterization of digital circles in triangular grid, Pattern Recognit. Lett., 25, 11, 1231-1242 (2004) |
| [35] | Nagy, B.; Strand, R., Approximating Euclidean circles by neighbourhood sequences in a hexagonal grid, Theor. Comput. Sci., 412, 15, 1364-1377 (2011) ·Zbl 1207.68421 |
| [36] | Nakamura, A.; Aizawa, K., Digital circles, Comput. Vis. Graph. Image Process., 26, 2, 242-255 (1984) |
| [37] | Pal, S.; Bhowmick, P., Determining digital circularity using integer intervals, J. Math. Imaging Vis., 42, 1, 1-24 (2012) ·Zbl 1255.68262 |
| [38] | Pitteway, M. L.V., Integer circles, etc.—Some further thoughts, Comput. Graph. Image Process., 3, 262-265 (1974) |
| [39] | Pla, F., Recognition of partial circular shapes from segmented contours, Comput. Vis. Image Underst., 63, 2, 334-343 (1996) |
| [40] | Rosin, P. L.; West, G. A.W., Detection of circular arcs in images, (Proc. 4th Alvey Vision Conf.. Proc. 4th Alvey Vision Conf., Manchester (1988)), 259-263 |
| [41] | Shimizu, K., Algorithm for generating a digital circle on a triangular grid, Comput. Graph. Image Process., 15, 4, 401-402 (1981) |
| [42] | Stelldinger, P., Image Digitization and Its Influence on Shape Properties in Finite Dimensions (2007), IOS Press |
| [43] | Suenaga, Y.; Kamae, T.; Kobayashi, T., A high speed algorithm for the generation of straight lines and circular arcs, IEEE Trans. Comput., 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, Comput. Vis. Graph. Image Process., 45, 3, 362-370 (1989) |
| [45] | Worring, M.; Smeulders, A. W.M., Digitized circular arcs: Characterization and parameter estimation, IEEE Trans. Pattern Anal. Mach. Intell., 17, 6, 587-598 (1995) |
| [46] | Wright, W. E., Parallelization of Bresenhamʼs line and circle algorithms, IEEE Comput. Graph. Appl., 10, 5, 60-67 (1990) |
| [47] | Wu, X.; Rokne, J. G., Double-step incremental generation of lines and circles, Comput. Vis. Graph. Image Process., 37, 3, 331-344 (1987) |
| [48] | Yao, C.; Rokne, J. G., Hybrid scan-conversion of circles, IEEE Trans. Vis. Comput. Graph., 1, 4, 311-318 (1995) |
| [49] | Yuen, P. C.; Feng, G. C., A novel method for parameter estimation of digital arc, Pattern Recognit. Lett., 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.
