R. Basri et al., EFFICIENT DETERMINATION OF SHAPE FROM MULTIPLE IMAGES CONTAINING PARTIAL INFORMATION, Pattern recognition, 31(11), 1998, pp. 1691-1703
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.