Decision trees for geometric models

A fundamental problem in model-based computer vision is that of identifying which of a given set of geometric models is present at 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 show that a [lg k] height binary decision tree always exists for k polygonal models (in fixed position), provided (1) they are non-degenerate (do not share boundaries) and (2) they share a common point of intersection. Further, we give an efficient algorithm for constructing such decision trees when the models are given as a set of polygons in the plane. We show that constructing a minimum height tree is NP-complete if either of the two assumptions is omitted. We provide an efficient greedy heuristic strategy and show that, in the general case, it yields a decision tree whose height is at most [lg n] times that of an optimal tree. Finally, we discuss some restricted cases whose special structure allows for improved results.