Learning Similarities for Rigid and Non-Rigid Object Detection
Asako Kanezaki
The Univ. of Tokyo

Emanuele Rodolà
TU MunichDaniel Cremers
TU MunichTatsuya Harada
The Univ. of Tokyo

Abstracta graph matching problem between the graphs of the reference and observed shapes.

In this paper, we propose an optimization method for
estimating the parameters that typically appear in graphtheoretical formulations of the matching problem for object
detection. Although several methods have been proposed to
optimize parameters for graph matching in a way to promote correct correspondences and to restrict wrong ones,
our approach is novel in the sense that it aims at improving
performance in the more general task of object detection. In
our formulation, similarity functions are adjusted so as toincrease the overall similarity among a reference model andthe observed target, and at the same time reduce the similarity among reference and ”non-target” objects. We evaluate
the proposed method in two challenging scenarios, namely
object detection using data captured with a Kinect sensor
in a real environment, and intrinsic metric learning for deformable shapes, demonstrating substantial improvements
in both settings.

More formally, let (X, dX ) and (Y, dY ) be two (compact) metric spaces with X, Y ⊂ Rm , and let C ⊂ X × Y
be a correspondence set between them. We formulate thematching problem as a Lp -regularized Quadratic Assignment Problem (QAP),
max xT Ax
xs.t. xp = 1 ,(1)where x ∈ [0, 1]|C| represents a (weighted) cluster ofmatches and A is a |C| × |C| symmetric matrix representing pairwise similarity terms between matches. The problem above aims at maximizing the overall similarity among
the two given metric spaces. The QAP formulation of thematching problem is rather common in the shape and graphmatching communities, and in particular Lp relaxations to it
have proved beneficial in a variety of settings. For instance,
Leordeanu and Hebert [9] use p = 2 and Rodolà et al. [15]use p = 1. More recently, mixed norm combinations havebeen proposed [19, 17]. Matrix A can be regarded as therealization of some similarity function π : C × C → [0, 1].
Clearly, many definitions for π are possible depending on
the specific problem at hand. For example, when dealing
with deformable shapes we expect the similarity function
to be as invariant as possible to non-rigid transformationsof the data (e.g., change of pose), and thus define π to take
into account intrinsic shape quantities (such as geodesic distances) that do not depend on how the shape is embedded in
Euclidean space.

1. Introduction
It has been an ultimate objective of computer vision torealize a system that can see the world as a human being
does. These days, technology has enabled us to take advantage of rich visual information in our surroundings in
the form of realistic 3D data (as captured, for instance, byconsumer-level depth cameras); however, it remains an abstruse problem to make an intelligent system see the world
and to let it know ”what is where” in the real world.
In this paper, we propose an optimization method to design effective score functions for object detection tasks. For
the detection step we make use of reference shape data ofthe target objects, and thereby obtain point-to-point correspondences between reference and real-world observations.
Compared to conventional object detection methods which
employ global features extracted from bounding boxes, thislocal approach is more robust to the pose variations and occlusions frequently occurring in a real environment. In order to reduce false local correspondences (mismatches), we
raise the order of the problem and consider pairwise similarity terms. The resulting formulation takes the form of

