Multi-Image Semantic Matching by Mining Consistent Features

arXiv:1711.07641v1 [] 21 Nov 2017

Qianqian Wang† , Xiaowei Zhou† , Kostas Daniilidis‡
†
‡
Zhejiang University
University of Pennsylvania

Figure 1: Given initial feature candidates in multiple images and their noisy correspondences between image pairs, the proposed method
identifies a sparse set of reliable feature points to establish cyclically and geometrically consistent correspondences across all images.
The figure shows an example of identified features (colored crosses) from 1000 cat head images (only 30 images shown here). The color
indicates correspondence. The last column: initial feature candidates (top) and manually-annotated landmarks provided by the dataset
(bottom), both in the first image. Interestingly, the automatically-identified feature points by the proposed method roughly coincide with
the manually-annotated landmarks.

Abstract

an increasing interest in semantic matching (e.g. [28, 22]),
i.e., establishing semantic correspondences across scenes or
object instances in the same class. Most research on semantic matching focuses on the pairwise case that considers only image pairs. Finding consistent correspondences
across multiple images is important in many situations,
e.g., object-class model reconstruction [21] and automatic
landmark annotation [38]. Multi-image semantic matching
problem is the focus of this work.

This work proposes a multi-image matching method to
estimate semantic correspondences across multiple images.
In contrast to the previous methods that optimize all pairwise correspondences, the proposed method identifies and
matches only a sparse set of reliable features in the image
collection. In this way, the proposed method is able to prune
nonrepeatable features and also highly scalable to handle
thousands of images. We additionally propose a low-rank
constraint to ensure the geometric consistency of feature
correspondences over the whole image collection. Besides
the competitive performance on multi-graph matching and
semantic flow benchmarks, we also demonstrate the applicability of the proposed method to reconstruct object-class
models and discover object-class landmarks from images
without any annotation.

Despite remarkable advances in solving both semantic
matching and multi-image matching problems (see related
work section), the following challenges remain. First, repeatable feature point detection for semantic matching is
an open problem [25, 38]. Previous work bypassed this issue by either using all pixels (dense flow) [28] or randomly
sampled points [41], resulting in numerous nonrepeatable
features that have no real correspondences in other images
and should be explicitly handled. Second, previous multiimage matching methods (e.g. [35, 54]) mainly optimize the
cycle consistency of correspondences and seldom consider
the geometric consistency simultaneously. While there have
been effective ways to enforce geometric constraints in the
pairwise setting (e.g. RANSAC [15] and graph matching
[26]), few solutions exist for the multi-image case. Finally,
the existing multi-image matching methods are computa-

1. Introduction
Computing feature correspondences across images is a
fundamental problem in computer vision. Low-level geometric features (e.g. SIFT [30]) are successful for matching images of the same scene. Recently, there has been
1

tionally expensive, which could hardly process hundreds of
images. Analyzing large datasets requires more scalable algorithms.
In most situations one only needs the correspondences
of a sparse set of highly repeatable semantic features which
are cyclically and geometrically consistent across images.
Dense correspondences could be achieved by interpolation.
Therefore, in contrast to the previous multi-image matching methods that optimize all pairwise correspondences, we
formulate the problem as a feature selection and labeling
problem: Starting from fussy pairwise correspondences, we
aim to select a sparse set of feature points from the initial
set of candidates in each image, and establish their correspondences across images by assigning labels to them.
The selection and labeling are accomplished by optimizing both cycle consistency and geometric consistency of selected features. Formulating the problem in this way allows
us to 1) explicitly deal with nonrepeatable points in the initial feature sets and 2) dramatically decrease the number
of variables, resulting in a scalable algorithm that is able
to jointly analyze thousands of images. Finally, inspired
by classic results on factorization-based structure from motion [39], we propose a low-rank constraint that enforces the
geometric consistency for matching multiple images and is
very efficient to solve in optimization. Figure 1 gives an
example illustrating our problem and proposed method.
The main contributions of this work are summarized as
follows:

