Predicting the future motion of traffic agents is crucial for safe and efficient autonomous driving. To this end, we present PredictionNet, a deep neural network (DNN) that predicts the motion of all surrounding traffic agents together with the ego-vehicle's motion. All predictions are probabilistic and are represented in a simple top-down rasterization that allows an arbitrary number of agents. Conditioned on a multi-layer map with lane information, the network outputs future positions, velocities, and backtrace vectors jointly for all agents including the ego-vehicle in a single pass. Trajectories are then extracted from the output. The network can be used to simulate realistic traffic, and it produces competitive results on popular benchmarks. More importantly, it has been used to successfully control a real-world vehicle for hundreds of kilometers, by combining it with a motion planning/control subsystem. The network runs faster than real-time on an embedded GPU, and the system shows good generalization (across sensory modalities and locations) due to the choice of input representation. Furthermore, we demonstrate that by extending the DNN with reinforcement learning (RL), it can better handle rare or unsafe events like aggressive maneuvers and crashes.

In this paper, we present results and experiments with several methods for bundle adjustment, producing the fastest bundle adjuster ever published in terms of computation and convergence. From a computational perspective, the fastest methods naturally handle the block-sparse pattern that arises in a reduced camera system. Adapting to the naturally arising block-sparsity allows the use of BLAS3, efficient memory handling, fast variable ordering, and customized sparse solving, all simultaneously. We present two methods; one uses exact minimum degree ordering and block-based LDL solving and the other uses block-based preconditioned conjugate gradients. Both methods are performed on the reduced camera system. We show experimentally that the adaptation to the natural block sparsity allows both of these methods to perform better than previous methods. Further improvements in convergence speed are achieved by the novel use of embedded point iterations. Embedded point iterations take place inside each camera update step, yielding a greater cost decrease from each camera update step and, consequently, a lower minimum. This is especially true for points projecting far out on the flatter region of the robustifier. Intensive analyses from various angles demonstrate the improved performance of the presented bundler.

In this paper, we present results and experiments with several methods for bundle adjustment, producing the fastest bundle adjuster ever published. The fastest methods work with the well known reduced camera system and handle the block-sparse pattern arising in the reduced camera system in a natural way. Adapting to the naturally arising block-sparsity allows the use of BLAS3, efficient memory handling, fast variable ordering, and customized sparse solving all at the same time. We present two methods, one using exact minimum degree ordering and block-based LDL solving, and one using block-based preconditioned conjugate gradient, both on the reduced camera system. We show experimentally that the adaptation to the natural block sparsity allows both these methods to perform better than previous ones. Further speed improvements are achieved by the novel use of embedded point iterations. The embedded point iterations take place inside each camera update step, yielding a higher cost decrease from each camera update step. This is especially true for points projecting far out on the flatter region of the robustifier.

In this paper, we formulate a stereo matching algorithm with careful handling of disparity, discontinuity and occlusion. The algorithm works with a global matching stereo model based on an energy-minimization framework. The global energy contains two terms, the data term and the smoothness term. The data term is first approximated by a color-weighted correlation, then refined in occluded and low-texture areas in a repeated application of a hierarchical loopy belief propagation algorithm. The experimental results are evaluated on the Middlebury data sets, showing that our algorithm is the top performer among all the algorithms listed there.

In this paper we present a novel approach to directly recover the location of both microphones and sound sources from time-difference-of-arrival measurements only. No approximation solution is required for initialization and in the absence of noise our approach is guaranteed to always recover the exact solution. Our approach only requires solving linear equations and matrix factorization. We demonstrate the feasibility of our approach with synthetic data.

This paper presents minimal solutions for the geometric parameters of a camera rotating about its optical centre. In particular we present new 2 and 3 point solutions for the homography induced by a rotation with 1 and 2 unknown focal length parameters. Using tests on real data, we show that these algorithms outperform the standard 4 point linear homography solution in terms of accuracy of focal length estimation and image based projection errors.

We present an autocalibration algorithm for upgrading a projective reconstruction to a metric reconstruction by estimating the absolute dual quadric. The algorithm enforces the rank degeneracy and the positive semidefiniteness of the dual quadric as part of the estimation procedure, rather than as a post-processing step. Furthermore, the method allows the user, if he or she so desires, to enforce conditions on the plane at infinity so that the reconstruction satisfies the chirality constraints. The algorithm works by constructing low degree polynomial optimization problems, which are solved to their global optimum using a series of convex linear matrix inequality relaxations. The algorithm is fast, stable, robust and has time complexity independent of the number of views. We show extensive results on synthetic as well as real datasets to validate our algorithm.

