Loading...
Please wait, while we are loading the content...
Similar Documents
International Journal of Computational Geometry & Applications C World Scientiic Publishing Company Decision Trees for Geometric Models
| Content Provider | Semantic Scholar |
|---|---|
| Author | NyDepartment, Esther M. A. R. K. I. |
| Copyright Year | 1993 |
| Abstract | A fundamental problem in model-based computer vision is that of identifying 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 e cient 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 dlgke height binary decision tree always exists for k polygonal models (in xed position), provided (1) they are non-degenerate (do not share boundaries) and (2) they share a common point of intersection. Further, we give an e cient algorithm for constructing such decision tress 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 e cient greedy heuristic strategy and show that, in the general case, it yields a decision tree whose height is at most dlgke times that of an optimal tree. Finally, we discuss some restricted cases whose special structure allows for improved results. |
| File Format | PDF HTM / HTML |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