low-level geometric feature detectors (e.g. corner and covariant regions [32]) and descriptors (e.g. SIFT [30], SURF
[1] and HoG [17]). The geometric consistency is imposed
by either using RANSAC [15] as a postprocessing step or
solving a graph matching problem that minimizes the geometric distortion between images (e.g. [26, 8]). Many recent works attempt to find semantic correspondences across
different scenes (e.g. [28, 37]). Hierarchical matching
[22] and region-based [16] strategies have been proposed
to make use of high-level semantics in images.
Learning of detectors and descriptors: Recent results
(e.g. [14, 29]) show that the CNN features extracted from
neural networks are very effective in matching and outperform handcrafted features even if the CNNs are not trained
for matching. Supervised learning has been used to explicitly learn descriptors. The supervision is from manually annotated correspondences [9], images transformations [34], and additional cues (e.g. silhouettes [20]) and
data (e.g. CAD models [52]). Meanwhile, there are few
efforts towards learning feature detectors that are repeatable and covariant to transformations [49, 25, 38]. The
proposed method can be viewed as an unsupervised approach to harvesting reliable features and consistent correspondences from image collections, which may provide
training data for detector and descriptor learning.
Multi-image matching: The proposed method is technically related to the joint matching methods (e.g. [23, 19,
35]). Most existing methods aim to make use of the cycle consistency to improve the pairwise correspondences.
Various approaches have been proposed such as unclosed
cycle elimination [50, 33], constrained local optimization
[46, 45, 47, 44, 53], spectral relaxation [23, 18, 35] and
convex relaxation [18, 6, 54]. The proposed method differs from them as we aim to identify the most consistent
features instead of optimizing all pairwise correspondences,
which makes the proposed algorithm more scalable for exploring large datasets. In addition, we introduce a lowrank constraint to optimize the geometric consistency of
selected features. The matrix decomposition method for
multi-graph matching proposed in [48] imposes the lowrank constraint on graph edges. In this work the constraint
is directly imposed on feature locations resulting in more efficient optimization. The recent work [40] proposes an efficient method to discover clusters of discriminative features
for matching, but no geometric constraint is considered.

• We propose a novel approach to solving multi-image
semantic matching problem as a feature selection and
labeling problem. The proposed algorithm is able to
discover consistent features in an image collection and
is scalable to handle thousands of images.
• We introduce a novel low-rank constraint for multiimage matching that allows the proposed algorithm to
optimize cycle consistency and geometric consistency
simultaneously.
• We demonstrate competitive performance of the proposed method on standard benchmarks. We show its
applications with two examples: 1) reconstruct 3D
object-class models from images of different instances
without using any manual annotations. 2) match 1000
cat head images and interestingly find that the automatically selected feature points represent very discriminative landmarks on eyes, ears and mouths, which
demonstrates the potential applicability of the proposed method for automatic landmark annotation.

3. Preliminaries and notation
3.1. Pairwise matching
Given n images to match and pi feature points in each
image i, the pairwise feature correspondences for each image pair (i, j) can be represented by a partial permutation matrix Pij ∈ {0, 1}pi ×pj , which satisfies the doubly

2. Related work
Image matching: In classical image matching, sparse feature correspondences between images are estimated using
2

column vector of X is the label of the corresponding features. The image features with identical label match each
other. To accommodate all feature points, previous work
usually defines a sufficiently large u [6, 54].
However, not all features that appear in the image collection are desirable for matching. Particularly, in semantic
matching most of the randomly or uniformly sampled features are nonrepeatable across a set of images and should
be excluded during matching. Inspired by this, we select
the most repeatable image features and map them to a more
compact feature space containing only k elements, where k
is a predefined small value meaning the number of selected
features in each image.
Suppose the correspondences between the feature points
in image i and the selected feature space is represented by
Xi ∈ {0, 1}pi ×k . Each Xi is a partial permutation matrix
with a small number of columns which satisfies

stochastic constraints:
0 ≤ Pij 1 ≤ 1, 0 ≤ PijT 1 ≤ 1

(1)

Pij can be estimated by maximizing the inner product
between itself and the feature similarities subject to the constraints in (1). This is a linear assignment problem, which
is well-studied and can be solved by the Hungarian algorithm. Finding Pij can also be formulated as a graph matching problem, which can be cast as a quadratic assignment
problem (QAP). Specifically, an objective function encoding both local compatibilities (feature similarity) and structural compatibilities (spatial rigidity) is maximized in order
to find the assignment. Although QAP is NP-hard, many
effective algorithms have been proposed to solve it approximately, e.g., [2, 8, 26]. We will use the outputs of linear
matching or graph matching, denoted by Wij ∈ Rpi ×pj , as
our inputs.

0 ≤ Xi 1 ≤ 1, XiT 1 = 1

3.2. cycle consistency
Recent work [6, 35, 45] proposes to use cycle consistency as a constraint to match multiple images. The correspondence between all pairs of images is cyclically consistent if any triplet of images (i, j, z) in the collection satisfies
Pij = Piz Pzj

The sum of each column in Xi equals to 1, meaning that every element in the selected feature space should correspond
to a feature point in each image. On the contrary, the sum of
a row could be zero, meaning that the corresponding feature
point is not selected.
The set of Xi for i = 1, 2, · · · , n is what we need to estimate. Xi XjT gives the pairwise correspondences between
selected features in image i and j, which must be cyclically
consistent by construction as explained in Section 3.2. As
we attempt to identify the discriminative features that are
supposed to produce more cyclically consistent correspondences in the initial pairwise matching, we minimize the
discrepancy between the initial pairwise matching results
and the constructed ones to estimate X:

