Bayesian Multiple Target Localization

We consider the problem of quickly localizing multiple targets by asking questions of the form “How many targets are within this set ” while ob-taining noisy answers. This setting is a gener-alization to multiple targets of the game of 20 questions in which only a single target is queried. We assume that the targets are points on the real line, or in a two dimensional plane for the experi-ments, drawn independently from a known distri-bution. We evaluate the performance of a policy using the expected entropy of the posterior dis-tribution after a fixed number of questions with noisy answers. We derive a lower bound for the value of this problem and study a specific pol-icy, named the dyadic policy. We show that this policy achieves a value which is no more than twice this lower bound when answers are noise-free, and show a more general constant factor ap-proximation guarantee for the noisy setting. We present an empirical evaluation of this policy on simulated data for the problem of detecting mul-tiple instances of the same object in an image. Fi-nally, we present experiments on localizing mul-tiple faces simultaneously on real images