TY - JOUR
T1 - EFFICIENT DETERMINATION OF SHAPE FROM MULTIPLE IMAGES CONTAINING PARTIAL INFORMATION
JF - Pattern Recognition
Y1 - 1998
A1 - Basri,Ronen
A1 - GROVE,ADAM J.
A1 - Jacobs, David W.
KW - 2-D shape recovery from multiple images
KW - NP-complete
KW - Shape recovery with occlusion
AB - We consider the problem of reconstructing the shape of a 2-D object from multiple partial images related by scaled translations, in the presence of occlusion. Lindenbaum and Bruckstein have considered this problem in the specific case of a translating object seen by small sensors, for application to the understanding of insect vision. Their solution is limited by the fact that its run time is exponential in the number of images and sensors. We generalize the problem to allow for arbitrary types of occlusion of objects that translate and change scale. We show that this more general version of the problem can be solved in time that is polynomial in the number of sensors, but that even the original problem posed by Lindenbaum and Bruckstein is, in fact, NP-hard when the number of images is unbounded. Finally, we consider the case where the object is known to be convex. We show that Lindenbaum and Brucksteinâ€™s version of the problem is then efficiently solvable even when many images are used, as is the general problem in certain more restricted cases.
VL - 31
SN - 0031-3203
UR - http://www.sciencedirect.com/science/article/pii/S0031320398000508
CP - 11
M3 - 10.1016/S0031-3203(98)00050-8
ER -