In this paper we investigate how to scale a content based image retrieval approach beyond the RAM limits of a single computer and to make use of its hard drive to store the feature database. The feature vectors describing the images in the database are binned in multiple independent ways. Each bin contains images similar to a representative prototype. Each binning is considered through two stages of processing. First, the prototype closest to the query is found. Second, the bin corresponding to the closest prototype is fetched from disk and searched completely. The query process is repeatedly performing these two stages, each time with a binning independent of the previous ones. The scheme cuts down the hard drive access significantly and results in a major speed up. An experimental comparison between the binning scheme and a raw search shows competitive retrieval quality.

This paper presents a general method, based on Galois theory, for establishing that a problem can not be solved by a 'machine' that is capable of the standard arithmetic operations, extraction of radicals (that is, m-th roots for any m), as well as extraction of roots of polynomials of degree smaller than n, but no other numerical operations. The method is applied to two well known structure from motion problems: five point calibrated relative orientation, which can be realized by solving a tenth degree polynomial [6], and L2-optimal two-view triangulation, which can be realized by solving a sixth degree polynomial [3]. It is shown that both these solutions are optimal in the sense that an exact solution intrinsically requires the solution of a polynomial of the given degree (10 or 6 respectively), and cannot be solved by extracting roots of polynomials of any lesser degree.

Given five motion vectors observed in a calibrated camera, what is the rotational and translational velocity of the camera? This problem is the infinitesimal motion analogue to the five-point relative orientation problem, which has previously been solved through the derivation of a tenth-degree polynomial and extraction of its roots. Here, we present the first efficient solution to the infinitesimal version of the problem. The solution is faster than its finite counterpart. In our experiments, we investigate over which range of motions and scene distances the infinitesimal approximation is valid and show that the infinitesimal approximation works well in applications such as camera tracking.

We present a new post-processing step to enhance the resolution of range images. Using one or two registered and potentially high-resolution color images as reference, we iteratively refine the input low-resolution range image, in terms of both its spatial resolution and depth precision. Evaluation using the Middlebury benchmark shows across-the-board improvement for sub-pixel accuracy. We also demonstrated its effectiveness for spatial resolution enhancement up to 100 times with a single reference image.

We present a viewpoint-based approach for the quick fusion of multiple stereo depth maps. Our method selects depth estimates for each pixel that minimize violations of visibility constraints and thus remove errors and inconsistencies from the depth maps to produce a consistent surface. We advocate a two-stage process in which the first stage generates potentially noisy, overlapping depth maps from a set of calibrated images and the second stage fuses these depth maps to obtain an integrated surface with higher accuracy, suppressed noise, and reduced redundancy. We show that by dividing the processing into two stages we are able to achieve a very high throughput because we are able to use a computationally cheap stereo algorithm and because this architecture is amenable to hardware-accelerated (GPU) implementations. A rigorous formulation based on the notion of stability of a depth estimate is presented first. It aims to determine the validity of a depth estimate by rendering multiple depth maps into the reference view as well as rendering the reference depth map into the other views in order to detect occlusions and free- space violations. We also present an approximate alternative formulation that selects and validates only one hypothesis based on confidence. Both formulations enable us to perform video-based reconstruction at up to 25 frames per second. We show results on the multi-view stereo evaluation benchmark datasets and several outdoors video sequences. Extensive quantitative analysis is performed using an accurately surveyed model of a real building as ground truth.

This paper shows that structure from motion is NP-hard for most sensible cost functions when missing data is allowed. The result provides a fundamental limitation of what is possible to achieve with any structure from motion algorithm. Even though there are recent, promising attempts to compute globally optimal solutions, there is no hope of obtaining a polynomial time algorithm unless P=NP. The proof proceeds by encoding an arbitrary Boolean formula as a structure from motion problem of polynomial size, such that the structure from motion problem has a zero cost solution if and only if the Boolean formula is satisfiable. Hence, if there was a guaranteed way to minimize the error of the relevant family of structure from motion problems in polynomial time, the NP-complete problem 3SAT could be solved in polynomial time, which would imply that P=NP The proof relies heavily on results from both structure from motion and complexity theory.

In this paper we present a highly scalable vision-based localization and mapping method using image collections. A topological world representation is created online during robot exploration by adding images to a database and maintaining a link graph. An efficient image matching scheme allows real-time mapping and global localization. The compact image representation allows us to create image collections containing millions of images, which enables mapping of very large environments. A path planning method using graph search is proposed and local geometric information is used to navigate in the topological map. Experiments show the good performance of the image matching for global localization and demonstrate path planning and navigation.

