The concept of viewing graph solvability has gained significant interest in the context of structure-from-motion. A viewing graph is a mathematical structure where nodes are associated with cameras and edges represent the epipolar geometry connecting overlapping views. Solvability studies under which conditions the cameras are uniquely determined by the graph. In this paper we propose a novel framework for analyzing solvability problems based on algebraic geometry, demonstrating its potential in understanding structure-from-motion graphs and proving a conjecture that was previously proposed.

In the structure from motion, the viewing graph is a graph where the vertices correspond to cameras (or images) and the edges represent the fundamental matrices. We provide a new formulation and an algorithm for determining whether a viewing graph is solvable, i.e., uniquely determines a set of projective cameras. The known theoretical conditions either do not fully characterize the solvability of all viewing graphs, or are extremely difficult to compute because they involve solving a system of polynomial equations with a large number of unknowns. The main result of this paper is a method to reduce the number of unknowns by exploiting cycle consistency. We advance the understanding of solvability by (i) finishing the classification of all minimal graphs up to 9 nodes, (ii) extending the practical verification of solvability to minimal graphs with up to 90 nodes, (iii) finally answering an open research question by showing that finite solvability is not equivalent to solvability, and (iv) formally drawing the connection with the calibrated case (i.e., parallel rigidity). Finally, we present an experiment on real data that shows that unsolvable graphs may appear in practice.

We present an advance in understanding the projective Structure-from-Motion, focusing in particular on the viewing graph: such a graph has cameras as nodes and fundamental matrices as edges. We propose a practical method for testing finite solvability, i.e., whether a viewing graph induces a finite number of camera configurations. Our formulation uses a significantly smaller number of equations (up to 400×) with respect to previous work. As a result, this is the only method in the literature that can be applied to large viewing graphs coming from real datasets, comprising up to 300K edges. In addition, we develop the first algorithm for identifying maximal finite-solvable components.

In this paper we address the rotation synchronization problem, where the objective is to recover absolute rotations starting from pairwise ones, where the unknowns and the measures are represented as nodes and edges of a graph, respectively. This problem is an essential task for structure from motion and simultaneous localization and mapping. We focus on the formulation of synchronization via neural networks, which has only recently begun to be explored in the literature. Inspired by deep matrix completion, we express rotation synchronization in terms of matrix factorization with a deep neural network. Our formulation exhibits implicit regularization properties and, more importantly, is unsupervised, whereas previous deep approaches are supervised. Our experiments show that we achieve comparable accuracy to the closest competitors in most scenes, while working under weaker assumptions.

In structure-from-motion the viewing graph is a graph where vertices correspond to cameras and edges represent fundamental matrices. We provide a new formulation and an algorithm for establishing whether a viewing graph is solvable, i.e. it uniquely determines a set of projective cameras. Known theoretical conditions either do not fully characterize the solvability of all viewing graphs, or are exceedingly hard to compute for they involve solving a system of polynomial equations with a large number of unknowns. The main result of this paper is a method for reducing the number of unknowns by exploiting the cycle consistency. We advance the understanding of the solvability by (i) finishing the classification of all previously undecided minimal graphs up to 9 nodes, (ii) extending the practical solvability testing up to minimal graphs with up to 90 nodes, and (iii) definitely answering an open research question by showing that the finite solvability is not equivalent to the solvability. Finally, we present an experiment on real data showing that unsolvable graphs are appearing in practical situations.

Synchronization refers to the problem of inferring the unknown values attached to vertices of a graph where edges are labelled with the ratio of the incident vertices, and labels belong to a group. This paper addresses the synchronization problem on multi-graphs, that are graphs with more than one edge connecting the same pair of nodes. The problem naturally arises when multiple measures are available to model the relationship between two vertices. This happens when different sensors measure the same quantity, or when the original graph is partitioned into sub-graphs that are solved independently. In this case, the relationships among sub-graphs give rise to multi-edges and the problem can be traced back to a multi-graph synchronization. The baseline solution reduces multi-graphs to simple ones by averaging their multi-edges, however this approach falls short because: i) averaging is well defined only for some groups and ii) the resulting estimator is less precise and accurate, as we prove empirically. Specifically, we present MULTISYNC, a synchronization algorithm for multi-graphs that is based on a principled constrained eigenvalue optimization. MULTISYNC is a general solution that can cope with any linear group and we show to be profitably usable both on synthetic and real problems.

