Fast circular arc segmentation based on approximate circularity and cuboid graph.(English)Zbl 1361.68290
Summary: A fast and efficient algorithm for circular arc segmentation is presented. The algorithm is marked by several novel features includingapproximate circularity for arc detection,cuboid graph defined by the detected arcs in the 3D parameter space, and resolving alldelimited cliques in the cuboid graph to form larger arcs. As circular arcs present in a digitized document often deviate from the ideal conditions ofdigital circularity, we have loosened their radius intervals and center locations depending on anadaptive tolerance so as to detect the arcs by approximate circularity. The notion of approximate circularity is realized by modifying certain number-theoretic properties of digital circularity, which ensures that theisothetic deviation of each point in an input curve segment from the reported circle does not exceed the specified tolerance. Owing to integer computation and judiciousness of delimited cliques, the algorithm runs significantly fast even for very large images. Exhaustive experimentation with benchmark datasets demonstrate its speed, efficiency, and robustness.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Cite
Full Text:DOI
References:
| [1] | Andres, E.; Roussillon, T.; Debled-Rennesson, I. (ed.); etal., Analytical description of digital circles, No. 6607, 235-246 (2011), Berlin ·Zbl 1272.68349 |
| [2] | Andres, E.: Discrete circles, rings and spheres. Comput. Graph. 18(5), 695-706 (1994) ·doi:10.1016/0097-8493(94)90164-3 |
| [3] | Asano, T., Klette, R., Ronse, C. (eds.): Geometry, Morphology, and Computational Imaging. LNCS, vol. 2616. Springer, Berlin (2003) ·Zbl 1017.00029 |
| [4] | 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 |
| [5] | Bera, S.; Bhowmick, P.; Bhattacharya, B. B., Detection of circular arcs in a digital image using Chord and Sagitta properties, No. 6020, 69-80 (2010), Berlin |
| [6] | 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 |
| [7] | Bhowmick, P., Bhattacharya, B.B.: Real polygonal covers of digital discs—some theories and experiments. Fundam. Inform. 91(3-4), 487-505 (2009) ·Zbl 1191.68756 |
| [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] | Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16, 575-577 (1973) ·Zbl 0261.68018 ·doi:10.1145/362342.362367 |
| [11] | Cazals, F., Karande, C.: A note on the problem of reporting maximal cliques. Theor. Comput. Sci. 407(1-3), 564-568 (2008) ·Zbl 1153.68038 ·doi:10.1016/j.tcs.2008.05.010 |
| [12] | 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 |
| [13] | 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 ·doi:10.1006/cviu.2001.0923 |
| [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] | 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 |
| [17] | 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 |
| [18] | 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 |
| [19] | Eppstein, D., Strash, D.: Listing all maximal cliques in large sparse real-world graphs. CoRR (2011). arXiv:1103.0318 ·Zbl 1365.05276 |
| [20] | 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 |
| [21] | 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 |
| [22] | Gonzalez, R.C., Woods, R.E.: Digital Image Processing. Addison-Wesley, Reading (1993) |
| [23] | Seventh IAPR international workshop on Graphics RECognition (GREC 2007). http://www.iupr.org/arcseg2007 |
| [24] | Ninth IAPR international workshop on Graphics RECognition (GREC 2011). http://grec2011.cau.ac.kr/ArcSeg.html ·Zbl 1255.68245 |
| [25] | de Guevara, I.L., Muñoz, J., de Cózar, O., Blázquez, E.: Robust fitting of circle arcs. J. Math. Imaging Vis. 40, 147-161 (2011) ·Zbl 1255.68245 ·doi:10.1007/s10851-010-0249-8 |
| [26] | Gutin, G.; Gross, J. L. (ed.); Yellin, J. (ed.), Independent sets and cliques (2004), Boca Raton |
| [27] | 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 |
| [28] | 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 |
| [29] | Ho, C.T., Chen, L.H.: A fast ellipse/circle detector using geometric symmetry. Pattern Recognit. 28(1), 117-124 (1995) ·doi:10.1016/0031-3203(94)00077-Y |
| [30] | Illingworth, J., Kittler, J.: A survey of the Hough transform. Comput. Vis. Graph. Image Process. 44(1), 87-116 (1988) ·doi:10.1016/S0734-189X(88)80033-1 |
| [31] | 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 |
| [32] | 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 |
| [33] | Kimme, C., Ballard, D., Sklansky, J.: Finding circles by an array of accumulators. Commun. ACM 18(2), 120-122 (1975) ·Zbl 0296.68099 ·doi:10.1145/360666.360677 |
| [34] | Klette, R.; Davis, L. S. (ed.), Digital geometry—the birth of a new discipline, 33-71 (2001), Boston ·Zbl 1012.68549 ·doi:10.1007/978-1-4615-1529-6_2 |
| [35] | Klette, R.; Žunić, J.; Latecki, L. J. (ed.); Mount, D. M. (ed.); Wu, A. Y. (ed.), Interactions between number theory and image analysis, No. 4117, 210-221 (2000), Belingham ·doi:10.1117/12.404823 |
| [36] | Klette, R., Rosenfeld, A.: Digital Geometry: Geometric Methods for Digital Picture Analysis. Morgan Kaufmann, San Francisco (2004) ·Zbl 1064.68090 |
| [37] | Kovalevsky, V. A., New definition and fast recognition of digital straight segments and arcs, 31-34 (1990), Los Alamitos |
| [38] | 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 |
| [39] | 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 |
| [40] | Leavers, V.: Survey: Which Hough transform? Comput. Vis. Graph. Image Process. 58(2), 250-264 (1993) ·doi:10.1006/cviu.1993.1043 |
| [41] | 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 |
| [42] | Nakamura, A., Aizawa, K.: Digital circles. Comput. Vis. Graph. Image Process. 26(2), 242-255 (1984) ·doi:10.1016/0734-189X(84)90187-7 |
| [43] | Nguyen, T.P., Debled-Rennesson, I.: A linear method for segmentation of digital arcs. Rapport de recherche n∘ 0001, Centre de recherche INRIA Nancy (Feb 2010) |
| [44] | Pal, S., Bhowmick, P.: Determining digital circularity using integer intervals. J. Math. Imaging Vis. 42(1), 1-24 (2011) ·Zbl 1255.68262 ·doi:10.1007/s10851-011-0270-6 |
| [45] | 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 |
| [46] | Ritter, N., Cooper, J.: New resolution independent measures of circularity. J. Math. Imaging Vis. 35(2), 117-127 (2009) ·doi:10.1007/s10851-009-0158-x |
| [47] | Rodríguez, M.; Abdoulaye, S.; Largeteau-Skapin, G.; Andres, E., Generalized perpendicular bisector and circumcenter, No. 6026, 1-10 (2010), Berlin ·Zbl 1272.68418 ·doi:10.1007/978-3-642-12712-0_1 |
| [48] | 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 |
| [49] | 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 |
| [50] | Simmons, C., Maguire, D., Phelps, N.: Manual of Engineering Drawing. Technical Product Specification and Documentation to British and International Standards, 3rd edn. Elsevier, Amsterdam (2010) |
| [51] | Song, J.: An object oriented progressive-simplification based vectorization system for engineering drawings: model, algorithm, and performance. IEEE Trans. Pattern Anal. Mach. Intell. 24(8), 890-904 (2002) |
| [52] | Tsai, C.-M., Lee, H.-J.: Binarization of color document images via luminance and saturation color features. IEEE Trans. Image Process. 11(4), 434-451 (2002) ·doi:10.1109/TIP.2002.999677 |
| [53] | 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 |
| [54] | Xu, L., Oja, E.: Randomized Hough transform (RHT): basic mechanisms, algorithms, and computational complexities. CVGIP, Image Underst. 57(2), 131-154 (1993) ·doi:10.1006/ciun.1993.1009 |
| [55] | Yip, R., Tam, P., Leung, D.: Modification of Hough transform for circles and ellipses detection using a 2-dimensional array. Pattern Recognit. 25(9), 1007-1022 (1992) ·doi:10.1016/0031-3203(92)90064-P |
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.
