Matching Hierarchical Structures Using Association Graphs.
AbstractIt is well-known that the problem of matching two relational structures can be posed as an equivalent problem of finding a maximal clique in a (derived) association graph. However, it is not clear how to apply this approach to computer vision problems where the graphs are hierarchically organized, i.e., are trees, since maximal cliques are not constrained to preserve the partial order. Here, we provide a solution to the problem of matching two trees by constructing the association graph using the graph-theoretic concept of connectivity. We prove that, in the new formulation, there is a one-to-one correspondence between maximal cliques and maximal subtree isomorphisms. This allows us to cast the tree matching problem as an indefinite quadratic program using the Motzkin-Straus theorem, and we use replicator dynamical systems developed in theoretical biology to solve it. Such continuous solutions to discrete problems are attractive because they can motivate analog and biological implementations. The framework is also extended to the matching of attributed trees by using weighted association graphs. We illustrate the power of the approach by matching articulated and deformed shapes described by shock trees.
where jCj denotes the cardinality of C.
Now, consider the following quadratic function
where A ??aij? is the adjacency matrix of G, i.e., the n n
symmetric matrix defined as

0; otherwise:
A point x 2 Sn is said to be a global maximizer of f in Sn if
f?x?f?x?, for all x 2 Sn. It is said to be a local maximizer
if there exists an >0 such that f?x?f?x? for all x 2 Sn
whose distance from x is less than and if f?x??f?x?
PELILLO ET AL.: MATCHING HIERARCHICAL STRUCTURES USING ASSOCIATION GRAPHS 1109
implies x ? x, then x is said to be a strict local maximizer.
Note that f?x?1 for all x 2 Sn.
The Motzkin-Straus theorem [40] establishes a remarkable
connection between global (local) maximizers of the
function f in Sn and maximum (maximal) cliques of G.
Specifically, it states that a subset of vertices C of a graph G
is a maximum clique if and only if its characteristic vector
xc is a global maximizer of f on Sn. A similar relationship
holds between (strict) local maximizers and maximal
cliques [19], [50]. This result has an intriguing computational
significance in that it allows us to shift from the
discrete to the continuous domain. Such a reformulation is
attractive for several reasons: It suggests how to exploit the
full arsenal of continuous optimization techniques, thereby
leading to the development of new algorithms, and may
also reveal unexpected theoretical properties. Additionally,
continuous optimization methods are often described in
terms of sets of differential equations and are, therefore,
potentially implementable in analog circuitry. The Motzkin-
Straus theorem has served as the basis of several clique-
finding procedures [10], [18], [45], [46] and has also been
used to determine theoretical bounds on the cardinality of
the maximum clique [45], [64].
One drawback associated with the original Motzkin-
Straus formulation relates to the existence of spurious
solutions, i.e., maximizers of f which are not in the form of
characteristic vectors. This was observed empirically by
Pardalos and Phillips [45] and more recently formalized by
Pelillo and Jagota [50]. In principle, spurious solutions
represent a problem since, while providing information
about the cardinality of the maximum clique, they do not
allow us to easily extract its vertices. Fortunately, there is a
solution to this problem which has recently been introduced
and studied by Bomze [7]. Consider the following regularized
version of f:f^?x??x0Ax ? x0x; ?2?which is obtained from (1) by substituting the adjacency
matrix A of G withA^ ? A ? In;where In is the n n identity matrix. The following is the
spurious-free counterpart of the original Motzkin-Straus
theorem (see [7] for a proof).
Theorem 2. Let C be a subset of vertices of a graph G, and let xc
be its characteristic vector. Then the following statements hold:
1. C is a maximum clique of G if and only if xc is a global
maximizer of the function f^ in Sn. In this case,
2. C is a maximal clique of G if and only if xc is a local
maximizer of f^ in Sn.
3. All local (and, hence, global) maximizers of f^ in Sn are
strict.
Unlike the original Motzkin-Straus formulation, the
previous result guarantees that all maximizers of f^ on Sn
are strict, and are characteristic vectors of maximal/
maximum cliques in the graph. In a formal sense, therefore,
a one-to-one correspondence exists between maximal
cliques and local maximizers of f^ in Sn on the one hand
and maximum cliques and global maximizers on the other
hand.
We now turn our attention to a class of dynamical systems
that we use for solving our quadratic optimization problem.
Let W be a nonnegative real-valued n n matrix and
consider the following dynamical system:

