Distributed Consistent Data Association

arXiv:1609.07015v2 [cs.MA] 25 Oct 2016

Spyridon Leonardos1 , Xiaowei Zhou2 and Kostas Daniilidis3

Abstract— Data association is one of the fundamental problems in multi-sensor systems. Most current techniques rely on
pairwise data associations which can be spurious even after the
employment of outlier rejection schemes. Considering multiple
pairwise associations at once significantly increases accuracy
and leads to consistency. In this work, we propose two fully
decentralized methods for consistent global data association
from pairwise data associations. The first method is a consensus
algorithm on the set of doubly stochastic matrices. The second
method is a decentralization of the spectral method proposed by
Pachauri et al. [28]. We demonstrate the effectiveness of both
methods using theoretical analysis and experimental evaluation.

I. INTRODUCTION
Multi-sensor data association has been a long standing
problem in robotics and computer vision. It refers to the
problem of establishing correspondences between feature
points, regions, or objects observed by different sensors
and serves as the basis for many high-level tasks such as
localization, mapping and planning. Most of the efforts in
previous works have been dedicated to improving the data association by designing new feature detectors, descriptors, and
outlier removal algorithms in a pairwise setting. However,
the problem setting in practice is often multi-way if the data
are collected by a sensor network or a multi-robot system,
and how to establish consistent data association for multiple
sensors and leverage the global reasoning to improve the
association has drawn increasing attention in recent years.
A necessary condition for good data association among
multiple sensors is the cycle consistency meaning that the
composition of associations along a cycle of sensors should
be identity. The cycle consistency is often violated in practice
due to outliers and how to use such a constraint to remove
the false associations has been studied in robotics, computer
vision and graphics. The related work will be discussed
in Section II. While promising empirical and theoretical
results have been reported in previous works, most of them
addressed the problem in a centralized manner and assumed
that the observations and states of all sensors could be
accessed at the same time. This assumption is impractical
in a distributed system where the data is processed on
local sensors with limited computational and communication
resources. In this paper, we aim to develop distributed
algorithms that can efficiently operate on each sensor, requiring only local information and communication with its
1,2,3 The authors are with the Department of Computer and Information Science, University of Pennsylvania Philadelphia, PA 19104, USA

{spyridon,xiaowz,kostas}@seas.upenn.edu
Support by the grants ARL MAST-CTA W911NF-08-2-0004 and ARL
RCTA W911NF-10-2-0016 is gratefully acknowledged.

Fig. 1.

Illustration of consistent data association.

neighbors, and finally producing globally consistent data
association.
Our contributions are the following. 1) We propose a novel
consensus-like algorithm for distributed data association.
2) We propose a decentralized version of the centralized
state-of-art spectral method [28]. 3) We show that both
methods provably converge, do not depend on initialization,
are parameter-free and guarantee global consistency. 4) We
demonstrate the validity of proposed methods through both
theoretical analysis and experimentation with synthetic and
real data.
The rest of this paper is organized as follows. Section II
includes a brief review of prior works. Section III introduces
the reader to notation and preliminaries essential to understanding the main results of this paper. A rigorous problem
formulation is the topic of Section IV. The two proposed
methods are presented in Sections V and VI respectively.
Finally, experimental evaluation is presented in Section VII.
II. RELATED WORK
The cycle consistency has been explored in a variety of
computer vision applications. For example, Zach et al. [37]
studied the problem of multi-view reconstruction and proposed to identify unreliable geometric relations (e.g. relative
poses) between views by measuring the consistencies along a
number of cycles. Nguyen et al. [26] addressed the problem
of finding point-wise maps among a collection of shapes
and proposed to use the cycle consistency to identify the
correctness of maps and replace the incorrect maps with the
compositions of correct ones. Yan et al. [35], [36] considered the multiple graph matching problem and imposed the

cycle consistency by penalizing the inconsistency during the
optimization. Zhou et al. [38] developed a discrete searching
algorithm that maximizes the cycle consistency to improve
the dense optical flow in an image collection. Instead of
iteratively optimizing the pairwise matches, [15], [21], [28]
showed that finding globally consistent associations from
noisy pairwise associations can be formulated as a quadratic
integer program and relaxed into a generalized Rayleigh
problem and solved by the eigenvalue decomposition. More
recently, Huang and Guibas [14] and Chen et al. [6] theoretically proved that the consistent associations could be
exactly recovered from noisy measurements under certain
conditions by convex relaxation and solved the problem by
semidefinite programming. Zhou et al. [39] proposed to solve
the problem by rank minimization and developed a more
efficient algorithm. All of these works addressed problem
in a centralized setting, i.e., all pairwise measurements are
available and optimized jointly.
In the robotics community, numerous approaches for associating elements of two sets have been proposed and
extensively used in single robot Simultaneous Localization
And Mapping (SLAM) settings. These include but are not
limited to Nearest Neighbor (NN) and Maximum Likelihood
(ML) approaches [18], [40], Iterative Closest Point (ICP)
[5], RANSAC [8], Joint Compatibility Branch and Bound
(JCBB) [25], Maximum Common Subgraph (MCS) [3],
Random Finite Sets (RFS) [33]. More recently, multi-robot
localization and mapping algorithms have been developed. In
almost all of them, the data association is addressed either in
a pairwise fashion by directly generalizing data association
techniques from the single robot case [7], [9], [34] or by
considering all associations jointly in a centralized manner
[16]. Closer to our approach is the work by Aragues et al. [1]
which is a decentralized method for finding inconsistencies
based on cycle detection. However, the proposed inconsistency resolution algorithm comes without any optimality or
guarantees.
III. PRELIMINARIES, NOTATION AND
DEFINITIONS
A. Graph Theory
In this subsection, we review some elementary facts from
graph theory. For an in depth analysis, we refer the reader
to standard texts [10], [24]. An undirected graph or simply
a graph is denoted by the pair G = (V, E), where V =
{1, 2, . . . , n} is the set of vertices and E ⊆ [V]2 is the
set of edges, where [V]2 denotes the set of unordered pairs
of elements of V. The neighborhood Ni of the vertex i is
the subset of V defined by Ni = {j ∈ V | {i, j} ∈ E}. A
path is a sequence i0 , i1 , . . . , im of distinct vertices such that
{ik−1 , ik } ∈ E for all k = 1, . . . , m. A graph is connected
if there is a path between any two vertices. Given a graph
G = (V, E), its adjacency matrix is defined by

