nach oben

2013 | Buch

Kapitel lesen Erstes Kapitel lesen

Optimization for Computer Vision

An Introduction to Core Concepts and Methods

verfasst von: Marco Alexander Treiber

Verlag: Springer London

Buchreihe : Advances in Pattern Recognition

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This practical and authoritative text/reference presents a broad introduction to the optimization methods used specifically in computer vision. In order to facilitate understanding, the presentation of the methods is supplemented by simple flow charts, followed by pseudocode implementations that reveal deeper insights into their mode of operation. These discussions are further supported by examples taken from important applications in computer vision. Topics and features: provides a comprehensive overview of computer vision-related optimization; covers a range of techniques from classical iterative multidimensional optimization to cutting-edge topics of graph cuts and GPU-suited total variation-based optimization; describes in detail the optimization methods employed in computer vision applications; illuminates key concepts with clearly written and step-by-step explanations; presents detailed information on implementation, including pseudocode for most methods.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract

The vast majority of computer vision algorithms use some form of optimization, as they intend to find some solution which is “best” according to some criterion. Consequently, the field of optimization is worth studying for everyone being seriously interested in computer vision. In this chapter, some expressions being of widespread use in literature dealing with optimization are clarified first. Furthermore, a classification framework is presented, which intends to categorize optimization methods into the four categories continuous, discrete, combinatorial, and variational, according to the nature of the set from which they select their solution. This categorization helps to obtain an overview of the topic and serves as a basis for the structure of the remaining chapters at the same time. Additionally, some concepts being quite common in optimization and therefore being used in diverse applications are presented. Especially to mention are so-called energy functionals measuring the quality of a particular solution by calculating a quantity called “energy”, graphs, and last but not least Markov Random Fields.

Marco Alexander Treiber

Chapter 2. Continuous Optimization

Abstract

A very general approach to optimization are local search methods, where one or, more typically, multiple variables to be optimized are allowed to take continuous values. There exist numerous approaches aiming at finding the set of values which optimize (i.e., minimize or maximize) a certain objective function. The most straightforward way is possible if the objective function is a quadratic form, because then taking its first derivative and setting it to zero leads to a linear system of equations, which can be solved in one step. This proceeding is employed in linear least squares regression, e.g., where observed data is to be approximated by a function being linear in the design variables. More general functions can be tackled by iterative schemes, where the two steps of first specifying a promising search direction and subsequently performing a one-dimensional optimization along this direction are repeated iteratively until convergence. These methods can be categorized according to the extent of information about the derivatives of the objective function they utilize into zero-order, first-order, and second-order methods. Schemes for both steps of the general proceeding are treated in this chapter.

Marco Alexander Treiber

Chapter 3. Linear Programming and the Simplex Method

Abstract

Problems where the objective function to be optimized is linear in its design variables are of particular interest, because then a solution can be found very efficiently. Solutions of linear objective functions can only be unique if additional constraints exist. While the constraints bound the solution space, the linear nature of the objective ensures that the solution must be located at the border of this bounded solution space. In the case of linear constraints, the bounded solution space has the form of a polyhedron, and, hence, it suffices to seek for the solution at the vertices of the bounded space. As a consequence, the optimum can be found very fast. One method for solving linear programs is the simplex algorithm, which is one of the most famous optimization algorithms. It identifies the solution by moving from a vertex to one of its neighbors until the value of the objective cannot be reduced further for all neighboring vertices. In order to benefit from the speed advantage of linear programming, it sometimes is promising to approximate a given problem by linear relationships. Such an approximation is presented for the task of stereo disparity estimation at the end of this chapter.

Marco Alexander Treiber

Chapter 4. Variational Methods

Abstract

The main goal of many computer vision tasks can in summary be described by finding a function which is optimal according to some criteria. Examples of such functions are the two-dimensional intensity/color function of the image itself in image restoration or deblurring, two-dimensional vector fields like optical flow, or the course of a curve separating the image into multiple areas (which are all presented as examples in this chapter). This is the domain of variational optimization, which aims at estimating those functional relationships. The functional quantifying the quality of a particular solution typically consists of two terms: one for measuring the fidelity of the solution to the observed data and a second term for incorporating prior assumptions about the expected solution, e.g., smoothness constraints. There exist several ways of finding the solution, such as closed-form solutions via the so-called Euler-Lagrange equation, or iterative gradient-based schemes. Despite of the iterative and therefore inherently slow nature of the last-mentioned approach, quite simple iterative update rules can be found for some applications, which allow for a very fast implementation on massively parallel hardware like GPUs. Therefore, variational methods currently are an active area of research in computer vision.

