Global Optimization in Computer Vision: Convexity, Cuts and Approximation Algorithms
Författare
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.
Avdelning/ar
- Matematik LTH
- Mathematical Imaging Group
Publiceringsår
2009
Språk
Engelska
Dokumenttyp
Doktorsavhandling
Förlag
Centre for Mathematical Sciences, Lund University
Ämne
- Computer Vision and Robotics (Autonomous Systems)
- Mathematics
Nyckelord
- Spectral Relaxation
- Normalized Cuts
- Continuous Cuts
- Segmentation
- Generalized Convexity
- 3D-Reconstruction
- Global Optimization
- Multiple View Geometry
- Trust Region Subproblem
Status
Published
Forskningsgrupp
- Mathematical Imaging Group
Handledare
- Fredrik Kahl
ISBN/ISSN/Övrigt
- ISBN: 978-91-628-7784-2
Försvarsdatum
29 maj 2009
Försvarstid
13:15
Försvarsplats
Lecture hall MH:C, Centre for Mathematical Studies, Sölvegatan 18, Lund University Faculty of Engineering
Opponent
- Yuri Boykov (Prof.)