Paper Viewing Graph Solvability via Cycle Consistency co-authored by Federica Arrigoni, Andrea Fusiello, Elisa Ricci, and Tomas Pajdla were awarded Marr Prize Best Paper Honorable Mention at the ICCV 2021 in Montreal. ICCV – IEEE International Conference on Computer Vision – is the premier international computer vision event with 1600+ accepted papers (out of more than 6000 submitted) in 2021.
Tomas Pajdla from Applied Algebra and Geometry Group of the CIIRC CTU ranks as the 3rd top computer vision researcher in the Czech Republic according to Guide2Research. At the previous event, ICCV 2019, Tomáš Pajdla was one of the authors of the Best Student Paper.
In structure-from-motion, the viewing graph is a graph where vertices correspond to cameras and edges represent relative poses of the cameras represented by fundamental matrices. Paper presented a new formulation and an algorithm for establishing whether a viewing graph is solvable, i.e. it uniquely determines a set of projective cameras from its viewing graph. Previously known theoretical conditions either did not fully characterize the solvability of all viewing graphs or are exceedingly hard to compute for they involve solving a system of polynomial equations with a large number of unknowns.
The main result of this paper is a method for reducing the number of unknowns by exploiting the cycle consistency. It advances the understanding of the solvability by (i) finishing the classification of all previously undecided minimal graphs up to 9 nodes, (ii) extending the practical solvability testing up to minimal graphs with up to 90 nodes, and (iii) definitely answering an open research question by showing that the finite solvability is not equivalent to the solvability. Finally, the paper presents an experiment on real data showing that unsolvable graphs are appearing in practical situations.
„In applications, our result helps to recognize situations where there is not enough information to do uncalibrated 3D reconstruction from images, thus making reconstruction algorithms faster and more robust,“ says Tomas Pajdla.
The research leading to the paper was supported by the European Regional Development Fund under the project IMPACT (reg. no. CZ.02.1.01/0.0/0.0/15 003/0000468) and by EU H2020 Programme under the project SPRING (No. 871245).