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 nonconvex 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 nonconvex and may have many local optima.
The thesis can roughly be divided into two parts and two introductory chapters. In the first part, Chapters 35, 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 nonconvex, 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 affineprojective 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 68, 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:
http://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, 3DReconstruction, 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
 20090529 13:15
 ISSN
 14040034
 ISBN
 9789162877842
 language
 English
 LU publication?
 yes
 id
 58efa72a4925498db6dfabc6aba0a70a (old id 1392606)
 date added to LUP
 20090505 10:31:49
 date last changed
 20160919 08:44:47
@phdthesis{58efa72a4925498db6dfabc6aba0a70a, 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 nonconvex 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 35, 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 nonconvex, 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 affineprojective 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 68, 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 = {9789162877842}, issn = {14040034}, keyword = {Spectral Relaxation,Normalized Cuts,Continuous Cuts,Segmentation,Generalized Convexity,3DReconstruction,Global Optimization,Multiple View Geometry,Trust Region Subproblem}, language = {eng}, pages = {216}, publisher = {Centre for Mathematical Sciences, Lund University}, school = {Lund University}, title = {Global Optimization in Computer Vision: Convexity, Cuts and Approximation Algorithms}, year = {2009}, }