DECISION TREES FOR GEOMETRIC-MODELS

A fundamental problem in model-based computer vision is that of identi fying which of a given set of geometric models is present in an image. Considering a ''probe'' to be an oracle that tells us whether or not a model is present at a given point, we study the problem of computing efficient strategies (''decision trees'') for probing an image, with the goal to minimize the number of probes necessary (in the worst case ) to determine which single model is present. We shaw that a inverted right perpendicular lg k inverted left perpendicular height binary dec ision tree always exists for k polygonal models (in fixed position), p rovided (1) they are non-degenerate (do not share boundaries) and (2) they share a common point of intersection. Further, we give an efficie nt algorithm for constructing such decision tress when the models are given as a set of polygons in the plane. We show that constructing a m inimum height tree is NP-complete if either of the two assumptions is omitted. We provide an efficient greedy heuristic strategy and show th at, in the general case, it yields a decision tree whose height is at most inverted right perpendicular lg k inverted left perpendicular tim es that of an optimal tree. Finally, we discuss some restricted cases whose special structure allows for improved results.