cvpr cvpr2013 cvpr2013-24 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Pushmeet Kohli, Anton Osokin, Stefanie Jegelka
Abstract: We discuss a model for image segmentation that is able to overcome the short-boundary bias observed in standard pairwise random field based approaches. To wit, we show that a random field with multi-layered hidden units can encode boundary preserving higher order potentials such as the ones used in the cooperative cuts model of [11] while still allowing for fast and exact MAP inference. Exact inference allows our model to outperform previous image segmentation methods, and to see the true effect of coupling graph edges. Finally, our model can be easily extended to handle segmentation instances with multiple labels, for which it yields promising results.
Reference: text
sentIndex sentText sentNum sentScore
1 To wit, we show that a random field with multi-layered hidden units can encode boundary preserving higher order potentials such as the ones used in the cooperative cuts model of [11] while still allowing for fast and exact MAP inference. [sent-2, score-0.804]
2 Exact inference allows our model to outperform previous image segmentation methods, and to see the true effect of coupling graph edges. [sent-3, score-0.298]
3 Like many other image labeling problems, interactive segmentation is commonly modelled using pairwise Markov Random fields that incorporate priors on labels of pairs of neighbouring pixels. [sent-8, score-0.405]
4 These models allow efficient inference of the Maximum a Posteriori (MAP) solution using algorithms such graph cuts [4, 28] but have restricted expressive power [12]. [sent-9, score-0.196]
5 One of the major side-effects of using pairwise MRFs for segmentation is the short-boundary bias [20], illustrated in Figure 1(c). [sent-10, score-0.21]
6 It results from the fact that the standard pairwise model encourages smooth segmentations by penalizing the assignment of different labels to neighbouring pixels [1, 4]. [sent-11, score-0.328]
7 Jegelka & Bilmes [11] recently proposed a different approach – a cooperative graph cut model – to overcome the short-boundary bias. [sent-16, score-0.612]
8 Instead of favoring short object boundaries by penalizing the number of label discontinuities, their model favors “congruous” boundaries by penalizing the number of types of label discontinuities. [sent-17, score-0.168]
9 This new term is a submodular function on pairs of variables, a cooperative cut potential. [sent-18, score-0.664]
10 The cost of label discontinuities does not grow linearly with the number of discontinuities in the labeling, as is the case in the standard pairwise model. [sent-19, score-0.287]
11 Cooperative cut potentials can make MAP inference an NP-hard problem, and therefore [11] propose an approximation algorithm that still outperforms previous segmentation methods. [sent-21, score-0.606]
12 In this work, we rephrase the model of [11] and construct an equivalent hierarchical model by using a transformation inspired by a lower envelope representation of higher-order potentials [13]. [sent-24, score-0.392]
13 (ii) It yields a refined complexity analysis and, in the language of parameterized complexity [8, 23], shows that a practically useful subset of cooperative cut problems is fixed-parameter tractable. [sent-28, score-0.546]
14 (iv) The model structure shows an explicit connection between cooperative cuts and hierarchical models, hinting at the potential representational power of deep models such as Deep Boltzmann Machines (DBM) [27]. [sent-31, score-0.586]
15 Coupling Edges for Image Segmentation We first introduce the standard pairwise Markov ran- dom field (MRF) model for interactive segmentation and the extension proposed in [11]. [sent-33, score-0.254]
16 111999667199 (a) (b) Figure 1: (a) User-specified seeds; (b) Ground truth segmentation; (c) (d)(e) (c) MAP solution of standard pairwise MRF model; (d) Global minimum of cooperative of the 1546 cut energy obtained by our method. [sent-37, score-0.889]
17 The (summed) weight of the boundary is edges cut in (c) belong to 3 out of 11 types, while for (d) the edges: colour channel C (R, G, or B) of the pixel is set to Ψg 255 3 types include 99% of the 4849 in (c) and 11273 in (d). [sent-38, score-0.324]
18 (e) type ID of cut if this pixel is incident to a cut edge whose type is C. [sent-40, score-0.429]
19 The coupling potentials for the three main edge types contribute a total penalty that is 0. [sent-41, score-0.549]
20 35 times the pairwise penalty in (c) and only 0. [sent-42, score-0.201]
21 2 times the pairwise penalty in (d), and hence solutions like (d) are favored. [sent-43, score-0.201]
22 The set of all variables xi for i∈ V is denoted by x. [sent-47, score-0.175]
23 f Tthhee pairwise dmisotdrieblu ftaiocnto Pri(zexs| i)nt =o unary potentials xφ)i ()x oi)f athned pairwise potentials ψij (zxeis, xj). [sent-49, score-0.921]
24 The Short-Boundary Bias and Coupling Edges The above pairwise model can be illustrated by a gridstructured graph, where each potential ψij corresponds to an edge. [sent-54, score-0.217]
25 A labeling corresponds to a partition of this graph, and label discontinuities between neighboring pixels correspond to cut edges. [sent-55, score-0.349]
26 The potential (1) grows linearly with the weights θij of cut edges or neighboring pixels with differing labels. [sent-56, score-0.372]
27 In particular, in the special case of θ being constant, the contribution of the pairwise potentials to the energy is a linear function of the perimeter of the figure. [sent-57, score-0.584]
28 “Diversity” is defined by partitioning the set E of pixel pairs iinvetor groups (types) Eg (g ∈tit oGn) nofg tshimei slaert pairs, iaxnedl a congruous boundary uses (fgew ∈ types. [sent-65, score-0.168]
29 iTmhiel new energy considers all pairs of a type simultaneously and gives a “discount” for using edges (pairs) of the same type. [sent-66, score-0.25]
30 The discount results from a monotonically increasing concave function F, and the resulting energy function is = E(x) Xφi(xi) +XΨg(x), Xi∈V Xg∈G Ψg(x) = F? [sent-67, score-0.234]
31 , where (4) (5) As the values of the pairwise penalty terms are grouped together using a higher-order potential, [11] referred to this model as coupling edges, or cooperative cuts. [sent-69, score-0.674]
32 If F is the identity, then the energy in Equation (4) is equal to the standard energy (1). [sent-71, score-0.278]
33 Edge groups ti nhadti flfeearde ntot a bdi aasp pfloyr congruous Gbo oufn gdraoruipess can g bee computed by clustering graph edges [11]. [sent-73, score-0.248]
34 Inferring the Maximum a Posteriori (MAP) solution of the models above corresponds to minimizing their respective energy functions. [sent-75, score-0.2]
35 It is well known that the energy function (1) is submodular if all θ(Ii, Ij ) ≥ 0 and can then be minimized in polynomial time by so)lv ≥ing an (s, t)-mincut problem [4]. [sent-76, score-0.264]
36 In contrast, the higherorder potential (5) makes MAP inference in general NPhard, and therefore [11] proposed an iterative bound minimization algorithm for approximate inference. [sent-77, score-0.207]
37 We show 111999777200 next that higher order potentials of the form (5) can be converted into a pairwise model by the addition of some binary auxiliary variables. [sent-78, score-0.562]
38 Since inference in pairwise models is very well studied, one popular technique is to transform the higher-order energy function into that of a pairwise random field. [sent-81, score-0.473]
39 In fact, any higher-order pseudoboolean function can be converted to a pairwise one, by introducing additional auxiliary random variables [2, 10, 13]. [sent-82, score-0.276]
40 Unfortunately, the number of auxiliary variables grows exponentially with the arity of the function, and in practice this approach is only feasible for higher-order functions with few variables. [sent-83, score-0.176]
41 This is the case for the edgecoupling potentials (4). [sent-85, score-0.301]
42 We explain our transformation using the example of a special cooperative cut potential: Ψg(x) = minnXij∈Egθij|xi− xj|,To, (6) where T is a truncation parameter. [sent-86, score-0.59]
43 Incorporated into energy (4), this potential penalizes the number of types of transitions in the boundary. [sent-88, score-0.24]
44 Instead of using lower envelopes of linear (modular) functions as they did, our transformation will employ lower envelopes of general second order functions. [sent-90, score-0.17]
45 A similar application of lower envelopes was used in [9], but for different potentials in a different application. [sent-91, score-0.364]
46 The problem of minimizing the cooperative cut potential (6) is equivalent to minimizing a pairwise function with additional |Eg | + 1auxiliary variables. [sent-93, score-0.831]
47 First, we rewrite the potential in Equation (6) as a third order pseudo-boolean function by represenPting it as a lower envelope of the two functions f1(x) = Pij∈Eg θij |xi − xj | and f2 (x) = T. [sent-96, score-0.364]
48 This strategy has been used to express higher order potentials that are concave functions of the value of modular function [15]. [sent-108, score-0.445]
49 If |G| is fixed, there is an FPTAS for minimizing energy ( I5f) Gw|it ihs any nondecreasing, nonnegative concave function F, i. [sent-112, score-0.238]
50 assume that the pairwise potentials are directed, i. [sent-123, score-0.445]
51 The potentials (6) (and equally (5)) extend to directed edges too: = Ψg(x) = minnXij∈Egθij(xi− xj)+,To. [sent-127, score-0.43]
52 (10) The two potentials ψij and ψji may belong to different groups g; in that case they are discounted differently and independently. [sent-128, score-0.337]
53 The cooperative cut potential (10) is equivalent to a pairwise potential with |Eg | + 1auxiliary variables. [sent-130, score-0.836]
54 But the problem (11) contains one additional binary variable per edge zij and per group of edges hg, and this large number makes any such direct relaxation approach computationally very expensive. [sent-135, score-0.27]
55 If we fix the value of the variables hg, then the non-submodular pairwise terms (xi + xj)hg become linear, and the resulting submodular energy function can be minimized exactly and efficiently. [sent-137, score-0.423]
56 As there are only few hg, we compute the MAP solution of the overall energy by finding the global minimum for each possible assignment of the hg using a graph cut algorithm [5]. [sent-138, score-0.908]
57 To speed up the search over all possible assignments of hg we use a dynamic max-flow algorithm [17] that rapidly solves a set of related max-flow problems. [sent-142, score-0.45]
58 Moreover, we sort the variables hg in decreasing order with respect to the total weight of edges that correspond to type g and make variables with lower weight change their value more often than those with higher weight. [sent-144, score-0.64]
59 In addition, we investigate three greedy heuristics that are polynomial in the number |G| of types: Greedy: oSmtairatl iwnit thh ea nllu hg = 1, a onfd t iteratively switch the label of that hg whose switch to zero decreases the energy most; repeat until there is no more improvement. [sent-146, score-1.289]
60 Descent: Like Greedy, but applying the switch whenever it improves the energy without searching for the best switch. [sent-147, score-0.181]
61 1-pass: Pass over all variables hg only once, applying all 111999777422 switches that decrease the energy. [sent-148, score-0.507]
62 All of these heuristics require testing whether changing the value of a particular variable hg will reduce the energy. [sent-149, score-0.541]
63 If we want to avoid searching over all assignments of the group indicator variables hg, then we can alternatively employ the common heuristic of simply pruning out the non-submodular terms, here the terms (xi + xj)hg, from the energy [19, 24]. [sent-152, score-0.196]
64 This truncation results in an under-approximation of the energy since the deleted terms contributed a positive cost. [sent-153, score-0.183]
65 Minimizing the remaining energy using graph cuts, we obtain solutions h∗ and x∗ . [sent-154, score-0.205]
66 Multiple labels Equivalently to binary MRFs, can be extended to variables xi a discrete space L. [sent-159, score-0.243]
67 ls O Oisn eto w wdaeyfin teo our higher-order models ∈ L that take labels in generalize ttahkee potentials glaebneel-rasleinzseit tihvee couplings Ψg(x) = P‘∈L F‘(Pij∈Eg ψij(xi, xj)1[xi=‘]). [sent-161, score-0.327]
68 PAs in the binary case, fixing all variables hg,‘ makes the energy pairwise and the potentials metric, and techniques such as the α-expansion algorithm [6] apply. [sent-163, score-0.683]
69 The multi-label model can be reduced to a nonsubmodular pairwise model analogous to the binary model. [sent-166, score-0.216]
70 The expansion move algorithm for cooperative multiple-label potentials of the form (5) returns a solution x that is a 2c-approximation to the optimal solution x∗: E(x) ≤ 2cE(x∗), for c = F‘01(0)/F‘02(Pij∈Eg θij). [sent-169, score-0.745]
71 The example results in Figure 5 show that label-sensitive coupling improves detailed segmentations in the multi-label case too. [sent-172, score-0.159]
72 In the experiments, we use piece-wise linear coupling functions F with one breakpoint of the form Ψg (x) = (12) λminiXj∈Egθij(xi− xj)+,ijX∈Egαθij(xi− xj)++ θg pwahrearme θtgers= ha ϑveP thiej∈ foElglθowij,ing and ef ϑe,cαt: λ ∈ co (n0t,ro1l]s. [sent-178, score-0.234]
73 th Tehe we thigrehet of the high-ordPer potentials relative to the unary ones, α defines the slope after the breakpoint, and ϑ controls the position of the breakpoint which is located at depicted in Figure 3. [sent-179, score-0.402]
74 θg, The unary potentials are computed by fitting a Gaussian mixture model with 5 components to pixels of seed regions. [sent-181, score-0.362]
75 We use an 8-neighbor graph structure and contrast-dependent Potts pairwise potentials θij = 2. [sent-182, score-0.511]
76 The exact solutions of the cooperative cut potentials extract fine structures much better than the standard model, and slightly improve on the approximate solutions. [sent-195, score-0.942]
77 0 is the energy for the MAP labeling of the standard pairwise MRF. [sent-200, score-0.321]
78 (a) Images from the dataset; (b) Ground truth segmentation;(c) MAP solution from a standard pairwise MRF model; (d) result of the iterative approximation from [11]; (e) Global minimum of cooperative cut energy (4) obtained by our method. [sent-229, score-0.889]
79 Moreover, these results demonstrate that not only an approximate minimum as in [11], but in particular the global minimum of the cooperative cut energy results in very low errors, especially compared to the standard model. [sent-241, score-0.78]
80 gz that cooperative cut energies very well capture the particularities of segmentation problems and settles the question raised in the introduction. [sent-249, score-0.652]
81 The edge groups and function F were defined analogous to the binary case, and we compute exact expansion moves, and the unary potentials were learned as GMMs as in the binary case (details in [16]). [sent-253, score-0.628]
82 Therefore, Figure 5 only shows example quantitative results that nevertheless suggest beneficial effects of edge coupling for detailed multi-label segmentations too. [sent-255, score-0.202]
83 Conclusions and Discussion In this paper, we explored a hierarchical model that is equivalent to the cooperative cut model of [11]. [sent-257, score-0.546]
84 (Column 1) Images from the dataset; (Column 2) Ground truth segmentation;(Column 3) MAP solution from a standard pairwise MRF model; (Column 4) result of our hierarchical model using the inference method described in section 4. [sent-272, score-0.217]
85 Parameters are chosen in such a way that the global minimum of the energy has maximum Hamming accuracy: λ = 1. [sent-277, score-0.172]
86 The algorithm solves the class of cooperative cut potentials proposed in [11] exactly or within a factor of (1 ? [sent-288, score-0.847]
87 ) and thereby admits to show that not only an approximate solution (as in [11]), but also the true MAP solution of those potentials overcomes the short-boundary bias that poses severe problems to the standard pairwise model for image segmentation. [sent-289, score-0.528]
88 The exact algorithm does not violate the NPhardness of cooperative cuts. [sent-292, score-0.419]
89 Instead, it demonstrates that the potentials (5) are fixed-parameter tractable: if the number ofedge groups is assumed to be constant (and in practice it is small), then the algorithm runs in polynomial-time. [sent-293, score-0.337]
90 If |G| is not used explicitly in the analysis and is not fixed, Ithfe |Gn no polynomial-time algorithm neaxliysstsis, ainn dfa icst, n othte fnix nedot, even a constant-factor approximation for the class of potentials (6) is possible [3 1]. [sent-295, score-0.301]
91 In general, the proposed algorithms are an effective and very practical method for a sub-class of minimum cuts with submodular costs [11] the images in the experiments have up to 6 · 105 x[v1a1r]ia –bl eths. [sent-297, score-0.173]
92 The Pn functions defined in Equations (14) and (15) in [12] are of the form (5) here, and shown to be amenable to expansion moves if the pairwise potentials form a semi-metric. [sent-300, score-0.526]
93 In addition, the formulation here does not require general submodular minimization (which can be impractical and also does not in general apply if asymmetric potentials are used). [sent-302, score-0.443]
94 The explicit hierarchical formulation in Figure 2 shows that the higher-order potentials for improved segmentations can be expressed as a deep multi-layer pairwise model with additional hidden (auxiliary) variables. [sent-305, score-0.552]
95 Considering the expressive power of cooperative cut models [11, 9, 12, 3 1], this connection highlights the representational power of multi-layer random fields. [sent-309, score-0.581]
96 Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images. [sent-335, score-0.216]
97 Submodularity beyond submodular energies: Coupling edges in graph cuts. [sent-372, score-0.225]
98 Minimizing sparse higher order energy functions of discrete variables. [sent-453, score-0.183]
99 A comparative study of energy minimization methods for Markov random fields. [sent-477, score-0.168]
100 Approximation and hardness results for label cut and related problems. [sent-501, score-0.226]
wordName wordTfidf (topN-words)
[('hg', 0.45), ('cooperative', 0.353), ('potentials', 0.301), ('ij', 0.267), ('eg', 0.241), ('cut', 0.193), ('xj', 0.156), ('pairwise', 0.144), ('energy', 0.139), ('coupling', 0.12), ('xi', 0.118), ('zij', 0.109), ('fptas', 0.094), ('heuristics', 0.091), ('envelope', 0.091), ('ixj', 0.083), ('submodular', 0.083), ('kohli', 0.079), ('edges', 0.076), ('auxiliary', 0.075), ('potential', 0.073), ('breakpoint', 0.07), ('congruous', 0.07), ('jegelka', 0.07), ('mhgint', 0.07), ('thg', 0.07), ('deep', 0.068), ('segmentation', 0.066), ('exact', 0.066), ('graph', 0.066), ('concave', 0.065), ('envelopes', 0.063), ('ijx', 0.063), ('osokin', 0.058), ('penalty', 0.057), ('variables', 0.057), ('cuts', 0.057), ('discontinuities', 0.055), ('directed', 0.053), ('pij', 0.053), ('hamming', 0.052), ('neighbouring', 0.052), ('mrf', 0.05), ('minnxij', 0.047), ('nondecreasing', 0.047), ('xixjhg', 0.047), ('inference', 0.046), ('map', 0.045), ('truncation', 0.044), ('functions', 0.044), ('interactive', 0.044), ('ii', 0.043), ('msrc', 0.043), ('edge', 0.043), ('binary', 0.042), ('switch', 0.042), ('polynomial', 0.042), ('moscow', 0.042), ('qpbf', 0.042), ('qpbfs', 0.042), ('lemma', 0.041), ('energies', 0.04), ('segmentations', 0.039), ('labeling', 0.038), ('penalizing', 0.037), ('boltzmann', 0.037), ('kolmogorov', 0.037), ('expansion', 0.037), ('groups', 0.036), ('mrfs', 0.036), ('theorem', 0.035), ('modular', 0.035), ('representational', 0.035), ('pairs', 0.035), ('minimizing', 0.034), ('minimum', 0.033), ('label', 0.033), ('corollary', 0.032), ('boykov', 0.031), ('rother', 0.031), ('boros', 0.031), ('lempitsky', 0.031), ('unary', 0.031), ('discount', 0.03), ('higherorder', 0.03), ('asymmetric', 0.03), ('analogous', 0.03), ('pixels', 0.03), ('gx', 0.029), ('approximate', 0.029), ('minimization', 0.029), ('markov', 0.028), ('types', 0.028), ('solution', 0.027), ('implications', 0.027), ('boundary', 0.027), ('labels', 0.026), ('ground', 0.026), ('pages', 0.025), ('xij', 0.025)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000007 24 cvpr-2013-A Principled Deep Random Field Model for Image Segmentation
Author: Pushmeet Kohli, Anton Osokin, Stefanie Jegelka
Abstract: We discuss a model for image segmentation that is able to overcome the short-boundary bias observed in standard pairwise random field based approaches. To wit, we show that a random field with multi-layered hidden units can encode boundary preserving higher order potentials such as the ones used in the cooperative cuts model of [11] while still allowing for fast and exact MAP inference. Exact inference allows our model to outperform previous image segmentation methods, and to see the true effect of coupling graph edges. Finally, our model can be easily extended to handle segmentation instances with multiple labels, for which it yields promising results.
2 0.21432613 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.
3 0.21046665 230 cvpr-2013-Joint 3D Scene Reconstruction and Class Segmentation
Author: Christian Häne, Christopher Zach, Andrea Cohen, Roland Angst, Marc Pollefeys
Abstract: Both image segmentation and dense 3D modeling from images represent an intrinsically ill-posed problem. Strong regularizers are therefore required to constrain the solutions from being ’too noisy’. Unfortunately, these priors generally yield overly smooth reconstructions and/or segmentations in certain regions whereas they fail in other areas to constrain the solution sufficiently. In this paper we argue that image segmentation and dense 3D reconstruction contribute valuable information to each other’s task. As a consequence, we propose a rigorous mathematical framework to formulate and solve a joint segmentation and dense reconstruction problem. Image segmentations provide geometric cues about which surface orientations are more likely to appear at a certain location in space whereas a dense 3D reconstruction yields a suitable regularization for the segmentation problem by lifting the labeling from 2D images to 3D space. We show how appearance-based cues and 3D surface orientation priors can be learned from training data and subsequently used for class-specific regularization. Experimental results on several real data sets highlight the advantages of our joint formulation.
4 0.2050111 156 cvpr-2013-Exploring Compositional High Order Pattern Potentials for Structured Output Learning
Author: Yujia Li, Daniel Tarlow, Richard Zemel
Abstract: When modeling structured outputs such as image segmentations, prediction can be improved by accurately modeling structure present in the labels. A key challenge is developing tractable models that are able to capture complex high level structure like shape. In this work, we study the learning of a general class of pattern-like high order potential, which we call Compositional High Order Pattern Potentials (CHOPPs). We show that CHOPPs include the linear deviation pattern potentials of Rother et al. [26] and also Restricted Boltzmann Machines (RBMs); we also establish the near equivalence of these two models. Experimentally, we show that performance is affected significantly by the degree of variability present in the datasets, and we define a quantitative variability measure to aid in studying this. We then improve CHOPPs performance in high variability datasets with two primary contributions: (a) developing a loss-sensitive joint learning procedure, so that internal pattern parameters can be learned in conjunction with other model potentials to minimize expected loss;and (b) learning an image-dependent mapping that encourages or inhibits patterns depending on image features. We also explore varying how multiple patterns are composed, and learning convolutional patterns. Quantitative results on challenging highly variable datasets show that the joint learning and image-dependent high order potentials can improve performance.
5 0.19698168 43 cvpr-2013-Analyzing Semantic Segmentation Using Hybrid Human-Machine CRFs
Author: Roozbeh Mottaghi, Sanja Fidler, Jian Yao, Raquel Urtasun, Devi Parikh
Abstract: Recent trends in semantic image segmentation have pushed for holistic scene understanding models that jointly reason about various tasks such as object detection, scene recognition, shape analysis, contextual reasoning. In this work, we are interested in understanding the roles of these different tasks in aiding semantic segmentation. Towards this goal, we “plug-in ” human subjects for each of the various components in a state-of-the-art conditional random field model (CRF) on the MSRC dataset. Comparisons among various hybrid human-machine CRFs give us indications of how much “head room ” there is to improve segmentation by focusing research efforts on each of the tasks. One of the interesting findings from our slew of studies was that human classification of isolated super-pixels, while being worse than current machine classifiers, provides a significant boost in performance when plugged into the CRF! Fascinated by this finding, we conducted in depth analysis of the human generated potentials. This inspired a new machine potential which significantly improves state-of-the-art performance on the MRSC dataset.
6 0.1925763 165 cvpr-2013-Fast Energy Minimization Using Learned State Filters
7 0.13477936 397 cvpr-2013-Simultaneous Super-Resolution of Depth and Images Using a Single Camera
8 0.1252407 86 cvpr-2013-Composite Statistical Inference for Semantic Segmentation
9 0.11215872 121 cvpr-2013-Detection- and Trajectory-Level Exclusion in Multiple Object Tracking
10 0.10460063 95 cvpr-2013-Continuous Inference in Graphical Models with Polynomial Energies
12 0.10007456 207 cvpr-2013-Human Pose Estimation Using a Joint Pixel-wise and Part-wise Formulation
13 0.090130247 25 cvpr-2013-A Sentence Is Worth a Thousand Pixels
14 0.08554358 466 cvpr-2013-Whitened Expectation Propagation: Non-Lambertian Shape from Shading and Shadow
15 0.084505439 6 cvpr-2013-A Comparative Study of Modern Inference Techniques for Discrete Energy Minimization Problems
16 0.082705289 62 cvpr-2013-Bilinear Programming for Human Activity Recognition with Unknown MRF Graphs
17 0.08253409 13 cvpr-2013-A Higher-Order CRF Model for Road Network Extraction
18 0.081943236 92 cvpr-2013-Constrained Clustering and Its Application to Face Clustering in Videos
19 0.081785373 128 cvpr-2013-Discrete MRF Inference of Marginal Densities for Non-uniformly Discretized Variable Space
20 0.080662839 406 cvpr-2013-Spatial Inference Machines
topicId topicWeight
[(0, 0.18), (1, 0.039), (2, 0.026), (3, 0.011), (4, 0.12), (5, 0.031), (6, 0.046), (7, 0.052), (8, -0.114), (9, -0.022), (10, 0.14), (11, 0.025), (12, -0.128), (13, 0.057), (14, -0.085), (15, 0.138), (16, -0.017), (17, 0.084), (18, 0.105), (19, -0.067), (20, -0.072), (21, -0.054), (22, -0.03), (23, 0.053), (24, 0.086), (25, -0.047), (26, -0.048), (27, 0.141), (28, -0.07), (29, -0.121), (30, 0.027), (31, -0.042), (32, 0.042), (33, 0.034), (34, -0.003), (35, 0.018), (36, 0.058), (37, -0.006), (38, -0.08), (39, 0.059), (40, 0.038), (41, 0.1), (42, 0.045), (43, -0.031), (44, -0.021), (45, -0.002), (46, -0.086), (47, -0.028), (48, -0.034), (49, -0.062)]
simIndex simValue paperId paperTitle
same-paper 1 0.96058285 24 cvpr-2013-A Principled Deep Random Field Model for Image Segmentation
Author: Pushmeet Kohli, Anton Osokin, Stefanie Jegelka
Abstract: We discuss a model for image segmentation that is able to overcome the short-boundary bias observed in standard pairwise random field based approaches. To wit, we show that a random field with multi-layered hidden units can encode boundary preserving higher order potentials such as the ones used in the cooperative cuts model of [11] while still allowing for fast and exact MAP inference. Exact inference allows our model to outperform previous image segmentation methods, and to see the true effect of coupling graph edges. Finally, our model can be easily extended to handle segmentation instances with multiple labels, for which it yields promising results.
2 0.786201 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.
3 0.75485194 165 cvpr-2013-Fast Energy Minimization Using Learned State Filters
Author: Matthieu Guillaumin, Luc Van_Gool, Vittorio Ferrari
Abstract: Pairwise discrete energies defined over graphs are ubiquitous in computer vision. Many algorithms have been proposed to minimize such energies, often concentrating on sparse graph topologies or specialized classes of pairwise potentials. However, when the graph is fully connected and the pairwise potentials are arbitrary, the complexity of even approximate minimization algorithms such as TRW-S grows quadratically both in the number of nodes and in the number of states a node can take. Moreover, recent applications are using more and more computationally expensive pairwise potentials. These factors make it very hard to employ fully connected models. In this paper we propose a novel, generic algorithm to approximately minimize any discrete pairwise energy function. Our method exploits tractable sub-energies to filter the domain of the function. The parameters of the filter are learnt from instances of the same class of energies with good candidate solutions. Compared to existing methods, it efficiently handles fully connected graphs, with many states per node, and arbitrary pairwise potentials, which might be expensive to compute. We demonstrate experimentally on two applications that our algorithm is much more efficient than other generic minimization algorithms such as TRW-S, while returning essentially identical solutions.
4 0.7259779 156 cvpr-2013-Exploring Compositional High Order Pattern Potentials for Structured Output Learning
Author: Yujia Li, Daniel Tarlow, Richard Zemel
Abstract: When modeling structured outputs such as image segmentations, prediction can be improved by accurately modeling structure present in the labels. A key challenge is developing tractable models that are able to capture complex high level structure like shape. In this work, we study the learning of a general class of pattern-like high order potential, which we call Compositional High Order Pattern Potentials (CHOPPs). We show that CHOPPs include the linear deviation pattern potentials of Rother et al. [26] and also Restricted Boltzmann Machines (RBMs); we also establish the near equivalence of these two models. Experimentally, we show that performance is affected significantly by the degree of variability present in the datasets, and we define a quantitative variability measure to aid in studying this. We then improve CHOPPs performance in high variability datasets with two primary contributions: (a) developing a loss-sensitive joint learning procedure, so that internal pattern parameters can be learned in conjunction with other model potentials to minimize expected loss;and (b) learning an image-dependent mapping that encourages or inhibits patterns depending on image features. We also explore varying how multiple patterns are composed, and learning convolutional patterns. Quantitative results on challenging highly variable datasets show that the joint learning and image-dependent high order potentials can improve performance.
5 0.6925239 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.
7 0.67468876 308 cvpr-2013-Nonlinearly Constrained MRFs: Exploring the Intrinsic Dimensions of Higher-Order Cliques
8 0.64853406 6 cvpr-2013-A Comparative Study of Modern Inference Techniques for Discrete Energy Minimization Problems
9 0.64428467 95 cvpr-2013-Continuous Inference in Graphical Models with Polynomial Energies
10 0.64205265 262 cvpr-2013-Learning for Structured Prediction Using Approximate Subgradient Descent with Working Sets
11 0.64175278 43 cvpr-2013-Analyzing Semantic Segmentation Using Hybrid Human-Machine CRFs
12 0.64030159 466 cvpr-2013-Whitened Expectation Propagation: Non-Lambertian Shape from Shading and Shadow
13 0.60251904 13 cvpr-2013-A Higher-Order CRF Model for Road Network Extraction
14 0.59498078 128 cvpr-2013-Discrete MRF Inference of Marginal Densities for Non-uniformly Discretized Variable Space
15 0.58133185 132 cvpr-2013-Discriminative Re-ranking of Diverse Segmentations
16 0.57778811 51 cvpr-2013-Auxiliary Cuts for General Classes of Higher Order Functionals
17 0.55579251 25 cvpr-2013-A Sentence Is Worth a Thousand Pixels
18 0.54502511 86 cvpr-2013-Composite Statistical Inference for Semantic Segmentation
19 0.51592368 171 cvpr-2013-Fast Trust Region for Segmentation
20 0.51486969 230 cvpr-2013-Joint 3D Scene Reconstruction and Class Segmentation
topicId topicWeight
[(10, 0.117), (16, 0.015), (26, 0.036), (33, 0.323), (67, 0.049), (69, 0.039), (87, 0.093), (93, 0.231)]
simIndex simValue paperId paperTitle
1 0.94078863 208 cvpr-2013-Hyperbolic Harmonic Mapping for Constrained Brain Surface Registration
Author: Rui Shi, Wei Zeng, Zhengyu Su, Hanna Damasio, Zhonglin Lu, Yalin Wang, Shing-Tung Yau, Xianfeng Gu
Abstract: Automatic computation of surface correspondence via harmonic map is an active research field in computer vision, computer graphics and computational geometry. It may help document and understand physical and biological phenomena and also has broad applications in biometrics, medical imaging and motion capture. Although numerous studies have been devoted to harmonic map research, limited progress has been made to compute a diffeomorphic harmonic map on general topology surfaces with landmark constraints. This work conquer this problem by changing the Riemannian metric on the target surface to a hyperbolic metric, so that the harmonic mapping is guaranteed to be a diffeomorphism under landmark constraints. The computational algorithms are based on the Ricci flow method and the method is general and robust. We apply our algorithm to study constrained human brain surface registration problem. Experimental results demonstrate that, by changing the Riemannian metric, the registrations are always diffeomorphic, and achieve relative high performance when evaluated with some popular cortical surface registration evaluation standards.
2 0.89154118 120 cvpr-2013-Detecting and Naming Actors in Movies Using Generative Appearance Models
Author: Vineet Gandhi, Remi Ronfard
Abstract: We introduce a generative model for learning person and costume specific detectors from labeled examples. We demonstrate the model on the task of localizing and naming actors in long video sequences. More specifically, the actor’s head and shoulders are each represented as a constellation of optional color regions. Detection can proceed despite changes in view-point and partial occlusions. We explain how to learn the models from a small number of labeled keyframes or video tracks, and how to detect novel appearances of the actors in a maximum likelihood framework. We present results on a challenging movie example, with 81% recall in actor detection (coverage) and 89% precision in actor identification (naming).
same-paper 3 0.88756162 24 cvpr-2013-A Principled Deep Random Field Model for Image Segmentation
Author: Pushmeet Kohli, Anton Osokin, Stefanie Jegelka
Abstract: We discuss a model for image segmentation that is able to overcome the short-boundary bias observed in standard pairwise random field based approaches. To wit, we show that a random field with multi-layered hidden units can encode boundary preserving higher order potentials such as the ones used in the cooperative cuts model of [11] while still allowing for fast and exact MAP inference. Exact inference allows our model to outperform previous image segmentation methods, and to see the true effect of coupling graph edges. Finally, our model can be easily extended to handle segmentation instances with multiple labels, for which it yields promising results.
4 0.87611586 449 cvpr-2013-Unnatural L0 Sparse Representation for Natural Image Deblurring
Author: Li Xu, Shicheng Zheng, Jiaya Jia
Abstract: We show in this paper that the success of previous maximum a posterior (MAP) based blur removal methods partly stems from their respective intermediate steps, which implicitly or explicitly create an unnatural representation containing salient image structures. We propose a generalized and mathematically sound L0 sparse expression, together with a new effective method, for motion deblurring. Our system does not require extra filtering during optimization and demonstrates fast energy decreasing, making a small number of iterations enough for convergence. It also provides a unifiedframeworkfor both uniform andnon-uniform motion deblurring. We extensively validate our method and show comparison with other approaches with respect to convergence speed, running time, and result quality.
5 0.87348187 89 cvpr-2013-Computationally Efficient Regression on a Dependency Graph for Human Pose Estimation
Author: Kota Hara, Rama Chellappa
Abstract: We present a hierarchical method for human pose estimation from a single still image. In our approach, a dependency graph representing relationships between reference points such as bodyjoints is constructed and thepositions of these reference points are sequentially estimated by a successive application of multidimensional output regressions along the dependency paths, starting from the root node. Each regressor takes image features computed from an image patch centered on the current node ’s position estimated by the previous regressor and is specialized for estimating its child nodes ’ positions. The use of the dependency graph allows us to decompose a complex pose estimation problem into a set of local pose estimation problems that are less complex. We design a dependency graph for two commonly used human pose estimation datasets, the Buffy Stickmen dataset and the ETHZ PASCAL Stickmen dataset, and demonstrate that our method achieves comparable accuracy to state-of-the-art results on both datasets with significantly lower computation time than existing methods. Furthermore, we propose an importance weighted boosted re- gression trees method for transductive learning settings and demonstrate the resulting improved performance for pose estimation tasks.
6 0.85495663 376 cvpr-2013-Salient Object Detection: A Discriminative Regional Feature Integration Approach
7 0.85024768 44 cvpr-2013-Area Preserving Brain Mapping
8 0.84220052 242 cvpr-2013-Label Propagation from ImageNet to 3D Point Clouds
9 0.8403784 365 cvpr-2013-Robust Real-Time Tracking of Multiple Objects by Volumetric Mass Densities
10 0.84033281 98 cvpr-2013-Cross-View Action Recognition via a Continuous Virtual Path
11 0.83999801 111 cvpr-2013-Dense Reconstruction Using 3D Object Shape Priors
12 0.83953446 187 cvpr-2013-Geometric Context from Videos
13 0.83906525 121 cvpr-2013-Detection- and Trajectory-Level Exclusion in Multiple Object Tracking
14 0.83887202 256 cvpr-2013-Learning Structured Hough Voting for Joint Object Detection and Occlusion Reasoning
15 0.83882141 147 cvpr-2013-Ensemble Learning for Confidence Measures in Stereo Vision
16 0.83855551 362 cvpr-2013-Robust Monocular Epipolar Flow Estimation
17 0.83849919 143 cvpr-2013-Efficient Large-Scale Structured Learning
18 0.83837539 329 cvpr-2013-Perceptual Organization and Recognition of Indoor Scenes from RGB-D Images
19 0.83819425 446 cvpr-2013-Understanding Indoor Scenes Using 3D Geometric Phrases
20 0.83775693 14 cvpr-2013-A Joint Model for 2D and 3D Pose Estimation from a Single Image