| 1. |
- Eriksson, Anders, 1972, et al.
(författare)
-
Rotation Averaging and Strong Duality
- 2018
-
Ingår i: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. - 1063-6919. - 9781538664209 ; , s. 127-135
-
Konferensbidrag (refereegranskat)abstract
- In this paper we explore the role of duality principles within the problem of rotation averaging, a fundamental task in a wide range of computer vision applications. In its conventional form, rotation averaging is stated as a minimization over multiple rotation constraints. As these constraints are non-convex, this problem is generally considered challenging to solve globally. We show how to circumvent this difficulty through the use of Lagrangian duality. While such an approach is well-known it is normally not guaranteed to provide a tight relaxation. Based on spectral graph theory, we analytically prove that in many cases there is no duality gap unless the noise levels are severe. This allows us to obtain certifiably global solutions to a class of important non-convex problems in polynomial time. We also propose an efficient, scalable algorithm that out-performs general purpose numerical solvers and is able to handle the large problem instances commonly occurring in structure from motion settings. The potential of this proposed method is demonstrated on a number of different problems, consisting of both synthetic and real-world data.
|
|
| 2. |
- Eriksson, Anders, et al.
(författare)
-
Rotation Averaging with the Chordal Distance: Global Minimizers and Strong Duality
- 2021
-
Ingår i: IEEE Transactions on Pattern Analysis and Machine Intelligence. - 1939-3539 .- 0162-8828. ; 43:1, s. 256-268
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper we explore the role of duality principles within the problem of rotation averaging, a fundamental task in a wide range of applications. In its conventional form, rotation averaging is stated as a minimization over multiple rotation constraints. As these constraints are non-convex, this problem is generally considered challenging to solve globally. We show how to circumvent this difficulty through the use of Lagrangian duality. While such an approach is well-known it is normally not guaranteed to provide a tight relaxation. Based on spectral graph theory, we analytically prove that in many cases there is no duality gap unless the noise levels are severe. This allows us to obtain certifiably global solutions to a class of important non-convex problems in polynomial time. We also propose an efficient, scalable algorithm that outperforms general purpose numerical solvers by a large margin and compares favourably to current state-of-the-art. Further, our approach is able to handle the large problem instances commonly occurring in structure from motion settings and it is trivially parallelizable. Experiments are presented for a number of different instances of both synthetic and real-world data.
|
|
| 3. |
- Le, Huu, 1988, et al.
(författare)
-
Deterministic Approximate Methods for Maximum Consensus Robust Fitting
- 2021
-
Ingår i: IEEE Transactions on Pattern Analysis and Machine Intelligence. - 1939-3539 .- 0162-8828. ; 43:3, s. 842-857
-
Tidskriftsartikel (refereegranskat)abstract
- Maximum consensus estimation plays a critically important role in several robust fitting problems in computer vision. Currently, the most prevalent algorithms for consensus maximization draw from the class of randomized hypothesize-and-verify algorithms, which are cheap but can usually deliver only rough approximate solutions. On the other extreme, there are exact algorithms which are exhaustive search in nature and can be costly for practical-sized inputs. This paper fills the gap between the two extremes by proposing deterministic algorithms to approximately optimize the maximum consensus criterion. Our work begins by reformulating consensus maximization with linear complementarity constraints. Then, we develop two novel algorithms: one based on non-smooth penalty method with a Frank-Wolfe style optimization scheme, the other based on the Alternating Direction Method of Multipliers (ADMM). Both algorithms solve convex subproblems to efficiently perform the optimization. We demonstrate the capability of our algorithms to greatly improve a rough initial estimate, such as those obtained using least squares or a randomized algorithm. Compared to the exact algorithms, our approach is much more practical on realistic input sizes. Further, our approach is naturally applicable to estimation problems with geometric residuals. Matlab code and demo program for our methods can be downloaded from https://goo.gl/FQcxpi.
|
|
| 4. |
- Palkopoulou, Eleftheria, et al.
(författare)
-
A comprehensive genomic history of extinct and living elephants
- 2018
-
Ingår i: Proceedings of the National Academy of Sciences of the United States of America. - : NATL ACAD SCIENCES. - 0027-8424 .- 1091-6490. ; 115:11, s. E2566-E2574
-
Tidskriftsartikel (refereegranskat)abstract
- Elephantids are the world's most iconic megafaunal family, yet there is no comprehensive genomic assessment of their relationships. We report a total of 14 genomes, including 2 from the American mastodon, which is an extinct elephantid relative, and 12 spanning all three extant and three extinct elephantid species including an similar to 120,000-y-old straight-tusked elephant, a Columbian mammoth, and woolly mammoths. Earlier genetic studies modeled elephantid evolution via simple bifurcating trees, but here we show that interspecies hybridization has been a recurrent feature of elephantid evolution. We found that the genetic makeup of the straight-tusked elephant, previously placed as a sister group to African forest elephants based on lower coverage data, in fact comprises three major components. Most of the straight-tusked elephant's ancestry derives from a lineage related to the ancestor of African elephants while its remaining ancestry consists of a large contribution from a lineage related to forest elephants and another related to mammoths. Columbian and woolly mammoths also showed evidence of interbreeding, likely following a latitudinal cline across North America. While hybridization events have shaped elephantid history in profound ways, isolation also appears to have played an important role. Our data reveal nearly complete isolation between the ancestors of the African forest and savanna elephants for similar to 500,000 y, providing compelling justification for the conservation of forest and savanna elephants as separate species.
|
|
