cvpr cvpr2013 cvpr2013-171 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Lena Gorelick, Frank R. Schmidt, Yuri Boykov
Abstract: Trust region is a well-known general iterative approach to optimization which offers many advantages over standard gradient descent techniques. In particular, it allows more accurate nonlinear approximation models. In each iteration this approach computes a global optimum of a suitable approximation model within a fixed radius around the current solution, a.k.a. trust region. In general, this approach can be used only when some efficient constrained optimization algorithm is available for the selected nonlinear (more accurate) approximation model. In this paper we propose a Fast Trust Region (FTR) approach for optimization of segmentation energies with nonlinear regional terms, which are known to be challenging for existing algorithms. These energies include, but are not limited to, KL divergence and Bhattacharyya distance between the observed and the target appearance distributions, volume constraint on segment size, and shape prior constraint in a form of 퐿2 distance from target shape moments. Our method is 1-2 orders of magnitude faster than the existing state-of-the-art methods while converging to comparable or better solutions.
Reference: text
sentIndex sentText sentNum sentScore
1 ca 1 Computer Vision Group University of Western Ontario, Canada Abstract Trust region is a well-known general iterative approach to optimization which offers many advantages over standard gradient descent techniques. [sent-7, score-0.418]
2 In particular, it allows more accurate nonlinear approximation models. [sent-8, score-0.136]
3 In each iteration this approach computes a global optimum of a suitable approximation model within a fixed radius around the current solution, a. [sent-9, score-0.21]
4 In this paper we propose a Fast Trust Region (FTR) approach for optimization of segmentation energies with nonlinear regional terms, which are known to be challenging for existing algorithms. [sent-14, score-0.37]
5 These energies include, but are not limited to, KL divergence and Bhattacharyya distance between the observed and the target appearance distributions, volume constraint on segment size, and shape prior constraint in a form of 퐿2 distance from target shape moments. [sent-15, score-0.733]
6 Introduction In the recent years there is a general trend in computer vision towards using complex non-linear energies with higher-order regional terms for the task of image segmentation, co-segmentation and stereo [10, 7, 14, 2, 1, 11, 8]. [sent-18, score-0.257]
7 In image segmentation such energies are particularly useful when there is a prior knowledge of the appearance model or the shape of an object being segmented. [sent-19, score-0.269]
8 One straightforward approach to minimizing such energies could be based on gradient descent. [sent-23, score-0.218]
9 In the context of level-set techniques the corresponding linear approximation model for 퐸(푆) combines a first-order Taylor term for 푅(푆) with the standard curvature-flow term for 푄(푆). [sent-24, score-0.156]
10 Linear approximation model may work reasonably well for simple quadratic regional terms, e. [sent-25, score-0.29]
11 However, it is well known that robust implementation of gradients descent for more complex regional constraints requires tiny time steps yielding slow running times and sensitivity to initialization [7, 1]. [sent-28, score-0.329]
12 Significantly better optimization and speed are often achieved by methods specifically designed for particular regional constraints, e. [sent-29, score-0.152]
13 In this paper we propose a fast algorithm for minimizing general high-order energies like (1) based on more accurate non-linear approximation models and a general trust region framework for iterative optimization. [sent-32, score-1.095]
14 We still compute a first-order approximation 푈0 (푆) for the regional term 푅(푆). [sent-33, score-0.281]
15 At each iteration we use nonlinear approximation model 퐸˜(푆) = 푈0(푆) + 푄(푆) similar to those in˜ [10, 14, 8]. [sent-35, score-0.174]
16 Unlike [10, 14] we globally optimize such approximation models within a trust region ∣푆 − 푆0 ∣퐿2 ≤ 푑, which is a ball of certain radius 푑 around c∣∣u푆rr −en 푆t s∣o∣luti≤on 푑 ,푆 w0. [sent-36, score-1.039]
17 At each iteration, ∣ ∣ they use a parametric max-flow technique to exhaustively explore solutions for all values of 푑 and find the solution with the largest decrease of the original energy 퐸(푆). [sent-38, score-0.158]
18 OLnager aofn our contributions is˜ a derivation of a simple analytic relationship between radius 푑 and Lagrange multiplier 휆. [sent-42, score-0.217]
19 This allows us to translate the standard adaptive scheme controlling the trust region radius 푑 into an efficient adaptive scheme for the Lagrange multiplier 휆. [sent-43, score-1.102]
20 Overview of Trust Region Framework Trust region is a general iterative optimization framework that in some sense is dual to the gradient descent, see Fig. [sent-55, score-0.241]
21 While gradient descent fixes the direction of the step and then chooses the step size, trust region fixes the step size and then computes the optimal descent direction, as described below. [sent-57, score-1.372]
22 At each iteration, an approximate model of the energy is constructed near the current solution. [sent-58, score-0.162]
23 The global minimum ofthe approximate model within the trust region gives a new solution. [sent-63, score-0.863]
24 The size of the trust region is adjusted for the next iteration based on the quality of the current approximation. [sent-65, score-0.934]
25 Variants of trust region approach differ in the kind of approximate model used, optimizer for the trust-region subproblem, and a merit function to decide on the acceptance of the candidate solution and adjustment of the next trust region size. [sent-66, score-1.7]
26 For a detailed review of trust region methods see [17]. [sent-67, score-0.839]
27 One interesting example of the general trust region framework is well-known Levenberg–Marquardt algorithm, which is commonly used in multi-view geometry to minimize non-linear re-projection errors [9]. [sent-68, score-0.839]
28 Inspired by the ideas in [6, 8], we propose a trust region approach for minimizing high-order segmentation energies 퐸(푆) in (1). [sent-69, score-1.047]
29 The general idea outlined in Algorithm 1 is consistent with the standard trust region practices [3, 17]. [sent-70, score-0.839]
30 Given current solution 푆0, energy 퐸(푆) is approximated by 퐸˜(푆) = 푈0(푆) + 푄(푆), (2) where 푈0 (푆) is ˜the first order Taylor approximation of the non-linear term 푅(푆) near 푆0. [sent-71, score-0.313]
31 Approximation 퐸˜(푆) for energy 퐸(푆) is constructed near →푆0 푆. [sent-77, score-0.137]
32 The blue line shows the spectrum of possible trust region steps (moves). [sent-80, score-0.892]
33 Small 푑 gives steps aligned with gradient descent direction, while large 푑 would give step 푆˜ similar to Newton’s approach. [sent-81, score-0.266]
34 퐸˜ within a ball of (3) Once a candidate solution 푆∗ is obtained, the quality of the approximation is measured using the ratio between the actual and predicted reduction in energy. [sent-83, score-0.263]
35 Based on this ratio, current solution 푆0 is updated in line 10 and the trust region size 푑 is adjusted in line 12. [sent-84, score-1.024]
36 It is common to set the parameter 휏1 in line 10 to zero so that any candidate solution decreasing the actual energy is accepted. [sent-85, score-0.182]
37 Reduction ratio above 휏2 implies that approximation model 퐸˜ is sufficiently good within the current trust region and that˜ the trust region size (step size) could be increased in the ne˜xt iteration. [sent-88, score-1.829]
38 Our Algorithm Constrained non-linear optimization (3) is a central problem for a general trust region approach. [sent-91, score-0.839]
39 2 discusses the relationship between trust region size 푑 in (3) and Lagrange multiplier 휆. [sent-95, score-1.008]
40 Relationship between 휆 and 푑 The standard trust region approach (see Algorithm 1) adaptively adjusts the distance parameter 푑. [sent-138, score-0.862]
41 Since we use the Lagrangian formulation (4) to solve the trust region subproblem (3), we do not directly control 푑. [sent-139, score-0.878]
42 However, for each Lagrangian multiplier 휆 there is a corresponding distance 푑 such that minimizer 푆휆 of (4) also solves (3) for that 푑. [sent-141, score-0.165]
43 Using log-scale for both and 휆, it can be seen that the slope of empirical dependence is the same as the slope of 1/푑 which justifies our heuristic. [sent-171, score-0.163]
44 It is based on the high-level principles of the trust region framework presented in Algorithm 1, but uses Lagrangian formulation (4) instead ofconstrained optimiza- tion in (3). [sent-175, score-0.839]
45 The relationship between Lagrange multiplier 휆 and distance 푑 established in Section 3. [sent-176, score-0.17]
46 We can show that our algorithm converges: in each iteration the method solves the trust region sub-problem with the given multiplier 휆 (Line 6). [sent-179, score-0.975]
47 The algorithm either decreases the energy by accepting the candidate solution (line 20) or reduces the trust region (Line 23). [sent-180, score-0.968]
48 When the trust region is so small that 푆휆 = 푆0 (Line 9), one more attempt is made using 휆max (see Property 2). [sent-181, score-0.839]
49 If no reduction in actual energy is achieved using 푆휆max (Line 16), we have arrived at local minimum [6] and the algorithm stops (Line 17). [sent-182, score-0.193]
50 Following recommendations for standard trust region methods [17], we set parameter 휏2 = 0. [sent-183, score-0.839]
51 Reduction ratio Δ퐴/Δ푃 above 휏2 implies good approximation quality, allowing increase of the trust region. [sent-185, score-0.813]
52 Relationship to Gradient Descent A trust region approach can be seen as a generalization of a gradient descent approach. [sent-188, score-1.105]
53 In this section we will revisit this relationship in the case of the specific energy that we use. [sent-189, score-0.156]
54 2 we express the energy as a function of segmentation boundary ∂푆. [sent-195, score-0.186]
55 Note that Equation (11) is an update step that may arise during gradient descent approaches using the level-set formulation. [sent-202, score-0.266]
56 111777111755 Another difference is that our trust region approach does not follow −∇퐸˜(푆0) but rather −∇퐸˜(푆휆) instead. [sent-205, score-0.839]
57 Obviously 푆휆 becomes a gradient descent step for such small 푡. [sent-208, score-0.266]
58 According to (7), 푆휆max is a descent step of the energy, i. [sent-210, score-0.177]
59 We use this property˜ in order to si˜mulate a gradient descent approach. [sent-213, score-0.266]
60 Starting with segmentation 푆0, at iteration 푘 + 1, we set 푆푘+1 = 푆휆max computed with respect to segmentation 푆푘. [sent-214, score-0.196]
61 We show in˜ Section 4 that such a simulated gradient descent approac˜h is not only much slower than our trustregion approach, but also less reliable as it is prone to get stuck in a weaker local minimum. [sent-216, score-0.466]
62 We selected several examples of segmentation energies with non-linear regional constraints. [sent-219, score-0.336]
63 These include volume constraint, shape prior in a form of 퐿2 distance from target shape moments, as well as Kullback-Leibler divergence and Bhattacharyya distance between the segment and target appearance distributions. [sent-220, score-0.52]
64 We compare the performance of our Fast Trust Region approach with the exact line-search algorithm proposed in [8] and simulated gradient descent described in Section 3. [sent-221, score-0.398]
65 4, because these are the most related general algorithms for minimization of non-linear regional segmentation energies. [sent-222, score-0.231]
66 While the running time of simulated gradient descent could potentially be improved by using level-sets implementation, it would still be prone to getting stuck in weak local minimum when optimizing complex energies (see Figures 7-9). [sent-225, score-0.574]
67 This behavior of simulated gradient descent method also conforms to the conclusions made in [2, 1] regarding gradient descent based on level-sets. [sent-226, score-0.62]
68 Volume Constraint Below, we perform image segmentation with volume constraint. [sent-233, score-0.147]
69 Namely, 퐸(푆) = 푅(푆) + 푄(푆) where 푅(푆) =12(⟨1Ω,푆⟩ − 푉 )2, 푉 is a given target volume and 푄(푆) is a 16-neighborhood quadratic length term, 푄(푆) = 휆∑푤푝푞 (∑푝,푞) ⋅ 훿(푠푝 = 푠푞). [sent-234, score-0.202]
70 This is a relatively simple energy and Figure 4(top) shows that FTR as well as exact line-search [8] and simulated gradient descent converge to good local minimum solutions (circle), with FTR being significantly faster (bottom). [sent-237, score-0.581]
71 Figure 5 shows four examples of vertebrae segmentation with volume constraint. [sent-238, score-0.238]
72 Since the volume varies considerably across vertebrae we use a range volume constraint that penalizes deviations from the allowable range, namely 푅(푆)=⎨⎧1 0/2 ( ⟨ 1 Ω ,푆 ⟩ − 푉 m ainx) 2 ioft∣h 푆 er∣ w ≥≤is 푉 e. [sent-240, score-0.281]
73 Four examples of vertebrae segmentation with range volume constraint, color coded (yellow, green, red, cyan). [sent-242, score-0.238]
74 In this example, in addition to the volume constraint and contrast-sensitive quadratic length term we make use of Boykov-Jolly style log-likelihoods [4] based on color histograms. [sent-247, score-0.185]
75 Again, all three metho˜ds (FTR, exact line-search and simulated gradient descent) 퐸˜(푆) + + to good solutions (see Figure 5) with FTR being significantly faster. [sent-250, score-0.25]
76 The volume constraint strongly controls the resulting segmentation compared to the one obtained without the constraint (top-right). [sent-252, score-0.255]
77 Shape Prior with Geometric Shape Moments Below, we perform image segmentation with shape prior using 퐿2 distance between segment and target geometric shape moments. [sent-255, score-0.276]
78 Here, 퐷(푆) is a standard log-likelihood unary term based on color histograms, 푄(푆) is a contrastsensitive quadratic length term and 푅(푆) is given by 푅(푆) =12푝+∑푞≤푑(⟨푥푝푦푞,푆⟩ − 푚푝푞)2, with 푑 = denoting the target geometric moment of order + 푞. [sent-257, score-0.21]
79 The target shape moments and appearance model are computed for the user provided input (ellipse). [sent-260, score-0.258]
80 We used moments of up to order 2 excluding volume and appearance models with 100 bins. [sent-261, score-0.19]
81 푝∑+푞≤푑 Figure 6 shows an example of liver segmentation with the shape prior constraint. [sent-264, score-0.152]
82 The target shape moments as well as the foreground and background appearance models are computed from an input ellipse (top-left) provided by user as in [11]. [sent-265, score-0.283]
83 This energy can be optimized quite well with the exact line-search and the simulated gradient descent methods, but it is 10 to 100 times faster to do so with FTR (bottom). [sent-267, score-0.528]
84 Shape prior constraint controls the resulting segmentation compared to the best segmentation obtained without shape prior (top-right). [sent-268, score-0.25]
85 In the next experiments we show that as the segmentation energy becomes more complex, FTR becomes more advantageous since Gradient Descent often gets stuck in weak local minimum while exact line-search is too slow. [sent-270, score-0.345]
86 Matching Target Appearance In the experiments below we apply FTR to optimize segmentation energies where the goal is to match a given target 111777111977 Figure 7. [sent-273, score-0.282]
87 Matching target appearance: via log-likelihood data term a la Boykov-Jolly [4] with 15 bins per channel (top), KL divergence with 15 bins per channel (middle) and KL divergence with 100 bins per channel (bottom). [sent-274, score-0.602]
88 appearance distribution using either Kullback-Leibler divergence [8] or Bhattacharyya distance [1, 8] between the segment and target appearance distributions. [sent-277, score-0.302]
89 The target appearance distributions for the object and background were obtained from the ground truth segments. [sent-281, score-0.145]
90 Figure 7 illustrates the superior performance of FTR compared to the simulated gradient descent method. [sent-283, score-0.354]
91 Matching target appearance using KL divergence and 100 bins per channel. [sent-286, score-0.299]
92 Matching target appearance using Bhattacharyya distance and 100 bins per channel. [sent-290, score-0.235]
93 third), the Gradient Descent approach gets stuck in weak local minimum while our FTR efficiently converges to good solutions (see right column for comparing the energy). [sent-292, score-0.144]
94 Figures 8-9 show additional examples with KL divergence and Bhattacharyya distance respectively, using 100 bins per color channel and regularizing with contrast sensitive quadratic length term 푄(푆). [sent-293, score-0.274]
95 The simulated gradient descent is unable to reduce the energy, while exact line-search is about 100 times slower than the proposed FTR. [sent-294, score-0.398]
96 Robustness to reduction ratio 휏2 with KL divergence, 100 bins per channel, 휆Smooth = 0. [sent-304, score-0.153]
97 We use a Lagrangian formulation of the trust region subproblem and derive a simple analytic relationship between step size 푑 and Lagrange multiplier 휆. [sent-309, score-1.05]
98 This relationship allows to control the trust region size via 휆. [sent-310, score-0.888]
99 We analyze the relationship between FTR and classical gradient descent approaches based on level-sets. [sent-312, score-0.315]
100 [2] [3] [4] [5] [6] [7] [8] [9] [10] Graph cut segmentation with a global constraint: Recovering region distribution via a bound of the Bhattacharyya measure. [sent-327, score-0.231]
wordName wordTfidf (topN-words)
[('trust', 0.687), ('ftr', 0.351), ('descent', 0.177), ('regional', 0.152), ('region', 0.152), ('lagrangian', 0.116), ('energy', 0.107), ('energies', 0.105), ('approximation', 0.102), ('target', 0.098), ('multiplier', 0.098), ('app', 0.093), ('bhattacharyya', 0.092), ('vertebrae', 0.091), ('dist', 0.091), ('gradient', 0.089), ('simulated', 0.088), ('divergence', 0.087), ('segmentation', 0.079), ('moments', 0.075), ('taylor', 0.07), ('convergedflag', 0.068), ('volume', 0.068), ('bins', 0.067), ('stuck', 0.067), ('kl', 0.064), ('reduction', 0.062), ('lagrange', 0.062), ('boykov', 0.061), ('max', 0.054), ('constraint', 0.054), ('line', 0.053), ('ball', 0.053), ('dependence', 0.052), ('relationship', 0.049), ('appearance', 0.047), ('init', 0.046), ('ioft', 0.046), ('argmin', 0.046), ('curr', 0.045), ('fixes', 0.045), ('trustregion', 0.045), ('radius', 0.045), ('kolmogorov', 0.045), ('exact', 0.044), ('minimizer', 0.044), ('slope', 0.04), ('ayed', 0.04), ('trusted', 0.04), ('subproblem', 0.039), ('shape', 0.038), ('schmidt', 0.038), ('iteration', 0.038), ('freiburg', 0.037), ('ution', 0.037), ('quadratic', 0.036), ('induces', 0.035), ('liver', 0.035), ('yuri', 0.035), ('october', 0.035), ('smooth', 0.034), ('channel', 0.034), ('nonlinear', 0.034), ('tru', 0.032), ('adjusted', 0.032), ('ben', 0.031), ('empirical', 0.031), ('property', 0.031), ('near', 0.03), ('monotonic', 0.03), ('solutions', 0.029), ('gorelick', 0.028), ('medical', 0.028), ('term', 0.027), ('adaptive', 0.026), ('fast', 0.025), ('ellipse', 0.025), ('ol', 0.025), ('analytic', 0.025), ('current', 0.025), ('exhaustive', 0.025), ('translate', 0.024), ('minimizing', 0.024), ('holds', 0.024), ('weak', 0.024), ('minimum', 0.024), ('ratio', 0.024), ('iofth', 0.023), ('cyan', 0.023), ('distance', 0.023), ('rother', 0.023), ('er', 0.023), ('faster', 0.023), ('parameterization', 0.023), ('solution', 0.022), ('discusses', 0.022), ('moment', 0.022), ('break', 0.022), ('june', 0.022), ('scheme', 0.022)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999994 171 cvpr-2013-Fast Trust Region for Segmentation
Author: Lena Gorelick, Frank R. Schmidt, Yuri Boykov
Abstract: Trust region is a well-known general iterative approach to optimization which offers many advantages over standard gradient descent techniques. In particular, it allows more accurate nonlinear approximation models. In each iteration this approach computes a global optimum of a suitable approximation model within a fixed radius around the current solution, a.k.a. trust region. In general, this approach can be used only when some efficient constrained optimization algorithm is available for the selected nonlinear (more accurate) approximation model. In this paper we propose a Fast Trust Region (FTR) approach for optimization of segmentation energies with nonlinear regional terms, which are known to be challenging for existing algorithms. These energies include, but are not limited to, KL divergence and Bhattacharyya distance between the observed and the target appearance distributions, volume constraint on segment size, and shape prior constraint in a form of 퐿2 distance from target shape moments. Our method is 1-2 orders of magnitude faster than the existing state-of-the-art methods while converging to comparable or better solutions.
2 0.093826987 51 cvpr-2013-Auxiliary Cuts for General Classes of Higher Order Functionals
Author: Ismail Ben Ayed, Lena Gorelick, Yuri Boykov
Abstract: Several recent studies demonstrated that higher order (non-linear) functionals can yield outstanding performances in the contexts of segmentation, co-segmentation and tracking. In general, higher order functionals result in difficult problems that are not amenable to standard optimizers, and most of the existing works investigated particular forms of such functionals. In this study, we derive general bounds for a broad class of higher order functionals. By introducing auxiliary variables and invoking the Jensen ’s inequality as well as some convexity arguments, we prove that these bounds are auxiliary functionals for various non-linear terms, which include but are not limited to several affinity measures on the distributions or moments of segment appearance and shape, as well as soft constraints on segment volume. From these general-form bounds, we state various non-linear problems as the optimization of auxiliary functionals by graph cuts. The proposed bound optimizers are derivative-free, and consistently yield very steep functional decreases, thereby converging within a few graph cuts. We report several experiments on color and medical data, along with quantitative comparisons to stateof-the-art methods. The results demonstrate competitive performances of the proposed algorithms in regard to accuracy and convergence speed, and confirm their potential in various vision and medical applications.
3 0.090930246 376 cvpr-2013-Salient Object Detection: A Discriminative Regional Feature Integration Approach
Author: Huaizu Jiang, Jingdong Wang, Zejian Yuan, Yang Wu, Nanning Zheng, Shipeng Li
Abstract: Salient object detection has been attracting a lot of interest, and recently various heuristic computational models have been designed. In this paper, we regard saliency map computation as a regression problem. Our method, which is based on multi-level image segmentation, uses the supervised learning approach to map the regional feature vector to a saliency score, and finally fuses the saliency scores across multiple levels, yielding the saliency map. The contributions lie in two-fold. One is that we show our approach, which integrates the regional contrast, regional property and regional backgroundness descriptors together to form the master saliency map, is able to produce superior saliency maps to existing algorithms most of which combine saliency maps heuristically computed from different types of features. The other is that we introduce a new regional feature vector, backgroundness, to characterize the background, which can be regarded as a counterpart of the objectness descriptor [2]. The performance evaluation on several popular benchmark data sets validates that our approach outperforms existing state-of-the-arts.
4 0.088677339 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.
5 0.074571416 164 cvpr-2013-Fast Convolutional Sparse Coding
Author: Hilton Bristow, Anders Eriksson, Simon Lucey
Abstract: Sparse coding has become an increasingly popular method in learning and vision for a variety of classification, reconstruction and coding tasks. The canonical approach intrinsically assumes independence between observations during learning. For many natural signals however, sparse coding is applied to sub-elements (i.e. patches) of the signal, where such an assumption is invalid. Convolutional sparse coding explicitly models local interactions through the convolution operator, however the resulting optimization problem is considerably more complex than traditional sparse coding. In this paper, we draw upon ideas from signal processing and Augmented Lagrange Methods (ALMs) to produce a fast algorithm with globally optimal subproblems and super-linear convergence.
6 0.065896094 33 cvpr-2013-Active Contours with Group Similarity
7 0.065723591 165 cvpr-2013-Fast Energy Minimization Using Learned State Filters
8 0.062459126 24 cvpr-2013-A Principled Deep Random Field Model for Image Segmentation
9 0.062108383 300 cvpr-2013-Multi-target Tracking by Lagrangian Relaxation to Min-cost Network Flow
10 0.061754763 370 cvpr-2013-SCALPEL: Segmentation Cascades with Localized Priors and Efficient Learning
11 0.061185732 20 cvpr-2013-A New Model and Simple Algorithms for Multi-label Mumford-Shah Problems
13 0.058258045 397 cvpr-2013-Simultaneous Super-Resolution of Depth and Images Using a Single Camera
14 0.056475591 262 cvpr-2013-Learning for Structured Prediction Using Approximate Subgradient Descent with Working Sets
15 0.053401288 285 cvpr-2013-Minimum Uncertainty Gap for Robust Visual Tracking
16 0.052794885 321 cvpr-2013-PDM-ENLOR: Learning Ensemble of Local PDM-Based Regressions
17 0.052019082 457 cvpr-2013-Visual Tracking via Locality Sensitive Histograms
18 0.050019335 121 cvpr-2013-Detection- and Trajectory-Level Exclusion in Multiple Object Tracking
19 0.049756687 420 cvpr-2013-Supervised Descent Method and Its Applications to Face Alignment
20 0.049745817 468 cvpr-2013-Winding Number for Region-Boundary Consistent Salient Contour Extraction
topicId topicWeight
[(0, 0.131), (1, 0.034), (2, 0.019), (3, 0.03), (4, 0.04), (5, -0.011), (6, 0.029), (7, -0.015), (8, -0.04), (9, 0.026), (10, 0.05), (11, -0.01), (12, -0.035), (13, -0.016), (14, -0.027), (15, -0.0), (16, -0.006), (17, 0.0), (18, 0.062), (19, 0.041), (20, -0.053), (21, 0.013), (22, -0.06), (23, -0.017), (24, 0.081), (25, 0.05), (26, 0.001), (27, 0.025), (28, 0.01), (29, -0.047), (30, 0.083), (31, 0.028), (32, -0.035), (33, -0.001), (34, -0.071), (35, -0.022), (36, 0.072), (37, 0.008), (38, -0.02), (39, 0.008), (40, 0.016), (41, 0.022), (42, -0.032), (43, 0.038), (44, -0.004), (45, -0.0), (46, 0.043), (47, -0.0), (48, -0.002), (49, 0.005)]
simIndex simValue paperId paperTitle
same-paper 1 0.93548775 171 cvpr-2013-Fast Trust Region for Segmentation
Author: Lena Gorelick, Frank R. Schmidt, Yuri Boykov
Abstract: Trust region is a well-known general iterative approach to optimization which offers many advantages over standard gradient descent techniques. In particular, it allows more accurate nonlinear approximation models. In each iteration this approach computes a global optimum of a suitable approximation model within a fixed radius around the current solution, a.k.a. trust region. In general, this approach can be used only when some efficient constrained optimization algorithm is available for the selected nonlinear (more accurate) approximation model. In this paper we propose a Fast Trust Region (FTR) approach for optimization of segmentation energies with nonlinear regional terms, which are known to be challenging for existing algorithms. These energies include, but are not limited to, KL divergence and Bhattacharyya distance between the observed and the target appearance distributions, volume constraint on segment size, and shape prior constraint in a form of 퐿2 distance from target shape moments. Our method is 1-2 orders of magnitude faster than the existing state-of-the-art methods while converging to comparable or better solutions.
2 0.80464756 51 cvpr-2013-Auxiliary Cuts for General Classes of Higher Order Functionals
Author: Ismail Ben Ayed, Lena Gorelick, Yuri Boykov
Abstract: Several recent studies demonstrated that higher order (non-linear) functionals can yield outstanding performances in the contexts of segmentation, co-segmentation and tracking. In general, higher order functionals result in difficult problems that are not amenable to standard optimizers, and most of the existing works investigated particular forms of such functionals. In this study, we derive general bounds for a broad class of higher order functionals. By introducing auxiliary variables and invoking the Jensen ’s inequality as well as some convexity arguments, we prove that these bounds are auxiliary functionals for various non-linear terms, which include but are not limited to several affinity measures on the distributions or moments of segment appearance and shape, as well as soft constraints on segment volume. From these general-form bounds, we state various non-linear problems as the optimization of auxiliary functionals by graph cuts. The proposed bound optimizers are derivative-free, and consistently yield very steep functional decreases, thereby converging within a few graph cuts. We report several experiments on color and medical data, along with quantitative comparisons to stateof-the-art methods. The results demonstrate competitive performances of the proposed algorithms in regard to accuracy and convergence speed, and confirm their potential in various vision and medical applications.
3 0.76018178 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.
4 0.75718647 9 cvpr-2013-A Fast Semidefinite Approach to Solving Binary Quadratic Problems
Author: Peng Wang, Chunhua Shen, Anton van_den_Hengel
Abstract: Many computer vision problems can be formulated as binary quadratic programs (BQPs). Two classic relaxation methods are widely used for solving BQPs, namely, spectral methods and semidefinite programming (SDP), each with their own advantages and disadvantages. Spectral relaxation is simple and easy to implement, but its bound is loose. Semidefinite relaxation has a tighter bound, but its computational complexity is high for large scale problems. We present a new SDP formulation for BQPs, with two desirable properties. First, it has a similar relaxation bound to conventional SDP formulations. Second, compared with conventional SDP methods, the new SDP formulation leads to a significantly more efficient and scalable dual optimization approach, which has the same degree of complexity as spectral methods. Extensive experiments on various applications including clustering, image segmentation, co-segmentation and registration demonstrate the usefulness of our SDP formulation for solving large-scale BQPs.
5 0.74301809 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.
7 0.73402166 448 cvpr-2013-Universality of the Local Marginal Polytope
8 0.72167522 23 cvpr-2013-A Practical Rank-Constrained Eight-Point Algorithm for Fundamental Matrix Estimation
9 0.72094059 41 cvpr-2013-An Iterated L1 Algorithm for Non-smooth Non-convex Optimization in Computer Vision
10 0.71179909 6 cvpr-2013-A Comparative Study of Modern Inference Techniques for Discrete Energy Minimization Problems
11 0.6936335 20 cvpr-2013-A New Model and Simple Algorithms for Multi-label Mumford-Shah Problems
12 0.67806596 468 cvpr-2013-Winding Number for Region-Boundary Consistent Salient Contour Extraction
13 0.65721303 262 cvpr-2013-Learning for Structured Prediction Using Approximate Subgradient Descent with Working Sets
14 0.64881295 222 cvpr-2013-Incorporating User Interaction and Topological Constraints within Contour Completion via Discrete Calculus
15 0.63286591 33 cvpr-2013-Active Contours with Group Similarity
16 0.6305666 437 cvpr-2013-Towards Fast and Accurate Segmentation
17 0.61481589 128 cvpr-2013-Discrete MRF Inference of Marginal Densities for Non-uniformly Discretized Variable Space
18 0.59646207 24 cvpr-2013-A Principled Deep Random Field Model for Image Segmentation
19 0.5761112 143 cvpr-2013-Efficient Large-Scale Structured Learning
20 0.5648585 11 cvpr-2013-A Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles
topicId topicWeight
[(10, 0.112), (16, 0.016), (26, 0.067), (33, 0.317), (38, 0.211), (67, 0.047), (69, 0.04), (77, 0.014), (87, 0.074)]
simIndex simValue paperId paperTitle
1 0.93865883 350 cvpr-2013-Reconstructing Loopy Curvilinear Structures Using Integer Programming
Author: Engin Türetken, Fethallah Benmansour, Bjoern Andres, Hanspeter Pfister, Pascal Fua
Abstract: We propose a novel approach to automated delineation of linear structures that form complex and potentially loopy networks. This is in contrast to earlier approaches that usually assume a tree topology for the networks. At the heart of our method is an Integer Programming formulation that allows us to find the global optimum of an objective function designed to allow cycles but penalize spurious junctions and early terminations. We demonstrate that it outperforms state-of-the-art techniques on a wide range of datasets.
2 0.91241974 263 cvpr-2013-Learning the Change for Automatic Image Cropping
Author: Jianzhou Yan, Stephen Lin, Sing Bing Kang, Xiaoou Tang
Abstract: Image cropping is a common operation used to improve the visual quality of photographs. In this paper, we present an automatic cropping technique that accounts for the two primary considerations of people when they crop: removal of distracting content, and enhancement of overall composition. Our approach utilizes a large training set consisting of photos before and after cropping by expert photographers to learn how to evaluate these two factors in a crop. In contrast to the many methods that exist for general assessment of image quality, ours specifically examines differences between the original and cropped photo in solving for the crop parameters. To this end, several novel image features are proposed to model the changes in image content and composition when a crop is applied. Our experiments demonstrate improvements of our method over recent cropping algorithms on a broad range of images.
Author: Alessandro Perina, Nebojsa Jojic
Abstract: Recently, the Counting Grid (CG) model [5] was developed to represent each input image as a point in a large grid of feature counts. This latent point is a corner of a window of grid points which are all uniformly combined to match the (normalized) feature counts in the image. Being a bag of word model with spatial layout in the latent space, the CG model has superior handling of field of view changes in comparison to other bag of word models, but with the price of being essentially a mixture, mapping each scene to a single window in the grid. In this paper we introduce a family of componential models, dubbed the Componential Counting Grid, whose members represent each input image by multiple latent locations, rather than just one. In this way, we make a substantially more flexible admixture model which captures layers or parts of images and maps them to separate windows in a Counting Grid. We tested the models on scene and place classification where their com- ponential nature helped to extract objects, to capture parallax effects, thus better fitting the data and outperforming Counting Grids and Latent Dirichlet Allocation, especially on sequences taken with wearable cameras.
same-paper 4 0.88950163 171 cvpr-2013-Fast Trust Region for Segmentation
Author: Lena Gorelick, Frank R. Schmidt, Yuri Boykov
Abstract: Trust region is a well-known general iterative approach to optimization which offers many advantages over standard gradient descent techniques. In particular, it allows more accurate nonlinear approximation models. In each iteration this approach computes a global optimum of a suitable approximation model within a fixed radius around the current solution, a.k.a. trust region. In general, this approach can be used only when some efficient constrained optimization algorithm is available for the selected nonlinear (more accurate) approximation model. In this paper we propose a Fast Trust Region (FTR) approach for optimization of segmentation energies with nonlinear regional terms, which are known to be challenging for existing algorithms. These energies include, but are not limited to, KL divergence and Bhattacharyya distance between the observed and the target appearance distributions, volume constraint on segment size, and shape prior constraint in a form of 퐿2 distance from target shape moments. Our method is 1-2 orders of magnitude faster than the existing state-of-the-art methods while converging to comparable or better solutions.
5 0.8816731 233 cvpr-2013-Joint Sparsity-Based Representation and Analysis of Unconstrained Activities
Author: Raghuraman Gopalan
Abstract: While the notion of joint sparsity in understanding common and innovative components of a multi-receiver signal ensemble has been well studied, we investigate the utility of such joint sparse models in representing information contained in a single video signal. By decomposing the content of a video sequence into that observed by multiple spatially and/or temporally distributed receivers, we first recover a collection of common and innovative components pertaining to individual videos. We then present modeling strategies based on subspace-driven manifold metrics to characterize patterns among these components, across other videos in the system, to perform subsequent video analysis. We demonstrate the efficacy of our approach for activity classification and clustering by reporting competitive results on standard datasets such as, HMDB, UCF-50, Olympic Sports and KTH.
6 0.87742913 158 cvpr-2013-Exploring Weak Stabilization for Motion Feature Extraction
7 0.85797465 250 cvpr-2013-Learning Cross-Domain Information Transfer for Location Recognition and Clustering
8 0.85356903 242 cvpr-2013-Label Propagation from ImageNet to 3D Point Clouds
9 0.85293078 187 cvpr-2013-Geometric Context from Videos
10 0.85275221 446 cvpr-2013-Understanding Indoor Scenes Using 3D Geometric Phrases
11 0.85267913 96 cvpr-2013-Correlation Filters for Object Alignment
12 0.85267425 43 cvpr-2013-Analyzing Semantic Segmentation Using Hybrid Human-Machine CRFs
13 0.85197681 362 cvpr-2013-Robust Monocular Epipolar Flow Estimation
14 0.85147947 111 cvpr-2013-Dense Reconstruction Using 3D Object Shape Priors
15 0.85133857 121 cvpr-2013-Detection- and Trajectory-Level Exclusion in Multiple Object Tracking
16 0.85109645 212 cvpr-2013-Image Segmentation by Cascaded Region Agglomeration
17 0.85103965 104 cvpr-2013-Deep Convolutional Network Cascade for Facial Point Detection
18 0.85080218 329 cvpr-2013-Perceptual Organization and Recognition of Indoor Scenes from RGB-D Images
19 0.85076296 370 cvpr-2013-SCALPEL: Segmentation Cascades with Localized Priors and Efficient Learning
20 0.85063428 124 cvpr-2013-Determining Motion Directly from Normal Flows Upon the Use of a Spherical Eye Platform