(2)

The cycle consistency can be described more concisely
by introducing a virtual “universe” which is defined as the
set of unique features that appear in the image collection
[35, 18]. Each point in the universe must be observed by at
least one image and matched to corresponding image points.
Suppose the underlying correspondence between image i
and the universe is denoted by partial permutation matrix
Xi ∈ {0, 1}pi ×u , where u is the size of the universe and
u ≥ pi for all i. Then the pairwise correspondence Pij can
be represented as Xi XjT .
If the permutation matrices are concatenated as


 
P11 P12 . . . P1n
X1
 P21 P22 . . . P2n 
 X2 


 
P = .
..
..  , X =  ..  , (3)
..
 ..

 . 
.
.
.
Pn1

Pn2

...

Pnn

(4)

min
X

s.t.

1
kW − XX T k2F
4
Xi ∈ Ppi ×k , 1 ≤ i ≤ n

(5)

where P denotes the set of partial permutation matrices and
W ∈ Rm×m is the collection of Wij . By solving (5), the
most repeatable features in the image collection will be selected and matched in a consistent way.

Xn

4.2. Geometric constraint

it has been shown that the set {Pij |∀i, j} are cyclically consistent if and only if P can be factorized as XX T [26, 18].

Suppose we have tracked k features over n frames in a
scene. We use Mi ∈ R2×k to denote the coordinates of
the k ordered features of frame i, and concatenate all Mi
as rows in a matrix M ∈ R2n×k with each column per
feature. M is known as the measurement matrix in structure
from motion [39]. It can be shown that under orthographic
projection, M is of rank 4.
In our problem, we represent the coordinates of all feature candidates in image i by Ci ∈ R2×pi . Then, the coor-

4. Proposed methods
4.1. Matching by labeling
Recall that X ∈ {0, 1}m×u is the map from image features to the universe, where m and u denote the total number
of local features in the image collection and the size of universe, respectively. Another interpretation of X is that each
3

dinates of selected feature points in image i are given by
M̃i = Ci Xi

by replacing X in the first term with an auxiliary variable
Y ∈ Rm×k and rewrite the optimization as:

(6)

n

λX
1
kW − Y Y T k2F +
kCi Xi − Zi k2F
X,Y ,Z 4
2 i=1
ρ
+ kX − Y k2
2
(10)
s.t. Xi ∈ Ppi ×k , 1 ≤ i ≤ n

2×k

min

where M̃i ∈ R
stores the coordinates of selected feature points that are aligned in the same order as the selected
feature space. Similarly, we could concatenate all M̃i as
rows in a matrix M̃ ∈ R2n×k :


C1 X1


(7)
M̃ =  ... 

Y ∈C
rank(Z) ≤ r

Cn Xn
where C denotes the set of matrices satisfying the constraints as follows:

If feature points are correctly selected and labeled, M̃
will become a measurement matrix of rank 4 under orthographic projection. Even though the scene is non-rigid, M̃
can still be approximated by a low-rank matrix [3] . This
conclusion can be effectively utilized to better estimate X.
Suppose the ground-truth rank of M̃ is no larger than r.
Then, the following term can be minimized to impose geometric consistency on selected feature points:

0 ≤ Y ≤ 1, 0 ≤ Yi 1 ≤ 1, YiT 1 = 1, 1 ≤ i ≤ n

and ρ is a parameter controlling the degree of similarity between X and Y . When ρ approaches infinity, the problem
in (10) is equivalent to the original one (9).
The motivation for rewriting the problem as (10) is that
each subproblem in the block coordinate descent will be
much easier to solve. We alternately update Y , X, Z in
the following manner.
Y is updated via projected gradient descent [36, 31]:

n

fgeo =

1X
1
kM̃ − Zk2F =
kCi Xi − Zi k2F
2
2 i=1

(8)

where Z ∈ R2n×k is an auxiliary variable whose rank is
no larger than r, and Zi ∈ R2×k denotes the 2i − 1-th and
2i-th rows of Z.

Y ← ΠC [Y − η(Y Y T Y − W Y + ρ(X − Y ))] (12)
where ΠC denotes projection onto C and η > 0 is the stepsize. We update Y until convergence before updating X
and Z.
Each Xi is updated via the Hungarian algorithm, whose
cost matrix is constructed as

4.3. Formulation
Combining the cycle consistency and geometric consistency discussed in Section 4.1 and 4.2, we obtain the final
optimization problem:

Hi = D(Ci , Zi ) − ρYi ,

n

min

X,Z

s.t.

1
λX
kW − XX T k2F +
kCi Xi − Zi k2F
4
2 i=1
Xi ∈ Ppi ×k , 1 ≤ i ≤ n

