cvpr cvpr2013 cvpr2013-51 knowledge-graph by maker-knowledge-mining
Source: pdf
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.
Reference: text
sentIndex sentText sentNum sentScore
1 ca 1 GE Healthcare London, ON, Canada Abstract Several recent studies demonstrated that higher order (non-linear) functionals can yield outstanding performances in the contexts of segmentation, co-segmentation and tracking. [sent-6, score-0.597]
2 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. [sent-7, score-0.563]
3 In this study, we derive general bounds for a broad class of higher order functionals. [sent-8, score-0.101]
4 From these general-form bounds, we state various non-linear problems as the optimization of auxiliary functionals by graph cuts. [sent-10, score-0.813]
5 The proposed bound optimizers are derivative-free, and consistently yield very steep functional decreases, thereby converging within a few graph cuts. [sent-11, score-0.734]
6 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. [sent-13, score-0.226]
7 , discrete graph cuts [5] or continuous convex-relaxation techniques [6], are restricted to special linear (or unary) forms of regional functionals, where R can be expressed as the sum (or integral in the continuous setting) of individual-pixel penalties [4, 21, 16]. [sent-18, score-0.223]
8 Linear functionals Let Ip = I(p) : Ω ⊂ R2 → Z ⊂ Rn, n ∈ N∗, be an image-feature f)u:n c Ωtion ⊂ de Rfine→d over a d Rom,anin ∈Ω. [sent-21, score-0.492]
9 Linear functionals can be expressed in the following general form [4, 21, 16]: ? [sent-24, score-0.519]
10 Ω is the characteristic function of segment S ⊂ Ω: χS(p) =? [sent-30, score-0.1]
11 Linear functionals are frequently used in vision and medical imaging because they are easily amenable to powerful global optimizers. [sent-33, score-0.612]
12 Several recent research efforts have demonstrated that higher order (non-linear) functionals can enforce much more powerful constraints in various vision [8, 18, 20, 1, 11] and medical-imaging applications [2, 12]. [sent-35, score-0.492]
13 Prior art on non-linear functionals Useful non-linear functionals include but are not limited to several affinity measures on the distributions or moments of segment appearance [8, 20, 1, 11, 18] and shape 1 1 13 3 30 0 024 2 [12, 2], as well as soft constraints on segment volume [8, 24]. [sent-38, score-1.263]
14 For instance, distribution (or histogram) matching formulations, which enforce some consistency between the feature distribution of the target segment and a given model, have recently sparked a significant research effort [8, 11, 20, 1, 18]. [sent-39, score-0.1]
15 In general, non-linear functionals result in difficult optimization problems that are not amenable to standard global optimization techniques. [sent-42, score-0.603]
16 Some notable prior-art studies investigated specialized optimizers for particular forms of non-linear functionals. [sent-43, score-0.187]
17 They cfo tmheb Lined some approximation of the functional with a heuristic linear term to damp the New- ton’s steps. [sent-46, score-0.248]
18 For better initialization, they used a submodular-supermodular procedure [19] that assumes the functional is supermodular, and proved that this holds for the L1-distance. [sent-49, score-0.248]
19 h suggested sto f replace the L1 by the L2Mdisutaknhcerej,e arguing sthugatg ethstee dla ttoter r aplffaocreds t some interesting combinatorial properties, which befit graph cut optimization. [sent-51, score-0.093]
20 Although QPBFs are non-submodular, the ensuing optimization problems allow roof-duality relaxation that can be solved by graph cuts [13]. [sent-54, score-0.191]
21 In [1], the authors built a bound optimizer specific for the Bhattacharyya measure, which yielded very rapid convergences and competitive accuracies/optima. [sent-57, score-0.485]
22 Unfortunately, the bound derivation in [1] relies on very specific properties of the Bhattacharyya coefficient, which precludes its use for any of the other important non-linear functionals. [sent-58, score-0.217]
23 At each iteration, they used graph cuts to optimize some second-order approximation of the functional within adaptively selected step size. [sent-68, score-0.374]
24 Bound optimization and auxiliary functionals Let E(u) be a functional to be optimized over some variable function u. [sent-78, score-1.01]
25 Bound-optimization algorithms proceed by constructing and optimizing upper bounds of E, which serve as auxiliary functionals whose optimization is easier than the original functional: Definition 1. [sent-79, score-0.836]
26 Given an auxiliary variable ui, A(u, ui) is an auxiliary functional of E if it satisfies: E(u) ≤ A(u, ui) E(u) = A(u, u) (4a) (4b) Rather than optimizing directly E, we optimize iteratively a sequence of auxiliary functionals: ui+1 = muin A(u,ui), i = 1,2,. [sent-80, score-0.962]
27 Bound optimizers are derivative- and parameter-free algorithms (They do not require the functional to be differentiable, neither do they use optimizer parameters such as step sizes), and enjoy a strong guarantee: they never worsen the functional. [sent-85, score-0.575]
28 Bound optimization has yielded efficient solutions for difficult problems in Nonnegative Matrix Factorization [15] and computational statistics [14], and is gaining interest in machine learning [25]. [sent-87, score-0.113]
29 For instance, the study [25] demonstrated the power of bound optimization in solving AdaBoost and logistic regression models. [sent-88, score-0.218]
30 The key difficulty in bound optimization is in constructing an appropriate auxiliary functional. [sent-89, score-0.456]
31 On the one hand, the bound should be close enough to the original functional. [sent-90, score-0.186]
32 On the other hand, a good auxiliary functional should be amenable to fast and global solvers. [sent-91, score-0.533]
33 Contributions of this study In this study, we derive general bounds for a broad class of higher order functionals, which can be expressed as nonlinear combinations of linear terms and their ratios. [sent-94, score-0.101]
34 From these general-form bounds, we state various non-linear problems as the optimization of auxiliary functionals by graph cuts. [sent-96, score-0.813]
35 The proposed bound optimizers are derivative-free, and consistently yield very steep functional decreases, thereby converging within a few graph cuts (typically less than 5). [sent-97, score-0.809]
36 We report several experimental evaluations on color and medical data, along with quantitative comparisons of the proposed bound optimizers to the methods in [8, 22]. [sent-98, score-0.4]
37 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. [sent-99, score-0.226]
38 Non-linear functions of linear terms In this section, we focus on functionals E = R + Q, where R is a non-linear term of the following general form: R(S) = ? [sent-101, score-0.519]
39 z∈Z where gz : Ω → R+, z ∈ Z, is a family of non-negative scalar func:ti Ωons → →de Rfine,d z over ,th ies image dyo omfa nino,n -annedg aFtizv : R → R+, z ∈ Z, is a family of non-negative scalar functRion →s. [sent-105, score-0.3]
40 RTh,e following li fasmts some examples voef very ru fsuenfuc-l non-linear regional functionals of the form (6). [sent-106, score-0.54]
41 The Lj-distance between histograms This type of terms enforces an Lj-distance consistency betTwheeisn t tyhpee image histogram osf a tnhe L target segment S and a given model histogram {hz , z ∈ Z}, and is very useful in co-segmentation [o2gr2,a m18, { h23], zan ∈d tracking [ is1 1 v]:e z? [sent-109, score-0.173]
42 p∈S δ(Ip − z) counts the number of segment pixels w? [sent-126, score-0.1]
43 (6) T, wei Lth the following particular functions: gz (p) = δ(Ip − z), z ∈ Z, and Fz(t) = |t − hz |j, j ∈ N∗, z ∈ Z. [sent-130, score-0.298]
44 The volume/area penalty function The volume/area function penalizes a segment S when its size deviates from a given volume/area v1 [8]: ⎝⎛v1−p? [sent-133, score-0.1]
45 )2 (9) The volume penalty can be written in the form of (6), with the following particular functions: gz = 1, z ∈ {1}, and Fz (t) = (vz − t)2, z ∈ {1}. [sent-136, score-0.19]
46 A general auxiliary functional In the following, we will derive a family of general bounds (auxiliary functionals) for non-linear terms of the form in (6) by introducing auxiliary variables and invoking the Jensen’s inequality as well as convexity arguments. [sent-141, score-1.025]
47 If Fz is convex ∀z ∈ Z, and given an auxiliary segment Si, the fiosll ocownivnegx f ∀uznc ∈tio Zna,l a nisd an upper b aouuxnildof the general non-linear form R(S) in (6), ∀α ∈ R+ and for any segment oSn verifying rSm ⊂ R S(Si:) Aα(S,Si) = (1+α)R(Si)−α? [sent-143, score-0.535]
48 applying the Jensen’s inequality to (14) with xp = ? [sent-200, score-0.094]
49 (17) Plugging (17) in the bound in (16), and after some manipulations, we obtain: Fz(? [sent-254, score-0.186]
50 obtain the following bound of the general non-linear functional in (6): R(S) ≤ R(Si) +? [sent-264, score-0.461]
51 (19) Now notice the following inequality ∀α ∈ R+ R(Si) =(1 + α)R(Si) − αR(Si) ≤(1 + α)R(Si) − αR(Si)? [sent-267, score-0.097]
52 If Fz is convex ∀z ∈ Z, Aα (S, Si) + Q(S) is an auxiliary functional oonfv Eex(S ∀)z = ∈ RZ(,S A) + Q(S) for nonlinear terms R(S) of the form in (6), ∀α ∈ R+ and for any segment rSm verifying fS t ⊂e Sfori Proof. [sent-286, score-0.656]
53 To prove that Aα +Q is an auxiliary function of E = R + Q, we need to have two conditions: (i) Aα (S, Si) + Q(S) obeys the bound condition of the form in (4a), i. [sent-287, score-0.471]
54 The bound condition follows directly from the result in proposition 1. [sent-292, score-0.288]
55 Non-linear functions of the ratio of linear terms In this section, we focus on functionals E = J + Q, where J is a non-linear, general-form functional containing the ratio of linear terms: J(S) =? [sent-317, score-0.74]
56 (22) where gz , hz : Ω → R+, z ∈ Z, are two families of nonnegative scala:r Ωfun →ctio Rns d ze f∈ine Zd, over wthoe f image d oofm naoinn,- and Fz : C ⊂ R → R, z ∈ Z, is a family of scalar functions defined over a convex ,d zom ∈a Zin, iCs . [sent-324, score-0.452]
57 They include but are not limited to several affinity measures on the distributions or moments of segment appearance [8, 20, 1] and shape [12, 2]. [sent-326, score-0.179]
58 Following are some examples of functionals of the form (22). [sent-327, score-0.492]
59 Probability product kernels Here we introduce the probability product kernel [10] as a segmentation constraint that can be viewed as a generalization of the Bhattacharyya measure, which has recently led to competitive performances in segmentation [20, 1]: −? [sent-330, score-0.123]
60 istheker- nel density estimate of the distribution of image data within segment S, with kz the Gaussian kernel (σ the width of the kernel): kz(p) =(2πσ12)n2exp−? [sent-341, score-0.129]
61 2 (24) Minimization of (23) aims at finding a segment S whose distribution most closely matches model {Mz , z ∈ Z}. [sent-343, score-0.1]
62 Kullback-Leibler divergence Minimization of this type of constraints enforces a Kullback-Leibler consistency between the distribution of the target segment S and a given model {Mz , z ∈ Z} [17]: ? [sent-348, score-0.165]
63 pper bound in (28) reduces to the general non-linear term of the type in (6). [sent-430, score-0.213]
64 (29) 1 1 13 3 30 0 068 6 The rest of the proof follows the same steps as the proof of proposition 1. [sent-440, score-0.137]
65 The proof follows the same steps as the proof of proposition 2. [sent-443, score-0.137]
66 A general bound-optimization algorithm The results in propositions 2 and 4 instruct us to derive the following general-purpose bound-optimization algorithm for non-linear functionals of the forms E(S) = R(S) + Q(S) with R of the type (6) and E(S) = J(S) + Q(S) with J of the type (22). [sent-446, score-0.543]
67 Algorithm 1 Bound optimization cuts Algorithm 1Bound optimization cuts 1. [sent-447, score-0.214]
68 i= 0: Initialize the auxiliary segment by S0; S0 can be a trivial segment corresponding to the whole image domain, i. [sent-449, score-0.438]
69 b with a graph cut: Auxiliary functionals Aα + Q and Bα + Q are in the form of a sum of unary and pairwise (submodular) terms. [sent-458, score-0.543]
70 Experiments We report several experiments on color and medical data, along with quantitative comparisons to the methods in [8, 22] in regard to convergence speed and accuracy. [sent-466, score-0.159]
71 Each of the functionals is combined with a standard 16-neighborhood boundary smoothness term Q(S) = λ ? [sent-467, score-0.492]
72 e1n depicts a comparison to the recent method in [8], and demonstrates that auxiliary cuts can lead to a competitive performance in regard to convergence speed and ac- × + curacy. [sent-472, score-0.455]
73 We used the same functional (E = R Q, with R the L2-distance between histograms and smoothness weight tλh e=L 10) and initialization for both methods. [sent-473, score-0.248]
74 The plots show the functional and error (number of misclassified pixels) as functions of the iteration number, and the arrows in the plots indicate the convergence points. [sent-476, score-0.323]
75 The bound optimizer yielded a faster decrease of the functional and converged after 4 iterations (it requires only 1graph cut per iteration), whereas the method in [8] performed 10 iterations to reach convergence (and may require more that one graph cut per iteration). [sent-477, score-0.889]
76 Notice that the proposed method yielded a lower error, which indicates that the non-linear term R obtained at convergence is lower. [sent-478, score-0.134]
77 We learned a histogram hV of one VB from the user input, and used 7 hV as model to segment the whole spine i(lnupmutb,a arn spine images contain 7 VBs). [sent-484, score-0.243]
78 The bound optimizer segmented successfully aanlld t 1he0 V×B1)s,. [sent-487, score-0.372]
79 Twhheer beoasu nthde o Boykov-Jolly menotdeedl s (uBc-J) [4] yielded several incorrect segments (We used the same training mask, number of bins and smoothness weight for 1Note that for the case of the L1-distance, the method of Gorelick et al. [sent-488, score-0.167]
80 [8] isN notote athpaptl fiocarb thlee b caecsaeu osef hite er Lequires the functional to be differentiable (in order to compute a first-order approximation). [sent-489, score-0.286]
81 1 1 13 3 30 0 079 7 ConstraintGeneral formAuxiliary functionalFz(t)gz(p)hz(p) corresponding auxiliary functionals. [sent-490, score-0.238]
82 Notice that Fz is convex for all the examples, and is monotonically decreasing for the examples involving form J(S) in (22). [sent-491, score-0.12]
83 L2-distance example: log-scale plots of the functional aFnigdu dreis t1a. [sent-497, score-0.248]
84 nc Le from ground truth (or error) for bound optimization and the method in [8]. [sent-498, score-0.218]
85 The bound optimizer yielded a steeper decrease in the error/functional (the arrows indicate convergence points). [sent-499, score-0.506]
86 Notice that we obtained a lower error, which indicates that the bound optimizer yielded a lower non-linear term R at convergence. [sent-500, score-0.453]
87 Similarly to the previous experiment, the L1-distance bound optimizer yielded a steep xdpeecrriemaseen to,f t hthee L Lfunctional, using only 4 graph cuts. [sent-507, score-0.558]
88 3entaionwith wodifer ntmeth- ods: the L1-distance bound optimizer and the Boykov-Jolly (B-J) modosd:e thl [4]. [sent-525, score-0.372]
89 Evaluation of histogram matching on the GrabCut dataset (50 color images): average error for the bound optimizer (L2distance) a inmda tghees m):e tahvoedra gofe eR eortrohrer oetr ra tl. [sent-532, score-0.397]
90 The results in Table 2 demonstrate that the bound optimizer obtained a significant improvement in accuracy over the method in [22]. [sent-535, score-0.372]
91 Even though each of these examples contains a camouflage (an overlap between the distributions of the foreground/background segments), the bound optimizer obtained accurate image partitions, and consistently converged within less than 5 graph cuts. [sent-538, score-0.463]
92 25GB of RAM, the bound optimizer required between 3 and 6 seconds to process an image. [sent-541, score-0.372]
93 4 confirms the fast convergence and very steep functional 1 1 13 3 3 0101080 8 Inital? [sent-543, score-0.355]
94 c7un3ts obtained with the bound optimizer (L2-distance) using some camouflage examples oinu nthde GprtiambCizuetr d (Lata. [sent-552, score-0.435]
95 The plot depicts the functional versus the number of cuts/iterations. [sent-556, score-0.272]
96 decrease obtained by the proposed optimizers in the case of the KL divergence (we used an example from the GrabCut data). [sent-557, score-0.183]
97 We show the initial/final segments, and plot the functional versus the number of iterations. [sent-558, score-0.248]
98 For this example, the bound optimizer required only two graph cuts. [sent-559, score-0.423]
99 Graph cut segmentation with a global constraint: Recovering region distribution via a bound of the bhattacharyya measure. [sent-567, score-0.372]
100 Interactive graph cuts for optimal boundary and region segmentation of objects in n-d images. [sent-587, score-0.154]
wordName wordTfidf (topN-words)
[('functionals', 0.492), ('fz', 0.439), ('functional', 0.248), ('auxiliary', 0.238), ('si', 0.199), ('gz', 0.19), ('bound', 0.186), ('optimizer', 0.186), ('optimizers', 0.141), ('ggzz', 0.119), ('bhattacharyya', 0.116), ('hz', 0.108), ('segment', 0.1), ('gzi', 0.099), ('ui', 0.088), ('jensen', 0.088), ('yielded', 0.081), ('proposition', 0.077), ('cuts', 0.075), ('bounds', 0.074), ('medical', 0.073), ('inequality', 0.069), ('mz', 0.068), ('gorelick', 0.062), ('spine', 0.059), ('grabcut', 0.055), ('steep', 0.054), ('ben', 0.054), ('nonnegative', 0.053), ('convergence', 0.053), ('azi', 0.053), ('ayed', 0.053), ('graph', 0.051), ('regional', 0.048), ('amenable', 0.047), ('convex', 0.046), ('boykov', 0.044), ('invoking', 0.044), ('moments', 0.044), ('divergence', 0.042), ('cut', 0.042), ('rother', 0.04), ('camouflage', 0.04), ('ginm', 0.04), ('bins', 0.039), ('differentiable', 0.038), ('decreasing', 0.038), ('monotonically', 0.036), ('equality', 0.035), ('performances', 0.035), ('inital', 0.035), ('punithakumar', 0.035), ('cosegmentation', 0.035), ('affinity', 0.035), ('regard', 0.033), ('rsm', 0.033), ('ensuing', 0.033), ('optimization', 0.032), ('ip', 0.032), ('competitive', 0.032), ('convexity', 0.032), ('derivation', 0.031), ('yuri', 0.031), ('pages', 0.03), ('proof', 0.03), ('kz', 0.029), ('notice', 0.028), ('wpq', 0.028), ('mukherjee', 0.028), ('sp', 0.028), ('segmentation', 0.028), ('family', 0.028), ('arguments', 0.027), ('converging', 0.027), ('yield', 0.027), ('scalar', 0.027), ('general', 0.027), ('hv', 0.025), ('histogram', 0.025), ('evolution', 0.025), ('condition', 0.025), ('penalties', 0.025), ('xp', 0.025), ('vb', 0.024), ('kl', 0.024), ('segments', 0.024), ('forms', 0.024), ('verifying', 0.024), ('depicts', 0.024), ('kolmogorov', 0.024), ('enforces', 0.023), ('nthde', 0.023), ('studies', 0.022), ('schmidt', 0.022), ('misclassified', 0.022), ('prove', 0.022), ('canada', 0.022), ('bk', 0.022), ('surrogate', 0.021), ('outstanding', 0.021)]
simIndex simValue paperId paperTitle
same-paper 1 1.0 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.
2 0.16858655 381 cvpr-2013-Scene Parsing by Integrating Function, Geometry and Appearance Models
Author: Yibiao Zhao, Song-Chun Zhu
Abstract: Indoor functional objects exhibit large view and appearance variations, thus are difficult to be recognized by the traditional appearance-based classification paradigm. In this paper, we present an algorithm to parse indoor images based on two observations: i) The functionality is the most essentialproperty to define an indoor object, e.g. “a chair to sit on ”; ii) The geometry (3D shape) ofan object is designed to serve its function. We formulate the nature of the object function into a stochastic grammar model. This model characterizes a joint distribution over the function-geometryappearance (FGA) hierarchy. The hierarchical structure includes a scene category, , functional groups, , functional objects, functional parts and 3D geometric shapes. We use a simulated annealing MCMC algorithm to find the maximum a posteriori (MAP) solution, i.e. a parse tree. We design four data-driven steps to accelerate the search in the FGA space: i) group the line segments into 3D primitive shapes, ii) assign functional labels to these 3D primitive shapes, iii) fill in missing objects/parts according to the functional labels, and iv) synthesize 2D segmentation maps and verify the current parse tree by the Metropolis-Hastings acceptance probability. The experimental results on several challenging indoor datasets demonstrate theproposed approach not only significantly widens the scope ofindoor sceneparsing algorithm from the segmentation and the 3D recovery to the functional object recognition, but also yields improved overall performance.
3 0.093826987 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.
4 0.090001531 20 cvpr-2013-A New Model and Simple Algorithms for Multi-label Mumford-Shah Problems
Author: Byung-Woo Hong, Zhaojin Lu, Ganesh Sundaramoorthi
Abstract: In this work, we address the multi-label Mumford-Shah problem, i.e., the problem of jointly estimating a partitioning of the domain of the image, and functions defined within regions of the partition. We create algorithms that are efficient, robust to undesirable local minima, and are easy-toimplement. Our algorithms are formulated by slightly modifying the underlying statistical model from which the multilabel Mumford-Shah functional is derived. The advantage of this statistical model is that the underlying variables: the labels and thefunctions are less coupled than in the original formulation, and the labels can be computed from the functions with more global updates. The resulting algorithms can be tuned to the desired level of locality of the solution: from fully global updates to more local updates. We demonstrate our algorithm on two applications: joint multi-label segmentation and denoising, and joint multi-label motion segmentation and flow estimation. We compare to the stateof-the-art in multi-label Mumford-Shah problems and show that we achieve more promising results.
5 0.06803795 21 cvpr-2013-A New Perspective on Uncalibrated Photometric Stereo
Author: Thoma Papadhimitri, Paolo Favaro
Abstract: We investigate the problem of reconstructing normals, albedo and lights of Lambertian surfaces in uncalibrated photometric stereo under the perspective projection model. Our analysis is based on establishing the integrability constraint. In the orthographicprojection case, it is well-known that when such constraint is imposed, a solution can be identified only up to 3 parameters, the so-called generalized bas-relief (GBR) ambiguity. We show that in the perspective projection case the solution is unique. We also propose a closed-form solution which is simple, efficient and robust. We test our algorithm on synthetic data and publicly available real data. Our quantitative tests show that our method outperforms all prior work of uncalibrated photometric stereo under orthographic projection.
6 0.06730102 285 cvpr-2013-Minimum Uncertainty Gap for Robust Visual Tracking
7 0.066836961 24 cvpr-2013-A Principled Deep Random Field Model for Image Segmentation
9 0.052124087 164 cvpr-2013-Fast Convolutional Sparse Coding
10 0.051345982 193 cvpr-2013-Graph Transduction Learning with Connectivity Constraints with Application to Multiple Foreground Cosegmentation
11 0.050583664 41 cvpr-2013-An Iterated L1 Algorithm for Non-smooth Non-convex Optimization in Computer Vision
12 0.049798064 450 cvpr-2013-Unsupervised Joint Object Discovery and Segmentation in Internet Images
13 0.048418082 70 cvpr-2013-Bottom-Up Segmentation for Top-Down Detection
14 0.047973983 6 cvpr-2013-A Comparative Study of Modern Inference Techniques for Discrete Energy Minimization Problems
15 0.047823943 121 cvpr-2013-Detection- and Trajectory-Level Exclusion in Multiple Object Tracking
16 0.047434963 133 cvpr-2013-Discriminative Segment Annotation in Weakly Labeled Video
17 0.046906874 227 cvpr-2013-Intrinsic Scene Properties from a Single RGB-D Image
18 0.046469279 199 cvpr-2013-Harry Potter's Marauder's Map: Localizing and Tracking Multiple Persons-of-Interest by Nonnegative Discretization
19 0.045187831 86 cvpr-2013-Composite Statistical Inference for Semantic Segmentation
20 0.044322092 317 cvpr-2013-Optimal Geometric Fitting under the Truncated L2-Norm
topicId topicWeight
[(0, 0.115), (1, 0.028), (2, 0.009), (3, 0.018), (4, 0.039), (5, -0.002), (6, 0.018), (7, -0.006), (8, -0.047), (9, 0.02), (10, 0.051), (11, -0.017), (12, -0.056), (13, -0.02), (14, -0.046), (15, 0.01), (16, 0.009), (17, 0.005), (18, 0.06), (19, 0.029), (20, -0.057), (21, 0.021), (22, 0.001), (23, -0.016), (24, 0.092), (25, 0.006), (26, -0.016), (27, -0.005), (28, 0.025), (29, -0.031), (30, 0.046), (31, 0.016), (32, 0.009), (33, -0.0), (34, -0.044), (35, -0.023), (36, 0.025), (37, 0.053), (38, -0.019), (39, -0.049), (40, -0.022), (41, 0.012), (42, 0.019), (43, -0.037), (44, -0.014), (45, -0.022), (46, 0.013), (47, -0.001), (48, 0.007), (49, 0.024)]
simIndex simValue paperId paperTitle
same-paper 1 0.93563098 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.
2 0.79580837 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.
3 0.78484023 20 cvpr-2013-A New Model and Simple Algorithms for Multi-label Mumford-Shah Problems
Author: Byung-Woo Hong, Zhaojin Lu, Ganesh Sundaramoorthi
Abstract: In this work, we address the multi-label Mumford-Shah problem, i.e., the problem of jointly estimating a partitioning of the domain of the image, and functions defined within regions of the partition. We create algorithms that are efficient, robust to undesirable local minima, and are easy-toimplement. Our algorithms are formulated by slightly modifying the underlying statistical model from which the multilabel Mumford-Shah functional is derived. The advantage of this statistical model is that the underlying variables: the labels and thefunctions are less coupled than in the original formulation, and the labels can be computed from the functions with more global updates. The resulting algorithms can be tuned to the desired level of locality of the solution: from fully global updates to more local updates. We demonstrate our algorithm on two applications: joint multi-label segmentation and denoising, and joint multi-label motion segmentation and flow estimation. We compare to the stateof-the-art in multi-label Mumford-Shah problems and show that we achieve more promising results.
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.76420981 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.
6 0.75766808 95 cvpr-2013-Continuous Inference in Graphical Models with Polynomial Energies
7 0.75204098 448 cvpr-2013-Universality of the Local Marginal Polytope
8 0.73468101 308 cvpr-2013-Nonlinearly Constrained MRFs: Exploring the Intrinsic Dimensions of Higher-Order Cliques
9 0.72684389 6 cvpr-2013-A Comparative Study of Modern Inference Techniques for Discrete Energy Minimization Problems
10 0.7085278 128 cvpr-2013-Discrete MRF Inference of Marginal Densities for Non-uniformly Discretized Variable Space
11 0.69933778 23 cvpr-2013-A Practical Rank-Constrained Eight-Point Algorithm for Fundamental Matrix Estimation
12 0.68194807 41 cvpr-2013-An Iterated L1 Algorithm for Non-smooth Non-convex Optimization in Computer Vision
13 0.67007452 262 cvpr-2013-Learning for Structured Prediction Using Approximate Subgradient Descent with Working Sets
14 0.64122802 24 cvpr-2013-A Principled Deep Random Field Model for Image Segmentation
15 0.63043171 317 cvpr-2013-Optimal Geometric Fitting under the Truncated L2-Norm
16 0.60527343 429 cvpr-2013-The Generalized Laplacian Distance and Its Applications for Visual Matching
17 0.57587546 184 cvpr-2013-Gauging Association Patterns of Chromosome Territories via Chromatic Median
18 0.56702095 33 cvpr-2013-Active Contours with Group Similarity
19 0.56595683 31 cvpr-2013-Accurate and Robust Registration of Nonrigid Surface Using Hierarchical Statistical Shape Model
20 0.55512309 468 cvpr-2013-Winding Number for Region-Boundary Consistent Salient Contour Extraction
topicId topicWeight
[(10, 0.143), (16, 0.021), (26, 0.043), (33, 0.231), (57, 0.011), (67, 0.048), (69, 0.049), (84, 0.267), (87, 0.074), (96, 0.011)]
simIndex simValue paperId paperTitle
same-paper 1 0.80733162 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.
2 0.76783669 15 cvpr-2013-A Lazy Man's Approach to Benchmarking: Semisupervised Classifier Evaluation and Recalibration
Author: Peter Welinder, Max Welling, Pietro Perona
Abstract: How many labeled examples are needed to estimate a classifier’s performance on a new dataset? We study the case where data is plentiful, but labels are expensive. We show that by making a few reasonable assumptions on the structure of the data, it is possible to estimate performance curves, with confidence bounds, using a small number of ground truth labels. Our approach, which we call Semisupervised Performance Evaluation (SPE), is based on a generative model for the classifier’s confidence scores. In addition to estimating the performance of classifiers on new datasets, SPE can be used to recalibrate a classifier by reestimating the class-conditional confidence distributions.
3 0.74355745 247 cvpr-2013-Learning Class-to-Image Distance with Object Matchings
Author: Guang-Tong Zhou, Tian Lan, Weilong Yang, Greg Mori
Abstract: We conduct image classification by learning a class-toimage distance function that matches objects. The set of objects in training images for an image class are treated as a collage. When presented with a test image, the best matching between this collage of training image objects and those in the test image is found. We validate the efficacy of the proposed model on the PASCAL 07 and SUN 09 datasets, showing that our model is effective for object classification and scene classification tasks. State-of-the-art image classification results are obtained, and qualitative results demonstrate that objects can be accurately matched.
4 0.73132426 248 cvpr-2013-Learning Collections of Part Models for Object Recognition
Author: Ian Endres, Kevin J. Shih, Johnston Jiaa, Derek Hoiem
Abstract: We propose a method to learn a diverse collection of discriminative parts from object bounding box annotations. Part detectors can be trained and applied individually, which simplifies learning and extension to new features or categories. We apply the parts to object category detection, pooling part detections within bottom-up proposed regions and using a boosted classifier with proposed sigmoid weak learners for scoring. On PASCAL VOC 2010, we evaluate the part detectors ’ ability to discriminate and localize annotated keypoints. Our detection system is competitive with the best-existing systems, outperforming other HOG-based detectors on the more deformable categories.
5 0.72813392 414 cvpr-2013-Structure Preserving Object Tracking
Author: Lu Zhang, Laurens van_der_Maaten
Abstract: Model-free trackers can track arbitrary objects based on a single (bounding-box) annotation of the object. Whilst the performance of model-free trackers has recently improved significantly, simultaneously tracking multiple objects with similar appearance remains very hard. In this paper, we propose a new multi-object model-free tracker (based on tracking-by-detection) that resolves this problem by incorporating spatial constraints between the objects. The spatial constraints are learned along with the object detectors using an online structured SVM algorithm. The experimental evaluation ofour structure-preserving object tracker (SPOT) reveals significant performance improvements in multi-object tracking. We also show that SPOT can improve the performance of single-object trackers by simultaneously tracking different parts of the object.
6 0.72664511 285 cvpr-2013-Minimum Uncertainty Gap for Robust Visual Tracking
7 0.72444057 408 cvpr-2013-Spatiotemporal Deformable Part Models for Action Detection
8 0.7240181 365 cvpr-2013-Robust Real-Time Tracking of Multiple Objects by Volumetric Mass Densities
9 0.72345966 325 cvpr-2013-Part Discovery from Partial Correspondence
10 0.72303194 225 cvpr-2013-Integrating Grammar and Segmentation for Human Pose Estimation
11 0.72288615 314 cvpr-2013-Online Object Tracking: A Benchmark
12 0.72255582 400 cvpr-2013-Single Image Calibration of Multi-axial Imaging Systems
13 0.72186321 324 cvpr-2013-Part-Based Visual Tracking with Online Latent Structural Learning
14 0.72150677 98 cvpr-2013-Cross-View Action Recognition via a Continuous Virtual Path
15 0.72107661 143 cvpr-2013-Efficient Large-Scale Structured Learning
16 0.72096378 445 cvpr-2013-Understanding Bayesian Rooms Using Composite 3D Object Models
17 0.72090167 360 cvpr-2013-Robust Estimation of Nonrigid Transformation for Point Set Registration
18 0.72057211 331 cvpr-2013-Physically Plausible 3D Scene Tracking: The Single Actor Hypothesis
19 0.72049361 267 cvpr-2013-Least Soft-Threshold Squares Tracking
20 0.72008109 227 cvpr-2013-Intrinsic Scene Properties from a Single RGB-D Image