1, if {i, j} ∈ E
[A(G)]ij =
(1)
0, otherwise

The degree matrix ∆(G) is the diagonal matrix such that
[∆(G)]ii = |Ni |, where |·| denotes the cardinality of a set.
A directed graph or digraph is denoted by the pair G =
(V, E), where E ⊆ V ×V. A weighted digraph G = (V, E, w)
is a graph along with a function w : E → R+ . The adjacency
matrix of a weighted digraph is defined by

w(j, i), if (j, i) ∈ E
[A(G)]ij =
(2)
0,
otherwise
Intuitively, if [A(G)]ij > 0 there is information flow from
vertex j to vertex i. The neighborhood Ni of the vertex i is
the subset of V defined by Ni = {j ∈ V | (j, i) ∈ E}. The
degree matrix ∆(G)
. X
[A(G)]ij
(3)
[∆(G)]ii = din (i) =
j∈Ni

A directed path is a sequence i0 , i1 , . . . , im of distinct vertices such that (ik−1 , ik ) ∈ E for all k = 1, . . . , m. A digraph
is strongly connected if there is a directed path between any
two vertices. A digraph is a rooted out-branching tree if it has
a vertex to which all other vertices are path connected and
does not contain any cycles. A digraph is balanced
if the in. P
degree din (i) and the out-degree dout (i) = (i,j)∈E [A(G)]ji
are equal for all i ∈ V. From this point and on, all graphs
under consideration are assumed to be directed unless stated
otherwise. The graph Laplacian L(G) is defined as
L(G) = ∆(G) − A(G)

(4)

By construction, L(G)1 = 0. A digraph on n vertices
contains a rooted-out branching if and only the rank of its
Laplacian is n − 1. A matrix closely related to the graph
Laplacian is defined by
.
F (G) = (I + ∆(G))−1 (I + A(G))
(5)
B. Stochastic Matrices and Permutations
Stochastic matrices and their properties have been well
studied in the area of distributed dynamical systems [4], [17],
[27] and in probability theory in the context of computing
invariant distributions of Markov chains [2], [4]. A nonnegative square matrix is stochastic if all its row sums are equal
to 1. The spectral radius ρ(A) of a stochastic matrix A is
equal to 1 and it is an eigenvalue of A since A1 = 1. The
existence and the form of the limit limk→∞ Ak depends on
the multiplicity of 1 as an eigenvalue. A nonegative square
matrix A is irreducible if its associated graph [13] is strongly
connected. An irreducible stochastic matrix is primitive if it
has only one eigenvalue of maximum modulus.
A nonnegative square matrix is doubly stochastic matrix
if both its row sums and column sums are equal to 1.
A doubly stochastic matrix is a permutation matrix if its
elements are either 0 or 1. The sets of stochastic matrices
and doubly stochastic matrices are compact convex sets. This
is a rather useful property since it implies closure under
convex combinations. For more details, regarding the theory
of stochastic matrices, we refer the reader to [13].
.
Let [n] = {1, 2, . . . , n} for some positive integer n. A
mapping π : [n] → [n] is a permutation of [n] if it

is bijective. The set of all permutations of [n] forms a
group under composition, termed the symmetric group Sn . A
permutation π ∈ Sn is represented 1 by a n × n permutation
matrix Π defined by

1, if π(j) = i
[Π]ij =
(6)
0, otherwise
or equivalently Πej = eπ(j) , where ej is the jth canonical
basis vector. The simplest choice for a distance on Sn is
given by
.
d(π1 , π2 ) = d(e, π1−1 π2 ) = n − hΠ1 , Π2 i
(7)
.
where hA, Bi = tr(AT B), e is the identity map and Π1 , Π2
are the matrix representations of the permutations π1 and π2
respectively. The distance function defined above is simply
the number of labels assigned differently by permutations π1
and π2 . With a slight abuse of notation, we write Π ∈ Sn
meaning that Π is an n × n permutation matrix.
C. Consensus Algorithms
Consensus algorithms have been extensively studied in the
control community [4], [17], [27]. In its simplest form, a
consensus algorithm is a decentralized protocol in which the
agents, modeled as vertices of a graph, try to reach agreement
by communicating only with their neighbors. More formally,
let xi (t) ∈ R denote the state of agent i at time time t. The,
the simplest consensus protocol is given by
X
xi (t + 1) =
aij xj (t)
(8)
j∈Ni ∪i

