Determining digital circularity using integer intervals.(English)Zbl 1255.68262
Summary: Digital circularity is a well-researched topic for its real-world practicality to circularity measure, estimation of discrete curvature, circular arc segmentation, etc. The proposed work reveals a novel technique to determine whether a digital curve segment is digitally circular using the correspondence of its constituent runs with the square numbers in integer intervals. The notion of radii nesting is used to successively analyze these runs of digital points. Two algorithms have been proposed along with their demonstrations and detailed analysis, and a simple-yet-effective solution has been provided to expedite them using infimum circle and supremum circles that bound the initial range of radii. We have also shown how the proposed technique can be used for segmentation of an arbitrary digital curve segment into a sequence of circular arcs. Experimental results have been given to demonstrate the efficiency and elegance of the proposed technique.
MSC:
| 68U10 | Computing methodologies for image processing |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Cite
Full Text:DOI
References:
| [1] | Andres, E.: Discrete circles, rings and spheres. Comput. Graph. 18(5), 695–706 (1994) ·doi:10.1016/0097-8493(94)90164-3 |
| [2] | Andres, E., Jacob, M.: The discrete analytical hyperspheres. IEEE Trans. Vis. Comput. Graph. 3(1), 75–86 (1997) ·doi:10.1109/2945.582354 |
| [3] | Asano, T., Klette, R., Ronse, C. (eds.): Geometry, Morphology, and Computational Imaging. LNCS, vol. 2616. Springer, Berlin (2003) ·Zbl 1017.00029 |
| [4] | Balog, A., Bárány, I.: On the convex hull of the integer points in a disc. In: Proc. 7th Annual Symposium on Computational Geometry (SCG 1991), pp. 162–165 (1991) |
| [5] | Barneva, R.P., Brimkov, V.E., Hauptman, H.A., Jorge, R.M.N., Tavares, J.M.R.S. (eds.) Computational Modeling of Objects Represented in Images, 2nd Intl. Symposium, CompIMAGE (2010). LNCS, vol. 6026. Springer, Berlin (2010) ·Zbl 1204.68002 |
| [6] | Bera, S., Bhowmick, P., Bhattacharya, B.B.: Detection of circular arcs in a digital image using chord and sagitta properties. In: Extended Version of Proc. Eighth Intl. Workshop on Graphics Recognition (GREC 2009). LNCS, vol. 6020, pp. 69–80 (2010) |
| [7] | 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 ·doi:10.1016/j.dam.2007.10.022 |
| [8] | Bresenham, J.E.: A linear algorithm for incremental digital display of circular arcs. Commun. ACM 20(2), 100–106 (1977) ·Zbl 0342.68058 ·doi:10.1145/359423.359432 |
| [9] | Brimkov, V., Coeurjolly, D., Klette, R.: Digital planarity–A review. Discrete Appl. Math. 155(4), 468–495 (2007) ·Zbl 1109.68122 ·doi:10.1016/j.dam.2006.08.004 |
| [10] | Brimkov, V.E., Barneva, R.P.: Graceful planes and lines. Theor. Comput. Sci. 283(1), 151–170 (2002) ·Zbl 1050.68147 ·doi:10.1016/S0304-3975(01)00061-5 |
| [11] | Brimkov, V.E., Barneva, R.P.: Connectivity of discrete planes. Theor. Comput. Sci. 319(1–3), 203–227 (2004) ·Zbl 1068.52018 ·doi:10.1016/j.tcs.2004.02.015 |
| [12] | Brimkov, V.E., Barneva, R.P.: On the polyhedral complexity of the integer points in a hyperball. Theor. Comput. Sci. 406(1–2), 24–30 (2008) ·Zbl 1151.52010 ·doi:10.1016/j.tcs.2008.07.014 |
| [13] | Chattopadhyay, S., Das, P.P., Ghosh-Dastidar, D.: Reconstruction of a digital circle. Pattern Recognit. 27(12), 1663–1676 (1994) ·doi:10.1016/0031-3203(94)90085-X |
| [14] | Chiu, S.H., Liaw, J.J.: An effective voting method for circle detection. Pattern Recognit. Lett. 26(2), 121–133 (2005) ·doi:10.1016/j.patrec.2004.09.037 |
| [15] | 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 ·doi:10.1016/j.dam.2003.08.003 |
| [16] | Coeurjolly, D., Miguet, S., Tougne, L.: Discrete curvature based on osculating circle estimation. In: IWVF-4: Proc. 4th Intl. Workshop Visual Form, pp. 303–312. Springer, London (2001) ·Zbl 0985.68540 |
| [17] | Coeurjolly, D., Sivignon, I., Dupont, F., Feschet, F., Chassery, J.-M.: On digital plane preimage structure. Discrete Appl. Math. 151(1–3), 78–92 (2005) ·Zbl 1101.68900 ·doi:10.1016/j.dam.2005.02.022 |
| [18] | Damaschke, P.: The linear time recognition of digital arcs. Pattern Recognit. Lett. 16, 543–548 (1995) ·Zbl 0837.68125 ·doi:10.1016/0167-8655(95)00127-3 |
| [19] | Davies, E.: Machine Vision: Theory, Algorithms, Praticalities. Academic Press, London (1990) |
| [20] | Davies, E.R.: A modified Hough scheme for general circle location. Pattern Recognit. 7(1), 37–43 (1984) ·doi:10.1016/0167-8655(88)90042-6 |
| [21] | Davies, E.R.: A high speed algorithm for circular object detection. Pattern Recognit. Lett. 6, 323–333 (1987) ·doi:10.1016/0167-8655(87)90015-8 |
| [22] | Debled-Rennesson, I., Reveilles, J.P.: A linear algorithm for segmentation of digital curves. Int. J. Pattern Recognit. Artif. Intell. 9, 635–662 (1995) ·doi:10.1142/S0218001495000249 |
| [23] | Dori, D., Liu, W.: Sparse pixel vectorization: An algorithm and its performance evaluation. IEEE Trans. PAMI 21(3) (1999) |
| [24] | Fisk, S.: Separating point sets by circles, and the recognition of digital disks. IEEE Trans. Pattern Anal. Mach. Intell. 8, 554–556 (1986) ·doi:10.1109/TPAMI.1986.4767821 |
| [25] | Foley, J.D., Dam, A.V., Feiner, S.K., Hughes, J.F.: Computer Graphics–Principles and Practice. Addison-Wesley, Reading (1993) ·Zbl 0875.68891 |
| [26] | Foresti, G.L., Regazzoni, C.S., Vernazza, G.: Circular arc extraction by direct clustering in a 3D Hough parameter space. Signal Process. 41, 203–224 (1995) ·Zbl 0875.68906 ·doi:10.1016/0165-1684(94)00101-5 |
| [27] | Freeman, H.: On the encoding of arbitrary geometric configurations. IRE Trans. Electron. Comput. EC-10, 260–268 (1961) ·doi:10.1109/TEC.1961.5219197 |
| [28] | Freeman, H.: Techniques for the digital computer analysis of chain-encoded arbitrary plane curves. In: Proc. National Electronics Conf., vol. 17, pp. 421–432 (1961) |
| [29] | Gonzalez, R.C., Woods, R.E.: Digital Image Processing. Addison-Wesley, Reading (1993) |
| [30] | Haralick, R.M.: A measure for circularity of digital figures. IEEE Trans. Syst. Man Cybern. 4, 394–396 (1974) ·Zbl 0277.68063 ·doi:10.1109/TSMC.1974.5408463 |
| [31] | Hilaire, X., Tombre, K.: Robust and accurate vectorization of line drawings. IEEE Trans. Pattern Anal. Mach. Intell. 28(6), 890–904 (2006) ·doi:10.1109/TPAMI.2006.127 |
| [32] | Ioannoua, D., Hudab, W., Lainec, A.: Circle recognition through a 2D Hough Transform and radius histogramming. Image Vis. Comput. 17, 15–26 (1999) ·doi:10.1016/S0262-8856(98)00090-0 |
| [33] | Kim, C.: Digital disks. IEEE Trans. Pattern Anal. Mach. Intell. 6, 372–374 (1984) ·Zbl 0531.68048 ·doi:10.1109/TPAMI.1984.4767531 |
| [34] | Kim, C.E., Anderson, T.A.: Digital disks and a digital compactness measure. In: Proc. 16th Annual ACM Symposium on Theory of Computing, pp. 117–124 (1984) |
| [35] | 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 ·doi:10.1016/S0167-8655(01)00020-4 |
| [36] | Klette, R.: Digital geometry–The birth of a new discipline. In: Davis, L.S. (ed.) Foundations of Image Understanding, pp. 33–71. Kluwer, Boston (2001) ·Zbl 1012.68549 |
| [37] | Klette, R., Rosenfeld, A.: Digital Geometry: Geometric Methods for Digital Picture Analysis. Morgan Kaufmann, San Francisco (2004) ·Zbl 1064.68090 |
| [38] | Klette, R., Žunić, J.: Interactions between number theory and image analysis. In: Latecki, L.J., Mount, D.M., Wu, A.Y. (eds.) Proc. SPIE, Vision Geometry IX, vol. 4117, pp. 210–221 (2000) |
| [39] | Kong, T.Y.: Digital topology. In: Davis, L.S. (ed.) Foundations of Image Understanding, pp. 33–71. Kluwer, Boston (2001) ·Zbl 0991.68129 |
| [40] | Kovalevsky, V.A.: New definition and fast recognition of digital straight segments and arcs. In: Proc. 10th Intl. Conf. Pattern Recognition (ICPR), pp. 31–34. IEEE Comput. Soc., Los Alamitos (1990) |
| [41] | Kulpa, Z., Kruse, B.: Algorithms for circular propagation in discrete images. Comput. Vis. Graph. Image Process. 24(3), 305–328 (1983) ·doi:10.1016/0734-189X(83)90058-0 |
| [42] | Lamiroy, B., Guebbas, Y.: Robust and precise circular arc detection. In: Extended Version of Proc. Eighth Intl. Workshop on Graphics Recognition (GREC 2009). LNCS, vol. 6020, pp. 49–60 (2010) |
| [43] | Latecki, L.J., Lakämper, R.: Shape similarity measure based on correspondence of visual parts. IEEE Trans. Pattern Anal. Mach. Intell. 22(10), 1185–1190 (2000) ·doi:10.1109/34.879802 |
| [44] | Leavers, V.: Survey: Which Hough transform? CVGIP, Image Underst. 58, 250–264 (1993) ·doi:10.1006/ciun.1993.1041 |
| [45] | McIlroy, M.D.: A note on discrete representation of lines. AT&T Bell Lab. Tech. J. 64(2), 481–490 (1985) |
| [46] | Megiddo, N.: Linear time algorithm for linear programming in \(\mathbb{R}\)3 and related problems. SIAM J. Comput. 12, 759–776 (1983) ·Zbl 0521.68034 ·doi:10.1137/0212052 |
| [47] | Nakamura, A., Aizawa, K.: Digital circles. Comput. Vis. Graph. Image Process. 26(2), 242–255 (1984) ·doi:10.1016/0734-189X(84)90187-7 |
| [48] | Nakamura, A., Rosenfeld, A.: Digital calculus. Inf. Sci. 98, 83–98 (1997) ·Zbl 0911.68215 ·doi:10.1016/S0020-0255(96)00194-6 |
| [49] | Nguyen, T.P., Debled-Rennesson, I.: A linear method for segmentation of digital arcs. Rapport de recherche no 0001 (Centre de recherche INRIA Nancy), Feb. 2010 |
| [50] | Pitteway, M.L.V.: Algorithm for drawing ellipses or hyperbolae with a digital plotter. Comput. J. 10(3), 282–289 (1967) ·Zbl 0148.40105 ·doi:10.1093/comjnl/10.3.282 |
| [51] | Richard, A., Wallet, G., Fuchs, L., Andres, E., Largeteau-Skapin, G.: Arithmetization of a circular arc. In: Proc. 15th IAPR International Conference on Discrete Geometry for Computer Imagery (DGCI ’09). LNCS, vol. 5810, pp. 350–361. Springer, Berlin (2009) ·Zbl 1261.65025 |
| [52] | Rodríguez, M., Abdoulaye, S., Largeteau-Skapin, G., Andres, E.: Generalized perpendicular bisector and circumcenter. In: Computational Modeling of Objects Represented in Images, 2nd Intl. Symposium, CompIMAGE (2010). LNCS, vol. 6026, pp. 1–10. Springer, Berlin (2010) ·Zbl 1272.68418 |
| [53] | Rosenfeld, A., Kak, A.C.: Digital Picture Processing, 2nd edn. Academic Press, New York (1982) ·Zbl 0564.94002 |
| [54] | Roussillon, T., Sivignon, I., Tougne, L.: Measure of circularity for parts of digital boundaries and its fast computation. Pattern Recognit. 43(1), 37–46 (2010) ·Zbl 1192.68606 ·doi:10.1016/j.patcog.2009.06.014 |
| [55] | Roussillon, T., Tougne, L., Sivignon, I.: On three constrained versions of the digital circular arc recognition problem. In: Proc. 15th IAPR International Conference on Discrete Geometry for Computer Imagery (DGCI ’09). LNCS, vol. 5810, pp. 34–45. Springer, Berlin (2009) ·Zbl 1261.68138 |
| [56] | Sauer, P.: On the recognition of digital circles in linear time. Comput. Geom. 2, 287–302 (1993) ·Zbl 0793.68196 ·doi:10.1016/0925-7721(93)90025-2 |
| [57] | Song, J.: An object oriented progressive-simplification based vectorzation system for engineering drawings: Model, algorithm, and performance. IEEE Trans. Pattern Anal. Mach. Intell. 24(8), 890–904 (2002) |
| [58] | Sonka, M., Hlavac, V., Boyle, R.: Image Processing, Analysis, and Machine Vision. Chapman and Hall, London (1993) |
| [59] | Worring, M., Smeulders, A.W.M.: Digitized circular arcs: Characterization and parameter estimation. IEEE Trans. Pattern Anal. Mach. Intell. 17(6), 587–598 (1995) ·doi:10.1109/34.387505 |
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.
