Uncovering Symmetries in Polynomial Systems
In this paper we study symmetries in polynomial equation systems and how they can be integrated into the action matrix method. The main contribution is a generalization of the partial p-fold symmetry and we provide new theoretical insights as to why these
- PDF / 772,536 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 24 Downloads / 203 Views
Abstract. In this paper we study symmetries in polynomial equation systems and how they can be integrated into the action matrix method. The main contribution is a generalization of the partial p-fold symmetry and we provide new theoretical insights as to why these methods work. We show several examples of how to use this symmetry to construct more compact polynomial solvers. As a second contribution we present a simple and automatic method for finding these symmetries for a given problem. Finally we show two examples where these symmetries occur in real applications.
1
Introduction
Polynomial systems have become an integral part of Computer Vision due to their ability to encode many geometric constraints. Polynomial solvers have been successfully used for many minimal problem such as absolute pose estimation [1–3], relative pose estimation [4–6] and homography estimation [7,8]. They have also been used for some some non-minimal problem such as PnP [9,10]. One technique for constructing polynomial solvers is the so called action matrix method. The method reduces the polynomial system to an eigenvalue problem for which there exist good numerical methods. For a brief introduction to polynomial solvers in Computer Vision we recommend Byr¨ od et al. [11]. In [12] Ask et al. considers polynomial systems, where the degree of each monomial has the same remainder modulo p. This introduces a p-fold symmetry into the solution set. By taking this symmetry into account they construct smaller and more stable polynomial solvers. This work was later extended by Kuang et al. [13] to polynomial systems where this symmetry only exists in a subset of the variables. This type of symmetry has been used in [1,9,14–16]. In this paper we generalize the symmetry from [12,13] and provide new theoretical insight as to why these methods work. We show that if the system has these symmetries the action matrix can be chosen block diagonal and by considering only a single block we can construct more compact solvers. In [17] Corless et al. also use symmetries in the action matrix method. Their approach is based on studying the group structure of the symmetry using tools from linear representation theory. While the paper present theory for symmetries Electronic supplementary material The online version of this chapter (doi:10. 1007/978-3-319-46487-9 16) contains supplementary material, which is available to authorized users. c Springer International Publishing AG 2016 B. Leibe et al. (Eds.): ECCV 2016, Part III, LNCS 9907, pp. 252–267, 2016. DOI: 10.1007/978-3-319-46487-9 16
Uncovering Symmetries in Polynomial Systems
253
of general group structure and show a few examples with integer or rational coefficients it is not clear how to directly apply it to build polynomial solvers for types of problems encountered in Computer Vision. In contrast the theory developed in this paper classifies the symmetry based on the monomial structure in the equations. This allows the method to integrate naturally into the standard methods for building polynomial so
Data Loading...