(11)

(13)

where D(Ci , Zi ) ∈ Rpi ×k denotes the euclidean distance
between each pair of observations in Ci and Zi .
Z is updated via singular value decomposition (SVD):

(9)

rank(Z) ≤ r

Z = U Σ̃V T ,

where λ controls the weight of the geometric constraint.

(14)

where U and V are the left and right singular vectors of M̃
respectively, and Σ̃ is a diagonal matrix with the diagonal
elements corresponding to the r largest singular values of
M̃ .
For better convergence, we use an increasing sequence
of ρ to enforce the geometric constraint gradually. For each
value of ρ, we update the variables alternately until the objective in (10) does not decrease. As each update never increases the objective, the local convergence is guaranteed.
In our experiment, we set the sequence of ρ as (1, 10, 100),
λ as 0.01 and r as 4 empirically.
As the optimization is nonconvex and involves both continuous and discrete variables, a reliable initialization is

4.4. Optimization
We propose to solve the optimization problem in (9) by
block coordinate descent, i.e., alternately updating one variable while fixing the others.
We attempted to relax the integer constraint of (9) and
treated X as a real matrix X ∈ [0, 1]m×k , which is a common practice in solving quadratic assignment problems.
However, we observed that, if the integer constraint on X
is relaxed, the effect of the geometric constraint is negligible as the system Ci Xi = Zi is ill-posed for arbitrary Zi .
Therefore, we keep the integer constraint on X. To make
the optimization tractable, we decouple the two terms in (9)
4

Dataset
Input [35] [6] [54] Ours− Ours Ours+
Hotel
0.57 0.53 0.64 0.58 0.63 0.90
1
House
0.74 0.74 0.79 0.75 0.79 0.93
1
Car
0.48 0.55 0.66 0.65 0.72 0.75
1
Duck
0.43 0.59 0.56 0.56 0.63 0.77 0.88
Face
0.86 0.92 0.93 0.94 0.95 0.95
1
Motorbike 0.30 0.25 0.28 0.27 0.40 0.73
1
Winebottle 0.52 0.64 0.71 0.72 0.73 0.82
1

necessary. We first initialize Y by ignoring the geometric
constraint and solve
min
Y

s.t.

1
kW − Y Y T k2F
4
Y ∈C

(15)

using the projected gradient descent as (12) with ρ = 0.
After initializing Y , X can be initialized by discretizing
Y.

Table 1: The recall rates on CMU datasets and WILLOW Object
Class dataset. The proposed method is compared with spectral
method [35], MatchLift [6] and MatchALS [54]. Ours− represents
the matching accuracy when the geometric constraint is ignored.
Ours+ represents the matching accuracy when graph matching is
applied to obtain the initial pairwise correspondences.

5. Experiments
5.1. Multi-graph matching
We first validate the effectiveness of the proposed algorithm in the setting of multi-graph matching, where the feature locations are annotated but their correspondences need
to be estimated. The matching accuracy is evaluated by the
recall and the precision. The recall is defined as the number
of true correspondences found by the algorithm divided by
the number of ground-truth correspondences. The precision
is defined as the number of true correspondences divided
by the total number of correspondences found by the algorithm.
The CMU datasets and WILLOW Object Class dataset
are used for evaluation. The CMU datasets contain the
hotel sequence (111 frames) and the house sequence (101
frames). We adopt SIFT descriptors [30] to 30 feature
point annotations provided by [4] in each frame. The WILLOW Object Class dataset [7] provides images of five object classes (Car, Duck, Motorbike, Face, Winebottle) and
10 annotated points corresponding to several discriminative parts of each class. Each class contains at least 40
images with different instances. As the object appearance in each class varies greatly, geometric descriptors like
SIFT can hardly work. Instead, the deep features extracted
from pretrained convolutional neural networks (CNNs) are
adopted, which have proven to be effective in previous work
[29]. Specifically, each image is fed through the AlexNet
[24] (pretrained on ImageNet [11]) and the feature map responses of Conv4 and Conv5 corresponding to each landmark is extracted as its descriptor. Then, for both datasets,
the initial pairwise correspondences are obtained from linear matching and fed into the proposed algorithm. Three
alternative methods whose codes are publicly available are
used as baselines: the spectral method [35], MatchLift [6]
and MatchALS [54]. For all methods, the size of universe
is set as the number of annotations in each image.
The recall rates are reported in Table 1, which shows
that the proposed method outperforms other methods on all
datasets. Table 1 also demonstrates another two cases: 1)
if graph matching is leveraged to improve the initial pairwise correspondences, the matching accuracy of the proposed method can achieve 100% on all datasets except the

