Decision trees for geometric models

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 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.

References

1. 1.E. Arkin and J. Mitchell. Applications of combinatorics and computational geometry to pattern recognition. Technical report, Gornen University, 1990.]]
2. 2.P. Belleville and T. Shermer. Probing polygons minimially is hard. Technical Report 91-12, Dept. of Computing Science, Simon Fraser University, Burnaby, B. C. Canada, December 1991.]]
3. 3.H. Bernstein. Determining the shape of a convex n-sided polygon by using 2n + k tactile probes, information Processing Letters, 22:255-260, 1986.]]
4. 4.E. Bienenstock, D. Geman, and S. Geman. A relational approach in object recognition. Technical report, Brown University, 1988.]]
5. 5.E. Bienenstock, D. Geman, S. Geman, and D.E. Mc- Clure. Phase II technical report, development of laser radar ATR algorithms. Technical Report Contract No. DAAL02-89-C-0081, CECOM Center for Night Vision and Electro-Optics, October 1990.]]
6. 6.B. ChazeUe and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. J. A CM, 39:1-54, 1992.]]
7. 7.R. Chin and C. Dyer. Model-based recognition in robot vision. Computing Surveys, pages 67-108, 1986.]]
8. 8.H. De Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10:41-51, 1990.]]
9. 9.I-I. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, Heidelberg, 1987.]]
10. 10.A. Fiat and A. Shamir. How to find a battleship. Networks, 19:361-371, 1989.]]
11. 11.R. J. Fowler, M. S. Paterson, and L. Tanimoto. Optimal packing and covering in the plane are NP-complete. Information Processing Letters, 12:133-137, 1981.]]
12. 12.K. Y. Fung, T. M. Nicholl, R. E. Tarjan, and C. J. Van Wyk. Simplified linear-time Jordan sorting and polygon clipping. Inform. Process. Lett., 35:85-92, 1990.]]
13. 13.M. Garey. Optimal binary identification procedures. SIAM J. Appl. Math., 23:173-186, 1972.]]
14. 14.P. Gaston and T. Lozano-Perez. Tactile recognition and localization using object models: The case of polyhedra on a plane. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-6:257-266, May 1984.]]
15. 15.M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, NY, 1980.]]
16. 16.W. E. Grimson. The combinatorics of local constraints in model-based recognition and localization from sparse dat~. J. A CM, 33:658-686, 1986.]]
17. 17.W. E. Grimson and T. Lozano-Perez. Localizing overlapping parts by searching the interpretation tree. IEEE Transactions on Pattern Recognition and Machine Intelligence, PAMI-9:469-482, July 1987.]]
18. 18.K. Hoffmann, K. Mehlhorn, P. Rosenstiehl, and R. E. Tarjan. Sorting Jordan sequences in linear time using level-linked search trees. Inform. Control, 68:170-184, 1986.]]
19. 19.L. Hyafil and R. Rivest. Constructing optimal binary decision trees is NP-complete. Information Processing Letters, 5:15-17, 1976.]]
20. 20.D. S. Johnson. Approximation algorithms for combinatorial problems. J. Comp. Sys. Sciences, 9:256-278, 1974.]]
21. 21.E. Joseph and S. Skiena. Model-based probing strategies for convex polygons. Computational Geometry: Theory and Applications, 2, 1992.]]
22. 22.D. Lichtenstein. Planar formulae and their uses. SIAM J. Comput., 11:329-343, 1982.]]
23. 23.K. Lyons and D. Rappaport. An efficienlL algorithm for identifying objects using robot probes. The Visual Computer, to appear.]]
24. 24.B. Motet. Decision trees and diagrams. Computing Surveys, pages 593-623, 1982.]]
25. 25.C. H. Papadimitriou. On certain problems in algorithmic vision. Technical report, Computer Science, UCSD, 1991.]]
26. 26.S. Skiena. Interactive reconstruction via probing. IEEE Proceedings, 80:1364-1383, 1992.]]

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Computer vision

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Trees

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry