Abstract

This thesis studies sparse resultants for solving polynomial systems with a view towards camera geometry problems in computer vision. These problems are typically modeled as polynomial systems, parameterized by minimal data samples, and known as minimal problems in computer vision. These polynomial systems present a challenging case as they tend to consist of sparse polynomials with non-generic coefficients. Further, for robust estimation they have to be solved within a RANSAC-like scheme, giving rise to an offline + online strategy. The offline stage has to symbolically analyze the polynomial system, and generate a fast and accurate online stage, i.e. the minimal solver.

The most important contribution of this thesis is in algorithms for the offline stage using the sparse resultants via Sylvester-style matrix constructions. Sylvester-style matrices are attractive for offline manipulation as the matrix entries are either 0 or one of the polynomial coefficients. Two algorithms fall in this category: one constructs a sparse resultant matrix by hiding one of the variables of the given polynomial system, while the other algorithm adds an extra polynomial with a special form involving an extra variable and then hides the new variable

The two algorithms are automated, and available as open source software. They lead to minimal solvers at the two ends of a spectrum in terms of the number of numerical matrix operations needed as well as the solver stability. One crucial question still remains unanswered: “for a given polynomial system, what is the smallest/fastest solver?” To this end, the thesis demonstrates that it is important to generate minimal solvers using both the proposed resultant-based methods as well as the SOTA action matrix-based methods.

The thesis also observes a connection between a convex polytope based resultant matrix construction and the Gröbner basis-based action matrix algorithm, which is investigated, along with an intuitive explanation of the role played by convex geometry in basis selection for resultant-based methods.

Lastly, the proposed resultant-based methods are applied to the semi-generalized pose estimation problem and novel minimal solvers are presented for two scenarios: a planar scene and a hybrid set of 2D-2D and 2D-3D point correspondences. The proposed minimal solvers are extensively tested on synthetic and real scenes.

Tiivistelmä

Tässä väitöskirjassa tutkitaan harvoja resultantteja polynomijärjestelmien ratkaisemiseksi tietokonenäön kamerageometriaongelmien näkökulmasta. Nämä ongelmat mallinnetaan tyypillisesti polynomijärjestelmiksi, parametroidaan minimaalisilla datanäytteillä, ja niistä käytetään nimitystä minimaaliset ongelmat tietokonenäössä. Nämä polynomijärjestelmät edustavat haastavaa tapausta kaikkien ratkaisujen laskemisen kontekstissa, koska ne koostuvat yleensä harvoista polynomeista, joilla on ei-geneeriset kertoimet. Lisäksi luotettavaa estimointia varten ne on ratkaistava RANSAC:n kaltaisessa järjestelyssä, mikä johtaa offline + online -strategiaan. Offline-vaiheen täytyy symbolisesti analysoida polynomijärjestelmää ja luoda nopea ja tarkka online-vaihe, eli minimiratkaisija.

Tämän väitöskirjan tärkein kontribuutio on offline-vaiheen algoritmeissa, joissa käytetään harvaa resultanttia Sylvester-tyylisten matriisirakenteiden kautta. Sylvester-tyyliset matriisit ovat houkuttelevia offline-käsittelyyn, koska yksittäinen matriisialkio on joko nolla tai jokin polynomikertoimista. Kaksi algoritmia kuuluu tähän luokkaan: toinen muodostaa harvan resultanttimatriisin piilottamalla yhden annetun polynomijärjestelmän muuttujista, kun taas toinen algoritmi lisää ylimääräisen polynomin, jolla on erityinen muoto sisältäen ylimääräisen muuttujan, ja piilottaa sitten kyseisen uuden muuttujan. Molemmat algoritmit ovat automatisoituja ja saatavilla avoimen lähdekoodin ohjelmistoina. Nämä kaksi ehdotettua algoritmia johtavat minimaalisiin ratkaisijoihin spektrin kahdessa ääripäässä tarvittavien numeeristen matriisioperaatioiden lukumäärän sekä ratkaisijan stabiilisuuden kannalta. Yksi ratkaiseva kysymys on edelleen vaille vastausta: mikä on annetulle polynomijärjestelmälle pienin/nopein ratkaisija? Tätä tarkoitusta varten väitöskirja osoittaa, että on tärkeää generoida minimiratkaisijoita käyttäen sekä ehdotettuja resultanttipohjaisia menetelmiä että alan viimeisimpiä toimintamatriisipohjaisia menetelmiä.

Väitöskirjassa tehdään myös havainto konveksiin polytooppiin perustuvan resultanttimatriisikonstruktion ja Gröbnerin kantapohjaisen toimintamatriisialgoritmin välisestä yhteydestä, jota tutkitaan yhdessä intuitiivinen selityksen kanssa konveksin geometrian roolista resultanttipohjaisten menetelmien kantavalinnassa.

Tässä väitöskirjassa sovelletaan myös ehdotettuja resultanttipohjaisia menetelmiä puoliyleistettyyn asennon estimointiongelmaan ja esitetään uusia minimiratkaisijoita kahdelle skenaariolle, ts. tasomainen näkymä ja hybridijoukko 2D-2D ja 2D-3D pistevastaavuuksia. Ehdotetut minimiratkaisijat on testattu laajasti synteettisillä ja todellisilla näkymillä.

Osajulkaisut / Original papers

Osajulkaisut eivät sisälly väitöskirjan elektroniseen versioon. / Original papers are not included in the electronic version of the dissertation.

1. Bhayani, S., Kukelova, Z., & Heikkilä, J. (2020). A sparse resultant based method for efficient minimal solvers. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 1767–1776. https://doi.org/10.1109/CVPR42600.2020.00184

   Rinnakkaistallennettu versio / Self-archived version

2. Bhayani, S., Kukelova, Z., & Heikkilä, J. (2021). Computing stable resultant-based minimal solvers by hiding a variable. In 2020 25th International Conference on Pattern Recognition (ICPR), 6104–6111. https://doi.org/10.1109/ICPR48806.2021.9411957

   Rinnakkaistallennettu versio / Self-archived version

3. Bhayani, S., Sattler, T., Barath, D., Beliansky, P., Heikkilä, J., & Kukelova, Z. (2021). Calibrated and partially calibrated semi-generalized homographies. In 2021 IEEE/CVF International Conference on Computer Vision (ICCV), 5916–5925. https://doi.org/10.1109/ICCV48922.2021.00588

   Rinnakkaistallennettu versio / Self-archived version

4. Bhayani, S., Sattler, T., Larsson, V., Heikkilä, J., & Kukelova, Z. (2023). Partially calibrated semi-generalized pose from hybrid point correspondences. 2023 IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), 2881–2890. https://doi.org/10.1109/WACV56688.2023.00290

   Rinnakkaistallennettu versio / Self-archived version

5. Bhayani, S., Heikkilä, J., & Kukelova, Z. (2023). Sparse resultant based minimal solvers in computer vision and their connection with the action matrix. Manuscript submitted for publication. http://arxiv.org/abs/2301.06443