1.4.1
There are three basic issues in optimization-based vision: problem representation, objective function and optimization algorithms. There are two aspects of a representation: descriptive and computational. The former concerns how to represent image features and object shapes, which relates to photometry and geometry [Koenderink 1990 ; Mundy and Zisserman 1992 ; Kanatani 1993] and is not an emphasis of this book. The latter concerns how to represent the solution, which relates to the choice of sites and label set for a labeling problem. For example, in image segmentation, we may use a chain of boundary locations to represent the solution; we may alternatively use a region map to do the same job. Comparatively speaking, however, the region map is a more natural representation for MRFs.
The second issue is how to formulate an objective function for the optimization. The objective function maps a solution to a real number measuring the quality of the solution in terms of some goodness or cost. The formulation determines how various constraints, which may be pixel properties like intensity and color and/or context like relations between pixels or object features, are encoded into the function. Because the optimal solution which is the optimum of the objective function, the formulation defines the optimal solution.
The third is how to optimize the objective, i.e. how to search for the optimal solution in the admissible space. Two major concerns are (1) the problem of local minima existing in non-convex functions and (2) the efficiency of algorithms in space and time. They are somewhat contradictory and currently there is no algorithms which guarantee the global solution with good efficiency.
These three issues are related to one another. In the first place, the scheme of representation influences the formulation of the objective function and the design of the search algorithm. On the other hand, the formulation of an objective function affects the search. For example, suppose two objective functions has the same point as the unique global optimum but one of them is convex whereas the other is not; obviously the convex one is much more desired because it provides convenience for the search.
In the following presentation, we will be mainly dealing with minimization problems. An objective function is in the form of an energy function and is to be minimized.