cvpr cvpr2013 cvpr2013-448 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: unkown-author
Abstract: We show that solving the LP relaxation of the MAP inference problem in graphical models (also known as the minsum problem, energy minimization, or weighted constraint satisfaction) is not easier than solving any LP. More precisely, any polytope is linear-time representable by a local marginal polytope and any LP can be reduced in linear time to a linear optimization (allowing infinite weights) over a local marginal polytope.
Reference: text
sentIndex sentText sentNum sentScore
1 c z Abstract We show that solving the LP relaxation of the MAP inference problem in graphical models (also known as the minsum problem, energy minimization, or weighted constraint satisfaction) is not easier than solving any LP. [sent-4, score-0.164]
2 More precisely, any polytope is linear-time representable by a local marginal polytope and any LP can be reduced in linear time to a linear optimization (allowing infinite weights) over a local marginal polytope. [sent-5, score-1.812]
3 This NP-complete combinatorial optimization problem occurs in MAP inference in graphical models [10], and is also known as energy minimization or weighted constraint satisfaction [3]. [sent-8, score-0.126]
4 While the exact min-sum problem is equivalent to linear optimization over the marginal polytope, the LP relaxation approximates this polytope by its outer bound, known as the local marginal polytope [10]. [sent-10, score-1.754]
5 We show that linear optimization over the local marginal polytope is in certain sense not easier than any linear program. [sent-11, score-0.898]
6 Every polytope is (up to scale) a coordinateerasing projection of a face of a local marginal polytope with 3 labels, whose description can be computed from the description of the original polytope in linear time. [sent-14, score-1.936]
7 Any linear program can be reduced in linear time to a linear optimization (allowinginfinite weights) over a local marginal polytope with 3 labels. [sent-30, score-1.09]
8 While Theorem 2 immediately follows from Theorem 1, the situation is more complex when infinite weights in the min-sum problem are not allowed. [sent-31, score-0.13]
9 Similar universality result are known also for other polytopes, such as the three-way transportation polytope [4]. [sent-33, score-0.637]
10 The most important consequence of our result is that it imposes a practical constraint on complexity of any algorithm to solve the LP relaxation of the min-sum problem. [sent-34, score-0.23]
11 Designing a very efficient such algorithm might mean improving complexity (time complexity, or a combination of × space and time complexity) of the best known algorithm for general linear programming, which is unlikely. [sent-35, score-0.129]
12 The local marginal polytope Let V be a finite set of objects and E ⊆ ? [sent-37, score-0.809]
13 (1) where the functions gu: K → R and guv: K K → R are unary and pairwise :i Knter →act Rion as,n dR g = R K K∪ × {∞ K} →, →an Rd we adopt t ahnadt guv (rwk,i s? [sent-48, score-0.372]
14 RW =e w Ril ∪ ∪re {f∞er }to, atnhed values of gu and guv as weigths. [sent-51, score-0.269]
15 The values of all gu and guv together will be understood as a vector g ∈ with I { (u, k) | u ∈ V, k ∈ K } ∪ = { {(u, k), (v, ? [sent-52, score-0.269]
16 The local marginal polytope is defined by a triplet (V, E, K). [sent-67, score-0.816]
17 Now the LP relaxation of problem (1) reads Λ∗(g) = arμg∈mΛin? [sent-68, score-0.103]
18 The input polyhedron The input polyhedron is assumed to have the form P = { x = (x1, . [sent-82, score-0.322]
19 Any convex polyhedron that can be represented by a fi ≤nit en . [sent-89, score-0.161]
20 In the i-th equation ai1x1 + · · · + ainxn = bi (6) it is assumed that bi ≥ 0 (ifnot, multiply the whole equation by −1). [sent-92, score-0.25]
21 Precisely, (6) is rewritten as ai+1x1 + · · · + ai+nxn = ai−1x1 + · · · + ai−nxn + bi (7) where ai+j ≥ 0, ai−j ≥ 0, and aij = ai+j − ai−j. [sent-95, score-0.113]
22 If ai−1 = ··· = ai−n = bi = 0 and ai+j > 0 then inevitably xj = 0= an ··d· th =u sa xj can be eliminated from (5). [sent-97, score-0.214]
23 It is well-known from the simplex algorithm that every vertex x of the polyhedron is a solution of a system A? [sent-144, score-0.256]
24 edron P is bounded then for every x ∈ P, each side of equation (7) is not greater than n? [sent-186, score-0.217]
25 , xn) ∈ P is a convex combination of the vertices of P, hence), by PLem ism aa c o4,n veeaxch c xj bsaintiastfiioens xj ≤ M. [sent-195, score-0.169]
26 Encoding In this section we prove Theorem 1 by giving a lineartime algorithm to encode the polyhedron P as a face of a local marginal polytope. [sent-200, score-0.463]
27 Its output is a min-sum problem (V, E, K, g) with |K| = 3 loaubteplust tan isd aw mithin weights gu (lekm) = ( V0, fEor, Kall, u )∈ wVit ahn |dK Kk| |∈ = =K 3, and guv (k, ? [sent-204, score-0.317]
28 In the sequel, only a subset of the nine edges between two objects are shown, where the visible edges have weight guv (k, ? [sent-229, score-0.224]
29 ) = 0 and the invisible edges have weight guv (k, ? [sent-230, score-0.224]
30 Elementary constructions The encoding algorithm uses several elementary constructions as its building blocks. [sent-234, score-0.284]
31 Precisely, Eif w a, bile, c, md,p e, ifn g≥ n 0o aonthde a +on bs t+ra c =s 1n b=, d, e+, e + Pr efc, stheleyn, tihf aer,eb ,exc,isdt, pairwise pseudomarginals satisfying (3) if and only if a = d. [sent-236, score-0.327]
32 eEalsch k n∈od Ke aiss assigned a unary pseudomarginal μu (k) a ansd eedagcehs edge cish assigned a pairwise pseudomarginal μuv (k, ? [sent-242, score-0.428]
33 One constraint (3b) imposes for unary pseudomarginals a, b, c that a + b + c = 1. [sent-244, score-0.466]
34 One constraint (3a) imposes for pairwise pseudomarginals p, q, r that a = p + q + r. [sent-245, score-0.412]
35 ADDITION, Figure 2(b), adds two unary pseudomarginals a, b in one object and represents the result as a unary pseudomarginal c = a+b in another object. [sent-246, score-0.622]
36 No other constraints are imposed on the remaining unary pseudomarginals. [sent-247, score-0.101]
37 EQUALITY, Figure 2(c), enforces equality of two unary pseudomarginals a, b in a single object, introducing two auxiliary objects. [sent-248, score-0.456]
38 No other constraints are imposed on the remaining unary pseudomarginals. [sent-249, score-0.101]
39 In the sequel, this construction will be abbreviated by omitting the two auxiliary objects and writing the equality sign between the two nodes, as in Figure 2(d). [sent-250, score-0.075]
40 POWERS, Figure 2(e), creates the sequence of unary pseudomarginals with values 2ia for i = 0, . [sent-251, score-0.408]
41 Figure 3 shows an example of how the elementary constructions can be combined. [sent-260, score-0.136]
42 The algorithm Now we describe the whole encoding algorithm. [sent-263, score-0.088]
43 For each variable xj in (5), introduce a new object j into V . [sent-272, score-0.06]
44 The variable xj will be represented by pseudomarginal μj (1). [sent-273, score-0.2]
45 The choice of d ensures that all values that have to be represented by pseudomarginals will be bounded by 1. [sent-291, score-0.422]
46 Then the algorithm proceeds by encoding each equation (7) in turn. [sent-292, score-0.128]
47 Construct pseudomarginals with values ai+jxj, ai−jxj by summing selected values from the powers built in Step 2 of the initialization, similarly as in Figure 3. [sent-300, score-0.438]
48 Construct a pseudomarginal with value 2−dbi by summing selected values from the negative powers built in 111777334088 Step 3 of the initialization, similarly as in Figure 3. [sent-302, score-0.298]
49 The value 2−dbi represents bi, which sets the scale between the input and output polytope to 2−d. [sent-303, score-0.521]
50 Represent each side of the equation by summing all its terms by repetitively applying ADDITION and COPY. [sent-305, score-0.074]
51 Apply COPY to enforce equality of the two sides of the equation. [sent-307, score-0.075]
52 When the algorithm finishes, the output min-sum problem encodes the (nonempty) input polytope as P = π(Λ∗ (g)) (10) where π: RI → Rn is the scaled coordinate-erasing projection given by (x1, . [sent-308, score-0.521]
53 (11) Figure 4 shows the output min-sum problem for an example polytope P. [sent-315, score-0.521]
54 The length of the encoding Here we finish the proof of Theorem 1 by showing that the encoding time is linear in the length L of the description of the input polyhedron P. [sent-318, score-0.492]
55 Since this time is obviously1 linear in |E|, it suffices to show that |E| = O(L). [sent-319, score-0.091]
56 Object pairs are ccresea ttoed s only hwath |eEn an object is created and the number of object pairs added with one object is always bounded by a constant. [sent-320, score-0.142]
57 Finally, encoding one equality n(u7)m abdedrss aatr em Oos(Lt as many objects as there are bits in the binary representation of all its coefficients. [sent-335, score-0.163]
58 Reducing a linear program to linear optimization over a local marginal polytope In this section we show how to efficiently reduce any linear program to linear optimization over a local marginal polytope. [sent-338, score-1.443]
59 By saying that problem A can be reduced to problem B we mean there is an oracle to solve problem B which 1 The only thing that may not be obvious is how to multiply large integers a, b in linear time. [sent-339, score-0.225]
60 , which can be done in linear time using bitwise operations. [sent-344, score-0.058]
61 We further assume that if problem B is a linear program then the oracle returns both an optimal argument and the optimal value. [sent-348, score-0.189]
62 The input linear program is assumed to have the form P∗(c) = arxg∈mPin? [sent-349, score-0.142]
63 The encoding in §4 can be applied only t ∈o a bounded polyhedron oPd nbugt tihne § L4P c (a1n3 )b can bpel uednb oonulnyde tod. [sent-355, score-0.391]
64 Everylinearprogram (13) can be reducedin linear time to a linear program over a bounded polyhedron. [sent-358, score-0.342]
65 (14) Each side of (14) is a linear program over a bounded polyhedron. [sent-373, score-0.284]
66 The linear programs (14) are infeasible if and only if (13) is infeasible. [sent-375, score-0.103]
67 The description length of numbers nM and 2nM is O(L), thus the reduction is done in linear time. [sent-376, score-0.12]
68 By Lemma 6 and Theorem 1, any linear program (13) can be reduced in linear time to optimizing a linear function over a face of Λ. [sent-378, score-0.308]
69 Given an oracle to optimize a linear function over Λ, it may seem unclear how to optimize a linear function over a face of Λ. [sent-379, score-0.163]
70 But this can be done by setting some pairwise weights to a large constant, g∞. [sent-380, score-0.095]
71 ) be the min-sum problem encoding P, as constructed in §4. [sent-382, score-0.088]
72 are precisely those that represent the varitahbelepsr xi uocft t? [sent-397, score-0.047]
73 s e Wteh assume ehnetreth tehavta rPi111777334199 is bounded and non-empty; recall that the case P = ∅ is i nsd bicoauntedde by minμ∈Λ ? [sent-399, score-0.142]
74 situation is different depending on whether we are allowed to use infinite weights (components of g) or not. [sent-406, score-0.13]
75 If infinite weights are allowed, we simply set g∞ = ∞. [sent-407, score-0.13]
76 If infinite weights are nhoits aplrloovweesd T, g∞ emmu s2t. [sent-409, score-0.13]
77 To prove it, we need Lemma 7, which refines Lemma 4 for the special case of the local marginal polytope. [sent-413, score-0.302]
78 Let Λ be a local marginal polytope given by a triplet (V, E, K) where |K| = 3. [sent-415, score-0.816]
79 Any linear program (13) can be reduced in time and space O(L(L + L? [sent-435, score-0.192]
80 )) to a linear optimization (allowing only fcieni Ote( weights) over a local marginal polytope with 3 labels, where L? [sent-436, score-0.84]
81 ) be the min-sum problem encoding P, where we assume that P is bounded and non-empty. [sent-440, score-0.23]
82 To prove this, we need to show that every μ ∈ Λ∗ (g) satisfies μij (k, ? [sent-447, score-0.076]
83 ∈It Λ Λsuffices to show this only for the vertices of Λ∗ (g) because taking a convex combination cannot violate the condition μij (k, ? [sent-450, score-0.049]
84 Our last theorem specifies a class of linear programs that can be reduced in strongly polynomial time to the LP relaxation of a min-sum problem. [sent-481, score-0.518]
85 Every linear program (13) where A ∈ {−1, 0, 1}m×n and b ∈ {−1, 0, 1}m can be reduced i∈n strongly polynomial tbim ∈e ∈to { a 1li,n0ea,r1 optimization over a lo- cal marginal polytope. [sent-483, score-0.57]
86 ice B)o an equation iwnehoasre p rboi-nary length is O(n + m log m). [sent-488, score-0.075]
87 Most importantly, it shows that solving the LP relaxation of a pairwise min-sum problem is comparably hard as solving any LP. [sent-495, score-0.15]
88 Then, by Theorem 2, the reduction is done in time O(L), while the best known algorithm [5] for general LP hOa(sL ti)m, ew complexity tO k(nno3w. [sent-497, score-0.071]
89 Finding a very fimaset algorithm, ysu Och(n as O(L2 log L), to solve LP relaxavteiroyn oasft tm align-orsiuthmm problems (Ow(hLich permit infinite weights) would imply improving the best-known complexity of LP. [sent-499, score-0.151]
90 Our result makes more precise the known observation that local marginal polytopes with |K| = 3 labels are more complex lt mhaanr gthinoasle p owliythto 2p lsab weiltsh. [sent-500, score-0.472]
91 Any pairwise amrein- msuomre problem with 2 labels can be reduced in linear time to a quadratic pseudoboolean optimization problem, whose LP relaxation can be reduced in linear time to a max-flow problem [1, 8], which has a lower best known complexity than a general LP. [sent-501, score-0.464]
92 Local marginal polytopes with 2 labels have half-integral vertices (i. [sent-502, score-0.446]
93 , all components of the vertices are in {0, 21 , 1}) [6, 11], while the components of the vertices of lionc {a0l marginal polytopes ew tihteh c3o lmabpeolsn can oh afv tehe em vuecrthic more general values, as indicated by Figure 4. [sent-504, score-0.518]
94 Moreover, there seems to be not much difference in complexity between local marginal polytopes with 3 labels and those with 4 or more labels. [sent-505, score-0.439]
95 When solving the LP relaxation of a min-sum problem by the simplex algorithm, due to high degeneracy of the local marginal polytope the simplex algorithm sometimes stays in a single basic solution for a very large number of iterations, only changing degenerate bases (this is known as stalling). [sent-506, score-1.034]
96 Finding a pivoting rule that would guarantee no stalling would imply this rule is applicable to any LP. [sent-507, score-0.141]
97 Approximation algorithms for the metric labeling problem via a new linear programming formulation. [sent-522, score-0.058]
98 All linear and integer programs are slim 3-way transportation programs. [sent-535, score-0.14]
99 The partial constraint satisfaction problem: Facets and lifting theorems. [sent-552, score-0.097]
100 A linear programming approach to max-sum problem: A review. [sent-578, score-0.058]
wordName wordTfidf (topN-words)
[('polytope', 0.521), ('pseudomarginals', 0.28), ('marginal', 0.261), ('guv', 0.224), ('lp', 0.182), ('polyhedron', 0.161), ('theorem', 0.145), ('bounded', 0.142), ('pseudomarginal', 0.14), ('lemma', 0.131), ('powers', 0.124), ('ai', 0.112), ('polytopes', 0.109), ('relaxation', 0.103), ('unary', 0.101), ('encoding', 0.088), ('gij', 0.087), ('uv', 0.086), ('program', 0.084), ('det', 0.082), ('infinite', 0.082), ('elementary', 0.076), ('equality', 0.075), ('polynomial', 0.07), ('aj', 0.069), ('bi', 0.068), ('satisfaction', 0.065), ('xj', 0.06), ('constructions', 0.06), ('simplex', 0.06), ('linear', 0.058), ('czech', 0.058), ('jxj', 0.056), ('mhin', 0.056), ('negpowers', 0.056), ('bj', 0.056), ('dk', 0.054), ('imposes', 0.053), ('copy', 0.053), ('ij', 0.052), ('dbi', 0.05), ('nxn', 0.05), ('universality', 0.05), ('detu', 0.05), ('stalling', 0.05), ('reduced', 0.05), ('vertices', 0.049), ('weights', 0.048), ('strongly', 0.047), ('precisely', 0.047), ('oracle', 0.047), ('pairwise', 0.047), ('lsab', 0.046), ('programs', 0.045), ('aij', 0.045), ('gu', 0.045), ('republic', 0.043), ('complexity', 0.042), ('prove', 0.041), ('dj', 0.041), ('equation', 0.04), ('arithmetic', 0.04), ('sequel', 0.037), ('ku', 0.037), ('transportation', 0.037), ('min', 0.037), ('mn', 0.037), ('inequality', 0.037), ('integers', 0.036), ('nm', 0.035), ('zm', 0.035), ('length', 0.035), ('every', 0.035), ('multiply', 0.034), ('triplet', 0.034), ('ov', 0.034), ('summing', 0.034), ('suffices', 0.033), ('xn', 0.033), ('rule', 0.032), ('ic', 0.032), ('constraint', 0.032), ('rn', 0.032), ('bm', 0.03), ('known', 0.029), ('ri', 0.029), ('er', 0.028), ('ec', 0.028), ('bn', 0.027), ('labels', 0.027), ('nu', 0.027), ('imply', 0.027), ('description', 0.027), ('whenever', 0.027), ('creates', 0.027), ('finite', 0.027), ('inevitably', 0.026), ('bounds', 0.026), ('isn', 0.026), ('components', 0.025)]
simIndex simValue paperId paperTitle
same-paper 1 1.000001 448 cvpr-2013-Universality of the Local Marginal Polytope
Author: unkown-author
Abstract: We show that solving the LP relaxation of the MAP inference problem in graphical models (also known as the minsum problem, energy minimization, or weighted constraint satisfaction) is not easier than solving any LP. More precisely, any polytope is linear-time representable by a local marginal polytope and any LP can be reduced in linear time to a linear optimization (allowing infinite weights) over a local marginal polytope.
2 0.1187699 6 cvpr-2013-A Comparative Study of Modern Inference Techniques for Discrete Energy Minimization Problems
Author: Jörg H. Kappes, Bjoern Andres, Fred A. Hamprecht, Christoph Schnörr, Sebastian Nowozin, Dhruv Batra, Sungwoong Kim, Bernhard X. Kausler, Jan Lellmann, Nikos Komodakis, Carsten Rother
Abstract: Seven years ago, Szeliski et al. published an influential study on energy minimization methods for Markov random fields (MRF). This study provided valuable insights in choosing the best optimization technique for certain classes of problems. While these insights remain generally useful today, the phenominal success of random field models means that the kinds of inference problems we solve have changed significantly. Specifically, the models today often include higher order interactions, flexible connectivity structures, large label-spaces of different cardinalities, or learned energy tables. To reflect these changes, we provide a modernized and enlarged study. We present an empirical comparison of 24 state-of-art techniques on a corpus of 2,300 energy minimization instances from 20 diverse computer vision applications. To ensure reproducibility, we evaluate all methods in the OpenGM2 framework and report extensive results regarding runtime and solution quality. Key insights from our study agree with the results of Szeliski et al. for the types of models they studied. However, on new and challenging types of models our findings disagree and suggest that polyhedral methods and integer programming solvers are competitive in terms of runtime and solution quality over a large range of model types.
3 0.11302853 128 cvpr-2013-Discrete MRF Inference of Marginal Densities for Non-uniformly Discretized Variable Space
Author: Masaki Saito, Takayuki Okatani, Koichiro Deguchi
Abstract: This paper is concerned with the inference of marginal densities based on MRF models. The optimization algorithmsfor continuous variables are only applicable to a limited number of problems, whereas those for discrete variables are versatile. Thus, it is quite common to convert the continuous variables into discrete ones for the problems that ideally should be solved in the continuous domain, such as stereo matching and optical flow estimation. In this paper, we show a novel formulation for this continuous-discrete conversion. The key idea is to estimate the marginal densities in the continuous domain by approximating them with mixtures of rectangular densities. Based on this formulation, we derive a mean field (MF) algorithm and a belief propagation (BP) algorithm. These algorithms can correctly handle the case where the variable space is discretized in a non-uniform manner. By intentionally using such a non-uniform discretization, a higher balance between computational efficiency and accuracy of marginal density estimates could be achieved. We present a method for actually doing this, which dynamically discretizes the variable space in a coarse-to-fine manner in the course of the computation. Experimental results show the effectiveness of our approach.
Author: Jörg Hendrik Kappes, Markus Speth, Gerhard Reinelt, Christoph Schnörr
Abstract: Discrete graphical models (also known as discrete Markov random fields) are a major conceptual tool to model the structure of optimization problems in computer vision. While in the last decade research has focused on fast approximative methods, algorithms that provide globally optimal solutions have come more into the research focus in the last years. However, large scale computer vision problems seemed to be out of reach for such methods. In this paper we introduce a promising way to bridge this gap based on partial optimality and structural properties of the underlying problem factorization. Combining these preprocessing steps, we are able to solve grids of size 2048 2048 in less than 90 seconds. On the hitherto unsolva2b04le8 C×h2i0ne4s8e character dataset of Nowozin et al. we obtain provably optimal results in 56% of the instances and achieve competitive runtimes on other recent benchmark problems. While in the present work only generalized Potts models are considered, an extension to general graphical models seems to be feasible.
5 0.07383883 317 cvpr-2013-Optimal Geometric Fitting under the Truncated L2-Norm
Author: Erik Ask, Olof Enqvist, Fredrik Kahl
Abstract: This paper is concerned with model fitting in the presence of noise and outliers. Previously it has been shown that the number of outliers can be minimized with polynomial complexity in the number of measurements. This paper improves on these results in two ways. First, it is shown that for a large class of problems, the statistically more desirable truncated L2-norm can be optimized with the same complexity. Then, with the same methodology, it is shown how to transform multi-model fitting into a purely combinatorial problem—with worst-case complexity that is polynomial in the number of measurements, though exponential in the number of models. We apply our framework to a series of hard registration and stitching problems demonstrating that the approach is not only of theoretical interest. It gives a practical method for simultaneously dealing with measurement noise and large amounts of outliers for fitting problems with lowdimensional models.
6 0.072894685 24 cvpr-2013-A Principled Deep Random Field Model for Image Segmentation
7 0.06738583 62 cvpr-2013-Bilinear Programming for Human Activity Recognition with Unknown MRF Graphs
8 0.060361378 247 cvpr-2013-Learning Class-to-Image Distance with Object Matchings
9 0.060009234 23 cvpr-2013-A Practical Rank-Constrained Eight-Point Algorithm for Fundamental Matrix Estimation
10 0.059095532 165 cvpr-2013-Fast Energy Minimization Using Learned State Filters
11 0.05769996 180 cvpr-2013-Fully-Connected CRFs with Non-Parametric Pairwise Potential
12 0.054952797 95 cvpr-2013-Continuous Inference in Graphical Models with Polynomial Energies
13 0.054793499 300 cvpr-2013-Multi-target Tracking by Lagrangian Relaxation to Min-cost Network Flow
14 0.053862881 230 cvpr-2013-Joint 3D Scene Reconstruction and Class Segmentation
16 0.051296268 423 cvpr-2013-Template-Based Isometric Deformable 3D Reconstruction with Sampling-Based Focal Length Self-Calibration
17 0.049770731 20 cvpr-2013-A New Model and Simple Algorithms for Multi-label Mumford-Shah Problems
18 0.049693275 156 cvpr-2013-Exploring Compositional High Order Pattern Potentials for Structured Output Learning
19 0.049577329 404 cvpr-2013-Sparse Quantization for Patch Description
20 0.049129844 8 cvpr-2013-A Fast Approximate AIB Algorithm for Distributional Word Clustering
topicId topicWeight
[(0, 0.119), (1, 0.023), (2, -0.013), (3, 0.022), (4, 0.046), (5, -0.003), (6, -0.009), (7, -0.025), (8, -0.045), (9, -0.002), (10, 0.053), (11, 0.012), (12, -0.06), (13, -0.001), (14, -0.061), (15, 0.033), (16, 0.002), (17, 0.042), (18, 0.084), (19, -0.01), (20, -0.073), (21, -0.018), (22, -0.023), (23, 0.058), (24, 0.09), (25, 0.033), (26, -0.083), (27, 0.068), (28, -0.02), (29, -0.018), (30, 0.062), (31, 0.048), (32, 0.077), (33, -0.027), (34, -0.043), (35, -0.024), (36, 0.041), (37, -0.001), (38, -0.013), (39, -0.012), (40, 0.026), (41, 0.036), (42, -0.0), (43, -0.027), (44, 0.017), (45, 0.04), (46, 0.05), (47, -0.047), (48, -0.013), (49, -0.035)]
simIndex simValue paperId paperTitle
same-paper 1 0.94496441 448 cvpr-2013-Universality of the Local Marginal Polytope
Author: unkown-author
Abstract: We show that solving the LP relaxation of the MAP inference problem in graphical models (also known as the minsum problem, energy minimization, or weighted constraint satisfaction) is not easier than solving any LP. More precisely, any polytope is linear-time representable by a local marginal polytope and any LP can be reduced in linear time to a linear optimization (allowing infinite weights) over a local marginal polytope.
2 0.83453578 95 cvpr-2013-Continuous Inference in Graphical Models with Polynomial Energies
Author: Mathieu Salzmann
Abstract: In this paper, we tackle the problem of performing inference in graphical models whose energy is a polynomial function of continuous variables. Our energy minimization method follows a dual decomposition approach, where the global problem is split into subproblems defined over the graph cliques. The optimal solution to these subproblems is obtained by making use of a polynomial system solver. Our algorithm inherits the convergence guarantees of dual decomposition. To speed up optimization, we also introduce a variant of this algorithm based on the augmented Lagrangian method. Our experiments illustrate the diversity of computer vision problems that can be expressed with polynomial energies, and demonstrate the benefits of our approach over existing continuous inference methods.
Author: Jörg Hendrik Kappes, Markus Speth, Gerhard Reinelt, Christoph Schnörr
Abstract: Discrete graphical models (also known as discrete Markov random fields) are a major conceptual tool to model the structure of optimization problems in computer vision. While in the last decade research has focused on fast approximative methods, algorithms that provide globally optimal solutions have come more into the research focus in the last years. However, large scale computer vision problems seemed to be out of reach for such methods. In this paper we introduce a promising way to bridge this gap based on partial optimality and structural properties of the underlying problem factorization. Combining these preprocessing steps, we are able to solve grids of size 2048 2048 in less than 90 seconds. On the hitherto unsolva2b04le8 C×h2i0ne4s8e character dataset of Nowozin et al. we obtain provably optimal results in 56% of the instances and achieve competitive runtimes on other recent benchmark problems. While in the present work only generalized Potts models are considered, an extension to general graphical models seems to be feasible.
4 0.76650226 6 cvpr-2013-A Comparative Study of Modern Inference Techniques for Discrete Energy Minimization Problems
Author: Jörg H. Kappes, Bjoern Andres, Fred A. Hamprecht, Christoph Schnörr, Sebastian Nowozin, Dhruv Batra, Sungwoong Kim, Bernhard X. Kausler, Jan Lellmann, Nikos Komodakis, Carsten Rother
Abstract: Seven years ago, Szeliski et al. published an influential study on energy minimization methods for Markov random fields (MRF). This study provided valuable insights in choosing the best optimization technique for certain classes of problems. While these insights remain generally useful today, the phenominal success of random field models means that the kinds of inference problems we solve have changed significantly. Specifically, the models today often include higher order interactions, flexible connectivity structures, large label-spaces of different cardinalities, or learned energy tables. To reflect these changes, we provide a modernized and enlarged study. We present an empirical comparison of 24 state-of-art techniques on a corpus of 2,300 energy minimization instances from 20 diverse computer vision applications. To ensure reproducibility, we evaluate all methods in the OpenGM2 framework and report extensive results regarding runtime and solution quality. Key insights from our study agree with the results of Szeliski et al. for the types of models they studied. However, on new and challenging types of models our findings disagree and suggest that polyhedral methods and integer programming solvers are competitive in terms of runtime and solution quality over a large range of model types.
5 0.75415981 128 cvpr-2013-Discrete MRF Inference of Marginal Densities for Non-uniformly Discretized Variable Space
Author: Masaki Saito, Takayuki Okatani, Koichiro Deguchi
Abstract: This paper is concerned with the inference of marginal densities based on MRF models. The optimization algorithmsfor continuous variables are only applicable to a limited number of problems, whereas those for discrete variables are versatile. Thus, it is quite common to convert the continuous variables into discrete ones for the problems that ideally should be solved in the continuous domain, such as stereo matching and optical flow estimation. In this paper, we show a novel formulation for this continuous-discrete conversion. The key idea is to estimate the marginal densities in the continuous domain by approximating them with mixtures of rectangular densities. Based on this formulation, we derive a mean field (MF) algorithm and a belief propagation (BP) algorithm. These algorithms can correctly handle the case where the variable space is discretized in a non-uniform manner. By intentionally using such a non-uniform discretization, a higher balance between computational efficiency and accuracy of marginal density estimates could be achieved. We present a method for actually doing this, which dynamically discretizes the variable space in a coarse-to-fine manner in the course of the computation. Experimental results show the effectiveness of our approach.
6 0.71644932 24 cvpr-2013-A Principled Deep Random Field Model for Image Segmentation
7 0.70341742 308 cvpr-2013-Nonlinearly Constrained MRFs: Exploring the Intrinsic Dimensions of Higher-Order Cliques
8 0.66919345 51 cvpr-2013-Auxiliary Cuts for General Classes of Higher Order Functionals
9 0.64743847 23 cvpr-2013-A Practical Rank-Constrained Eight-Point Algorithm for Fundamental Matrix Estimation
10 0.64099002 262 cvpr-2013-Learning for Structured Prediction Using Approximate Subgradient Descent with Working Sets
11 0.63535601 62 cvpr-2013-Bilinear Programming for Human Activity Recognition with Unknown MRF Graphs
12 0.62097651 41 cvpr-2013-An Iterated L1 Algorithm for Non-smooth Non-convex Optimization in Computer Vision
13 0.61329556 9 cvpr-2013-A Fast Semidefinite Approach to Solving Binary Quadratic Problems
14 0.60311586 171 cvpr-2013-Fast Trust Region for Segmentation
15 0.5736503 20 cvpr-2013-A New Model and Simple Algorithms for Multi-label Mumford-Shah Problems
16 0.57149088 165 cvpr-2013-Fast Energy Minimization Using Learned State Filters
17 0.56207961 317 cvpr-2013-Optimal Geometric Fitting under the Truncated L2-Norm
18 0.55732137 466 cvpr-2013-Whitened Expectation Propagation: Non-Lambertian Shape from Shading and Shadow
19 0.54831451 180 cvpr-2013-Fully-Connected CRFs with Non-Parametric Pairwise Potential
20 0.53101164 184 cvpr-2013-Gauging Association Patterns of Chromosome Territories via Chromatic Median
topicId topicWeight
[(10, 0.097), (16, 0.035), (25, 0.077), (26, 0.065), (28, 0.024), (33, 0.233), (67, 0.042), (69, 0.058), (71, 0.139), (77, 0.013), (87, 0.071), (96, 0.022)]
simIndex simValue paperId paperTitle
1 0.89678001 385 cvpr-2013-Selective Transfer Machine for Personalized Facial Action Unit Detection
Author: Wen-Sheng Chu, Fernando De La Torre, Jeffery F. Cohn
Abstract: Automatic facial action unit (AFA) detection from video is a long-standing problem in facial expression analysis. Most approaches emphasize choices of features and classifiers. They neglect individual differences in target persons. People vary markedly in facial morphology (e.g., heavy versus delicate brows, smooth versus deeply etched wrinkles) and behavior. Individual differences can dramatically influence how well generic classifiers generalize to previously unseen persons. While a possible solution would be to train person-specific classifiers, that often is neither feasible nor theoretically compelling. The alternative that we propose is to personalize a generic classifier in an unsupervised manner (no additional labels for the test subjects are required). We introduce a transductive learning method, which we refer to Selective Transfer Machine (STM), to personalize a generic classifier by attenuating person-specific biases. STM achieves this effect by simultaneously learning a classifier and re-weighting the training samples that are most relevant to the test subject. To evaluate the effectiveness of STM, we compared STM to generic classifiers and to cross-domain learning methods in three major databases: CK+ [20], GEMEP-FERA [32] and RU-FACS [2]. STM outperformed generic classifiers in all.
same-paper 2 0.89612222 448 cvpr-2013-Universality of the Local Marginal Polytope
Author: unkown-author
Abstract: We show that solving the LP relaxation of the MAP inference problem in graphical models (also known as the minsum problem, energy minimization, or weighted constraint satisfaction) is not easier than solving any LP. More precisely, any polytope is linear-time representable by a local marginal polytope and any LP can be reduced in linear time to a linear optimization (allowing infinite weights) over a local marginal polytope.
Author: Li He, Hairong Qi, Russell Zaretzki
Abstract: This paper addresses the problem of learning overcomplete dictionaries for the coupled feature spaces, where the learned dictionaries also reflect the relationship between the two spaces. A Bayesian method using a beta process prior is applied to learn the over-complete dictionaries. Compared to previous couple feature spaces dictionary learning algorithms, our algorithm not only provides dictionaries that customized to each feature space, but also adds more consistent and accurate mapping between the two feature spaces. This is due to the unique property of the beta process model that the sparse representation can be decomposed to values and dictionary atom indicators. The proposed algorithm is able to learn sparse representations that correspond to the same dictionary atoms with the same sparsity but different values in coupled feature spaces, thus bringing consistent and accurate mapping between coupled feature spaces. Another advantage of the proposed method is that the number of dictionary atoms and their relative importance may be inferred non-parametrically. We compare the proposed approach to several state-of-the-art dictionary learning methods super-resolution. tionaries learned resolution results ods. by applying this method to single image The experimental results show that dicby our method produces the best supercompared to other state-of-the-art meth-
4 0.84899414 61 cvpr-2013-Beyond Point Clouds: Scene Understanding by Reasoning Geometry and Physics
Author: Bo Zheng, Yibiao Zhao, Joey C. Yu, Katsushi Ikeuchi, Song-Chun Zhu
Abstract: In this paper, we present an approach for scene understanding by reasoning physical stability of objects from point cloud. We utilize a simple observation that, by human design, objects in static scenes should be stable with respect to gravity. This assumption is applicable to all scene categories and poses useful constraints for the plausible interpretations (parses) in scene understanding. Our method consists of two major steps: 1) geometric reasoning: recovering solid 3D volumetric primitives from defective point cloud; and 2) physical reasoning: grouping the unstable primitives to physically stable objects by optimizing the stability and the scene prior. We propose to use a novel disconnectivity graph (DG) to represent the energy landscape and use a Swendsen-Wang Cut (MCMC) method for optimization. In experiments, we demonstrate that the algorithm achieves substantially better performance for i) object segmentation, ii) 3D volumetric recovery of the scene, and iii) better parsing result for scene understanding in comparison to state-of-the-art methods in both public dataset and our own new dataset.
5 0.84839851 20 cvpr-2013-A New Model and Simple Algorithms for Multi-label Mumford-Shah Problems
Author: Byung-Woo Hong, Zhaojin Lu, Ganesh Sundaramoorthi
Abstract: In this work, we address the multi-label Mumford-Shah problem, i.e., the problem of jointly estimating a partitioning of the domain of the image, and functions defined within regions of the partition. We create algorithms that are efficient, robust to undesirable local minima, and are easy-toimplement. Our algorithms are formulated by slightly modifying the underlying statistical model from which the multilabel Mumford-Shah functional is derived. The advantage of this statistical model is that the underlying variables: the labels and thefunctions are less coupled than in the original formulation, and the labels can be computed from the functions with more global updates. The resulting algorithms can be tuned to the desired level of locality of the solution: from fully global updates to more local updates. We demonstrate our algorithm on two applications: joint multi-label segmentation and denoising, and joint multi-label motion segmentation and flow estimation. We compare to the stateof-the-art in multi-label Mumford-Shah problems and show that we achieve more promising results.
6 0.84833586 365 cvpr-2013-Robust Real-Time Tracking of Multiple Objects by Volumetric Mass Densities
7 0.84575367 104 cvpr-2013-Deep Convolutional Network Cascade for Facial Point Detection
8 0.84556746 4 cvpr-2013-3D Visual Proxemics: Recognizing Human Interactions in 3D from a Single Image
9 0.84550536 248 cvpr-2013-Learning Collections of Part Models for Object Recognition
10 0.84550059 19 cvpr-2013-A Minimum Error Vanishing Point Detection Approach for Uncalibrated Monocular Images of Man-Made Environments
11 0.84546345 331 cvpr-2013-Physically Plausible 3D Scene Tracking: The Single Actor Hypothesis
12 0.84531689 311 cvpr-2013-Occlusion Patterns for Object Class Detection
13 0.84426731 446 cvpr-2013-Understanding Indoor Scenes Using 3D Geometric Phrases
14 0.84426272 60 cvpr-2013-Beyond Physical Connections: Tree Models in Human Pose Estimation
15 0.84419304 249 cvpr-2013-Learning Compact Binary Codes for Visual Tracking
16 0.84410191 445 cvpr-2013-Understanding Bayesian Rooms Using Composite 3D Object Models
17 0.84289831 242 cvpr-2013-Label Propagation from ImageNet to 3D Point Clouds
18 0.84252077 227 cvpr-2013-Intrinsic Scene Properties from a Single RGB-D Image
19 0.8419022 424 cvpr-2013-Templateless Quasi-rigid Shape Modeling with Implicit Loop-Closure
20 0.84157562 372 cvpr-2013-SLAM++: Simultaneous Localisation and Mapping at the Level of Objects