iccv iccv2013 iccv2013-141 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Guoqing Zhou, Qing Wang
Abstract: Optimization using the L∞ norm has been becoming an effective way to solve parameter estimation problems in multiview geometry. But the computational cost increases rapidly with the size of measurement data. Although some strategies have been presented to improve the efficiency of L∞ optimization, it is still an open issue. In the paper, we propose a novel approach under theframework ofenhanced continuous tabu search (ECTS) for generic parameter estimation in multiview geometry. ECTS is an optimization method in the domain of artificial intelligence, which has an interesting ability of covering a wide solution space by promoting the search far away from current solution and consecutively decreasing the possibility of trapping in the local minima. Taking the triangulation as an example, we propose the corresponding ways in the key steps of ECTS, diversification and intensification. We also present theoretical proof to guarantee the global convergence of search with probability one. Experimental results have validated that the ECTS based approach can obtain global optimum efficiently, especially for large scale dimension of parameter. Potentially, the novel ECTS based algorithm can be applied in many applications of multiview geometry.
Reference: text
sentIndex sentText sentNum sentScore
1 cn Abstract Optimization using the L∞ norm has been becoming an effective way to solve parameter estimation problems in multiview geometry. [sent-5, score-0.228]
2 In the paper, we propose a novel approach under theframework ofenhanced continuous tabu search (ECTS) for generic parameter estimation in multiview geometry. [sent-8, score-0.614]
3 ECTS is an optimization method in the domain of artificial intelligence, which has an interesting ability of covering a wide solution space by promoting the search far away from current solution and consecutively decreasing the possibility of trapping in the local minima. [sent-9, score-0.126]
4 Taking the triangulation as an example, we propose the corresponding ways in the key steps of ECTS, diversification and intensification. [sent-10, score-0.328]
5 We also present theoretical proof to guarantee the global convergence of search with probability one. [sent-11, score-0.18]
6 Experimental results have validated that the ECTS based approach can obtain global optimum efficiently, especially for large scale dimension of parameter. [sent-12, score-0.16]
7 Potentially, the novel ECTS based algorithm can be applied in many applications of multiview geometry. [sent-13, score-0.137]
8 Introduction Parameter estimation is one of the most fundamental problems in multiview geometry. [sent-15, score-0.182]
9 The typical measurements of error function include algebraic distance, geometric distance, reprojection error, and Sampson error [9]. [sent-16, score-0.148]
10 Traditional optimization algorithms have been dominated by local optimization techniques based on the L2 norm, such as Newton or Levenberg-Marquardtiterations [9] or bundle adjustment [20] for finding a local optimum. [sent-17, score-0.103]
11 However, solving multiple view geometry problems in general is difficult due to the inherent non-convexity and the presence of local optima. [sent-19, score-0.085]
12 To remedy these problems, a number of literatures have shown that many multiview geometric problems are quasiconvex under L∞ norm [8][13]. [sent-20, score-0.294]
13 A particularly fruitful line of work has been the development of methods that minimize the maximal of reprojection errors (L∞ norm) across observations, instead of the sum of squared reprojection errors. [sent-21, score-0.172]
14 It has been proven that many multiview problems have a single local optimum under the framework of L∞ norm. [sent-22, score-0.263]
15 The existence of globally optimal solution enables it ef- fective to use convex optimization in parameter estimation [11]. [sent-23, score-0.082]
16 However, this kind of algorithm is too complicated to solve large-scale geometric problems efficiently. [sent-24, score-0.076]
17 Recently, researchers proposed a new strategy, that by giving a simple sufficient condition for global optimality that can be used to verify that a solution obtained from any local methods is indeed global [15] [17]. [sent-25, score-0.153]
18 This algorithm returns either a certificate of optimality for local solution or global solution. [sent-26, score-0.103]
19 [5] found the sequence of convex problems are highly related and proposed a method to derive a Newton-like step from any given point. [sent-30, score-0.073]
20 All of the above mentioned algorithms are still on the ways of traditional optimization, and fewer modern optimization methods are considered to solve these problems so far. [sent-32, score-0.091]
21 In recent years, Tabu search (TS), a meta-heuristic optimization method originally proposed by Glover [6][7], has extensively attracted attentions of researchers. [sent-33, score-0.064]
22 It enhances the performance of a local search method by using memory structures that describe the visited solutions: once a potential solution has been determined, it is marked as ‘tabu’ so that the algorithm does not visit that possibility repeatedly. [sent-34, score-0.072]
23 However, the basic TS is proposed for combinatorial optimization problems primitively. [sent-35, score-0.068]
24 [4] proposed a variant ofTS for the global continuous optimization problems (GCOPs), called enhanced continuous tabu search 33223403 (ECTS). [sent-37, score-0.651]
25 This scheme divides the optimization process into two sequential phases, namely diversification and intensification. [sent-38, score-0.233]
26 In this paper, we proposed a novel method under the ECTS framework for parameter estimation in multiview geometry. [sent-40, score-0.137]
27 The procedure takes the result of linear method as initial estimation, and utilizes the ECTS to attain the global optimum. [sent-41, score-0.082]
28 In the phase of diversification, we propose a non-iterative way to obtain an initial bounding convex hull that contains the global optimum. [sent-42, score-0.126]
29 At the stage of intensification, we propose a new approach to attain the best neighbor set according to the characteristics of multiview geometric problems. [sent-43, score-0.2]
30 Finally, we prove the convergence of ECTS method in multiview geometry from the viewpoint of probability. [sent-44, score-0.201]
31 For the reason, we can prove that the proposed ECTS method converges with probability one to the global optimum. [sent-46, score-0.12]
32 Problem formulation The geometric vision problems we are considering in this paper are the ones where the reprojection error can be written as affine functions composed with a projection, i. [sent-49, score-0.162]
33 These problems can be represented as (P0) based on the squared reprojection error, minf(x) = ? [sent-52, score-0.131]
34 x +b˜i> 0 (P0) where x ∈ Rn is the unknowns to be solved for, and aij , bi ∈ Rn and aij , ∈ R are differentiated with geometric problems. [sent-60, score-0.162]
35 In order to facilitate the following discussions, here, we take the N-view triangulation as an example. [sent-65, score-0.118]
36 x + b˜i > 0 where x, aij , bi ∈ Rn and aij , b˜i ∈ R and abiij== p pi3ij,−b˜i= uij ˜ppii3,3i,˜ a =ij 1=,2 p˜ ,i. [sent-86, score-0.131]
37 ECTS in multiview geometry ECTS is a variant of traditional tabu search for the global continuous optimization [6]. [sent-90, score-0.75]
38 It is consisted of five stages, including setting of parameters, diversification, search for the most promising area, intensification, and output of the best point found. [sent-91, score-0.095]
39 The key stages of ECTS are diversification and intensification. [sent-92, score-0.21]
40 At the stage of diversification, the algorithm scans the whole solution space and detects the promising areas, which are likely to contain the global minimum. [sent-93, score-0.135]
41 The centers of these promising areas are stored in a so-called promising list. [sent-94, score-0.108]
42 The aim of diversification is to determine the most promising area from the promising list. [sent-95, score-0.34]
43 When the diversification ends, the step of intensification will start. [sent-96, score-0.297]
44 It searches inside the most promising area for a more optimal result. [sent-97, score-0.076]
45 In this phase, the search is concentrated on the most promising area by making the search domain smaller and gradually reducing the neighborhood structure. [sent-98, score-0.158]
46 This strategy improves the performance of the algorithm and allows exploiting the most promising area with more accuracy. [sent-99, score-0.076]
47 The diversification Now, we present how to carry out the diversification for multiview geometry problems. [sent-102, score-0.597]
48 In order to facilitate discussion, we also take the triangulation as the example. [sent-103, score-0.118]
49 At first, we show the way how to determine the most promising area, which should contain the global optimum xopt. [sent-104, score-0.185]
50 We start with a convex hull and an initial point xinit found by linear algebraic method. [sent-105, score-0.159]
51 If xopt is the true global optimum of L2 norm minimization, it follows N E(xopt) = min? [sent-106, score-0.27]
52 We wish to obtain a convex hull containing the optimal xopt. [sent-144, score-0.076]
53 )x + ai2 (6) ≤ 0 This process then provides an initial bounding convex hull that contains the global optimum xopt based on the L2 norm cost function. [sent-161, score-0.346]
54 Compared to traditional diversification methods, the above mentioned way does not need iterative process for the most promising area, so it is effective to solve multiview geometry problems. [sent-162, score-0.464]
55 The intensification In the classical ECTS, the intensification carries out the following routines: generation ofneighbors, selection ofthe best neighbor, updating of the various lists and adjustment of the parameters. [sent-165, score-0.206]
56 In other words, if the current solution converges in the local optimum, we must give the feasible direction to enable the solution escaping from the local one. [sent-166, score-0.092]
57 In this paper, we propose a new approach to attain the best neighbor set according to the characteristics of multiview geometry problems. [sent-169, score-0.209]
58 In the proposed method, we take the gradient of fi(xk) (k is the iteration of ECTS) as the descent direction and construct the candidate solution set. [sent-186, score-0.057]
59 The Lemma 1ensures that the candidate solution set includes the solution trailing offthe error, so the better solution could be obtained through the ECTS. [sent-195, score-0.119]
60 Since pseudo-convex is the sufficient and necessary condition for a global optimum in Lemma 1, each iteration ensures the solution toward to the global optimum. [sent-196, score-0.212]
61 In a word, in our proposed approach, we can construct the most promising area from L2 based basic method for the diversification and determine the best search direction from L∞ based optimality conditions for the intensification. [sent-197, score-0.349]
62 2, the problem (P1) is a global continuous optimization problem. [sent-202, score-0.107]
63 Essentially, the proposed method is an instance of the memory tabu search (MTS) [10]. [sent-207, score-0.443]
64 Otherwise, if f(y) ≤ f(xk), then xk+1 = y, else if y does not satisfy the tabu conditions, then xk+1 = y, else xk+1 = xk. [sent-214, score-0.478]
65 We say that {ξm} converges in probability towards a random variable if∀? [sent-219, score-0.07]
66 We say that {ξm} converges with probability one (or almost surely) towards a random variable ξ (denoted as ξm −a→. [sent-224, score-0.07]
67 he Lemma 2 and Theorem 2 give the global convergence property of the objective optimal value sequence induced by MTS, as described in solving problem (P2). [sent-242, score-0.074]
68 Let the probability of xk∗+1 ∈ D1 be qk+1 and the probability of xk∗+1 ∈ Do be pk+1 . [sent-249, score-0.08]
69 Namely xk∗ converges with probability one to the global optimal solution of (P2). [sent-259, score-0.151]
70 In Theorem 2, f∗ is the a global optimum of f and y is the candidate solution in each step of tabu search. [sent-261, score-0.59]
71 For the reason, we can predicate that the proposed ECTS converges in probability one to the global optimum. [sent-264, score-0.12]
72 The algorithm Now we summarize our framework of ECTS for estimating parameters in multiview geometry. [sent-266, score-0.137]
73 Input: 2D point ui in the image and camera matrix Pi, the step size of tabu search is t = 10−4, the tolerance is ? [sent-267, score-0.467]
74 Construct the convex hull which contains the global optimization xopt, as mentioned in the section 3. [sent-274, score-0.149]
75 zj, the element of z, satisfies the Gaussian distribution with mean xkj and standard deviation σ. [sent-288, score-0.069]
76 If z ∈ Ω and it is not in the tabu list, we put z in the candidate set S. [sent-291, score-0.428]
77 Otherwise, if maxfi (y) ≤ maxfi (xk) or y is i i not in the tabu list, then xk+1 = y, else xk∗+1 = xk. [sent-299, score-0.544]
78 It is worthy noted that, in the step 1, if the initial point is an unreliable algebraic result or a random initial value, the iteration of Tabu search will increase accordingly. [sent-309, score-0.072]
79 At the first stage of evaluation, we compared our method with bisection algorithm (Bisect-I) [11] to verify the effectiveness and efficiency for moderate scale problems, taking the triangulation and resection as examples. [sent-313, score-0.274]
80 The reported runtimes are the total time spent in optimization routines and the time of setting up the problem is omitted. [sent-322, score-0.105]
81 For the moderate scale problems we tested the algorithms on randomly generated instances of triangulation and resection problems with different sizes. [sent-344, score-0.337]
82 In Figures 1 and 2, the RMS (Root Mean Squares) errors of tri- angulation and resection problems with different sizes are reported. [sent-348, score-0.174]
83 have pointed out that the improved bisection algorithm based on the L∞ norm can obtain the global optimum [12]. [sent-351, score-0.23]
84 Apart from the expected global optimum being achieved by the ECTS algorithm, Table 1 and 2 clearly show that the ECTS algorithm is more efficient than Bisect-I algorithm. [sent-352, score-0.131]
85 The time cost of the triangulation on synthetic data shows that the speedup of our ECTS method decreases when the number of views increases. [sent-353, score-0.205]
86 We have also validated algorithms on different Gaussian noise level for the triangulation and resection. [sent-356, score-0.147]
87 Resection As far as to the resection issue, we chose four public available benchmarks from VGG data sets. [sent-410, score-0.129]
88 The details of average reprojection error and computational cost can be found in Table 4. [sent-411, score-0.086]
89 Since our ECTS algo- rithm focuses on L2 norm reprojection error, we compare it with Bisect-II, Dinkel-II, and Gugat algorithms discussed in [1] (the source code is provided by the author). [sent-435, score-0.132]
90 In [1], the author pointed out that Gugat’s algorithm is the best one comparing to others. [sent-436, score-0.06]
91 The RMS error of our algorithm based on L2 norm reprojection is 0. [sent-470, score-0.132]
92 This has proven that the proposed ECTS algorithm is suitable to large scale multiview geometric problems. [sent-475, score-0.168]
93 But traditional Tabu search applicable to SfM is only O(N2) in each iteration [18]. [sent-480, score-0.064]
94 We have validated the ECTS method for multiview geometric problems on both synthetic and real scene data, including triangulation, resection and N-view based structure and motion recovery. [sent-498, score-0.408]
95 Therefore, the proposed method can be extended to many problems of parameter estimation in multiview geometry. [sent-502, score-0.182]
96 A novel fast method for l∞ problems in multiview geometry. [sent-539, score-0.182]
97 An efficient implementation of the robust tabu search heuristic for sparse quadratic assignment problems. [sent-607, score-0.443]
98 Proof of Lemma 2 Proof: Let xmin be a global optimal solution of (P2). [sent-627, score-0.127]
99 probability density function g = the acceptance probability is Thus, A =? [sent-639, score-0.08]
100 μ1{Ω − ∪kk−L(S1∩ S2∪ S3)}/μ{Ω} f ( y ) ≤ > f ( x k ) , where S1, S2 and S3 are three criteria used to determine whether the candidate solution is tabu or not, S1 = {y ∈ Ω | ? [sent-640, score-0.459]
wordName wordTfidf (topN-words)
[('ects', 0.62), ('tabu', 0.402), ('xk', 0.299), ('diversification', 0.21), ('dinosaur', 0.139), ('multiview', 0.137), ('resection', 0.129), ('triangulation', 0.118), ('qk', 0.108), ('lemma', 0.097), ('gugat', 0.093), ('xopt', 0.093), ('intensification', 0.087), ('reprojection', 0.086), ('optimum', 0.081), ('pr', 0.078), ('fi', 0.074), ('mts', 0.072), ('ectsspeedup', 0.07), ('ingo', 0.07), ('rms', 0.062), ('oxford', 0.06), ('bi', 0.055), ('promising', 0.054), ('theorem', 0.054), ('maxfi', 0.052), ('miaxfi', 0.052), ('wadham', 0.052), ('xinit', 0.052), ('xjmax', 0.052), ('xjmin', 0.052), ('runtimes', 0.051), ('global', 0.05), ('speedup', 0.05), ('dame', 0.049), ('notre', 0.049), ('pk', 0.049), ('agarwal', 0.049), ('hull', 0.048), ('minf', 0.046), ('xkj', 0.046), ('vgg', 0.046), ('abi', 0.046), ('xmin', 0.046), ('norm', 0.046), ('problems', 0.045), ('ba', 0.041), ('search', 0.041), ('geometry', 0.04), ('probability', 0.04), ('else', 0.038), ('aij', 0.038), ('synthetic', 0.037), ('sfm', 0.035), ('elsc', 0.035), ('fther', 0.035), ('gcops', 0.035), ('oisel', 0.035), ('opuixre', 0.035), ('orsa', 0.035), ('quasiconvex', 0.035), ('sedumi', 0.035), ('kahl', 0.035), ('olsson', 0.035), ('continuous', 0.034), ('author', 0.034), ('adjustment', 0.032), ('attain', 0.032), ('geometric', 0.031), ('algebraic', 0.031), ('routines', 0.031), ('solution', 0.031), ('converges', 0.03), ('validated', 0.029), ('dino', 0.029), ('convex', 0.028), ('yj', 0.028), ('operational', 0.027), ('bisection', 0.027), ('candidate', 0.026), ('snavely', 0.026), ('pointed', 0.026), ('bundle', 0.025), ('tracks', 0.025), ('proof', 0.025), ('vanish', 0.025), ('ui', 0.024), ('ak', 0.024), ('convergence', 0.024), ('traditional', 0.023), ('house', 0.023), ('satisfies', 0.023), ('optimization', 0.023), ('area', 0.022), ('zs', 0.022), ('proofs', 0.022), ('lesser', 0.022), ('hartley', 0.022), ('enhanced', 0.022), ('optimality', 0.022)]
simIndex simValue paperId paperTitle
same-paper 1 1.0 141 iccv-2013-Enhanced Continuous Tabu Search for Parameter Estimation in Multiview Geometry
Author: Guoqing Zhou, Qing Wang
Abstract: Optimization using the L∞ norm has been becoming an effective way to solve parameter estimation problems in multiview geometry. But the computational cost increases rapidly with the size of measurement data. Although some strategies have been presented to improve the efficiency of L∞ optimization, it is still an open issue. In the paper, we propose a novel approach under theframework ofenhanced continuous tabu search (ECTS) for generic parameter estimation in multiview geometry. ECTS is an optimization method in the domain of artificial intelligence, which has an interesting ability of covering a wide solution space by promoting the search far away from current solution and consecutively decreasing the possibility of trapping in the local minima. Taking the triangulation as an example, we propose the corresponding ways in the key steps of ECTS, diversification and intensification. We also present theoretical proof to guarantee the global convergence of search with probability one. Experimental results have validated that the ECTS based approach can obtain global optimum efficiently, especially for large scale dimension of parameter. Potentially, the novel ECTS based algorithm can be applied in many applications of multiview geometry.
2 0.061681103 292 iccv-2013-Non-convex P-Norm Projection for Robust Sparsity
Author: Mithun Das Gupta, Sanjeev Kumar
Abstract: In this paper, we investigate the properties of Lp norm (p ≤ 1) within a projection framework. We start with the (KpK T≤ equations of the neoctni-olnin efraarm optimization problem a thnde then use its key properties to arrive at an algorithm for Lp norm projection on the non-negative simplex. We compare with L1projection which needs prior knowledge of the true norm, as well as hard thresholding based sparsificationproposed in recent compressed sensing literature. We show performance improvements compared to these techniques across different vision applications.
3 0.060657009 17 iccv-2013-A Global Linear Method for Camera Pose Registration
Author: Nianjuan Jiang, Zhaopeng Cui, Ping Tan
Abstract: We present a linear method for global camera pose registration from pairwise relative poses encoded in essential matrices. Our method minimizes an approximate geometric error to enforce the triangular relationship in camera triplets. This formulation does not suffer from the typical ‘unbalanced scale ’ problem in linear methods relying on pairwise translation direction constraints, i.e. an algebraic error; nor the system degeneracy from collinear motion. In the case of three cameras, our method provides a good linear approximation of the trifocal tensor. It can be directly scaled up to register multiple cameras. The results obtained are accurate for point triangulation and can serve as a good initialization for final bundle adjustment. We evaluate the algorithm performance with different types of data and demonstrate its effectiveness. Our system produces good accuracy, robustness, and outperforms some well-known systems on efficiency.
4 0.060504448 402 iccv-2013-Street View Motion-from-Structure-from-Motion
Author: Bryan Klingner, David Martin, James Roseborough
Abstract: We describe a structure-from-motion framework that handles “generalized” cameras, such as moving rollingshutter cameras, and works at an unprecedented scale— billions of images covering millions of linear kilometers of roads—by exploiting a good relative pose prior along vehicle paths. We exhibit a planet-scale, appearanceaugmented point cloud constructed with our framework and demonstrate its practical use in correcting the pose of a street-level image collection.
5 0.056595307 80 iccv-2013-Collaborative Active Learning of a Kernel Machine Ensemble for Recognition
Author: Gang Hua, Chengjiang Long, Ming Yang, Yan Gao
Abstract: Active learning is an effective way of engaging users to interactively train models for visual recognition. The vast majority of previous works, if not all of them, focused on active learning with a single human oracle. The problem of active learning with multiple oracles in a collaborative setting has not been well explored. Moreover, most of the previous works assume that the labels provided by the human oracles are noise free, which may often be violated in reality. We present a collaborative computational model for active learning with multiple human oracles. It leads to not only an ensemble kernel machine that is robust to label noises, but also a principled label quality measure to online detect irresponsible labelers. Instead of running independent active learning processes for each individual human oracle, our model captures the inherent correlations among the labelers through shared data among them. Our simulation experiments and experiments with real crowd-sourced noisy labels demonstrated the efficacy of our model.
6 0.055214357 184 iccv-2013-Global Fusion of Relative Motions for Robust, Accurate and Scalable Structure from Motion
7 0.053434134 111 iccv-2013-Detecting Dynamic Objects with Multi-view Background Subtraction
8 0.051793594 252 iccv-2013-Line Assisted Light Field Triangulation and Stereo Matching
9 0.051056869 45 iccv-2013-Affine-Constrained Group Sparse Coding and Its Application to Image-Based Classifications
10 0.050099183 367 iccv-2013-SUN3D: A Database of Big Spaces Reconstructed Using SfM and Object Labels
11 0.048891101 115 iccv-2013-Direct Optimization of Frame-to-Frame Rotation
12 0.048865627 27 iccv-2013-A Robust Analytical Solution to Isometric Shape-from-Template with Focal Length Calibration
13 0.043879967 353 iccv-2013-Revisiting the PnP Problem: A Fast, General and Optimal Solution
14 0.042568631 323 iccv-2013-Pose Estimation with Unknown Focal Length Using Points, Directions and Lines
15 0.041739974 140 iccv-2013-Elastic Net Constraints for Shape Matching
16 0.040715598 62 iccv-2013-Bird Part Localization Using Exemplar-Based Models with Enforced Pose and Subcategory Consistency
17 0.039096385 273 iccv-2013-Monocular Image 3D Human Pose Estimation under Self-Occlusion
18 0.038858924 196 iccv-2013-Hierarchical Data-Driven Descent for Efficient Optimal Deformation Estimation
19 0.038625155 434 iccv-2013-Unifying Nuclear Norm and Bilinear Factorization Approaches for Low-Rank Matrix Decomposition
20 0.037892412 138 iccv-2013-Efficient and Robust Large-Scale Rotation Averaging
topicId topicWeight
[(0, 0.1), (1, -0.038), (2, -0.032), (3, -0.013), (4, -0.019), (5, 0.024), (6, 0.011), (7, -0.021), (8, 0.006), (9, -0.013), (10, 0.003), (11, -0.008), (12, -0.054), (13, 0.008), (14, 0.011), (15, 0.04), (16, 0.02), (17, 0.032), (18, 0.007), (19, 0.008), (20, 0.027), (21, -0.054), (22, -0.054), (23, -0.023), (24, 0.021), (25, 0.003), (26, 0.052), (27, -0.007), (28, 0.016), (29, -0.004), (30, 0.003), (31, 0.009), (32, -0.001), (33, -0.021), (34, -0.003), (35, 0.009), (36, 0.033), (37, 0.007), (38, -0.023), (39, 0.038), (40, -0.019), (41, -0.018), (42, 0.02), (43, -0.013), (44, -0.058), (45, -0.001), (46, -0.024), (47, -0.005), (48, -0.007), (49, -0.011)]
simIndex simValue paperId paperTitle
same-paper 1 0.89738595 141 iccv-2013-Enhanced Continuous Tabu Search for Parameter Estimation in Multiview Geometry
Author: Guoqing Zhou, Qing Wang
Abstract: Optimization using the L∞ norm has been becoming an effective way to solve parameter estimation problems in multiview geometry. But the computational cost increases rapidly with the size of measurement data. Although some strategies have been presented to improve the efficiency of L∞ optimization, it is still an open issue. In the paper, we propose a novel approach under theframework ofenhanced continuous tabu search (ECTS) for generic parameter estimation in multiview geometry. ECTS is an optimization method in the domain of artificial intelligence, which has an interesting ability of covering a wide solution space by promoting the search far away from current solution and consecutively decreasing the possibility of trapping in the local minima. Taking the triangulation as an example, we propose the corresponding ways in the key steps of ECTS, diversification and intensification. We also present theoretical proof to guarantee the global convergence of search with probability one. Experimental results have validated that the ECTS based approach can obtain global optimum efficiently, especially for large scale dimension of parameter. Potentially, the novel ECTS based algorithm can be applied in many applications of multiview geometry.
2 0.77881485 353 iccv-2013-Revisiting the PnP Problem: A Fast, General and Optimal Solution
Author: Yinqiang Zheng, Yubin Kuang, Shigeki Sugimoto, Kalle Åström, Masatoshi Okutomi
Abstract: In this paper, we revisit the classical perspective-n-point (PnP) problem, and propose the first non-iterative O(n) solution that is fast, generally applicable and globally optimal. Our basic idea is to formulate the PnP problem into a functional minimization problem and retrieve all its stationary points by using the Gr¨ obner basis technique. The novelty lies in a non-unit quaternion representation to parameterize the rotation and a simple but elegant formulation of the PnP problem into an unconstrained optimization problem. Interestingly, the polynomial system arising from its first-order optimality condition assumes two-fold symmetry, a nice property that can be utilized to improve speed and numerical stability of a Gr¨ obner basis solver. Experiment results have demonstrated that, in terms of accuracy, our proposed solution is definitely better than the state-ofthe-art O(n) methods, and even comparable with the reprojection error minimization method.
3 0.76466614 115 iccv-2013-Direct Optimization of Frame-to-Frame Rotation
Author: Laurent Kneip, Simon Lynen
Abstract: This work makes use of a novel, recently proposed epipolar constraint for computing the relative pose between two calibrated images. By enforcing the coplanarity of epipolar plane normal vectors, it constrains the three degrees of freedom of the relative rotation between two camera views directly—independently of the translation. The present paper shows how the approach can be extended to n points, and translated into an efficient eigenvalue minimization over the three rotational degrees of freedom. Each iteration in the non-linear optimization has constant execution time, independently of the number of features. Two global optimization approaches are proposed. The first one consists of an efficient Levenberg-Marquardt scheme with randomized initial value, which already leads to stable and accurate results. The second scheme consists of a globally optimal branch-and-bound algorithm based on a bound on the eigenvalue variation derived from symmetric eigenvalue-perturbation theory. Analysis of the cost function reveals insights into the nature of a specific relative pose problem, and outlines the complexity under different conditions. The algorithm shows state-of-the-art performance w.r.t. essential-matrix based solutions, and a frameto-frame application to a video sequence immediately leads to an alternative, real-time visual odometry solution. Note: All algorithms in this paper are made available in the OpenGV library. Please visit http : / / l aurent kne ip .github . i / opengv o
4 0.73569381 138 iccv-2013-Efficient and Robust Large-Scale Rotation Averaging
Author: Avishek Chatterjee, Venu Madhav Govindu
Abstract: In this paper we address the problem of robust and efficient averaging of relative 3D rotations. Apart from having an interesting geometric structure, robust rotation averaging addresses the need for a good initialization for largescale optimization used in structure-from-motion pipelines. Such pipelines often use unstructured image datasets harvested from the internet thereby requiring an initialization method that is robust to outliers. Our approach works on the Lie group structure of 3D rotations and solves the problem of large-scale robust rotation averaging in two ways. Firstly, we use modern ?1 optimizers to carry out robust averaging of relative rotations that is efficient, scalable and robust to outliers. In addition, we also develop a twostep method that uses the ?1 solution as an initialisation for an iteratively reweighted least squares (IRLS) approach. These methods achieve excellent results on large-scale, real world datasets and significantly outperform existing methods, i.e. the state-of-the-art discrete-continuous optimization method of [3] as well as the Weiszfeld method of [8]. We demonstrate the efficacy of our method on two large- scale real world datasets and also provide the results of the two aforementioned methods for comparison.
5 0.73068213 184 iccv-2013-Global Fusion of Relative Motions for Robust, Accurate and Scalable Structure from Motion
Author: Pierre Moulon, Pascal Monasse, Renaud Marlet
Abstract: Multi-view structure from motion (SfM) estimates the position and orientation of pictures in a common 3D coordinate frame. When views are treated incrementally, this external calibration can be subject to drift, contrary to global methods that distribute residual errors evenly. We propose a new global calibration approach based on the fusion of relative motions between image pairs. We improve an existing method for robustly computing global rotations. We present an efficient a contrario trifocal tensor estimation method, from which stable and precise translation directions can be extracted. We also define an efficient translation registration method that recovers accurate camera positions. These components are combined into an original SfM pipeline. Our experiments show that, on most datasets, it outperforms in accuracy other existing incremental and global pipelines. It also achieves strikingly good running times: it is about 20 times faster than the other global method we could compare to, and as fast as the best incremental method. More importantly, it features better scalability properties.
7 0.70532674 17 iccv-2013-A Global Linear Method for Camera Pose Registration
8 0.69509143 323 iccv-2013-Pose Estimation with Unknown Focal Length Using Points, Directions and Lines
9 0.68349385 342 iccv-2013-Real-Time Solution to the Absolute Pose Problem with Unknown Radial Distortion and Focal Length
10 0.67517126 280 iccv-2013-Multi-view 3D Reconstruction from Uncalibrated Radially-Symmetric Cameras
11 0.64141738 55 iccv-2013-Automatic Kronecker Product Model Based Detection of Repeated Patterns in 2D Urban Images
12 0.63828033 152 iccv-2013-Extrinsic Camera Calibration without a Direct View Using Spherical Mirror
13 0.62936354 292 iccv-2013-Non-convex P-Norm Projection for Robust Sparsity
14 0.62547833 27 iccv-2013-A Robust Analytical Solution to Isometric Shape-from-Template with Focal Length Calibration
15 0.59774989 140 iccv-2013-Elastic Net Constraints for Shape Matching
16 0.59106421 60 iccv-2013-Bayesian Robust Matrix Factorization for Image and Video Processing
17 0.59052116 436 iccv-2013-Unsupervised Intrinsic Calibration from a Single Frame Using a "Plumb-Line" Approach
18 0.56792313 407 iccv-2013-Subpixel Scanning Invariant to Indirect Lighting Using Quadratic Code Length
19 0.55809432 167 iccv-2013-Finding Causal Interactions in Video Sequences
20 0.5543831 90 iccv-2013-Content-Aware Rotation
topicId topicWeight
[(2, 0.048), (3, 0.164), (7, 0.021), (13, 0.017), (26, 0.054), (27, 0.024), (31, 0.04), (34, 0.018), (42, 0.116), (64, 0.03), (73, 0.035), (77, 0.123), (89, 0.14), (95, 0.022), (98, 0.053)]
simIndex simValue paperId paperTitle
same-paper 1 0.79528505 141 iccv-2013-Enhanced Continuous Tabu Search for Parameter Estimation in Multiview Geometry
Author: Guoqing Zhou, Qing Wang
Abstract: Optimization using the L∞ norm has been becoming an effective way to solve parameter estimation problems in multiview geometry. But the computational cost increases rapidly with the size of measurement data. Although some strategies have been presented to improve the efficiency of L∞ optimization, it is still an open issue. In the paper, we propose a novel approach under theframework ofenhanced continuous tabu search (ECTS) for generic parameter estimation in multiview geometry. ECTS is an optimization method in the domain of artificial intelligence, which has an interesting ability of covering a wide solution space by promoting the search far away from current solution and consecutively decreasing the possibility of trapping in the local minima. Taking the triangulation as an example, we propose the corresponding ways in the key steps of ECTS, diversification and intensification. We also present theoretical proof to guarantee the global convergence of search with probability one. Experimental results have validated that the ECTS based approach can obtain global optimum efficiently, especially for large scale dimension of parameter. Potentially, the novel ECTS based algorithm can be applied in many applications of multiview geometry.
2 0.75297558 350 iccv-2013-Relative Attributes for Large-Scale Abandoned Object Detection
Author: Quanfu Fan, Prasad Gabbur, Sharath Pankanti
Abstract: Effective reduction of false alarms in large-scale video surveillance is rather challenging, especially for applications where abnormal events of interest rarely occur, such as abandoned object detection. We develop an approach to prioritize alerts by ranking them, and demonstrate its great effectiveness in reducing false positives while keeping good detection accuracy. Our approach benefits from a novel representation of abandoned object alerts by relative attributes, namely staticness, foregroundness and abandonment. The relative strengths of these attributes are quantified using a ranking function[19] learnt on suitably designed low-level spatial and temporal features.These attributes of varying strengths are not only powerful in distinguishing abandoned objects from false alarms such as people and light artifacts, but also computationally efficient for large-scale deployment. With these features, we apply a linear ranking algorithm to sort alerts according to their relevance to the end-user. We test the effectiveness of our approach on both public data sets and large ones collected from the real world.
3 0.74340004 181 iccv-2013-Frustratingly Easy NBNN Domain Adaptation
Author: Tatiana Tommasi, Barbara Caputo
Abstract: Over the last years, several authors have signaled that state of the art categorization methods fail to perform well when trained and tested on data from different databases. The general consensus in the literature is that this issue, known as domain adaptation and/or dataset bias, is due to a distribution mismatch between data collections. Methods addressing it go from max-margin classifiers to learning how to modify the features and obtain a more robust representation. The large majority of these works use BOW feature descriptors, and learning methods based on imageto-image distance functions. Following the seminal work of [6], in this paper we challenge these two assumptions. We experimentally show that using the NBNN classifier over existing domain adaptation databases achieves always very strong performances. We build on this result, and present an NBNN-based domain adaptation algorithm that learns iteratively a class metric while inducing, for each sample, a large margin separation among classes. To the best of our knowledge, this is the first work casting the domain adaptation problem within the NBNN framework. Experiments show that our method achieves the state of the art, both in the unsupervised and semi-supervised settings.
4 0.74012923 365 iccv-2013-SIFTpack: A Compact Representation for Efficient SIFT Matching
Author: Alexandra Gilinsky, Lihi Zelnik Manor
Abstract: Computing distances between large sets of SIFT descriptors is a basic step in numerous algorithms in computer vision. When the number of descriptors is large, as is often the case, computing these distances can be extremely time consuming. In this paper we propose the SIFTpack: a compact way of storing SIFT descriptors, which enables significantly faster calculations between sets of SIFTs than the current solutions. SIFTpack can be used to represent SIFTs densely extracted from a single image or sparsely from multiple different images. We show that the SIFTpack representation saves both storage space and run time, for both finding nearest neighbors and for computing all distances between all descriptors. The usefulness of SIFTpack is also demonstrated as an alternative implementation for K-means dictionaries of visual words.
5 0.73269141 286 iccv-2013-NYC3DCars: A Dataset of 3D Vehicles in Geographic Context
Author: Kevin Matzen, Noah Snavely
Abstract: Geometry and geography can play an important role in recognition tasks in computer vision. To aid in studying connections between geometry and recognition, we introduce NYC3DCars, a rich dataset for vehicle detection in urban scenes built from Internet photos drawn from the wild, focused on densely trafficked areas of New York City. Our dataset is augmented with detailed geometric and geographic information, including full camera poses derived from structure from motion, 3D vehicle annotations, and geographic information from open resources, including road segmentations and directions of travel. NYC3DCars can be used to study new questions about using geometric information in detection tasks, and to explore applications of Internet photos in understanding cities. To demonstrate the utility of our data, we evaluate the use of the geographic information in our dataset to enhance a parts-based detection method, and suggest other avenues for future exploration.
6 0.73160636 142 iccv-2013-Ensemble Projection for Semi-supervised Image Classification
7 0.72830558 26 iccv-2013-A Practical Transfer Learning Algorithm for Face Verification
8 0.71909994 180 iccv-2013-From Where and How to What We See
9 0.71905667 250 iccv-2013-Lifting 3D Manhattan Lines from a Single Image
10 0.71389127 83 iccv-2013-Complementary Projection Hashing
11 0.70745814 427 iccv-2013-Transfer Feature Learning with Joint Distribution Adaptation
12 0.69862467 434 iccv-2013-Unifying Nuclear Norm and Bilinear Factorization Approaches for Low-Rank Matrix Decomposition
13 0.69543839 123 iccv-2013-Domain Adaptive Classification
14 0.6939351 438 iccv-2013-Unsupervised Visual Domain Adaptation Using Subspace Alignment
15 0.69104552 435 iccv-2013-Unsupervised Domain Adaptation by Domain Invariant Projection
16 0.68991244 182 iccv-2013-GOSUS: Grassmannian Online Subspace Updates with Structured-Sparsity
17 0.68971974 328 iccv-2013-Probabilistic Elastic Part Model for Unsupervised Face Detector Adaptation
18 0.68942034 19 iccv-2013-A Learning-Based Approach to Reduce JPEG Artifacts in Image Matting
19 0.6887539 52 iccv-2013-Attribute Adaptation for Personalized Image Search
20 0.68853503 44 iccv-2013-Adapting Classification Cascades to New Domains