Global Optimization in Computer Vision: Convexity, Cuts and Approximation Algorithms
Global Optimization in Computer Vision: Convexity, Cuts and Approximation Algorithms
复制标题
计算机视觉中的全局优化：凸性、切割和近似算法
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Carl Olsson
中科院分区：
文献类型：
--
作者：
Carl Olsson
计算机视觉如今是一个广泛的研究领域，包括机器人视觉、图像分析、模式识别、医学成像和几何重建问题等主题。在过去的几十年里，不同计算机视觉应用的理解和建模取得了快速发展。尽管大量工作致力于对不同问题进行建模，但在推导最佳解决这些问题的算法上花费的工作却很少。通常，一种称为局部搜索方法，例如基于牛顿的方法。在本文中，我们感兴趣的是开发保证找到全局最优解决方案的方法。通常，所考虑的优化问题是非凸的，并且可能有许多局部最优值。论文大致可分为两个部分和两个绪论章节。在第一部分（第 3-5 章）中，我们从优化的角度研究各种多视图几何问题。在此设置中，我们通常尝试估计相机位置和方向以及由 3D 点表示的观察结构。该估计是通过最小化重投影误差来完成的，即最小化重投影的 3D 点与其相应的图像测量之间的距离。在第三章中，我们考虑残差可以写成由投影组成的仿射函数的情况。我们将这种情况称为仿射投影估计。已知该问题的残差是拟凸函数的示例。由于在最大运算下保留了拟凸性，因此在最小化 L∞ 范数（即最小化最大误差）时可以使用有效的方法。在这项工作中，我们证明它们也是伪凸的，这是一个更强的属性并且具有算法含义。具体来说，我们证明 KKT 条件足以实现全局最优。我们还考虑L2范数版本，即最小二乘估计。尽管目标函数是非凸的，但我们表明通常可以验证局部最小值是否是全局的。在第 4 章和第 5 章中，我们考虑仿射投影估计框架之外的多视图问题。首先我们考虑异常值问题，其次考虑正交约束问题。尽管这些问题更加困难，但我们表明在某些情况下可以使用全局优化的方法来解决它们。在第二部分，第 6-8 章中，我们考虑解决变分问题的割法。在第六章中，我们考虑与众所周知的图割方法相对应的连续方法。虽然已经观察到图形切割有利于沿着图形边缘的方向进行切割，但连续切割会产生更平滑的切割。我们扩展了连续框架以包括具有各向异性度量的切割，并且我们表明 α 扩展的概念也可以在连续框架中制定。我们得出与离散情况相同的界限。在第 7 章和第 8 章中，我们考虑非子模能量，因此没有已知的多项式时间算法来解决这些问题。我们提出了两种基于谱松弛的半定规划替代方案。在最后一章中，我们提出了用于图像分割的经典归一化切割方法的重新表述。使用此公式可以在优化中纳入上下文信息。 （较少的）
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)