| 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)
-
Conjugate Gradient Bundle Adjustment
- 2010
-
Ingår i: Computer Vision-Eccv 2010, Pt II. - 0302-9743 .- 1611-3349. ; 6312, s. 114-127
-
Konferensbidrag (refereegranskat)abstract
- Bundle adjustment for multi-view reconstruction is traditionally done using the Levenberg-Marquardt algorithm with a direct linear solver, which is computationally very expensive. An alternative to this approach is to apply the conjugate gradients algorithm in the inner loop. Tins is appealing since the main computational step of the CG algorithm involves only a simple matrix-vector multiplication with the Jacobian. In this work we improve on the latest published approaches to bundle adjustment with conjugate gradients by making full use of the least squares nature of the problem. We employ an easy-to-compute QR factorization based block preconditioner and show how a certain property of the preconditioned system allows us to reduce the work per iteration to roughly half of the standard CG algorithm.
|
|
| 4. |
- Byröd, Martin, 1980, et al.
(författare)
-
Efficient Reachability Analysis on Modular Discrete-Event Systems using Binary Decision Diagrams
- 2006
-
Ingår i: 8th International Workshop on Discrete Event Systems, WODES 2006; Ann Arbor, MI; United States; 10 July 2006 through 12 July 2006. - 1424400538 ; , s. 288-293
-
Konferensbidrag (refereegranskat)abstract
- A well known strategy for handling the exponential complexity of modular discrete event systems is to represent the state space symbolically, using binary decision diagrams (BBDs). In this paper, key success factors in the design of efficient BDD-based reachability algorithms for synthesis and verification are discussed. It is also shown how the modular structure of a discrete event system (DES) can be utilized by taking advantage of the process communication graph and partitioning techniques. A reachability algorithm based on these principles is discussed and a proof of correctness for the algorithm is given.
|
|
| 5. |
- 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.
|
|
| 6. |
- 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.
|
|
| 7. |
- 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.
|
|
| 8. |
- 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.
|
|
| 9. |
- 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.
|
|
| 10. |
- 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.
|
|
