The Library

Unsupervised shape clustering using diffusion map

Tools

Rajpoot, Nasir M. (Nasir Mahmood) and Arif, Muhammad. (2008) Unsupervised shape clustering using diffusion map. Annals of the BMVA, Volume 2008 (Number 5).

Preview

PDF
WRAP_Rajpoot_2008-0005.pdf - Published Version - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (738Kb) | Preview

Abstract

The quotient space of all smooth and connected curves represented by a ﬁxed number of boundary points is a ﬁnite-dimensional Riemannian manifold, also known as a shape manifold. This makes the preservation of locality a critically important issue when reducing the dimensionality of shapes on the manifold. We present a completely unsupervised clustering algorithm employing diffusion maps for locality-preserving embedding of shapes onto a much lower-dimensional space. The algorithm ﬁrst obtains a non-linear low-dimensional embedding of shape context features of outer boundary contours of the shapes. Considering the embedded coordinates as a new minimalist representation of shapes, a clustering of shapes is obtained using a ﬁnite mixture model. The proposed clustering algorithm is computationally efﬁcient, as it relies on clustering in a very lowdimensional space, and produces much improved results (88.6% for a 7-class dataset) as compared to clustering with conventional linear projections.

Item Type:

Journal Article

Subjects:

Q Science > QA Mathematics
Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software

Divisions:

Faculty of Science > Computer Science

Library of Congress Subject Headings (LCSH):

Riemannian manifolds, Algorithms

Journal or Publication Title:

Annals of the BMVA

Publisher:

The British Machine Vision Association and Society for Pattern Recognition

Official Date:

2008

Dates:

Date	Date Type
2008	Published

Volume:

Volume 2008

Number:

Number 5

Number of Pages:

Status:

Peer Reviewed

Publication Status:

Published

Access rights to Published version:

Restricted or Subscription Access

Related URLs:

Open Access File

References:

M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation.
Neural computation, 15(6):1373–1396, 2003.
S. Belongie, J. Malik, and J. Puzicha. Shape matching and object recognition using shape contexts. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 24(4):509–522,
2002. URL http://ieeexplore.ieee.org/xpls/abs_all.jsp%3Farnumber%
3D993558.
Serge Belongie, J. Malik, and J. Puzicha. Matching shapes. In Proceedings International Conference
on Computer Vision, volume 1, pages 454–461, July 2001.
F.L. Bookstein. Size and shape spaces for landmark data in two dimensions. Statistical Science,
1(2):181–242, 1986. URL http://www.jstor.org/stable/2245441.
Anders Brun. Manifolds in Image Science and Visualization. PhD thesis, Linköping University,
Department of Biomedical Engineering, 2007.
R. Coifman and S. Lafon. Diffusion maps. Applied and Computational Harmonic Analysis,
Special Issue on Diffusion Maps and Wavelets, 21:5–30, July 2006.
T. Cootes, D. Cooper, C. Taylor, and J. Graham. Active shape models – their training and
applications. Computer Vision and Image Understanding, 61(1):38–59, 1995.
P. Etyngier, F. Segonne, and R. Keriven. Shape priors using manifold learning techniques. In
International Conference on Computer Vision (ICCV), pages 1–8, 2007.
C. Fraley and AE Raftery. How many clusters? Which clustering method? Answers via
model-based cluster analysis. The Computer Journal, 41(8):578–588, 1998.
D.G. Kendall. Shape manifolds, procrustean metrics,and complex projective spaces. Bulletin
of the London Mathematical Society, 16(2):81–121, 1984. URL http://intl-blms.
oxfordjournals.org/cgi/content/abstract/16/2/81.
E. Klassen, A. Srivastava, W. Mio, and S.H. Joshi. Analysis of planar shapes using geodesic
paths on shape spaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(3):
372–383, March 2004. URL http://ieeexplore.ieee.org/xpls/abs_all.jsp?
arnumber=1262333.
S. Lafon, Y. Keller, and RR Coifman. Data fusion and multicue data matching by diffusion
maps. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(11):1784–1797, 2006.
S. Lafon and A.B. Lee. Diffusion maps and coarse-graining: A unified framework for dimensionality
reduction, graph partitioning, and data set parmeterization. IEEE Transactions on
Pattern Analysis and Machine Intelligence, 28(9):1393–1403, September 2006.
M. Leventon, E. Grimson, and O. Faugeras. Statistical shape influence in geodesic active
contours. In Proceedings International Conference onComputer Vision and Pattern Recognition
(CVPR), pages 316–323, 2000.
W.L. Martinez and A.R. Martinez. Exploratory data analysis with MATLAB. Chapman &
Hall/CRC, 2004.
M. Meil˘a. Comparing clusterings£an information based distance. Journal of Multivariate
Analysis, 98(5):873–895, 2007.
P.W. Michor and D. Mumford. Riemannian geometries on spaces of plane curves. Arxiv
preprint math.DG/0312384, 2003. URL http://arxiv.org/abs/math.DG/0312384.
N. Rajpoot, M. Arif, and A. Bhalerao. Unsupervised learning of shape manifolds. In Proceedings
British Machine Vision Conference (BMVC’2007), pages 312–321, September 2007. URL
http://www.dcs.warwick.ac.uk/~nasir/papers/bmvc07a.pdf.
J.B. Tenenbaum, V. Silva, and J.C. Langford. A global geometric framework for nonlinear
dimensionality reduction. Science, 290(5500):2319–2323, 2000. URL http://www.
sciencemag.org/cgi/content/abstract/290/5500/2319.
L.J.P. van der Maaten, E.O. Postma, and H.J. van den Herik. Dimensionality reduction: A
comparative review. Submitted to Neurorecognition, 2008.
D. Yankov and E. Keogh. Manifold clustering of shapes. In Proceedings International Conference
on Data Mining (ICDM), pages 1167–1171, 2006. URL http://ieeexplore.ieee.
org/xpls/abs_all.jsp?arnumber=4053173.
D. Zhang and G. Lu. Review of shape representation and description techniques. Pattern
recognition, 37(1):1–19, 2004.