cvpr cvpr2013 cvpr2013-23 knowledge-graph by maker-knowledge-mining
Source: pdf
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.
Reference: text
sentIndex sentText sentNum sentScore
1 Abstract Due to its simplicity, the eight-point algorithm has been widely used in fundamental matrix estimation. [sent-4, score-0.315]
2 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. [sent-5, score-0.543]
3 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. [sent-6, score-0.492]
4 To avoid singularities, we propose to solve seven subproblems and retrieve their globally optimal solutions by using tailored polynomial system solvers. [sent-8, score-0.587]
5 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. [sent-10, score-0.196]
6 Introduction Fundamental matrix estimation from eight or more point correspondences is a classical and important problem in multiview geometry analysis [11], with widespread applications in camera calibration, 3D reconstruction, motion segmentation and so on. [sent-12, score-0.134]
7 To properly account for the epipolar geometry, a fundamental matrix should be of rank-2, an essential but extremely challenging nonconvex constraint that every fundamental matrix estimation algorithm has to cope with. [sent-13, score-0.85]
8 Related Works Ever since the pioneering work by Longuet-Higgins [17], a great variety of algorithms, taking into consideration the rank constraint via either posterior rank correction or interior rank-2 parametrization, have been proposed in . [sent-16, score-0.272]
9 Among them, there is a category of robust estimation methods, like RANSAC [7] and MLESAC [22], that seek to estimate the fundamental matrix in the presence of outliers, i. [sent-22, score-0.315]
10 Although robustness to outliers is certainly of great interest, in this work, we concentrate on the other important category of methods that aim at estimating an accurate fundamental matrix from noisy and redundant cor- respondences after outliers, if any, have been properly removed. [sent-25, score-0.396]
11 Some noticeable algorithms, like [2], have been proposed for this regard, however, it is still widely believed that reprojection error minimization is a challenging task. [sent-30, score-0.125]
12 It is even nontrivial to evaluate the minimum reprojection error compatible with a known fundamental matrix, i. [sent-31, score-0.357]
13 Due to their simplicity, algebraic error based algorithms have attracted a lot of attention in fundamental matrix estimation. [sent-38, score-0.461]
14 Longuet-Higgins [17] proposed the first eight-point algorithm to estimate the (calibrated therein) fundamental matrix, which boils down to a simple eigenvalue factorization problem. [sent-39, score-0.49]
15 Although this hyper-renormalization technique is shown to be effective in ellipse fitting [12], we have found that it fails to work as expected for fundamental matrix estimation. [sent-44, score-0.315]
16 The main reason lies in that the rank-2 constraint of a fundamental matrix is ignored in the process of iterative bias correction. [sent-45, score-0.39]
17 As in the normalized eight-point algorithm [8], one has to posteriorly correct the estimated fundamental matrix to be of rank-2, which leads to non-optimal solutions. [sent-46, score-0.315]
18 In [9], Hartley proposed a projection technique to estimate the epipole in an iterative way, which suffers from the risk ofgetting trapped into local minimum. [sent-49, score-0.151]
19 [5] proposed a sum-of-square (SOS) convex relaxation method to minimize the algebraic error with rank-2 constraint, in which one has to adopt bisection and solve a sequence of semidefinite programming (SDP) problems of fixed size. [sent-52, score-0.355]
20 More seriously, it suffers from some singularities caused by improper parametrization2, thus inapplicable to some otherwise well-posed camera configurations (provided nondegenerate parametrization), such as pure camera translation along the horizontal axis. [sent-55, score-0.243]
21 [3] avoided these singularities by using the determinant constraint and advocated moment relaxation to solve the resulting polynomial optimization problem. [sent-57, score-0.645]
22 The cost is to solving a hierarchy of SDP relaxation problems of increasing size, whose computational burden is even higher than the SOS relaxation in [5]. [sent-58, score-0.204]
23 In addition, the global optimality certificate is to check whether the rank of the moment matrix is one, again a numerically sensitive operation. [sent-59, score-0.327]
24 1The bisection path is determined by the sign of the maximum eigenvalue in Equation 15 of [5]. [sent-60, score-0.283]
25 Overview of Our Work In this work, we propose a new rank-2 constrained eightpoint algorithm for fundamental matrix estimation. [sent-67, score-0.438]
26 Similar to [3,5], it is based on the algebraic error, and copes with the rank-2 constraint directly. [sent-68, score-0.171]
27 By carefully investigating the linear dependence between the three columns of a fundamental matrix, we solve seven subproblems so as to avoid improper singularities and keep the resulting optimization problems tractable. [sent-69, score-0.728]
28 According to the problem structure of their firstorder optimality conditions, we use univariate/multivariate polynomial system solving techniques to find the guaranteed globally optimal solution without iterations. [sent-70, score-0.461]
29 Especially, for high order multivariate systems, we customize a novel generalized eigenvalue solver, which successfully conquers numerical instabilities that would upset an automatically constructed Gr¨ obner basis solver [15] and a polynomial eigenvalue solver with linearization [ 16]. [sent-71, score-1.054]
30 When compared with the state-of-the-art SOS convex relaxation algorithm [5], our proposed method is noniterative, computationally efficient and numerically stable. [sent-75, score-0.175]
31 3 shows the details of solving polynomial systems, with emphasis on the generalized eigenvalue factorization method for multivariate systems. [sent-80, score-0.627]
32 The uppercase letter T is reserved for matrix or vector transpose. [sent-94, score-0.126]
33 × jective is to estimate a 3 3 fundamental matrix F satisfying tjhecet epipolar cstoinmsatrtaeinat3s x? [sent-97, score-0.421]
34 Therefore, to estimate F, it is common to minimize the algebraic error defined by ? [sent-101, score-0.146]
35 (2) Because of the epipolar geometry constraint that all epipolar lines must intersect at a point, i. [sent-105, score-0.287]
36 the epipole, a fundamental matrix should be of rank-2. [sent-107, score-0.315]
37 In order to avoid the drawback of posterior rank-2 correction in [8, 12], it is mandatory to incorporate the rank constraint in the minimization process. [sent-108, score-0.293]
38 To this end, we can add the determinant constraint [3, 24], which leads to a challenging polynomial optimization problem. [sent-109, score-0.354]
39 On the contrary, it is possible to parameterize the fundamental matrix properly such that the rank-2 constraint is interiorly satisfied. [sent-110, score-0.429]
40 In this work, we adopt the right epipole parametrization, such that Fe = 0. [sent-111, score-0.151]
41 Therefore, when using this epipole parametrization, special attention must be paid in order to avoid any possibility of additional singularities. [sent-120, score-0.28]
42 In the following, we present seven subproblems so as to avoid improper singularities and keep the resulting optimization problems tractable. [sent-125, score-0.458]
43 1 Case-1: f3 = f6 = f9 = 0 When f3 = f6 = f9 = 0, the fundamental matrix F is naturally rank deficient. [sent-130, score-0.359]
44 To avoid the all-zero solution, we add the unit-norm constraint fk2 = 1, leading to the first subproblem (SP-1) ? [sent-131, score-0.267]
45 1 By analyzing its first order optimality condition, it is trivial to solve the optimization problem in Eq. [sent-142, score-0.165]
46 2 Case-2: f3 =0 = When f3 0, we can rescale F such that f3 = 1to avoid the all-zer? [sent-146, score-0.141]
47 a nN roeswc we Fcon ssucidhe rth htahte following three possibilities: (i) x 0: Based on the scale and sign ambiguities of x, y, z, we can B raessceadle o x shuec hsc tahlaet x d= s g1n. [sent-148, score-0.191]
48 aTmheb optimization problem corresponding to the second subproblem (SP2) reads = ? [sent-149, score-0.127]
49 The denominator q(y, z) is a 6-order positive bivariate polynomial with respect to y and z, since G is positive definite. [sent-176, score-0.341]
50 The nominator p(y, z) is a 6-order nonnegative bivariate polynomial with respect to y and z, due to the facts that the objective function is nonnegative and q(y, z) > 0. [sent-177, score-0.341]
51 (ii) x = 0, y 0: Based on the scale and sign ambiguities(i io)f x x, y, z, we can B raessceadle o y shuec hsc athleat a y d= s g1. [sent-183, score-0.191]
52 n N amowbi gthueoptimization problem corresponding to the third subproblem (SP-3) is formulated as = ? [sent-184, score-0.127]
53 (10) can be simplified (details omitted) into the following unconstrained fractional programming mzin p q˜˜((zz)), (11) in which ˜ q(z) is a 4th-order univariate polynomial, while ˜p(z) a 6th-order univariate polynomial with respect to z. [sent-198, score-0.497]
54 3 Case-3: f6 =0 = When f6 0, we can rescale F such that f6 = 1to avoid the all-zer? [sent-209, score-0.141]
55 a nS rimesiclaalre t oF C suasceh-2 th, we can obtain the fourth subproblem (SP-4) corresponding to the possibility x 0, and the fifth subproblem (SP-5) corresponding to txhe? [sent-211, score-0.318]
56 Although tmheit c toheef dfieciteanilsts might v baedifferent, the polynomial formation of (SP-4) is the same as that in (SP-2). [sent-214, score-0.279]
57 4 Case-4: f9 0 = = = Similarly, when f9 0, we can rescale F such that f9 = 1 to avoid the all-zero? [sent-218, score-0.141]
58 c aSnim reislacra ltoe CFa ssuec-h2, we can obtain the sixth subproblem (SP-6) corresponding to the possibility x 0, and the seventh subproblem (SP-7) corresponding t? [sent-220, score-0.318]
59 Again, t h=e polynomial fhoer dmearitivoanti oonf (SP-6) is the same as that in (SP-2) and (SP-4). [sent-223, score-0.279]
60 3, for each subproblem, we can find all its stationary points by solving the polynomial system arising from its first-order optimality condition. [sent-228, score-0.406]
61 As a consequence, there are at most seven solutions after solving all seven subproblems. [sent-230, score-0.138]
62 Solving Polynomial Systems To find the globally optimal solution of the fractional problem, we derive its first-order optimality condition, and identify all the stationary points. [sent-233, score-0.236]
63 Univariate Polynomial For (SP-3), its first-order optimality condition reads dp˜d (zz) q˜(z) − p˜ (z)d q˜d(zz)= 0, × (12) which is a 9th-order univariate polynomial. [sent-236, score-0.265]
64 We calculate the eigenvalues of its companion matrix, and choose the real eigenvalue with the smallest objective value in Eq. [sent-237, score-0.216]
65 Multivariate Polynomials The first-order optimality condition corresponding to (SP-2) is composed of the following two 11-order bivariate polynomials Formu∂l tpiv∂( ayrz,ia te)qp(oyl,zn)om− iap(lys,z )te∂ mqs(∂ ,yzi,t zs)co=m0 ,. [sent-242, score-0.245]
66 [15] developed an automatic program to build the Gr¨ obner basis based polynomial system solver. [sent-245, score-0.378]
67 e Through 2ex1t8e,n wsihviel tests, we hheaavec ifoonunmda tthriaxt tisheo fn1u1m0e×ri1c1a0l stability hofe xthteisn aiuvteotmesatst,ically generated Gr¨ obner basis solver is poor. [sent-249, score-0.17]
68 The other possible choice is the latest polynomial eigenvalue factorization technique [ 16], which can be further reduced to the general eigenvalue factorization problem using linearization. [sent-251, score-0.795]
69 In addition, it drastically deteriorates the condition number and causes numerical instability, since the order of the polynomial system in Eq. [sent-253, score-0.392]
70 To avoid the aforementioned numerical problems, we first introduce an auxiliary variable δ, such that my,zi,nδ δ, s. [sent-255, score-0.122]
71 Actually, it helps avoid any explicit elimination and makes possible a stable polynomial system solver via generalized eigenvalue factorization. [sent-259, score-0.694]
72 After introducing the Lagrange multiplier ρ, we derive the first-order optimality condition of Eq. [sent-260, score-0.183]
73 As a consequence, the first-order optimality condition in Eq. [sent-263, score-0.183]
74 (15) can be simplified into ∂p∂(yy,z)= δ∂q(∂yy,z), ∂p∂(yz,z)= δ∂q(∂yz,z), (16) p(y, z) = δq(y, z) , which is composed of three polynomial equations with respect to three variables y, z, δ. [sent-264, score-0.279]
75 (16), we can directly set δ as the hidden variable, resulting in a generalized eigenvalue factorization problem without the necessity of linearization. [sent-268, score-0.309]
76 Let u denote a 28-D column vector containing all the monomials of y and z up to 6th-order. [sent-270, score-0.139]
77 (16), we have to generate more equations by multiplying some monomials at both sides of the three equations. [sent-274, score-0.139]
78 We have found that it is necessary to multiply all 45 monomials (up to 8th-order) at both sides of the third equation in Eq. [sent-275, score-0.139]
79 (16), and all 55 monomials (up to 9th-order) at both sides of the first and second equation in Eq. [sent-276, score-0.139]
80 It leads to an expanded polynomial system C˜0 u˜ = δC˜1 u˜, (18) in which u˜ is a 120-D column vector including all 120 monomials up to 14th-order, i. [sent-278, score-0.418]
81 By applying generalized eigenvalue factorization on the 120× 120 matrix pair (Cˆ0, Cˆ1), we can fcintodr zalal tiohen eigenvectors 1 ˜u,2 0fro mma wrixhic pha y, z can be obtained after normalizing the first element of ˜u to 1. [sent-288, score-0.448]
82 Therefore, there might be Cˆ0 Cˆ0 Cˆ1, some dummy solutions that violate the original polynomial system in Eq. [sent-290, score-0.279]
83 To find the globally optimal solution, we evaluate the objective value for each real solution pair (y, z), and choose the one with the smallest objective value (e. [sent-292, score-0.153]
84 By using the same generalized eigenvalue solver, we can also solve the polynomial system from (SP-4) and (SP-6). [sent-296, score-0.542]
85 In both algorithms, the rank-2 constraint is imposed via posterior rank-2 correction. [sent-300, score-0.115]
86 It is widely recognized that the Sampson distance error is sufficiently close to, but much easier to evaluate than, the reprojection error. [sent-354, score-0.125]
87 Given an image pair, we first build tentative matches by matching SIFT points and remove potential outliers by using RANSAC together with the minimal 7-point 111555445 919 (a) Image Pair ? [sent-359, score-0.128]
88 Then, we estimate the fundamental matrix by using CLM+RC8P, and correct the correspondences to be noisefree via optimal triangulation [10]. [sent-391, score-0.366]
89 The SOS algorithm provides poor estimation results due to its numerical instability as well as its risk of inaccuracy when the camera motion approaches its singularities. [sent-418, score-0.119]
90 We use SeDuMi [2 1] to solve the SDP relaxation problems in SOS. [sent-425, score-0.14]
91 Then, we estimate the fundamental matrix by 111555555200 the competing algorithms. [sent-434, score-0.36]
92 Conclusions We have presented a new eight-point algorithm, in which the rank-2 constraint of a fundamental matrix is directly enforced in the process of minimization. [sent-444, score-0.39]
93 Unlike the stateof-the-art sum-of-square relaxation method, our proposed algorithm does not suffer from additional singularities caused by improper parametrization. [sent-445, score-0.345]
94 Numer- × ical experiments, using both synthetic data and real images, have demonstrated its superiority over the popular normalized eight-point algorithm with posterior rank-2 correction as well as the convex relaxation method. [sent-447, score-0.211]
95 We have noted that the most time-consuming operation in our proposed algorithm is the generalized eigenvalue factorization of three 120 120 matrix pairs. [sent-451, score-0.392]
96 It is expected that our algorithm could be significantly accelerated by using the characteristic polynomial based technique in [4]. [sent-453, score-0.279]
97 Rank-constrained fundamental matrix estimation by polynomial global optimization versus the eightpoint algorithm. [sent-474, score-0.678]
98 Estimating the fundamental matrix via constrained least-squares: a convex approach. [sent-488, score-0.354]
99 Evaluation of epipole estimation methods with/without rank-2 constraint across algebraic/geometric error functions. [sent-575, score-0.276]
100 A branch and contract algorithm for globally optimal fundamental matrix estimation. [sent-596, score-0.37]
wordName wordTfidf (topN-words)
[('clm', 0.343), ('polynomial', 0.279), ('fundamental', 0.232), ('eigenvalue', 0.174), ('sos', 0.165), ('epipole', 0.151), ('singularities', 0.151), ('sampson', 0.148), ('monomials', 0.139), ('subproblem', 0.127), ('optimality', 0.127), ('rmse', 0.119), ('mtm', 0.114), ('chesi', 0.111), ('dinosaur', 0.111), ('kanatani', 0.111), ('merton', 0.111), ('epipolar', 0.106), ('relaxation', 0.102), ('kukelova', 0.099), ('obner', 0.099), ('algebraic', 0.096), ('improper', 0.092), ('hartley', 0.091), ('sdp', 0.09), ('factorization', 0.084), ('arial', 0.084), ('bujnak', 0.084), ('eightpoint', 0.084), ('hyperren', 0.084), ('itfxi', 0.084), ('mfin', 0.084), ('matrix', 0.083), ('univariate', 0.082), ('subproblems', 0.081), ('rescale', 0.076), ('reprojection', 0.075), ('constraint', 0.075), ('noniterative', 0.074), ('numerically', 0.073), ('solver', 0.071), ('correction', 0.069), ('seven', 0.069), ('bisection', 0.069), ('avoid', 0.065), ('possibility', 0.064), ('bivariate', 0.062), ('instability', 0.062), ('parametrization', 0.059), ('gr', 0.059), ('numerical', 0.057), ('condition', 0.056), ('pair', 0.056), ('bugarin', 0.056), ('cathedral', 0.056), ('chojnacki', 0.056), ('migita', 0.056), ('msleip', 0.056), ('raessceadle', 0.056), ('sugimoto', 0.056), ('tfxi', 0.056), ('wtieo', 0.056), ('globally', 0.055), ('elimination', 0.054), ('fractional', 0.054), ('zz', 0.052), ('correspondences', 0.051), ('generalized', 0.051), ('error', 0.05), ('milliseconds', 0.05), ('mlesac', 0.049), ('notre', 0.049), ('renormalization', 0.049), ('shuec', 0.049), ('college', 0.047), ('sedumi', 0.046), ('generator', 0.046), ('dame', 0.046), ('hsc', 0.046), ('zheng', 0.045), ('competing', 0.045), ('rank', 0.044), ('minimal', 0.043), ('bartoli', 0.043), ('lls', 0.043), ('lowercase', 0.043), ('tentative', 0.043), ('uppercase', 0.043), ('outliers', 0.042), ('smallest', 0.042), ('pairs', 0.041), ('iii', 0.041), ('sign', 0.04), ('tpami', 0.04), ('posterior', 0.04), ('linearization', 0.039), ('properly', 0.039), ('multivariate', 0.039), ('constrained', 0.039), ('solve', 0.038)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999976 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.
2 0.15161204 95 cvpr-2013-Continuous Inference in Graphical Models with Polynomial Energies
Author: Mathieu Salzmann
Abstract: In this paper, we tackle the problem of performing inference in graphical models whose energy is a polynomial function of continuous variables. Our energy minimization method follows a dual decomposition approach, where the global problem is split into subproblems defined over the graph cliques. The optimal solution to these subproblems is obtained by making use of a polynomial system solver. Our algorithm inherits the convergence guarantees of dual decomposition. To speed up optimization, we also introduce a variant of this algorithm based on the augmented Lagrangian method. Our experiments illustrate the diversity of computer vision problems that can be expressed with polynomial energies, and demonstrate the benefits of our approach over existing continuous inference methods.
Author: Jörg Hendrik Kappes, Markus Speth, Gerhard Reinelt, Christoph Schnörr
Abstract: Discrete graphical models (also known as discrete Markov random fields) are a major conceptual tool to model the structure of optimization problems in computer vision. While in the last decade research has focused on fast approximative methods, algorithms that provide globally optimal solutions have come more into the research focus in the last years. However, large scale computer vision problems seemed to be out of reach for such methods. In this paper we introduce a promising way to bridge this gap based on partial optimality and structural properties of the underlying problem factorization. Combining these preprocessing steps, we are able to solve grids of size 2048 2048 in less than 90 seconds. On the hitherto unsolva2b04le8 C×h2i0ne4s8e character dataset of Nowozin et al. we obtain provably optimal results in 56% of the instances and achieve competitive runtimes on other recent benchmark problems. While in the present work only generalized Potts models are considered, an extension to general graphical models seems to be feasible.
4 0.10804983 290 cvpr-2013-Motion Estimation for Self-Driving Cars with a Generalized Camera
Author: Gim Hee Lee, Friedrich Faundorfer, Marc Pollefeys
Abstract: In this paper, we present a visual ego-motion estimation algorithm for a self-driving car equipped with a closeto-market multi-camera system. By modeling the multicamera system as a generalized camera and applying the non-holonomic motion constraint of a car, we show that this leads to a novel 2-point minimal solution for the generalized essential matrix where the full relative motion including metric scale can be obtained. We provide the analytical solutions for the general case with at least one inter-camera correspondence and a special case with only intra-camera correspondences. We show that up to a maximum of 6 solutions exist for both cases. We identify the existence of degeneracy when the car undergoes straight motion in the special case with only intra-camera correspondences where the scale becomes unobservable and provide a practical alternative solution. Our formulation can be efficiently implemented within RANSAC for robust estimation. We verify the validity of our assumptions on the motion model by comparing our results on a large real-world dataset collected by a car equipped with 4 cameras with minimal overlapping field-of-views against the GPS/INS ground truth.
5 0.10113211 359 cvpr-2013-Robust Discriminative Response Map Fitting with Constrained Local Models
Author: Akshay Asthana, Stefanos Zafeiriou, Shiyang Cheng, Maja Pantic
Abstract: We present a novel discriminative regression based approach for the Constrained Local Models (CLMs) framework, referred to as the Discriminative Response Map Fitting (DRMF) method, which shows impressive performance in the generic face fitting scenario. The motivation behind this approach is that, unlike the holistic texture based features used in the discriminative AAM approaches, the response map can be represented by a small set of parameters and these parameters can be very efficiently used for reconstructing unseen response maps. Furthermore, we show that by adopting very simple off-the-shelf regression techniques, it is possible to learn robust functions from response maps to the shape parameters updates. The experiments, conducted on Multi-PIE, XM2VTS and LFPW database, show that the proposed DRMF method outperforms stateof-the-art algorithms for the task of generic face fitting. Moreover, the DRMF method is computationally very efficient and is real-time capable. The current MATLAB implementation takes 1second per image. To facilitate future comparisons, we release the MATLAB code1 and the pretrained models for research purposes.
6 0.098901019 344 cvpr-2013-Radial Distortion Self-Calibration
7 0.096883431 317 cvpr-2013-Optimal Geometric Fitting under the Truncated L2-Norm
8 0.096484579 9 cvpr-2013-A Fast Semidefinite Approach to Solving Binary Quadratic Problems
9 0.096209995 362 cvpr-2013-Robust Monocular Epipolar Flow Estimation
10 0.096097209 164 cvpr-2013-Fast Convolutional Sparse Coding
11 0.09199968 423 cvpr-2013-Template-Based Isometric Deformable 3D Reconstruction with Sampling-Based Focal Length Self-Calibration
12 0.081174225 360 cvpr-2013-Robust Estimation of Nonrigid Transformation for Point Set Registration
13 0.071026273 113 cvpr-2013-Dense Variational Reconstruction of Non-rigid Surfaces from Monocular Video
14 0.070727631 188 cvpr-2013-Globally Consistent Multi-label Assignment on the Ray Space of 4D Light Fields
15 0.070123404 170 cvpr-2013-Fast Rigid Motion Segmentation via Incrementally-Complex Local Models
16 0.069781624 300 cvpr-2013-Multi-target Tracking by Lagrangian Relaxation to Min-cost Network Flow
17 0.068732478 429 cvpr-2013-The Generalized Laplacian Distance and Its Applications for Visual Matching
18 0.065524027 437 cvpr-2013-Towards Fast and Accurate Segmentation
19 0.063363902 286 cvpr-2013-Mirror Surface Reconstruction from a Single Image
20 0.061422739 138 cvpr-2013-Efficient 2D-to-3D Correspondence Filtering for Scalable 3D Object Recognition
topicId topicWeight
[(0, 0.145), (1, 0.08), (2, -0.022), (3, 0.044), (4, 0.03), (5, -0.02), (6, -0.011), (7, -0.065), (8, -0.033), (9, 0.012), (10, 0.033), (11, 0.087), (12, -0.032), (13, -0.069), (14, -0.051), (15, -0.018), (16, 0.003), (17, 0.034), (18, 0.067), (19, 0.026), (20, -0.021), (21, -0.012), (22, -0.039), (23, -0.004), (24, 0.153), (25, 0.002), (26, -0.119), (27, 0.017), (28, 0.041), (29, -0.026), (30, 0.053), (31, 0.009), (32, 0.002), (33, -0.05), (34, -0.083), (35, 0.009), (36, 0.027), (37, 0.028), (38, -0.017), (39, 0.007), (40, 0.02), (41, 0.003), (42, -0.087), (43, -0.005), (44, -0.013), (45, 0.025), (46, 0.045), (47, -0.012), (48, 0.028), (49, 0.067)]
simIndex simValue paperId paperTitle
same-paper 1 0.94628805 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.
2 0.82897145 95 cvpr-2013-Continuous Inference in Graphical Models with Polynomial Energies
Author: Mathieu Salzmann
Abstract: In this paper, we tackle the problem of performing inference in graphical models whose energy is a polynomial function of continuous variables. Our energy minimization method follows a dual decomposition approach, where the global problem is split into subproblems defined over the graph cliques. The optimal solution to these subproblems is obtained by making use of a polynomial system solver. Our algorithm inherits the convergence guarantees of dual decomposition. To speed up optimization, we also introduce a variant of this algorithm based on the augmented Lagrangian method. Our experiments illustrate the diversity of computer vision problems that can be expressed with polynomial energies, and demonstrate the benefits of our approach over existing continuous inference methods.
3 0.7699877 41 cvpr-2013-An Iterated L1 Algorithm for Non-smooth Non-convex Optimization in Computer Vision
Author: Peter Ochs, Alexey Dosovitskiy, Thomas Brox, Thomas Pock
Abstract: Natural image statistics indicate that we should use nonconvex norms for most regularization tasks in image processing and computer vision. Still, they are rarely used in practice due to the challenge to optimize them. Recently, iteratively reweighed ?1 minimization has been proposed as a way to tackle a class of non-convex functions by solving a sequence of convex ?2-?1 problems. Here we extend the problem class to linearly constrained optimization of a Lipschitz continuous function, which is the sum of a convex function and a function being concave and increasing on the non-negative orthant (possibly non-convex and nonconcave on the whole space). This allows to apply the algorithm to many computer vision tasks. We show the effect of non-convex regularizers on image denoising, deconvolution, optical flow, and depth map fusion. Non-convexity is particularly interesting in combination with total generalized variation and learned image priors. Efficient optimization is made possible by some important properties that are shown to hold.
4 0.75195873 317 cvpr-2013-Optimal Geometric Fitting under the Truncated L2-Norm
Author: Erik Ask, Olof Enqvist, Fredrik Kahl
Abstract: This paper is concerned with model fitting in the presence of noise and outliers. Previously it has been shown that the number of outliers can be minimized with polynomial complexity in the number of measurements. This paper improves on these results in two ways. First, it is shown that for a large class of problems, the statistically more desirable truncated L2-norm can be optimized with the same complexity. Then, with the same methodology, it is shown how to transform multi-model fitting into a purely combinatorial problem—with worst-case complexity that is polynomial in the number of measurements, though exponential in the number of models. We apply our framework to a series of hard registration and stitching problems demonstrating that the approach is not only of theoretical interest. It gives a practical method for simultaneously dealing with measurement noise and large amounts of outliers for fitting problems with lowdimensional models.
5 0.74337238 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.
7 0.73169905 448 cvpr-2013-Universality of the Local Marginal Polytope
8 0.69470495 6 cvpr-2013-A Comparative Study of Modern Inference Techniques for Discrete Energy Minimization Problems
9 0.6849128 308 cvpr-2013-Nonlinearly Constrained MRFs: Exploring the Intrinsic Dimensions of Higher-Order Cliques
10 0.67651206 51 cvpr-2013-Auxiliary Cuts for General Classes of Higher Order Functionals
11 0.65168273 171 cvpr-2013-Fast Trust Region for Segmentation
12 0.64738125 20 cvpr-2013-A New Model and Simple Algorithms for Multi-label Mumford-Shah Problems
13 0.64486969 128 cvpr-2013-Discrete MRF Inference of Marginal Densities for Non-uniformly Discretized Variable Space
14 0.60450375 35 cvpr-2013-Adaptive Compressed Tomography Sensing
15 0.59397119 47 cvpr-2013-As-Projective-As-Possible Image Stitching with Moving DLT
16 0.59262925 341 cvpr-2013-Procrustean Normal Distribution for Non-rigid Structure from Motion
17 0.57705706 290 cvpr-2013-Motion Estimation for Self-Driving Cars with a Generalized Camera
18 0.5630185 429 cvpr-2013-The Generalized Laplacian Distance and Its Applications for Visual Matching
19 0.54780519 262 cvpr-2013-Learning for Structured Prediction Using Approximate Subgradient Descent with Working Sets
20 0.54132283 7 cvpr-2013-A Divide-and-Conquer Method for Scalable Low-Rank Latent Matrix Pursuit
topicId topicWeight
[(10, 0.126), (16, 0.044), (26, 0.075), (28, 0.013), (33, 0.247), (67, 0.026), (69, 0.035), (70, 0.293), (87, 0.051)]
simIndex simValue paperId paperTitle
1 0.79617101 174 cvpr-2013-Fine-Grained Crowdsourcing for Fine-Grained Recognition
Author: Jia Deng, Jonathan Krause, Li Fei-Fei
Abstract: Fine-grained recognition concerns categorization at sub-ordinate levels, where the distinction between object classes is highly local. Compared to basic level recognition, fine-grained categorization can be more challenging as there are in general less data and fewer discriminative features. This necessitates the use of stronger prior for feature selection. In this work, we include humans in the loop to help computers select discriminative features. We introduce a novel online game called “Bubbles ” that reveals discriminative features humans use. The player’s goal is to identify the category of a heavily blurred image. During the game, the player can choose to reveal full details of circular regions ( “bubbles”), with a certain penalty. With proper setup the game generates discriminative bubbles with assured quality. We next propose the “BubbleBank” algorithm that uses the human selected bubbles to improve machine recognition performance. Experiments demonstrate that our approach yields large improvements over the previous state of the art on challenging benchmarks.
same-paper 2 0.79586065 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.77906448 466 cvpr-2013-Whitened Expectation Propagation: Non-Lambertian Shape from Shading and Shadow
Author: Brian Potetz, Mohammadreza Hajiarbabi
Abstract: For problems over continuous random variables, MRFs with large cliques pose a challenge in probabilistic inference. Difficulties in performing optimization efficiently have limited the probabilistic models explored in computer vision and other fields. One inference technique that handles large cliques well is Expectation Propagation. EP offers run times independent of clique size, which instead depend only on the rank, or intrinsic dimensionality, of potentials. This property would be highly advantageous in computer vision. Unfortunately, for grid-shaped models common in vision, traditional Gaussian EP requires quadratic space and cubic time in the number of pixels. Here, we propose a variation of EP that exploits regularities in natural scene statistics to achieve run times that are linear in both number of pixels and clique size. We test these methods on shape from shading, and we demonstrate strong performance not only for Lambertian surfaces, but also on arbitrary surface reflectance and lighting arrangements, which requires highly non-Gaussian potentials. Finally, we use large, non-local cliques to exploit cast shadow, which is traditionally ignored in shape from shading.
4 0.76671171 150 cvpr-2013-Event Recognition in Videos by Learning from Heterogeneous Web Sources
Author: Lin Chen, Lixin Duan, Dong Xu
Abstract: In this work, we propose to leverage a large number of loosely labeled web videos (e.g., from YouTube) and web images (e.g., from Google/Bing image search) for visual event recognition in consumer videos without requiring any labeled consumer videos. We formulate this task as a new multi-domain adaptation problem with heterogeneous sources, in which the samples from different source domains can be represented by different types of features with different dimensions (e.g., the SIFTfeaturesfrom web images and space-time (ST) features from web videos) while the target domain samples have all types of features. To effectively cope with the heterogeneous sources where some source domains are more relevant to the target domain, we propose a new method called Multi-domain Adaptation with Heterogeneous Sources (MDA-HS) to learn an optimal target classifier, in which we simultaneously seek the optimal weights for different source domains with different types of features as well as infer the labels of unlabeled target domain data based on multiple types of features. We solve our optimization problem by using the cutting-plane algorithm based on group-based multiple kernel learning. Comprehensive experiments on two datasets demonstrate the effectiveness of MDA-HS for event recognition in consumer videos.
5 0.74198025 87 cvpr-2013-Compressed Hashing
Author: Yue Lin, Rong Jin, Deng Cai, Shuicheng Yan, Xuelong Li
Abstract: Recent studies have shown that hashing methods are effective for high dimensional nearest neighbor search. A common problem shared by many existing hashing methods is that in order to achieve a satisfied performance, a large number of hash tables (i.e., long codewords) are required. To address this challenge, in this paper we propose a novel approach called Compressed Hashing by exploring the techniques of sparse coding and compressed sensing. In particular, we introduce a sparse coding scheme, based on the approximation theory of integral operator, that generate sparse representation for high dimensional vectors. We then project sparse codes into a low dimensional space by effectively exploring the Restricted Isometry Property (RIP), a key property in compressed sensing theory. Both of the theoretical analysis and the empirical studies on two large data sets show that the proposed approach is more effective than the state-of-the-art hashing algorithms.
6 0.70965594 309 cvpr-2013-Nonparametric Scene Parsing with Adaptive Feature Relevance and Semantic Context
7 0.70085645 360 cvpr-2013-Robust Estimation of Nonrigid Transformation for Point Set Registration
8 0.6986255 104 cvpr-2013-Deep Convolutional Network Cascade for Facial Point Detection
9 0.6975466 311 cvpr-2013-Occlusion Patterns for Object Class Detection
10 0.69594425 424 cvpr-2013-Templateless Quasi-rigid Shape Modeling with Implicit Loop-Closure
11 0.69372374 330 cvpr-2013-Photometric Ambient Occlusion
12 0.6935842 31 cvpr-2013-Accurate and Robust Registration of Nonrigid Surface Using Hierarchical Statistical Shape Model
13 0.69332862 267 cvpr-2013-Least Soft-Threshold Squares Tracking
14 0.6930669 68 cvpr-2013-Blur Processing Using Double Discrete Wavelet Transform
15 0.69286364 285 cvpr-2013-Minimum Uncertainty Gap for Robust Visual Tracking
16 0.69283605 96 cvpr-2013-Correlation Filters for Object Alignment
17 0.69282418 245 cvpr-2013-Layer Depth Denoising and Completion for Structured-Light RGB-D Cameras
18 0.69275171 440 cvpr-2013-Tracking People and Their Objects
19 0.69269252 331 cvpr-2013-Physically Plausible 3D Scene Tracking: The Single Actor Hypothesis
20 0.69263434 317 cvpr-2013-Optimal Geometric Fitting under the Truncated L2-Norm