Figure 2: The comparison of matching results with and without
geometric constraint are shown in bottom and top rows, respectively. The true matches and false matches are shown in blue and
red, respectively.

hotel

house

Figure 3: The matches with outliers on the CMU hotel/house
datasets. The true matches and false matches are shown in green
and red, respectively. The top and bottom rows correspond to the
results of pairwise matching and our joint matching method, respectively. Besides 30 annotated feature points, we introduce 30
randomly sampled outliers in each frame. 30 features are selected
and matched using our method.

duck. 2) If geometric consistency is ignored, the matching accuracy reduces significantly. Two pairs of examples
are visualized in Figure 2 which shows that geometrically
distorted matches can be corrected after enforcing the geometric consistency.
The proposed method can automatically select reliable
5

Methods
Ours
LOM [16]
DeepFlow [37]
GMK [13]
SIFT Flow [28]
DSP [22]
Zhou et al. [52]

car(S)
0.88
0.86
0.33
0.48
0.54
0.46
0.77

car(G)
0.57
0.60
0.13
0.25
0.37
0.30
0.34

car(M)
0.37
0.53
0.22
0.34
0.36
0.32
0.52

duc(S)
0.71
0.64
0.20
0.27
0.32
0.25
0.42

mot(S)
0.47
0.49
0.20
0.31
0.41
0.31
0.34

mot(G)
0.27
0.25
0.08
0.12
0.20
0.15
0.19

mot(M)
0.30
0.29
0.13
0.15
0.23
0.14
0.20

win(w/o C)
0.93
0.91
0.46
0.41
0.83
0.85
0.78

win(w/C)
0.60
0.37
0.08
0.17
0.16
0.25
0.19

win(M)
0.77
0.65
0.18
0.18
0.33
0.64
0.38

Avg.
0.59
0.56
0.20
0.27
0.38
0.37
0.41

Table 2: PCK (α = 0.1) comparison for dense flow field on the PF-WILLOW dataset (SS w/HOG).

Source image

Target image

Proposal Flow

Optimized

Figure 4: Examples of dense flow. Source images are warped to the target images using the dense correspondences estimated by Proposal
Flow [16] and optimized by the proposed method.

features for matching. Figure 3 gives an example where
randomly sampled feature points are added in each frame
of the CMU datasets as outliers. It is shown that the outliers can effectively be pruned and moreover, the correspondences between the selected feature points are improved.

benchmark for evaluating semantic flow techniques. PFWILLOW dataset is generated from the WILLOW Object
Class dataset, which is split into 10 sub-classes according
to viewpoint or background clutter. They are car (S), (G),
(M), duck (S), motorbike (S), (G), (M), winebottle (w/oC),
(w/C), (M), where (S) and (G) represent side and general
viewpoints, respectively, (C) denotes background clutter,
and (M) denotes mixed viewpoints. Each sub-class includes
10 images of different object instances.
The percentage of correct keypoints (PCK) is used as
the evaluation metric [16]. It evaluates the percentage of
correctly located keypoints when transferring the annotated
keypoints from an image to another image using the estimated flow. Ground-truth feature points are deemed to be
correctly predicted if they lie within αmax(h, w) pixels of
the predicted points for α in [0, 1], where h and w are the
height and width of the object bounding box, respectively.

5.2. Dense semantic matching
In this section, we show the application of the proposed
method by combining it with region based semantic flow
methods, for example, proposal flow [16]. In the proposal
flow method, the correspondences of region proposals between images are estimated and then transformed into a
dense flow field. For a collection of images, we apply the
proposed method on top of proposal flow to improve the
estimated pairwise correspondences of proposals, thus improving the performance of dense flow.
We experiment with the PF-WILLOW dataset [16], a
6

1

For proposal flow, the select search (SS) [42] is used as proposal generator, HOG [10] as feature descriptors, and local
offset matching (LOM) [16] as geometric matching strategy. 500 proposals are extracted and used for matching and
generating dense flow field in each image. For our method,
the number of selected features is set as 30 and the center
of each region proposal is regarded as its coordinates in our
geometric constraint.
Our method is compared to proposal flow and other
methods on the PF-WILLOW dataset. The result in Table 2
shows that our method outperforms the original proposal
flow on all classes except car (G), car (M) and mot (S).
The decrease of performance on these classes is due to the
very low initial matching accuracy between active proposals, which may lead to the selection of proposals in background. A qualitative example is given in Figure 4.

Precision

0.8
0.6
Pairwise
Ours-50kpts
Ours-100kpts
Ours-200kpts
Ours-300kpts

0.4
0.2
0

0

0.1

0.2

0.3

Threshold
Figure 5: The precision for different numbers of selected features
on the FG3DCar dataset.

