Acquisition of 2D Shape Models from Scenes with Overlapping Objects using String Matching

In this paper we describe a system that is able to acquire models of 2D shapes from cluttered scenes. The input of the system is a sequence of images, each of which shows an unknown number of overlapping unknown 2D objects. The system identifies matching partial shapes across different images and combines them into complete 2D shape models, thus giving a complete interpretation of the input scenes. The identification of partial shapes is based on string matching, whereas a graph search procedure is used for shape model generation. The system has been fully implemented and tested on images containing parts of a jigsaw puzzle. Received: 20 November 1998?Received in revised form: 24 December 1998?Accepted: 4 January 1999