A combinatorial technique for construction of triangular covers of digital objects.(English)Zbl 1486.68209
Barneva, Reneta P. (ed.) et al., Combinatorial image analysis. 16th international workshop, IWCIA 2014, Brno, Czech Republic, May 28–30, 2014. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8466, 76-90 (2014).
Summary: The construction of a minimum-area geometric cover of a digital object is important in many fields of image analysis and computer vision. We propose here the first algorithm for constructing a minimum-area polygonal cover of a 2D digital object as perceived on a uniform triangular grid. 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 perimeter of the object. We present experimental results to demonstrate the efficacy, robustness, and versatility of the algorithm, and they indicate that the runtime varies inversely with the grid size.
For the entire collection see [Zbl 1327.68010].
For the entire collection see [Zbl 1327.68010].
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68T45 | Machine vision and scene understanding |
| 68U10 | Computing methodologies for image processing |
Cite
Full Text:DOI
References:
| [1] | Beeson, M., Triangle tiling I: The tile is similar to ABC or has a right angle, arXiv preprint, arXiv, 1206-2231 (2012) |
| [2] | Birch, C. P.D.; Oom, S. P.; Beecham, J. A., Rectangular and hexagonal grids used for observation, experiment and simulation in ecology, Ecological Modelling, 206, 3, 347-359 (2007) ·doi:10.1016/j.ecolmodel.2007.03.041 |
| [3] | Biswas, A.; Bhowmick, P.; Bhattacharya, B. B., Construction of isothetic covers of a digital object: A combinatorial approach, Journal of Visual Communication and Image Representation, 21, 4, 295-310 (2010) ·doi:10.1016/j.jvcir.2010.02.001 |
| [4] | Bodini, O.; Rémila, E., Tilings with trichromatic colored-edges triangles, Theoretical Computer Science, 319, 1, 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 & Computational Geometry, 44, 4, 896-903 (2010) ·Zbl 1205.52013 ·doi:10.1007/s00454-010-9249-0 |
| [6] | Clason, R. G., Tiling with golden triangles and the penrose rhombs using logo, Journal of Computers in Mathematics and Science Teaching, 9, 2, 41-53 (1989) |
| [7] | Conway, J. H.; Lagarias, J. C., Tiling with polyominoes and combinatorial group theory, Journal of Combinatorial Theory, Series A, 53, 2, 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, arXiv preprint, arXiv, 1012-5253 (2010) |
| [9] | Freeman, H., Algorithm for generating a digital straight line on a triangular grid, IEEE Transactions on Computers, 100, 2, 150-152 (1979) ·Zbl 0393.68099 ·doi:10.1109/TC.1979.1675305 |
| [10] | Gardner, M., Knotted Doughnuts and Other Mathematical Entertainments (1986), New York: Freeman and Company, New York ·Zbl 0671.00002 |
| [11] | Goodman-Strauss, C., Regular production systems and triangle tilings, Theoretical Computer Science, 410, 16, 1534-1549 (2009) ·Zbl 1162.68019 ·doi:10.1016/j.tcs.2008.12.012 |
| [12] | Innchyn, H., Geometric transformations on the hexagonal grid, IEEE Transactions on Image Processing, 4, 9, 1213-1222 (1995) ·doi:10.1109/83.413166 |
| [13] | Klette, R.; Rosenfeld, A., Digital Geometry: Geometric Methods for Picture Analysis (2004), San Francisco: Morgan Kaufmann, San Francisco ·Zbl 1064.68090 |
| [14] | Laczkovich, M., Tilings of convex polygons with congruent triangles, Discrete & Computational Geometry, 48, 2, 330-372 (2012) ·Zbl 1255.52016 ·doi:10.1007/s00454-012-9404-x |
| [15] | Luczak, E.; Rosenfeld, A., Distance on a hexagonal grid, IEEE Transactions on Computers, 25, 5, 532-533 (1976) ·Zbl 0337.68065 ·doi:10.1109/TC.1976.1674642 |
| [16] | Nagy, B.: Neighbourhood sequences in different grids. Ph.D. thesis, University of Debrecen (2003) ·Zbl 1026.68015 |
| [17] | Nagy, B., Shortest paths in triangular grids with neighbourhood sequences, Journal of Computing and Information Technology, 11, 2, 111-122 (2003) ·doi:10.2498/cit.2003.02.04 |
| [18] | Nagy, B., Characterization of digital circles in triangular grid, Pattern Recognition Letters, 25, 11, 1231-1242 (2004) ·doi:10.1016/j.patrec.2004.04.001 |
| [19] | Nagy, B., Generalised triangular grids in digital geometry, Acta Mathematica Academiae Paedagogicae Nyíregyháziensis, 20, 1, 63-78 (2004) ·Zbl 1060.52502 |
| [20] | Nagy, B., Distances with neighbourhood sequences in cubic and triangular grids, Pattern Recognition Letters, 28, 1, 99-109 (2007) ·doi:10.1016/j.patrec.2006.06.007 |
| [21] | Nagy, B.; Barneva, R. P.; Brimkov, V. E.; Aggarwal, J. K., Cellular topology on the triangular grid, Combinatorial Image Analaysis, 143-153 (2012), Heidelberg: Springer, Heidelberg ·Zbl 1377.68286 ·doi:10.1007/978-3-642-34732-0_11 |
| [22] | Nagy, B.; Barczi, K., Isoperimetrically optimal polygons in the triangular grid with Jordan-type neighbourhood on the boundary, International Journal of Computer Mathematics, 90, 8, 1-24 (2012) |
| [23] | Shimizu, K., Algorithm for generating a digital circle on a triangular grid, Computer Graphics and Image Processing, 15, 4, 401-402 (1981) ·doi:10.1016/S0146-664X(81)80020-2 |
| [24] | Subramanian, K. G.; Wiederhold, P., Generative models for pictures tiled by triangles, Science and Technology, 15, 3, 246-265 (2012) |
| [25] | Sury, B., Group theory and tiling problems, Symmetry: A Multi-Disciplinary Perspective, 16, 16, 97-117 (2011) ·Zbl 1356.52011 |
| [26] | Wüthrich, C. A.; Stucki, P., An algorithmic comparison between square-and hexagonal-based grids, CVGIP: Graphical Models and Image Processing, 53, 4, 324-339 (1991) |
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.