5.3. Object-class model reconstruction
Matching images of different object instances is a main
challenge in reconstructing object-class models from images. Some previous works [43, 5, 21] rely on annotated
keypoints in images. The recent work [54] requires no keypoint annotation but object masks to remove background
and ground-truth viewpoints for reconstruction. We show
that the proposed method can produce consistent correspondences for reconstruction without using any manual annotation. We demonstrate with the FG3DCar dataset [27], try
to match all left-view sedan images (37 in total), and reconstruct a 3D model. In addition, we collect another dataset
containing 30 images of different motorbikes with similar
views for matching and reconstruction.
Similar to [54], we uniformly sample feature candidates
on image edges detected by the structured forests [12]. Unlike [54], we don’t need object masks thanks to the capability of the proposed method to prune nonrepeatable features
in the background. On average, ∼ 550 feature candidates
are obtained for each image. The deep features described
in 5.1 are used as descriptors and the graph matching solver
RRWM [8] is adopted for initial pairwise matching.
To illustrate the effect of selection, we vary the number
of selected features and compare the precisions of recovered correspondences in Figure 5. It is shown that the proposed method achieves obvious improvements compared to
the original pairwise matching, whose precision is low in
the presence of background clutter. Moreover, the fewer the
features we select, the higher the precision will be. This
justifies the use of selection, which prunes nonrepeatable
features such as the ones in the background. Only the reliable feature points near the object are selected and matched
consistently. An example is visualized in Figure 6.
For reconstruction, we simply run affine reconstruction
through the factorization method [39]. The selected feature
points, correspondences and reconstructions are visualized

Figure 6: The matches between two sedan images. The true
matches and false matches are shown in blue and red, respectively. The top and bottom rows correspond to the results of pairwise matching and the proposed method respectively. The feature
points are automatically sampled and 100 of them in each image
are selected and matched by the proposed method.

in Figure 7. Clearly, most of the selected feature points are
located on objects and the corresponding parts are correctly
matched despite the large variety in object appearances and
viewpoints. In spite of some noises and missing points, we
can see the structures of sedan and motorbike from the reconstructions. It is believed that more sophisticated reconstruction techniques can be adopted to obtain better reconstructions. Quantitatively, we evaluate the estimated relative rotations between all pairs of images with the ground
truth provided by the FG3DCar dataset. The mean error in
geodesic distance is 18.5◦ . To our knowledge, no previous
result exists for unsupervised relative pose estimation between different instances.

5.4. Automatic landmark annotation
We apply the proposed algorithm to the first 1000 images
from the cat head dataset [51]. Similar to the previous experiment, the candidate features are sampled from detected
edges in images, yielding ∼ 43 candidates per image on av7

Figure 7: Matching sedans and motorbikes. Only four images are selected and shown for each image set. Note that the instances are
different. All the feature points are automatically sampled and selected by the proposed method. The markers with the same color indicate
the matched points. The 3D reconstruction is rendered with the colors in the first image and visualized in two viewpoints.

gardless of pairwise matching, which can hardly be solved
by the previous multi-image matching algorithms.

erage. We set the number of selected features to be 10. The
results are shown in Figure 1. As the figure shows, while
initial candidates distribute randomly over the whole image
including the background, the selected features are all on
the objects with correct correspondences established across
very different instances with a variety of appearances and
poses. More interestingly, the automatically selected features roughly coincide with human annotations provided by
the dataset, representing the discriminative parts of cat such
as ears, eyes and mouth. This demonstrates the potential
of the proposed method for automatic landmark annotation,
which imitates humans’ annotation process: we compare a
collection of images and find a set of parts that are invariant
in appearance and geometry across images.

6. Conclusion
We presented a novel method that solved the problem of
semantic matching across multiple images as a feature selection and labeling problem. The proposed method could
establish reliable feature correspondences among a collection of images which satisfy both cycle consistency and geometric consistency. Experiments showed that the proposed
method outperformed the previous multi-image matching
methods while being highly scalable to match thousands
of images. Several applications were demonstrated: improving dense flow estimation on top of the proposal flow
method, reconstructing object-class models without using
any manual annotation, and automatically annotating image
landmarks in 1000 cat head images.

5.5. Computational complexity
The bottleneck restricting the scalability of the proposed
method is the matrix multiplication when updating Y , while
the other update steps only involve much smaller matrices.
In (12), the dominant part is Y Y T Y which takes O(mk 2 )
flops for each update, where m and k are the total number of
features in all images and the number of selected features in
each image, respectively. As a comparison, the complexity
of MatchALS [54] is O(m2 k). As k is much smaller than
m, the proposed method is much more scalable. For example, m ≈ 43, 000 and k = 10 in the cat head experiment in
Section 5.4. We implement the proposed algorithm in Matlab on a PC with an Intel i7 3.4GHz CPU and 16G RAM.
The CPU time for the cat head experiment is ∼ 650s re-