This paper proposes two novel convolutional neural networks for 3D object classification, tailored to process point clouds that are composed of planar slices (profiles). In particular, the application that we are targeting is the classification of vehicles by scanning them along planes perpendicular to the driving direction, within the context of Electronic Toll Collection. Depending on sensors configurations, the distance between slices can be measured or not, thus resulting in two types of point clouds, namely metric and non-metric. In the latter case, two coordinates are indeed metric but the third one is merely a temporal index. Our networks, named SliceNets, extract metric information from the spatial coordinates and neighborhood information from the third one (either metric or temporal), thus being able to handle both types of point clouds. Experiments on two datasets collected in the field show the effectiveness of our networks in comparison with state-of-the-art ones.

This paper addresses the problem of multiple models fitting in the general context where the sought structures can be described by a mixture of heterogeneous parametric models drawn from different classes. To this end, we conceive a multi-model selection framework that extend T-linkage to cope with different nested class of models. Our method, called MCT, compares favourably with the state-of-the-art on publicly available data-sets for various fitting problems: lines and conics, homographies and fundamental matrices, planes and cylinders.

This paper provides a unifying view and offers new insights on bearing-based network localizability, that is the problem of establishing whether a set of directions between pairs of nodes uniquely determines (up to translation and scale) the position of the nodes in d-space. If nodes represent cameras then we are in the context of global structure from motion. The contribution of the paper is theoretical: first, we rewrite and link in a coherent structure several results that have been presented in different communities using disparate formalisms; second, we derive some new localizability results within the edge-based formulation.

Point cloud classification is one of the most important and time-consuming stages of airborne LiDAR (Light Detection and Ranging) data processing, playing a key role in the generation of cartographic products. This paper describes an innovative algorithm to perform LiDAR point-cloud classification, which relies on Convolutional Neural Networks (CNNs) and takes advantage of full-waveform data registered by modern laser scanners. The proposed method consists of two steps. First, a simple CNN is used to preprocess each waveform, providing a compact representation of the data. By exploiting the coordinates of the points associated with the waveforms, output vectors generated by the first CNN are then mapped into an image that is subsequently segmented by a Fully Convolutional Network (FCN): a label is assigned to each pixel and, consequently, to the point falling in the pixel. In this way, spatial positions and geometrical relationships between neighboring data are taken into account. These particular architectures allow to accurately identify even challenging classes such as power line and transmission tower.

The automatic reconstruction of the walls of an interior environment is a fundamental task in any "scan2BIM" application. In this work, we address this problem resorting to an original and improved version of J-Linkage that leverages on the min-Hash technique to boost the efficiency without sacrificing the accuracy. A framework to automatically and robustly extract floor plans from large-scale point clouds is described and validated on real-word publicly available data.

In this paper we propose a novel solution to the multi-view matching problem that, given a set of noisy pairwise correspondences, jointly updates them so as to maximize their consistency. Our method is based on a spectral decomposition, resulting in a closed-form efficient algorithm, in contrast to other iterative techniques that can be found in the literature. Experiments on both synthetic and real datasets show that our method achieves comparable or superior accuracy to state-of-the-art algorithms in significantly less time. We also demonstrate that our solution can efficiently handle datasets of hundreds of images, which is unprecedented in the literature.

In this paper we address the Wireless Sensor Networks localization problem in a realistic scenario with outliers and structured missing data (i.e. non-random). Our approach couples SMACOF, which handles incomplete data, with IRLS, which is resilient to outliers. In addition, we provide a new insight on how the initialization method — which is crucial to ensure fold-free solutions — should be adapted to the pattern of missing measures. Experiments shows that the proposed method compares favorably with the state-of-the-art.

This letter presents a novel total least squares (TLS) solution of the anisotropic row-scaling Procrustes problem. The ordinary LS Procrustes approach finds the transformation parameters between origin and destination sets of observations minimizing errors affecting only the destination one. In this letter, we introduce the errors-in-variables model in the anisotropic Procrustes analysis problem and present a solution that can deal with the uncertainty affecting both sets of observations. The algorithm is applied to solve the image exterior orientation problem. Experiments show that the proposed TLS method leads to an accuracy in the parameters estimation that is higher than the one reached with the ordinary LS anisotropic Procrustes solution when the number of points, whose coordinates are known in both the image and the external systems, is small.

This paper deals with the problem of estimating camera motion in the context of structure-from-motion. We describe a pipeline that consumes relative orientations and produces absolute orientations (i.e. camera position and attitude in an absolute reference frame). This pipeline exploits the concept of "group synchronization" in most of its stages, all of which entail direct solutions such as eigenvalue decompositions or linear least squares. A comprehensive introduction to the group synchronization problem is provided, and the proposed pipeline is evaluated on standard real datasets.

