Technical Report CS0773

Authors: S. Ben-David and M. Lindenbaum
PDFNot Available

How difficult is it to find the position of a known object using random samples? We study this question, which is central to Computer Vision and Robotics, in a formal way. We compare the information complexity of two types of tasks: the task of identification, in which all the student known is a description of a natural class to which the object belongs, and the task of localization, in which he knows that the target is a transformed image of some given object. We model localization as the task of learning the class of transformed instances of the given object. We apply some fundamental results from Algebraic Geometry to bound the VC-dimension of such `transformed class' and compare it to the VC-dimension of some natural library classes to which the objects belong. We carry on the comparison to the scenario of learning under the uniform distribution, which leads us to calculating the \epsilon-entropy of the relevant classes. Our analysis provides a mathematical ground to the intuition that Localization is indeed much easier than Identification.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1993
To the main CS technical reports page

Computer science department, Technion