| 1. |
- Byröd, Martin, et al.
(författare)
-
A Column-Pivoting Based Strategy for Monomial Ordering in Numerical Gröbner Basis Calculations
- 2008
-
Ingår i: Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. ; 5305, s. 130-143
-
Konferensbidrag (refereegranskat)abstract
- This paper presents a new fast approach to improving stability in polynomial equation solving. 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. An interesting approach to stabilising the computations is to study basis selection for the quotient space C[x]/I . In this paper, the exact matrix computations involved in the solution procedure are clarified and using this knowledge we propose a new fast basis selection scheme based on QR-factorization with column pivoting. We also propose an adaptive scheme for truncation of the Gröbner basis to further improve stability. The new basis selection strategy is studied on some of the latest reported uses of Gröbner basis methods in computer vision and we demonstrate a fourfold increase in speed and nearly as good overall precision as the previous SVD-based method. Moreover, we get typically get similar or better reduction of the largest errors.
|
|
| 2. |
- Byröd, Martin, et al.
(författare)
-
Bundle Adjustment using Conjugate Gradients with Multiscale Preconditioning
- 2009
-
Ingår i: British Machine Vision Conference.
-
Konferensbidrag (refereegranskat)abstract
- Bundle adjustment is a key component of almost any feature based 3D reconstruction system, used to compute accurate estimates of calibration parameters and structure and motion configurations. These problems tend to be very large, often involving thousands of variables. Thus, efficient optimization methods are crucial. The traditional Levenberg Marquardt algorithm with a direct sparse solver can be efficiently adapted to the special structure of the problem and works well for small to medium size setups. However, for larger scale configurations the cubic computational complexity makes this approach pro- hibitively expensive. The natural step here is to turn to iterative methods for solving the normal equations such as conjugate gradients. So far, there has been little progress in this direction. This is probably due to the lack of suitable pre-conditioners, which are con- sidered essential for the success of any iterative linear solver. In this paper, we show how multi scale representations, derived from the underlying geometric layout of the problem, can be used to dramatically increase the power of straight forward preconditioners such as Gauss-Seidel.
|
|
| 3. |
- Byröd, Martin, et al.
(författare)
-
Fast and Robust Numerical Solutions to Minimal Problems for Cameras with Radial Distortion
- 2008
-
Ingår i: [Host publication title missing]. ; , s. 2586-2593
-
Konferensbidrag (refereegranskat)abstract
- A number of minimal problems of structure from motion for cameras with radial distortion have recently been studied and solved in some cases. These problems are known to be numerically very challenging and in several cases there exist no known practical algorithm yielding solutions in floating point arithmetic. We make some crucial observations concerning the floating point implementation of Gröbner basis computations and use these new insights to formulate fast and stable algorithms for two minimal problems with radial distortion previously solved in exact rational arithmetic only: (i) simultaneous estimation of essential matrix and a common radial distortion parameter for two partially calibrated views and six image point correspondences and (ii) estimation of fundamental matrix and two different radial distortion parameters for two uncalibrated views and nine image point correspondences. We demonstrate on simulated and real experiments that these two problems can be efficiently solved in floating point arithmetic.
|
|
| 4. |
- Byröd, Martin, et al.
(författare)
-
Fast and Stable Polynomial Equation Solving and Its Application to Computer Vision
- 2009
-
Ingår i: International Journal of Computer Vision. - : Springer Science and Business Media LLC. - 1573-1405 .- 0920-5691. ; 84:3, s. 237-256
-
Tidskriftsartikel (refereegranskat)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.
|
|
| 5. |
- Byröd, Martin, et al.
(författare)
-
Fast Optimal Three View Triangulation
- 2007
-
Ingår i: Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 9783540763895 ; 4844, s. 549-559
-
Konferensbidrag (refereegranskat)abstract
- We consider the problem of $L_2$-optimal triangulation from three separate views. Triangulation is an important part of numerous computer vision systems. Under gaussian noise, minimizing the $L_2$ norm of the reprojection error gives a statistically optimal estimate. This has been solved for two views. However, for three or more views, it is not clear how this should be done. A previously proposed, but computationally impractical, method draws on Gr{"o}bner basis techniques to solve for the complete set of stationary points of the cost function. We show how this method can be modified to become significantly more stable and hence given a fast implementation in standard IEEE double precision. We evaluate the precision and speed of the new method on both synthetic and real data. The algorithm has been implemented in a freely available software package which can be downloaded from the Internet.
|
|
| 6. |
- Byröd, Martin, et al.
(författare)
-
Fast Optimal Three View Triangulation
- 2008
-
Ingår i: ; , s. 95-98
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- We consider the problem of L2-optimal triangulation from three separate views. Triangulation is an important part of numerous computer vision systems. Under gaussian noise, minimizing the L2 norm of the reprojection error gives a statistically optimal estimate. This has been solved for two views. However, for three or more views, it is not clear how this should be done. A previously proposed, but computationally impractical, method draws on Gröbner basis techniques to solve for the complete set of stationary points of the cost function. We show how this method can be modified to become significantly more stable and hence given a fast implementation in standard IEEE double precision. We evaluate the precision and speed of the new method on both synthetic and real data. The algorithm has been implemented in a freely available software package which can be downloaded from the Internet.
|
|
| 7. |
- Byröd, Martin, et al.
(författare)
-
Improving numerical accuracy of Grobner basis polynomial equation solvers
- 2007
-
Ingår i: Proceedings of the IEEE 11th International Conference on Computer Vision. - 1550-5499. - 9781424416318 ; , s. 449-456
-
Konferensbidrag (refereegranskat)abstract
- This paper presents techniques for improving the numerical stability of Grobner basis solvers for polynomial equations. Recently Grobner basis methods have been used succesfully to solve polynomial equations arising in global optimization e.g. three view triangulation and in many important minimal cases of structure from motion. Such methods work extremely well for problems of reasonably low degree, involving a few variables. Currently, the limiting factor in using these methods for larger and more demanding problems is numerical difficulties. In the paper we (i) show how to change basis in the quotient space R[x]/I and propose a strategy for selecting a basis which improves the conditioning of a crucial elimination step, (ii) use this technique to devise a Grobner basis with improved precision and (iii) show how solving for the eigenvalues instead of eigenvectors can be used to improve precision further while retaining the same speed. We study these methods on some of the latest reported uses of Grobner basis methods and demonstrate dramatically improved numerical precision using these new techniques making it possible to solve a larger class of problems than previously.
|
|
| 8. |
- Byröd, Martin, et al.
(författare)
-
Minimal Solutions for Panoramic Stitching with Radial Distortion
- 2009
-
Ingår i: British Machine Vision Conference.
-
Konferensbidrag (refereegranskat)abstract
- This paper presents a solution to panoramic image stitching of two images with co- inciding optical centers, but unknown focal length and radial distortion. The algorithm operates with a minimal set of corresponding points (three) which means that it is well suited for use in any RANSAC style algorithm for simultaneous estimation of geometry and outlier rejection. Compared to a previous method for this problem, we are able to guarantee that the right solution is found in all cases. The solution is obtained by solving a small system of polynomial equations. The proposed algorithm has been integrated in a complete multi image stitching system and we evaluate its performance on real images with lens distortion. We demonstrate both quantitative and qualitative improvements compared to state of the art methods.
|
|
| 9. |
- Josephson, Klas, et al.
(författare)
-
Image-based localization using hybrid feature correspondences
- 2007
-
Ingår i: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. - 1063-6919. ; , s. 2732-2739
-
Konferensbidrag (refereegranskat)abstract
- Where am I and what am I seeing? This is a classical vision problem and this paper presents a solution based on efficient use of a combination of 2D and 3D features. Given a model of a scene, the objective is to find the relative camera location of a new input image. Unlike traditional hypothesize-and-test methods that try to estimate the unknown camera position based on 3D model features only, or alternatively, based on 2D model features only, we show that using a mixture of such features, that is, a hybrid correspondence set, may improve performance. We use minimal cases of structure-from-motion for hypothesis generation in a RANSAC engine. For this purpose, several new and useful minimal cases are derived for calibrated, semi-calibrated and uncalibrated settings. Based on algebraic geometry methods, we show how these minimal hybrid cases can be solved efficiently. The whole approach has been validated on both synthetic and real data, and we demonstrate improvements compared to previous work. © 2007 IEEE.
|
|
| 10. |
- Kuang, Yubin, et al.
(författare)
-
Optimizing Visual Vocabularies Using Soft Assignment Entropies
- 2011
-
Ingår i: Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 9783642192814 - 9783642192821 ; 6495, s. 255-268
-
Konferensbidrag (refereegranskat)abstract
- The state of the art for large database object retrieval in images is based on quantizing descriptors of interest points into visual words. High similarity between matching image representations (as bags of words) is based upon the assumption that matched points in the two images end up in similar words in hard assignment or in similar representations in soft assignment techniques. In this paper we study how ground truth correspondences can be used to generate better visual vocabularies. Matching of image patches can be done e.g. using deformable models or from estimating 3D geometry. For optimization of the vocabulary, we propose minimizing the entropies of soft assignment of points. We base our clustering on hierarchical k-splits. The results from our entropy based clustering are compared with hierarchical k-means. The vocabularies have been tested on real data with decreased entropy and increased true positive rate, as well as better retrieval performance.
|
|