where a dot signifies derivative w.r.t. time t, and its
discrete-time counterpart
It is readily seen that the simplex Sn is invariant under these
dynamics, which means that every trajectory starting in Sn
will remain in Sn for all future times. Moreover, it turns out
that their stationary points, i.e., the points satisfying x_i?t??0
for (3) or xi?t ? 1??xi?t? for (4), coincide and are the
solutions of the equations:
A stationary point x is said to be asymptotically stable if every
solution to (3) or (4) which starts close enough to x
converges to x as t !1.
Both (3) and (4) are called replicator equations in
theoretical biology since they are used to model evolution
over time of relative frequencies of interacting, self-replicating
entities [23]. The discrete-time dynamical equations
turn out to be a special case of a general class of
dynamical systems introduced by Baum and Eagon [5] in
the context of the theory of Markov chains. They also
represent an instance of the original Rosenfeld-Hummel-
Zucker relaxation labeling algorithm [56], whose dynamical
properties have recently been clarified [47] (specifically, it
corresponds to the 1-object, n-label case).
We are now interested in the dynamical properties of
replicator equations; it is these properties that will allow us
to solve our original tree matching problem.
Theorem 3. If W ? W0, then the function x?t?0Wx?t? is strictly
increasing with increasing t along any nonstationary trajectory
x?t? under both continuous-time (3) and discrete-time (4)
replicator dynamics. Furthermore, any such trajectory converges
to a stationary point. Finally, a vector x 2 Sn is
asymptotically stable under (3) and (4) if and only if x is a
strict local maximizer of x0Wx on Sn.
The previous result is known in mathematical biology as
the fundamental theorem of natural selection [13], [23], [63]
and, in its original form, traces back to Fisher [15]. As far as
the discrete-time model is concerned, it can be regarded as a
straightforward implication of the more general Baum-
Eagon theorem [5]. The fact that all trajectories of the
replicator dynamics converge to a stationary point has been
proven more recently [33], [35].
Fig. 4. A coloring of shocks into four types [28]. A 1-shock derives from a protrusion and traces out a curve segment of adjacent 1-shocks, along
which the radius function varies monotonically. A 2-shock arises at a neck, where the radius function attains a strict local minimum, and is
immediately followed by two 1-shocks flowing away from it in opposite directions. 3-shocks correspond to an annihilation into a curve segment due to
a bend, along which the radius function is constant, and a 4-shock is an annihilation into a point or a seed, where the radius function attains a strict
local maximum. The loci of these shocks gives Blum's medial axis.
In light of their dynamical properties, replicator equations
naturally suggest themselves as a simple heuristic for
solving the maximal subtree isomorphism problem. Let
be two rooted trees and let A
denote the N-node adjacency matrix of the corresponding
TAG. By lettingW ? A ? IN;where IN is the N N identity matrix, we know that the
replicator dynamical systems (3) and (4), starting from an
arbitrary initial state, will iteratively maximize the function
f^ defined in (2) over SN and will eventually converge with
probability 1 to a strict local maximizer which, by virtue of
Theorem 2, will then correspond to the characteristic vector
of a maximal clique in the association graph. As stated in
Theorem 1, this will in turn induce a maximal subtree
isomorphism between
Clearly, in theory, there is no guarantee that the
converged solution will be a global maximizer of f^ and,
therefore, that it will induce a maximum isomorphism
between the two original trees. Previous experimental work
done on the maximum clique problem [10], [46], and also
the results presented in this paper, however, suggest that
the basins of attraction of optimal or near-optimal solutions
are quite large and, very frequently, the algorithm converges
to one of them, despite its inherent inability to
escape from local optima.
Since the process cannot leave the boundary of SN,itis
customary to start out the relaxation process from some
interior point, a common choice being the barycenter of SN,
i.e., the vector ?1 This prevents the search from
being initially biased in favor of any particular solution.
5AN EXAMPLE:MATCHING SHOCK TREES
We now illustrate our framework for matching hierarchical
structures with numerical examples of shape matching.
Because of the subtleties associated with generating random
trees of relevance to applications in computer vision and
pattern recognition, we use a class of example trees derived
from a real system. Our representation for shape is based on
an abstraction of the shocks (or singularities) of a curve
evolution process, acting on a simple closed curve in the
plane, into a shock tree. We begin by providing some
background on the representation (for details see [28], [62])
and then present experimental results on matching shock
trees. In Section 6, we extend the framework to incorporate
attributes associated with shock tree nodes.
5.1 The Shock Tree
In [27], [28], the following evolution equation was proposed
for visual shape analysis:
Here, C?p;t? is the vector of curve coordinates, N?p;t? is the
inward normal, p is the curve parameter, and t is the
evolutionary time of the deformation. The constant 0
controls the regularizing effects of curvature . When is
large, the equation becomes a geometric heat equation;
When ? 0, the equation is hyperbolic and shocks [30], or
entropy-satisfying singularities, can form. In the latter case
the locus of points through which the shocks migrate is
related to Blum's grassfire transformation [12], [28],
although significantly more information is available via a
?coloring? of these positions. Four types can arise, according
to the local variation of the radius function along the
medial axis (Fig. 4). Intuitively, the radius function varies
monotonically at a type 1, reaches a strict local minimum at
a type 2, is constant at a type 3, and reaches a strict local
maximum at a type 4. The classification of shock positions
according to their colors and an enumeration of the possible
local neighborhoods around each shock type is at the heart
of the representation.
Shocks of the same type that form a connected
component are grouped together to comprise the nodes of
a shock graph, with the 1-shock groups separated at branch-points
of the skeleton. Directed edges in the graph are
PELILLO ET AL.: MATCHING HIERARCHICAL STRUCTURES USING ASSOCIATION GRAPHS 1111
Fig. 5. Two illustrative examples of the shocks obtained from curve evolution (from [62]). Left: The notation associated with the locus of shock points
is of the form shock_type-identifier. Right: The corresponding trees have the shock_type on each node, with the identifier adjacent. The last shocks
to form during the curve evolution process appear under a root node labeled #.
placed between shock groups that touch one another such
that each parent node contains no shocks that formed prior
to any shocks in a child node. This corresponds to a
?reversal? in time of the curve evolution process to obtain a
hierarchy of connected components. The graph is rooted at
a unique vertex #, the children of which are the last shock
groups to form, e.g., the palms of the hand silhouettes in
Fig. 5. (The letters ?a? and ?b? denote different sides of the
same shock group). A key property of the shock graph is
that its topological structure is highly constrained because
the events that govern the birth, combination, and death of
shock groups are completely characterized by a shock
grammar, with a small number of rewrite rules [62]. In
particular, each shock graph can be reduced to a unique
rooted shock tree.
5.2 Experimental Results
We now illustrate the power of the hierarchical structure
matching algorithm on shock trees. Whereas each node has
geometric attributes, related to properties of the shocks in
each group, for now we shall consider only the shock tree
topologies. (We shall consider the geometry shortly.) We
selected 25 silhouettes representing eight different object
classes (Table 1, first column); the tool shapes were taken
from the Rutgers Tools database. Each shape was then
matched against all entries in the database. Fig. 6 shows the
maximal subtree isomorphisms found by the algorithm for
three examples. The top eight matches for each query shape,
along with the associated scores, are shown in Table 1. The
scores indicate the average of n=n1 and n=n2, where n is the
size of the maximal clique found, and n1 and are the
number of nodes in each tree. We observed that, in all our
1112 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 21, NO. 11, NOVEMBER 1999