This paper deals with the extraction of multiple models from noisy or outlier-contaminated data. We cast the multi-model fitting problem in terms of set coverage, deriving a simple and effective method that generalizes Ransac to multiple models and deals with intersecting structures and outliers in a straightforward and principled manner, while avoiding the typical shortcomings of sequential approaches and those of clustering. The method compares favorably against the state-of-the-art on simulated and publicly available real data-sets.

This paper addresses the problem of rigid-motion synchronization (a.k.a. motion averaging) in the Special Euclidean Group SE(3), which finds application in structure-from-motion and registration of multiple three-dimensional (3D) point-sets. After relaxing the geometric constraints of rigid motions, we derive a simple closed-form solution based on a spectral decomposition, which is then projected onto SE(3). Our formulation is extremely efficient, as rigid-motion synchronization is cast to an eigenvalue decomposition problem. Robustness to outliers is gained through Iteratively Reweighted Least Squares. Besides providing a theoretically appealing solution, since our method recovers at the same time both rotations and translations, we demonstrate through experimental results that our approach is significantly faster than the state of the art, while providing accurate estimates of rigid motions.

This paper deals with the problem of recovering the unknown norm of relative translations between cameras based on the knowledge of relative rotations and translation directions. We provide theoretical conditions for the solvability of such a problem, and we propose a two-stage method to solve it. First, a cycle basis for the epipolar graph is computed, then all the scaling factors are recovered simultaneously by solving a homogeneous linear system. We demonstrate the accuracy of our solution by means of synthetic and real experiments.

In this paper we formulate the point-line registration problem, which generalizes absolute orientation to point-line matching, in terms of an instance of the orthogonal Procrustes problem, and derive its solution. The same formulation solves the Non-Perspective-n-Point camera pose problem, which in turn generalizes exterior orientation to non-central cameras, i.e., Generalized cameras where projection rays do not meet in a single point. Our Procrustean solution is very simple and compact, and copes also with scaling. Experiments with simulated data demonstrate that our method compares favourably with the state-of-the-art in terms of accuracy.

This paper deals with the extraction of multiple models from outlier-contaminated data. The method we present is based on preference analysis and low rank approximation. After representing points in a conceptual space, Robust PCA (Principal Component Analysis) and Symmetric NMF (Non negative Matrix Factorization) are employed to reduce the multi-model fitting problem to many single-fitting problems, which in turn are solved with a strategy that resembles MSAC (M-estimator SAmple Consensus). Experimental validation on public, real data-sets demonstrates that our method compares favorably with the state of the art.

This paper proposes a robust method to solve the absolute rotation estimation problem, which arises in global registration of 3D point sets and in structure-from-motion. A novel cost function is formulated which inherently copes with outliers. In particular, the proposed algorithm handles both outlier and missing relative rotations, by casting the problem as a "low-rank & sparse" matrix decomposition. As a side effect, this solution can be seen as a valid and cost-effective detector of inconsistent pair wise rotations. Computational efficiency and numerical accuracy, are demonstrated by simulated and real experiments.

This paper presents an improvement of the J-linkage algorithm for fitting multiple instances of a model to noisy data corrupted by outliers. The binary preference analysis implemented by J-linkage is replaced by a continuous (soft, or fuzzy) generalization that proves to perform better than J-linkage on simulated data, and compares favorably with state of the art methods on public domain real datasets.

The limited depth-of-field of some cameras prevents them from capturing perfectly focused images when the imaged scene covers a large distance range. In order to compensate for this problem, image fusion has been exploited for combining images captured with different camera settings, thus yielding a higher quality all-in-focus image. Since most current approaches for image fusion rely on maximizing the spatial frequency of the composed image, the fusion process is sensitive to noise. In this paper, a new algorithm for computing the all-in-focus image from a sequence of images captured with a low depth-of-field camera is presented. The proposed approach adaptively fuses the different frames of the focus sequence in order to reduce noise while preserving image features. The algorithm consists of three stages: 1) focus measure; 2) selectivity measure; 3) and image fusion. An extensive set of experimental tests has been carried out in order to compare the proposed algorithm with state-of-the-art all-in-focus methods using both synthetic and real sequences. The obtained results show the advantages of the proposed scheme even for high levels of noise.

We present a completely automated Structure and Motion pipeline capable of working with uncalibrated images with varying internal parameters and no ancillary information. The system is based on a novel hierarchical scheme which reduces the total complexity by one order of magnitude. We assess the quality of our approach analytically by comparing the recovered point clouds with laser scans, which serves as ground truth data.

