9.6.2
Apart from theory-supported methods, heuristics are often combined into search. Solution candidates are quickly located using some efficient means. They are then evaluated by the derived energy function. Because the number of such candidates is usually small, the energy values can be compared exhaustively to give the minimal solution.
Not to miss the true global solution is crucial for the success of applying heuristics. One has to balance between efficiency and danger of missing the true solution. More restricting heuristics reduce the number of generated hypotheses and increase the efficiency, but they also cause a greater chance to miss the true minimum.
The bounded noise model [Baird 1985,Breuel 1992] is a simple heuristic for approximating noise distributions to quickly reduce the search space. By checking whether an error is within the allowed bound, numerical constraints are converted into symbolic ones so that yes-or-no decision can be made to prune the search space. This strategy has been used in many methods where numerical constraints have to be converted into symbolic one. For example, in maximal cliques [Ambler et al. 1973], dynamic programming [ search [Faugeras and Hebert 1986,Grimson and Lozano-Prez 1987], symbolic compatibilities are determined; in Hough transform [Hough 1962,Duda and Hart 1972] and geometric hashing [Lamdan and Wolfson 1988], numerical values are quantized to vote accumulators.
Hypothesis-verification is another approach for efficient search. Hypotheses are generated, which may correspond to peaks in Hough transform space or geometric hashing space, or leaves of an interpretation tree [Grimson and Lozano-Prez 1987], or random samples in random sampling [Fischler and Bolles 1981,Roth and Levine 1993], or result from minimal sets of image-model correspondences in the alignment method [Huttenlocher and Ullman]. Because the number of generated hypotheses is much smaller than the number of points in the original solution space, costs incurred by hypotheses evaluation is much reduced. In [Lowe 1992], matching and measurement errors are used to determine the probability of correctness for individual labels. Techniques presented therein may be used to speed verification. All these have potential applications in MRFs to tackle the problem of low computational efficiency.