In this paper, we present a belief propagation based global algorithm that generates high quality results while maintaining real-time performance. To our knowledge, it is the first BP based global method that runs at real-time speed. Our efficiency performance gains mainly from the parallelism of graphics hardware,which leads to a 45 times speedup compared to the CPU implementation. To qualify the accurancy of our approach, the experimental results are evaluated on the Middlebury data sets, showing that our approach is among the best (ranked first in the new evaluation system) for all real-time approaches. In addition, since the running time of general BP is linear to the number of iterations, adopting a large number of iterations is not feasible for practical applications. Hence a novel approach is proposed to adaptively update pixel cost. Unlike general BP methods, the running time of our proposed algorithm dramatically converges.

We present an attempt to determine whether the shape of a generic central-projection camera, such as the eye of an insect or a log-polar camera, can be determined from two motion flows resulting from purely rotational motions with non-collinear axes. Our first contribution is to write the smooth non-parametric calibration problem as a differential equation. It is unclear at present whether this problem has unique solution, up to an orthogonal transformation. Our second contribution is a discretized version of this smooth problem, for which we give a calibration algorithm - a third contribution. Using this algorithm, we explore numerically the properties of the discrete self-calibration problem, giving some insight on the nature of the problem. We show examples of successful self-calibration, but cannot give a definite affirmative answer to the question in the title.

A recognition scheme that scales efficiently to a large number of objects is presented. The efficiency and quality is exhibited in a live demonstration that recognizes CD-covers from a database of 40000 images of popular music CD’s. The scheme builds upon popular techniques of indexing descriptors extracted from local regions, and is robust to background clutter and occlusion. The local region descriptors are hierarchically quantized in a vocabulary tree. The vocabulary tree allows a larger and more discriminatory vocabulary to be used efficiently, which we show experimentally leads to a dramatic improvement in retrieval quality. The most significant property of the scheme is that the tree directly defines the quantization. The quantization and the indexing are therefore fully integrated, essentially being one and the same. The recognition quality is evaluated through retrieval on a database with ground truth, showing the power of the vocabulary tree approach, going as high as 1 million images.

In this paper, we formulate an algorithm for the stereo matching problem with careful handling of disparity, discontinuity and occlusion. The algorithm works with a global matching stereo model based on an energy- minimization framework. The global energy contains two terms, the data term and the smoothness term. The data term is first approximated by a color-weighted correlation, then refined in occluded and low-texture areas in a repeated application of a hierarchical loopy belief propagation algorithm. The experimental results are evaluated on the Middlebury data set, showing that our algorithm is the top performer.

Assume that we have two perspective images with known intrinsic parameters except for an unknown common focal length. It is a minimally constrained problem to find the relative orientation between the two images given six corresponding points. We present an efficient solution to the problem and show that there are 15 solutions in general (including complex solutions). To the best of our knowledge this was a previously unsolved problem. The solutions are found through eigen-decomposition of a 15/spl times/15 matrix. The matrix itself is generated in closed form. We demonstrate through practical experiments that the algorithm is correct and numerically stable.

In this paper, we develop a theory of non-parametric self-calibration. Recently, schemes have been devised for non-parametric laboratory calibration, but not for self-calibration. We allow an arbitrary warp to model the intrinsic mapping, with the only restriction that the camera is central and that the intrinsic mapping has a well-defined non-singular matrix derivative at a finite number of points under study. We give a number of theoretical results, both for infinitesimal motion and finite motion, for a finite number of observations and when observing motion over a dense image, for rotation and translation. Our main result is that through observing the flow induced by three instantaneous rotations at a finite number of points of the distorted image, we can perform projective reconstruction of those image points on the undistorted image. We present some results with synthetic and real data.

We present a solution for optimal triangulation in three views. The solution is guaranteed to find the optimal solution because it computes all the stationary points of the (maximum likelihood) objective function. Internally, the solution is found by computing roots of multivariate polynomial equations, directly solving the conditions for stationarity. The solver makes use of standard methods from computational commutative algebra to convert the root-finding problem into a 47 /spl times/ 47 nonsymmetric eigenproblem. Although there are in general 47 roots, counting both real and complex ones, the number of real roots is usually much smaller. We also show experimentally that the number of stationary points that are local minima and lie in front of each camera is small but does depend on the scene geometry.

