Lecture Notes in Computer Science 5534

Commenced Publication in 1973

Founding and Former Series Editors:
Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen

Editorial Board
David Hutchison
Lancaster University, UK
Takeo Kanade
Carnegie Mellon University, Pittsburgh, PA, USA
Josef Kittler
University of Surrey, Guildford, UK
Jon M. Kleinberg
Cornell University, Ithaca, NY, USA
Alfred Kobsa
University of California, Irvine, CA, USA
Friedemann Mattern
ETH Zurich, Switzerland
John C. Mitchell
Stanford University, CA, USA
Moni Naor
Weizmann Institute of Science, Rehovot, Israel
Oscar Nierstrasz
University of Bern, Switzerland
C. Pandu Rangan
Indian Institute of Technology, Madras, India
Bernhard Steffen
University of Dortmund, Germany
Madhu Sudan
Massachusetts Institute of Technology, MA, USA
Demetri Terzopoulos
University of California, Los Angeles, CA, USA
Doug Tygar
University of California, Berkeley, CA, USA
Gerhard Weikum
Max-Planck Institute of Computer Science, Saarbruecken, Germany
Andrea Torsello Francisco Escolano
Luc Brun (Eds.)

Graph-Based
Representations in
Pattern Recognition
7th IAPR-TC-15 International Workshop, GbRPR 2009
Venice, Italy, May 26-28, 2009
Proceedings

13
Volume Editors

Andrea Torsello
Department of Computer Science
“Ca’ Foscari” University of Venice
Venice, Italy
E-mail: torsello@[Link]
Francisco Escolano
Department of Computer Science
and Artificial Intelligence
Alicante University
Alicante, Spain
E-mail: sco@[Link]
Luc Brun
GreyC
University of Caen
Caen Cedex, France
E-mail: [Link]@[Link]

Library of Congress Control Number: Applied for

CR Subject Classification (1998): I.5, I.3, I.4, I.2.10, G.2.2

LNCS Sublibrary: SL 6 – Image Processing, Computer Vision, Pattern Recognition,

and Graphics

ISSN 0302-9743
ISBN-10 3-642-02123-9 Springer Berlin Heidelberg New York
ISBN-13 978-3-642-02123-7 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, re-use of illustrations, recitation, broadcasting,
reproduction on microfilms 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. Violations are liable
to prosecution under the German Copyright Law.
[Link]
© Springer-Verlag Berlin Heidelberg 2009
Printed in Germany
Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India
Printed on acid-free paper SPIN: 12682966 06/3180 543210
 Preface