P

where aij ≥ 0 and
j aij = 1. A popular consensus
protocol [27], which converges to the average of the initial
values provided that G is balanced, is described by
x(t + 1) = (I − L(G))x(t)

(9)

where x = [x1 , . . . , xn ]T and 0 <  < 1/ maxi [∆(G)]ii .
IV. PROBLEM FORMALIZATION
In this section, we formalize the problem of consistent
data association. We assume there are n sensors observing
m targets. For instance, assume we have a set of n cameras
observing a scene in the world described by a set of m
feature points. Sensors communicate only with a subset of
all sensors. Communication constraints between sensors are
encoded by the sensor graph. The sensor graph is the digraph
G = (V, E) where V = {1, 2, . . . , n} and (i, j) ∈ E if there
is information flow from sensor i to j. The pairwise association πij ∈ Sm is defined as follows: we have that πij (l) = k
if the lth target in jth sensor corresponds to the kth target in
ith sensor. Observe that the pairwise associations πij can be
written as πij = πi ◦ πj−1 , where πi ∈ Sm is the mapping
from the labels of sensor i to some global labels, termed
the “universe of features” in some works [6], [39]. This is
analogous to the absolute position in Euclidean spaces in
1 A representation of a group G on Rn is a map ρ : G → GL(n)
satisfying ρ(g1 g2 ) = ρ(g1 )ρ(g2 ).

S1

S2

S3

1

1

1

2

2

2

3

3

3

1

1

1

2

2

2

3

3

3

Fig. 2. Example with n = 3 sensors S1 , S2 , S3 observing m = 3 targets.
Top: consistent data association. Bottom: inconsistent data association since
π12 ◦ π23 (2) = 3 but π31 (2) = 2.

