Partial Shape Matching

You can find more details on our team homepage at Virtual Habitat: http://vh.icg.tugraz.at

Shape matching is a well investigated problem in computer vision and has versatile applications as e. g. in object detection or image retrieval. The most important part of a shape matcher is the choice of the shape representation which has a significant effect on the subsequent matching step. Shapes have for example been represented by curves, medial axis, shock structures or sampled points.

One of the currently most popular methods for shape matching is the shape context proposed by Belongie et. al. The method uses randomly sampled points as shape representation and is based on a robust shape descriptor – the shape context – which allows to formulate the matching step as point correspondence problem. The shape context also constitutes the basis for different state-of-the-art extensions, e.g. using the inner distance instead of the Euclidean in the descriptor. The shape context does not exploit any ordering constraint on neighboring points. We propose a novel partial shape matching framework which also uses sampled boundary points as shape representation. We focus on the problem of matching outer contours (silhouettes) which allows to order the sampled points.

By analyzing a novel chord angle based descriptor and finding the correspondences in an integral image based order preserving assignment problem, we are able to provide godd partial matching results within milliseconds. Evaluation on the well-known MPEG-7 data-set provides a score of approximately 84% (ACCV 2009:1).

We further proposed a method for improving shape retrieval and clustering results by going beyond the pairwise shape similarity analysis. We exploit distances between all shapes of a data set by building a modified mutual k-NN tree structure, which allows improvement of retrieval scores given only an affinity matrix between all the shapes. Using our graph we achieve a retrieval score of 93.40% on MPEG-7, which is one of the highest ever reported score on this well-known data set (ACCV 2009:2).

Finally, we applied the partial shape matching to detect object instances by comparison to a provided shape prototype. All partial matches are organized in a huge data structure and a Hough voting scheme hypothesizes object locations. We evaluated our method on the wll-known ETHZ recognition data-set obtaining results close to state-of-the-art (ECCV 2010:3).