Marco Alexander Treiber - Optimization for Computer Vision

Marco Alexander Treiber 1

(1)

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.

Optimization plays an important role in computer vision, because many computer vision algorithms employ an optimization step at some point of their proceeding. Before taking a closer look at the diverse optimization methods and their utilization in computer vision, lets first clarify the concept of optimization. Intuitively, in optimization we have to find a solution for a given problem which is best in the sense of a certain criterion.

Consider a satnav system, for example: here the satnav has to find the best route to a destination location. In order to rate alternative solutions and eventually find out which solution is best, a suitable criterion has to be applied. A reasonable criterion could be the length of the routes. We then would expect the optimization algorithm to select the route of shortest length as a solution. Observe, however, that other criteria are possible, which might lead to different optimal solutions, e.g., the time it takes to travel the route leading to the fastest route as a solution.

Mathematically speaking, optimization can be described as follows: Given a function which is called the objective function , find the argument which minimizes :

S defines the so-called solution set, which is the set of all possible solutions for our optimization problem. Sometimes, the unknown(s) are referred to design variables . The function describes the optimization criterion, i.e., enables us to calculate a quantity which indicates the goodness of a particular .

In the satnav example, is composed of the roads, streets, motorways, etc., stored in the database of the system, is the route the system has to find, and the optimization criterion (which measures the optimality of a possible solution) could calculate the travel time or distance to the destination (or a combination of both), depending on our preferences.

Sometimes there also exist one or more additional constraints which the solution has to satisfy. In that case we talk about constrained optimization (opposed to unconstrained optimization if no such constraint exists). Referring to the satnav example, constraints could be that the route has to pass through a certain location or that we dont want to use toll roads.

As a summary, an optimization problem has the following components:

In order to be of practical use, an optimization algorithm has to find a solution in a reasonable amount of time with reasonable accuracy. Apart from the performance of the algorithm employed, this also depends on the problem at hand itself. If we can hope for a numerical solution, we say that the problem is well-posed . For assessing whether an optimization problem can be solved numerically with reasonable accuracy, the French mathematician Hadamard established several conditions which have to be fulfilled for well-posed problems:

If one or more of these conditions is not fulfilled, the problem is said to be ill-posed . If condition (3) is not fulfilled, we also speak of ill-conditioned problems.

Observe that in computer vision, we often have to solve so-called inverse problems. Consider the relationship , for example. Given some kind of observed data , the inverse problem would be the task to infer a different data representation from . The two representations are related via some kind of transformation