A Tabulation of the Top Eight Topological Matches for Each Query
The scores indicate the average of the fraction of nodes matched in each of the two trees (see text). Note that only the topology of the shock trees
was used; the addition of geometric information permits finer discrimination (compare with Table 2).
experiments, the maximal cliques found were also maximum
cliques. This is due to the property that global
maximizers of the objective function typically have large
basins of attraction, as also shown experimentally in [46],
[49], [10]. The matching algorithm generally takes only two
to three seconds to converge on a Sparc 10.
Note that, despite the fact that metric/label information
associated with nodes in the shock trees was discounted
altogether, all exemplars in the same class as the query
shape are typically within the top five matches, illustrating
the potential of a topological matching process for indexing
into a database of shapes. Nevertheless, there exist a few
matches which appear to be counterintuitive, e.g., matches
[(Row 1, Column 3); (Row 2, Column 3); (Row 13, Column
(Row 14, Column 4); (Row 21, Column 2) and (Row 21,
Column 3)]. These correspond to shapes with similar shock-
tree topologies (hierarchies of parts), but drastically
different shock geometries (part shapes). In the following
section, we extend our framework to incorporate the latter
geometric information contained in each shock sequence
(the location, time of formation, speed, and direction of each
shock) as attributes on the nodes. We show that this leads to
better discrimination between shapes than that provided by
shock tree topologies alone.
PELILLO ET AL.: MATCHING HIERARCHICAL STRUCTURES USING ASSOCIATION GRAPHS 1113
Fig. 6. Maximal subtree isomorphisms found for three illustrative
examples. The shock-based descriptions of the hand silhouettes are
shown in Fig. 5; the shock-trees for the other silhouettes were computed
in a similar fashion.
6ATTRIBUTED TREE MATCHING AND WEIGHTED
TAGS
In many computer vision and pattern recognition applica-
tions, the trees being matched have nodes with an
associated vector of symbolic and/or numeric attributes.
In this section, we show how the proposed framework can
naturally be extended for solving attributed tree matching
problems.
6.1 Attributed Tree Matching as Weighted Clique
Search
Formally, an attributed tree is a triple T ??V;E;?, where
?V;E? is the ?underlying? rooted tree and is a function
which assigns an attribute vector ?u? to each node u
is clear that, in matching two attributed trees, our objective
is to find an isomorphism which pairs nodes having
?similar? attributes. To this end, let be any similarity
measure on the attribute space, i.e., any (symmetric)
function which assigns a positive number to any pair of
attribute vectors. If : H1 ! H2 is a subtree isomorphism
between two attributed trees
??V2;E2;2?, the overall similarity between the induced
subtrees T1?H1? and T2?H2? can be defined as follows:
The isomorphism is called a maximal similarity subtree
isomorphism if there is no other subtree isomorphism
H20 such that H1 is a strict subset of H10 and
S?? <S?0?. It is called a maximum similarity subtree
isomorphism if S?? is largest among all subtree isomorphisms
between
The weighted TAG of two attributed trees T1 and T2 is the
weighted graph G ??V;E;!?, where V and E are defined
as in Definition 2 and ! is a function which assigns a
positive weight to each node ?u; v?2V ? V1 V2 as follows:
Given a subset of nodes C of V , the total weight assigned to
C is simply the sum of all the weights associated with its
nodes. A maximal weight clique in G is one which is not
contained in any other clique having larger total weight,
while a maximum weight clique is a clique having largest
total weight. The maximum weight clique problem is to find
a maximum weight clique of G [9]. Note that the
unweighted version of the maximum clique problem arises
as a special case when all the nodes are assigned a constant
weight.
The following result, which is the weighted counterpart
of Theorem 1, establishes a one-to-one correspondence
between the attributed tree matching problem and the
maximum weight clique problem (the proof is essentially
identical to that of Theorem 1).
Theorem 4. Any maximal (maximum) similarity subtree
isomorphism between two attributed trees induces a maximal
weight clique in the corresponding weighted TAG,
and vice versa.
6.2 Matching Attributed Trees
Recently, the Motzkin-Straus formulation of the maximum
clique problem has been extended to the weighted case [19].
Let G ??V;E;!? be an arbitrary weighted graph of order n.
The (weighted) characteristic vector of any subset of nodes
denoted xc, is defined as follows:

c !?ui?=?C?; if ui 2 C
where ?C?? uj2C !?uj? is the total weight on C.
Now, consider the following class of n n symmetric
matrices:
1114 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 21, NO. 11, NOVEMBER 1999
and the quadratic function
2M?G?. The following theorem, which is the
weighted counterpart of Theorem 2, expands on a recent
result by Gibbons et al. [19], which in turn generalizes the
Motzkin-Straus theorem to the weighted case (see [8], [11]
for a proof).
Theorem 5. Let G ??V;E;!? be an arbitrary weighted graph
and let B 2M?G?. Then, the following hold:
1. A vector x 2 Sn is a local minimizer of g on Sn if
and only if x ? xc, where C is a maximal weight
clique of G.
2. A vector x 2 Sn is a global minimizer of g on Sn if
and only if x ? xc, where C is a maximum weight
clique of G.
3. All local (and hence global) minimizers of g on Sn are
strict.
In contrast to the Gibbons et al. formulation [19], which is
plagued by the presence of spurious solutions, as is the
original Motzkin-Straus problem [11], the previous result
guarantees that all minimizers of g on Sn are strict and are
characteristic vectors of maximal/maximum weight cliques
in the graph. Note that the class M?G? is isomorphic to the
positive orthant in n ?jEj dimensions, where jEj is thenumber of edges in G. This class is a polyhedral pointed
cone with its apex given by the following matrix, which is
the one used in the experiments described below:< 2!?1ui? if i ? j;
Having formulated the maximum weight clique problem
as a quadratic program over the standard simplex,
we can use the replicator equations to approximately
solve it. However, note that replicator equations are
maximization procedures, while ours is a minimization
problem. It is straightforward to see that the problem of
minimizing the quadratic form x0Bx on the simplex is
equivalent to that of maximizing x0?ee0 ? B?x, where
is an arbitrary constant.1
be two attributed trees, G ??V;E;!?
be the corresponding weighted TAG, and define
where B ??bij? is any matrix in the class M?G? and
maxbij. From the fundamental theorem of natural
1. Note that the conversion of the minimization problem to a
maximization problem is driven by a purely algorithmic (as opposed to
issue. One could minimize x0Bx on the simplex using
alternative optimization techniques [29], [53]. However, since we are
matching trees and not graphs, we expect the difference in performance to
be marginal.
selection (Theorem 3), we know that the replicator
dynamical systems (3) and (4) will find local maximizers
of the function x0Wx (and, hence, minimizers of x0Bx) over
the standard simplex and, by virtue of Theorem 5, these will
correspond to the characteristic vectors of maximal weight
cliques in the weighted TAG. As stated in Theorem 4, these
will in turn induce maximal similarity subtree isomorphisms
between As in the unweighted case, there is
no theoretical guarantee that the solutions found will be the
globally optimal ones, but the experiments reported in [11]
on the maximum weight clique problem suggest that, here
too, the attraction basins of global maximizers are quite
large. This observation is also confirmed by the experiments
reported below, each of which typically took 5 to 10 seconds
to run on a Sparc 10.
6.3 Experimental Results
We now provide examples of weighted shock tree match-
ing, using the geometric attributes associated with shock
tree nodes. The vector of attributes assigned to each node
of the attributed shock tree T ??V;E;? is given by
is the
number of shocks in the group, and xi;yi;ri;vi;i are,
respectively, the x coordinate, the y coordinate, the radius
(or time of formation), the speed, and the direction of each
shock i in the sequence, obtained as outputs of the shock
detection process [60], [61]. In order to apply our frame-
work, we must define a similarity measure between the
attributes of two nodes u and v.
The similarity measure we use is a linear combination of
four terms, incorporating the differences in lengths, radii,
velocities, and curvature of the two shock sequences,
respectively. Each term is normalized to provide a unitless
quantity so that these different geometric properties can be
combined. Let u contain m shocks and v contain n shocks
and, without loss of generality, assume that m n. The
Euclidean length of each sequence of shocks is given by:
Xn?1 q??????????????????????????????????????????????????????
!di:ne be the many-to-one mapping of each
index i 2f1; :::; mg to an index j 2f1; :::; ng. The similarity
measure between the two attribute vectors used in our
experiments is defined as:
PELILLO ET AL.: MATCHING HIERARCHICAL STRUCTURES USING ASSOCIATION GRAPHS 1115
different problems and the maximal
clique formulation invokes much weaker constraints. In [4],
(1 Xm r?i??r??i?? 2)12 we present an extension of the maximal clique formulation
? r to the case of many-to-one correspondences, which is of
i?1 particular interest in computer vision and pattern recogni-
tion applications where the trees being matched are noisy,
? v and vertices are deleted or added.
(2)1
i?1 We have developed a formal approach for matching
hierarchical structures by constructing an association graph
whose maximal cliques are in one-to-one correspondence
where l;r;v; are nonnegative constants summing to 1 with maximal subtree isomorphisms. The framework is
and is the change in orientation at each shock. The
general and can be applied in a variety of computer vision
measure provides a number between 0 and 1, which
and pattern recognition domains: We have demonstrated its
represents the overall similarity between the geometric
potential for shape matching. The formulation allows us to
attributes of the two nodes being compared. The measure is
cast the tree-matching problem as an indefinite quadratic
designed to be invariant under rotations and translations of
program owing to the Motzkin-Straus theorem. The solu-
two shapes and to satisfy the requirements of the weight
tion is found by using a dynamical system, which makes it
function discussed in Section 6.1.
amenable to hardware implementation and offers the
We repeated the earlier experiments, but now with
advantage of biological plausibility. In particular, these
weights w?u; v????u?;?v?? placed on each node ?u;v? of relaxation equations are related to putative neuronal
a weighted TAG. The weights were defined by (9), with implementations [38], [39]. We have also extended the
l;r;v; set to 0.25, 0.4, 0.2, and 0.15, respectively. We framework to the problem of matching hierarchical struc-
verified that the overall results were not sensitive to the tures with attributes. The attributes result in weights being
precise choice of these parameters or to slight variations in placed on the nodes of the association graph and a
the similarity measure such as the use of a different norm. conversion of the maximum clique problem to a maximum
We ranked the results using a score given by the quantity weight clique problem. An extension of the proposed
is the size of framework to problems involving many-to-one correspondences
is presented in [4].
the maximal weight clique found, W its weight, M1 and M2
Characterizing the complexity of our approach appears
the total mass associated with the nodes of each tree, and
to be difficult since it involves the simulation of a dynamical
m?u?;m?v? the masses of nodes u and v, respectively. The
system. However, we have observed experimentally that
score represents the weight of the maximal clique scaled by
the basins of attraction of the global maximizers are large,
the average of the total (relative) mass of nodes in each tree
both in the unweighted and weighted cases, and that the
that participates in the match. As before, the top eight system converges quickly when applied to shock-tree
matches are shown for each query shape, in Table 2. It is matching. Conversely, whereas polynomial time algorithms
evident that, for almost all queries, performance improves exist for the maximum common subtree problem [37], [54],
with the incorporation of geometric attributes, with better [17], to our knowledge no such algorithm exists for the case
overall discrimination between the shapes (compare with of weighted tree matching. This provides further justifica-
Table

1). Nonetheless, there is an inherent trade-off between tion for our framework.
geometry and topology, e.g., observe that the short fat
screwdriver in row 15 scores better with the fatter hand APPENDIX
shapes than with the thin, elongated screwdrivers.
We note that the qualitative results, specifically, the
partial ordering of matches in each row of Table 2, compare Before presenting the proof of Lemma 1, we need some
favorably with those obtained using an alternate approach preliminary remarks and definitions. First, note that path-
described in [62]. The latter approach has been applied strings cannot be arbitrary strings of ?1s and ?1s. Since
successfully to the same database of shapes used here and is trees do not have cycles, in fact, once we go down one level
a sequential (level by level) approach with backtracking. At along a path (i.e., we make a ?+1? move), we cannot return
each step, an eigenvalue labeling of the adjacency matrix of to the parent. This is formally stated by saying that if
the subtrees rooted at the two nodes being matched is used. str?u; v??s1s2 .sn is the path-string between any two
In other words, the cost of matching two nodes incorporates nodes u and v, then si ??1 implies sj ??1 for all j i.
not only their geometries, but a measure of the similarity Now, we define the path-pair of any two nodes u and v in
between their subtrees, which is global. Furthermore, the a tree as pair?u; v???n; p?, where n is the number of
algorithm tolerates noise by allowing for jumps between negative components in str?u; v? and p is the number of
levels. Hence, strictly speaking, it solves an approximation to positive components in str?u; v?. It is clear from the previous
the subtree isomorphism problem. For these reasons, a one- observation that path-pairs and path-strings are equivalent
to-one comparison between the two algorithms is not concepts. In fact, we have: str?u;v??str?w; z? if and only if

A Tabulation of the Top Eight Attributed Toplogical Matches for Each Query
The scores indicate the weight of the maximal clique multiplied by the average of the total relative mass of nodes in each tree matched (see text).
The addition of geometric information permits finer discrimination between the shapes (compare with Table 1).
note that if a node w is on
the path between any two nodes u and v in a rooted tree,
then str?u; v? can be obtained by concatenating str?u; w? and
str?w; v?. This implies that
where ??? denotes the usual sum between vectors. In a
sense, then, path-pairs allow us to do ?arithmetic? on path-
strings, a fact which will be technically useful in the sequel.
(The full algebraic structure will not be needed here.)
We are now in a position to prove Lemma 1. For
convenience, we repeat its statement below.
Lemma 1. Let u1;v1;w1;z1 2 V1 and u2;v2;w2;z2 2 V2 be
distinct nodes of rooted trees
??V2;E2?, and suppose that the following conditions hold:
1. w1 is on the u1v1-path, and w2 is on the u2v2-path
2. str?u1;w1??str?u2;w2?
3. str?w1;v1??str?w2;v2?
4. str?u1;z1??str?u2;z2?
5. str?v1;z1??str?v2;z2?
Then, str?w1;z1??str?w2;z2?.
PELILLO ET AL.: MATCHING HIERARCHICAL STRUCTURES USING ASSOCIATION GRAPHS 1117
Fig. 7. An illustration of the cases arising in the proof of Lemma 1.
Proof. First, note that, from conditions 1-3, we also have
6. str?u1;v1??str?u2;v2?.
We shall prove that pair?w1;z1??pair?w2;z2?, which is,
of course, equivalent to the thesis of the lemma. The
proof consists of enumerating all possible cases and
exploiting the previous observation that, when w is on a
uv-path, then pair?u; v??pair?u; w??pair?w; v?. Before
doing so, however, we need an auxiliary notation. Let u
be a node of a rooted tree T ??V;E?. The set of nodes
belonging to the subtree rooted at u will be denoted by
?u?. This can be formally defined as follows:
Note that
We shall enumerate all the possible ways in which u1,
v1, w1, and z1 can relate to one another in T1, but it is clear
from conditions 1-6 that each such configuration induces
a perfectly symmetric situation in T2 and vice versa.
Therefore, from now on, we shall use the index i ? to
simplify the discussion. Technically, this means that we
are assuming something about one tree and, because of
our hypotheses, the same situation arises in the other.
The enumeration of all possible cases starts from the
observation that, given two different subtrees of a tree,
either one is a strict subset of the other or they are
disjoint (otherwise, in fact, there will be cycles in the
graph). Therefore, considering the subtrees rooted at
nodes ui and vi (i ? only the following cases can
arise:
1. V ?vi?V ?ui?
2. V ?ui?V ?vi?
3. V ?ui?\V ?vi??;
The first two are symmetric and, therefore, we shall
only consider Case 1. In this case, since wi is on the uivi-
path, we have V ?vi?V 2. Clearly, only four
subcases are possible (cf. Fig. 7a), that is:
1.1
1.2
1.3
2.
Let us consider Case 1.1. In this case, the vis are on the
wizi-paths and, therefore:
In Case 1.2, we have that the wis are on the uizi-paths
and, hence, pair?ui;zi??pair?ui;wi??pair?wi;zi?,
2. Therefore, we have:
Case 1.3 is similar to Case 1.2. In this case, we have that
wi is on the zivi-path and, therefore
Finally, Case 1.4 is similar to Case 1.1, since ui is on the
path joining wi and zi.
let us consider Case 3, i.e., V ?ui?\V ?vi??;
Here, the situation is slightly more compli-
cated. Since wi is on the uivi-path and this has the form
we have the following three
subcases:
3.1
3.2 V ?vi?V ?wi? and V ?wi?\V ?ui??;
3.3 V ?vi?V ?wi? and V ?ui?V ?wi?
Cases 3.1 and 3.2 are symmetric, so we shall only
consider Cases 3.1 and 3.3.
Let us start with Case 3.1. Four possible subcases arise
(Fig.
3.1.1
3.1.2
3.1.3
zi2=V ?wi? and zi 2 V ?vi?3.1.4
All these cases are similar to the previous ones and the
corresponding proofs are therefore analogous.
Finally, let us consider Case 3.3. Again, four possible
subcases arise (Fig. 7c):
3.3.1.
3.3.2.
3.3.3.
3.3.4.
and 3.3.4 are similar to those seen
before and, hence, we omit the corresponding proofs. As
to Case 3.3.3, we note that wi must necessarily be either
on the path joining ui and zi or on that joining vi and zi
(or on both), otherwise the graph would have a cycle. So,
the proof in this case is analogous to the previous ones,
and this concludes the proof of the lemma. tu

ACKNOWLEDGMENTS

This work was done while Marcello Pelillo was visiting the
Center for Computational Vision and Control at Yale
University. It was supported by Consiglio Nazionale delle
Ricerche (Italy), NSERC, FCAR, NSF, and AFOSR. We
thank the reviewers for their helpful comments and Sven
Dickinson for the use of shapes from the Rutgers Tools
database.


--R


Computer Vision.










An Introduction to Population Genetics Theory.

The Genetical Theory of Natural Selection.

Computer and Intractability: A Guide to




Graph Theory.
The Theory of Evolution and Dynamical Systems.



















--TR

--CTR
Karsten Hartelius , Jens Michael Carstensen, Bayesian Grid Matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.2, p.162-173, February
Brijnesh J. Jain , Fritz Wysotzki, Automorphism Partitioning with Neural Networks, Neural Processing Letters, v.17 n.2, p.205-215, April
Philip N. Klein , Thomas B. Sebastian , Benjamin B. Kimia, Shape matching using edit-distance: an implementation, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.781-790, January 07-09, 2001, Washington, D.C., United States
Gunilla Borgefors , Giuliana Ramella , Gabriella Sanniti di Baja, Hierarchical Decomposition of Multiscale Skeletons, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.11, p.1296-1312, November 2001
Andrea Torsello , Edwin R. Hancock, Computing approximate tree edit distance using relaxation labeling, Pattern Recognition Letters, v.24 n.8, p.1089-1097, May
Graphical models for graph matching: approximate models and optimal algorithms, Pattern Recognition Letters, v.26 n.3, p.339-346, February 2005
Marco Carcassoni , Edwin R. Hancock, Correspondence Matching with Modal Clusters, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.12, p.1609-1615, December
Horst Bunke , Simon Gnter, Weighted mean of a pair of graphs, Computing, v.67 n.3, p.209-224, November 2001
Alessio Massaro , Marcello Pelillo, Matching graphs by pivoting, Pattern Recognition Letters, v.24 n.8, p.1099-1106, May
Evgeny B. Krissinel , Kim Henrick, Common subgraph isomorphism detection by backtracking search, SoftwarePractice & Experience, v.34 n.6, p.591-607, May 2004
Simon Gnter , Horst Bunke, Self-organizing map for clustering in the graph domain, Pattern Recognition Letters, v.23 n.4, p.405-417, February 2002
Chris Ding , Xiaofeng He , Hanchuan Peng, Finding cliques in protein interaction networks via transitive closure of a weighted graph, Proceedings of the 5th international workshop on Bioinformatics, August 21-21, 2005, Chicago, Illinois
Dmitriy Bespalov , Ali Shokoufandeh , William C. Regli , Wei Sun, Scale-space representation of 3D models and topological matching, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA
Andrea Torsello , Dzena Hidovic-Rowe , Marcello Pelillo, Polynomial-Time Metrics for Attributed Trees, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.7, p.1087-1099, July 2005
S. Tabbone , L. Wendling , J.-P. Salmon, A new shape descriptor defined on the radon transform, Computer Vision and Image Understanding, v.102 n.1, p.42-51, April 2006
Marcello Pelillo, Matching Free Trees, Maximal Cliques, and Monotone Game Dynamics, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.11, p.1535-1541, November 2002
Duck Hoon Kim , Il Dong Yun , Sang Uk Lee, A comparative study on attributed relational gra matching algorithms for perceptual 3-D shape descriptor in MPEG-7, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA
Jiang , Andreas Munger , Horst Bunke, On Median Graphs: Properties, Algorithms, and Applications, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.10, p.1144-1151, October 2001
Josep Llados , Enric Mart , Juan Jose Villanueva, Symbol Recognition by Error-Tolerant Subgraph Matching between Region Adjacency Graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.10, p.1137-1143, October 2001
Davi Geiger , Tyng-Luh Liu , Robert V. Kohn, Representation and Self-Similarity of Shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.1, p.86-99, January
Michel Neuhaus , Horst Bunke, Edit distance-based kernel functions for structural pattern classification, Pattern Recognition, v.39 n.10, p.1852-1863, October, 2006
Peter J. Giblin , Benjamin B. Kimia, On the Intrinsic Reconstruction of Shape from Its Symmetries, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.7, p.895-911, July
Andrea Torsello , Edwin R. Hancock, A skeletal measure of 2D shape similarity, Computer Vision and Image Understanding, v.95 n.1, p.1-29, July 2004
M. Fatih Demirci , Ali Shokoufandeh , Yakov Keselman , Lars Bretzner , Sven Dickinson, Object Recognition as Many-to-Many Feature Matching, International Journal of Computer Vision, v.69 n.2, p.203-222, August    2006
Luca Lombardi , Alfredo Petrosino, Distributed recursive learning for shape recognition through multiscale trees, Image and Vision Computing, v.25 n.2, p.240-247, February, 2007
Thomas B. Sebastian , Philip N. Klein , Benjamin B. Kimia, Recognition of Shapes by Editing Their Shock Graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.5, p.550-571, May 2004
Bin Luo , Edwin R. Hancock, Structural Graph Matching Using the EM Algorithm and Singular Value Decomposition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.10, p.1120-1136, October 2001
Andrea Torsello , Antonio Robles-Kelly , Edwin R. Hancock, Discovering Shape Classes using Tree Edit-Distance and Pairwise Clustering, International Journal of Computer Vision, v.72 n.3, p.259-285, May       2007
Thomas B. Sebastian , Benjamin B. Kimia, Curves vs. skeletons in object recognition, Signal Processing, v.85 n.2, p.247-263, February 2005
Arjan Kuijper , Ole Fogh Olsen , Peter Giblin , Mads Nielsen, Alternative 2D Shape Representations using the Symmetry Set, Journal of Mathematical Imaging and Vision, v.26 n.1-2, p.127-147, November  2006
Ali Shokoufandeh , Diego Macrini , Sven Dickinson , Kaleem Siddiqi , Steven W. Zucker, Indexing Hierarchical Structures Using Graph Spectra, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.7, p.1125-1140, July 2005
Ali Shokoufandeh , Lars Bretzner , Diego Macrini , M. Fatih Demirci , Clas Jnsson , Sven Dickinson, The representation and matching of categorical shape, Computer Vision and Image Understanding, v.103 n.2, p.139-154, August 2006
Stefano Berretti , Alberto Del Bimbo , Enrico Vicario, Efficient Matching and Indexing of Graph Models in Content-Based Retrieval, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.10, p.1089-1105, October 2001
Yakov Keselman , Sven Dickinson, Generic Model Abstraction from Examples, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.7, p.1141-1156, July 2005
Brijnesh J. Jain , Fritz Wysotzki, Central Clustering of Attributed Graphs, Machine Learning, v.56 n.1-3, p.169-207
Marcello Pelillo, Replicator Equations, Maximal Cliques, and Graph Isomorphism, Neural Computation, v.11 n.8, p.1933-1955, November 1999
Michal A. van Wyk , Tariq S. Durrani , Barend J. van Wyk, A RKHS Interpolator-Based Graph Matching Algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.7, p.988-995, July 2002
Marcello Pelillo , Andrea Torsello, Payoff-Monotonic Game Dynamics and the Maximum Clique Problem, Neural Computation, v.18 n.5, p.1215-1258, May 2006
shape recognition;replicator dynamical systems;maximal subtree isomorphisms;shock trees;association graphs;maximal cliques