This volume contains the papers presented at the 7th IAPR-TC-15 Workshop
on Graph-Based Representations in Pattern Recognition – GbR 2009. The work-
shop was held in Venice, Italy between May 26–28, 2009. The previous work-
shops in the series were held in Lyon, France (1997), Haindorf, Austria (1999),
Ischia, Italy (2001), York, UK (2003), Poitiers, France (2005), and Alicante,
Spain (2007).
The Technical Committee (TC15, [Link]
of the IAPR (International Association for Pattern Recognition) was founded in
order to federate and to encourage research work at the intersection of pattern
recognition and graph theory. Among its activities, the TC15 encourages the
organization of special graph sessions in many computer vision conferences and
organizes the biennial GbR Workshop.
The scientific focus of these workshops covers research in pattern recognition
and image analysis within the graph theory framework. This workshop series
traditionally provide a forum for presenting and discussing research results and
applications in the intersection of pattern recognition, image analysis and graph
theory.
The papers in the workshop cover the use of graphs at all levels of represen-
tation, from low-level image segmentation to high-level human behavior. There
are papers on formalizing the use of graphs for representing and recognizing data
ranging from visual shape to music, papers focusing on the development of new
and efficient approaches to matching graphs, on the use of graphs for super-
vised and unsupervised classification, on learning the structure of sets of graphs,
and on the use of graph pyramids and combinatorial maps to provide suitable
coarse-to-fine representations. Encouragingly, the workshop saw the convergence
of ideas from several fields, from spectral graph theory, to machine learning, to
graphics.
The papers presented in the proceedings have been reviewed by at least two
members of the Program Committee and each paper received on average of three
reviews, with more critical papers receiving as many as five reviews. We sincerely
thank all the members of the Program Committee and all the additional referees
for their effort and invaluable help. We received 47 papers from 18 countries and
5 continents. The Program Committee selected 18 of them for oral presentation
and 19 as posters. The resulting 37 papers revised by the authors are published
in this volume.

March 2009 Andrea Torsello

Francisco Escolano
Luc Brun
 Organization

General Chairs
Andrea Torsello Univesità Ca’ Foscari di Venezia, Italy
Francisco Escolano Universidad de Alicante, Spain
Luc Brun GREYC ENSICAEN, France

Program Committee
I. Bloch TELECOM ParisTech, France
H. Bunke University of Bern, Switzerland
S. Dickinson University of Toronto, Ontario, Canada
M. Figueiredo Instituto Superior Técnico, Portugal
E. R. Hancock University of York, UK
C. de la Higuera University of Saint-Etienne, France
J.-M. Jolion Universite de Lyon, France
W. G. Kropatsch Vienna University of Technology, Austria
M. Pelillo Univesità Ca’ Foscari di Venezia, Italy
A. Robles-Kelly National ICT Australia (NICTA), Australia
A. Shokoufandeh Drexel University, PA, USA
S. Todorovic Oregon State University, OR, USA
M. Vento Università di Salerno, Italy
R. Zabih Cornell University, NY, USA

Organizing Committee
S. Rota Bulò Univesità Ca’ Foscari di Venezia, Italy
A. Albarelli Univesità Ca’ Foscari di Venezia, Italy
E. Rodolà Univesità Ca’ Foscari di Venezia, Italy

Additional Referees
Andrea Albarelli Daniela Giorgi Emanuele Rodolà
Xiang Bai Michael Jamieson Samuel Rota Bulò
Sebastien Bougleux Jean-Christophe Janodet Émilie Samuel
Gustavo Carneiro Rolf Lakemper Cristian Sminchisescu
Fatih Demirci Miguel Angel Lozano
Aykut Erdem James Maclean
Sébastien Fourey Anand Rangarajan

Sponsoring Institutions
Dipartimento di Informatica
Università Ca’ Foscari di Venezia, Italy
 Table of Contents

Graph-Based Representation and Recognition

Matching Hierarchies of Deformable Shapes . . . . . . . . . . . . . . . . . . . . . . . . . 1
Nadia Payet and Sinisa Todorovic
Edition within a Graph Kernel Framework for Shape Recognition . . . . . . 11
François-Xavier Dupé and Luc Brun
Coarse-to-Fine Matching of Shapes Using Disconnected Skeletons by
Learning Class-Specific Boundary Deformations . . . . . . . . . . . . . . . . . . . . . . 21
Aykut Erdem and Sibel Tari
An Optimisation-Based Approach to Mesh Smoothing: Reformulation
and Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Yskandar Hamam and Michel Couprie
Graph-Based Representation of Symbolic Musical Data . . . . . . . . . . . . . . . 42
Bassam Mokbel, Alexander Hasenfuss, and Barbara Hammer
Graph-Based Analysis of Nasopharyngeal Carcinoma with Bayesian
Network Learning Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Alex Aussem, Sergio Rodrigues de Morais, Marilys Corbex, and
Joël Favrel
Computing and Visualizing a Graph-Based Decomposition for
Non-manifold Shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Leila De Floriani, Daniele Panozzo, and Annie Hui
A Graph Based Data Model for Graphics Interpretation . . . . . . . . . . . . . . 72
Endre Katona
Tracking Objects beyond Rigid Motion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Nicole Artner, Adrian Ion, and Walter G. Kropatsch
Graph-Based Registration of Partial Images of City Maps Using
Geometric Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
Steffen Wachenfeld, Klaus Broelemann, Xiaoyi Jiang, and
Antonio Krüger

Graph Matching
A Polynomial Algorithm for Submap Isomorphism: Application to
Searching Patterns in Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
Guillaume Damiand, Colin de la Higuera, Jean-Christophe Janodet,
Émilie Samuel, and Christine Solnon
VIII Table of Contents

A Recursive Embedding Approach to Median Graph Computation . . . . . 113

M. Ferrer, D. Karatzas, E. Valveny, and H. Bunke

Efficient Suboptimal Graph Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

Kaspar Riesen, Stefan Fankhauser, Horst Bunke, and
Peter Dickinson

Homeomorphic Alignment of Edge-Weighted Trees . . . . . . . . . . . . . . . . . . . 134

Benjamin Raynal, Michel Couprie, and Venceslas Biri

Inexact Matching of Large and Sparse Graphs Using Laplacian

Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
David Knossow, Avinash Sharma, Diana Mateus, and Radu Horaud

Graph Matching Based on Node Signatures . . . . . . . . . . . . . . . . . . . . . . . . . 154

Salim Jouili and Salvatore Tabbone

A Structural and Semantic Probabilistic Model for Matching and

Representing a Set of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
Albert Solé-Ribalta and Francesc Serratosa

Arc-Consistency Checking with Bilevel Constraints: An Optimization . . . 174

Aline Deruyver and Yann Hodé

Graph Clustering and Classification

Pairwise Similarity Propagation Based Graph Clustering for Scalable

Object Indexing and Retrieval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
Shengping Xia and Edwin R. Hancock

A Learning Algorithm for the Optimum-Path Forest Classifier . . . . . . . . . 195

João Paulo Papa and Alexandre Xavier Falcão

Improving Graph Classification by Isomap . . . . . . . . . . . . . . . . . . . . . . . . . . 205

Kaspar Riesen, Volkmar Frinken, and Horst Bunke

On Computing Canonical Subsets of Graph-Based Behavioral

Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
Walter C. Mankowski, Peter Bogunovich, Ali Shokoufandeh, and
Dario D. Salvucci

Object Detection by Keygraph Classification . . . . . . . . . . . . . . . . . . . . . . . . 223

Marcelo Hashimoto and Roberto M. Cesar Jr.

Graph Regularisation Using Gaussian Curvature . . . . . . . . . . . . . . . . . . . . . 233

Hewayda ElGhawalby and Edwin R. Hancock
 Table of Contents IX

Characteristic Polynomial Analysis on Matrix Representations of

Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
Peng Ren, Richard C. Wilson, and Edwin R. Hancock

Flow Complexity: Fast Polytopal Graph Complexity and 3D Object

Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
Francisco Escolano, Daniela Giorgi, Edwin R. Hancock,
Miguel A. Lozano, and Bianca Falcidieno

Pyramids, Combinatorial Maps, and Homologies

Irregular Graph Pyramids and Representative Cocycles of Cohomology

Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
Rocio Gonzalez-Diaz, Adrian Ion, Mabel Iglesias-Ham, and
Walter G. Kropatsch

Annotated Contraction Kernels for Interactive Image Segmentation . . . . 273

Hans Meine

3D Topological Map Extraction from Oriented Boundary Graph . . . . . . . 283

Fabien Baldacci, Achille Braquelaire, and Guillaume Damiand

An Irregular Pyramid for Multi-scale Analysis of Objects and Their

Parts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
Martin Drauschke

A First Step toward Combinatorial Pyramids in n-D Spaces . . . . . . . . . . . 304

Sébastien Fourey and Luc Brun

Cell AT-Models for Digital Volumes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314

Pedro Real and Helena Molina-Abril

From Random to Hierarchical Data through an Irregular Pyramidal

Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
Rimon Elias, Mohab Al Ashraf, and Omar Aly

Graph-Based Segmentation

Electric Field Theory Motivated Graph Construction for Optimal

Medical Image Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
Yin Yin, Qi Song, and Milan Sonka

Texture Segmentation by Contractive Decomposition and Planar

Grouping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
Anders Bjorholm Dahl, Peter Bogunovich, and Ali Shokoufandeh
X Table of Contents

Image Segmentation Using Graph Representations and Local

Appearance and Shape Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
Johannes Keustermans, Dieter Seghers, Wouter Mollemans,
Dirk Vandermeulen, and Paul Suetens

Comparison of Perceptual Grouping Criteria within an Integrated

Hierarchical Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
R. Marfil and A. Bandera

Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377

 Matching Hierarchies of Deformable Shapes

Nadia Payet and Sinisa Todorovic

Oregon State University, Corvallis, OR 97331, USA

payetn@[Link], sinisa@[Link]

Abstract. This paper presents an approach to matching parts of deformable

shapes. Multiscale salient parts of the two shapes are first identified. Then, these
parts are matched if their immediate properties are similar, the same holds recur-
sively for their subparts, and the same holds for their neighbor parts. The shapes
are represented by hierarchical attributed graphs whose node attributes encode the
photometric and geometric properties of corresponding parts, and edge attributes
capture the strength of neighbor and part-of interactions between the parts. Their
matching is formulated as finding the subgraph isomorphism that minimizes a
quadratic cost. The dimensionality of the matching space is dramatically reduced
by convexifying the cost. Experimental evaluation on the benchmark MPEG-7
and Brown datasets demonstrates that the proposed approach is robust.

1 Introduction
This paper is about shape matching by using: (1) a new hierarchical shape representa-
tion, and (2) a new quadratic-assignment objective function that is efficiently optimized
via convexification. Many psychophysical studies suggest that shape perception is the
major route for acquiring knowledge about the visual world [1]. However, while hu-
mans are very efficient in recognizing shapes, this proves a challenging task for com-
puter vision. This is mainly due to certain limitations in existing shape representations
and matching criteria used, which typically cannot adequately address matching of de-
formable shapes. Two perceptually similar deformable shapes may have certain parts
very different or even missing, whereas some other parts very similar. Therefore, ac-
counting for shape parts in matching is important. However, it is not always clear how to
define a shape part. The motivation behind the work described in this paper is to improve
robustness of shape matching by using a rich hierarchical shape representation that will
provide access to all shape parts existing at all scales, and by formulating a matching
criterion that will account for these shape parts and their hierarchical properties.
We address the following problem: Given two shapes find correspondences between
all their parts that are similar in terms of photometric, geometric, and structural prop-
erties, the same holds recursively for their subparts, and the same holds for their neigh-
bor parts. To this end, a shape is represented by a hierarchical attributed graph whose
node attributes encode the intrinsic properties of corresponding multiscale shape parts
(e.g., intensity gradient, length, orientation), and edge attributes capture the strength of
neighbor and part-of interactions between the parts. We formulate shape matching as
finding the subgraph isomorphism that preserves the original graph connectivity and
minimizes a quadratic cost whose linear and quadratic terms account for differences

A. Torsello, F. Escolano, and L. Brun (Eds.): GbRPR 2009, LNCS 5534, pp. 1–10, 2009.

c Springer-Verlag Berlin Heidelberg 2009
2 N. Payet and S. Todorovic

between node and edge attributes, respectively. The cost is defined so as to be invariant
to scale changes and in-plane rotation of the shapes. The search in the matching space
of all shape-part pairs is accelerated by convexifying the quadratic cost, which also re-
duces the chances to get trapped in a local minimum. As our experiments demonstrate,
the proposed approach is robust against large variations of individual shape parts and
partial occlusion.
In the rest of this paper, Sec. 2 points out main contributions of our approach with re-
spect to prior work, Sec. 3 describes our hierarchical representation of a shape, Sec. 4.1
specifies node and edge compatibilities and formulates our matching algorithm, Sec. 4.2
explains how to convexify and solve the quadratic program, and Sec. 5 presents experi-
mental evaluation of our approach.

2 Our Contributions and Relationships to Prior Work

This section reviews prior work and points out our main contributions. Hierarchical
shape representations are aimed at efficiently capturing both global and local properties
of shapes, and thus facilitating their matching. Shortcomings of existing representations
typically reduce the efficiency of matching algorithms. For example, the arc-tree [2,3]
trades off its accuracy and stability for lower complexity, since it is a binary tree, gener-
ated by recursively splitting the curve in two halves. Arc-trees are different for similar
shapes with some part variations, which will be hard to match. Another example is the
curvature scale-space [4,5] that loses its descriptive power by pre-specifying the degree
of image decimation (i.e., blurring and subsampling), while capturing salient curvature
points of a contour at different degrees of smoothing. Also, building the articulation-
invariant, part-based signatures of deformable shapes, presented in [6], is sensitive to
the correct identification of the shape’s landmark points and to the multidimensional
scaling and estimating of the shortest path between these points. Other hierarchical
shape descriptions include the Markov-tree graphical models [7], and the hierarchy of
polygons [8] that are based on the restrictive assumptions about the number, size, and
hierarchy depth of parts that a curve consists of. The aforementioned methods encode
only geometric properties of shape parts, and their part-of relationships, yielding a strict
tree. In contrast, we use a more general, hierarchical graph that encodes the strength of
all ascendant-descendant and neighbor relationships between shape parts, as well as
their geometric and photometric properties. The sensitivity of the graph structure to
small shape variations is reduced, since we estimate the shape’s salient points at multi-
ple scales. Also, unlike in prior work, the number of nodes, depth, and branching factor
in different parts of the hierarchical graph are data dependent.
Graph-based shape matching has been the focus of sustained research activity for more
than three decades. Graph matching may be performed by: (i) exploiting spectral prop-
erties of the graphs’ adjacency matrices [9,10]; (ii) minimizing the graph edit-distance
[11,12]; (iii) finding a maximum clique of the association graph [13]; (iv) using the
expectation-maximization of a statistical, generative model [14]. Regardless of a particu-
lar formulation, graph matching in general can be cast as a quadratic assignment problem,
where a linear term in the objective function encodes node compatibility functions, and
a quadratic term encodes edge compatibility functions. Therefore, approaches to graph
 Matching Hierarchies of Deformable Shapes 3

matching mainly focus on: (i) finding suitable definitions of the compatibility functions;
and (ii) developing efficient algorithms for approximately solving the quadratic assign-
ment problem (since it is NP-hard), including a suitable reformulation of the quadratic
into linear assignment problem. However, most popular approximation algorithms (e.g.,
relaxation labeling, and loopy belief propagation) critically depend on a good initial-
ization and may be easily trapped in a local minimum, while some (e.g., deterministic
annealing schemes) can be used only for graphs with a small number of nodes. Graduated
nonconvexity schemes [15], and successive convexification methods [16] have been used
to convexify the objective function of graph matching, and thus alleviate these problems.
Since it is difficult to convexify matching cost surfaces that are not explicit functions,
these methods resort to restrictive assumptions about the functional form of a matching
cost, or reformulate the quadratic objective function into a linear program. In this pa-
per, we develop a convexification scheme that shrinks the pool of matching candidates
for each individual node in the shape hierarchy, and thus renders the objective function
amenable to solution by a convex quadratic solver.

3 Hierarchical Shape Representation

In this paper, a shape (also called contour or curve) is represented by a hierarchical

graph. We first detect the contour’s salient points at multiple scales, which in turn define
the corresponding shape parts. Then, we derive a hierarchy of these shape parts, as
illustrated in Fig. 1.
Multiscale part detection. A data-driven number of salient (or dominant) points along
the contour are detected using the scale-invariant algorithm of [17]. This algorithm does
not require any input parameters, and remains reliable even when the shape is rich in
both fine and coarse details, unlike most existing approaches. The algorithm first de-
termines, for each point along the curve, its curvature and the region of support, which
jointly serve as a measure of the point’s relative significance. Then, the dominant points
are detected by the standard nonmaximum suppression. Each pair of subsequent domi-
nant points along the shape define the corresponding shape part. The end points of each
shape part define a straight line that is taken to approximate the part. We recursively
apply the algorithm of [17] to each shape part whose associated line segment has a

ae ea
ab be ia
eh ik ka
...
ef gh jk ...

Fig. 1. An example contour: (left) Lines approximating the detected contour parts are marked
with different colors. (right) The shape parts are organized in a hierarchical graph that encodes
their part-of and neighbor relationships. Only a few ascendant-descendant and neighbor edges
are depicted for clarity.
4 N. Payet and S. Todorovic

larger approximation error than a pre-set threshold. This threshold controls the resolu-
tion level (i.e., scale) at which we seek to represent the contour’s fine details. How to
compute this approximation error is explained later in this section. After the desired
resolution level is reached, the shape parts obtained at different scales can be organized
in a tree structure, where nodes and parent-child (directed) edges represent the shape
parts and their part-of relationships. The number of nodes, depth, and branching factors
of each node of this tree are all automatically determined by the shape at hand.
Transitive closure. Small, perceptually negligent shape variations (e.g., due to varying
illumination in images) may lead to undesired, large structural changes in the shape
tree (e.g., causing a tree node to split into multiple descendants at multiple levels).
As in [18], we address these potential structural changes of the shape tree by adding
new directed edges that connect every node with all of its descendants, resulting in a
transitive closure of the tree. Later, in matching, the transitive closures will allow that
a search for a maximally matching node pair is conducted over all descendants under a
visited ancestor node pair, rather than stopping the search if the ancestors’ children do
not match. This, in turn, will make matching more robust.
Neighbors. Like other strictly hierarchical representations, the transitive closure of the
shape tree is capable of encoding only a limited description of spatial-layout properties
of the shape parts. For example, it cannot distinguish different layouts of the same set
of parts along the shape. In the literature, this problem has been usually addressed by
associating a context descriptor with each part. In this paper, we instead augment the
transitive closure with new, undirected edges, capturing the neighbor relationships be-
tween parts. This transforms the transitive closure of the shape tree into a more general
graph that we call the shape hierarchy.
Node Attributes. Both nodes and edges of the shape hierarchy are attributed. Node
attributes are vectors whose elements describe photometric and geometric properties of
the corresponding shape part. The following estimates help us define the shape proper-
ties. We estimate the contour’s mean intensity gradient, and use this vector to identify
the contour’s direction – namely, the sequence of points along the shape – by the right-
hand rule. The principal axis of the entire contour is estimated as the principal axis of
an ellipse fitted to all points of the shape. The attribute vector of a node (i.e., shape
part) includes the following properties: (1) length as a percentage of the parent length;
(2) angle between the principal axes of this shape part and its parent; (3) approxima-
tion error estimated as the total area between the shape part and its associated straight
line, expressed as a percentage of the area of the fitted ellipse; (4) signed approximation
error is similar to the approximation error except that the total area between the shape
part and its approximating straight line is computed by accounting for the sign of the
intensity gradient along the shape; and (5) curvature at the two end points of the shape
part. All the properties are normalized to be in [0, 1].
Edge Attributes. The attribute of an edge in the shape hierarchy encodes the strength
of the corresponding part-of or neighbor relationship. Given a directed edge between a
shape part and its descendant part, the attribute of this edge is defined as the percentage
that the length of the descendant makes in the length of the shape part. Thus, the shorter
descendant or the longer ancestor, the smaller strength of their interaction. The attribute
 Matching Hierarchies of Deformable Shapes 5

of an undirected edge between two shape parts can be either 1 or 0, where 1 means that
the parts have one common end point, and 0 means that the parts are not neighbors.

4 Shape Matching
Given two shapes, our goal is to identify best matching shape parts and discard dis-
similar parts, so that the total cost is minimized. This cost is defined as a function of
geometric, photometric, and structural properties of the matched parts, their subparts,
and their neighbor parts, as explained below.

4.1 Definition of the Objective Function of Matching

Let H = (V, E, ψ, φ) denote the shape hierarchy, where V = {v} and E = {(v, u)} ⊆
V × V are the sets of nodes and edges, and ψ and φ are functions that assign attributes
to nodes, ψ : V →[0, 1]d, and to edges, φ : E→[0, 1]. Given two shapes, H and H  , the
goal of the matching algorithm is to find the subgraph isomorphism, f :U →U  , where
U ⊆V and U  ⊆V  , which minimizes the cost, C, defined as
   
C = β v∈V c1 (v, f (v)) + (1 − β) (v,u)∈E c2 (v, f (v), u, f (u)) , (1)

where c1 is a non-negative cost function of matching nodes v and v  = f (v), and c2

is a non-negative cost function of matching edges (v, u) and (v  , u ), and β ∈ [0, 1]
weights their relative significance to matching. To minimize C, we introduce a vector,
X, indexed by all node pairs (v, v  )∈V ×V  , whose each element xvv ∈[0, 1] encodes
the confidence that pair (v, v  ) should be matched. Matching can then be reformulated
as estimating X so that C is minimized. That is, we use the standard linearization and
relaxation of (1) to obtain the following quadratic program (QP):
 
minX βAT X + (1 − β)X T BX ,   (2)
s.t. ∀(v, v  )∈V ×V  , xvv ≥0, ∀v  ∈V  , v∈V xvv =1, ∀v∈V, v ∈V  xvv =1,

where A is a vector of costs avv of matching nodes v and v  , and B is a matrix of costs
bvv uu of matching edges (v, u) and (v  , u ). We define avv = d1 ψ(v) − ψ(v  )2 ,
where d is the dimensionality of the node attribute vector. Also, we define bvv uu so
that matching edges of different types is prohibited, and matches between edges of the
same type with similar properties are favored in (2): bvv uu = ∞ if edges (v, u) and
(v  , u ) are not of the same type; and bvv uu = |φ(v, v  ) − φ(u, u )| ∈ [0, 1] if edges
(v, u) and (v  , u ) are of the same type.
The constraints in (2) are typically too restrictive, because of potentially large struc-
tural changes of V or E in H that may be caused by relatively small variations of
certain shape parts. For example, suppose H and H  represent similar shapes. It may
happen that node v in H corresponds to a subgraph consisting of nodes {v1 , . . . , vm 
}

in H , and vice versa. Therefore, a more general many-to-many matching formulation
would be more appropriate for our purposes. The literature reports a number of heuris-
tic approaches to many-to-many matching [19,20,21], which however are developed
only for weighted graphs, and thus cannot be used for our shape hierarchies that have
6 N. Payet and S. Todorovic

a1v a2v avv

v v ... v
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

Fig. 2. Convexification of costs {avv }v ∈V  for each node v ∈ V . Matching candidates of v that
belong to the region of support of the lower convex hull, v  ∈ V̆  (v), are marked red.

attributes on both nodes and edges. To relax the constraints in (2), we first match H to
H  , which yields solution X1 . Then, we match H  to H, which yields solution X2 . The
final solution, X̃, is estimated as an intersection of non-zero elements of X1 and X2 .
 
Formally, theconstraints are relaxed as follows: (i) ∀(v, v ) ∈ V ×V  , xvv ≥ 0; and
(ii) ∀v ∈ V, v ∈V  xvv = 1 when matching H to H  ; and ∀v  ∈ V  , v∈V xvv = 1
when matching H  to H.

4.2 Convexification of the Objective Function of Matching

The QP in (2) is in general non-convex, and defines a matching space of typically 104
possible node pairs in our experiments. In order to efficiently find a solution, we con-
vexify the QP. This significantly reduces the number of matching candidates.
Given H and H  to be matched, for each node v ∈ V of H, we identify those
matching candidates v  ∈ V  of H  that form the region of support of the lower convex
hull of costs {avv }v ∈V  , as illustrated in Fig. 2. Let V̆  (v) ⊂ V  denote this region
of support of the convex hull, and let Ṽ  (v) ⊂ V  denote the set of true matches of
node v that minimize the QP in (2) (i.e., the solution). Then, by definition, we have
that Ṽ  (v) ⊆ V̆  (v), i.e., the true matches must be located in the region of support of
the convex hull. It follows, that for each node v ∈ V , we can discard those matching
candidates from V  that do not belong to V̆  (v). In our experiments, we typically ob-
tain |V̆  (v)| |V  |, which leads to a dramatic reduction of the dimensionality of the
original matching space, |V ×V  |.
In summary, we compute Ă, X̆, B̆ from original A, X, B, respectively, by deleting
all their elements avv , xvv , bvv uu for which v  ∈/ V̆  (v). Then, we use the standard
interior-reflective Newton method to solve the following program:
 
minX̆ β ĂT X̆ + (1 − β)X̆ T B̆ X̆ ,
 (3)
s.t. ∀(v, v  )∈V ×V̆  (v), xvv ≥0, ∀v∈V, v  ∈V̆  (v) xvv =1.


5 Results

This section presents the experimental evaluation of our approach on the standard
MPEG-7 and Brown shape datasets [12]. MPEG-7 has 1400 silhouette images show-
ing 70 different object classes, with 20 images per object class, as illustrated in Fig. 3.
MPEG-7 presents many challenges due to a large intra-class variability within each
class, and small differences between certain classes. The Brown shape dataset has 11
examples from 9 different object categories, totaling 99 images. This dataset introduces
 Matching Hierarchies of Deformable Shapes 7

additional challenges, since many of the shapes have missing parts (e.g., due to occlu-
sion), and the images may contain clutter in addition to the silhouettes, as illustrated
in Figs. 1, 4, 5. We use the standard evaluation on both datasets. For every silhouette
in MPEG-7, we retrieve the 40 best matches, and count the number of those that are
in the same class as the query image. The retrieval rate is defined as the ratio of the
total number of correct hits obtained and the best possible number of correct hits. The
latter number is 1400 · 20. Also, for each shape in the Brown dataset, we first retrieve
the 10 best matches, then, check if they are in the same class as the query shape, and,
finally, compute the retrieval rate, as explained above. Input to our algorithm consists
of two parameters: the fine-resolution level (approximation error defined in Sec. 3) of
representing the contour, and β. For silhouettes in both datasets, and the approximation
error (defined in Sec. 3) equal to 1%, we obtain shape hierarchies with typically 50-100
nodes, maximum hierarchy depths of 5-7, and maximum branching factors of 4-6. For
every query shape, the distances to other shapes are computed as the normalized total
matching cost, D, between the query and these other shapes. If X is the solution of our
quadratic programming, then D=[βAT X + (1−β)X T BX]/[|V | + |V  |], where |V | is
the total number of nodes in one shape hierarchy. Matching two shape hierarchies takes
about 5-10sec in MATLAB on a 3.1GHz, 1GB RAM PC.
Qualitative evaluation. Fig. 3 shows a few examples of our shape retrieval results on
MPEG-7. From the figure, our approach makes errors mainly due to the non-optimal
pre-setting of the fine-resolution level at which contours are represented by the shape
hierarchy. Also, some object classes in the MPEG-7 are characterized by multiple

Fig. 3. MPEG-7 retrieval results on three query examples and comparison with [6]. For each
query, we show 11 retrieved shapes with smallest to highest cost. (top) Results of [6]. (bottom)
Our results. Note that for deer we make the first mistake in 6th retrieval, and then get confused
with shapes whose parts are very similar to those of deer. Mistakes for other queries usually occur
due to missing to capture fine details of the curves in the shape hierarchy in our implementation.
8 N. Payet and S. Todorovic

Fig. 4. The Brown dataset – each of the four columns shows one example pair of silhouettes, and
each of the two rows shows shape parts at a specific scale that got matched; top row shows finer
scale and bottom row shows coarser scale. As can be seen, silhouettes that belong to the same
class may have large differences; despite the differences, corresponding parts got successfully
matched (each match is marked with unique color).

Fig. 5. The Brown dataset – two example pairs of silhouettes, and their shape parts that got
matched. The shapes belong to different classes, but the algorithm identifies their similar parts, as
expected (each match is marked with unique color). The normalized total matching cost between
the bunny and gen (left), or the fish and tool (right) is larger than the costs computed for the
examples shown in Fig 4, since there are fewer similar than dissimilar parts. (β = 0.4).

disjoint contours, whereas our approach is aimed at matching only one single contour
at a time. Next, Fig. 4 shows four example pairs of silhouettes from the same class,
and their matched shape parts. Similar shape parts at multiple scales got successfully
matched in all cases, as expected. Fig. 4 presents two example pairs of silhouettes that
belong to different classes. As in the previous case, similar shape parts got successfully
matched; however, since there are fewer similar than dissimilar parts the normalized
total matching cost in this case is larger. This helps discriminate between the shapes
from different classes in the retrieval.
Quantitative evaluation. To evaluate the sensitivity of our approach to input param-
eter β, we compute the average retrieval rate on the Brown dataset as a function of
input β = 0.1 : 0.1 : 0.9. The maximum retrieval rate of 99% is obtained for β=0.4,
while for β = {0.3, 0.5, 0.6} we obtain the rate of 98%, while for other values of β
the retrieval rate gracefully decreases. This suggests that both intrinsic properties of
shape parts and their spatial relations are important for shape matching, and that our
 Matching Hierarchies of Deformable Shapes 9

Table 1. Retrieval results on the Brown dataset for β = 0.4

Approaches 1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th
[12] 99 99 99 98 98 97 96 95 93 82
[6] 99 99 99 98 98 97 97 98 94 79
[3] 99 99 99 99 99 99 99 97 93 86
Our method 99 99 98 98 98 97 96 94 93 82

algorithm is relatively insensitive to small changes of β around 0.4. However, as any

hierarchical approach, ours also seems to be sensitive to the right choice of the finest
resolution at which the shape is represented. As mentioned above, different values of
this input parameter may result in large variations of the number of nodes in the shape
hierarchy, which, in turn, cause changes in computing the normalized total matching
cost. If the right choice is selected separately for each class of MPEG-7, using valida-
tion data, then we obtain the retrieval rate of 88.3%. If this parameter is set to 1%, as
stated above, for all classes, then our performance drops to 84.3%. This is comparable
to the state of the art that achieves the rates of 85.40% in [6] and 87.70% in [3]. Table 1
summarizes our retrieval rates on the Brown dataset after first top 1 to 10 retrievals, for
β = 0.4 and shape-resolution level fixed over all classes. Again, this retrieval improves
if we select a suitable value for the resolution parameter for each class separately, using
validation data.

6 Conclusion

Matching deformable shapes is difficult since they may be perceptually similar, but
have certain parts very different or even missing. We have presented an approach aimed
at robust matching of deformable shapes by identifying multiscale salient shape parts,
and accounting for their intrinsic properties, and part-of and neighbor relationships.
Experimental evaluation of the proposed hierarchical shape representation and shape
matching via minimizing a quadratic cost has demonstrated that the approach robustly
deals with large variations or missing parts of perceptually similar shapes.

References
1. Biederman, I.: Recent psychophysical and neural research in shape recognition. In: Osaka,
N., Rentschler, I., Biederman, I. (eds.) Object Recognition, Attention, and Action, pp. 71–88.
Springer, Heidelberg (2007)
2. Günther, O., Wong, E.: The arc tree: an approximation scheme to represent arbitrary curved
shapes. Comput. Vision Graph. Image Process. 51(3), 313–337 (1990)
3. Felzenszwalb, P.F., Schwartz, J.D.: Hierarchical matching of deformable shapes. In: CVPR
(2007)
4. Mokhtarian, F., Mackworth, A.K.: A theory of multiscale, curvature-based shape representa-
tion for planar curves. IEEE TPAMI 14(8), 789–805 (1992)
5. Ueda, N., Suzuki, S.: Learning visual models from shape contours using multiscale con-
vex/concave structure matching. IEEE TPAMI 15(4), 337–352 (1993)
10 N. Payet and S. Todorovic

6. Ling, H., Jacobs, D.: Shape classification using the inner-distance. IEEE TPAMI 29(2), 286–
299 (2007)
7. Fan, X., Qi, C., Liang, D., Huang, H.: Probabilistic contour extraction using hierarchical
shape representation. In: ICCV, pp. 302–308 (2005)
8. Mcneill, G., Vijayakumar, S.: Hierarchical procrustes matching for shape retrieval. In: CVPR
(2006)
9. Siddiqi, K., Shokoufandeh, A., Dickinson, S.J., Zucker, S.W.: Shock graphs and shape match-
ing. Int. J. Comput. Vision 35(1), 13–32 (1999)
10. Shokoufandeh, A., Macrini, D., Dickinson, S., Siddiqi, K., Zucker, S.W.: Indexing hierarchi-
cal structures using graph spectra. IEEE TPAMI 27(7), 1125–1140 (2005)
11. Bunke, H., Allermann, G.: Inexact graph matching for structural pattern recognition. Pattern
Rec. Letters 1(4), 245–253 (1983)
12. Sebastian, T.B., Klein, P.N., Kimia, B.B.: Recognition of shapes by editing their shock
graphs. IEEE Trans. Pattern Anal. Machine Intell. 26(5), 550–571 (2004)
13. Pelillo, M., Siddiqi, K., Zucker, S.W.: Matching hierarchical structures using association
graphs. IEEE TPAMI 21(11), 1105–1120 (1999)
14. Tu, Z., Yuille, A.: Shape matching and recognition - using generative models and informative
features. In: Pajdla, T., Matas, J(G.) (eds.) ECCV 2004. LNCS, vol. 3023, pp. 195–209.
Springer, Heidelberg (2004)
15. Gold, S., Rangarajan, A.: A graduated assignment algorithm for graph matching. IEEE
TPAMI 18(4), 377–388 (1996)
16. Jiang, H., Drew, M.S., Li, Z.N.: Matching by linear programming and successive convexifi-
cation. IEEE TPAMI 29(6), 959–975 (2007)
17. Teh, C.H., Chin, R.T.: On the detection of dominant points on digital curves. IEEE Trans.
Pattern Anal. Mach. Intell. 11(8), 859–872 (1989)
18. Torsello, A., Hancock, E.R.: Computing approximate tree edit distance using relaxation la-
beling. Pattern Recogn. Lett. 24(8), 1089–1097 (2003)
19. Pelillo, M., Siddiqi, K., Zucker, S.W.: Many-to-many matching of attributed trees using as-
sociation graphs and game dynamics. In: Arcelli, C., Cordella, L.P., Sanniti di Baja, G. (eds.)
IWVF 2001. LNCS, vol. 2059, pp. 583–593. Springer, Heidelberg (2001)
20. Demirci, M.F., Shokoufandeh, A., Keselman, Y., Bretzner, L., Dickinson, S.J.: Object recog-
nition as many-to-many feature matching. Int. J. Computer Vision 69(2), 203–222 (2006)
21. Todorovic, S., Ahuja, N.: Region-based hierarchical image matching. Int. J. of Computer
Vision 78(1), 47–66 (2008)
 Edition within a Graph Kernel Framework for
Shape Recognition

François-Xavier Dupé and Luc Brun