In this paper, we propose a patch-based technique for robust background initialization that exploits both spatial and temporal consistency of the static background. The proposed technique is able to cope with heavy clutter, i.e, foreground objects that stand still for a considerable portion of time. First, the sequence is subdivided in patches that are clustered along the time-line in order to narrow down the number of background candidates. Then, a tessellation is grown incrementally by selecting at each step the best continuation of the current background. The method rests on sound principles in all its stages and only few, intelligible parameters are needed. Experimental results show that the proposed algorithm is effective and compares favorably with existing techniques.

This paper proposes a technique for estimating piece wise planar models of objects from their images and geometric constraints. First, assuming a bounded noise in the localization of 2D points, the position of the 3D point is estimated as a polyhedron containing all the possible solutions of the triangulation. Then, given the topological structure of the 3D points cloud, geometric relationships among facets, such as coplanarity, parallelism, orthogonality, and angle equality, are automatically detected. A subset of them that is sufficient to stabilize the 3D model estimation is selected with a flow-network based algorithm. Finally a feasible instance of the 3D model, i.e. one that satisfies the selected geometric relationships and whose 3D points lie within the associated polyhedral bounds, is computed by solving a Constraint Satisfaction Problem.

This paper deals with the problem of epipolar rectification in the uncalibrated case. First the calibrated (Euclidean) case is recognized as the ideal one, then we observe that in that case images are transformed with a collineation induced by the plane at infinity, which has a specific structure. That structure is therefore imposed to the sought transformation while minimizing the rectification error. Experiments show that this method yields images that are remarkably close to the ones produced by Euclidean rectification.

In this paper a method for the extraction of shading and reflectance intrinsic images from a single uncalibrated image is presented. It is based on the classification of the image derivatives as either caused by shading or reflectance effects, using an illumination-invariant image to guide this classification. Our approach avoids the learning process -which requires ground truth intrinsic images -and obtain results comparable with the state of the art.

This paper deals with the views synthesis problem and proposes an automatic method for specifying the virtual camera position and orientation in an uncalibrated setting, based on the interpolation and extrapolation of the motion among the reference views. Novel images can be rendered from virtual cameras moving on parametric trajectories. Synthetic and real experiments illustrate the approach

In this paper we demonstrate how Interval Analysis and Constraint Logic Programming can be used to obtain an accurate geometric model of a scene that rigorously takes into account the propagation of data errors and roundoff. Image points are represented as small rectangles: As a result, the output of the n-views triangulation is not a single point in space, but a polyhedron that contains all the possible solutions. Interval Analysis is used to bound this polyhedron with a box. Geometrical constraints such as orthogonality, parallelism, and coplanarity are subsequently enforced in order to reduce the size of those boxes, using Constraint Logic Programming. Experiments with real calibrated images illustrate the approach.

In this paper we present a method for novel view synthesis from two uncalibrated reference views. Snapshots of a scene are created as if they were taken from a different "virtual" viewpoint. The relative affine structure is used to describe the geometry of the scene and then to extrapolate and interpolate novel views. The contribution of this paper is an automatic method for specifying the virtual viewpoint in an uncalibrated setting, based on the interpolation and extrapolation of the epipolar geometry linking the reference views. Experimental results using synthetic and real images are shown.

In this paper we present a technique for tracking complex models in video sequences with multiple cameras. Our method uses information derived from image gradient by comparing them with edges of the tracked object, whose 3D model is known. A score function is defined, depending on the amount of image gradient "seen" by the model edges. The sought pose parameters are obtained by maximizing this function using a non deterministic algorithm which proved to be optimal for this problem. Preliminary experiments with both synthetic and real sequences have shown small errors in pose estimations and a good behavior in augmented reality applications.

We address the problem of autocalibration of a moving camera with unknown constant intrinsic parameters. Existing autocalibration techniques use numerical optimization algorithms whose convergence to the correct result cannot be guaranteed, in general. To address this problem, we have developed a method where an interval branch-and-bound method is employed for numerical minimization. Thanks to the properties of Interval Analysis this method converges to the global solution with mathematical certainty and arbitrary accuracy and the only input information it requires from the user are a set of point correspondences and a search interval. The cost function is based on the Huang-Faugeras constraint of the essential matrix. A recently proposed interval extension based on Bernstein polynomial forms has been investigated to speed up the search for the solution. Finally, experimental results are presented.

In this paper, underwater scene modeling from multisensor data is addressed. Acoustic and optical devices aboard an underwater vehicle are used to sense the environment in order to produce an output that is readily understandable even by an inexperienced operator. The main idea is to integrate multiple-sensor data by geometrically registering such data to a model. The geometrical structure of this model is a priori known but not ad hoc designed for this purpose. As a result, the vehicle pose is derived and model objects can be superimposed upon actual images, thus generating an augmented-reality representation. Results on a real underwater scene are reported, showing the effectiveness of the proposed approach.