References
[1] H. Bay, T. Tuytelaars, and L. Van Gool. Surf: speeded up
robust features. In ECCV, 2006. 2
[2] A. C. Berg, T. L. Berg, and J. Malik. Shape matching and
object recognition using low distortion correspondences. In
CVPR, 2005. 3
[3] C. Bregler, A. Hertzmann, and H. Biermann. Recovering
non-rigid 3d shape from image streams. In CVPR, 2000. 4
[4] T. S. Caetano, J. J. McAuley, L. Cheng, Q. V. Le, and A. J.
Smola. Learning graph matching. IEEE transactions on

8

[5]

[6]

[7]
[8]
[9]
[10]
[11]

[12]
[13]
[14]

[15]

[16]

[17]
[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25] K. Lenc and A. Vedaldi. Learning covariant feature detectors. In ECCV Workshops, 2016. 1, 2
[26] M. Leordeanu and M. Hebert. A spectral technique for correspondence problems using pairwise constraints. In ICCV,
2005. 1, 2, 3
[27] Y.-L. Lin, V. I. Morariu, W. Hsu, and L. S. Davis. Jointly
optimizing 3d model fitting and fine-grained classification.
In ECCV, 2014. 7
[28] C. Liu, J. Yuen, and A. Torralba. Sift flow: Dense correspondence across scenes and its applications. IEEE transactions
on pattern analysis and machine intelligence, 33(5):978–
994, 2011. 1, 2, 6
[29] J. L. Long, N. Zhang, and T. Darrell. Do convnets learn
correspondence? In NIPS, 2014. 2, 5
[30] D. G. Lowe. Distinctive image features from scale-invariant
keypoints.
International Journal of Computer Vision,
60(2):91–110, 2004. 1, 2, 5
[31] Y. Lu, K. Huang, and C.-L. Liu. A fast projected fixed-point
algorithm for large graph matching. Pattern Recognition,
60:971–982, 2016. 4
[32] K. Mikolajczyk, T. Tuytelaars, C. Schmid, A. Zisserman,
J. Matas, F. Schaffalitzky, T. Kadir, and L. Van Gool. A
comparison of affine region detectors. International Journal
of Computer Vision, 65(1-2):43–72, 2005. 2
[33] A. Nguyen, M. Ben-Chen, K. Welnicka, Y. Ye, and
L. Guibas. An optimization approach to improving collections of shape maps.
Computer Graphics Forum,
30(5):1481–1491, 2011. 2
[34] D. Novotny, D. Larlus, and A. Vedaldi. Anchornet: A weakly
supervised network to learn geometry-sensitive features for
semantic matching. In CVPR, 2017. 2
[35] D. Pachauri, R. Kondor, and V. Singh. Solving the multi-way
matching problem by permutation synchronization. In NIPS,
2013. 1, 2, 3, 5
[36] N. Parikh and S. Boyd. Proximal algorithms. Foundations
and Trends in Optimization, 1(3):123–231, 2013. 4
[37] J. Revaud, P. Weinzaepfel, Z. Harchaoui, and C. Schmid.
Deepmatching: Hierarchical deformable dense matching. International Journal of Computer Vision, 120(3):300–323,
2016. 2, 6
[38] J. Thewlis, H. Bilen, and A. Vedaldi. Unsupervised learning
of object landmarks by factorized spatial embeddings. In
ICCV, 2017. 1, 2
[39] C. Tomasi and T. Kanade. Shape and motion from image
streams under orthography: a factorization method. International Journal of Computer Vision, 9(2):137–154, 1992. 2,
3, 7
[40] R. Tron, X. Zhou, C. Esteves, and K. Daniilidis. Fast multiimage matching via density-based clustering. In CVPR,
2017. 2
[41] N. Ufer and B. Ommer. Deep semantic feature matching. In
CVPR, 2017. 1
[42] J. R. Uijlings, K. E. Van De Sande, T. Gevers, and A. W.
Smeulders. Selective search for object recognition. International journal of computer vision, 104(2):154–171, 2013.
7

