Matching Attributed Graphs: 2nd-Order Probabilities for Pruning the Search Tree

descriptionPublicationkeyboard_double_arrow_right Part of book or chapter of book , Conference object , Article 01 Jan 2005 Spain Publisher:Springer Berlin Heidelberg

Authors: Francesc Serratosa; Alberto Sanfeliu;

doi: 10.1007/11492542_17

handle: 10261/30413

Matching Attributed Graphs: 2nd-Order Probabilities for Pruning the Search Tree

- Summary
- Subjects
- Metrics

Abstract

A branch-and-bound algorithm for matching Attributed Graphs (AGs) with Second-Order Random Graphs (SORGs) is presented. We show that the search space explored by this algorithm is drastically reduced by using the information of the 2nd-order joint probabilities of vertices of the SORGs. A SORG is a model graph, described elsewhere, that contains 1st and 2nd-order order probabilities of attribute relations between elements for representing a set of AGs compactly. In this work, we have applied SORGs and the reported algorithm to the recognition of real-life objects on images and the results show that the use of 2nd-order relations between vertices is not only useful to decrease the run time but also to increase the correct classification ratio.

Iberian Conference on Pattern Recognition and Image Analysis (IbPRIA), 2005, Estoril (Portugal)

Peer Reviewed

Country

Spain

Related Organizations

Spanish National Research Council
Spain
Institute of Robotics and Industrial Informatics
Spain
Universitat Politècnica de Catalunya
Spain
Universitat Rovira i Virgili
Spain

Keywords

Pattern recognition, Pattern recognition systems

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	0
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average