Topology preservation on the triangular grid
Tóm tắt
There are exactly three regular planar grids, which are formed by tiling the 2-dimensional Euclidean space with regular triangles, squares, and hexagons. The topology of the square grid is well-understood, but it cannot be said of the remaining two regular sampling schemes. This work deals with the topological properties of digital binary pictures sampled on the triangular grid. Some characterizations of simple pixels and sufficient conditions for topology preserving operators are reported. These results provide the theoretical background to various topological algorithms including thinning, shrinking, generating discrete Voronoi diagrams, and contour smoothing on the triangular grid.
Tài liệu tham khảo
Bertrand, G., Couprie, M.: Transformations topologiques discrètes. In: Coeurjolly, D., Montanvert, A., Chassery, J. (eds.) Géométrie discrète et images numériques, pp. 187–209. Hermès Science Publications (2007)
Bertrand, G., Couprie, M.: Two-dimensional thinning algorithms based on critical kernels. J. Math. Imaging Vision 31(1), 35–56 (2008)
Bloch, I., Pescatore, J., Garnero, L.: A new characterization of simple elements in a tetrahedral mesh. Graph. Model. 67(4), 260–284 (2005)
Brimkov, V.E., Barneva, R.P.: Analytical Honeycomb Geometry for Raster and Volume Graphics. Comput. J. 48, 180–199 (2005)
Deutsch, E.S.: On parallel operations on hexagonal arrays. IEEE Trans. Comp. C-19(10), 982–983 (1970)
Deutsch, E.S.: Thinning algorithms on rectangular, hexagonal, and triangular arrays. Commun. ACM 15, 827–837 (1972)
Gaspar, F.J., Gracia, J.L., Lisbona, F.J., Rodrigo, C.: On geometric multigrid methods for triangular grids using three-coarsening strategy. Appl. Numer. Math. 59(7), 1693–1708 (2009)
Hall, R.W. In: Kong, T.Y., Rosenfeld, A. (eds.) : Parallel connectivity-preserving thinning algorithms. In: Topological algorithms for digital image processing, pp. 145–179. Elsevier Science (1996)
Hall, R.W., Kong, T.Y., Rosenfeld, A. In: Kong, T.Y., Rosenfeld, A. (eds.) : Shrinking binary images. In: Topological algorithms for digital image processing, pp. 31–98. Elsevier Science (1996)
Hartmann, E.: A marching method for the triangulation of surfaces. Vis. Comput. 14, 95–108 (1998)
Kardos, P., Palágyi, K.: On topology preservation for hexagonal parallel thinning algorithms. In: Proceedings 14th International Workshop on Combinatorial Image Analysis, IWCIA 2011, Madrid, Spain, Lecture Notes in Computer Science, Vol. 6636, pp. 31–42. Springer (2011)
Kardos, P., Palágyi, K.: On topology preservation for triangular thinning algorithms. In: Proceedings 15th International Workshop on Combinatorial Image Analaysis, IWCIA 2012, Austin, TX, USA, Lecture Notes in Computer Science, Vol. 7655, pp. 128–142. Springer (2012)
Kardos, P., Palágyi, K.: Topology preserving hexagonal thinning. Int. J. Comput. Math. 90, 1607–1617 (2013)
Kardos, P., Palágyi, K.: Sufficient conditions for topology preserving additions and general operators. In: Proceddings 14th IASTED International Conference Computer Graphics and Imaging, CGIM 2013, pp. 107–114. IASTED ACTA Press (2013)
Kong, T.Y.: On topology preservation in 2-d and 3-d thinning. Int. J. Pattern Recognit. Artif. Intell. 9, 813–844 (1995)
Kong, T.Y., Rosenfeld, A.: Digital topology: Introduction and survey. Comp. Vision Graph. Image Process. 48, 357–393 (1989)
Lam, L., Lee, S.-W., Suen, C.Y.: Thinning methodologies — A comprehensive survey. IEEE Trans. Pattern Anal. Mach. Intell. 14, 869–885 (1992)
Lee, M., Jayanthi, S.: Hexagonal Image Processing: A Practical Approach (Advances in Pattern Recognition). Springer-Verlag (2005)
Ma, C.M.: On topology preservation in 3D thinning. CVGIP: Image Underst. 59, 328–339 (1994)
Marchand-Maillet, S., Sharaiha, Y.M.: Binary Digital Image Processing – A Discrete Approach. Academic Press (2000)
Nagy, B.: Characterization of digital circles in triangular grid. Pattern Recogn. Lett. 25(11), 1231–1242 (2004)
Ronse, C.: Minimal test patterns for connectivity preservation in parallel thinning algorithms for binary digital images. Discret. Appl. Math. 21, 67–79 (1988)
Sahr, K., White, D., Kimerling, A.J.: Geodesic discrete global grid systems. Cartogr. Geogr. Inf. Sci. 30(2), 121–134 (2003)
Serra, J.: Image analysis and mathematical morphology. Academic Press (1982)
Staunton, R.C.: An analysis of hexagonal thinning algorithms and skeletal shape representation. Pattern Recog. 29, 1131–1146 (1996)
Staunton, R.C.: One-pass parallel hexagonal thinning algorithm. In: Proceedings IEE 7th International Conference Image Processing and Its Applications, pp. 841–845 (1999)
In: Suen, C.Y., Wang, P.S.P. (eds.) : Thinning methodologies for pattern recognition. Series in Machine Perception and Artificial Intelligence 8. World Scientific, Singapore (1994)
Wiederhold, P., Morales, S.: Thinning on quadratic, triangular, and hexagonal cell complexes. In: Proceedings 13th International Workshop on Combinatorial Image Analysis, IWCIA 2009, Lecture Notes in Computer Science, Vol. 5852, pp. 162–175. Springer (2009)
Wuthrich, C., Stucki, P.: An algorithm comparison between square- and hexagonal-based grids. Graph. Model Image Process. 53, 324–339 (1991)