Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Wilson, Richard Charles; Hancock, Edwin R; Pekalska, Elzbieta; Duin, Robert P. W.
Languages: English
Types: Article

Classified by OpenAIRE into

arxiv: Mathematics::Differential Geometry
Many computer vision and pattern recognition problems may be posed as the analysis of a set of {\bf dissimilarities} between objects. For many types of data, these dissimilarities are not Euclidean (i.e. they do not represent the distances between points in a Euclidean space), and therefore cannot be isometrically embedded in a Euclidean space. Examples include shape-dissimilarities, graph distances and mesh geodesic distances. In this paper, we provide a means of embedding such non-Euclidean data onto surfaces of constant curvature. We aim to embed the data on a space whose radius of curvature is determined by the dissimilarity data. The space can be either of positive curvature (spherical) or of negative curvature (hyperbolic). We give an efficient method for solving the spherical and hyperbolic embedding problems on symmetric dissimilarity data. Our approach gives the radius of curvature and a method for approximating the objects as points on a hyperspherical manifold without optimisation. For objects which do not reside exactly on the manifold, we develop a optimisation-based procedure for approximate embedding on a hyperspherical manifold. We use the exponential map between the manifold and its local tangent space to solve the optimisation problem locally in the Euclidean tangent space. This process is efficient enough to allow us to embed datasets of several thousand objects. We apply our method to a variety of data including time warping functions, shape similarities, graph similarity and gesture similarity data. In each case the embedding maintains the local structure of the data while placing the points in a metric space.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] G. Andreu, A. Crespo, and J.M. Valiente. Selecting the toroidal selforganizing feature maps (tsofm) best organized to object recognition. In ICNN'97, pages 1341-1346, 1997.
    • [2] M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373- 1396, 2003.
    • [3] M. Brand. Charting a manifold. In Advances in Neural Information Processing Systems 15: Proceedings of the 2003 Conference (NIPS), pages 961-968. MIT Press., 2003.
    • [4] A.M. Bronstein, M.M. Bronstein, and R. Kimmel. Expression-invariant face recognition via spherical embedding. In Image Processing, 2005. ICIP 2005. IEEE International Conference on, volume 3, pages III756-9, 2005.
    • [5] H. Bunke and U. Buhler. Applications of approximate string matching to 2d shape recognition. Pattern Recognition, 26:1797-1812, 1993.
    • [6] M. A. A. Cox and T. F. Cox. Multidimensional scaling. In Handbook of Data Visualization, pages 315-347. Springer Handbooks of Computational Statistics, 2008.
    • [7] T. F. Cox and M. A. A. Cox. Multidimensional scaling on a sphere. Communications in Statistics - Theory and Methods, 20(9):2943-2953, 1991.
    • [8] M. Kitsak A. Vahdat M. Boguna D. Krioukov, F. Papadopoulos. Hyperbolic geometry of complex networks. Physical Review E, 82:036106, 2010.
    • [9] J. De Leeuw. Applications of convex analysis to multidimensional scaling. In J. R. Barra, F. Brodeau, G. Romier, and B. van Cutsem, editors, Recent Developments in Statistics, pages 133-145, 1977.
    • [10] J. De Leeuw and W. J. Heiser. Multidimensional scaling with restrictions on the configuration. In P. R. Krishnaiah, editor, Multivariate Analysis, pages 501-522, 1980.
    • [11] R. P.W. Duin and E. Pe¬łkalska. Datasets and tools for dissimilarity analysis in pattern recognition. Technical report, SIMBAD Deliverable 3.3, http://www.simbad-fp7.eu/images/D3.3 Datasets and tools for dissimilarity analysis in pattern recognition.pdf, 2009.
    • [12] A. Elad, Y. Keller, and R. Kimmel. Texture mapping via spherical multidimensional scaling. In Scale-Space 2005, volume 3459 of LNCS, pages 443-455, 2005.
    • [13] P. T. Fletcher, C. Lu, S. M. Pizer, and S. Joshi. Principal geodesic analysis for the study of nonlinear statistics of shape. IEEE Transactions on Medical Imaging, 23(8):995-1005, 2004.
    • [14] S. Gold and A. Rangarajan. A graduated assignment algorithm for graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18:377-388, 1996.
    • [15] L. Goldfarb. A unified approach to pattern recognition. Pattern Recognition, 17:575-582, 1984.
    • [16] L. Hubert, P. Arabie, and J. Meulman. Linear and circular unidimensional scaling for symmetric proximity matrices. British Journal of Mathematical & Statistical Psychology, 50:253-284, 1997.
    • [17] J.B. Kruskal. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika, 29:1-27, 1964.
    • [18] J. Lichtenauer, E. A. Hendriks, and M. J. T. Reinders. Sign language recognition by combining statistical DTW and independent classfication. IEEE Transactions on Pattern Analysis and Machine Intelligence, 30:2040-2046, 2008.
    • [19] H. Lindman and T. Caelli. Constant curvature Riemannian scaling. Journal of Mathematical Psychology, 17:89-109, 1978.
    • [20] J. S. B. Mitchell, D. M. Mount, and C. H. Papadimitriou. The discrete geodesic problem. SIAM Journal of Computing, 16:647-668, 1987.
    • [21] Elzbieta Pekalska and Robert P. W. Duin. The dissimilarity representation for pattern recognition. World Scientific, 2005.
    • [22] Elzbieta Pekalska, Artsiom Harol, Robert P. W. Duin, Barbara Spillmann, and Horst Bunke. Non-Euclidean or non-metric measures can be informative. In SSPR/SPR, pages 871-880, 2006.
    • [23] X. Pennec, P. Fillard, and N. Ayache. A riemannian framework for tensor computing. International Journal of Computer Vision, 66(1):41- 66, 2006.
    • [24] A. Robles-Kelly and E. R. Hancock. A Riemannian approach to graph embedding. Pattern Recognition, 40:1042-1056, 2007.
    • [25] S. Roweis and L. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323-2326, 2000.
    • [26] J. Scannell, C. Blakemore, and M. Young. Analysis of connectivity in the cat cerebral cortex. Journal of Neuroscience, 15:1463-1483, 1995.
    • [27] I.J. Schoenberg. On certain metric spaces arising from Euclidean spaces by a change of metric and their imbedding in hilbert space. Annals of Mathematics, 38:787-797, 1937.
    • [28] Y. Shavitt and T. Tankel. Hyperbolic embedding of internet graph for distance estimation and overlay construction. IEEE/ACM Transactions on Networking, 16:25-36, 2008.
    • [29] R. N. Shepard. Representation of structure in similarity data: Problems and prospects. Pyschometrika, 39:37300421, 1974.
    • [30] A. Srivastava, I. Jermyn, and S. Joshi. Riemannian analysis of probability density functions with applications in vision. In Computer Vision and Pattern Recognition, 2007. CVPR '07. IEEE Conference on, pages 1 -8, june 2007.
    • [31] J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319- 2323, 2000.
    • [32] 1958. Torgerson, W.S. Theory and methods of scaling. Wiley, New York, 1958.
    • [33] A. Veeraraghavan, A. Srivastava, A.K. Roy-Chowdhury, and R. Chellappa. Rate-invariant recognition of humans and their activities. IEEE Transactions on Image Processing, 18(6):1326 -1339, june 2009.
    • [34] B. Xiao and E. R. Hancock. Geometric characterisation of graphs. ICIAP 2005, LNCS 3617:471-478, 2005.
    • [35] B. Xiao and E. R. Hancock. Geometric characterisation of graphs. In ICIAP 2005, LNCS 3617, pages 471-478, 2005.
  • No related research data.
  • No similar publications.

Share - Bookmark

Funded by projects


Cite this article