To deal with an object detection task, we need to define a mechanism according to which the score functions
are to be learned. These functions express how similar an
observed object is to some target object. Here, we attempt
to determine the geometric and visual properties that bettercharacterize each object, together with their influence on
the detection task. In particular, we expect these properties
to depend on the object class to be matched. To this end,
we propose a learning method that optimizes over a vectorof weight parameters representing combination coefficientsfor several similarity functions.
12. Related Work
Arguably the most common method for object detection
consists in the adoption of HOG descriptors [7] extracted
from bounding boxes of the objects, followed by a learning
step on their weights by means of a SVM. A recent, now defacto standard approach for object detection is DeformablePart Models (DPM) [8], which also employs a combinationof HOG and linear SVMs in order to determine the model
parameters. Although DPM provides a flexible model for
object detection, it is not sufficiently robust to handle strong
posture variation or occlusions, as it assumes that the descriptor extracted from each bounding box does not change
dramatically across several instances of the same object.
A second approach to object detection is given by
matching-based methods. Extracting a set of correspondences among sets of features is a fundamental problem
in object detection. In general, the correspondence set obtained by mere comparison of local descriptors includes numerous false corresponding points. Various methods considering the overall consistency of the solution have been
proposed to eliminate these false matches, with derivationsof the QAP taking the lion’s share.
These formulations typically differ in the way the potentials (composing matrix A in Eq. (1)) are defined, suggesting that combinations of several similarity functions mightlead to different results depending on how each similarity
term is weighted relative to the others. In this view, there
has recently been some interest in learning the optimal setof weights for the similarity functions [5, 10, 12, 14]. Caetano et al. [5] optimized these parameters by minimizing
the Hamming loss between a ground-truth assignment vector x and an estimated assignment vector x̂. Leordeanu etal. [10] took a similar view and ran the optimization process based on a smoothed version of the objective function,
leading to an increase of performance. While these methods
require ground-truth correspondence sets, an unsupervised
learning method [12] was recently proposed that makes useof a binarized assignment vector x, obtained as a solution
to a L2 -regularized QAP, in place of the ground-truth assignment vector. This approach, which adopts the estimatedcorrespondence sets as ”teaching signals”, notably allows toachieve equivalent performance to the ground-truth case.
A common feature of the methods mentioned above isthat they specifically attempt to improve matching performance by promoting correct matches, while at the sametime restricting incorrect matches. Nevertheless, it is important to note that the obtained parameters do not necessarily lead to superior performance in object detection
tasks. Although a few methods attempt indeed to “learn
the graph matching” for the classification task [11, 1], they
do not do so by directly minimizing the classification error.
In [11], for instance, the parameters used for matching arelearned independently of the object class (thus ignoring thedifference in scores across all classes), given positive (correct) correspondences and negative (incorrect) correspondences in input. Brendel and Todorovic [1] learn the graphstructures themselves rather than their matching parameters,
whereas the similarity values of the nodes of given training
graphs are fixed.
In our work, we focus on learning the similarity functions for pairwise potentials in graph matching. Intuitively,
the similarity functions tell us how important each featureused in graph matching is to detect each target object. No
prior information on the weight parameters of the similarity
functions is given to the learning process. To detect objects, we obtain correspondence sets between points on reference shape data of target objects and observed shape data.
Differently from the other methods, we place a high valueon achieving proper similarity scores for each target object,rather than improving the accuracy of each correspondence
set separately.

3. Method
Our objective is to learn the parameters of a score function g : X × Y → R representing the similarity value between an observed object X and a target object Y . Our
approach is based on the adoption of an online learning
method that, presuming target and non-target objects exist
in the scene, updates the model parameters by observing
training object samples one after another. Parameters are
updated in such a way to make the score of the correct object higher than those of non-target objects. In the following, we describe how the training samples are obtained, thedefinition of the score function g, and the parameter learning step for the score function.

3.1. Training samples
In this paper, we consider generalized similarity functions π defined by the composition:π(ci , cj ) = exp [−s (ci , cj )] ,(2)

