Matching and Interpolation of Shapes using Unions of Circles

Abstract

While the notion of shape of an object is very intuitive, its precise definition is very elusive, and defining a useful metric for the shape distance between objects is a difficult endeavor. At the same time many successful techniques have been developed which interpolate between two objects, so in essence interpolate between shapes.W e present here work which uses a representation of objects as union of circles to define a distance between two objects and to base a method to interpolate between the two. This method can be used in a totally automatic fashion (that is, without any user intervention), or users can guide a pre-registration phase as well as a segmentation phase, after which the matched segments are interpolated pair-wise. The union of circles representation of the two objects is obtained from the Delaunay triangulation of their boundary points. The circles can be simplified to obtain smaller data sets. The circles are then optimally matched according to a distance metric between circles which is a function of their position, size, and feature, that is, a local configuration of circles. The interpolation between the two objects is then obtained by interpolating between the matched pairs of circles (the interpolations can be affine or non -affine).Examples with simple and more complex objects show how the technique can give results which correspond closely to the human notion of shape interpolation. The interpolations shown include some between a calf and a cow and between a cow and a giraffe. The examples given are in two dimensions, but all the steps except the segmentation have been implemented as well for three dimensional objects. W e also show the results of computation of distances between the objects used in our examples.