Abraham Kandel, Horst Bunke, Mark Last (Eds.)
Applied Graph Theory in Computer Vision and Pattern Recognition
Studies in Computational Intelligence, Volume 52
Editor-in-chief
Prof. Janusz Kacprzyk
Systems Research Institute
Polish Academy of Sciences
ul. Newelska 6
01-447 Warsaw
Poland
E-mail:
kacprzyk@ibspan.waw.pl
Further volumes of this series
can be found on our homepage:
springer.com
Vol. 33. Martin Pelikan, Kumara Sastry, Erick
Cant´u-Paz (Eds.)
Scalable Optimization via Probabilistic
Modeling,
2006
ISBN 978-3-540-34953-2
Vol. 34. Ajith Abraham, Crina Grosan, Vitorino
Ramos (Eds.)
Swarm Intelligence in Data Mining,
2006
ISBN 978-3-540-34955-6
Vol. 35. Ke Chen, Lipo Wang (Eds.)
Trends in Neural Computation,
2007
ISBN 978-3-540-36121-3
Vol. 36. Ildar Batyrshin, Janusz Kacprzyk, Leonid
Sheremetor, Lotfi A. Zadeh (Eds.)
Preception-based Data Mining and Decision Making
in Economics and Finance,
2006
ISBN 978-3-540-36244-9
Vol. 37. Jie Lu, Da Ruan, Guangquan Zhang (Eds.)
E-Service Intelligence,
2007
ISBN 978-3-540-37015-4
Vol. 38. Art Lew, Holger Mauch
Dynamic Programming,
2007
ISBN 978-3-540-37013-0
Vol. 39. Gregory Levitin (Ed.)
Computational Intelligence in Reliability Engineering,
2007
ISBN 978-3-540-37367-4
Vol. 40. Gregory Levitin (Ed.)
Computational Intelligence in Reliability Engineering,
2007
ISBN 978-3-540-37371-1
Vol. 41. Mukesh Khare, S.M. Shiva Nagendra (Eds.)
Artificial Neural Networks in Vehicular Pollution
Modelling,
2007
ISBN 978-3-540-37417-6
Vol. 42. Bernd J. Kr
¨
amer, Wolfgang A. Halang (Eds.)
Contributions to Ubiquitous Computing,
2007
ISBN 978-3-540-44909-6
Vol. 43. Fabrice Guillet, Howard J. Hamilton (Eds.)
Quality Measures in Data Mining,
2007
ISBN 978-3-540-44911-9
Vol. 44. Nadia Nedjah, Luiza de Macedo
Mourelle, Mario Neto Borges,
Nival Nunes de Almeida (Eds.)
Intelligent Educational Machines,
2007
ISBN 978-3-540-44920-1
Vol. 45. Vladimir G. Ivancevic, Tijana T. Ivancevic
Neuro-Fuzzy Associative Machinery for Comprehensive
Brain and Cognition Modeling,
2007
ISBN 978-3-540-47463-0
Vol. 46. Valentina Zharkova, Lakhmi C. Jain
Artificial Intelligence in Recognition and Classification
of Astrophysical and Medical Images,
2007
ISBN 978-3-540-47511-8
Vol. 47. S. Sumathi, S. Esakkirajan
Fundamentals of Relational Database Management
Systems,
2007
ISBN 978-3-540-48397-7
Vol. 48. H. Yoshida (Ed.)
Advanced Computational Intelligence Paradigms
in Healthcare,
2007
ISBN 978-3-540-47523-1
Vol. 49. Keshav P. Dahal, Kay Chen Tan, Peter I. Cowling
(Eds.)
Evolutionary Scheduling,
2007
ISBN 978-3-540-48582-7
Vol. 50. Nadia Nedjah, Leandro dos Santos Coelho,
Luiza de Macedo Mourelle (Eds.)
Mobile Robots: The Evolutionary Approach,
2007
ISBN 978-3-540-49719-6
Vol. 51. Shengxiang Yang, Yew-Soon Ong, Yaochu Jin
(Eds.)
Evolutionary Computation in Dynamic and Uncertain
Environments,
2007
ISBN 978-3-540-49772-1
Vol. 52. Abraham Kandel, Horst Bunke, Mark Last (Eds.)
Applied Graph Theory in Computer Vision and Pattern
Recognition,
2007
ISBN 978-3-540-68019-2
Abraham Kandel
Horst Bunke
Mark Last
(Eds.)
Applied Graph Theory
in Computer Vision and
Pattern Recognition
With 85 Figures and 17 Tables
Prof. Abraham Kandel
National Institute for Applied
Computational Intelligence
Computer Science & Engineering Department
University of South Florida
4202 E. Fowler Ave.,
ENB 118
Tampa, FL 33620
USA
E-mail:
kandel@csee.usf.edu
Prof. Dr. Horst Bunke
Institute of Computer Science
and Applied Mathematics (IAM)
Neubr¨uckstrasse 10
CH-3012 Bern
Switzerland
E-mail:
bunke@iam.unibe.ch
Dr. Mark Last
Department of Information Systems Engineering
Ben-Gurion University of the Negev
Beer-Sheva 84105
Israel
E-mail:
mlast@bgu.ac.il
Library of Congress Control Number: 2006939143
ISSN print edition: 1860-949X
ISSN electronic edition: 1860-9503
ISBN-10 3-540-68019-5 Springer Berlin Heidelberg New York
ISBN-13 978-3-540-68019-2 Springer Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material
is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broad-
casting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of
this publication or parts thereof is permitted only under the provisions of the German Copyright Law
of September 9, 1965, in its current version, and permission for use must always be obtained from
Springer-Verlag. Violations are liable to prosecution under the German Copyright Law.
Springer is a part of Springer Science+Business Media
springer.com
c
° Springer-Verlag Berlin Heidelberg 2007
The use of general descriptive names, registered names, trademarks, etc. in this publication does not
imply, even in the absence of a specific statement, that such names are exempt from the relevant
protective laws and regulations and therefore free for general use.
Cover design: deblik, Berlin
Typesetting by the SPi using a Springer L
A
T
E
X macro package
Printed on acid-free paper SPIN: 11946359 89/SPi 5 4 3 2 1 0
Preface
Graph theory has strong historical roots in mathematics, especially in topology. Its
birth is usually associated with the “four-color problem” posed by Francis Guthrie
in 1852,
1
but its real origin probably goes back to the Seven Bridges of K
¨
onigsberg
problem proved by Leonhard Euler in 1736.
2
A computational solution to these two
completely different problems could be found after each problem was abstracted to
the level of a graph model while ignoring such irrelevant details as country shapes
or cross-river distances. In general, a graph is a nonempty set of points (vertices)
and the most basic information preserved by any graph structure refers to adjacency
relationships (edges) between some pairs of points. In the simplest graphs, edges
do not have to hold any attributes, except their endpoints, but in more sophisticated
graph structures, edges can be associated with a direction or assigned a label. Graph
vertices can be labeled as well. A graph can be represented graphically as a drawing
(vertex = dot, edge = arc), but, as long as every pair of adjacent points stays connected
by the same edge, the graph vertices can be moved around on a drawing without
changing the underlying graph structure.
The expressive power of the graph models placing a special emphasis on con-
nectivity between objects has made them the models of choice in chemistry, physics,
biology, and other fields. Their increasing popularity in the areas of computer vision
and pattern recognition can be easily explained by the graphs’ ability to represent
complex visual patterns on one hand and to keep important structural information,
which may be relevant for pattern recognition tasks, on the other hand. This is in
sharp contrast with the more conventional feature vector or attribute-value represen-
tation of patterns where only unary measurements – the features, or equivalently,
the attribute values – are used for object representation. Graph representations also
have a number of invariance properties that may be very convenient for certain tasks.
1
Is it possible to color, using only four colors, any map of countries in such a way as to
prevent two bordering countries from having the same color?
2
Given the location of seven bridges in the city of K
¨
onigsberg, Prussia, Euler has proved that
it was not possible to walk with a route that crosses each bridge exactly once, and return to
the starting point.
