Shape Matching and Object Recognition Using Shape Contexts

Title: Shape Matching and Object Recognition Using Shape Contexts
Author: Serge Belongie, Jitendra Malik, Jan Puzincha
Publisher: IEEE
Month of Publication: April 2002

The paper proposes a stable and simple algorithm for finding corresponding between shapes. They introduce a shape descriptor, shape context, and maximize the similarity in the bipartite graph. The demonstration of 2D objects, e.g., handwritten digits, silhouettes, and trademarks, and 3D objects from Columbia COIL data set shows the improved performance.

First, a rich local descriptor, shape context, is proposed in order to match easier. It considers the set of vectors originating from a point to all other sample points on a shape. For a point on the shape, compute a coarse histogram of the relative coordinates of the remaining points according to the bins in log-polar space, making nearer points have more weighting. Use chi-square test statistic to be the cost C and identify the similarity. Second, when minimizing the cost of bipartite graph matching, they consider the scale invariance by normalizing all radial distance and rotation invariance by turning relative frames with the tangent angle. Moreover, one can add “dummy” nodes to get robust handling of outliers. Third, in the modeling transformation, they use the thin plate spline (TPS) model which includes the affine model, it is possible to estimate transformations in few iterations. Finally, estimate shape distances as the weighted sum of three terms: shape context distance, image appearance distance, and bending energy. And then apply the prototype-based approach. That is, use a variant of K-means, K-medoids, to select a ideal example for each category, and classify the query shape based on the minimal cost.

In conclusion, it is able to retrieval the objects which have similar shapes with the query, and the performance is really improved.

In my opinion, it is thoughtful that they consider several key points and construct the distance weighting function based on three term. However, it is possible that more parameters may cause biased query results. Maybe they should show individual statistic for each terms and convey us that the weighting function is really believable. Besides, I think that the modified K-means may be helpful in some cases. The outlier removal and warped transformation seems useful to remove noises according to the figure 4.

Nonlinear Dimensionality Reduction by Locally Linear Embedding

Title : Nonlinear Dimensionality Reduction by Locally Linear Embedding
Author : S. T. Roweis and L. K. Saul
Year of Publication: 2000

The paper introduces an unsupervised learning algorithm, locally linear embedding(LLE). The following is the steps of locally linear embedding.

1.Find the neighbors of each point which close to a locally linear patch the manifold. (kNN in this paper)
2.Reconstruct each data point from its neighbors with the constrained least-square error.
3.Compute the low-dimensional embedding vector by minimizing the embedded cost function.

In summary, unlike PCA or MDS, LLE succeeds in mapping nearby data points in the low dimensional system. LLE avoids solving large dynamic programming problems and accumulate sparse matrices; consequently, LLE saves a lot of time and space in the computation.

In my opinion, LLE is easy to figure out because of three simple steps. However, the first time I read the paper, I have no idea about what LLE is. That is, the paper seems to organize many research results together and hide the details, so it may expect the readers to have relative background knowledge or survey the references when reading.

Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection

Title: Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection
Author: Peter N. Belhumeur, Joao P. Hespanha, and David J. kriegman
Year of Publication: 1997
Publisher: IEEE

In this paper, the authors proposed the method, Fisherfaces, for face recognition. Fisherfaces is insensitive to large variations in illumination and facial expressions. Compared with eigenfaces which uses PCA for dimensionality reduction and maximize the total scatter across all classes, fisherfaces maximize the ratio of between-class scatter to that of the within-in class scatter. They compare four methods for recognition under variation in lighting and facial expression: correlation, a variant of the linear subspace method, the Eigenface method, and the Fisherface method.
(1) Correlation is the simplest method but need variant lighting training data and require large time complexity and storage.
(2) Eigenfaces apply PCA and reduces time complexity a lot. However, when it maximizes between-class scatter, it also maximizes with-in class scatter which is unwanted information for face recognition. It have been suggested that by discarding the three most significant principal components, the effects of variant illumination may be reduced, but it may also result in unexpected consequence.
(3) The linear subspace algorithm take the normal vector to the surface and the albedo of the surface into consideration. That is, the algorithm can easily recognize Lambertian surfaces and be insensitive to a wide range of lighting conditions. Nevertheless, it has to learn where the good regions for recognition are, and its computation and storage are higher than the Eigenfaces method.
(4) Fisherfaces use the Fisher’s Linear Discriminant method which is class specific. The approach maximize the ratio of the between-class scatter and the within-class scatter, that is, achieve greater between-class scatter and decrease within-class scatter.

In conclusion, it shows that fisherfaces perform better than other three methods in the several experiments, variant lighting, facial expression, and glasses recognition. It is based on more reasonable dimensionality reduction, and it requires lower computation by modifying the original equation with PCA. Also, it doesn’t need storage as much as the Linear Subspace method. What it can be improved is how to deal with extreme lighting condition and , maybe, side face recognition.