where s : C × C → R is a (not necessarily positive) function expressing the degree of compatibility of two candidate
matches ci and cj .
For the training process, we prepare a reference shapemodel R for each target object, together with a collectionof observed shape data of the same object, which we de(pos)}i=1,...,N , and observed shape data of difnote by {Oi(neg)}j=1,...,N  .
ferent objects, which make up the set {Oj
The process then proceeds as follows. A set of K points are
sampled from each reference shape R, and local descriptors computed at each point. Then, for each observation
(pos)
(neg)
and Ojwe search the knn nearest neighbors (inOidescriptor space) to each sample point in R; by doing so,
we obtain knn K candidate matches for each pair of shapes

(pos)(neg)(R, Oi) and (R, Oj). Since in this step we are only
looking at similarity of the descriptors, the correspondence
(pos)
(neg)
, Cj
⊂ X × Y obtained in this manner may
sets Ci
certainly include wrong matches. These wrong correspondences are filtered out by solving problem (1); in particular, since density of the correspondence is not a concern at
this point, we take the point of view of inlier selection andadopt the L1 -regularized relaxation of the QAP (p = 1) as
proposed in [15], which allows to obtain an accurate (yetsparse) solution to the resulting QAP in an efficient manner.
The solution vector x ∈ [0, 1] is then binarized in {0, 1} by
hard-thresholding. The result of this process is a collectionof filtered correspondence sets between the model R and
(pos)
(neg)
for i = 1, . . . , N , and between R and Oj
forOi
j = 1, . . . , N  .
Note that the generality of the process allows the compatibility function s to be defined as desired. For rigid
object detection tasks we adopt the Euclidean distancedE (a, b) of the pair (a, b) ∈ X × X and definesr ((a, a ), (b, b )) ≡ |dE (a, b) − dE (a , b )| ,(3)

where (a, a ), (b, b ) ∈ C. Since rigid motions preserve
Euclidean distances, we expect a correct correspondence
to attain a value of zero under the function above. Similarly, for non-rigid object detection tasks we employ intrinsic (i.e., isometry invariant) quantities. Namely, we consider the multi-scale diffusion (MD) metric [16] dM (a, b)
and the commute-time (CT) metric [3] dC (a, b), to definesn ((a, a ),(b, b )) ≡sM ((a, a ), (b, b ))+sC ((a, a ), (b, b )),2where sM and sC are defined as in (3), with the appropriate
metrics.

3.2. Score function
In the specific case in which the composite function of
Eq. (2) is directly replaced by the local measure of distortion |dX (a, b) − dY (a , b )|, the quadratic form xT Ax
encodes a notion of proximity between metric spaces X
and Y , namely their Gromov-Wasserstein distance [16, 13].
In particular, the two shapes are isomorphic (i.e., measurepreserving isometric) if their Gromov-Wasserstein distanceequals zero. While in our current setting we replace the local distortion criterion with a similarity potential, it makes
sense to regard the value attained by xT Ax for each cor(pos)
(neg)
, Oj
as therespondence set between R and each Oi
similarity of the corresponding underlying metric spaces.
In particular, since we can only obtain a local optimum foreach (relaxed) QAP, different pairs of shapes will have locally optimal correspondences of different sizes; we thus
normalize the similarity values xT Ax by dividing them by
the corresponding number of matches, which we denote by

M . The baseline score g<base> between two objects canthus be defined as:
g<base> ≡

M 
M

2
exp [−s (ci , cj )] .
M (M − 1) i=1 j=i+1(4)

The function above, which uniformly integrates the pairwise similarity over all correspondences, can be improvedby taking into account additional properties (e.g., color) tohelp distinguishing and give an informed weighting of thecorrespondences. Alternatively, it is possible to integratedifferent similarity functions s with proper weights to define the total score function. The following subsections will
describe the design of the proposed score functions for rigid
and non-rigid object detection.
3.2.1

Rigid object detection (RGBD)

As noted in the previous sections, Eq. (3) is probably themost direct way to encode a similarity criterion between
objects transforming in a rigid manner. However, with therecent surge in availability of consumer-level 3D scanningdevices, there has been a growing interest in providing additional data together with the reconstructed geometry. Color
information, when available, can be employed to drastically
improve recognition results.
In Figure 1 we show a conceptual diagram of our approach for rigid object detection with RGBD data. Specifically, we operate in a quantized HSV space in which we discretize the hue value into k bins; we then define hi ∈ [0, 1]kto be an indicator vector for the point in the reference shapecorresponding to the i-th candidate match, specifying towhich bin this point belongs to. Given two matches i and j,
we may then compute a matrix H for the corresponding hue
values as hi hT
j , and then compute a matrix H where thenon-diagonal element Hmn = Hmn + Hnm (m = n) and
= Hnn . Let qij ∈ [0, 1]k(k+1)/2
the diagonal element Hnn
denote a vector which consists of the elements of the upper triangular portion (including diagonal components) ofH  . Our objective here is to optimize the weight vectorw ∈ [0, 1]k(k+1)/2 for qij with respect to each target object.
The final score function gr (w) for rigid object detection
is defined as follows:


M 
M 

−α · w · qij
2
gr (w) ≡1−exp,
M (M −1) i=1 j=i+1
sr (ci , cj )+(5)
where α > 0 controls the shape of the exponential function, and  is a small number preventing the denominatorfrom being 0. In our experiments, we set α = 10−3 and = 10−20 .

Figure 1. Conceptual diagram of the proposed learning method in a RGBD object detection scenario. Our method learns the weights for apair of matches distinguished by color so that the total score of a correct correspondence set is higher than a wrong one. In this example,
there are three different types of corresponding pairs: white-green, white-white, and green-green.

3.2.2

Non-rigid object detection

A common problem in the metric approach to matching is represented by the appropriate choice of a metricfunction that be invariant to a given class of deformations [13]. For example, geodesic distances are invariant tonearly-isometric deformations but are extremely sensitive
to topological changes in the mesh, whereas commute-time
metrics [3] are more robust to topology and global scalechanges but less accurate on a local scale. In this set of experiments, we are interested in learning the best choice for
an intrinsic metric (or combinations thereof) given different
types of deformations of a shape. In particular, we consider two such distance functions in the definition of pairwise similarity: the multi-scale diffusion (MD) metric [16]and the commute-time (CT) metric.
Letting w ≡ [wM wC ]T ∈ R2 be a vector of weights
and s(ci , cj ) ≡ [sM (ci , cj ) sC (ci , cj )]T ∈ R2 , we define
the score function gn (w) for non-rigid object detection as:
gn (w) ≡M M2
exp[−w · s(ci , cj )] .
M (M −1) i=1 j=i+1(6)

3.3. Learning of parameters
The method we propose in this subsection allows to obtain the optimal w (appearing in Eqs. (5) and (6)) by computing a separating hyperplane on the training samples.
This is similar in spirit to conventional methods such as
SVM, in that we optimize w so that the value of g(w) for apositive sample is high and the value attained by a negative
sample is low. We do so by minimizing a quantity called
hinge loss (Eq. (8) below), which represents the penalty incurred by training samples for being within the margin of
the separating hyperplane.
Within this framework, the score function that outputs
how similar an observed object is to the target object must

range from −∞ to +∞. Therefore, we define the scorefunction f used for training as follows:f (w, b)≡=logit (g(w)) + b,log(g(w)) − log(1 − g(w)) + b,

(7)

where b is an offset value that is optimized together with
w. Letting the label of a correct (positive) set of correspondences be y = 1 and the label of a wrong (negative) set ofcorrespondences be y = −1, the hinge loss is defined as0
yf (w, b) ≥ 1 ,(8)l(w, b; (f, y)) =otherwise .
1 − yf (w, b)
We initialize w as w0 = ( , . . . ,  ),  ∼ 0, and b as
b0 = 0. Each time a training correspondence set is observed, these two parameters are updated accordingly. Letting wt and bt be the parameters obtained after the t-th update, the solutions at successive time steps are obtained bysolving the projection problem
1{wt+1 , bt+1 } = arg min w − wt 2 +b − bt 2
(9)
2
w,b
s.t. l(w, b; (ft , yt )) = 0.

(10)This problem can be solved in closed-form. In particular,when yt ft (wt , bt ) ≥ 1, we have the steady states wt+1 =wt and bt+1 = bt . Therefore, we can just consider the casein which yt ft (wt , bt ) < 1. In this case, the Lagrangiantakes the form:
1
1
L(wt , bt , λ) = wt+1 − wt 2 + bt+1 − bt 2
2
2+λ(1 − yt ft (wt , bt )). (11)Differentiating with respect to wt and bt and setting thederivatives to zero provides the following:
wt+1=

wt − λyt

bt+1=

bt − λyt .

∂ft (wt , bt )
,
∂wt

(12)
(13)

Therein, ∂b∂ t ft (wt , bt ) = 1. Plugging the above back into(11) yields
1 2 ∂ft (wt , bt )
λ
2
∂wt

2

1
+ λ2 + λ(1 − yt ft (wt , bt )).
2(14)
Taking now the derivative of L(λ) with respect to λ andsetting it to zero gives us the following closed-form solution
for the optimal λ:L(λ) =

yt ft (wt , bt ) − 1

λ=∂ft (wt ,bt )
∂wt

2

.

(15)

+1

Finally, wt+1 and bt+1 are obtained by the iterative equations:
wt+1 = wt +bt+1 = bt +(yt − ft (wt , bt ))2∂ft (wt ,bt )∂wt+1(yt − ft (wt , bt ))∂ft (wt ,bt )
∂wt

2

·

∂ft (wt , bt ), (16)
∂wt

,

(17)

+1

where the gradient of f is computed as:∂f (w, b)
∂w

=
=

∂
(log(g(w)) − log(1 − g(w)))
∂w
∂g(w)
1
.
(18)
g(w)(1 − g(w)) ∂w

Note that the gradient of gr (w) is given by
M 
M 




4. Results
4.1. Rigid object detection (RGBD)
Our first experiment is aimed at evaluating the proposed
method in a rigid setting, using data captured with a Kinect
sensor in a real-world environment. The captured data consists of 3D point clouds, where each point is endowed witha color attribute. The training set is composed of 10 target
objects, each coming with a reference model and nine observations from as many view points (see Fig. 2). Negative
samples for the non-target objects were prepared by capturing 70 scenes containing none of the target objects, and thenby attempting to match each target model with these scenes(see Fig. 3 (a)). We search the knn = 5 nearest neighbors in
RGB space1 to 2,000 sample points in a reference model toobtain the candidate correspondence sets. For comparison,
we extracted SIFT keypoints from color images and performed brute-force matching, i.e., nearest neighbors in descriptor space. Then we solved the QAP problem via [15] toobtain final (sparse) correspondence sets. We set the quantization number of hue values to k = 3. Experiments withother values for k led to substantially similar results. We1−α · w · qij
α · qij
2· exp
M (M −1) i=1 j=i+1 sE (ci , cj )+sE (ci , cj )+

employ can be regarded as an extension to PA, obtained byreplacing the score function f (x) with Eq. (7). Note that
our approach is more general than PA as we allow any differentiable score function to be adopted, whereas only linear scores can be employed with the PA method.

,

2

(19)

3

whereas the gradient of gn (w) becomes
4

−

M 
M


2
s(ci , cj ) · exp [−w · s(ci , cj )] .
M (M − 1) i=1 j=i+1(20)
The derivation of the gradient of gr (w) and gn (w) are omitted for space reasons.

5
6
7
8

Discussion9

It is particularly interesting to note that the proposed update rule for the parameters shares a connection with the
Passive–Aggressive (PA) [6] online learning method of linear classifiers. Letting x be the descriptor of a training
sample, PA computes the gradient of the score function
f (x) = w · x + b to minimize the hinge loss, and it updates the parameters with the constraint of minimizing theL2 distance from the current parameters. The algorithm we

10

Figure 2. Target objects used in the training dataset for similarity
weight learning. Reference models of the target objects are shownin the leftmost column.
1 Depth information is only used to obtain 3D coordinates of each point.

Model Shapes

human

dog

horse

Transformed
Shape Samples

Figure 3. Exemplar correspondences between the reference modelof the target object #1 and observed objects. (a) Positive correspondences in training data. (b) Correct correspondences in testing
data. (c) Wrong correspondences in testing data.

terminate the learning process if the sum of the hinge loss
becomes sufficiently small before γ = 100 iterations.
Quantitative evaluation was performed by capturing 120
scenes in a different environment and then computing thecorrespondence sets of all target objects on each of them(see Fig. 3 (a) and Fig. 3 (b)). The Precision-Recall curves
and average precision values are shown in Fig. 4. The bluelines represent the results with SIFT keypoints and the baseline score function (Eq. (4)), the green lines represent theresults with RGB nearest neighbor search and the baseline
score function (Eq. (4)), and the red lines represent the results with RGB nearest neighbor search and the proposed
score function (Eq. (5)). SIFT keypoints do not bring any
clear advantage except for target objects 1 and 5, which contain textured planes. RGB nearest neighbor search with theproposed score function outperformed the baseline score in
all the cases except for target object 4. The average values of precision are 0.13 with SIFT keypoints, 0.27 with
RGB nearest search and the baseline score function, and0.31 with RGB nearest search and the proposed score function.

4.2. Non-rigid object detection
In the second set of experiments we evaluate the improvements gained by adopting the proposed learning
method in a non-rigid matching scenario. This setting is
considerably more challenging than the previous case as
the shapes are allowed to undergo non-rigid deformations.
Recent attempts at introducing domain knowledge into thisfamily of problems include [18], where the authors trained arandom forest with an intrinsic shape descriptor to directly
estimate dense correspondences between complete (i.e., no
partiality is allowed), previously unseen shapes. Differently
from [18], in this section we demonstrate the applicability of our approach to learn an optimal weighting of metric functions for each class of shapes; the learned weights
can then be employed within a QAP formulation to matchpartial, deformable shapes as in [16].
For this set of experiments we make use of the

5 levelsFigure 5. Datasets used in the non-rigid recognition experiments.

Figure 6. Examples of positive (left) and negative (right) correspondence sets.

SHREC’10 correspondence benchmark [2]. This dataset
consists of three classes, namely “human”, “dog”, and“horse”; each class consists of one reference shape modeland several data shapes transformed with nine different deformations (see Fig. 5), each coming in 5 intensities. We
used one class among “human”, “dog”, and “horse” as thetarget class and used the samples in the other classes as negative samples. In each experiment, we used the samples of
one type among all the 9 types of deformation.
In order to keep the problem more tractable, each shape
was sampled at 200 points via Farthest Point Sampling(FPS) [3] using the extrinsic Euclidean metric (this choice ismore robust to topology and partiality deformations than using an intrinsic metric). We applied FPS 10 times per shapestarting from different seeds, obtaining 10 point sets per
shape, and for each point in the sample sets we computed
an intrinsic local descriptor, namely its Scale-Invariant Heat
Kernel Signature (SI-HKS) [4]. The “positive” set of correspondences was formed by manually selecting 200 ground(pos)and the cortruth pairs among each deformed shape Oi
responding model R. The “negative” sets (i.e., sets ofmatches between a deformed shape from one class andthe reference model from another class) were formed byseeking the 5 nearest points in descriptor space for all the
200 sampled points on each reference shape, thus obtaining
1,000 candidate matches per set. Exemplary positive andnegative correspondence sets are shown in Fig. 6.
The “human”, “dog”, and “horse” shapes were respec-

Figure 4. Precision-Recall curves and average precision values (below each Precision-Recall curve). The results of target objects from
No. 1 to No. 10 are shown from the top left to the bottom right. The blue lines represent the results with SIFT keypoints and the baseline
score function (Eq. (4)), the green lines represent the results with RGB nearest neighbor search and the baseline score function (Eq. (4)),
and the red lines represent the results with RGB nearest neighbor search and the proposed score function (Eq. (5)).

tively used as a target object, and shapes not belonging to
the target class were used as the negative samples. We thenran an experiment for each type of deformation. Specifically, for each experiment we constructed the training set
by randomly selecting one positive and negative samples
out of the 10 sets of FPS samples per shape, and we did
this at deformation strengths 1, 3, and 5 (for a total of 3
positive samples and 6 negative samples in the training set).
The test set was then formed by selecting all 10 sets of FPS
samples per shape; we did this at the remaining deformation
strengths 2 and 4, for a total of 2×10 = 20 positive samples
and 2 × 2 × 10 = 40 negative samples in the test set. We set
the maximum number of learning iterations to γ = 10, 000.
The resulting average precision values are presented inTable 1. From left to right we report the average precision values obtained by using MD only (“MD”), CT
only (“CT”), uniform weights {0.5, 0.5} (“baseline”), andlearned weights (“learned”). Average precision over thewhole dataset is reported in the last row; the proposed
method (“learned”) gave the best overall results when compared with “MD”, “CT”, and “baseline” alone.
Figure 7 shows the learned weights for similarity functions (MD and CT) in the deformation class “scale” and“shotnoise”. Note that in the case of “scale” samples, theaverage precision values obtained with the CT metric are
higher than those obtained with MD; likewise, the learned

weight for the CT term is higher than MD. This is easily
explained since CT is a fully scale-invariant metric whereas
MD is only invariant to limited scale ranges. Similarly, thelearned weight for the MD term is higher than CT in thecase of “shotnoise” samples, whereas the average precision
values obtained with the MD metric are higher than thoseobtained with CT. This implies, in particular, that a proper
selection of the metrics could be achieved when the “scale”
samples and “shotnoise” samples are used.

5. Conclusion
In this paper we proposed an optimization method for
estimating the parameters that typically appear in graphtheoretical formulations of the matching problem. In particular, we restricted our attention to the object detection
scenario. We formulated our method in an online learning
framework, and evaluated the approach on two challenging problems, namely object detection of color 3D point
clouds in a real environment, and intrinsic metric learningfor deformable 3D shapes. The learning process improved
the performance of object detection in both the consideredscenarios. Our method can be easily extended and accommodated by considering different definitions of similarity.
In particular, considering higher-order potentials and hypergraph matching scenarios are important future directions ofresearch.

Table 1. Average precision in a non-rigid object detection task.

D

d
ŚƵŵĂŶ

tĞŝŐŚƚƐ

ƐŚŽƚŶŽŝƐĞ
Ϯ
Ͳϯ
Ͳϴ
Ͳϭϯ
Ͳϭϴ
ͲϮϯ
ͲϮϴ

D

d

Ϯϯ
ϭϵ
ϭϱ
ϭϭ
ϳ
ϯ
Ͳϭ

ϭϮϬ
ϭϬϬ
ϴϬ
ϲϬ
ϰϬ
ϮϬ
Ϭ

ĚŽŐ
tĞŝŐŚƚƐ

ŚƵŵĂŶtĞŝŐŚƚƐ

Ϭ͘ϰ
Ϭ͘Ϯ
Ϭ
ͲϬ͘Ϯ
ͲϬ͘ϰ
ͲϬ͘ϲ
ͲϬ͘ϴ

tĞŝŐŚƚƐ

tĞŝŐŚƚƐ

ƐĐĂůĞ

Average Precision
CT baseline learned
0.94
1.00
1.00
0.94
0.75
1.00
0.96
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.82
0.33
1.00
0.82
0.33
0.75
1.00
0.85
1.00
0.69
0.33
1.00
0.52
0.36
1.00
1.00
1.00
1.00
0.55
0.34
1.00
1.00
0.82
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.78
1.00
1.00
1.00
1.00
1.00
0.33
0.74
1.00
0.33
1.00
1.00
0.33
1.00
0.77
1.00
0.96
0.75
0.77
1.00
1.00
1.00
1.00
0.92
0.77
0.98

MD
1.00
0.69
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.33
0.33
0.85
0.33
0.33
1.00
0.33
0.68
1.00
1.00
0.66
1.00
0.33
0.33
0.33
1.00
0.85
1.00
0.76

D

d
ĚŽŐ

D

ϭϯ
ϭϭ
ϵ
ϳ
ϱ
ϯ
ϭ
Ͳϭ

ŚŽƌƐĞ

D

d

d
ŚŽƌƐĞ

ϯ
tĞŝŐŚƚƐ

Deform.
Target
holes
human
holes
dog
holes
horse
isometryhuman
isometrydog
isometryhorse
microholes humanmicroholes
dog
microholes
horse
noise
human
noise
dog
noise
horse
localscale human
localscaledog
localscale
horse
topology
human
topology
dog
topologyhorsesampling
humansampling
dog
sampling
horse
scale
human
scale
dog
scale
horse
shotnoisehumanshotnoisedogshotnoise
horse
Average

Ϯ
ϭ
Ϭ

D

d

Figure 7. Learned weights for similarity functions (MD and CT)
in the deformation class “scale” (top) and “shotnoise” (bottom).

References[1] W. Brendel and S. Todorovic. Learning spatiotemporalgraphs of human activities. In Proc. IEEE ICCV, 2011. 2[2] A. M. Bronstein, M. M. Bronstein, U. Castellani, A. Dubrovina, et al. Shrec 2010: robust correspondence benchmark. In
Proc. EUROGRAPHICS Workshop on 3D Object Retrieval(3DOR), 2010. 6[3] A. M. Bronstein, M. M. Bronstein, and R. Kimmel. Numerical geometry of non-rigid shapes. Springer, 2008. 3, 4, 6
[4] M. M. Bronstein and I. Kokkinos. Scale-invariant heat kernel
signatures for non-rigid shape recognition. In Proc. IEEE
CVPR, 2010. 6[5] T. S. Caetano, J. J. McAuley, L. Cheng, Q. V. Le, and A. J.
Smola. Learning graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 31(6):1048–
1058, 2009. 2[6] K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and
Y. Singer. Online passive-aggressive algorithms. Machine
Learning Research, 7:551–585, 2006. 5[7] N. Dalal and B. Triggs. Histograms of oriented gradients forhuman detection. In Proc. IEEE CVPR, 2005. 2[8] P. F. Felzenszwalb, R. B. Girshick, D. McAllester, and D. Ramanan. Object detection with discriminatively trained partbased models. IEEE Transactions on Pattern Analysis andMachine Intelligence (PAMI), 32(9), 2010. 2[9] M. Leordeanu and M. Hebert. A spectral technique for correspondence problems using pairwise constraints. In Proc.
IEEE ICCV, 2005. 1[10] M. Leordeanu and M. Hebert. Smoothing-based optimization. In Proc. IEEE CVPR, 2008. 2[11] M. Leordeanu, M. Hebert, and R. Sukthankar. Beyond local
appearance: Category recognition from pairwise interactionsof simple features. In Proc. IEEE CVPR, 2007. 2[12] M. Leordeanu, R. Sukthankar, and M. Hebert. Unsupervised
learning for graph matching. International Journal of Computer Vision, 96(1):28–45, 2012. 2[13] F. Mémoli. Gromov-Wasserstein distances and the metric approach to object matching. Found. Comput. Math.,
11:417–487, 2011. 3, 4
[14] D. Pachauri, M. Collins, V. Singh, and R. Kondor. Incorporating domain knowledge in matching problems via harmonic analysis. In Proc. ICML, 2012. 2[15] E. Rodolà, A. Albarelli, F. Bergamasco, and A. Torsello. A
scale independent selection process for 3d object recognition in cluttered scenes. International Journal of Computer
Vision (IJCV) - Special Issue on 3D Imaging, Processing andModeling Techniques, 19, 2012. 1, 3, 5[16] E. Rodolà, A. M. Bronstein, A. Albarelli, F. Bergamasco,and A. Torsello. A game-theoretic approach to deformableshape matching. In Proc. IEEE CVPR, 2012. 3, 4, 6
[17] E. Rodolà, T. Harada, Y. Kuniyoshi, and D. Cremers. Efficient shape matching using vector extrapolation. In Proc.
BMVC, 2013. 1[18] E. Rodolà, S. Rota Bulò, T. Windheuser, M. Vestner, and
D. Cremers. Dense non-rigid shape correspondence using
random forests. In Proc. IEEE CVPR, 2014. 6[19] E. Rodolà, A. Torsello, T. Harada, Y. Kuniyoshi, and D. Cremers. Elastic net constraints for shape matching. In Proc.
IEEE ICCV, 2013. 1