localization problems. We denote by π
eij ∈ Sm the, possibly
erroneous, estimated pairwise association between sensor i
e ij the corresponding matrix representation.
and j and by Π
.
Moreover, let Πi = ρ(πi ).
Related to the sensor graph is the data association graph
D = (VD , ED , wD ), where VD = V × {1, 2, . . . , m}. There
is an edge from (i, k) to (j, l) if and only if (i, j) ∈ E and
e ij ]kl > 0. The corresponding edge weight is simply equal
[Π
e ij ]kl .
to [Π
First, we need a precise definition of consistency.
Definition 4.1 (Consistency): A set of pairwise associations {e
πij }(i,j)∈E is consistent if
π
eij ◦ π
ejk = π
eik

(10)
{πi }ni=1

for all valid indices i, j, k. A set of labels
is consistent with respect to some consistent pairwise associations
{e
πij }(i,j)∈E , if
π
eij = πi ◦ πj−1 ,

∀(i, j) ∈ E

(11)

Based on the definition of consistency, the problem of
consistent data association is naturally defined as follows.
Definition 4.2 (Consistent data association):
Given pairwise associations {e
πij }(i,j)∈E , find labels
π1 , . . . , πn ∈ Sm , such that
π
eij = πi ◦ πj−1 ,

∀ (i, j) ∈ E

(12)

Remark 1: Under the presence of noise, it might not be
possible to find labels {πi }ni=1 satisfying (12) exactly. Therefore, in practice we are looking for labels {πi }ni=1 satisfying
(12) as much as possible according to some criterion.
V. DISTRIBUTED AVERAGING
In the classic consensus algorithms, each agent updates his
estimate of a collective quantity by taking convex combinations of the estimates of his neighbors. The problem at hand

is different: we do not want all πi ’s to converge to the same
value, rather to converge to a value satisfying consistency.
The first obstacle one encounters is the combinatorial nature
of the problem at hand. Therefore, we relax the domain of
problem and work with doubly stochastic matrices instead
of permutation matrices. This is a natural choice since the
convex hull of the set of m × m permutation matrices is
exactly the set of m × m doubly stochastic matrices.
A. Algorithm
Based on the previous discussion, we propose the following update rule:
X

1
e ij Πj (t)
Πi (t) +
Π
(13)
Πi (t + 1) =
|Ni | + 1
j∈Ni

Let Π = [ΠT1 , . . . , ΠTn ]T . The update rule (13) can be
collectively written as
Π(t + 1) = F (D)Π(t)

(14)

where D is the data association graph and F (D) is defined
in (5). The convergence properties of the update rule (13) depend solely on limk→∞ F (D)k and Π(0). These properties
will be presented in Section V-B.
After the convergence of Protocol (13), we discretize the
solution by solving the assignment problem, formally defined
by
e i , Πi i
maximize hΠ
Πi
(15)
subject to Πi ∈ Sm
e i is the result of Protocol (13). The assignment
where Π
problem can be solved using the Hungarian algorithm [22]
in O(m3 ) time.
Remark 2: The update rule (13) can be seen as a discretetime system with state Πi and control input Ui , i.e.
Πi (t + 1) = Πi (t) + Ui (t)
X

1
e ij Πj (t) − Πi (t)
Ui (t) =
Π
|Ni | + 1

(16)
(17)

j∈Ni

Remark 3: (Intrinsic ambiguity) Let {Πi }ni=1 ∈ (Sm )n
be a set of consistent labels. Then, for any Π0 ∈ Sm ,
{Πi Π0 }ni=1 are consistent as well. This intrinsic ambiguity is
analogous to the ambiguity of the global reference frame in
rotation localization [30]. To remove this ambiguity, one can
fix the label of one sensor, say the first sensor, by modifying
the sensor graph G so that the first sensor has only outgoing
edges resulting in Π1 (t) = Π1 (0) ∈ Sm for all t ≥ 0. This
approach is necessary in the presence of noise and we will
refer to it as Protocol (13) with a distinguished vertex.
Remark 4: (Equivalence to consensus) In the noiseless
e ij = Πi0 Π−1 for some consistent set
case, we can write Π
j0
n
of labels {Πi0 }i=1 ∈ (Sm )n . By defining new variables
.
Π0i = Π−1
i0 Πi , we obtain
X

1
Π0j (t)
(18)
Π0i (t) +
Π0i (t + 1) =
|Ni | + 1
j∈Ni

which is a component-wise Vicsek model [17], [32].

B. Properties
First of all, as the sets of stochastic and doubly stochastic
matrices are convex and thus, closed under convex combinations, we naturally have the following lemma.
e ij and Πi (0) are stochastic then, Πi (t)
Lemma 5.1: If all Π
e ij and Πi (0)
is stochastic for all t ≥ 0. Similarly, if all Π
are doubly stochastic then, Πi (t) is doubly stochastic for all
t ≥ 0.
Next, we show that in the noiseless case Protocol (13)
with a distinguished vertex converges to a consistent solution
under mild coniditions on the sensor graph. To prove this,
we need the following lemma:
Lemma 5.2: Given a digraph G that contains a rooted-out
branching tree, we have that the matrix F (G) as defined
in (5) satisfies: (a) ρ(F (G)) = 1, (b) 1 is an algebraically
simple
√ eigenvalue of F (G) with corresponding eigenvector
1/ n and (c) the limit F (G) exists and is given by
lim F (G)k = 1cT ,

k→∞

(19)

where c ≥ 0 and cT 1 = 1.
A proof of lemma 5.2 can be found in Appendix IX-A. Next,
we present the theorem of convergence of Protocol 13 to a
consistent labeling from arbitrary initialization. A proof of
theorem 5.3 is presented in Appendix IX-B and heavily relies
on lemma 5.2.
Theorem 5.3: If the sensor graph G contains a rootedout branching and the pairwise associations are noiseless,
then the consensus protocol with the distinguished vertex
converges to a set of consistent labels up to a global
permutation, that is
lim Πi (t) = Πi0 Π0

t→∞

(20)

where {Πi0 }ni=1 is a consistent set of labels (with respect
e ij ) and Π0 is an arbitrary permutation. Furthermore, if
to Π
vertex 1 is the distinguished vertex, then Π0 = ΠT10 Π1 (0).
However, in the general case, pairwise associations will
contain noise. Therefore, we should prove convergence without assuming perfect associations. We generalize lemma 5.2
for the case of interest. Consider a digraph D with n vertices
and m < n distinguished vertices that have only outgoing
edges. Assume that for every non-distinguished vertex there
is a (directed) path from at least one distinguished vertex.
Then, the succeeding lemma provides us with the limit of
F (D).
Lemma 5.4: The matrix F (D) as defined in (5) satisfies:
(a) ρ(F (D)) = 1, (b) F (D) has 1 as an eigenvalue with
algebraic and geometric multiplicities equal to the number
of distinguished vertices, (c) it asymptotically converges to
a limit of the form


Im 0
lim F (D)k = e
(21)
k→∞
F21 0
A proof of lemma 5.4 is presented in Appendix IX-C.
An immediate consequence of lemma 5.4 is the following
theorem.
Theorem 5.5: If the sensor graph G contains a rooted-out
branching, then the consensus protocol with a distinguished

vertex asymptotically converges to a solution that depends
e ij }(i,j)∈E and on the initial value of the labels of
only on {Π
the distinguished vertex.
Remark 5: Although Protocol (13) is not guaranteed to
converge to the true solution in the presence of noise, it is
verified experimentally (see Section VII) that for moderate
levels of noise the true solution is still recovered.
VI. DISTRIBUTED ORTHOGONAL ITERATION
In this section, we present a decentralized implementation
of the spectral method proposed by Pachauri et al. [28]. First,
we briefly review the main concept of [28]. Based on the
discussion in Section IV, the multi-sensor data association
can be cast as the following optimization problem:
X
minimize
d(e
πij , πi ◦ πj−1 )
(22)
π1 ,π2 ,...,πn ∈Sm

(i,j)∈E

which is equivalent to
maximize

Π1 ,Π2 ,...,Πn ∈Sm

X

e ij Πj )
tr(ΠTi Π

(23)

(i,j)∈E

In the above formulation, each Πi is a permutation matrix
which makes the problem computationally intractable. However, if the individual constraints are relaxed into a single collective constraint of the form ΠT Π = mIm as proposed in
[28], the relaxed problem becomes computationally tractable
since it becomes a Rayleigh quotient problem:
maximize
Π

tr(ΠT PΠ)

subject to ΠT Π = mIm

(24)

e ij . It is a well-known fact that the solution
where [P]ij = Π
of problem (24) is given by the matrix having as columns
√
the m leading eigenvectors of P scaled by a factor of m.
Numerically, the optimal solution in a centralized setting can
be computed using Orthogonal Iteration [11] (see Algorithm
1). Intuitively, each iteration consists of two main steps:
a power step and an orthogonalization step based on QRdecomposition. For details on the convergence of Orthogonal
Iteration we refer the reader to [11] and references therein.
Algorithm 1 Orthogonal Iteration
Require: Input matrix P, initial Π(0)
1: for t = 0, . . . , N do
2:
Y(t) = PΠ(t)
3:
Q(t)R(t) = Y(t)
4:
Π(t + 1) = Q(t)
5: end for
The Orthogonal Iteration method is not readily decentralizable since the QR-decomposition step requires information
from the entire sensor graph. Nevertheless, as observed
by Kempe and McSherry [20], if Y = [Y1T , . . . , YnT ]T
where each sub-matrix
Pn Yi is available at sensor
Pn i, we obtain
RT R = YT Y = i=1 YiT Yi . If the sum i=1 YiT Yi can
be computed in a decentralized manner, then we can recover
.
R(t) using Cholesky factorization. Let Zi = nYiT Yi and

Pn
.
Z = n1 i=1 Zi = RT R. Based on this observation, if all
sensors know n and solve a consensus problem for computing the average Z = RT R, then the orthogonalization
step can be performed locally using Cholesky decomposition.
denotes the
This is summarized in Algorithm 2 where Z i P
n
estimate of Z by sensor i. Alternatively, the sum i=1 YiT Yi
can be computed using the Push-Sum algorithm [19] as in
[20].
Remark 6: Kempe and McSherry [20] have shown that if
the error in the computation of Ri can be made arbitrarily
small in finite iterations, then Distributed Orthogonal Iteration converges asymptotically an invariant subspace of the
input matrix. A rigorous analysis on the number of iterations
of the inner consensus is the subject of future work.
Algorithm 2 Distributed Orthogonal Iteration
e ij }(i,j)∈E , initial {Πi (0)}i∈V
Require: Input associations {Π
1: for t = 0, . . . , N do
P
e ij Πj (t)
2:
Yi (t) = j∈Ni ∪{i} Π
3:
Estimate Z i (t) by consensus.
4:
Ri (t) = chol(Z i (t))
5:
Πi (t + 1) = Yi (t)Ri (t)−1
6: end for
Remark 7: Due to the nonlinear dependence of Zi on
Yi , dynamic consensus algorithms [29] cannot be readily
incorporated into the current approach.
The solution obtained by the Orthogonal Iteration is optimal up to an arbitrary m×m orthogonal transformation. That
is, if Π? is an optimal solution of (24), then any matrix of the
form Π? Q with Q ∈ O(m) is optimal as well. Finally, the
corrective orthogonal transformation is computed by solving
the following Orthogonal Procrustes [11] problem:
minimize kI − Π1 Qk2F

(25)

Q∈O(m)

It is well known [11] that if Π1 = U SV T is an SVD of Π1 ,
then Q? = V U T . As a final step, we apply the corrective
transformation Q to all remaining Πi , i = 2, . . . , n and then
find a discrete solution by the Hungarian algorithm.
VII. EXPERIMENTS
A. Synthetic data
First, we experiment with synthetic data to validate the
accuracy of proposed methods across different problem
settings. We generate instances with m = 50 targets and
n ∈ {20, 50, 100} sensors. As a performance criterion we use
the accuracy of the obtained labels, which is simply defined
as the percentage of correct labels. We vary the percentage
of erroneous associations in each pairwise association from
10% to 90% to test the robustness of each method against
the presence of outliers. We first experiment with a fully
connected graph, see Fig. 3 (a)-(c), and then we remove half
of the edges, see Fig. 3 (d)-(f). In the case of a fully connected graph, the consensus protocol achieves exact recovery
of the labels for up to approximately 40% of outliers. The

spectral method clearly outperforms the consensus protocol
and is able to achieve exact recovery for up to 80%-90%
of outliers. By reducing either the number of edges in the
sensor graph or the number of sensors, the accuracy of both
methods slightly drops. As expected, the benefit of using
joint matching in accuracy increases with the size of the
network and the number of edges.
B. Real data
First, we experiment with the CMU hotel sequence 2
which consists of 111 frames and the CMU house 3 sequence
which consists of 101 frames. We detect corner features
[12] in the first image that remain visible across the entire
sequence. The ground-truth associations are obtained by
tracking the features across the entire sequence. Specifically,
we used 89 points in the hotel sequence and 55 in the house
sequence. Pairwise matches are computed between an image
and at most 10 previous images and 10 subsequent images
in the sequence, thus the sensor graph is relatively sparse.
Pairwise matches are obtained by extracting SIFT descriptors
[23] and then solving the assignment problem using the
Hungarian algorithm. We used the SIFT implementation
of [31]. The baseline method consists of obtaining labels
by directly matching with the first image in the sequence.
The ground-truth associations are extracted by tracking the
features over the sequence. The results are presented in
Table I. Both methods significantly outperform the baseline
which shows that joint matching can significantly improve
the overall matching performance.
TABLE I
CMU DATASETS R ESULTS

Dataset

Baseline

Spectral

Consensus

Graffiti
Wall
Trees
Leuven
Bikes
UBC

0.544
0.570
0.912
0.962
0.986
0.996

0.639
0.646
0.902
0.972
0.987
0.996

0.647
0.658
0.909
0.979
0.987
0.996

VIII. CONCLUSIONS AND FUTURE WORK
In this paper, we proposed two fully decentralized methods
for the problem of data association in sensor networks.
The first was a computationally inexpensive consensus-like
algorithm and the second a decentralized spectral method.
We presented experimental results in the context of camera
sensor networks. We believe that the results of this work
will find applications in other settings as well. In the future,
we plan on generalizing these algorithms in order to handle
different number of targets in each sensor and time-varying
pairwise associations.
IX. APPENDIX
A. Proof of lemma 5.2
First, we need the following lemma:
Lemma 9.1: Let Li (G) be the matrix obtained from the
Laplacian L(G) by removing the ith row and ith column.
Define Fi (G) analogously. Then,
det(Li (G)) 6= 0 iff

Dataset

Baseline

Spectral

Consensus

House
Hotel

0.716
0.666

0.861
0.872

0.887
0.878

Next, we experiment with the Affine Covariant Regions
Datasets 4 which consist of sequences of 6 images with
significant overlap but with viewpoint variability. We detect
approximately 300 SIFT features [23] in each sequence
that are visible across the entire sequence. The groundtruth associations are extracted using the available groundtruth homographies. The results are presented in Table II.
Both methods significantly outperform the baseline in the
two challenging sequences Graffiti and Wall. However, in
the remaining sequences the input pairwise associations are
already very accurate resulting in only minor improvements
if any. It is worth noting that the spectral method and
the consensus method have similar performance in all real
sequences despite the fact that the spectral method is computationally more expensive. Therefore, in situations where
the computational resources are limited, for instance swarms
of UAVs with on-board cameras, the consensus algorithm
would be preferable.
2

TABLE II
G RAFFITI DATASETS R ESULTS

http://vasc.ri.cmu.edu//idb/html/motion/hotel/
3 http://vasc.ri.cmu.edu//idb/html/motion/house
4 http://www.robots.ox.ac.uk/ vgg/data/data-aff.
˜
html

det(I − Fi (G)) 6= 0

(26)

Proof: By construction L(G) = (I + ∆(G))(I − F (G))
and thus, Li (G) = (I + ∆i (G))(I − Fi (G)) since ∆(G) is
diagonal. Therefore, since det(I + ∆i (G)) > 0, we have that
det(Li (G)) 6= 0 if and only if det(I − Fi (G)) 6= 0.
Now, we are ready to proceed to the proof of lemma 5.2
By Gersǧorin’s discs theorem, we know that the eigenvalues
of F (G) lie in the unit circle and since it is stochastic, that is
F 1 = 1, it can be immediately concluded that ρ(F (G)) = 1.
From Proposition 3.8 page 51 of [24], we have that if
the (directed) graph G contains a rooted-out branching as a
subgraph, then rank L(G) = n − 1. Combining this result
with 9.1, we conclude that the existence of a rooted-out
branching implies that rank(I −F (G)) = n−1. We conclude
that 1 is a simple eigenvalue of F (G).
Let λ1 , λ2 , . . . , λn be an enumeration of the eigenvalues of
F (G) such that λ1 = 1. Moreover, let F (G) = P J(Λ)P −1
be the Jordan decomposition of F (G). From, F (G)P =
P J(Λ), it is easy to see that the the first column of P is in
the span of 1 and thus, limk→∞ F (G)k = 1cT . Moreover,
since F (G)k is stochastic for all positive integers k, it follows
that c ≥ 0 and cT 1 = 1.
B. Proof of theorem 5.3
In the noiseless case, observe that
F (D) = Π0 (F (G) ⊗ Im ) ΠT0 ,

(27)

CS
SP

1

0.4

0.8
accuracy

accuracy

0.6

0.6
0.4
0.2

0.2
0.2

0.4

0.6

0.8

1

0

0.2

Fraction of outliers

CS
SP

0.6

0.8

0

1

CS
SP

0.4

0.6
0.4

1

Fraction of outliers

(d) n = 20
Fig. 3.

0.8

1

CS
SP

0.6
0.4
0.2
0

0
0.8

0.6

0.8

0.2

0.2

0.4

1

accuracy

accuracy

0.6

0.6

0.2

(c) n = 100

0.8

0.4

0

Fraction of outliers

1

0.8
accuracy

0.4

(b) n = 50

1

0.2

0.4

Fraction of outliers

(a) n = 20

0

0.6

0.2

0
0

CS
SP

1

0.8

0.8
accuracy

CS
SP

1

0

0.2

0.4

0.6

0.8

1

Fraction of outliers

(e) n = 50

0

0.2

0.4

0.6

0.8

1

Fraction of outliers

(f) n = 100

Accuracy of consensus protocol (CS) and spectral method (SP) versus percentage of outliers in pairwise data associations.

Fig. 4. Top: initial matches. Blue color corresponds to inlier matches whereas red color corresponds to outlier matches. Bottom: matches after the
consensus algorithm.

where Π0 = diag(Π10 , . . . , Πn0 ), each Πi0 ∈ Sm satisfies
e ij .
Πi0 ΠTj0 = Π
lim F (D)k = Π0 (F (G)∞ ⊗ Im ) ΠT0

k→∞

(28)

since limk→∞ F (G)k exists as we proved earlier. It follows
that F (D)k converges to a limit as well. Any asymptotic solution of the consensus protocol satisfies Π(∞) =
F (D)Π(∞).
for all i ∈ {1, . . . , n} we have Πi (∞) =
P Then,
e ij Πj (∞). Using Π
e ij = Πi0 ΠT , we get
(1/|Ni |) j∈Ni Π
j0

ΠT10 Π1 (∞)


..
(L(G) ⊗ Im ) 
=0
.


ΠTn0 Πn (∞)

Under the assumption that G is contains a rooted-out branching and thus, null(L(G)) = span(1), we obtain Πi (∞) =
Πi0 Q where Q is an arbitrary matrix Q. Moreover, if one
enforces Π1 (t) = Π1 (0), Π1 (0) ∈ Sm , for all t ≥ 0, it
follows that Q = ΠT10 Π1 (0 and Πi (∞) = Πi0 ΠT10 Π1 (0),
that is equal to any valid labels up to a global permutation.

C. Proof of lemma 5.4
Part (a) follows from the fact that F (G) is stochastic.
Without loss of generality, assume that vertices {1, 2, . . . , m}
are the distinguished ones. Then, F (G) takes the form


I
0
F (G) = m
(29)
F21 F22

For all k = 1, 2, . . . we have by a simple induction:


Im
0
k
F (G) =
k
F21,k F22

(30)

k
where F21,1 = F21 , F21,k+1 = F21,k + F22
F21
By the assumption that every non-distinguished vertex is
path-connected to some distinguished vertex, it follows that
for k > 0 large enough, each row of F21,k contains at least
k
one positive entry. Thus, all eigenvalues of F22
lie strictly
k
inside the unit circle and thus, limk→∞ F22 = 0.


R EFERENCES
[1] Rosario Aragues, Eduardo Montijano, and Carlos Sagues. Consistent
data association in multi-robot systems with limited communications.
In Robotics: Science and Systems, pages 97–104, 2011.
[2] Søren Asmussen. Applied probability and queues, volume 51. Springer
Science & Business Media, 2008.
[3] Tim Bailey and Eduardo Nebot. Localisation in large-scale environments. Robotics and autonomous systems, 37(4):261–281, 2001.
[4] Dimitri P Bertsekas and John N Tsitsiklis. Parallel and distributed
computation: numerical methods, volume 23. Prentice hall Englewood
Cliffs, NJ, 1989.
[5] Paul J Besl and Neil D McKay. Method for registration of 3-d shapes.
In Robotics-DL tentative, pages 586–606. International Society for
Optics and Photonics, 1992.
[6] Yuxin Chen, Leonidas Guibas, and Qixing Huang. Near-optimal joint
object matching via convex relaxation. In International Conference
on Machine Learning, 2014.
[7] Alexander Cunningham, Kai M Wurm, Wolfram Burgard, and Frank
Dellaert. Fully distributed scalable smoothing and mapping with robust
multi-robot data association. In Robotics and Automation (ICRA), 2012
IEEE International Conference on, pages 1093–1100. IEEE, 2012.
[8] Martin A Fischler and Robert C Bolles. Random sample consensus:
a paradigm for model fitting with applications to image analysis and
automated cartography. Communications of the ACM, 24(6):381–395,
1981.
[9] Dieter Fox, Jonathan Ko, Kurt Konolige, Benson Limketkai, Dirk
Schulz, and Benjamin Stewart. Distributed multirobot exploration and
mapping. Proceedings of the IEEE, 94(7):1325–1339, 2006.
[10] Chris Godsil and Gordon F Royle. Algebraic graph theory, volume
207. Springer Science & Business Media, 2013.
[11] Gene H Golub and Charles F Van Loan. Matrix computations,
volume 3. JHU Press, 2012.
[12] Chris Harris and Mike Stephens. A combined corner and edge detector.
In Alvey vision conference, volume 15, page 50. Citeseer, 1988.
[13] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge
university press, 2012.
[14] Qi-Xing Huang and Leonidas Guibas. Consistent shape maps via
semidefinite programming. Computer Graphics Forum, 32(5):177–
186, 2013.
[15] Qi-Xing Huang, Guo-Xin Zhang, Lin Gao, Shi-Min Hu, Adrian
Butscher, and Leonidas Guibas. An optimization approach for extracting and encoding consistent maps in a shape collection. ACM
Transactions on Graphics, 31(6):167, 2012.
[16] Vadim Indelman, Erik Nelson, Nathan Michael, and Frank Dellaert.
Multi-robot pose graph localization and data association from unknown initial relative poses via expectation maximization. In 2014
IEEE International Conference on Robotics and Automation (ICRA),
pages 593–600. IEEE, 2014.
[17] Ali Jadbabaie, Jie Lin, and A Stephen Morse. Coordination of groups
of mobile autonomous agents using nearest neighbor rules. IEEE
Transactions on automatic control, 48(6):988–1001, 2003.
[18] Michael Kaess and Frank Dellaert. Covariance recovery from a square
root information matrix for data association. Robotics and autonomous
systems, 57(12):1198–1210, 2009.
[19] David Kempe, Alin Dobra, and Johannes Gehrke. Gossip-based
computation of aggregate information. In Foundations of Computer
Science, 2003. Proceedings. 44th Annual IEEE Symposium on, pages
482–491. IEEE, 2003.
[20] David Kempe and Frank McSherry. A decentralized algorithm for
spectral analysis. In Proceedings of the thirty-sixth annual ACM
symposium on Theory of computing, pages 561–568. ACM, 2004.

[21] Vladimir G Kim, Wilmot Li, Niloy J Mitra, Stephen DiVerdi, and
Thomas A Funkhouser. Exploring collections of 3d models using
fuzzy correspondences. ACM Transactions on Graphics, 31(4):54,
2012.
[22] Harold W Kuhn. The hungarian method for the assignment problem.
Naval research logistics quarterly, 2(1-2):83–97, 1955.
[23] David G Lowe. Distinctive image features from scale-invariant
keypoints. International journal of computer vision, 60(2):91–110,
2004.
[24] Mehran Mesbahi and Magnus Egerstedt. Graph theoretic methods in
multiagent networks. Princeton University Press, 2010.
[25] José Neira and Juan D Tardós. Data association in stochastic mapping
using the joint compatibility test. IEEE Transactions on robotics and
automation, 17(6):890–897, 2001.
[26] Andy Nguyen, Mirela Ben-Chen, Katarzyna Welnicka, Yinyu Ye, and
Leonidas Guibas. An optimization approach to improving collections
of shape maps. Computer Graphics Forum, 30(5):1481–1491, 2011.
[27] Reza Olfati-Saber, J Alex Fax, and Richard M Murray. Consensus
and cooperation in networked multi-agent systems. Proceedings of
the IEEE, 95(1):215–233, 2007.
[28] Deepti Pachauri, Risi Kondor, and Vikas Singh. Solving the multiway matching problem by permutation synchronization. In Advances
in neural information processing systems, pages 1860–1868, 2013.
[29] Demetri P Spanos, Reza Olfati-Saber, and Richard M Murray. Dynamic consensus on mobile networks. In IFAC world congress, pages
1–6. Prague Czech Republic, 2005.
[30] Roberto Tron and Rene Vidal. Distributed 3-d localization of camera
sensor networks from 2-d image measurements. Automatic Control,
IEEE Transactions on, 59(12):3325–3340, 2014.
[31] Andrea Vedaldi and Brian Fulkerson. Vlfeat: An open and portable
library of computer vision algorithms. In Proceedings of the 18th ACM
international conference on Multimedia, pages 1469–1472. ACM,
2010.
[32] Tamás Vicsek, András Czirók, Eshel Ben-Jacob, Inon Cohen, and Ofer
Shochet. Novel type of phase transition in a system of self-driven
particles. Physical review letters, 75(6):1226, 1995.
[33] B-N Vo, Sumeetpal Singh, and Arnaud Doucet. Sequential monte
carlo methods for multitarget filtering with random finite sets. IEEE
Transactions on Aerospace and electronic systems, 41(4):1224–1245,
2005.
[34] Stefan B Williams, Gamini Dissanayake, and Hugh Durrant-Whyte.
Towards multi-vehicle simultaneous localisation and mapping. In
Robotics and Automation, 2002. Proceedings. ICRA’02. IEEE International Conference on, volume 3, pages 2743–2748. IEEE, 2002.
[35] Junchi Yan, Minsu Cho, Hongyuan Zha, Xiaokang Yang, and
Stephen M Chu. Multi-graph matching via affinity optimization with
graduated consistency regularization. IEEE transactions on pattern
analysis and machine intelligence, 38(6):1228–1242, 2016.
[36] Junchi Yan, Jun Wang, Hongyuan Zha, Xiaokang Yang, and Stephen
Chu. Consistency-driven alternating optimization for multigraph
matching: A unified approach. IEEE Transactions on Image Processing, 24(3):994–1009, 2015.
[37] Christopher Zach, Manfred Klopschitz, and Manfred Pollefeys. Disambiguating visual relations using loop constraints. In IEEE Conference on Computer Vision and Pattern Recognition, 2010.
[38] Tinghui Zhou, Yong Jae Lee, X Yu Stella, and Alexei A Efros.
Flowweb: Joint image set alignment by weaving consistent, pixel-wise
correspondences. In IEEE Conference on Computer Vision and Pattern
Recognition (CVPR), 2015.
[39] Xiaowei Zhou, Menglong Zhu, and Kostas Daniilidis. Multi-image
matching via fast alternating minimization. In Proceedings of the
IEEE International Conference on Computer Vision, pages 4032–4040,
2015.
[40] Xun S Zhou and Stergios I Roumeliotis. Multi-robot slam with
unknown initial correspondence: The robot rendezvous case. In 2006
IEEE/RSJ International Conference on Intelligent Robots and Systems,
pages 1785–1792. IEEE, 2006.

