×

Topology-preserving conditions for 2D digital images under rigid transformations. (English) Zbl 1291.68421

Summary: In the continuous domain \(\mathbb R^n\), rigid transformations are topology-preserving operations. Due to digitization, this is not the case when considering digital images, i.e., images defined on \(\mathbb Z^n\). In this article, we begin to investigate this problem by studying conditions for digital images to preserve their topological properties under all rigid transformations on \(\mathbb Z^2\). Based on (i) the recently introduced notion of DRT graph, and (ii) the notion of simple point, we propose an algorithm for evaluating digital images topological invariance.

MSC:

68U10 Computing methodologies for image processing
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Zitová, B., Flusser, J.: Image registration methods: a survey. Image Vis. Comput. 21(11), 977-1000 (2003)
[2] Yilmaz, A., Javed, O., Shah, M.: Object tracking: a survey. ACM Comput. Surv. 38(4), 1-45 (2006)
[3] Jain, V.; Bollmann, B.; Richardson, M.; Berger, D.; Helmstaedter, M.; Briggman, K.; Denk, W.; Bowden, J.; Mendenhall, J.; Abraham, W.; Harris, K.; Kasthuri, N.; Hayworth, K.; Schalek, R.; Tapia, J.; Lichtman, J.; Seung, S., Boundary learning by optimization with topological constraints, 2488-2495 (2010), New York
[4] Faisan, S., Passat, N., Noblet, V., Chabrier, R., Meyer, C.: Topology preserving warping of 3-D binary images according to continuous one-to-one mappings. IEEE Trans. Image Process. 20(8), 2135-2145 (2011) · Zbl 1372.94078
[5] Dawant, B., Hartmann, S., Thirion, J., Maes, F., Vandermeulen, D., Demaerel, P.: Automatic 3-D segmentation of internal structures of the head in MR images using a combination of similarity and free-form deformations: Part I, methodology and validation on normal subjects. IEEE Trans. Med. Imaging 18(10), 902-916 (1999)
[6] Ngo, P.; Kenmochi, Y.; Passat, N.; Talbot, H., Sufficient conditions for topological invariance of 2D digital images under rigid transformations, No. 7749, 155-168 (2013), Berlin · Zbl 1382.68308
[7] Ngo, P., Kenmochi, Y., Passat, N., Talbot, H.: Combinatorial structure of rigid transformations in 2D digital images. Comput. Vis. Image Underst. 117(4), 393-408 (2013)
[8] Jacob, M.-A.; Andres, E., On discrete rotations, 161-174 (1995)
[9] Amir, A., Kapah, O., Tsur, D.: Faster two-dimensional pattern matching with rotations. Theor. Comput. Sci. 368(3), 196-204 (2006) · Zbl 1171.68874
[10] Amir, A., Landau, G.M., Vishkin, U.: Efficient pattern matching with scaling. J. Algorithms 13(1), 2-32 (1992) · Zbl 0767.68046
[11] Amir, A., Butman, A., Lewenstein, M., Porat, E.: Real two dimensional scaled matching. Algorithmica 53(3), 314-336 (2009) · Zbl 1188.68119
[12] Hundt, C., Liśkiewicz, M., Nevries, R.: A combinatorial geometrical approach to two-dimensional robust pattern matching with scaling and rotation. Theor. Comput. Sci. 410(51), 5317-5333 (2009) · Zbl 1187.68182
[13] Hundt, C.; Liśkiewicz, M., On the complexity of affine image matching, No. 4393, 284-295 (2007), Berlin · Zbl 1186.68523
[14] Hundt, C., Affine image matching is uniform TC0-complete, No. 6129, 13-25 (2010), Berlin · Zbl 1286.68466
[15] Hundt, C.; Liśkiewicz, M., Combinatorial bounds and algorithmic aspects of image matching under projective transformations, No. 5162, 395-406 (2008), Berlin · Zbl 1173.68787
[16] Reveillès, J.-P.: Géométrie discrète, calcul en nombres entiers et algorithmique, Thèse d’État. Université Strasbourg 1 (1991) · Zbl 1079.51513
[17] Andres, E., The quasi-shear rotation, No. 1176, 307-314 (1996), Berlin
[18] Richman, M. S., Understanding discrete rotations, No. 3, 2057-2060 (1997), New York
[19] Nouvel, B.: Rotations discrètes et automates cellulaires. Ph.D. thesis, École Normale Supérieure de Lyon (2006) · Zbl 0895.68138
[20] Nouvel, B.; Rémila, E., Incremental and transitive discrete rotations, No. 4040, 199-213 (2006), Berlin
[21] Thibault, Y., Kenmochi, Y., Sugimoto, A.: Computing upper and lower bounds of rotation angles from digital images. Pattern Recognit. 42(8), 1708-1717 (2009) · Zbl 1184.68572
[22] Bertrand, G.: On critical kernels. C. R. Acad. Sci., Sér. 1 Math. 345, 363-367 (2007) · Zbl 1130.68098
[23] Rosenfeld, A.: Connectivity in digital pictures. J. ACM 17(1), 146-160 (1970) · Zbl 0208.19806
[24] Kong, T.Y., Rosenfeld, A.: Digital topology: introduction and survey. Comput. Vis. Graph. Image Process. 48(3), 357-393 (1989)
[25] Mazo, L., Passat, N., Couprie, M., Ronse, C.: Paths, homotopy and reduction in digital images. Acta Appl. Math. 113(2), 167-193 (2011) · Zbl 1206.68337
[26] Mazo, L., Passat, N., Couprie, M., Ronse, C.: Digital imaging: a unified topological framework. J. Math. Imaging Vis. 44(1), 19-37 (2012) · Zbl 1255.68254
[27] Khalimsky, E.: Topological structures in computer science. J. Appl. Math. Simul. 1(1), 25-40 (1987) · Zbl 0655.68021
[28] Kovalevsky, V.A.: Finite topology as applied to image analysis. Comput. Vis. Graph. Image Process. 46(2), 141-161 (1989)
[29] Bertrand, G., Malandain, G.: A new characterization of three-dimensional simple points. Pattern Recognit. Lett. 15(2), 169-175 (1994) · Zbl 0802.68178
[30] Couprie, M., Bertrand, G.: New characterizations of simple points in 2D, 3D, and 4D discrete spaces. IEEE Trans. Pattern Anal. Mach. Intell. 31(4), 637-648 (2009)
[31] Ronse, C.: A topological characterization of thinning. Theor. Comput. Sci. 43(1), 31-41 (2007) · Zbl 0622.68072
[32] Bertrand, G.: On P-simple points. C. R. Acad. Sci., Sér. 1 Math. 321, 1077-1084 (1995) · Zbl 0843.68117
[33] Passat, N., Mazo, L.: An introduction to simple sets. Pattern Recognit. Lett. 30(15), 1366-1377 (2009)
[34] Couprie, M., Bezerra, F.N., Bertrand, G.: Topological operators for grayscale image processing. J. Electron. Imaging 10(4), 1003-1015 (2001)
[35] Latecki, L.J.: Multicolor well-composed pictures. Pattern Recognit. Lett. 16(4), 425-431 (1997)
[36] Damiand, G., Dupas, A., Lachaud, J.-O.: Fully deformable 3D digital partition model with topological control. Pattern Recognit. Lett. 32(9), 1374-1383 (2011)
[37] Mazo, L., Passat, N., Couprie, M., Ronse, C.: Topology on digital label images. J. Math. Imaging Vis. 44(3), 254-281 (2012) · Zbl 1255.68255
[38] Pham, D., Bazin, P.-L., Prince, J.: Digital topology in brain imaging. IEEE Signal Process. Mag. 27(4), 51-59 (2010)
[39] Mangin, J.-F., Frouin, V., Bloch, I., Régis, J., López-Krahe, J.: From 3D magnetic resonance images to structural representations of the cortex topography using topology preserving deformations. J. Math. Imaging Vis. 5(4), 297-318 (1995)
[40] Han, X., Xu, C., Prince, J.L.: A topology preserving level set method for geometric deformable models. IEEE Trans. Pattern Anal. Mach. Intell. 25(6), 755-768 (2003)
[41] Bazin, P.-L.; Ellingsen, L. M.; Pham, D. L., Digital homeomorphisms in deformable registration, No. 4584, 211-222 (2007), Berlin
[42] Ayala, R., Domínguez, E., Francés, A.R., Quintero, A.: Homotopy in digital spaces. Discrete Appl. Math. 125(1), 3-24 (2003) · Zbl 1010.68200
[43] Bertrand, G., Couprie, M., Passat, N.: A note on 3-D simple points and simple-equivalence. Inf. Process. Lett. 109(13), 700-704 (2009) · Zbl 1209.68578
[44] Nouvel, B., Rémila, E.: Configurations induced by discrete rotations: periodicity and quasi-periodicity properties. Discrete Appl. Math. 147(2-3), 325-343 (2005) · Zbl 1099.68125
[45] Thibault, Y.: Rotations in 2D and 3D discrete spaces. Ph.D. thesis, Université Paris-Est (2010)
[46] Latecki, L.J., Eckhardt, U., Rosenfeld, A.: Well-composed sets. Comput. Vis. Image Underst. 61(1), 70-83 (1995)
[47] Mazo, L., A framework for label images, No. 7309, 1-10 (2012), Berlin · Zbl 1255.68253
[48] Berenstein, C., Lavine, D.: On the number of digital straight line segments. IEEE Trans. Pattern Anal. Mach. Intell. 10(6), 880-887 (1988) · Zbl 0674.68054
[49] Nagy, B.: An algorithm to find the number of the digitizations of discs with a fixed radius. Electron. Notes Discrete Math. 20, 607-622 (2005) · Zbl 1179.94016
[50] Serra, J.: Image Analysis and Mathematical Morphology. Academic Press, San Diego (1983)
[51] Heijmans, H.J.A.M.: Discretization of morphological operators. J. Vis. Commun. Image Represent. 3(2), 182-193 (1992)
[52] Latecki, L.J., Conrad, C., Gross, A.: Preserving topology by a digitization process. J. Math. Imaging Vis. 8(2), 131-159 (1998) · Zbl 0895.68138
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.