Shape context

The approach 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 or inflection points. It is preferable to sample the shape with roughly uniform spacing, though it is not critical.[2]

This step is described in detail in the Theory section.

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 χ² test statistic as the "shape context cost" of matching the two points:

${\displaystyle 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.[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):

${\displaystyle C_{A}={\frac {1}{2}}{\begin{Vmatrix}{\dbinom {\cos(\theta _{1})}{\sin(\theta _{1})}}-{\dbinom {\cos(\theta _{2})}{\sin(\theta _{2})}}\end{Vmatrix}}}$

This is half the length of the chord in unit circle between the unit vectors with angles ${\displaystyle \theta _{1}}$ and ${\displaystyle \theta _{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:

${\displaystyle C=(1-\beta )C_{S}+\beta 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.

Results of matching

Now, a one-to-one matching ${\displaystyle \pi (i)}$ that matches each point p_i on shape 1 and q_j on shape 2 that minimizes the total cost of matching,

${\displaystyle H(\pi )=\sum _{i}C\left(p_{i},q_{\pi (i)}\right)}$

is needed. This can be done in ${\displaystyle O(N^{3})}$ time using the Hungarian method, although there are more efficient algorithms.[6] 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.

Given the set of correspondences between a finite set of points on the two shapes, a transformation ${\displaystyle T:\mathbb {R} ^{2}\to \mathbb {R} ^{2}}$ can be estimated to map any point from one shape to the other. There are several choices for this transformation, described below.

The affine model is a standard choice: ${\displaystyle T(p)=Ap+o\!}$. The least squares solution for the matrix ${\displaystyle A}$ and the translational offset vector o is obtained by:

${\displaystyle o={\frac {1}{n}}\sum _{i=1}^{n}\left(p_{i}-q_{\pi (i)}\right),A=(Q^{+}P)^{t}}$

Where ${\displaystyle P={\begin{pmatrix}1&p_{11}&p_{12}\\\vdots &\vdots &\vdots \\1&p_{n1}&p_{n2}\end{pmatrix}}}$ with a similar expression for ${\displaystyle Q\!}$. ${\displaystyle Q^{+}\!}$ is the pseudoinverse of ${\displaystyle Q\!}$.

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:

${\displaystyle T(x,y)=\left(f_{x}(x,y),f_{y}(x,y)\right)}$

where each of the ƒ_x and ƒ_y have the form:

${\displaystyle f(x,y)=a_{1}+a_{x}x+a_{y}y+\sum _{i=1}^{n}\omega _{i}U\left({\begin{Vmatrix}(x_{i},y_{i})-(x,y)\end{Vmatrix}}\right),}$

and the kernel function ${\displaystyle U(r)\!}$ is defined by ${\displaystyle U(r)=r^{2}\log r^{2}\!}$. The exact details of how to solve for the parameters can be found elsewhere[7][8] 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.

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 ${\displaystyle v_{i}}$ denote the target function values at corresponding locations ${\displaystyle p_{i}=(x_{i},y_{i})}$ (Note that for ${\displaystyle f_{x}}$, ${\displaystyle v_{i}}$ would ${\displaystyle x'}$ the x-coordinate of the point corresponding to ${\displaystyle p_{i}}$ and for ${\displaystyle f_{y}}$ it would be the y-coordinate, ${\displaystyle y'}$), relaxing the requirement amounts to minimizing

${\displaystyle H[f]=\sum _{i=1}^{n}(v_{i}-f(x_{i},y_{i}))^{2}+\lambda I_{f}}$

where ${\displaystyle I_{f}\!}$ is the bending energy and ${\displaystyle \lambda \!}$ is called the regularization parameter. This ƒ that minimizes H[ƒ] can be found in a fairly straightforward way.[9] If one uses normalize coordinates for ${\displaystyle (x_{i},y_{i}){\mbox{ and }}(x'_{i},y'_{i})}$, then scale invariance is kept. However, if one uses the original non-normalized coordinates, then the regularization parameter needs to be normalized.

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

Now, a shape distance between two shapes ${\displaystyle P\!}$ and ${\displaystyle 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:

${\displaystyle 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:

${\displaystyle D_{ac}(P,Q)={\frac {1}{n}}\sum _{i=1}^{n}\sum _{\Delta \in Z^{2}}G(\Delta )\left[I_{P}(p_{i}+\Delta )-I_{Q}(T(q_{\pi (i)})+\Delta )\right]^{2}}$

where ${\displaystyle I_{P}\!}$ and ${\displaystyle I_{Q}\!}$ are the gray-level images (${\displaystyle I_{Q}\!}$ is the image after warping) and ${\displaystyle G\!}$ is a Gaussian windowing function.

Transformation cost: The final cost ${\displaystyle 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.

The authors Serge Belongie and Jitendra Malik tested their approach on the MNIST database. 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.18%.[10]

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.[11] 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 number 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.[1][2][3][4] With these changes, they obtained a retrieval rate of 76.45%, which in 2002 was the best.

The next experiment performed on shape contexts involved the 20 common household objects in the 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 authors also developed an editing algorithm based on shape context similarity and k-medoid clustering that improved on their performance.[4]

Shape contexts were used to retrieve the closest matching trademarks from a database to a query trademark (useful in detecting trademark infringement). No visually similar trademark was missed by the algorithm (verified manually by the authors).[2]