- Shape context
**Shape Context**is the term given bySerge Belongie andJitendra Malik to the feature descriptor they first proposed in their paper "Matching with Shape Contexts" in2000 cite conference

author = S. Belongie and J. Malik

title = Matching with Shape Contexts

url = http://ieeexplore.ieee.org/iel5/6885/18538/00853834.pdf

booktitle = IEEE Workshop on Contentbased Access of Image and Video Libraries (CBAIVL-2000)

year = 2000] . Shape context can be used inobject recognition .**Theory**The shape context is intended to be a way of describing shapes that allows for measuring shape similarity and the recovering of point correspondences . The basic idea is to pick $n$ points on the contours of a shape. For each point $p\_i$ on the shape, consider the $n\; -\; 1$ vectors obtained by connecting $p\_i$ to all other points. The set of all these vectors is a rich description of the shape localized at that point but is far too detailed. The key idea is that the distribution over relative positions is a robust, compact, and highly discriminative descriptor. So, for the point $p\_i$, the coarse histogram of the relative coordinates of the remaining $n\; -\; 1$ points,

$h\_i(k)\; =\; \#\{q\; e\; p\_i\; :\; (q\; -\; p\_i)\; in\; mbox\{bin\}(k)\}$

is defined to be the shape context of $p\_i$. The bins are normally taken to be uniform in log-polar space. The fact that the shape context is a rich and discriminative descriptor can be seen in the figure below, in which the shape contexts of two different versions of the letter "A" are shown.

(a) and (b) are the sampled edge points of the two shapes. (c) is the diagram of the log-polar bins used to compute the shape context. (d) is the shape context for the circle, (e) is that for the diamond, and (f) is that for the triangle. As can be seen, since (d) and (e) are the shape contexts for two closely related points, they are quite similar, while the shape context in (f) is very different.

Now in order for a feature descriptor to be useful, it needs to have certain invariances. In particular it needs to be invariant to translation, scale, small perturbations, and depending on application rotation. Translational invariance come naturally to shape context. Scale invariance is obtained by normalizing all radial distances by the mean distance $alpha$ between all the point pairs in the shape cite journal

author = S. Belongie, J. Malik, and J. Puzicha

title = Shape Matching and Object Recognition Using Shape Contexts

url = http://www.eecs.berkeley.edu/Research/Projects/CS/vision/shape/belongie-pami02.pdf

journal = IEEE Transactions on Pattern Analysis and Machine Intelligence

volume = 24

issue = 24

date = April 2002

pages = 509–521

doi = 10.1109/34.993558] cite conference

author = S. Belongie, J. Malik, and J. Puzicha

title = Matching Shapes

url = http://www.eecs.berkeley.edu/Research/Projects/CS/vision/shape/belongie-iccv01.pdf

booktitle = Eighth IEEE International Conference on Computer Vision (July 2001)

date=July 2001] although the median distance can also be usedcite conference

author = S. Belongie, J. Malik, and J. Puzicha

title = Shape Context: A new descriptor for shape matching and object recognition

booktitle = NIPS 2000

year = 2000] . Shape contexts are empirically demonstrated to be robust to deformations, noise, and outliers using synthetic point set matching experiments [*cite conference*] .

author = H. Chui and A. Rangarajan

title = A new algorithm for non-rigid point matching

booktitle = CVPR

volume = 2

pages = 44-51

date=June 2000One can provide complete rotation invariance in shape contexts. One way is to measure angles at each point relative to the direction of the tangent at that point (since the points are chosen on edges). This results in a completely rotationally invariant descriptor. But of course this is not always desired since some local features lose their discriminative power if not measured relative to the same frame. Many applications in fact forbid rotation invariance e.g. distinguishing a "6" from a "9".

