cvpr cvpr2013 cvpr2013-9 knowledge-graph by maker-knowledge-mining
Source: pdf
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.
Reference: text
sentIndex sentText sentNum sentScore
1 A Fast Semidefinite Approach to Solving Binary Quadratic Problems Peng Wang, Chunhua Shen, Anton van den Hengel School of Computer Science, The University of Adelaide, Australia Abstract Many computer vision problems can be formulated as binary quadratic programs (BQPs). [sent-1, score-0.117]
2 Two classic relaxation methods are widely used for solving BQPs, namely, spectral methods and semidefinite programming (SDP), each with their own advantages and disadvantages. [sent-2, score-0.357]
3 Spectral relaxation is simple and easy to implement, but its bound is loose. [sent-3, score-0.114]
4 Semidefinite relaxation has a tighter bound, but its computational complexity is high for large scale problems. [sent-4, score-0.118]
5 First, it has a similar relaxation bound to conventional SDP formulations. [sent-6, score-0.151]
6 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. [sent-7, score-0.36]
7 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. [sent-8, score-0.11]
8 Introduction × Many problems in computer vision can be formulated as binary quadratic problems, such as image segmentation, image restoration, graph-matching and problems formulated by Markov Random Fields (MRFs). [sent-10, score-0.166]
9 Because general BQPs are NP-hard, they are commonly approximated by spectral or semidefinite relaxation. [sent-11, score-0.268]
10 Due to their simplicity, spectral methods have been applied to a variety of problems in computer vision, such as image segmentation [20, 25], motion segmentation [13] and many other MRF applications [2]. [sent-13, score-0.207]
11 However, the bound of spectral relaxation is loose and can lead to poor solution quality in many cases [5, 12, 9]. [sent-14, score-0.32]
12 Furthermore, the spectral formulation is hard to generalize to accommodate inequality constraints [2]. [sent-15, score-0.267]
13 In contrast, SDP methods produce tighter approximations than spectral methods, which have been applied to problems including image segmentation [6], restoration [10, 17], subgraph matching [18], co-segmentaion [7] and general MRFs [23]. [sent-16, score-0.242]
14 The worst-case complexity of solving a generic SDP problem involving a matrix variable of size n n and O(n) linear icnovnosltvrianingts a i sm aabtroixut vOa(rinab6. [sent-18, score-0.073]
15 Our approach achieves higher quality solutions than spectral methods while being significantly faster than the conventional SDP formulation. [sent-21, score-0.263]
16 (i) A new SDP formulation (SDCut) is proposed to solve binary quadratic problems. [sent-23, score-0.121]
17 By virtue of its use of the dual formulation, our approach is simplified and can be solved efficiently by first order optimization methods, e. [sent-24, score-0.154]
18 SDCut has the same level of computational complexity as spectral methods, roughly O(n3), wtathioicnha ils ommupchle lxoitwyer a sth sapne tchtrea lco mnevtehnotidosn,a rlo SuDghPl yfo Orm(nulation using interior-point method. [sent-27, score-0.172]
19 SDCut also achieves a similar bound with the conventional SDP formulation and therefore produces better estimates than spectral relaxation. [sent-28, score-0.272]
20 The SDCut formulation allows additional equality or inequality constraints, which enable it to have a broader application area than the spectral method. [sent-30, score-0.266]
21 [19], which presented a fast dual SDP approach to Mahalanobis metric learning. [sent-32, score-0.122]
22 The Frobenius-norm regularization in their objective function plays an important role, which leads to a simplified dual formulation. [sent-33, score-0.191]
23 The results show that our method achieves a better solution quality and a faster running speed. [sent-43, score-0.112]
24 [17] proposed fast SDP methods based on spectral subgradients and trust region methods. [sent-45, score-0.128]
25 Spectral and Semidefinite Relaxation As a simple example of a binary quadratic problem, we consider the following optimization problem: mxinx? [sent-106, score-0.068]
26 One of the spectral methods (again by way of example) relaxes the constraint x ∈ {−1, 1}n to ? [sent-111, score-0.157]
27 Although appealingly simple to implement, Oth(en spectral relaxation often yields poor solution quality. [sent-120, score-0.243]
28 There is no guarantee on the bound of its solution with respect to the optimum of (3). [sent-121, score-0.087]
29 The poor bound of spectral relaxation has been verified by a variety of au- thors [5, 12, 9]. [sent-122, score-0.264]
30 Furthermore, it is difficult to generalize the spectral method to BQPs with linear or quadratic inequality constraints. [sent-123, score-0.228]
31 Although linear equality constraints can be considered [3], solving (4) under additional inequality constraints is in general NP-hard [2]. [sent-124, score-0.182]
32 The SDP relaxation is tighter than spectral relaxation (4). [sent-140, score-0.286]
33 In particular, it has been proved in [4] that the expected values of solutions are bounded for the SDP formulation of some BQPs (e. [sent-141, score-0.072]
34 Another advantage of the SDP formulation is the ability of solving problems of more general forms, e. [sent-144, score-0.113]
35 Quadratic constraints on x are transformed to linear constraints on X = xx? [sent-147, score-0.068]
36 In summary, the constraints for SDP can be either equality or inequality. [sent-149, score-0.067]
37 constraint on trace(X) is common in the SDP formulation for BQPs. [sent-231, score-0.082]
38 d T Ttoh eth neo convex inequality lco cnosntsrtairnatin ? [sent-244, score-0.076]
39 When σ approaches 0, the bound of (11) is arbitrarily close to the bound of (9). [sent-282, score-0.108]
40 Next, we show that the dual of (11) has a much simpler form. [sent-284, score-0.122]
41 The dual problem of (11) can be simplified to muax s. [sent-286, score-0.154]
42 ; Since the primal problem (11) is convex, and both the primal and dual problems are feasible, strong duality holds. [sent-328, score-0.273]
43 in the Lagrangian (13), we obtain the dual problem: mua,Zx −41σ? [sent-346, score-0.122]
44 As the dual (15) is still a SDP problem, it seems that no efficient method can be used to solve (15) directly, other than the interior-point algorithms. [sent-356, score-0.122]
45 Given a fixed u, the dual (15) can be simplified to: mZin ? [sent-361, score-0.154]
46 By substituting Z to (15), the dual problem is simplified to (12). [sent-368, score-0.172]
47 We can see that the simplified dual problem (12) is not a SDP problem. [sent-369, score-0.154]
48 problem size of the dual is much smaller than that of the primal. [sent-375, score-0.122]
49 Because we need to calculate the value and gradient of the dual objective function at each gradient-descent step, a partial eigen-decomposition should be performed to compute C(u) −at each iteration; this is the most computationally expensive part. [sent-395, score-0.178]
50 After solving the dual using L-BFGS-B, the optimal primal X? [sent-412, score-0.211]
51 should be discretized to the feasible binary solution x? [sent-416, score-0.072]
52 Step 1: Solve the dual problem (12) using L-BFGS-B, based on the application-specific A, B, b and the σ chosen by the user. [sent-420, score-0.122]
53 Spectral methods also need the computation of the eigenvectors of the same matrix A, which means they have the same order of complexity with SDCut. [sent-431, score-0.073]
54 5), our method is much faster than the conventional SOD(Pn method. [sent-433, score-0.093]
55 Because SDCut can handle different types of constraints (equality/inequality, linear/quadratic), it can be applied to more problems than spectral methods. [sent-439, score-0.193]
56 Formulation Graph bisection is a problem of separating the vertices of a weighted graph into two disjoint sets with equal cardinality, and minimize the total weights of cut edges. [sent-445, score-0.112]
57 T{−hi1s process is repeated several times and the final solution is the one with the highest objective value. [sent-483, score-0.07]
58 Experiments To show the new SDP formulation has better solution quality than spectral relaxation, we compare the bisection results of RatioCut, NCut and SDCut on two artificial 2-dimensional data. [sent-484, score-0.296]
59 The similarity matrix W is calculated based on the Euclidean distance of points i 1 1 13 3 3 1 1 135 3 odbun−1 34260 10 Iteraion1σ 02 = 51 e - 0 2143 0 Figure 2: The convergence of the objective value of the dual (12), which can be seen as a lower bound. [sent-487, score-0.201]
60 SDCut is tested to bisect a random graph with 200 vertices and 0. [sent-488, score-0.075]
61 8520 Number of vertices Number of vertices Figure 3: Computation time for graph bisection. [sent-492, score-0.122]
62 SDCut is much more faster than the conventional SDP methods, and is faster when the graph is sparse. [sent-497, score-0.177]
63 RatioCut and NCut fail to offer satisfactory results on both of the data sets, possibly due to the loose bound of spectral relaxation. [sent-533, score-0.182]
64 The graph has 200 vertices and its edge density is 0. [sent-536, score-0.075]
65 2, we show the convergence of the objective value of the dual (12), i. [sent-539, score-0.159]
66 a lower bound of the objective value of the problem (6). [sent-541, score-0.091]
67 The optimal objective value of the conventional SDP method is −21. [sent-543, score-0.074]
68 e3 objective yv callousee, the Frobenius norm and the rank of solution X? [sent-550, score-0.093]
69 With the decrease of σ, the quality of the solution X is further optimized (the objective value is smaller and the rank is lower). [sent-552, score-0.116]
70 Our method is faster than SeDuMi and SDPT3 on all graph sizes. [sent-558, score-0.084]
71 Our method runs faster for smaller edge densities, which validates that our method can take the advantage of graph sparsity. [sent-567, score-0.105]
72 Application 2: Image Segmentation Formulation In graph based segmentation, images are represented by weighted graphs G(V, E), with vertices corresponding to pixels and edges encoding feature similarities between pixel pairs. [sent-571, score-0.075]
73 Prior knowledge is encoded as a quadratic constraint on x. [sent-580, score-0.077]
74 One disadvantage of BNCut is that at most one quadratic constraint can be incorporated into its formulation. [sent-582, score-0.077]
75 Unlike BNCut, SDCut can incorporate multiple quadratic constraints on x. [sent-585, score-0.082]
76 In our method, the partial group constraints of x are formulated as: (t? [sent-586, score-0.071]
77 r, (26) where fi and fj are color histograms of superpixels i,j,and d(i, j) is the spatial distance between superpixels i,j. [sent-652, score-0.08]
78 We can see that BNCut is much faster than SDP based methods, but with higher (worse) objective values. [sent-662, score-0.093]
79 SDCut achieves the similar objective value with SeDuMi and SDPT3, and is over 10 times faster than them. [sent-663, score-0.093]
80 The formulation of discriminative clustering for cosegmentation can be expressed as: x∈{m−1in,1}n? [sent-672, score-0.072]
81 SDCut achieves faster speeds and better solution quality than LowRank, on all the four datasets. [sent-690, score-0.112]
82 Standard toolboxes like SeDuMi and SDPT3 cannot handle such large-size problems on a standard desktop. [sent-728, score-0.084]
83 Application 4: Image Registration Formulation In image registration, K source points must be matched to L target points, where K < L. [sent-748, score-0.073]
84 c hh pair of source-target points; Hij,kl = exp(−(dij −dkl)2/σ2) encodes the structural consistency eoxfp source points i,j and target points k, l. [sent-766, score-0.091]
85 The SDP formulations are obtained by introducing into (6) and (11) the matrix Hˆ and the constraints (30a) to (30d). [sent-780, score-0.077]
86 For 2d (top row) and 3d (middle row) artificial data, 15 source points are matched to a subset of 30 target points. [sent-849, score-0.095]
87 For bunny data (bottom row), there are 50 source points and 50 target points. [sent-850, score-0.11]
88 Experiments We apply our registration formulation on some toy data and real-world data. [sent-859, score-0.104]
89 For toy data, we firstly generate 30 target points from a uniform distribution, and randomly select 15 source points. [sent-860, score-0.096]
90 6, we can see that the source and target points are matched correctly. [sent-865, score-0.073]
91 For the toy data, our method runs over 170 times and 50 times faster than SeDuMi and SDPT3 respectively. [sent-866, score-0.1]
92 The reason is that the SDP formulation for registration has much more constraints, which slows down SeDuMi and SDPT3 but has much less impact on SDCut. [sent-869, score-0.081]
93 Conclusion In this paper, we have presented an efficient semidefinite formulation (SDCut) for BQPs. [sent-870, score-0.193]
94 SDCut produces a similar lower bound with the conventional SDP formulation, and therefore is tighter than spectral relaxation. [sent-871, score-0.257]
95 Our formulation is easy to implement by using the L-BFGSB toolbox and standard eigen-decomposition software, and therefore is much more scalable than the conventional SDP formulation. [sent-872, score-0.113]
96 Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. [sent-906, score-0.171]
97 Low-rank optimization on the cone of positive semidefinite matrices. [sent-943, score-0.14]
98 Binary partitioning, perceptual grouping and restoration with semidefinite programming. [sent-958, score-0.161]
99 Improved semidefinite bounding procedure for solving max-cut problems to optimality. [sent-965, score-0.2]
100 Solving large scale binary quadratic problems: Spectral methods vs. [sent-1026, score-0.068]
wordName wordTfidf (topN-words)
[('sdcut', 0.67), ('sdp', 0.498), ('sedumi', 0.196), ('semidefinite', 0.14), ('bncut', 0.134), ('bqps', 0.134), ('spectral', 0.128), ('dual', 0.122), ('lowrank', 0.118), ('ratiocut', 0.104), ('ncut', 0.086), ('xx', 0.063), ('relaxation', 0.06), ('primal', 0.06), ('faster', 0.056), ('bound', 0.054), ('bqp', 0.053), ('toolboxes', 0.053), ('formulation', 0.053), ('diag', 0.053), ('inequality', 0.052), ('quadratic', 0.048), ('vertices', 0.047), ('tb', 0.045), ('arpack', 0.045), ('maxcut', 0.045), ('trace', 0.044), ('xr', 0.043), ('tf', 0.042), ('superpixels', 0.04), ('schellewald', 0.04), ('tighter', 0.038), ('conventional', 0.037), ('bisection', 0.037), ('bunny', 0.037), ('objective', 0.037), ('constraints', 0.034), ('solution', 0.033), ('equality', 0.033), ('simplified', 0.032), ('problems', 0.031), ('xm', 0.03), ('ene', 0.03), ('keuchel', 0.03), ('krislock', 0.03), ('mxinx', 0.03), ('spectrahedron', 0.03), ('xdm', 0.03), ('constraint', 0.029), ('source', 0.029), ('solving', 0.029), ('eigenvectors', 0.029), ('graph', 0.028), ('registration', 0.028), ('target', 0.026), ('ipip', 0.026), ('bi', 0.026), ('ect', 0.025), ('uj', 0.025), ('vlfeat', 0.025), ('lco', 0.024), ('spherical', 0.024), ('segmentation', 0.024), ('lx', 0.024), ('xij', 0.024), ('matrix', 0.024), ('rank', 0.023), ('olsson', 0.023), ('toolbox', 0.023), ('quality', 0.023), ('toy', 0.023), ('poor', 0.022), ('artificial', 0.022), ('matlab', 0.021), ('affinity', 0.021), ('restoration', 0.021), ('runs', 0.021), ('obj', 0.02), ('pso', 0.02), ('eigenvalue', 0.02), ('complexity', 0.02), ('binary', 0.02), ('bp', 0.02), ('nx', 0.02), ('oxf', 0.02), ('eigendecomposition', 0.02), ('formulations', 0.019), ('solutions', 0.019), ('factorization', 0.019), ('fp', 0.019), ('rounding', 0.019), ('shen', 0.019), ('partial', 0.019), ('feasible', 0.019), ('ax', 0.019), ('letter', 0.019), ('clustering', 0.019), ('formulated', 0.018), ('substituting', 0.018), ('points', 0.018)]
simIndex simValue paperId paperTitle
same-paper 1 0.9999997 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.
2 0.096484579 23 cvpr-2013-A Practical Rank-Constrained Eight-Point Algorithm for Fundamental Matrix Estimation
Author: Yinqiang Zheng, Shigeki Sugimoto, Masatoshi Okutomi
Abstract: Due to its simplicity, the eight-point algorithm has been widely used in fundamental matrix estimation. Unfortunately, the rank-2 constraint of a fundamental matrix is enforced via a posterior rank correction step, thus leading to non-optimal solutions to the original problem. To address this drawback, existing algorithms need to solve either a very high order polynomial or a sequence of convex relaxation problems, both of which are computationally ineffective and numerically unstable. In this work, we present a new rank-2 constrained eight-point algorithm, which directly incorporates the rank-2 constraint in the minimization process. To avoid singularities, we propose to solve seven subproblems and retrieve their globally optimal solutions by using tailored polynomial system solvers. Our proposed method is noniterative, computationally efficient and numerically stable. Experiment results have verified its superiority over existing algebraic error based algorithms in terms of accuracy, as well as its advantages when used to initialize geometric error based algorithms.
3 0.077589117 184 cvpr-2013-Gauging Association Patterns of Chromosome Territories via Chromatic Median
Author: Hu Ding, Branislav Stojkovic, Ronald Berezney, Jinhui Xu
Abstract: Computing accurate and robust organizational patterns of chromosome territories inside the cell nucleus is critical for understanding several fundamental genomic processes, such as co-regulation of gene activation, gene silencing, X chromosome inactivation, and abnormal chromosome rearrangement in cancer cells. The usage of advanced fluorescence labeling and image processing techniques has enabled researchers to investigate interactions of chromosome territories at large spatial resolution. The resulting high volume of generated data demands for high-throughput and automated image analysis methods. In this paper, we introduce a novel algorithmic tool for investigating association patterns of chromosome territories in a population of cells. Our method takes as input a set of graphs, one for each cell, containing information about spatial interaction of chromosome territories, and yields a single graph that contains essential information for the whole population and stands as its structural representative. We formulate this combinato- rial problem as a semi-definite programming and present novel techniques to efficiently solve it. We validate our approach on both artificial and real biological data; the experimental results suggest that our approach yields a nearoptimal solution, and can handle large-size datasets, which are significant improvements over existing techniques.
4 0.076430842 93 cvpr-2013-Constraints as Features
Author: Shmuel Asafi, Daniel Cohen-Or
Abstract: In this paper, we introduce a new approach to constrained clustering which treats the constraints as features. Our method augments the original feature space with additional dimensions, each of which derived from a given Cannot-link constraints. The specified Cannot-link pair gets extreme coordinates values, and the rest of the points get coordinate values that express their spatial influence from the specified constrained pair. After augmenting all the new features, a standard unconstrained clustering algorithm can be performed, like k-means or spectral clustering. We demonstrate the efficacy of our method for active semi-supervised learning applied to image segmentation and compare it to alternative methods. We also evaluate the performance of our method on the four most commonly evaluated datasets from the UCI machine learning repository.
5 0.066892058 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.
6 0.062574401 95 cvpr-2013-Continuous Inference in Graphical Models with Polynomial Energies
7 0.061735742 460 cvpr-2013-Weakly-Supervised Dual Clustering for Image Semantic Segmentation
8 0.055910368 379 cvpr-2013-Scalable Sparse Subspace Clustering
9 0.055743359 237 cvpr-2013-Kernel Learning for Extrinsic Classification of Manifold Features
10 0.05354917 437 cvpr-2013-Towards Fast and Accurate Segmentation
11 0.053415038 164 cvpr-2013-Fast Convolutional Sparse Coding
12 0.052087482 300 cvpr-2013-Multi-target Tracking by Lagrangian Relaxation to Min-cost Network Flow
13 0.051151909 109 cvpr-2013-Dense Non-rigid Point-Matching Using Random Projections
14 0.050333433 113 cvpr-2013-Dense Variational Reconstruction of Non-rigid Surfaces from Monocular Video
15 0.050101988 143 cvpr-2013-Efficient Large-Scale Structured Learning
16 0.043773644 282 cvpr-2013-Measuring Crowd Collectiveness
17 0.041139685 317 cvpr-2013-Optimal Geometric Fitting under the Truncated L2-Norm
18 0.040813167 234 cvpr-2013-Joint Spectral Correspondence for Disparate Image Matching
19 0.040716879 6 cvpr-2013-A Comparative Study of Modern Inference Techniques for Discrete Energy Minimization Problems
topicId topicWeight
[(0, 0.098), (1, 0.02), (2, -0.01), (3, 0.032), (4, 0.043), (5, -0.005), (6, 0.005), (7, -0.051), (8, -0.05), (9, -0.003), (10, 0.042), (11, 0.001), (12, -0.051), (13, -0.022), (14, -0.03), (15, -0.019), (16, -0.021), (17, -0.029), (18, 0.028), (19, 0.016), (20, -0.015), (21, 0.012), (22, -0.042), (23, -0.015), (24, 0.072), (25, 0.019), (26, -0.036), (27, -0.0), (28, 0.025), (29, -0.015), (30, 0.072), (31, 0.026), (32, 0.044), (33, -0.053), (34, -0.041), (35, 0.029), (36, 0.002), (37, 0.035), (38, 0.002), (39, -0.016), (40, -0.022), (41, 0.023), (42, -0.038), (43, 0.026), (44, 0.015), (45, -0.051), (46, 0.038), (47, 0.028), (48, 0.018), (49, 0.048)]
simIndex simValue paperId paperTitle
same-paper 1 0.93911165 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.
2 0.77691746 23 cvpr-2013-A Practical Rank-Constrained Eight-Point Algorithm for Fundamental Matrix Estimation
Author: Yinqiang Zheng, Shigeki Sugimoto, Masatoshi Okutomi
Abstract: Due to its simplicity, the eight-point algorithm has been widely used in fundamental matrix estimation. Unfortunately, the rank-2 constraint of a fundamental matrix is enforced via a posterior rank correction step, thus leading to non-optimal solutions to the original problem. To address this drawback, existing algorithms need to solve either a very high order polynomial or a sequence of convex relaxation problems, both of which are computationally ineffective and numerically unstable. In this work, we present a new rank-2 constrained eight-point algorithm, which directly incorporates the rank-2 constraint in the minimization process. To avoid singularities, we propose to solve seven subproblems and retrieve their globally optimal solutions by using tailored polynomial system solvers. Our proposed method is noniterative, computationally efficient and numerically stable. Experiment results have verified its superiority over existing algebraic error based algorithms in terms of accuracy, as well as its advantages when used to initialize geometric error based algorithms.
3 0.7345019 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.
4 0.71031141 429 cvpr-2013-The Generalized Laplacian Distance and Its Applications for Visual Matching
Author: Elhanan Elboer, Michael Werman, Yacov Hel-Or
Abstract: The graph Laplacian operator, which originated in spectral graph theory, is commonly used for learning applications such as spectral clustering and embedding. In this paper we explore the Laplacian distance, a distance function related to the graph Laplacian, and use it for visual search. We show that previous techniques such as Matching by Tone Mapping (MTM) are particular cases of the Laplacian distance. Generalizing the Laplacian distance results in distance measures which are tolerant to various visual distortions. A novel algorithm based on linear decomposition makes it possible to compute these generalized distances efficiently. The proposed approach is demonstrated for tone mapping invariant, outlier robust and multimodal template matching.
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.
6 0.70409769 93 cvpr-2013-Constraints as Features
7 0.69776815 6 cvpr-2013-A Comparative Study of Modern Inference Techniques for Discrete Energy Minimization Problems
8 0.6967088 95 cvpr-2013-Continuous Inference in Graphical Models with Polynomial Energies
9 0.69337386 171 cvpr-2013-Fast Trust Region for Segmentation
10 0.68143201 41 cvpr-2013-An Iterated L1 Algorithm for Non-smooth Non-convex Optimization in Computer Vision
11 0.66983759 448 cvpr-2013-Universality of the Local Marginal Polytope
12 0.64676225 191 cvpr-2013-Graph-Laplacian PCA: Closed-Form Solution and Robustness
13 0.64518309 106 cvpr-2013-Deformable Graph Matching
14 0.63706744 184 cvpr-2013-Gauging Association Patterns of Chromosome Territories via Chromatic Median
15 0.62433666 308 cvpr-2013-Nonlinearly Constrained MRFs: Exploring the Intrinsic Dimensions of Higher-Order Cliques
16 0.61589944 262 cvpr-2013-Learning for Structured Prediction Using Approximate Subgradient Descent with Working Sets
17 0.61198193 109 cvpr-2013-Dense Non-rigid Point-Matching Using Random Projections
18 0.60237402 437 cvpr-2013-Towards Fast and Accurate Segmentation
19 0.59786808 379 cvpr-2013-Scalable Sparse Subspace Clustering
20 0.58821106 20 cvpr-2013-A New Model and Simple Algorithms for Multi-label Mumford-Shah Problems
topicId topicWeight
[(3, 0.288), (10, 0.108), (16, 0.022), (26, 0.045), (33, 0.258), (67, 0.038), (69, 0.039), (80, 0.01), (87, 0.065)]
simIndex simValue paperId paperTitle
1 0.84452289 289 cvpr-2013-Monocular Template-Based 3D Reconstruction of Extensible Surfaces with Local Linear Elasticity
Author: Abed Malti, Richard Hartley, Adrien Bartoli, Jae-Hak Kim
Abstract: We propose a new approach for template-based extensible surface reconstruction from a single view. We extend the method of isometric surface reconstruction and more recent work on conformal surface reconstruction. Our approach relies on the minimization of a proposed stretching energy formalized with respect to the Poisson ratio parameter of the surface. We derive a patch-based formulation of this stretching energy by assuming local linear elasticity. This formulation unifies geometrical and mechanical constraints in a single energy term. We prevent local scale ambiguities by imposing a set of fixed boundary 3D points. We experimentally prove the sufficiency of this set of boundary points and demonstrate the effectiveness of our approach on different developable and non-developable surfaces with a wide range of extensibility.
same-paper 2 0.80094147 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.
3 0.7812832 226 cvpr-2013-Intrinsic Characterization of Dynamic Surfaces
Author: Tony Tung, Takashi Matsuyama
Abstract: This paper presents a novel approach to characterize deformable surface using intrinsic property dynamics. 3D dynamic surfaces representing humans in motion can be obtained using multiple view stereo reconstruction methods or depth cameras. Nowadays these technologies have become capable to capture surface variations in real-time, and give details such as clothing wrinkles and deformations. Assuming repetitive patterns in the deformations, we propose to model complex surface variations using sets of linear dynamical systems (LDS) where observations across time are given by surface intrinsic properties such as local curvatures. We introduce an approach based on bags of dynamical systems, where each surface feature to be represented in the codebook is modeled by a set of LDS equipped with timing structure. Experiments are performed on datasets of real-world dynamical surfaces and show compelling results for description, classification and segmentation.
4 0.75404876 91 cvpr-2013-Consensus of k-NNs for Robust Neighborhood Selection on Graph-Based Manifolds
Author: Vittal Premachandran, Ramakrishna Kakarala
Abstract: Propagating similarity information along the data manifold requires careful selection of local neighborhood. Selecting a “good” neighborhood in an unsupervised setting, given an affinity graph, has been a difficult task. The most common way to select a local neighborhood has been to use the k-nearest neighborhood (k-NN) selection criterion. However, it has the tendency to include noisy edges. In this paper, we propose a way to select a robust neighborhood using the consensus of multiple rounds of k-NNs. We explain how using consensus information can give better control over neighborhood selection. We also explain in detail the problems with another recently proposed neighborhood selection criteria, i.e., Dominant Neighbors, and show that our method is immune to those problems. Finally, we show the results from experiments in which we compare our method to other neighborhood selection approaches. The results corroborate our claims that consensus ofk-NNs does indeed help in selecting more robust and stable localities.
5 0.74785942 225 cvpr-2013-Integrating Grammar and Segmentation for Human Pose Estimation
Author: Brandon Rothrock, Seyoung Park, Song-Chun Zhu
Abstract: In this paper we present a compositional and-or graph grammar model for human pose estimation. Our model has three distinguishing features: (i) large appearance differences between people are handled compositionally by allowingparts or collections ofparts to be substituted with alternative variants, (ii) each variant is a sub-model that can define its own articulated geometry and context-sensitive compatibility with neighboring part variants, and (iii) background region segmentation is incorporated into the part appearance models to better estimate the contrast of a part region from its surroundings, and improve resilience to background clutter. The resulting integrated framework is trained discriminatively in a max-margin framework using an efficient and exact inference algorithm. We present experimental evaluation of our model on two popular datasets, and show performance improvements over the state-of-art on both benchmarks.
7 0.73290819 244 cvpr-2013-Large Displacement Optical Flow from Nearest Neighbor Fields
8 0.71924514 44 cvpr-2013-Area Preserving Brain Mapping
9 0.71118945 242 cvpr-2013-Label Propagation from ImageNet to 3D Point Clouds
10 0.71103609 365 cvpr-2013-Robust Real-Time Tracking of Multiple Objects by Volumetric Mass Densities
11 0.71084273 446 cvpr-2013-Understanding Indoor Scenes Using 3D Geometric Phrases
12 0.71030784 121 cvpr-2013-Detection- and Trajectory-Level Exclusion in Multiple Object Tracking
13 0.71022797 227 cvpr-2013-Intrinsic Scene Properties from a Single RGB-D Image
14 0.7099635 143 cvpr-2013-Efficient Large-Scale Structured Learning
15 0.70993167 98 cvpr-2013-Cross-View Action Recognition via a Continuous Virtual Path
16 0.70960766 248 cvpr-2013-Learning Collections of Part Models for Object Recognition
17 0.70906126 104 cvpr-2013-Deep Convolutional Network Cascade for Facial Point Detection
18 0.70891148 111 cvpr-2013-Dense Reconstruction Using 3D Object Shape Priors
19 0.70888156 14 cvpr-2013-A Joint Model for 2D and 3D Pose Estimation from a Single Image
20 0.70874596 245 cvpr-2013-Layer Depth Denoising and Completion for Structured-Light RGB-D Cameras