[BlogPost 1]: Implementation of a Shape Matching procedure

In the context of the project  “Ornaments in Print” described in a previous post (see here), we are interested in creating a shape matching procedure in order to classify a large database of medieval ornaments. We investigate in this article a shape matching procedure using shape contexts, inspired from the procedure described in [1].


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.

Figure 1: Example of handwritten letters. These two shapes are very similar to a human observer, but radically different in terms of pixels.
handwritten1 handwritten2

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 [1], 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  \mathcal{P}=\{p_1,\ldots,p_n\}, p_i\in\mathbb{R}^2, of n 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.

fonts - copie

Then, we face a correspondence problem:  for each point p_i on the first shape, we want to find the “best” matching point q_i 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 [1], as a rich local descriptor. The idea is the following :


Given a point  p_i 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  p_i on the shape, the shape context of  p_i is defined by the histogram  h_i  (see figure 4):



Histogram in the log-polar space.
histo - copie
Alternative representation of the same histogram.




Then, we draw a bipartite graph, with nodes  the sampled points of the first and second shape. Then,  every points p_i and q_i are linked by an edge with weight C_{ij}  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).






with the constraint that the matching be one-to-one,  \pi is a permutation on the neighbors of p_i. Applied to the case of the two “o”s we obtain the best matching represented in figure 6.

untitled - copie
Figure 6: Best bipartite graph matching

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).


SIMEONI Matthieu

