Triangular covers of a digital object.(English)Zbl 1447.52028
Summary: An optimal geometric representation of a digital object in the form of minimum-area cover is important in image analysis and computer vision. The first algorithm, to the best of our knowledge, for constructing the minimum-area polygonal cover of a 2D digital object as perceived on a uniform triangular grid, is proposed here. The polygonal cover is triangular in the sense that its boundary consists of a sequence of edges on the underlying grid. The proposed algorithm is based on certain combinatorial properties of a digital object on a grid, and it computes the tightest cover in time linear in the perimeter of the object. Experimental results are presented to demonstrate the efficacy, robustness, and versatility of the algorithm, and they indicate that the runtime varies inversely with the grid size. The proposed study on triangular covers of digital objects will find many applications to pattern analysis and shape matching.
Cite
Full Text:DOI
References:
| [1] | Beeson, M.: Triangle tiling I: the tile is similar to ABC or has a right angle (2012). arXiv preprint arXiv:1206.2231 |
| [2] | Birch, CPD; Oom, SP; Beecham, JA, Rectangular and hexagonal grids used for observation, experiment and simulation in ecology, Ecol. Model., 206, 347-359, (2007) ·doi:10.1016/j.ecolmodel.2007.03.041 |
| [3] | Biswas, A; Bhowmick, P; Bhattacharya, BB, Construction of isothetic covers of a digital object: a combinatorial approach, J. Vis. Commun. Image Represent., 21, 295-310, (2010) ·doi:10.1016/j.jvcir.2010.02.001 |
| [4] | Bodini, O; Rémila, E, Tilings with trichromatic colored-edges triangles, Theor. Comput. Sci., 319, 59-70, (2004) ·Zbl 1043.05031 ·doi:10.1016/j.tcs.2004.02.021 |
| [5] | Butler, S; Chung, F; Graham, R; Laczkovich, M, Tiling polygons with lattice triangles, Discrete Comput. Geom., 44, 896-903, (2010) ·Zbl 1205.52013 ·doi:10.1007/s00454-010-9249-0 |
| [6] | Clason, RG, Tiling with Golden triangles and the Penrose rhombs using logo, J. Comput. Math. Sci. Teach., 9, 41-53, (1989) |
| [7] | Conway, JH; Lagarias, JC, Tiling with polyominoes and combinatorial group theory, J. Comb. Theory Ser. A, 53, 183-208, (1990) ·Zbl 0741.05019 ·doi:10.1016/0097-3165(90)90057-4 |
| [8] | Daniel, H., Tom, K., Elmar, L.: Exploring simple triangular and hexagonal grid polygons online (2010). arXiv preprint arXiv:1012.5253 |
| [9] | Das, B., Dutt, M., Biswas, A., Bhowmick, P., Bhattacharya, B.B.: A combinatorial technique for construction of triangular covers of digital objects. In: Proceedings of 16th International Workshop on Combinatorial Image Analysis (IWCIA 14), LNCS 8466, pp. 76-90. Springer (2014) ·Zbl 1486.68209 |
| [10] | Freeman, H, Algorithm for generating a digital straight line on a triangular grid, IEEE Trans. Comput., 100, 150-152, (1979) ·Zbl 0393.68099 ·doi:10.1109/TC.1979.1675305 |
| [11] | Gardner, M.: Knotted Doughnuts and Other Mathematical Entertainments. Freeman and Company, New York (1986) ·Zbl 0671.00002 |
| [12] | Goodman-Strauss, C, Regular production systems and triangle tilings, Theor. Comput. Sci., 410, 1534-1549, (2009) ·Zbl 1162.68019 ·doi:10.1016/j.tcs.2008.12.012 |
| [13] | Her, I, Geometric transformations on the hexagonal grid, IEEE Trans. Image Process., 4, 1213-1222, (1995) ·doi:10.1109/83.413166 |
| [14] | Innchyn, H, Geometric transformations on the hexagonal grid, IEEE Trans. Image Process., 4, 1213-1222, (1995) ·doi:10.1109/83.413166 |
| [15] | Klette, R., Rosenfeld, A.: Digital Geometry: Geometric Methods for Picture Analysis. Morgan Kaufmann, San Francisco (2004) ·Zbl 1064.68090 |
| [16] | Kocayusufoǧlu, İ, Trigonometry on iso-taxicab geometry, Math. Comput. Appl., 5, 201-212, (2000) ·Zbl 0982.53011 |
| [17] | Kocayusufoǧlu, İ; Ada, T, On the iso-taxicab trigonometry, Appl. Sci., 8, 101-111, (2006) ·Zbl 1121.51011 |
| [18] | Kocayusufoǧlu, İ; Özdamar, E, Connections and minimizing geodesics of taxicab geometry, Math. Comput. Appl., 5, 191-200, (2000) ·Zbl 0982.53012 |
| [19] | Krause, E.F.: Taxicab Geometry. Addison-Wesley, Menlo Park, NJ (1975) |
| [20] | Laczkovich, M, Tilings of convex polygons with congruent triangles, Discrete Comput. Geom., 48, 330-372, (2012) ·Zbl 1255.52016 ·doi:10.1007/s00454-012-9404-x |
| [21] | Levenshtein, A, Binary codes capable of correcting deletions, insertions and reversals, Sov. Phys. Dokl., 10, 707-710, (1966) ·Zbl 0149.15905 |
| [22] | Nagy, B.: Neighbourhood sequences in different grids. Ph.D. thesis, University of Debrecen (2003) ·Zbl 1026.68015 |
| [23] | Nagy, B, Characterization of digital circles in triangular grid, Pattern Recognit. Lett., 25, 1231-1242, (2004) ·doi:10.1016/j.patrec.2004.04.001 |
| [24] | Nagy, B, Generalised triangular grids in digital geometry, Acta Mathematica Academiae Paedagogicae Nyíregyháziensis, 20, 63-78, (2004) ·Zbl 1060.52502 |
| [25] | Nagy, B.: Cellular topology on the triangular grid. In: Proceedings of 15th International Workshop on Combinatorial Image Analysis (IWCIA 12), LNCS 7655, pp. 143-153. Springer (2012) ·Zbl 1377.68286 |
| [26] | Nagy, B; Barczi, K, Isoperimetrically optimal polygons in the triangular grid with Jordan-type neighbourhood on the boundary, Int. J. Comput. Math., 90, 1-24, (2012) ·Zbl 1276.68163 |
| [27] | Rosenfeld, A., Kak, A.: Digital Picture Processing, vol. 1. Elsevier, Amsterdam (2014) ·Zbl 0564.94002 |
| [28] | Shimizu, K, Algorithm for generating a digital circle on a triangular grid, Comput. Graph. Image Process., 15, 401-402, (1981) ·doi:10.1016/S0146-664X(81)80020-2 |
| [29] | Sowell, KO, Taxicab geometry—a new slant, Math. Mag., 62, 238-248, (1989) ·Zbl 0685.51011 |
| [30] | Subramanian, KG; Wiederhold, P, Generative models for pictures tiled by triangles, Sci. Technol., 15, 246-265, (2012) |
| [31] | Sury, B, Group theory and tiling problems, Symmetry Multi Discip. Perspect., 16, 97-117, (2011) ·Zbl 1356.52011 |
| [32] | Wagner, RA; Fischer, MJ, The string-to-string correction problem, J. ACM (JACM), 21, 168-173, (1974) ·Zbl 0278.68032 ·doi:10.1145/321796.321811 |
| [33] | Wüthrich, CA; Stucki, P, An algorithmic comparison between square-and hexagonal-based grids, CVGIP Graph. Models Image Process., 53, 324-339, (1991) ·doi:10.1016/1049-9652(91)90036-J |
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.
