Fast and Stable Polynomial Equation Solving and Its Application to Computer Vision
Byröd, Martin LU ; Josephson, Klas LU and Åström, Karl LU
(2009)
In International Journal of Computer Vision
84(3).
p.237-256
- Abstract
- This paper presents several new results on techniques for solving systems of polynomial equations in computer vision. Gröbner basis techniques for equation solving have been applied successfully to several geometric computer vision problems. However, in many cases these methods are plagued by numerical problems. In this paper we derive a generalization of the Gröbner basis method for polynomial equation solving, which improves overall numerical stability. We show how the action matrix can be computed in the general setting of an arbitrary linear basis for ℂ[x]/I. In particular, two improvements on the stability of the computations are made by studying how the linear basis for ℂ[x]/I should be selected. The first of these strategies... (More)
- This paper presents several new results on techniques for solving systems of polynomial equations in computer vision. Gröbner basis techniques for equation solving have been applied successfully to several geometric computer vision problems. However, in many cases these methods are plagued by numerical problems. In this paper we derive a generalization of the Gröbner basis method for polynomial equation solving, which improves overall numerical stability. We show how the action matrix can be computed in the general setting of an arbitrary linear basis for ℂ[x]/I. In particular, two improvements on the stability of the computations are made by studying how the linear basis for ℂ[x]/I should be selected. The first of these strategies utilizes QR factorization with column pivoting and the second is based on singular value decomposition (SVD). Moreover, it is shown how to improve stability further by an adaptive scheme for truncation of the Gröbner basis. These new techniques are studied on some of the latest reported uses of Gröbner basis methods in computer vision and we demonstrate dramatically improved numerical stability making it possible to solve a larger class of problems than previously possible. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1389303
- author
- Byröd, Martin
LU
; Josephson, Klas
LU
and Åström, Karl
LU
- organization
- publishing date
- 2009
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Polynomial equations, Gröbner basis, Minimal problems, Structure from motion
- in
- International Journal of Computer Vision
- volume
- 84
- issue
- 3
- pages
- 237 - 256
- publisher
- Springer
- external identifiers
-
- wos:000267028600001
- scopus:67349135634
- ISSN
- 1573-1405
- DOI
- 10.1007/s11263-009-0235-z
- language
- English
- LU publication?
- yes
- id
- 3cb140a6-d814-4f55-b2ab-ac89d9f8be62 (old id 1389303)
- date added to LUP
- 2016-04-01 11:50:52
- date last changed
- 2022-04-05 05:55:46
@article{3cb140a6-d814-4f55-b2ab-ac89d9f8be62,
abstract = {{This paper presents several new results on techniques for solving systems of polynomial equations in computer vision. Gröbner basis techniques for equation solving have been applied successfully to several geometric computer vision problems. However, in many cases these methods are plagued by numerical problems. In this paper we derive a generalization of the Gröbner basis method for polynomial equation solving, which improves overall numerical stability. We show how the action matrix can be computed in the general setting of an arbitrary linear basis for ℂ[x]/I. In particular, two improvements on the stability of the computations are made by studying how the linear basis for ℂ[x]/I should be selected. The first of these strategies utilizes QR factorization with column pivoting and the second is based on singular value decomposition (SVD). Moreover, it is shown how to improve stability further by an adaptive scheme for truncation of the Gröbner basis. These new techniques are studied on some of the latest reported uses of Gröbner basis methods in computer vision and we demonstrate dramatically improved numerical stability making it possible to solve a larger class of problems than previously possible.}},
author = {{Byröd, Martin and Josephson, Klas and Åström, Karl}},
issn = {{1573-1405}},
keywords = {{Polynomial equations; Gröbner basis; Minimal problems; Structure from motion}},
language = {{eng}},
number = {{3}},
pages = {{237--256}},
publisher = {{Springer}},
series = {{International Journal of Computer Vision}},
title = {{Fast and Stable Polynomial Equation Solving and Its Application to Computer Vision}},
url = {{https://lup.lub.lu.se/search/files/2669072/1389304.pdf}},
doi = {{10.1007/s11263-009-0235-z}},
volume = {{84}},
year = {{2009}},
}