Abstract
We address the problem of comparing attributed trees and propose a novel distance measure centered around the notion of a maximal similarity common subtree. The proposed measure is general and defined on trees endowed with either symbolic or continuous-valued attributes, and can be equally applied to ordered and unordered, rooted and unrooted trees. We prove that our measure satisfies the metric constraints and provide a polynomial-time algorithm to compute it. This is a remarkable and attractive property since the computation of traditional edit-distance-based metrics is NP-complete, except for ordered structures. We experimentally validate the usefulness of our metric on shape matching tasks, and compare it with edit-distance measures.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. Prentice-Hall, Upper Saddle River (1993)
Bunke, H., Shearer, K.: A graph distance metric based on the maximal common subgraph. Pattern Recognition Letters 19, 255–259 (1998)
Dickinson, S.J., Pentland, A.P., Rosenfeld, A.: 3-D shape recovery using distributed aspect matching. PAMI 14(2), 174–198 (1992)
Eshera, M.A., Fu, K.-S.: An image understanding system using attributed symbolic representation and in exact graph-matching. PAMI 8, 604–618 (1986)
Fernandez, M.L., Valiente, G.: A graph distacne metric combining maximum common subgraph and minimum common supergraph. Pattern Recognition Letters 22, 753–758 (2001)
Hidović, D., Pelillo, M.: Metrics for attributed graphs based on the maximal similarity common subgraph. Int. J. Pattern Recognition Artif. Intell. (2004) (in press)
Ioffe, S., Forsyth, D.A.: Human tracking with mixtures of trees. In: Proc. ICCV, vol. I, pp. 690–695 (2001)
Jain, A.K., Dubes, R.C.: Algorithms for Clustering Data. Prentice Hall, Englewood Cliffs (1988)
Matula, D.W.: An algorithm for subtree identification. SIAM Review 10, 273–274 (1968)
Pavan, M., Pelillo, M.: A new graph-theoretic approach to clustering and segmentation. In: Proc. CVPR, vol. I, pp. 145–152 (2003)
Pelillo, M., Sidiqi, K., Zucker, S.W.: Matching hierarchical structures using association graphs. PAMI 21(11), 1105–1120 (1999)
Peura, M.: Attribute trees in image analysis: Heuristic matching and learning techniques. In: Proc. Int. Conf. Image Anal. Processing, pp. 1160-1165 (1999)
Sebastian, T.B., Klein, P.N., Kimia, B.B.: Recognition of shpes by editing their shock graphs. PAMI (2004) (to appear)
Shi, J., Malik, J.: Normalized cuts and image segmentation. PAMI 22(8), 888–905 (2000)
Siddiqi, K., Shokoufandeh, A., Dickinson, S.J., Zucker, S.W.: Shock graphs and shape matching. Int. J. Computer Vision 35(1), 13–32 (1999)
Torsello, A., Hancock, E.R.: A skeletal measure of 2D shape similarity. In: Arcelli, C., Cordella, L.P., Sanniti di Baja, G. (eds.) IWVF 2001. LNCS, vol. 2059, pp. 260–271. Springer, Heidelberg (2001)
Torsello, A., Hancock, E.R.: Efficiently computing weighted tree edit-distance using relaxation labeling. In: Figueiredo, M., Zerubia, J., Jain, A.K. (eds.) EMMCVPR 2001. LNCS, vol. 2134, pp. 438–453. Springer, Heidelberg (2001)
Tsai, W.H., Fu, K.-S.: Error-correcting isomorphism of attributed relational graphs for pattern analysis. IEEE Trans Syst. Man Cybern. 9, 757–768 (1979)
Valiente, G.: An efficient bottom-up distance between trees. In: Proc. Int. Symp. String Processing Information Retrieval, pp. 212–219 (2001)
Wallis, W.D., Shoubridge, P., Kraetz, M., Ray, D.: Graph distances using graph union. Pattern Recognition Letters 22, 701–704 (2001)
Wang, J.T.-L., Zhang, K.: Finding similar consesnus between trees: An algorithm and a distance hierarchy. Pattern Recognition 34, 127–137 (2001)
Zhang, K.: A constrained edit-distance between unordered labeled trees. Algorithmica 15, 205–222 (1996)
Zhang, K., Shasha, D.: Simple fast algorithms for the editing distance between trees and related problems. SIAM J. Comput. 18, 1245–1262 (1989)
Zhang, K., Statman, R., Shasha, D.: On the editing distance between unordered labeled trees. Inform. Process. Letters 42, 133–139 (1992)
Zhang, K., Wang, J.T.L., Shasha, D.: On the editing distance between undirected acyclic graphs. Int. J. Found. Computer Sci. 7(1), 43–57 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Torsello, A., Hidović, D., Pelillo, M. (2004). A Polynomial-Time Metric for Attributed Trees. In: Pajdla, T., Matas, J. (eds) Computer Vision - ECCV 2004. ECCV 2004. Lecture Notes in Computer Science, vol 3024. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24673-2_34
Download citation
DOI: https://doi.org/10.1007/978-3-540-24673-2_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21981-1
Online ISBN: 978-3-540-24673-2
eBook Packages: Springer Book Archive