**Use in Shape Matching**A complete system that uses shape contexts for shape matching consists of the following steps (which will be covered in more detail in the

#Details of Implementation section):# Finding a list of points on shape edges

# Computing the shape context of each point found in step 1

# Calculating the cost of matching each point in the first shape to each point of the second shape

# Find the one-to-one matching that minimizes the total cost of matching. This is an instance of theassignment problem .

# Find a transformation (e.g. Affine,Thin plate spline , etc) that maps one shape to the other (essentially aligning the two shapes)

# Calculate the "shape distance" between the two shapes as a weighted sum of the shape context distance, image appearance distance, and bending energy (a measure of how much transformation is required to bring the two shapes into alignment)Now that the shape distance has been calculated, the distance can be used in a nearest-neighbor classifier for a number of different object recognition problems.

**Details of Implementation****tep 1: Finding a list of points on shape edges**The approach essentially assumes that the shape of an object is essentially captured by a finite subset of the points on the internal or external contours on the object. These can be simply obtained using the

Canny edge detector and picking a random set of points from the edges. Note that these points need not and in general do not correspond to key-points such as maxima of curvature orinflection point s. It is preferable to sample the shape with roughly uniform spacing, though it is not critical .**tep 2: Computing the shape context**This step is described in detail in the Theory section.

**tep 3: Computing the cost matrix**Consider two points $p$ and $q$ that have normalized K-bin histograms (i.e. shape contexts) $g(k)$ and $h(k)$. As shape contexts are distributions represented as histograms, it is natural to use the $chi^2$ test statistic as the "shape context cost" of matching the two points:

$C\_S\; =\; frac\{1\}\{2\}sum\_\{k=1\}^K\; frac\{\; [g(k)\; -\; h(k)]\; ^2\}\{g(k)\; +\; h(k)\}$

The values of this range from 0 to 1 .In addition to the shape context cost, an extra cost based on the appearance can be added. For instance, it could be a measure of tangent angle dissimilarity (particularly useful in digit recognition):

$C\_A\; =\; frac\{1\}\{2\}egin\{Vmatrix\}\; dbinom\{cos(\; heta\_1)\}\{sin(\; heta\_1)\}\; -\; dbinom\{cos(\; heta\_2)\}\{sin(\; heta\_2)\}end\{Vmatrix\}$

This is half the length of the chord in unit circle between the unit vectors with angles $heta\_1$ and $heta\_2$. Its values also range from 0 to 1. Now the total cost of matching the two points could be a weighted-sum of the two costs:

$C\; =\; (1\; -\; eta)C\_S\; +\; eta\; C\_A!,$

Now for each point $p\_i$ on the first shape and a point $q\_j$ on the second shape, calculate the cost as described and call it $C\_\{i,j\}$. This is the cost matrix.

**tep 4: Finding the matching that minimizes total cost**Now, a one-to-one matching $pi\; (i)!$ that matches each point $p\_i$ on shape 1 and $q\_j$ on shape 2 that minimizes the total cost of matching,

$H(pi)\; =\; sum\_i\; Cleft\; (p\_i,q\_\{pi\; (i)\}\; ight\; )$

is needed. This can be done in $O(N^3)$ time using the

Hungarian method , although there are more efficient algorithms [*cite journal*] .To have robust handling of outliers, one can add "dummy" nodes that have a constant but reasonably large cost of matching to the cost matrix. This would cause the matching algorithm to match outliers to a "dummy" if there is no real match.

author = R. Jonker and A. Volgenant

title = A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems

journal = Computing

volume = 38

pages = 325–340

year = 1987

doi = 10.1007/BF02278710**tep 5: Modeling Transformation**Given the set of correspondences between a finite set of points on the two shapes, a transformation $T\; :\; Bbb\{R\}^2\; o\; Bbb\{R\}^2$ can be estimated to map any point from one shape to the other. There are several choices for this transformation, described below.

**Affine**The affine model is a standard choice: $T(p)\; =\; Ap\; +\; o!$. The

least squares solution for the matrix $A$ and the translational offset vector $o$ is obtained by:$o\; =\; frac\{1\}\{n\}sum\_\{i=1\}^n\; left\; (p\_i\; -\; q\_\{pi(i)\}\; ight\; ),\; A\; =\; (Q^+\; P)^t$

Where $P\; =\; egin\{pmatrix\}\; 1\; p\_\{11\}\; p\_\{12\}\; \backslash \; vdots\; vdots\; vdots\; \backslash \; 1\; p\_\{n1\}\; p\_\{n2\}end\{pmatrix\}$ with a similar expression for $Q!$. $Q^+!$ is the pseudoinverse of $Q!$.

**Thin Plate Spline**The thin plate spline (TPS) model is the most widely used model for transformations when working with shape contexts. A 2D transformation can be separated into two TPS function to model a coordinate transform:$T(x,y)\; =\; left\; (f\_x(x,y),f\_y(x,y)\; ight\; )$where each of the $f\_x!$ and $f\_y!$ have the form:$f(x,y)\; =\; a\_1\; +\; a\_xx\; +\; a\_yy\; +\; sum\_\{i=1\}^nomega\_iUleft\; (egin\{Vmatrix\}(x\_i,y\_i)\; -\; (x,y)\; end\{Vmatrix\}\; ight\; ),$

and the kernel function $U(r)!$ is defined by $U(r)\; =\; r^2log\; r^2!$. The exact details of how to solve for the parameters can be found elsewhere [

*cite conference*] [

author = M.J.D. Powell

title = A Thin Plate Spline Method for Mapping Curves into Curves in Two Dimensions

booktitle = Computational Techniques and Applications (CTAC '95)

year = 1995*cite journal*] but it essentially involves solving a linear system of equations. The bending energy (a measure of how much transformation is needed to align the points) will also be easily obtained.

author = J. Duchon

title = Splines Minimizing Rotation-Invariant Semi-Norms in Sobolev Spaces

journal = Constructive Theory of Functions of Several Variables

pages = 85–100**Regularized TPS**The TPS formulation above has exact matching requirement for the pairs of points on the two shapes. For noisy data, it is best to relax this exact requirement. If we let $v\_i$ denote the target function values at corresponding locations $p\_i\; =\; (x\_i,y\_i)$ (Note that for $f\_x$, $v\_i$ would $x\text{'}$ the x-coordinate of the point corresponding to $p\_i$ and for $f\_y$ it would be the y-coordinate, $y\text{'}$), relaxing the requirement amounts to minimizing$H\; [f]\; =\; sum\_\{i=1\}^n(v\_i\; -\; f(x\_i,y\_i))^2\; +\; lambda\; I\_f$ where $I\_f!$ is the bending energy and $lambda!$ is called the regularization parameter. This $f$ that minimizes $H\; [f]$ can be found in a fairly straightforward way [

*cite book*] . If one uses normalize coordinates for $(x\_i,y\_i)mbox\{\; and\; \}\; (x\text{'}\_i,y\text{'}\_i)$, then scale invariance is kept. However, if one uses the original non-normalized coordinates, then the regularization parameter needs to be normalized.

author = G. Wahba

title = Spline Models for Observational Data

publisher = Soc. Industrial and Applied Math

year = 1990Note that in many cases, regardless of the transformation used, the initial estimate of the correspondences contains some errors which could reduce the quality of the transformation. If we iterate the steps of finding correspondences and estimating transformations (i.e. repeating steps 2-5 with the newly transformed shape) we can overcome this problem. Typically, three iterations are all that is needed to obtain reasonable results.

**tep 6: Computing the shape distance**Now, a shape distance between two shapes $P!$ and $Q!$. This distance is going to be a weighted sum of three potential terms:

**Shape context distance**: this is the symmetric sum of shape context matching costs over best matching points: $D\_\{sc\}(P,Q)\; =\; frac\{1\}\{n\}sum\_\{p\; in\; P\}\; arg\; underset\{q\; in\; Q\}\{min\}\; C(p,T(q))\; +\; frac\{1\}\{m\}sum\_\{q\; in\; Q\}\; arg\; underset\{p\; in\; P\}\{min\}\; C(p,T(q))$Where $T(.)$ is the estimated TPS transform that maps the points in $Q$ to those in $P$.

**Appearance cost**: After establishing image correspondences and properly warping one image to match the other, one can define an appearance cost as the sum of squared brightness differences in Gaussian windows around corresponding image points:$D\_\{ac\}(P,Q)\; =\; frac\{1\}\{n\}sum\_\{i=1\}^nsum\_\{Delta\; in\; Z^2\}\; G(Delta)left\; [I\_P(p\_i\; +\; Delta)\; -\; I\_Q(T(q\_\{pi(i)\})\; +\; Delta)\; ight\; ]\; ^2$where $I\_P!$ and $I\_Q!$ are the gray-level images ($I\_Q!$ is the image after warping) and $G!$ is a Gaussian windowing function.

**Transformation cost**: The final cost $D\_\{be\}(P,Q)!,$ measures how much transformation is necessary to bring the two images into alignment. In the case of TPS, it is assigned to be the bending energy.Now that we have a way of calculating the distance between two shapes, we can use a nearest neighbor classifier (k-NN) with distance defined as the shape distance calculated here. The results of applying this to different situations is given in the following section.

**Results****Digit Recognition**The authors

Serge Belongie andJitendra Malik tested their approach on the [*http://yann.lecun.com/exdb/mnist/ MNIST dataset of handwritten digits*] . Currently, more than 50 algorithms have been tested on the database. The database has a training set of 60,000 examples, and a test set of 10,000 examples. The error rate for this approach was 0.63% using 20,000 training examples and 3-NN. At the time of publication, this error rate was the lowest. Currently, the lowest error rate is 0.39%.**ilhouette Similarity-based Retrieval**The authors experimented with the MPEG-7 shape silhouette database, performing Core Experiment CE-Shape-1 part B, which measures performance of similarity-based retrieval [

*cite journal*] . The database has 70 shape categories and 20 images per shape category. Performance of a retrieval scheme is tested by using each image as a query and counting the number of correct images in the top 40 matches. For this experiment, the authors increased the amount of points sampled from each shape. Also, since the shapes in the database sometimes were rotated or flipped, the authors took defined the distance between a reference shape and query shape to be minimum shape distance between the query shape and either the unchanged reference, the vertically flipped, or the reference horizontally flipped . With these changes, they obtained a retrieval rate of 76.45%, which by

author = S. Jeannin and M. Bober

title = Description of core experiments for MPEG-7 motion/shape. Technical Report ISO/IEC JTC 1/SC 29/WG 11 MPEG99/N2690, MPEG-7, Seoul

date=March 19992002 was the best.**3D Object Recognition**The next experiment performed on shape contexts involved the 20 common household objects in the [

*http://www1.cs.columbia.edu/CAVE/software/softlib/coil-20.php Columbia Object Image Library (COIL-20)*] . Each object has 72 views in the database. In the experiment, the method was trained on a number of equally spaced views for each object and the remaining views were used for testing. A 1-NN classifier was used. The results are shown to the right. The authors also developed an "editing" algorithm based on shape context similarity andk-medoid clustering that improved on their performance .**Trademark Retrieval**Shape contexts were used to retrieve the closest matching trademarks from a database to a query trademark (useful in detecting trademark infringement). The figure to the left depicts nearest neighbor retrieval results from a database of 300 trademarks. No visually similar trademark was missed by the algorithm (verified manually by the authors).

**External links*** [

*http://www.eecs.berkeley.edu/Research/Projects/CS/vision/shape/sc_digits.html Matching with Shape Contexts*]

* [*http://yann.lecun.com/exdb/mnist/ MNIST database of handwritten digits*]

* [*http://www1.cs.columbia.edu/CAVE/software/softlib/coil-20.php Columbia Object Image Library (COIL-20)*]

* [*http://www.vision.caltech.edu/Image_Datasets/Caltech101/ Caltech101 Database*]**References**

*Wikimedia Foundation.
2010.*