Deformable 2D shape matching based on shape contexts and dynamic programming

Brief description

We have proposed a method for matching closed, 2D shapes (2D object silhouettes) that are represented as an ordered collection of shape contexts. Shape context is a shape descriptor that is used for the purpose of robust local shape description. It is robust to affine transformations and other types of deformation and can be computed invariantly of rotations. Matching is performed using a recent method that computes the optimal alignment of two cyclic strings in sub-cubic runtime. Thus, the proposed method is suitable for efficient, near real-time matching of closed shapes. The method is qualitatively and quantitatively evaluated using several datasets. An application of the method for joint detection in human figures is also presented.

Sample results

Extensive retrieval results exist for the MPEG-7 dataset. Each row in this pdf depicts the retrieval results for the left-most shape. This shape is used as the query, and the following shapes in the row are shown in order of decreasing similarity (increasing distance).


Download video: Per frame detection of the observed human figure (the actual input to the method is background subtraction)


Download video: similar experiment, with the addition of temporal continuity (tracking)


  • Iasonas Oikonomidis, Xenophon Zabulis.
  • This work was partially supported by the IST-FP7-IP-215821 project GRASP.

Relevant publications

  • Oikonomidis, A.A. Argyros, “Deformable 2D Shape Matching Based on Shape Contexts and Dynamic Programming”, in proceedings of the International Symposium on Visual Computing, 2009, Las Vegas, USA, Nov 30 - Dec 2, 2009

The electronic versions of the above publications can be downloaded from my publications page.