Shape matching is an attempt to operationalize our intuitive notion of similarity between shapes: if we consider for example the two handwritten letters in figure 1, they appear rather similar to a human observer, while being radically different if compared as vectors of pixels.
One way to address this issue could be to design a notion of distance between two shapes : then, two shapes that match pretty well will be close in terms of this distance. To this end, we need first to define in a more rigorous way what is meant by the shape of an object. In mathematical terms, the shape of an object is classically defined as an equivalence class under the group of similarity transformations. Roughly speaking, this just means that we remove all information concerning location, scale and orientation. Thus, two objects can be said to have the same shape if they are similar in the sense of Euclidean geometry.
However, such a definition is too restrictive for our purposes: such a definition only tells us when two shapes are exactly the same. But in practice, objects rarely have the same shape, due to measurement errors. Therefore, we need need to relax a little this definition to obtain the desired distance notion.
Description of the procedure
In the approach we investigate here, we will, as suggested by , treat an object as a (possibly infinite) point set and we assume that the shape of an object is captured by a finite subset of its points. In practice, we sample the internal and external contour of the object using an edge detector (see figure 2). This gives us a set , of points. These points need not to be landmarks (points of special interest for the considered shape): they can simply be chosen uniformly spaced, which is particularly convenient for an unsupervised shape matching procedure.
Then, we face a correspondence problem: for each point on the first shape, we want to find the “best” matching point on the second shape. This matching can be efficiently performed by using rich local descriptors of the shape. In our case, we will use the shape context, introduced in , as a rich local descriptor. The idea is the following :
Given a point on the shape, we consider the set of vectors originating from a point to all other sample points on a shape. These vectors express the configuration of the entire point with respect to the reference point (see figure 3). Obviously, as the number of points increase, the description of the shape becomes more precise. But the full set of vectors is much too detailed to be used as a shape descriptor, and we choose a more compact descriptor: we consider the densities of these vectors in the log-polar space.
More specifically, for each point on the shape, the shape context of is defined by the histogram (see figure 4):
where the bins are taken uniformly in the log-polar space.
Then, the problem is to compare the shape context of two points on the first shape and on the second shape. We use the test statistic to determine wether or not two histograms (i.e. shape context) are significantly different:
This statistic can be interpreted as the cost of matching and .
Then, we draw a bipartite graph, with nodes the sampled points of the first and second shape. Then, every points and are linked by an edge with weight if we cannot reject the hypothesis that their two shape context are the same (see figure 5). This gives us for every point on the first shape, a set of potential match on the second one, and respectively (see figure 5).
Finally, we want to obtain the best bipartite graph matching, namely, we want to minimize the total cost matching,
with the constraint that the matching be one-to-one, is a permutation on the neighbors of . Applied to the case of the two “o”s we obtain the best matching represented in figure 6.
Conclusion and milestones for this semester
We observe that the results obtained are pretty encouraging in the context of matching two simple shapes like the two”o”‘s in the figures above. We need now to test this procedure on more complex shapes such as ornaments, and see how well it performs on it. If the results are satisfactory, then we will try to implement the procedure on C++ to make it more efficient, and will to apply it to a database of ornaments. This will provide us with a graph of shapes (each ornaments) with distance between them (total cost matching). Then, we could design a classifier on this graph (a cluster analysis for example could be an approach).
 S. Belongie,J. malik, J. Puzicha, Shape Matching an Object Recognition using Shape Contexts, IEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 24, April 2002