Abstract
Rigid motions are fundamental operations in image processing. While bijective and isometric in \(\mathbb {R}^3\), they lose these properties when digitized in \(\mathbb {Z}^3\). To understand how the digitization of 3D rigid motions affects the topology and geometry of a chosen image patch, we classify the rigid motions according to their effect on the image patch. This classification can be described by an arrangement of hypersurfaces in the parameter space of 3D rigid motions of dimension six. However, its high dimensionality and the existence of degenerate cases make a direct application of classical techniques, such as cylindrical algebraic decomposition or critical point method, difficult. We show that this problem can be first reduced to computing sample points in an arrangement of quadrics in the 3D parameter space of rotations. Then we recover information about remaining three parameters of translation. We implemented an ad-hoc variant of state-of-the-art algorithms and applied it to an image patch of cardinality 7. This leads to an arrangement of 81 quadrics and we recovered the classification in less than one hour on a machine equipped with 40 cores.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Our implementation of real algebraic numbers and their comparison can be downloaded from https://github.com/copyme/RigidMotionsMapleTools.
- 2.
Note that this time is affected by a time needed to read a list of sample points (a, b, c) from a hard drive before the main computations.
References
Abbott, J.: Quadratic interval refinement for real roots. Commun. Comput. Algebra 48(1/187), 3–12 (2014)
Amir, A., Kapah, O., Tsur, D.: Faster two-dimensional pattern matching with rotations. Theoret. Comput. Sci. 368(3), 196–204 (2006)
Basu, S., Pollack, R., Roy, M.F.: Algorithms in Real Algebraic Geometry. Springer, Heidelberg (2005)
Cayley, A., Forsyth, A.: The Collected Mathematical Papers of Arthur Cayley, vol. 1. The University Press, Cambridge (1898)
Collins, G.: Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In: Brakhage, H. (ed.) Automata Theory and Formal Languages. LNCS, vol. 33, pp. 134–183. Springer, Heidelberg (1975)
Cox, D., Little, J., O’Shea, D.: Ideals, Varieties and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, New York (1996)
El Din, M.S., Schost, E.: Properness defects of projections and computation of atleast one point in each connected component of a real algebraic set. Discrete Comput. Geomet. 32(3), 417 (2004)
Halperin, D.: Arrangements. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., pp. 529–562. Chapman and Hall/CRC (2004)
Hansen, E.: Global optimization using interval analysis - the multi-dimensional case. Numerische Mathematik 34(3), 247–270 (1980)
Hundt, C., Liśkiewicz, M.: On the complexity of affine image matching. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 284–295. Springer, Heidelberg (2007)
Jelonek, Z.: Topological characterization of finite mappings. Bull. Polish Acad. Sci. Math 49(3), 279–283 (2001)
Jelonek, Z., Kurdyka, K.: Quantitative generalized Bertini-Sard theorem for smooth affine varieties. Discrete Comput. Geom. 34(4), 659–678 (2005)
Kurdyka, K., Orro, P., Simon, S., et al.: Semialgebraic Sard theorem for generalized critical values. J. Diff. Geom. 56(1), 67–92 (2000)
Moroz, G.: Properness defects of projection and minimal discriminant variety. J. Symbol. Comput. 46(10), 1139–1157 (2011)
Mourrain, B., Tecourt, J.P., Teillaud, M.: On the computation of an arrangement of quadrics in 3D. Comput. Geom. 30(2), 145–164 (2005)
Neumaier, A.: Interval Methods for Systems of Equations. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (1991)
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)
Ngo, P., Kenmochi, Y., Passat, N., Talbot, H.: Topology-preserving conditions for 2D digital images under rigid transformations. J. Math. Imaging Vis. 49(2), 418–433 (2014)
Ngo, P., Passat, N., Kenmochi, Y., Talbot, H.: Topology-preserving rigid transformation of 2D digital images. IEEE Trans. Image Process. 23(2), 885–897 (2014)
Nouvel, B., Rémila, E.: On colorations induced by discrete rotations. In: Nyström, I., Sanniti di Baja, G., Svensson, S. (eds.) DGCI 2003. LNCS, vol. 2886, pp. 174–183. Springer, Heidelberg (2003)
Nouvel, B., Rémila, E.: Configurations induced by discrete rotations: periodicity and quasi-periodicity properties. Discrete Appl. Math. 147(2–3), 325–343 (2005)
Pluta, K., Kenmochi, Y., Passat, N., Talbot, H., Romon, P.: Topological alterations of 3D digital images under rigid transformations. Research report, Université Paris-Est, Laboratoire d’Informatique Gaspard-Monge UMR 8049 (2014). https://hal.archives-ouvertes.fr/hal-01333586
Pluta, K., Romon, P., Kenmochi, Y., Passat, N.: Bijective rigid motions of the 2D cartesian grid. In: Normand, N., Guédon, J., Autrusseau, F. (eds.) DGCI 2016. LNCS, vol. 9647, pp. 359–371. Springer, Heidelberg (2016). doi:10.1007/978-3-319-32360-2_28
Pluta, K., Romon, P., Kenmochi, Y., Passat, N.: Bijectivity certification of 3D digitized rotations. In: Bac, A., Mari, J. (eds.) CTIC 2016. LNCS, vol. 9667, pp. 30–41. Springer, Heidelberg (2016)
Rabier, P.J.: Ehresmann fibrations and Palais-Smale conditions for morphisms of Finsler manifolds. Ann. Math. 146, 647–691 (1997)
Renegar, J.: On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals. J. Symbol. Comput. 13(3), 255–299 (1992)
Rouillier, F., Zimmermann, P.: Efficient isolation of polynomial’s real roots. J. Comput. Appl. Math. 162(1), 33–50 (2004)
Safey El Din, M.: Testing sign conditions on a multivariate polynomial and applications. Math. Comput. Sci. 1(1), 177–207 (2007)
Singla, P., Junkins, J.L.: Multi-resolution Methods for Modeling and Control of Dynamical Systems. CRC Press, Boca Raton (2008)
Thibault, Y.: Rotations in 2D and 3D discrete spaces. Ph.D. thesis, Université Paris-Est (2010)
Thibault, Y., Sugimoto, A., Kenmochi, Y.: 3D discrete rotations using hinge angles. Theoret. Comput. Sci. 412(15), 1378–1391 (2011)
Yilmaz, A., Javed, O., Shah, M.: Object tracking: a survey. ACM Computing Surveys (CSUR) 38(4), 13 (2006)
Zitova, B., Flusser, J.: Image registration methods: a survey. Image Vis. Comput. 21(11), 977–1000 (2003)
Acknowledgments
This work received funding from the project Singcast (ANR–13–JS02–0006).
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Pluta, K., Moroz, G., Kenmochi, Y., Romon, P. (2016). Quadric Arrangement in Classifying Rigid Motions of a 3D Digital Image. In: Gerdt, V., Koepf, W., Seiler, W., Vorozhtsov, E. (eds) Computer Algebra in Scientific Computing. CASC 2016. Lecture Notes in Computer Science(), vol 9890. Springer, Cham. https://doi.org/10.1007/978-3-319-45641-6_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-45641-6_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-45640-9
Online ISBN: 978-3-319-45641-6
eBook Packages: Computer ScienceComputer Science (R0)