Localization vs. Identification of Semi-Algebraic Sets

摘要

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 of an unknown object from labeled examples input, and the task of localization in which the identity of the target is known and its location in some background scene has to be determined.