Global Optimization in Computer Vision: Convexity, Cuts and Approximation Algorithms
(2009)- Abstract
- Computer vision is today a wide research area including topics like robot vision, image analysis, pattern recognition, medical imaging and geometric reconstruction problems. Over the past decades there has been a rapid development in understanding and modeling different computer vision applications. Even though much work has been devoted to modelling different problems, less work has been spent on deriving algorithms that solve these problems optimally. Generally one is referred to local search methods such as Newton based method. In this thesis we are interested in developing methods that are guaranteed to find globally optimal solutions. Typically the considered optimization problems are non-convex and may have many local... (More)
- Computer vision is today a wide research area including topics like robot vision, image analysis, pattern recognition, medical imaging and geometric reconstruction problems. Over the past decades there has been a rapid development in understanding and modeling different computer vision applications. Even though much work has been devoted to modelling different problems, less work has been spent on deriving algorithms that solve these problems optimally. Generally one is referred to local search methods such as Newton based method. In this thesis we are interested in developing methods that are guaranteed to find globally optimal solutions. Typically the considered optimization problems are non-convex and may have many local optima.
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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1392606
- author
- Olsson, Carl LU
- supervisor
-
- Fredrik Kahl LU
- opponent
-
- Prof. Boykov, Yuri, University of Western Ontario, Canada
- organization
- publishing date
- 2009
- type
- Thesis
- publication status
- published
- subject
- keywords
- Spectral Relaxation, Normalized Cuts, Continuous Cuts, Segmentation, Generalized Convexity, 3D-Reconstruction, Global Optimization, Multiple View Geometry, Trust Region Subproblem
- pages
- 216 pages
- publisher
- Centre for Mathematical Sciences, Lund University
- defense location
- Lecture hall MH:C, Centre for Mathematical Studies, Sölvegatan 18, Lund University Faculty of Engineering
- defense date
- 2009-05-29 13:15:00
- ISBN
- 978-91-628-7784-2
- language
- English
- LU publication?
- yes
- id
- 58efa72a-4925-498d-b6df-abc6aba0a70a (old id 1392606)
- date added to LUP
- 2016-04-01 13:29:25
- date last changed
- 2018-11-21 20:16:39
@phdthesis{58efa72a-4925-498d-b6df-abc6aba0a70a,
abstract = {{Computer vision is today a wide research area including topics like robot vision, image analysis, pattern recognition, medical imaging and geometric reconstruction problems. Over the past decades there has been a rapid development in understanding and modeling different computer vision applications. Even though much work has been devoted to modelling different problems, less work has been spent on deriving algorithms that solve these problems optimally. Generally one is referred to local search methods such as Newton based method. In this thesis we are interested in developing methods that are guaranteed to find globally optimal solutions. Typically the considered optimization problems are non-convex and may have many local optima.<br/><br>
<br/><br>
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.<br/><br>
<br/><br>
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.<br/><br>
<br/><br>
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.<br/><br>
<br/><br>
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.}},
author = {{Olsson, Carl}},
isbn = {{978-91-628-7784-2}},
keywords = {{Spectral Relaxation; Normalized Cuts; Continuous Cuts; Segmentation; Generalized Convexity; 3D-Reconstruction; Global Optimization; Multiple View Geometry; Trust Region Subproblem}},
language = {{eng}},
publisher = {{Centre for Mathematical Sciences, Lund University}},
school = {{Lund University}},
title = {{Global Optimization in Computer Vision: Convexity, Cuts and Approximation Algorithms}},
year = {{2009}},
}