EFFICIENT DETERMINATION OF SHAPE FROM MULTIPLE IMAGES CONTAINING PARTIAL INFORMATION

We consider the problem of reconstructing the shape of a 2-D object fr om multiple partial images related by scaled translations, in the pres ence of occlusion. Lindenbaum and Bruckstein have considered this prob lem in the specific case of a translating object seen by small sensors , for application to the understanding of insect vision. Their solutio n is limited by the fact that its run time is exponential in the numbe r of images and sensors. We generalize the problem to allow for arbitr ary types of occlusion of objects that translate and change scale. We show that this more general version of the problem can be solved in ti me that is polynomial in the number of sensors, but that even the orig inal problem posed by Lindenbaum and Bruckstein is, in fact, NP-hard w hen the number of images is unbounded. Finally, we consider the case w here the object is known to be convex. We show that Lindenbaum and Bru ckstein's version of the problem is then efficiently solvable even whe n many images are used, as is the general problem in certain more rest ricted cases. (C) 1998 Pattern Recognition Society. Published by Elsev ier Science Ltd. All rights reserved.