iccv iccv2013 iccv2013-140 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Emanuele Rodolà, Andrea Torsello, Tatsuya Harada, Yasuo Kuniyoshi, Daniel Cremers
Abstract: We consider a parametrized relaxation of the widely adopted quadratic assignment problem (QAP) formulation for minimum distortion correspondence between deformable shapes. In order to control the accuracy/sparsity trade-off we introduce a weighting parameter on the combination of two existing relaxations, namely spectral and game-theoretic. This leads to the introduction of the elastic net penalty function into shape matching problems. In combination with an efficient algorithm to project onto the elastic net ball, we obtain an approach for deformable shape matching with controllable sparsity. Experiments on a standard benchmark confirm the effectiveness of the approach.
Reference: text
sentIndex sentText sentNum sentScore
1 de Abstract We consider a parametrized relaxation of the widely adopted quadratic assignment problem (QAP) formulation for minimum distortion correspondence between deformable shapes. [sent-15, score-0.75]
2 This leads to the introduction of the elastic net penalty function into shape matching problems. [sent-17, score-0.883]
3 In combination with an efficient algorithm to project onto the elastic net ball, we obtain an approach for deformable shape matching with controllable sparsity. [sent-18, score-0.983]
4 Introduction Shape matching is a pervasive problem in computer vision and arises in several different fields ranging from robotics to medical imaging. [sent-21, score-0.145]
5 As such, matching of deformable shapes has attracted the interest of researchers during the years and a wide variety of approaches have been proposed (see, e. [sent-24, score-0.293]
6 A prominent approach to the matching problem from a metric perspective was introduced in [12], a concept that was explored further in [3] with the introduction of the GMDS framework, where the minimum distortion isometric embedding of one surface onto another is explicitly sought. [sent-27, score-0.527]
7 This idea of a fuzzy map of assignments is not novel, and can be traced back, for instance, to the softassign method for graph matching [6]. [sent-30, score-0.276]
8 In the specific case of non-rigid shapes, fuzzy schemes are typically adopted to relax the point-to-point mappings [11, 14]. [sent-31, score-0.157]
9 [16] gave a linear programming relaxation to the matching problem; the method notably allows to obtain continuous correspondences, but it is sensitive to topological changes and, as noted by the authors, its GPU implementation takes about 2 hours per matching. [sent-36, score-0.26]
10 In this paper, we consider the widely adopted quadratic assignment problem (QAP) formulation for minimum distortion correspondence between deformable shapes. [sent-37, score-0.688]
11 Notable attempts at relaxing the NP-hard QAP include graduated assignment [6], spectral relaxation [8] and the more recent game-theoretic approach [14]. [sent-38, score-0.25]
12 This leads us to the introduction of the elastic net penalty function [18] into shape matching problems. [sent-40, score-0.883]
13 The contributions of this paper are two-fold: First, we provide an interpretation of the correspondence problem from the point of view of regression analysis, yielding a nat11 116699 ural connection between existing approaches and well established regularization techniques. [sent-41, score-0.311]
14 We introduce the fam- ×× ily of elastic net constraints into a relaxed QAP formulation, and show how previous relaxation attempts naturally constitute special cases of our formulation. [sent-42, score-0.83]
15 Second, we give a solution to the projection problem onto the new set of constraints from the viewpoint of variable selection, giving rise to an especially simple and efficient projection algorithm. [sent-44, score-0.547]
16 Minimum distortion correspondence We model shapes as compact Riemannian manifolds endowed with an intrinsic metric d. [sent-46, score-0.669]
17 A point-to-point correspondence between two shapes X and Y can be defined as a binary function c : X Y → {0, 1} satisfying the mapping acoryns fturnaicnttiso ? [sent-47, score-0.378]
18 Note that these constraints ensure vtherayt every point yin ∈ one shape haats t aets em coosnt one corresponding point in the other (and vice versa), thus allowing the two shapes to have different size. [sent-52, score-0.271]
19 In the following, we will slightly abuse nomenclature and equivalently refer to the correspondence as the respective collection of matches, that is, the set of pairs C ⊂ X Y for which c(x, y) 0. [sent-53, score-0.207]
20 Itn i o,r tdheer s etot give a measure ×of Y quality htioc hth ce( correspondence, we evaluate the distortion induced by the mapping as measured on the two shapes using the respec- = × tive metrics dX and dY. [sent-54, score-0.408]
21 ) | (2) directly quantifies to which extent the estimated correspondence deviates from isometry. [sent-62, score-0.207]
22 Following [11, 14], we first relax the correspondence from a discrete to a fuzzy notion by letting c : X Y → [0, 1], effectively setting offthe problem tfrtionmg cits : Xcom ×b Yin →ator [i0a,l1 n]a, teuffreec tainvde bringing oitf fttoh a continuous optimization domain. [sent-63, score-0.439]
23 Further, we adopt the so called Gromov-Wasserstein [11] family of metrics, which give rise to a relaxed notion of proximity between shapes: D(X, Y ) = 12mCin ? [sent-64, score-0.171]
24 ) ∈C Establishing a minimum distortion correspondence between the two shapes amounts to finding a minimizer of the above distance. [sent-74, score-0.667]
25 0, where vec{C} is the |C|-dimensional column-stack vector representation o ifs th thee correspondence ml caotrliuxm Cn-, Ata ciks a nonnegative symmetric cost matrix containing the pairwise distortion terms that appear in (3), 1is a vector of n = |C| ones, nan tder ? [sent-80, score-0.444]
26 d dQeAnPot, efusn ecletimone c iws itsaeke inne qtou ab eli a binary correspondence and the mapping constraints (1) hold with equality (requiring C to be a permutation matrix). [sent-83, score-0.31]
27 In the following, we present two existing approaches that relax the mapping constraints in (4) to find a minimum distortion correspondence. [sent-84, score-0.427]
28 Even though originating from distinct motivations, the two methods share a convenient interpretation as partitioning problems in the space of potential assignments. [sent-85, score-0.136]
29 Spectral matching Taking the point of view of graph clustering, [8] proposed the simplified problem minx xTAx (5) s. [sent-89, score-0.146]
30 The method has a tendency to produce matches for each point. [sent-98, score-0.193]
31 This makes it of limited use in real settings, where shapes may undergo partiality deformations. [sent-99, score-0.196]
32 The spectral method has been applied for non-rigid matching in [13]. [sent-101, score-0.201]
33 The L2 relaxation to the QAP was introduced mainly because it allows to obtain a global solution to the modified problem in closed form. [sent-102, score-0.141]
34 Here we give another interpretation of this approach as a relaxed two-way partitioning problem [1]. [sent-103, score-0.184]
35 n; these constraints restrict the values of xi to ±1, so the problem is equivalent to finding the partitioning ±(as1 “, msoa tthceh p” or “lenmonis-m eaqtucihva”l) on a s feitn odifn n tehleem pearntit-s that minimizes the total cost xTAx. [sent-107, score-0.219]
36 Game-theoretic matching Given the inherent difficulty to solve for a minimum distortion correspondence under general deformations, in a re11 117700 tic net (in between) balls in R2 . [sent-120, score-0.953]
37 cent paper [14] we proposed to shift the focus to the search of a maximal group of matches having least distortion, regardless of its cardinality. [sent-124, score-0.156]
38 While existing algorithms may be applied to densify the few obtained matches, in practice the high spatial locality of the final correspondence does not allow to properly constrain such densification methods [17, 13]. [sent-131, score-0.207]
39 Matching with the elastic net Both methods presented in the previous section are virtually free from parameters, but their performance directly depends on the specific definition of the distortion function ? [sent-144, score-0.892]
40 [13] recently introduced the notion of shape condition number. [sent-150, score-0.142]
41 According to this notion, the stability of the matching can be characterized as an intrinsic property of the shape itself, and is related to its intrinsic symmetries as well as the specific choice of a metric. [sent-151, score-0.356]
42 In order to incorporate a somewhat elusive notion of stability into the matching process, we propose to change the point of view by drawing an analogy between the correspondence problem and model-fitting. [sent-152, score-0.386]
43 Our goal, in this context, is to determine a good approximation of the true relationship between the two shapes: we seek to fit or approximate the optimal correspondence x? [sent-153, score-0.242]
44 These cbaunilddid uapte th hmea stecth oefs pacotte as predictors feonr tshe { xm}inimum distortion correspondence, and can be given the interpretation of explanatory variables which we observe, while we seek to find the combination that best describes the data in the minimal distortion sense. [sent-162, score-0.645]
45 Since in general these variables hold a certain degree of correlation among them, it is of particular interest to attempt to determine whole groups of highly correlated predictors, as they will likely form consistent groups of matches in terms of the adopted measure of distortion. [sent-163, score-0.269]
46 In this view, spectral matching can be directly related to ridge regression, whose L2 penalty is known to generally improve conditioning ofthe problem, yet always keeping all the predictors in the model. [sent-164, score-0.375]
47 To this end, we adopt a family ofconstraints known as elastic net [18]. [sent-168, score-0.709]
48 The elastic net criterion is defined as a convex combination of the lasso and ridge penalties: (1 − α)? [sent-170, score-0.887]
49 (7) It becomes ridge regression for α = 1, and the lasso for α = 0. [sent-175, score-0.222]
50 Let x ∈ R|C| be the vector representation of some corresponxde ∈nce R C ⊂ X Y , we expect the elastic net-penalized so11 117711 lution to keep the difference |xi − xj | small whenever the mluteitornic odi ksetoerpti othne ? [sent-179, score-0.384]
51 The trade-off between size of the correspondence and matching error is regulated by the convexity parameter which allows to fine tune the model complexity and balance the action of the penalty ranging from the highly selective pure lasso for α = 0 to the more tolerant ridge behavior for α = 1. [sent-181, score-0.73]
52 The family directly generalizes the spectral awnitdh game-theoretic techniques. [sent-190, score-0.145]
53 ,(9) where Ax = 21∇xTAx is a descent direction for the objective, γ > 0 is∇ xthe step length taken in that direction, and Π : Rn → Rn is a projection operator taking a solution back onto the→ fe Rasible set. [sent-198, score-0.308]
54 While efficient methods for projecting onto the L2 and L1 balls have been proposed in literature [15], projection onto their convex combination is a more involved task. [sent-199, score-0.454]
55 A detailed explanation of our approach on the computation of Π is deferred to the next Section; nevertheless, we anticipate here that this projection step can be performed in a very efficient manner. [sent-200, score-0.174]
56 This allows us to determine the optimal step size in (9) at each iteration by performing exact line search [1] along the ray {x + γAx : γ ≥ 0} through ltihnee application oalfo Nnegw tthoen r’as ym {exth+o d γ [A1],x a quadratic fitting algorithm having order two convergence. [sent-201, score-0.137]
57 Finally, we initialize x(0) to the barycenter of the elastic net boundary, i. [sent-202, score-0.655]
58 n we set xi to the positive solution ofthe quadratic equation αnx2+(1−α)nx−1 = 0. [sent-207, score-0.146]
59 Projection onto the elastic net ball Computing the Euclidean projection Π(x0) onto the (positive) elastic net ball boundary amounts to solving the following projection problem minx ? [sent-210, score-1.976]
60 [10] propose a linear time projection algorithm based on randomized median search; the algorithm is numerically stable, but it is outperformed by root finding for low dimensions [7]. [sent-223, score-0.263]
61 To this end, we take a different point of view and regard the projection problem as one of coordinate selection. [sent-227, score-0.212]
62 We determine a closed form projection onto C1 as followWs. [sent-231, score-0.304]
63 (13) Determining the optimal value for λ is straightforward; imposing the elastic net constraints on x, it must hold αi? [sent-242, score-0.72]
64 nTlyhe ∼ game-theoretic a(Lpe1) i sso mluatticohna bilse highly oswele dcitsitvoer taiondn only assigns 3% of the shape samples, with geodesic error 3. [sent-250, score-0.159]
65 12 (left image); in contrast, the spectral (L2) approach favors dense solutions and yields matches for 93% of the points, with total error 62. [sent-251, score-0.33]
66 Elastic net matching (middle) allows to regulate the trade-off between size and distortion: the correspondence is made more dense, and 53% of the points are matched while keeping the error at 15. [sent-253, score-0.788]
67 (17) always admits two real solutions, only one ofwhich gives the correct projection (we omit the complete derivations for space reasons). [sent-275, score-0.216]
68 The key step now consists in deselecting those coordinates getting a non-positive value after an unconstrained projection takes place: this gives us a rule for updating the indicator vector in such a way that projecting again with the new e will directly put those variables to zero. [sent-277, score-0.213]
69 Then projection problem (10) is minimized by application of the iterative rules x(t+1) = x(0)−1 + λ( λe((et)()t)1)−2ααe(t) (18) e(it+1) = ? [sent-281, score-0.174]
70 On the right, a scatter plot of error vs number of matches over the whole dataset. [sent-321, score-0.241]
71 (20) Using an analogous derivation we can show that the same holds for the elastic net projection. [sent-327, score-0.655]
72 Further, projection (16) is also monotonic in the active selected coordinates, i. [sent-328, score-0.213]
73 Due to this monotonicity of the projection the entries of e are eliminated in coordinate rank order, thus the algorithm never eliminates a coordinate that has a non-zero value in the optimal projection and con- verges in at most k steps, where k is the number of zero entries in the final vector. [sent-331, score-0.424]
74 Performance of the projection We compared the projection time against other projection methods onto the elastic net, namely piecewise root finding [7], randomized median finding [10], our method (coordinate selection), and its parallel version. [sent-334, score-1.184]
75 For these comparisons, we generated random vectors of varying size and ran each projection method on the same input. [sent-336, score-0.174]
76 The experiment was repeated 100 times per size, and projection times accumulated and plotted for each method. [sent-337, score-0.174]
77 While all methods demonstrate linear complexity, we observed that the root finding method produced suboptimal solutions for sizes larger than 104. [sent-340, score-0.136]
78 We measure the matching error of a correspondence C ⊂ X Y as its average geodesic rdoisrtaonfcaec forrormes ptohen ground-truth Cg, taking ianvteor aagcceoguenotd possible intrinsic symmetries, as in [2]: D(C,Cg) =|C1|min⎨⎧k? [sent-371, score-0.458]
79 only a limited number of samples (m = 1000 in our experiments) are considered from one shape, and then potential matches are built with the 5 closest points (in descriptor space) in the other. [sent-381, score-0.156]
80 Samples are generated via farthest point sampling (FPS) [12, 11] using the extrinsic Euclidean metric, since it gives for large m a good and efficient approximation to the intrinsic measures while being more robust to topological and partiality deformations. [sent-383, score-0.218]
81 Note also that in the matching process only one of the two shapes is subsampled, while we keep all points in the other. [sent-387, score-0.243]
82 Trade-off analysis Elastic net matching can be seen as an instance of multicriterion optimization, in which we wish to maximize the size of the correspondence while simultaneously bringing 11 117744 Transform. [sent-395, score-0.668]
83 2 presents an example in which the correct matches have a very small inlier ratio with respect to the set of candidates (a full Cartesian product in this case). [sent-401, score-0.156]
84 In this matching scenario, our method provides a means to select only highprecision correspondences in a situation where there is huge ambiguity in most correspondences. [sent-402, score-0.145]
85 In this view, we might naturally ask how much we must pay in terms of distortion in order to obtain an increase in the number of matches. [sent-403, score-0.237]
86 3 (right) we plot each shape-to-shape correspondence over the whole dataset as a point in this plane; for each matching instance, we vary the convexity coefficient α from 0 to 1 (shown by color). [sent-406, score-0.436]
87 The figure suggests that this parameter allows to regulate the compromise between the two criteria, while maintaining a comparable error variance (note that the plot is in log-log scale so we expect an expansion at the lower end of the scale for a fixed variance). [sent-407, score-0.252]
88 In most cases, there is a point of large curvature where a small increase in the number of matches can only be accomplished by a large increase in matching error. [sent-411, score-0.266]
89 Second, it is evident that smaller values of α do not necessarily lead to better solutions in terms of metric distortion; in particular, the game-theoretic solution will not always be the best choice, even when a sparse solution is being sought. [sent-415, score-0.162]
90 11 117755 false positive is a match with error larger than r, and false negatives are low-error matches in the candidate set which were not included in the final solution. [sent-446, score-0.192]
91 Note that the small recall we obtain in both graphs does not contradict the fact that for large α we should obtain dense correspondences, as it is due to a filtering step we perform on those matches having a very small value for xi (below 10% of the median). [sent-447, score-0.244]
92 mIno sftac ot,f since for small values it yields sparser solutions, the projection step needs more iterations to converge. [sent-457, score-0.209]
93 Finally, adopting the parallel version of the projection algorithm into the optimization process lowered the overall convergence time to ∼5 seconds per matching. [sent-462, score-0.225]
94 Conclusions In this paper, we proposed the adoption of the elastic net family of constraints as regularizers for the quadratic assignment problem, which frequently arises in deformable shape matching problems. [sent-464, score-1.157]
95 It allows to regulate the relative contribution of distortion and size of the correspondence via a single convexity parameter. [sent-466, score-0.643]
96 We provided an efficient and provably optimal solution to the projection problem onto the new set of constraints, and demonstrated on a standard benchmark how the method allows to obtain sparseto-dense solutions with an accuracy at least as good as the state of the art. [sent-467, score-0.395]
97 Efficient euclidean projections via piecewise root finding and its application in gradient projection. [sent-511, score-0.181]
98 A spectral technique for correspondence problems using pairwise constraints. [sent-517, score-0.298]
99 Efficient learning of label ranking by soft projections onto polyhedra. [sent-574, score-0.151]
100 Geometrically consistent elastic matching of 3d shapes: A linear programming solution. [sent-586, score-0.459]
wordName wordTfidf (topN-words)
[('elastic', 0.349), ('net', 0.306), ('qap', 0.253), ('distortion', 0.237), ('correspondence', 0.207), ('projection', 0.174), ('matches', 0.156), ('shapes', 0.133), ('bronstein', 0.125), ('lasso', 0.121), ('matching', 0.11), ('onto', 0.095), ('xtax', 0.095), ('spectral', 0.091), ('regulate', 0.089), ('fuzzy', 0.079), ('vec', 0.075), ('xtx', 0.073), ('shape', 0.073), ('convexity', 0.07), ('interpretation', 0.069), ('notion', 0.069), ('dx', 0.068), ('partitioning', 0.067), ('ridge', 0.066), ('constraints', 0.065), ('tokyo', 0.065), ('predictors', 0.063), ('gmds', 0.063), ('partiality', 0.063), ('torsello', 0.063), ('symmetries', 0.063), ('quadratic', 0.062), ('relaxation', 0.062), ('isometry', 0.061), ('relaxations', 0.061), ('rodol', 0.056), ('shrec', 0.056), ('windheuser', 0.056), ('pareto', 0.056), ('uniformization', 0.056), ('projections', 0.056), ('intrinsic', 0.055), ('family', 0.054), ('lipman', 0.052), ('farthest', 0.052), ('harada', 0.052), ('graduated', 0.052), ('parallel', 0.051), ('geodesic', 0.05), ('deformable', 0.05), ('plot', 0.049), ('minimum', 0.048), ('relaxed', 0.048), ('topological', 0.048), ('solutions', 0.047), ('root', 0.047), ('traced', 0.047), ('ball', 0.046), ('penalty', 0.045), ('convex', 0.045), ('assignment', 0.045), ('xi', 0.045), ('munich', 0.045), ('balls', 0.045), ('bringing', 0.045), ('graphs', 0.043), ('ovsjanikov', 0.043), ('adoption', 0.043), ('finding', 0.042), ('derivations', 0.042), ('cartesian', 0.04), ('assignments', 0.04), ('allows', 0.04), ('monotonic', 0.039), ('adopted', 0.039), ('relax', 0.039), ('solution', 0.039), ('variables', 0.039), ('selection', 0.038), ('mapping', 0.038), ('maintaining', 0.038), ('coordinate', 0.038), ('susceptible', 0.038), ('metric', 0.037), ('tendency', 0.037), ('jp', 0.037), ('ax', 0.036), ('piecewise', 0.036), ('error', 0.036), ('minx', 0.036), ('determine', 0.035), ('ranging', 0.035), ('penalties', 0.035), ('othne', 0.035), ('cores', 0.035), ('regression', 0.035), ('iterations', 0.035), ('correspondences', 0.035), ('rn', 0.035)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999928 140 iccv-2013-Elastic Net Constraints for Shape Matching
Author: Emanuele Rodolà, Andrea Torsello, Tatsuya Harada, Yasuo Kuniyoshi, Daniel Cremers
Abstract: We consider a parametrized relaxation of the widely adopted quadratic assignment problem (QAP) formulation for minimum distortion correspondence between deformable shapes. In order to control the accuracy/sparsity trade-off we introduce a weighting parameter on the combination of two existing relaxations, namely spectral and game-theoretic. This leads to the introduction of the elastic net penalty function into shape matching problems. In combination with an efficient algorithm to project onto the elastic net ball, we obtain an approach for deformable shape matching with controllable sparsity. Experiments on a standard benchmark confirm the effectiveness of the approach.
2 0.15099253 11 iccv-2013-A Fully Hierarchical Approach for Finding Correspondences in Non-rigid Shapes
Author: Ivan Sipiran, Benjamin Bustos
Abstract: This paper presents a hierarchical method for finding correspondences in non-rigid shapes. We propose a new representation for 3D meshes: the decomposition tree. This structure characterizes the recursive decomposition process of a mesh into regions of interest and keypoints. The internal nodes contain regions of interest (which may be recursively decomposed) and the leaf nodes contain the keypoints to be matched. We also propose a hierarchical matching algorithm that performs in a level-wise manner. The matching process is guided by the similarity between regions in high levels of the tree, until reaching the keypoints stored in the leaves. This allows us to reduce the search space of correspondences, making also the matching process efficient. We evaluate the effectiveness of our approach using the SHREC’2010 robust correspondence benchmark. In addition, we show that our results outperform the state of the art.
3 0.13739817 292 iccv-2013-Non-convex P-Norm Projection for Robust Sparsity
Author: Mithun Das Gupta, Sanjeev Kumar
Abstract: In this paper, we investigate the properties of Lp norm (p ≤ 1) within a projection framework. We start with the (KpK T≤ equations of the neoctni-olnin efraarm optimization problem a thnde then use its key properties to arrive at an algorithm for Lp norm projection on the non-negative simplex. We compare with L1projection which needs prior knowledge of the true norm, as well as hard thresholding based sparsificationproposed in recent compressed sensing literature. We show performance improvements compared to these techniques across different vision applications.
4 0.13720703 139 iccv-2013-Elastic Fragments for Dense Scene Reconstruction
Author: Qian-Yi Zhou, Stephen Miller, Vladlen Koltun
Abstract: We present an approach to reconstruction of detailed scene geometry from range video. Range data produced by commodity handheld cameras suffers from high-frequency errors and low-frequency distortion. Our approach deals with both sources of error by reconstructing locally smooth scene fragments and letting these fragments deform in order to align to each other. We develop a volumetric registration formulation that leverages the smoothness of the deformation to make optimization practical for large scenes. Experimental results demonstrate that our approach substantially increases the fidelity of complex scene geometry reconstructed with commodity handheld cameras.
5 0.12461381 12 iccv-2013-A General Dense Image Matching Framework Combining Direct and Feature-Based Costs
Author: Jim Braux-Zin, Romain Dupont, Adrien Bartoli
Abstract: Dense motion field estimation (typically Romain Dupont1 romain . dupont @ cea . fr Adrien Bartoli2 adrien . bart o l @ gmai l com i . 2 ISIT, Universit e´ d’Auvergne/CNRS, France sions are explicitly modeled [32, 13]. Coarse-to-fine warping improves global convergence by making the assumption that optical flow, the motion of smaller structures is similar to the motion of stereo disparity and surface registration) is a key computer vision problem. Many solutions have been proposed to compute small or large displacements, narrow or wide baseline stereo disparity, but a unified methodology is still lacking. We here introduce a general framework that robustly combines direct and feature-based matching. The feature-based cost is built around a novel robust distance function that handles keypoints and “weak” features such as segments. It allows us to use putative feature matches which may contain mismatches to guide dense motion estimation out of local minima. Our framework uses a robust direct data term (AD-Census). It is implemented with a powerful second order Total Generalized Variation regularization with external and self-occlusion reasoning. Our framework achieves state of the art performance in several cases (standard optical flow benchmarks, wide-baseline stereo and non-rigid surface registration). Our framework has a modular design that customizes to specific application needs.
6 0.12297975 214 iccv-2013-Improving Graph Matching via Density Maximization
7 0.12077153 342 iccv-2013-Real-Time Solution to the Absolute Pose Problem with Unknown Radial Distortion and Focal Length
8 0.11283969 238 iccv-2013-Learning Graphs to Match
9 0.1120016 436 iccv-2013-Unsupervised Intrinsic Calibration from a Single Frame Using a "Plumb-Line" Approach
10 0.11166652 16 iccv-2013-A Generic Deformation Model for Dense Non-rigid Surface Registration: A Higher-Order MRF-Based Approach
11 0.1103427 283 iccv-2013-Multiple Non-rigid Surface Detection and Registration
12 0.10794901 183 iccv-2013-Geometric Registration Based on Distortion Estimation
13 0.10104082 256 iccv-2013-Locally Affine Sparse-to-Dense Matching for Motion and Occlusion Estimation
14 0.1009295 421 iccv-2013-Total Variation Regularization for Functions with Values in a Manifold
15 0.096678928 131 iccv-2013-EVSAC: Accelerating Hypotheses Generation by Modeling Matching Scores with Extreme Value Theory
16 0.094602369 346 iccv-2013-Rectangling Stereographic Projection for Wide-Angle Image Visualization
17 0.094020948 237 iccv-2013-Learning Graph Matching: Oriented to Category Modeling from Cluttered Scenes
18 0.093814582 358 iccv-2013-Robust Non-parametric Data Fitting for Correspondence Modeling
19 0.091858961 105 iccv-2013-DeepFlow: Large Displacement Optical Flow with Deep Matching
20 0.091487363 307 iccv-2013-Parallel Transport of Deformations in Shape Space of Elastic Surfaces
topicId topicWeight
[(0, 0.232), (1, -0.081), (2, -0.08), (3, -0.027), (4, -0.069), (5, 0.079), (6, 0.022), (7, -0.024), (8, 0.054), (9, -0.07), (10, -0.031), (11, 0.02), (12, -0.036), (13, 0.031), (14, 0.124), (15, 0.077), (16, 0.076), (17, 0.098), (18, 0.06), (19, -0.045), (20, 0.09), (21, 0.026), (22, -0.041), (23, -0.009), (24, 0.066), (25, -0.027), (26, 0.024), (27, 0.051), (28, -0.002), (29, -0.023), (30, 0.011), (31, -0.029), (32, -0.028), (33, 0.026), (34, 0.029), (35, -0.026), (36, 0.049), (37, -0.036), (38, 0.062), (39, -0.022), (40, 0.119), (41, -0.012), (42, 0.021), (43, 0.006), (44, -0.031), (45, 0.041), (46, 0.039), (47, -0.151), (48, -0.056), (49, 0.016)]
simIndex simValue paperId paperTitle
same-paper 1 0.96714866 140 iccv-2013-Elastic Net Constraints for Shape Matching
Author: Emanuele Rodolà, Andrea Torsello, Tatsuya Harada, Yasuo Kuniyoshi, Daniel Cremers
Abstract: We consider a parametrized relaxation of the widely adopted quadratic assignment problem (QAP) formulation for minimum distortion correspondence between deformable shapes. In order to control the accuracy/sparsity trade-off we introduce a weighting parameter on the combination of two existing relaxations, namely spectral and game-theoretic. This leads to the introduction of the elastic net penalty function into shape matching problems. In combination with an efficient algorithm to project onto the elastic net ball, we obtain an approach for deformable shape matching with controllable sparsity. Experiments on a standard benchmark confirm the effectiveness of the approach.
2 0.7445578 292 iccv-2013-Non-convex P-Norm Projection for Robust Sparsity
Author: Mithun Das Gupta, Sanjeev Kumar
Abstract: In this paper, we investigate the properties of Lp norm (p ≤ 1) within a projection framework. We start with the (KpK T≤ equations of the neoctni-olnin efraarm optimization problem a thnde then use its key properties to arrive at an algorithm for Lp norm projection on the non-negative simplex. We compare with L1projection which needs prior knowledge of the true norm, as well as hard thresholding based sparsificationproposed in recent compressed sensing literature. We show performance improvements compared to these techniques across different vision applications.
3 0.73353779 283 iccv-2013-Multiple Non-rigid Surface Detection and Registration
Author: Yi Wu, Yoshihisa Ijiri, Ming-Hsuan Yang
Abstract: Detecting and registering nonrigid surfaces are two important research problems for computer vision. Much work has been done with the assumption that there exists only one instance in the image. In this work, we propose an algorithm that detects and registers multiple nonrigid instances of given objects in a cluttered image. Specifically, after we use low level feature points to obtain the initial matches between templates and the input image, a novel high-order affinity graph is constructed to model the consistency of local topology. A hierarchical clustering approach is then used to locate the nonrigid surfaces. To remove the outliers in the cluster, we propose a deterministic annealing approach based on the Thin Plate Spline (TPS) model. The proposed method achieves high accuracy even when the number of outliers is nineteen times larger than the inliers. As the matches may appear sparsely in each instance, we propose a TPS based match growing approach to propagate the matches. Finally, an approach that fuses feature and appearance information is proposed to register each nonrigid surface. Extensive experiments and evaluations demonstrate that the proposed algorithm achieves promis- ing results in detecting and registering multiple non-rigid surfaces in a cluttered scene.
4 0.70791453 11 iccv-2013-A Fully Hierarchical Approach for Finding Correspondences in Non-rigid Shapes
Author: Ivan Sipiran, Benjamin Bustos
Abstract: This paper presents a hierarchical method for finding correspondences in non-rigid shapes. We propose a new representation for 3D meshes: the decomposition tree. This structure characterizes the recursive decomposition process of a mesh into regions of interest and keypoints. The internal nodes contain regions of interest (which may be recursively decomposed) and the leaf nodes contain the keypoints to be matched. We also propose a hierarchical matching algorithm that performs in a level-wise manner. The matching process is guided by the similarity between regions in high levels of the tree, until reaching the keypoints stored in the leaves. This allows us to reduce the search space of correspondences, making also the matching process efficient. We evaluate the effectiveness of our approach using the SHREC’2010 robust correspondence benchmark. In addition, we show that our results outperform the state of the art.
5 0.70477343 27 iccv-2013-A Robust Analytical Solution to Isometric Shape-from-Template with Focal Length Calibration
Author: Adrien Bartoli, Daniel Pizarro, Toby Collins
Abstract: We study the uncalibrated isometric Shape-fromTemplate problem, that consists in estimating an isometric deformation from a template shape to an input image whose focal length is unknown. Our method is the first that combines the following features: solving for both the 3D deformation and the camera ’s focal length, involving only local analytical solutions (there is no numerical optimization), being robust to mismatches, handling general surfaces and running extremely fast. This was achieved through two key steps. First, an ‘uncalibrated’ 3D deformation is computed thanks to a novel piecewise weak-perspective projection model. Second, the camera’s focal length is estimated and enables upgrading the 3D deformation to metric. We use a variational framework, implemented using a smooth function basis and sampled local deformation models. The only degeneracy which we easily detect– for focal length estimation is a flat and fronto-parallel surface. Experimental results on simulated and real datasets show that our method achieves a 3D shape accuracy – slightly below state of the art methods using a precalibrated or the true focal length, and a focal length accuracy slightly below static calibration methods.
6 0.69517034 183 iccv-2013-Geometric Registration Based on Distortion Estimation
7 0.68359554 16 iccv-2013-A Generic Deformation Model for Dense Non-rigid Surface Registration: A Higher-Order MRF-Based Approach
8 0.67615116 421 iccv-2013-Total Variation Regularization for Functions with Values in a Manifold
9 0.66176623 141 iccv-2013-Enhanced Continuous Tabu Search for Parameter Estimation in Multiview Geometry
10 0.65724295 200 iccv-2013-Higher Order Matching for Consistent Multiple Target Tracking
11 0.64956206 131 iccv-2013-EVSAC: Accelerating Hypotheses Generation by Modeling Matching Scores with Extreme Value Theory
12 0.61520702 185 iccv-2013-Go-ICP: Solving 3D Registration Efficiently and Globally Optimally
13 0.61020643 288 iccv-2013-Nested Shape Descriptors
14 0.60769862 353 iccv-2013-Revisiting the PnP Problem: A Fast, General and Optimal Solution
15 0.59518158 346 iccv-2013-Rectangling Stereographic Projection for Wide-Angle Image Visualization
16 0.58208382 196 iccv-2013-Hierarchical Data-Driven Descent for Efficient Optimal Deformation Estimation
17 0.57924002 56 iccv-2013-Automatic Registration of RGB-D Scans via Salient Directions
18 0.57590628 364 iccv-2013-SGTD: Structure Gradient and Texture Decorrelating Regularization for Image Decomposition
19 0.57118708 12 iccv-2013-A General Dense Image Matching Framework Combining Direct and Feature-Based Costs
20 0.57005346 139 iccv-2013-Elastic Fragments for Dense Scene Reconstruction
topicId topicWeight
[(2, 0.066), (7, 0.031), (12, 0.013), (26, 0.07), (27, 0.014), (31, 0.039), (34, 0.011), (40, 0.019), (42, 0.157), (48, 0.022), (64, 0.041), (73, 0.042), (89, 0.209), (90, 0.17), (95, 0.022), (98, 0.01)]
simIndex simValue paperId paperTitle
1 0.93043184 15 iccv-2013-A Generalized Low-Rank Appearance Model for Spatio-temporally Correlated Rain Streaks
Author: Yi-Lei Chen, Chiou-Ting Hsu
Abstract: In this paper, we propose a novel low-rank appearance model for removing rain streaks. Different from previous work, our method needs neither rain pixel detection nor time-consuming dictionary learning stage. Instead, as rain streaks usually reveal similar and repeated patterns on imaging scene, we propose and generalize a low-rank model from matrix to tensor structure in order to capture the spatio-temporally correlated rain streaks. With the appearance model, we thus remove rain streaks from image/video (and also other high-order image structure) in a unified way. Our experimental results demonstrate competitive (or even better) visual quality and efficient run-time in comparison with state of the art.
same-paper 2 0.89525646 140 iccv-2013-Elastic Net Constraints for Shape Matching
Author: Emanuele Rodolà, Andrea Torsello, Tatsuya Harada, Yasuo Kuniyoshi, Daniel Cremers
Abstract: We consider a parametrized relaxation of the widely adopted quadratic assignment problem (QAP) formulation for minimum distortion correspondence between deformable shapes. In order to control the accuracy/sparsity trade-off we introduce a weighting parameter on the combination of two existing relaxations, namely spectral and game-theoretic. This leads to the introduction of the elastic net penalty function into shape matching problems. In combination with an efficient algorithm to project onto the elastic net ball, we obtain an approach for deformable shape matching with controllable sparsity. Experiments on a standard benchmark confirm the effectiveness of the approach.
3 0.88718736 360 iccv-2013-Robust Subspace Clustering via Half-Quadratic Minimization
Author: Yingya Zhang, Zhenan Sun, Ran He, Tieniu Tan
Abstract: Subspace clustering has important and wide applications in computer vision and pattern recognition. It is a challenging task to learn low-dimensional subspace structures due to the possible errors (e.g., noise and corruptions) existing in high-dimensional data. Recent subspace clustering methods usually assume a sparse representation of corrupted errors and correct the errors iteratively. However large corruptions in real-world applications can not be well addressed by these methods. A novel optimization model for robust subspace clustering is proposed in this paper. The objective function of our model mainly includes two parts. The first part aims to achieve a sparse representation of each high-dimensional data point with other data points. The second part aims to maximize the correntropy between a given data point and its low-dimensional representation with other points. Correntropy is a robust measure so that the influence of large corruptions on subspace clustering can be greatly suppressed. An extension of our method with explicit introduction of representation error terms into the model is also proposed. Half-quadratic minimization is provided as an efficient solution to the proposed robust subspace clustering formulations. Experimental results on Hopkins 155 dataset and Extended Yale Database B demonstrate that our method outperforms state-of-the-art subspace clustering methods.
4 0.87943709 384 iccv-2013-Semi-supervised Robust Dictionary Learning via Efficient l-Norms Minimization
Author: Hua Wang, Feiping Nie, Weidong Cai, Heng Huang
Abstract: Representing the raw input of a data set by a set of relevant codes is crucial to many computer vision applications. Due to the intrinsic sparse property of real-world data, dictionary learning, in which the linear decomposition of a data point uses a set of learned dictionary bases, i.e., codes, has demonstrated state-of-the-art performance. However, traditional dictionary learning methods suffer from three weaknesses: sensitivity to noisy and outlier samples, difficulty to determine the optimal dictionary size, and incapability to incorporate supervision information. In this paper, we address these weaknesses by learning a Semi-Supervised Robust Dictionary (SSR-D). Specifically, we use the ℓ2,0+ norm as the loss function to improve the robustness against outliers, and develop a new structured sparse regularization com, , tom. . cai@sydney . edu . au , heng@uta .edu make the learning tasks easier to deal with and reduce the computational cost. For example, in image tagging, instead of using the raw pixel-wise features, semi-local or patch- based features, such as SIFT and geometric blur, are usually more desirable to achieve better performance. In practice, finding a set of compact features bases, also referred to as dictionary, with enhanced representative and discriminative power, plays a significant role in building a successful computer vision system. In this paper, we explore this important problem by proposing a novel formulation and its solution for learning Semi-Supervised Robust Dictionary (SSRD), where we examine the challenges in dictionary learning, and seek opportunities to overcome them and improve the dictionary qualities. 1.1. Challenges in Dictionary Learning to incorporate the supervision information in dictionary learning, without incurring additional parameters. Moreover, the optimal dictionary size is automatically learned from the input data. Minimizing the derived objective function is challenging because it involves many non-smooth ℓ2,0+ -norm terms. We present an efficient algorithm to solve the problem with a rigorous proof of the convergence of the algorithm. Extensive experiments are presented to show the superior performance of the proposed method.
5 0.87888491 341 iccv-2013-Real-Time Body Tracking with One Depth Camera and Inertial Sensors
Author: Thomas Helten, Meinard Müller, Hans-Peter Seidel, Christian Theobalt
Abstract: In recent years, the availability of inexpensive depth cameras, such as the Microsoft Kinect, has boosted the research in monocular full body skeletal pose tracking. Unfortunately, existing trackers often fail to capture poses where a single camera provides insufficient data, such as non-frontal poses, and all other poses with body part occlusions. In this paper, we present a novel sensor fusion approach for real-time full body tracking that succeeds in such difficult situations. It takes inspiration from previous tracking solutions, and combines a generative tracker and a discriminative tracker retrieving closest poses in a database. In contrast to previous work, both trackers employ data from a low number of inexpensive body-worn inertial sensors. These sensors provide reliable and complementary information when the monocular depth information alone is not sufficient. We also contribute by new algorithmic solutions to best fuse depth and inertial data in both trackers. One is a new visibility model to determine global body pose, occlusions and usable depth correspondences and to decide what data modality to use for discriminative tracking. We also contribute with a new inertial-basedpose retrieval, and an adapted late fusion step to calculate the final body pose.
6 0.85483515 159 iccv-2013-Fast Neighborhood Graph Search Using Cartesian Concatenation
7 0.85022962 79 iccv-2013-Coherent Object Detection with 3D Geometric Context from a Single Image
8 0.8493548 26 iccv-2013-A Practical Transfer Learning Algorithm for Face Verification
9 0.84874415 208 iccv-2013-Image Co-segmentation via Consistent Functional Maps
10 0.84822291 182 iccv-2013-GOSUS: Grassmannian Online Subspace Updates with Structured-Sparsity
11 0.84655005 328 iccv-2013-Probabilistic Elastic Part Model for Unsupervised Face Detector Adaptation
12 0.8461706 157 iccv-2013-Fast Face Detector Training Using Tailored Views
13 0.8460747 391 iccv-2013-Sieving Regression Forest Votes for Facial Feature Detection in the Wild
14 0.84582549 45 iccv-2013-Affine-Constrained Group Sparse Coding and Its Application to Image-Based Classifications
15 0.84575593 187 iccv-2013-Group Norm for Learning Structured SVMs with Unstructured Latent Variables
16 0.84560597 232 iccv-2013-Latent Space Sparse Subspace Clustering
17 0.84538794 259 iccv-2013-Manifold Based Face Synthesis from Sparse Samples
18 0.84531355 106 iccv-2013-Deep Learning Identity-Preserving Face Space
19 0.84526783 97 iccv-2013-Coupling Alignments with Recognition for Still-to-Video Face Recognition
20 0.84511828 206 iccv-2013-Hybrid Deep Learning for Face Verification