Global Optimization in Computer Vision: Convexity, Cuts and Approximation Algorithms
Author
Summary, in English
The thesis can roughly be divided into two parts and two introductory chapters. In the first part, Chapters 3-5, we study various multiple view geometry problems from an optimization point of view. In this setting we typically try to estimate camera positions and orientations and the viewed structure which is represented by 3D points. The estimation is done by minimizing the reprojection error, that is, minimizing the distance between a reprojected 3D point and its corresponding image measurement.
In Chapter 3 we consider the case when the residual errors can be written as affine functions composed with a projection. We refer to this case as affine projective estimation. The residuals of this problem are known to be examples of quasiconvex functions. Since quasiconvexity is preserved under the max operation it is possible to use efficient methods when minimizing the L∞ norm, that is, minimizing the maximal error. In this work we show that they are also pseudoconvex, which is a stronger property and has algorithmic implications. Specifically we show that the KKT conditions are sufficient for a global optimum. We also consider the L2 norm version, that is, least squares estimation. Although the objective function is non-convex, we show that often it is possible to verify that a local minimum is global.
In Chapters 4 and 5 we consider multiview problems which are outside the framework of affine-projective estimation. Firstly we consider problems with outliers and secondly problems with orthogonal constraints. Although these are more difficult we show that in certain cases they can be solved using methods from global optimization.
In the second part, Chapters 6-8, we consider cut methods for solving variational problems. In Chapter 6 we consider a continuous counterpart to the well known method of graph cuts. While graph cuts have been observed to favour cuts in directions along the graph edges, continuous cuts produce cuts that are smoother. We extend the continuous framework to include cuts with anisotropic metrics and we show that the concept of α-expansion can be formulated in the continuous framework as well. We derive the same bounds as in the discrete case. In Chapters 7 and 8 we consider energies which are not submodular and hence there are no known polynomial time algorithms for solving these. We present two alternatives to semidefinite programming, based on spectral relaxations. In the final chapter we present a reformulation of the classical normalized cut method for image segmentation. Using this formulation it is possible to incorporate contextual information in the optimization.
Department/s
- Mathematics (Faculty of Engineering)
- Mathematical Imaging Group
Publishing year
2009
Language
English
Document type
Dissertation
Publisher
Centre for Mathematical Sciences, Lund University
Topic
- Computer Vision and Robotics (Autonomous Systems)
- Mathematics
Keywords
- Spectral Relaxation
- Normalized Cuts
- Continuous Cuts
- Segmentation
- Generalized Convexity
- 3D-Reconstruction
- Global Optimization
- Multiple View Geometry
- Trust Region Subproblem
Status
Published
Research group
- Mathematical Imaging Group
Supervisor
- Fredrik Kahl
ISBN/ISSN/Other
- ISBN: 978-91-628-7784-2
Defence date
29 May 2009
Defence time
13:15
Defence place
Lecture hall MH:C, Centre for Mathematical Studies, Sölvegatan 18, Lund University Faculty of Engineering
Opponent
- Yuri Boykov (Prof.)