TY - JOUR

T1 - Matching with shape contexts

AU - Belongie, Serge

AU - Mori, Greg

AU - Malik, Jitendra

N1 - Funding Information: This research was supported by (ARO) DAAH04-96-1-0341, the Digital Library Grant IRI-9411334, an NSF Graduate Fellowship, and the German Research Foundation by DFG grant PU-165/1 to our collaborator J. Puzicha, now at Recommind, Inc. Parts of this work have appeared in [2?4, 31, 32]. We also thank H. Chui, A. Rangarajan and various members of the Berkeley computer vision group, particularly A. Berg, A. Efros, D. Forsyth, T. Leung, J. Shi and Y. Weiss, for useful discussions. Funding Information: This research was supported by (ARO) DAAH04-96-1-0341, the Digital Library Grant IRI-9411334, an NSF Graduate Fellowship, and the German Research Foundation by DFG grant PU-165/1 to our collaborator J. Puzicha, now at Recommind, Inc. Parts of this work have appeared in [2–4, 31, 32]. We also thank H. Chui, A. Rangarajan and various members of the Berkeley computer vision group, particularly A. Berg, A. Efros, D. Forsyth, T. Leung, J. Shi and Y. Weiss, for useful discussions. Publisher Copyright: © 2006, Birkhäuser Boston.

PY - 2006

Y1 - 2006

N2 - We present a novel approach to measuring similarity between shapes and exploit it for object recognition. In our framework, the measurement of similarity is preceded by (1) solving for correspondences between points on the two shapes, and (2) using the correspondences to estimate an aligning transform. In order to solve the correspondence problem, we attach a descriptor, the shape context, to each point. The shape context at a reference point captures the distribution of the remaining points relative to it, thus offering a globally discriminative characterization. Corresponding points on two similar shapes will have similar shape contexts, enabling us to solve for correspondences as an optimal assignment problem. Given the point correspondences, we estimate the transformation that best aligns the two shapes; regularized thin-plate splines provide a flexible class of transformation maps for this purpose. The dissimilarity between the two shapes is computed as a sum of matching errors between corresponding points, together with a term measuring the magnitude of the aligning transform. We treat recognition in a nearest neighbor classification framework as the problem of finding the stored prototype shape that is maximally similar to that in the image. We also demonstrate that shape contexts can be used to quickly prune a search for similar shapes. We present two algorithms for rapid shape retrieval: representative shape contexts, performing comparisons based on a small number of shape contexts, and shapemes, using vector quantization in the space of shape contexts to obtain prototypical shape pieces. Results are presented for silhouettes, handwritten digits and visual CAPTCHAs.

AB - We present a novel approach to measuring similarity between shapes and exploit it for object recognition. In our framework, the measurement of similarity is preceded by (1) solving for correspondences between points on the two shapes, and (2) using the correspondences to estimate an aligning transform. In order to solve the correspondence problem, we attach a descriptor, the shape context, to each point. The shape context at a reference point captures the distribution of the remaining points relative to it, thus offering a globally discriminative characterization. Corresponding points on two similar shapes will have similar shape contexts, enabling us to solve for correspondences as an optimal assignment problem. Given the point correspondences, we estimate the transformation that best aligns the two shapes; regularized thin-plate splines provide a flexible class of transformation maps for this purpose. The dissimilarity between the two shapes is computed as a sum of matching errors between corresponding points, together with a term measuring the magnitude of the aligning transform. We treat recognition in a nearest neighbor classification framework as the problem of finding the stored prototype shape that is maximally similar to that in the image. We also demonstrate that shape contexts can be used to quickly prune a search for similar shapes. We present two algorithms for rapid shape retrieval: representative shape contexts, performing comparisons based on a small number of shape contexts, and shapemes, using vector quantization in the space of shape contexts to obtain prototypical shape pieces. Results are presented for silhouettes, handwritten digits and visual CAPTCHAs.

KW - object recognition

KW - shape correspondence

KW - Shape distance

KW - thin-plate spline (TPS)

UR - http://www.scopus.com/inward/record.url?scp=84920259734&partnerID=8YFLogxK

U2 - 10.1007/0-8176-4481-4_4

DO - 10.1007/0-8176-4481-4_4

M3 - Journal article

AN - SCOPUS:84920259734

SP - 81

EP - 105

JO - Modeling and Simulation in Science, Engineering and Technology

JF - Modeling and Simulation in Science, Engineering and Technology

SN - 2164-3679

IS - 9780817643768

ER -