Existing autocalibration techniques use numerical optimization algorithms that are prone to the problem of local minima. To address this problem, we have developed a method where an interval branch-and-bound method is employed for numerical minimization. Thanks to the properties of interval analysis this method is guaranteed to converge to the global solution with mathematical certainty and arbitrary accuracy, and the only input information it requires from the user is a set of point correspondences and a search box. The cost function is based on the Huang-Faugeras constraint of the fundamental matrix. A recently proposed interval extension based on Bernstein polynomial forms has been investigated to speed up the search for the solution. Finally, some experimental results on synthetic images are presented.

In this paper we describe an application which takes a video shot as input and produces a compact representation composed by a background layer and segmented moving objects. We deal with the problems of global registration, super-resolution mosaicing, objects segmentation and tracking. Global registration is achieved with a graph-based technique that exploits situations when the camera returns to a previously seen area. Objects segmentation is based on motion analysis using a robust statistical model of the background. Tracking is based on blob matching using singular value decomposition.

We address the alignment of historical and present-day aerial photographs. Historical images refer to regions bombed during the Second World War. In these regions, the risk of unexploded bombs is still high, especially where the bombing was more frequent. Alignment is required to fill in an unexploded bombs risk map. The task is challenging because many features in the historical images have changed or are missing (and vice versa). Moreover, in the historical images, bomb craters introduce large gray level variations so that it is difficult to extract features automatically. This work propose a semi-automatic application for image alignment in order to improve accuracy and to speed up the alignment process.

This paper describes an electronic travel aid device, that may enable blind individuals to "see the world with their ears". A wearable prototype will be assembled using low-cost hardware: earphones, sunglasses fitted with two micro cameras, and a palmtop computer. The system, which currently runs on a desktop computer, is able to detect the light spot produced by a laser pointer, compute its angular position and depth, and generate a corresponding sound providing auditory cues for perception of the position and distance of the pointed surface patch. It permits different sonification modes that can be chosen by drawing, with the laser pointer, a predefined stroke which will be recognized by a hidden Markov model. In this way a blind person can use a common pointer as a replacement for the cane and will interact with the device using a flexible and natural sketch based interface.

This paper proposes some Markov random field (MRF) models for the restoration of stereo disparity maps. The main aspect is the use of confidence maps provided by the symmetric multiple windows (SMW) stereo algorithm to guide the restoration process. The SMW algorithm is an adaptive, multiple-window scheme using left-right consistency to compute disparity and its associated confidence in the presence of occlusions. The MRF approach allows the combining in a single functional of all the available information: observed data with its confidence, noise, and a-priori hypotheses. Optimal estimates of the disparity are obtained by minimizing an energy functional using simulated annealing. Results with a real stereo pair show the improvement obtained by restoration using the MRF approach integrating confidence data.

This paper proposes a technique for the 3D reconstruction of an underwater environment from multiple range views. The final target of the work lies in improving the understanding of a human operator guiding an underwater remotely operated vehicle (ROV) equipped with an acoustic camera, which provides a sequence of 3D images in real time. Since the field of view is narrow we devise a technique for the reconstruction of relevant information of the image sequence up to building a mosaic of the surrounding scene. Due to the very noisy nature of the data and the low range resolution, smoothing, segmentation, registration, and fusion problems have been tackled. Examples on real images are presented to show the promising performances of the algorithm.

We present a new, efficient stereo algorithm addressing robust disparity estimation in the presence of occlusions. The algorithm is an adaptive, multiwindow scheme using left–right consistency to compute disparity and its associated uncertainty. We demonstrate and discuss performances with both synthetic and real stereo pairs, and show how our results improve on those of closely related techniques for both accuracy and efficiency.

This paper addresses robust feature tracking. We extend the well-known Shi-Tomasi-Kanade tracker by introducing an automatic scheme for rejecting spurious features. We employ a simple and efficient outlier rejection rule, called X84, and prove that its theoretical assumptions are satisfied in the feature tracking scenario. Experiments with real and synthetic images confirm that our algorithm makes good features track better; we show a quantitative example of the benefits introduced by the algorithm for the case of fundamental matrix estimation. The complete code of the robust tracker is available via ftp.

We present a new, efficient stereo algorithm addressing robust disparity estimation in the presence of occlusions. The algorithm is an adaptive, multi-window scheme using left-right consistency to compute disparity and its associated uncertainty. We demonstrate and discuss performances with both synthetic and real stereo pairs, and show how our results improve on those of closely related techniques for both robustness and efficiency.