An A* perspective on deterministic optimization for deformable templates

Many vision problems involve the detection of the boundary of an object, li ke a hand, or the tracking of a one-dimensional structure, such as a road i n an aerial photograph. These problems can be formulated in terms of Bayesi an probability theory and hence expressed as optimization problems on trees or graphs. These optimization problems are difficult because they involve search through a high-dimensional space corresponding to the possible defor mations of the object. In this paper, we use the theory of A* heuristic alg orithms (Pearl, Heuristics, Addison-Wesley, Reading, MA, 1984) to compare t hree deterministic algorithms - Dijkstra, Dynamic Programming, and Twenty Q uestions - which have been applied to these problems. We point out that the first two algorithms can be thought of as special cases of A* with implici t choices of heuristics. We then analyze the twenty questions, or minimum e ntropy, algorithm which has recently been developed by Geman and Jedynak (G eman and Jedynak, IEEE Trans. Pattern Anal. Mach. Intell. 18 (1) (1996) 1-1 4) as a highly effective. and intuitive, toe search algorithm for road trac king. First we discuss its relationship to the focus of attention planning strategy used on causal graphs, or Bayes nets (Pearl, Probalilistic Reasoni ng in Intelligent Systems, Morgan Kauffman, San Mateo, CA, 1988). Then we p rove that, in many cases, twenty questions is equivalent to an algorithm, w hich we call A +, which is a variant of A*. Thus all three deterministic al gorithms are either exact, or approximate, versions of A* with implicit heu ristics. We then discuss choices of heuristics for optimization problems an d contrast the relative effectiveness of different heuristics. Finally, we briefly summarize some recent work (Yuille and Coughlan, Proceedings NIPS'9 8, 1998; Yuille and Coughlan, Trans. Pattern Anal. Mach. Intell. (1999), su bmitted for publication) which show that the Bayesian formulation can lead to a natural choice of heuristics which will be very effective with high pr obability. (C) 2000 Published by Elsevier Science Ltd. All rights reserved.