EFFICIENT DETERMINATION OF SHAPE FROM MULTIPLE IMAGES CONTAINING PARTIAL INFORMATION

TitleEFFICIENT DETERMINATION OF SHAPE FROM MULTIPLE IMAGES CONTAINING PARTIAL INFORMATION
Publication TypeJournal Articles
Year of Publication1998
AuthorsBasri R, GROVE ADAMJ, Jacobs DW
JournalPattern Recognition
Volume31
Issue11
Pagination1691 - 1703
Date Published1998/11//
ISBN Number0031-3203
Keywords2-D shape recovery from multiple images, NP-complete, Shape recovery with occlusion
Abstract

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.

URLhttp://www.sciencedirect.com/science/article/pii/S0031320398000508
DOI10.1016/S0031-3203(98)00050-8