1.4.2
The role of an energy function in minimization-based vision is twofold: (1) as the quantitative measure of the global quality of the solution and (2) as a guide to the search for a minimal solution. As the quantitative cost measure, an energy function defines the minimal solution as its minimum, usually a global one. In this regard, it is important to formulate an energy function so that the ``correct solution'' is embedded as the minimum. We call this the correctness of the formulation .
To understand an optimization approach, one should not mix problems in formulation and those in search. Differentiating the two different kinds of problems help debug the modeling. For example, if the output of an optimization procedure (assuming the implementation is correct) is not what is expected, there are two possible reasons: (1) the formulation of the objective function is not a correct one for modeling the reality and (2) the output is not a global minimum as the optimal solution is defined. Due to which one is the problem should be identified before the modeling can be improved.
The role of an energy function as a guide to the search may or may not be fully played. In real minimization, for example, when the energy function is smooth and convex w.r.t. its variables, global minimization is equivalent to local minimization and the gradient of the energy function provides sufficient information about where to search for the global solution. In this case, the role of guiding the search can be fully played. However, when the problem is non-convex, there is no general method which can efficiently utilize the energy function to guide the search. In this case, the role as the search-guide is underplayed.
In certain cases, it may be advantageous to consider the formulation of an energy function and the search simultaneously. This is to formulate the function appropriately to facilitate the search. The work of graduated non-convexity (GNC) [Blake and Zisserman 1987] is an example in this regard. There, the energy function is deformed gradually from a convex form to its target form in the process of approximating the global solution using a gradient-based algorithm.
Local minimization in real spaces is the most mature area in optimization and many formal approaches exist for solving it. This is not so for combinatorial and global minimization. In the latter cases, heuristics become an important and perhaps necessary element in practice. In the heuristic treatment of global minimization, rather restrictive assumptions are made. An example is the bounded model [Baird 1985 ; Breuel 1992]. It assumes that a measurement error is upper-bounded by a certain threshold (within the threshold, the error may be assumed to be evenly distributed). Whether the assumption is valid depends on the threshold. It is absolutely true when the threshold is infinitely large. But in practice, the threshold is almost always set to a value which is less than that required to entirely validate the bounded-error assumption. The lower the value, the higher the efficiency is, but the less general the algorithm becomes.
In the hypothesis-verification approach, efficient algorithms are used to generate hypothetical solutions, such as Hough transform [Hough 1962 ; Duda and Hart 1972], interpretation tree search [Grimson and Lozano-Prez 1987] and geometric hashing [Lamdan and wolfson 1988]. The efficiency comes from the fast elimination of infeasible solutions, or pruning of the solution space, by taking advantages of heuristics. In this way, a relatively small number of solution candidates are picked up relatively quickly and are then verified or evaluated thoroughly, for example, by using an energy function. In this strategy, the energy function is used for the evaluation only, not as a guide to the search.
Note that the advantage of formal approaches is in the evaluation and the advantage of heuristic approaches is in the search. A good strategy for the overall design of a specialized system may be the following: use a heuristic algorithm to quickly find a small number of solution candidates and then evaluate the found candidates using an energy function derived formally to give the best solution.