pattern analysis and machine intelligence, 31(6):1048–1058,
2009. 5
J. Carreira, A. Kar, S. Tulsiani, and J. Malik. Virtual
view networks for object reconstruction. arXiv preprint
arXiv:1411.6091, 2014. 7
Y. Chen, L. Guibas, and Q. Huang. Near-optimal joint object
matching via convex relaxation. In International Conference
on Machine Learning, 2014. 2, 3, 5
M. Cho, K. Alahari, and J. Ponce. Learning graphs to match.
In ICCV, 2013. 5
M. Cho, J. Lee, and K. M. Lee. Reweighted random walks
for graph matching. In ECCV, 2010. 2, 3, 7
C. B. Choy, J. Gwak, S. Savarese, and M. Chandraker. Universal correspondence network. In NIPS, 2016. 2
N. Dalal and B. Triggs. Histograms of oriented gradients for
human detection. In CVPR, 2005. 7
J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. FeiFei. Imagenet: A large-scale hierarchical image database. In
CVPR, 2009. 5
P. Dollár and C. L. Zitnick. Structured forests for fast edge
detection. In ICCV, 2013. 7
O. Duchenne, A. Joulin, and J. Ponce. A graph-matching
kernel for object categorization. In ICCV, 2011. 6
P. Fischer, A. Dosovitskiy, and T. Brox. Descriptor matching with convolutional neural networks: a comparison to sift.
arXiv preprint arXiv:1405.5769, 2014. 2
M. A. Fischler and R. 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. 1, 2
B. Ham, M. Cho, C. Schmid, and J. Ponce. Proposal
flow: Semantic correspondences from object proposals. In
arXiv:1703.07144, 2017. 2, 6, 7
B. K. Horn and B. G. Schunck. Determining optical flow.
Artificial intelligence, 17(1-3):185–203, 1981. 2
Q.-X. Huang and L. Guibas. Consistent shape maps via
semidefinite programming. Computer Graphics Forum,
32(5):177–186, 2013. 2, 3
Q.-X. Huang, G.-X. Zhang, L. Gao, S.-M. Hu, A. Butscher,
and L. Guibas. An optimization approach for extracting and
encoding consistent maps in a shape collection. ACM Transactions on Graphics, 31(6):167, 2012. 2
A. Kanazawa, D. W. Jacobs, and M. Chandraker. Warpnet:
Weakly supervised matching for single-view reconstruction.
In CVPR, 2016. 2
A. Kar, S. Tulsiani, J. Carreira, and J. Malik. Categoryspecific object reconstruction from a single image. In CVPR,
pages 1966–1974, 2015. 1, 7
J. Kim, C. Liu, F. Sha, and K. Grauman. Deformable spatial
pyramid matching for fast dense correspondences. In CVPR,
2013. 1, 2, 6
V. G. Kim, W. Li, N. J. Mitra, S. DiVerdi, and T. A.
Funkhouser. Exploring collections of 3d models using fuzzy
correspondences. ACM Transactions on Graphics, 31(4):54,
2012. 2
A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet
classification with deep convolutional neural networks. In
NIPS, 2012. 5

9

[43] S. Vicente, J. Carreira, L. Agapito, and J. Batista. Reconstructing pascal voc. In CVPR, 2014. 7
[44] J. Yan, M. Cho, H. Zha, X. Yang, and S. Chu. Multi-graph
matching via affinity optimization with graduated consistency regularization. IEEE transactions on pattern analysis
and machine intelligence, 2015. 2
[45] J. Yan, Y. Li, W. Liu, H. Zha, X. Yang, and S. M. Chu. Graduated consistency-regularized optimization for multi-graph
matching. In ECCV, 2014. 2, 3
[46] J. Yan, Y. Tian, H. Zha, X. Yang, Y. Zhang, and S. Chu.
Joint optimization for consistent multiple graph matching.
In ICCV, 2013. 2
[47] J. Yan, J. Wang, H. Zha, X. Yang, and S. Chu. Consistencydriven alternating optimization for multigraph matching: A
unified approach. IEEE Transactions on Image Processing,
24(3):994–1009, 2015. 2
[48] J. Yan, H. Xu, H. Zha, X. Yang, H. Liu, and S. Chu. A matrix
decomposition perspective to multiple graph matching. In
ICCV, 2015. 2
[49] K. M. Yi, E. Trulls, V. Lepetit, and P. Fua. Lift: Learned
invariant feature transform. In ECCV, 2016. 2
[50] C. Zach, M. Klopschitz, and M. Pollefeys. Disambiguating
visual relations using loop constraints. In CVPR, 2010. 2
[51] W. Zhang, J. Sun, and X. Tang. Cat head detection-how to effectively exploit shape and texture features. In ECCV, 2008.
7
[52] T. Zhou, P. Krahenbuhl, M. Aubry, Q. Huang, and A. A.
Efros. Learning dense correspondence via 3d-guided cycle
consistency. In CVPR, 2016. 2, 6
[53] T. Zhou, Y. J. Lee, S. X. Yu, and A. A. Efros. Flowweb:
Joint image set alignment by weaving consistent, pixel-wise
correspondences. In CVPR, 2015. 2
[54] X. Zhou, M. Zhu, and K. Daniilidis. Multi-image matching
via fast alternating minimization. In ICCV, 2015. 1, 2, 3, 5,
7, 8

10