Marco Alexander Treiber

Chapter 5. Correspondence Problems

Abstract

Quite numerous computer vision applications require an assignment of the elements of a set of some extracted salient positions/descriptors to their corresponding counterpart in a model set, at some point of their proceeding. Examples are object recognition or image registration schemes. Because an exhaustive evaluation of all possible combinations of individual assignments is infeasible in terms of runtime, more sophisticated approaches are required, and some of them will be presented in this chapter. Possible ways of speeding up the search are applying heuristics, as done in the so-called search tree, or iterative approaches like the iterative closest point method. A typical challenge when trying to find the correct correspondences is the existence of a quite large number of outliers, e.g., positions being spoiled by gross errors. The straightforward approach of minimizing total deviations runs into difficulties in that cases, and consequently, methods being more robust to outliers are required. Examples of robust schemes are the random sample consensus (RANSAC) or methods transforming the problem into a graph representation, such as spectral graph matching or bipartite graph matching as done in the so-called Hungarian algorithm.

Marco Alexander Treiber

Chapter 6. Graph Cuts

Abstract

Energy functions consisting of a pixel-wise sum of data-driven energies as well as a sum of terms affected by two adjacent pixels (aiming at ensuring consistency for neighboring pixels) are quite common in computer vision. This kind of energy can be represented well by Markov Random Fields (MRFs). If we have to take a binary decision, e.g., in binary segmentation, where each pixel has to be labeled as “object” or “background,” the MRF can be supplemented by two additional nodes, each representing one of the two labels. The globally optimal solution of the resulting graph can be found by finding its minimum cut (where the sum of the weights of all severed edges is minimized) in polynomial time by maximum flow algorithms. Graph cuts can be extended to the multi-label case, where it is either possible to find the exact solution when the labels are linearly ordered or the solution is approximated by iteratively solving binary decisions. An instance of the max-flow algorithm, binary segmentation, as well as stereo matching and optical flow calculation, which can both be interpreted as multi-labeling tasks, is presented in this chapter. Normalized cuts seeking a spectral, i.e., eigenvalue solution, complete the chapter.

Marco Alexander Treiber

Chapter 7. Dynamic Programming (DP)

Abstract

Some problems of computer vision can be formulated in a recursive manner. For this class of problems, the paradigm of dynamic programming (DP) represents an interesting tool in order to obtain a fast discrete solution. Here, the overall problem is broken down into a series of sub-problems, which are built upon each other and can therefore be solved iteratively. This way computation can be sped up considerably through the reusage of information gathered in already solved sub-problems. This chapter starts with presenting the well-known method of Dijkstra as an example of shortest path algorithms, which are closely related to DP. “Intelligent scissors” interactively segmenting an image are one example application. Furthermore, this chapter deals with two ways of applying the dynamic programming paradigm. First, dynamic programming is applicable if optimal positions or labels are to be found for a sequence of points, where the optimality criterion for each point depends on its predecessor(s). The task of calculating active contours can be reformulated in this manner. Second, some problems show a treelike structure, which makes a recursive formulation possible, too. The recognition of objects which are modeled as a configuration of parts is one example of this.

Marco Alexander Treiber

Backmatter

Titel: Optimization for Computer Vision
verfasst von: Marco Alexander Treiber
Verlag: Springer London
Electronic ISBN: 978-1-4471-5283-5
Print ISBN: 978-1-4471-5282-8
DOI: https://doi.org/10.1007/978-1-4471-5283-5

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Chapter 2. Continuous Optimization

Chapter 3. Linear Programming and the Simplex Method

Chapter 4. Variational Methods

Chapter 5. Correspondence Problems

Chapter 6. Graph Cuts

Chapter 7. Dynamic Programming (DP)

Backmatter

Premium Partner