Abstract
This paper considers two major applications of shape matching algorithms: (a) query-by-example, i. e. retrieving the most similar shapes from a database and (b) finding clusters of shapes, each represented by a single prototype. Our approach goes beyond pairwise shape similarity analysis by considering the underlying structure of the shape manifold, which is estimated from the shape similarity scores between all the shapes within a database. We propose a modified mutual kNN graph as the underlying representation and demonstrate its performance for the task of shape retrieval. We further describe an efficient, unsupervised clustering method which uses the modified mutual kNN graph for initialization. Experimental evaluation proves the applicability of our method, e. g. by achieving the highest ever reported retrieval score of 93.40% on the well known MPEG-7 database.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Shotton, J., Blake, A., Cipolla, R.: Multiscale categorical object recognition using contour fragments. IEEE Trans. on Pattern Analysis and Machine Intelligence 30(7), 1270–1281 (2008)
Opelt, A., Pinz, A., Zisserman, A.: A boundary-fragment-model for object detection. In: Leonardis, A., Bischof, H., Pinz, A. (eds.) ECCV 2006. LNCS, vol. 3952, pp. 575–588. Springer, Heidelberg (2006)
Ferrari, V., Tuytelaars, T., Gool, L.V.: Object detection by contour segment networks. In: Leonardis, A., Bischof, H., Pinz, A. (eds.) ECCV 2006. LNCS, vol. 3953, pp. 14–28. Springer, Heidelberg (2006)
Biederman, I., Ju, G.: Surface vs. edge-based determinants of visual recognition. Cognitive Psychology 20, 38–64 (1988)
Gavrila, D.M.: A Bayesian, exemplar-based approach to hierarchical shape matching. IEEE Trans. on Pattern Analysis and Machine Intelligence 29, 1408–1421 (2007)
Weinland, D., Boyer, E.: Action recognition using exemplar-based embedding. In: Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), pp. 1–7 (2008)
Yang, X., Bai, X., Latecki, L.J., Tu, Z.: Improving shape retrieval by learning graph transduction. In: Forsyth, D., Torr, P., Zisserman, A. (eds.) ECCV 2008, Part IV. LNCS, vol. 5305, pp. 788–801. Springer, Heidelberg (2008)
Yang, X., Koknar-Tezel, S., Latecki, L.: Locally constrained diffusion process on locally densified distance spaces with applications to shape retrieval. In: Proc. IEEE Conf. on Computer Vision and Pattern Recognition, CVPR (2009)
Ling, H., Jacobs, D.: Shape classification using the inner-distance. IEEE Trans. on Pattern Analysis and Machine Intelligence 29(2), 286–299 (2007)
Schmidt, F.R., Farin, D., Cremers, D.: Fast matching of planar shapes in sub-cubic runtime. In: Proc. IEEE Intern. Conf. on Computer Vision, ICCV (2007)
Yankov, D., Keogh, E.: Manifold clustering of shapes. In: Proc. Intern. Conf. on Data Mining (ICDM), pp. 1167–1171 (2006)
McNeill, G., Vijayakumar, S.: Hierarchical procrustes matching for shape retrieval. In: Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), vol. 1, pp. 885–894 (2006)
Felzenszwalb, P.F., Schwartz, J.D.: Hierarchical matching of deformable shapes. In: Proc. IEEE Conf. on Computer Vision and Pattern Recognition, CVPR (2007)
Zelnik-Manor, L., Perona, P.: Self-tuning spectral clustering. In: Advances in Neural Information Processing Systems (NIPS), pp. 1601–1608. MIT Press, Cambridge (2004)
Frey, B.J., Dueck, D.: Clustering by passing messages between data points. Science 315, 972–976 (2007)
Felzenszwalb, P.F., Huttenlocher, D.P.: Efficient graph-based image segmentation. Intern. Journal of Computer Vision 59(2), 167–181 (2004)
Sebastian, T., Klein, P., Kimia, B.: Recognition of shapes by editing their shock graphs. IEEE Trans. on Pattern Analysis and Machine Intelligence 26(5), 550–571 (2004)
Mokhtarian, F., Abbasi, S., Kittler, J.: Efficient and robust retrieval by shape content through curvature scale space. In: Proc. of International Workshop on Image Databases and Multimedia Search, pp. 35–42 (1996)
Strehl, A., Ghosh, J.: Cluster ensembles – a knowledge reuse framework for combining multiple partitions. The Journal of Machine Learning Research 3, 583–617 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kontschieder, P., Donoser, M., Bischof, H. (2010). Beyond Pairwise Shape Similarity Analysis. In: Zha, H., Taniguchi, Ri., Maybank, S. (eds) Computer Vision – ACCV 2009. ACCV 2009. Lecture Notes in Computer Science, vol 5996. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12297-2_63
Download citation
DOI: https://doi.org/10.1007/978-3-642-12297-2_63
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12296-5
Online ISBN: 978-3-642-12297-2
eBook Packages: Computer ScienceComputer Science (R0)