We present a quality assessment procedure for correspondence estimation based on geometric coherence rather than ground truth. The procedure can be used for performance evaluation of correspondence extraction schemes developed by researchers, as well as for online learning and adaptation aimed at better system performance. A very important aspect of the proposed procedure is that it considers uncertainty in the correspondence extraction, and encourages the evaluated methods to deal correctly with uncertainty. Other important strengths of the procedure are that it does not use any manual work, and that it does not put any strong constraints on the scene, but rather relies on geometric coherence in the motion. Thanks to these strengths, it can therefore be used with large amounts of real, potentially application specific data, or even data acquired during system operation. In the evaluation the correspondence extractor is handled as a black box producing a probability distribution for the local motion vector between a pair of image patches. The procedure is therefore quite general. We are making the evaluation procedure available for public use.

We propose a general framework for aligning continuous (oblique) video onto 3D sensor data. We align a point cloud computed from the video onto the point cloud directly obtained from a 3D sensor. This is in contrast to existing techniques where the 2D images are aligned to a 3D model derived from the 3D sensor data. Using point clouds enables the alignment for scenes full of objects that are difficult to model; for example, trees. To compute 3D point clouds from video, motion stereo is used along with a state-of-the-art algorithm for camera pose estimation. Our experiments with real data demonstrate the advantages of the proposed registration algorithm for texturing models in large-scale semiurban environments. The capability to align video before a 3D model is built from the 3D sensor data offers new practical opportunities for 3D modeling. We introduce a novel modeling-through-registration approach that fuses 3D information from both the 3D sensor and the video. Initial experiments with real data illustrate the potential of the proposed approach.

An efficient algorithmic solution to the classical five-point relative pose problem is presented. The problem is to find the possible solutions for relative camera pose between two calibrated views given five corresponding points. The algorithm consists of computing the coefficients of a tenth degree polynomial in closed form and, subsequently, finding its roots. It is the first algorithm well-suited for numerical implementation that also corresponds to the inherent complexity of the problem. We investigate the numerical precision of the algorithm. We also study its performance under noise in minimal as well as overdetermined cases. The performance is compared to that of the well-known 8 and 7-point methods and a 6-point scheme. The algorithm is used in a robust hypothesize-and-test framework to estimate structure and motion in real-time with low delay. The real-time system uses solely visual input and has been demonstrated at major conferences.

An efficient algorithmic solution to the classical five-point relative pose problem is presented. The problem is to find the possible solutions for relative camera motion between two calibrated views given five corresponding points. The algorithm consists of computing the coefficients of a tenth degree polynomial and subsequently finding its roots. It is the first algorithm well suited for numerical implementation that also corresponds to the inherent complexity of the problem. The algorithm is used in a robust hypothesis-and-test framework to estimate structure and motion in real-time.

A system capable of performing robust live ego-motion estimation for perspective cameras is presented. The system is powered by random sample consensus with preemptive scoring of the motion hypotheses. A general statement of the problem of efficient preemptive scoring is given. Then a theoretical investigation of preemptive scoring under a simple inlier-outlier model is performed. A practical preemption scheme is proposed and it is shown that the preemption is powerful enough to enable robust live structure and motion estimation.

A method for upgrading a projective reconstruction to metric is presented. The reconstruction is first transformed by considering cheirality so that the convex hull of the set of camera projection centres is the same as in the metric counterpart. The method then proceeds iteratively and starting from such a reconstruction is a necessary condition for many iterative calibration algorithms to converge. The results show that in practice it is also most often sufficient provided that the minimised objective function is a geometrically meaningful quantity. The method has been found extremely reliable for both large and small reconstructions in a large number of experiments on real data. When subjected to the common degeneracy of little or no rotation between the views, the method still yields a very reasonable member of the family of possible solutions. Furthermore, the method is very fast and therefore suitable for the purpose of viewing reconstructions.

An embedded DCT-based image coding algorithm is described. The decoder can cut the bitstream at any point and therefore reconstruct an image at lower rate. The quality of the reconstructed image at this lower rate would be the same as if the image was coded directly at that rate. The algorithm outperforms any other DCT-based coders published in the literature, including the JPEG algorithm. Moreover, our DCT-based embedded image coder gives results close to the best wavelet-based coders. The algorithm is very useful in various applications, like WWW, fast browsing of databases, etc.

An embedded discrete cosine transform-based (DCT-based) image coding algorithm is described. The algorithm outperforms other DCT-based coders published in the literature, including the Joint Photographers Expert Group (JPEG) algorithm.