cvpr cvpr2013 cvpr2013-308 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Yun Zeng, Chaohui Wang, Stefano Soatto, Shing-Tung Yau
Abstract: This paper introduces an efficient approach to integrating non-local statistics into the higher-order Markov Random Fields (MRFs) framework. Motivated by the observation that many non-local statistics (e.g., shape priors, color distributions) can usually be represented by a small number of parameters, we reformulate the higher-order MRF model by introducing additional latent variables to represent the intrinsic dimensions of the higher-order cliques. The resulting new model, called NC-MRF, not only provides the flexibility in representing the configurations of higher-order cliques, but also automatically decomposes the energy function into less coupled terms, allowing us to design an efficient algorithmic framework for maximum a posteriori (MAP) inference. Based on this novel modeling/inference framework, we achieve state-of-the-art solutions to the challenging problems of class-specific image segmentation and template-based 3D facial expression tracking, which demonstrate the potential of our approach.
Reference: text
sentIndex sentText sentNum sentScore
1 , shape priors, color distributions) can usually be represented by a small number of parameters, we reformulate the higher-order MRF model by introducing additional latent variables to represent the intrinsic dimensions of the higher-order cliques. [sent-11, score-0.137]
2 Based on this novel modeling/inference framework, we achieve state-of-the-art solutions to the challenging problems of class-specific image segmentation and template-based 3D facial expression tracking, which demonstrate the potential of our approach. [sent-13, score-0.162]
3 To overcome such a limitation, previous methods usually exploit tractable structures in higherorder cliques by representing the higher-order potentials us- Figure 1. [sent-17, score-0.241]
4 1(a)), one should be convpiantcteerdn st ohfat 3 t5h ×e plausible patch configurations lcdon best citounteonly a small fraction of the total 235×35 possibilities. [sent-30, score-0.157]
5 For instance, principal component analysis (PCA) shows that such plausible configurations exhibits a low intrinsic dimension, as shown in Fig. [sent-31, score-0.133]
6 Hence the practical applicability of MRFs would be largely extended if we can design efficient MAP-MRF inference algorithms by leveraging the fact that the configurations of a higher-order clique can be represented in a low-dimensional space. [sent-33, score-0.238]
7 By assuming each higherorder clique be represented using its local coordinates, we reformulate the MRF model by introducing additional latent variables to represent the intrinsic dimensions of the higherorder cliques. [sent-35, score-0.317]
8 Moreover, it facilitates efficient inference algorithm since the formulation automatically decomposes the energy function into less coupled terms. [sent-37, score-0.14]
9 Based on a proper Lagrangian relaxation of the original problem, we achieve a new optimization framework using the primal-dual schema [19]. [sent-40, score-0.135]
10 However, rather than focusing only on the dual problem, a primal-dual pair is maintained in each iteration, allowing us to exploit the combinatorial nature of the problem. [sent-42, score-0.267]
11 As a result, in our third contribution, we demonstrate the potential of our modeling/inference framework in two challenging applications: class-specific segmentation and template-based 3D facial expression tracking. [sent-45, score-0.162]
12 In the class-specific segmentation problem, based on the fact that the foreground/background patterns of each non-local patch only span a subset of all the possible configurations, higher-order cliques are used to represent such constrained patterns learnt by PCA. [sent-46, score-0.308]
13 In the even more challenging template-based 3D facial expression tracking problem, existing approaches are either based on low-level cues with local consistency constraints ([13, 3 1]) or on PCA-based global shape statistics [24]. [sent-49, score-0.168]
14 Our NC-MRF based formulation combines both low-level cues and non-local deformation constraints in the same inference framework, leading to a solution that is robust to the noisy input without losing important details. [sent-50, score-0.173]
15 In our experiments, we have achieved accurate tracking results on the BU 4D facial expression (BU-4DFE) database [27]. [sent-51, score-0.168]
16 2 we introduce the mathematical formulation of NC-MRF and the dual of its relaxation; a new algorithmic framework for the MAP inference of NC-MRF is proposed in Sec. [sent-53, score-0.367]
17 (AVl,soE) aw riathnd Vom th vea vriearbtelex xv ∈ L ? [sent-59, score-0.158]
18 problem w Nith both unary potentials (∈θv V : L → R, v ∈ V) and higher-order potentials (θe : L|e| → R, e ∈ RE), can b Ve defined as follows argx∈ mLin|V|{E(x) =v? [sent-68, score-0.161]
19 (1) Here xe represents the set of variables included in clique e. [sent-71, score-0.173]
20 In this paper, we represent each higher-order configuration xe (e ∈ E) via a mapping : ue ∈ Rle → xe, (2) where ue denotes the local coordinates and le ∈ N+. [sent-72, score-0.804]
21 Besides, it provides the flexibility of controlling the complexities of the higher-order potentials (e. [sent-86, score-0.105]
22 , it first decomposes the original problem into a sum of sub-problems, and then solves the Lagrangian relaxation on its primal and/or dual domain. [sent-96, score-0.505]
23 To this end, we first define a proper continuous relaxation of problem (3) in Sec. [sent-98, score-0.097]
24 , ∈L E− a 1n}d; (b) χeei (ue) = 1if uei < 2; (c) χeei k(u,ke) + += 1 L) a nifd uei ∈≥ L2 . [sent-106, score-0.116]
25 ar [yχ,ee if o(ure th) e= h i jg] feorr- oeradcehr ei ∈ e and j ∈ L. [sent-118, score-0.176]
26 A continuous relaxation of the above M(jI)NL (∀Pv can b,ej o ∈bt Lai)n. [sent-135, score-0.097]
27 Hence it )av (eoid ∈s introducing a very large amount of auxiliary indicator variables for all the possible configurations in the higher-order cliques. [sent-139, score-0.111]
28 In the next section, we show that this relaxation scheme provides high flexibility in designing efficient MAP algorithms. [sent-140, score-0.108]
29 Dual problem and optimality conditions Given the primal problem defined by Eq. [sent-143, score-0.194]
30 4, now we look at its dual problem based on Lagrangian relaxation [1]. [sent-144, score-0.338]
31 τei:j (e ∈ E, ei ∈ e, j ∈ L) and hv for each constraint ? [sent-146, score-0.35]
32 ET,ehe∈ne tjh∈eL dual function forv problem 4 is defined as follows Dual(μ,h) ? [sent-191, score-0.267]
33 τ≥in0f,uL(τ,u;μ,h) (7) and its dual problem becomes μ,shu∈pDDual(μ,h), (8) 2 [p] = 1if p is true and [p] = 0 otherwise. [sent-192, score-0.267]
34 The domain D of the dual function Dual(·) is convex and TDhueadl (o·)m ias concave over Dl f. [sent-200, score-0.267]
35 For the value of the dual problem to be finite, we have (otherwise by letting τv;j → +∞, Dual(μ, h) → −∞) θv:j − hv −? [sent-202, score-0.441]
36 ˆτ ei ;j )e∈E,ei ∈e,j∈L is a supergradient ofDual(·) at λ, i. [sent-221, score-0.176]
37 Lemma 2 (Strong agreement conditions) For an optimal primal-dual solution (τ, u; μ, h), if the following holds (b. [sent-241, score-0.092]
38 3 is achieved by setting xv = {j |τv;j > 0}, ∀v ∈ V. [sent-251, score-0.158]
39 The uniqueness of xv is guaranteed by the definition of χe (Eq. [sent-252, score-0.189]
40 111777000866 The correctness of Lemma 2 can be proven by checking the duality gap becomes zeros if the strong agreement conditions are met. [sent-254, score-0.097]
41 In each iteration, we maintain both an integer solution (xv)v∈V (xv ∈ L), a continuous primal solution τ and a duval∈ Vsolution∈ μ. [sent-262, score-0.308]
42 ∈ e Solv (μ) is guaranteed to be nonempty if we consider the dual function Dual(μ, h(μ)) defined in Prop. [sent-274, score-0.298]
43 Intuitively, τv;j denotes the probability for label j to be the primal solution of the integer programming problem of Eq. [sent-276, score-0.23]
44 Accordingly, each xv is also chosen from those labels with non-zero probability, i. [sent-278, score-0.158]
45 The dual problem then becomes the following mμax{DualI(μ) =e? [sent-284, score-0.267]
46 (10) Here each subproblem se (·) is defined by se(μe) = muein{ψe(ue) +e? [sent-287, score-0.136]
47 The advantage of maintaining a primal solutio∈ne i,jn∈ eLach iteration, is that each sub- problem can also compute its solution based on current primal solution x, by solving a proximal problem muein{ψe(ue) +? [sent-291, score-0.38]
48 ∈Lμei:jχeei:j(ue) + d(χe(ue),x)}, where d(·, ·) denotes a similarity measure between the wsohleutrieon d proposed by ath seim subproblem uarned tehtew eceunrre thnet integer primal solution. [sent-293, score-0.278]
49 Given the solution proposed by each subproblem, the dual variables μ are updated to optimize the dual function by the dual ascent algorithm using its subgradient. [sent-296, score-0.969]
50 After the dual ascent update, the algorithm stops if the dual objective function can no longer be improved. [sent-298, score-0.592]
51 Otherwise, a new primal solution xv (v ∈ V) is selected from the updated set Solv (μ) (Eq. [sent-299, score-0.374]
52 By following the above design rules, it is guaranteed that the final solution is in the set Solv (μ) , v ∈ V. [sent-302, score-0.111]
53 Algorithm Algorithm 1: Outline of the PD strategy for NC-MRF Initialization: set t = 0, μt = 0, 1: xv0 = arg minj θv:j ,∀v ∈ V (break ties arbitrarily) Repeat Solve each subproblem (Eq. [sent-311, score-0.169]
54 Design of dual ascent algorithms Now let us look at strategies to improve the lower bound in the dual domain. [sent-318, score-0.592]
55 1(5), for each e ∈ E, ei ∈ e, j t ∈e dLu, athl ed osumbaginr. [sent-320, score-0.176]
56 However, as noted in [5], one issue with directly optimizing the dual problem of Eq. [sent-327, score-0.267]
57 v∈V 3Note that this dual ascent strategy underlies many dual optimization based MRF inference algorithms [8, 10, 11, 25]. [sent-334, score-0.647]
58 When the subproblems se (·) are formulated into LP, the dual objective of Eq. [sent-335, score-0.34]
59 10 when the dual function se (·) is relatively flat ((i·). [sent-338, score-0.303]
60 i,n given μe, hite ins tahleways possible to( f·i)n dis a primal yso flluatti o(ni. [sent-340, score-0.138]
61 e ue tihveatn a μchieves the same minimum) this is the case when the higher-order potentials ψe (ue) represents only configurational constraints. [sent-341, score-0.438]
62 o Tnvheerrgeefsor ine, Oth(e dual optimization algorithm only scales in the order of n log n, where n is the number of cliques in the graph. [sent-349, score-0.403]
63 Design of primal consensus rules Let us recall the process of the primal-dual update in the tth iteration of Alg. [sent-352, score-0.21]
64 1: (1) for each node v ∈ V, after eachi subproblem ilsg s. [sent-353, score-0.1]
65 o 1lv:ed (1 )b a fsoerd on hcu nrroednet primal-dual solution, a new solution is proposed by each clique e with v ∈ e; (2) if there are proposed solutions not in the current svet ∈ S eo;lv ( (Eq. [sent-354, score-0.158]
66 Eventually, the dual objective function will no longer be improved and a unique solution is determined from Solv (μt). [sent-358, score-0.319]
67 If there are cliques that disagree with the final solution, their proposed solutions will simply be disregarded. [sent-359, score-0.136]
68 Therefore, the role of the consensus rule is to guarantee that the final solution selected reflects the agreement of the majority. [sent-360, score-0.162]
69 Intuitively, when there are multiple choices in the set Solv (μ), larger weights are given for those labels with larger number of cliques that agree on them. [sent-367, score-0.136]
70 Hence a primal integral solution can be chosen from the set Solv (μ) with largest weight (tie is broken arbitrary). [sent-368, score-0.19]
71 Given the weighting system defined above, we can simply determine the primal solution for τ as τv;j=? [sent-369, score-0.19]
72 j∈Solvwv;j iofth je ∈rw Sisoelv, which is used for the subsequent dual optimization in the next iteration. [sent-371, score-0.267]
73 At this point, we have presented a complete algorithmic framework for solving the NC-MRF inference problem of Eq. [sent-372, score-0.1]
74 To demonstrate its potential, we present two applications: class-specific image segmentation and template-based 3D facial expression tracking. [sent-381, score-0.135]
75 In both cases, we consider the dual objective defined by Eq. [sent-382, score-0.267]
76 c hT nheo higher-order clique set E consists of all the p p patches in the image. [sent-394, score-0.106]
77 By choosing the first l components in the learnt PCA model, the configuration of the higher-order clique corresponding to each patch can be defined as ? [sent-401, score-0.251]
78 16, we can define the potential for each higher-order clique e ∈ E as ψ(ue) = ? [sent-419, score-0.133]
79 r usction given by s0 + uiesi outputs a p p patch with continuous valu? [sent-443, score-0.135]
80 1, the following topological constraints are obtained from the the learnt data: (a) each connected foreground region must be connected to one of the patch’s four boundaries; (b) there is at most one hole in the foreground region; (c) each patch has at most three connected foreground regions. [sent-448, score-0.2]
81 These conditions can be guaranteed by a binary search for the optimal threshold that separates the foreground from the background (with a complexity of only O(p2 log k), where k = 100 is the discretization level in the continuous space). [sent-449, score-0.112]
82 Results We evaluate our method on the popular Weizmann horses data set [2] which consists of 328 images of horses with various backgrounds. [sent-450, score-0.094]
83 Template-based 3D facial expression tracking We next look at the problem of template-based 3D surface tracking. [sent-473, score-0.168]
84 e Tsheti on tdh,e l template ean ad g rEa pthhe patch set (Fig. [sent-505, score-0.107]
85 We assume the deformation of each each patch e ∈ E lies in a subspace which can be represented by chon eti ∈nuo Eus l evasri ianb ales s ue. [sent-508, score-0.247]
86 (Best viewed in color) In the template-based 3D face tracking problem, a template is constructed for the first frame in a 3D sequence and the locations of its nodes are inferred in the subsequent frames. [sent-514, score-0.123]
87 Representation of deformation space The challenge of deformation modeling lies in the characterization of nonrigid motion. [sent-516, score-0.132]
88 In order to apply CDCs to representing the deformation of a patch e ⊂ 2V, we consider a triangulation of the mnoadteiosn nin o e, ad peantcothed e by F2e ⊂ e e e. [sent-521, score-0.136]
89 Since the deformation nofo deeaschin triangle efd b∈y FFe can ×bee represented using CmDatiCosn, tohfe e non-rigid ldeef form ∈a Ftion of the whole patch can then be represented by the vector de = (λf1 , λ2f)f∈Fe , de ∈ R|Fe | ×2 (Fig. [sent-522, score-0.136]
90 In this way, a prior deforma∈tion R space can be represented as d(α) = d0 + αidi, and the intrinsic parameters for a patch e are s? [sent-524, score-0.116]
91 imply ue = αe where αe ≡ (αei)il=1 are the coefficients fo? [sent-525, score-0.37]
92 Subproblem optimization Given the above representation of deformation space, each subproblem e then becomes searching for the optimal ue given current dual variables μe. [sent-528, score-0.835]
93 1), we obtain an initial solution by solving sole (ei) = arg minj {θei;j + μei;j }, ∀ei ∈ e, which also gives us an initial correspondence} ,f∀ore ea∈ch e n,o wdeh cinh e. [sent-531, score-0.166]
94 o, fw thheer patch, the optimal deformation of the patch can be solved by employing the higher-order MRF optimization proposed in [30], providing the final correspondence for each node. [sent-538, score-0.136]
95 0285 and our method achieves significantly smaller errors for every case, although a slight overhead is added in optimizing the higher-order cliques (∼ 1s / frame for 62 cliques on CPU). [sent-570, score-0.3]
96 NC-MRFs provide a compact representation of higher-order MRFs by introducing additional latent variables to represent the plausible configurations of higher-order cliques, and allow flexible design of efficient inference algorithms by decomposing the energy function into less coupled terms. [sent-573, score-0.288]
97 Notably, we have achieved state-of-the-art results for the challenging problems of class-specific image segmentation and template-based 3D facial expression tracking. [sent-574, score-0.135]
98 Dimitris Samaras for suggesting the bidirectional tracking error in evaluating our tracking results. [sent-577, score-0.159]
99 Efficient belief propagation for higher-order cliques using linear constraint nodes. [sent-682, score-0.136]
100 Revisiting the linear programming relaxation approach to Gibbs energy minimization and weighted constraint satisfaction. [sent-744, score-0.097]
wordName wordTfidf (topN-words)
[('eei', 0.562), ('ue', 0.37), ('dual', 0.267), ('ei', 0.176), ('hv', 0.174), ('solv', 0.172), ('xv', 0.158), ('primal', 0.138), ('cliques', 0.136), ('eti', 0.111), ('clique', 0.106), ('subproblem', 0.1), ('mrf', 0.096), ('mrfs', 0.088), ('samaras', 0.08), ('cdcs', 0.077), ('pv', 0.077), ('bte', 0.075), ('ute', 0.072), ('relaxation', 0.071), ('patch', 0.07), ('minj', 0.069), ('potentials', 0.068), ('deformation', 0.066), ('facial', 0.064), ('schema', 0.064), ('zeng', 0.063), ('nonlinearly', 0.06), ('ve', 0.059), ('muein', 0.058), ('uei', 0.058), ('ascent', 0.058), ('tracking', 0.058), ('inference', 0.055), ('solution', 0.052), ('pca', 0.05), ('configurations', 0.049), ('horses', 0.047), ('learnt', 0.046), ('expression', 0.046), ('intrinsic', 0.046), ('lemma', 0.045), ('sole', 0.045), ('algorithmic', 0.045), ('lagrangian', 0.045), ('ej', 0.043), ('harvard', 0.043), ('bidirectional', 0.043), ('consensus', 0.041), ('agreement', 0.04), ('integer', 0.04), ('wv', 0.04), ('duali', 0.039), ('dualii', 0.039), ('minlp', 0.039), ('supdual', 0.039), ('uiesi', 0.039), ('komodakis', 0.038), ('plausible', 0.038), ('subproblems', 0.037), ('higherorder', 0.037), ('template', 0.037), ('flexibility', 0.037), ('se', 0.036), ('weizmann', 0.035), ('xe', 0.035), ('pd', 0.033), ('variables', 0.032), ('opt', 0.032), ('subgradient', 0.032), ('bu', 0.032), ('guaranteed', 0.031), ('constrained', 0.031), ('update', 0.031), ('happy', 0.03), ('duality', 0.03), ('introducing', 0.03), ('coupled', 0.03), ('optimality', 0.029), ('rule', 0.029), ('map', 0.029), ('configuration', 0.029), ('decomposes', 0.029), ('dimensions', 0.029), ('die', 0.029), ('yau', 0.029), ('frame', 0.028), ('design', 0.028), ('foreground', 0.028), ('soatto', 0.027), ('conditions', 0.027), ('potential', 0.027), ('wang', 0.027), ('updated', 0.026), ('energy', 0.026), ('continuous', 0.026), ('cviu', 0.026), ('pw', 0.026), ('unary', 0.025), ('segmentation', 0.025)]
simIndex simValue paperId paperTitle
same-paper 1 0.9999994 308 cvpr-2013-Nonlinearly Constrained MRFs: Exploring the Intrinsic Dimensions of Higher-Order Cliques
Author: Yun Zeng, Chaohui Wang, Stefano Soatto, Shing-Tung Yau
Abstract: This paper introduces an efficient approach to integrating non-local statistics into the higher-order Markov Random Fields (MRFs) framework. Motivated by the observation that many non-local statistics (e.g., shape priors, color distributions) can usually be represented by a small number of parameters, we reformulate the higher-order MRF model by introducing additional latent variables to represent the intrinsic dimensions of the higher-order cliques. The resulting new model, called NC-MRF, not only provides the flexibility in representing the configurations of higher-order cliques, but also automatically decomposes the energy function into less coupled terms, allowing us to design an efficient algorithmic framework for maximum a posteriori (MAP) inference. Based on this novel modeling/inference framework, we achieve state-of-the-art solutions to the challenging problems of class-specific image segmentation and template-based 3D facial expression tracking, which demonstrate the potential of our approach.
2 0.16684532 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.
3 0.1100296 466 cvpr-2013-Whitened Expectation Propagation: Non-Lambertian Shape from Shading and Shadow
Author: Brian Potetz, Mohammadreza Hajiarbabi
Abstract: For problems over continuous random variables, MRFs with large cliques pose a challenge in probabilistic inference. Difficulties in performing optimization efficiently have limited the probabilistic models explored in computer vision and other fields. One inference technique that handles large cliques well is Expectation Propagation. EP offers run times independent of clique size, which instead depend only on the rank, or intrinsic dimensionality, of potentials. This property would be highly advantageous in computer vision. Unfortunately, for grid-shaped models common in vision, traditional Gaussian EP requires quadratic space and cubic time in the number of pixels. Here, we propose a variation of EP that exploits regularities in natural scene statistics to achieve run times that are linear in both number of pixels and clique size. We test these methods on shape from shading, and we demonstrate strong performance not only for Lambertian surfaces, but also on arbitrary surface reflectance and lighting arrangements, which requires highly non-Gaussian potentials. Finally, we use large, non-local cliques to exploit cast shadow, which is traditionally ignored in shape from shading.
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.095650233 180 cvpr-2013-Fully-Connected CRFs with Non-Parametric Pairwise Potential
Author: Neill D.F. Campbell, Kartic Subr, Jan Kautz
Abstract: Conditional Random Fields (CRFs) are used for diverse tasks, ranging from image denoising to object recognition. For images, they are commonly defined as a graph with nodes corresponding to individual pixels and pairwise links that connect nodes to their immediate neighbors. Recent work has shown that fully-connected CRFs, where each node is connected to every other node, can be solved efficiently under the restriction that the pairwise term is a Gaussian kernel over a Euclidean feature space. In this paper, we generalize the pairwise terms to a non-linear dissimilarity measure that is not required to be a distance metric. To this end, we propose a density estimation technique to derive conditional pairwise potentials in a nonparametric manner. We then use an efficient embedding technique to estimate an approximate Euclidean feature space for these potentials, in which the pairwise term can still be expressed as a Gaussian kernel. We demonstrate that the use of non-parametric models for the pairwise interactions, conditioned on the input data, greatly increases expressive power whilst maintaining efficient inference.
6 0.095443003 143 cvpr-2013-Efficient Large-Scale Structured Learning
7 0.089764364 386 cvpr-2013-Self-Paced Learning for Long-Term Tracking
8 0.083164513 13 cvpr-2013-A Higher-Order CRF Model for Road Network Extraction
9 0.079859607 161 cvpr-2013-Facial Feature Tracking Under Varying Facial Expressions and Face Poses Based on Restricted Boltzmann Machines
10 0.079037659 62 cvpr-2013-Bilinear Programming for Human Activity Recognition with Unknown MRF Graphs
11 0.079009965 24 cvpr-2013-A Principled Deep Random Field Model for Image Segmentation
12 0.077621691 6 cvpr-2013-A Comparative Study of Modern Inference Techniques for Discrete Energy Minimization Problems
13 0.07588242 165 cvpr-2013-Fast Energy Minimization Using Learned State Filters
14 0.073877744 300 cvpr-2013-Multi-target Tracking by Lagrangian Relaxation to Min-cost Network Flow
15 0.070715018 324 cvpr-2013-Part-Based Visual Tracking with Online Latent Structural Learning
16 0.070260294 164 cvpr-2013-Fast Convolutional Sparse Coding
17 0.069279209 262 cvpr-2013-Learning for Structured Prediction Using Approximate Subgradient Descent with Working Sets
18 0.069110096 156 cvpr-2013-Exploring Compositional High Order Pattern Potentials for Structured Output Learning
19 0.066892058 9 cvpr-2013-A Fast Semidefinite Approach to Solving Binary Quadratic Problems
20 0.064722888 397 cvpr-2013-Simultaneous Super-Resolution of Depth and Images Using a Single Camera
topicId topicWeight
[(0, 0.158), (1, 0.039), (2, -0.007), (3, 0.009), (4, 0.058), (5, -0.015), (6, 0.045), (7, -0.033), (8, -0.013), (9, -0.005), (10, 0.071), (11, 0.007), (12, -0.107), (13, 0.025), (14, -0.024), (15, 0.05), (16, -0.008), (17, 0.048), (18, 0.139), (19, 0.013), (20, -0.054), (21, -0.027), (22, -0.034), (23, -0.011), (24, 0.052), (25, 0.009), (26, -0.092), (27, 0.045), (28, -0.012), (29, -0.046), (30, 0.042), (31, -0.053), (32, 0.023), (33, -0.008), (34, -0.14), (35, 0.0), (36, 0.027), (37, -0.042), (38, -0.073), (39, 0.011), (40, 0.012), (41, 0.026), (42, -0.007), (43, -0.017), (44, -0.022), (45, 0.002), (46, 0.007), (47, 0.009), (48, 0.071), (49, -0.004)]
simIndex simValue paperId paperTitle
same-paper 1 0.9441278 308 cvpr-2013-Nonlinearly Constrained MRFs: Exploring the Intrinsic Dimensions of Higher-Order Cliques
Author: Yun Zeng, Chaohui Wang, Stefano Soatto, Shing-Tung Yau
Abstract: This paper introduces an efficient approach to integrating non-local statistics into the higher-order Markov Random Fields (MRFs) framework. Motivated by the observation that many non-local statistics (e.g., shape priors, color distributions) can usually be represented by a small number of parameters, we reformulate the higher-order MRF model by introducing additional latent variables to represent the intrinsic dimensions of the higher-order cliques. The resulting new model, called NC-MRF, not only provides the flexibility in representing the configurations of higher-order cliques, but also automatically decomposes the energy function into less coupled terms, allowing us to design an efficient algorithmic framework for maximum a posteriori (MAP) inference. Based on this novel modeling/inference framework, we achieve state-of-the-art solutions to the challenging problems of class-specific image segmentation and template-based 3D facial expression tracking, which demonstrate the potential of our approach.
2 0.83031505 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.75115407 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.
5 0.73731643 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.
6 0.73462623 24 cvpr-2013-A Principled Deep Random Field Model for Image Segmentation
7 0.69814688 51 cvpr-2013-Auxiliary Cuts for General Classes of Higher Order Functionals
8 0.6879794 262 cvpr-2013-Learning for Structured Prediction Using Approximate Subgradient Descent with Working Sets
9 0.68310016 171 cvpr-2013-Fast Trust Region for Segmentation
10 0.68238801 41 cvpr-2013-An Iterated L1 Algorithm for Non-smooth Non-convex Optimization in Computer Vision
11 0.67753369 128 cvpr-2013-Discrete MRF Inference of Marginal Densities for Non-uniformly Discretized Variable Space
12 0.67745107 466 cvpr-2013-Whitened Expectation Propagation: Non-Lambertian Shape from Shading and Shadow
13 0.63871515 180 cvpr-2013-Fully-Connected CRFs with Non-Parametric Pairwise Potential
14 0.6342746 23 cvpr-2013-A Practical Rank-Constrained Eight-Point Algorithm for Fundamental Matrix Estimation
15 0.6162954 165 cvpr-2013-Fast Energy Minimization Using Learned State Filters
16 0.61366278 20 cvpr-2013-A New Model and Simple Algorithms for Multi-label Mumford-Shah Problems
17 0.59880543 9 cvpr-2013-A Fast Semidefinite Approach to Solving Binary Quadratic Problems
18 0.57197309 143 cvpr-2013-Efficient Large-Scale Structured Learning
19 0.54823059 156 cvpr-2013-Exploring Compositional High Order Pattern Potentials for Structured Output Learning
20 0.52511525 429 cvpr-2013-The Generalized Laplacian Distance and Its Applications for Visual Matching
topicId topicWeight
[(10, 0.129), (16, 0.034), (26, 0.04), (33, 0.278), (63, 0.25), (67, 0.036), (69, 0.055), (87, 0.071)]
simIndex simValue paperId paperTitle
1 0.89900613 467 cvpr-2013-Wide-Baseline Hair Capture Using Strand-Based Refinement
Author: Linjie Luo, Cha Zhang, Zhengyou Zhang, Szymon Rusinkiewicz
Abstract: We propose a novel algorithm to reconstruct the 3D geometry of human hairs in wide-baseline setups using strand-based refinement. The hair strands arefirst extracted in each 2D view, and projected onto the 3D visual hull for initialization. The 3D positions of these strands are then refined by optimizing an objective function that takes into account cross-view hair orientation consistency, the visual hull constraint and smoothness constraints defined at the strand, wisp and global levels. Based on the refined strands, the algorithm can reconstruct an approximate hair surface: experiments with synthetic hair models achieve an accuracy of ∼3mm. We also show real-world examples to demonsotfra ∼te3 mthme capability t soh capture full-head hamairp styles as mwoenll- as hair in motion with as few as 8 cameras.
2 0.89876461 52 cvpr-2013-Axially Symmetric 3D Pots Configuration System Using Axis of Symmetry and Break Curve
Author: Kilho Son, Eduardo B. Almeida, David B. Cooper
Abstract: Thispaper introduces a novel approachfor reassembling pot sherds found at archaeological excavation sites, for the purpose ofreconstructing claypots that had been made on a wheel. These pots and the sherds into which they have broken are axially symmetric. The reassembly process can be viewed as 3D puzzle solving or generalized cylinder learning from broken fragments. The estimation exploits both local and semi-global geometric structure, thus making it a fundamental problem of geometry estimation from noisy fragments in computer vision and pattern recognition. The data used are densely digitized 3D laser scans of each fragment’s outer surface. The proposed reassembly system is automatic and functions when the pile of available fragments is from one or multiple pots, and even when pieces are missing from any pot. The geometric structure used are curves on the pot along which the surface had broken and the silhouette of a pot with respect to an axis, called axisprofile curve (APC). For reassembling multiple pots with or without missing pieces, our algorithm estimates the APC from each fragment, then reassembles into configurations the ones having distinctive APC. Further growth of configurations is based on adding remaining fragments such that their APC and break curves are consistent with those of a configuration. The method is novel, more robust and handles the largest numbers of fragments to date.
3 0.86318088 74 cvpr-2013-CLAM: Coupled Localization and Mapping with Efficient Outlier Handling
Author: Jonathan Balzer, Stefano Soatto
Abstract: We describe a method to efficiently generate a model (map) of small-scale objects from video. The map encodes sparse geometry as well as coarse photometry, and could be used to initialize dense reconstruction schemes as well as to support recognition and localization of three-dimensional objects. Self-occlusions and the predominance of outliers present a challenge to existing online Structure From Motion and Simultaneous Localization and Mapping systems. We propose a unified inference criterion that encompasses map building and localization (object detection) relative to the map in a coupled fashion. We establish correspondence in a computationally efficient way without resorting to combinatorial matching or random-sampling techniques. Instead, we use a simpler M-estimator that exploits putative correspondence from tracking after photometric and topological validation. We have collected a new dataset to benchmark model building in the small scale, which we test our algorithm on in comparison to others. Although our system is significantly leaner than previous ones, it compares favorably to the state of the art in terms of accuracy and robustness.
same-paper 4 0.86224705 308 cvpr-2013-Nonlinearly Constrained MRFs: Exploring the Intrinsic Dimensions of Higher-Order Cliques
Author: Yun Zeng, Chaohui Wang, Stefano Soatto, Shing-Tung Yau
Abstract: This paper introduces an efficient approach to integrating non-local statistics into the higher-order Markov Random Fields (MRFs) framework. Motivated by the observation that many non-local statistics (e.g., shape priors, color distributions) can usually be represented by a small number of parameters, we reformulate the higher-order MRF model by introducing additional latent variables to represent the intrinsic dimensions of the higher-order cliques. The resulting new model, called NC-MRF, not only provides the flexibility in representing the configurations of higher-order cliques, but also automatically decomposes the energy function into less coupled terms, allowing us to design an efficient algorithmic framework for maximum a posteriori (MAP) inference. Based on this novel modeling/inference framework, we achieve state-of-the-art solutions to the challenging problems of class-specific image segmentation and template-based 3D facial expression tracking, which demonstrate the potential of our approach.
5 0.82747692 40 cvpr-2013-An Approach to Pose-Based Action Recognition
Author: Chunyu Wang, Yizhou Wang, Alan L. Yuille
Abstract: We address action recognition in videos by modeling the spatial-temporal structures of human poses. We start by improving a state of the art method for estimating human joint locations from videos. More precisely, we obtain the K-best estimations output by the existing method and incorporate additional segmentation cues and temporal constraints to select the “best” one. Then we group the estimated joints into five body parts (e.g. the left arm) and apply data mining techniques to obtain a representation for the spatial-temporal structures of human actions. This representation captures the spatial configurations ofbodyparts in one frame (by spatial-part-sets) as well as the body part movements(by temporal-part-sets) which are characteristic of human actions. It is interpretable, compact, and also robust to errors on joint estimations. Experimental results first show that our approach is able to localize body joints more accurately than existing methods. Next we show that it outperforms state of the art action recognizers on the UCF sport, the Keck Gesture and the MSR-Action3D datasets.
6 0.81514579 33 cvpr-2013-Active Contours with Group Similarity
7 0.78495896 245 cvpr-2013-Layer Depth Denoising and Completion for Structured-Light RGB-D Cameras
8 0.78436321 61 cvpr-2013-Beyond Point Clouds: Scene Understanding by Reasoning Geometry and Physics
9 0.78415674 365 cvpr-2013-Robust Real-Time Tracking of Multiple Objects by Volumetric Mass Densities
10 0.78395116 227 cvpr-2013-Intrinsic Scene Properties from a Single RGB-D Image
11 0.78352147 446 cvpr-2013-Understanding Indoor Scenes Using 3D Geometric Phrases
12 0.7834878 98 cvpr-2013-Cross-View Action Recognition via a Continuous Virtual Path
13 0.78336453 143 cvpr-2013-Efficient Large-Scale Structured Learning
14 0.78318471 121 cvpr-2013-Detection- and Trajectory-Level Exclusion in Multiple Object Tracking
15 0.78309071 445 cvpr-2013-Understanding Bayesian Rooms Using Composite 3D Object Models
16 0.78297299 242 cvpr-2013-Label Propagation from ImageNet to 3D Point Clouds
17 0.78284919 248 cvpr-2013-Learning Collections of Part Models for Object Recognition
18 0.78243518 360 cvpr-2013-Robust Estimation of Nonrigid Transformation for Point Set Registration
19 0.78132379 372 cvpr-2013-SLAM++: Simultaneous Localisation and Mapping at the Level of Objects
20 0.78131175 267 cvpr-2013-Least Soft-Threshold Squares Tracking