TY - GEN
T1 - Point probe decision trees for geometric concept classes
AU - Arkin, Esther M.
AU - Goodrich, Michael T.
AU - Mitchell, Joseph S.B.
AU - Mount, David
AU - Piatko, Christine D.
AU - Skiena, Steven S.
N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1993.
PY - 1993
Y1 - 1993
N2 - A fundamental problem in model-based computer vision is that of identifying to which of a given set of concept classes of geometric models an observed model belongs. Considering a “probe” to be an oracle that tells whether or not the observed model is present at a given point in an image, 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 in which class the observed model belongs. We prove a hardness result and give strategies that obtain decision trees whose height is within a log factor of optimal.
AB - A fundamental problem in model-based computer vision is that of identifying to which of a given set of concept classes of geometric models an observed model belongs. Considering a “probe” to be an oracle that tells whether or not the observed model is present at a given point in an image, 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 in which class the observed model belongs. We prove a hardness result and give strategies that obtain decision trees whose height is within a log factor of optimal.
UR - https://www.scopus.com/pages/publications/2842520553
U2 - 10.1007/3-540-57155-8_239
DO - 10.1007/3-540-57155-8_239
M3 - Conference contribution
SN - 9783540571551
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 95
EP - 106
BT - Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings
A2 - Dehne, Frank
A2 - Sack, Jorg-Rudiger
A2 - Santoro, Nicola
A2 - Whitesides, Sue
PB - Springer Verlag
T2 - 3rd Workshop on Algorithms and Data Structures, WADS 1993
Y2 - 11 August 1993 through 13 August 1993
ER -