Hierarchical open-set classification handles previously unseen classes by assigning them to the most appropriate high-level category in a class taxonomy. We extend this paradigm to the semi-supervised setting, enabling the use of large-scale, uncurated datasets containing a mixture of known and unknown classes to improve the hierarchical open-set performance. To this end, we propose a teacher-student framework based on pseudo-labeling. Two key components are introduced: 1) subtree pseudo-labels, which provide reliable supervision in the presence of unknown data, and 2) age-gating, a mechanism that mitigates overconfidence in pseudo-labels. Experiments show that our framework outperforms self-supervised pretraining followed by supervised adaptation, and even matches the fully supervised counterpart when using only 20 labeled samples per class on the iNaturalist19 benchmark. Our code is available at https://github.com/walline/semihoc.

The rapid growth of AR/VR/MR applications and cloudbased visual localization has heightened concerns over user privacy. This privacy concern has been further escalated by the ability of deep neural networks to recover detailed images of a scene from a sparse set of 3D or 2D points and their descriptors - the so-called inversion attacks. Research on privacy-preserving localization has therefore focused on preventing such attacks through geometry obfuscation techniques like lifting points to higher dimensions or swapping coordinates. In this paper, we reveal a common vulnerability in these methods that allows approximate point recovery using known neighborhoods. We further show that these neighborhoods can be computed by learning to identify descriptors that co-occur in neighborhoods. Extensive experiments demonstrate that all existing geometric obfuscation schemes remain susceptible to such recovery, challenging their claims of being privacy-preserving. Code will be available at https://github.com/kunalchelani/RecoverPointsNeighborhood.

Antibiotic Resistance (AR) is a critical global health challenge that necessitates the development of cost-effective, efficient, and accurate diagnostic tools. Given the genetic basis of AR, techniques such as Polymerase Chain Reaction (PCR) that target specific resistance genes offer a promising approach for predictive diagnostics using a limited set of key genes. This study introduces GenoARM, a novel framework that integrates reinforcement learning (RL) with transformer-based models to optimize the selection of PCR gene tests and improve AR predictions, leveraging observed metadata for improved accuracy. In our evaluation, we developed several high-performing baselines and compared them using publicly available datasets derived from real-world bacterial samples representing multiple clinically relevant pathogens. The results show that all evaluated methods achieve strong and reliable performance when metadata is not utilized. When metadata is introduced and the number of selected genes increases, GenoARM demonstrates superior performance due to its capacity to approximate rewards for unseen and sparse combinations. Overall, our framework represents a major advancement in optimizing diagnostic tools for AR in clinical settings.

Out-of-distribution (OOD) detection in deep learning has traditionally been framed as a binary task, where samples are either classified as belonging to the known classes or marked as OOD, with little attention given to the semantic relationships between OOD samples and the in-distribution (ID) classes. We propose a framework for detecting and classifying OOD samples in a given class hierarchy. Specifically, we aim to predict OOD data to their correct internal nodes of the class hierarchy, whereas the known ID classes should be predicted as their corresponding leaf nodes. Our approach leverages the class hierarchy to create a probabilistic model and we implement this model by using networks trained for ID classification at multiple hierarchy depths. We conduct experiments on three datasets with predefined class hierarchies and show the effectiveness of our method. Our code is available at https://github.com/walline/prohoc.

Incorporating geometric invariance into neural networks enhances parameter efficiency but typically increases computational costs. This paper introduces new equivariant neural networks that preserve symmetry while maintaining a comparable number of floating-point operations (FLOPs) per parameter to standard non-equivariant networks. We focus on horizontal mirroring (flopping) invariance, common in many computer vision tasks. The main idea is to parametrize the feature spaces in terms of mirror-symmetric and mirror-antisymmetric features, i.e., irreps of the flopping group. This decomposes the linear layers to be block-diagonal, requiring half the number of FLOPs. Our approach reduces both FLOPs and wall-clock time, providing a practical solution for efficient, scalable symmetry-aware architectures.

With their meaningful geometry and omnipresence in the 3D world, edges are extremely useful primitives in computer vision. Methods for 3D edge reconstruction have 1) either focused on reconstructing 3D edges by triangulating tracks of 2D line segments across images or 2) more recently, learning a 3D edge distance field from multi-view images. The triangulation-based methods struggle to repeatedly detect and robustly match line segments resulting in noisy and incomplete reconstructions in many cases. Methods in the latter class rely on sampling edge points from the learnt implicit field, which is limited by the spatial resolution of the voxel grid used for sampling, resulting in imprecise points that require refinement. Further, such methods require a long training that scales poorly with the size of the scene. In this paper, we propose a method that explicitly learns 3D edge points with a 3D Gaussian Splatting representation trained from edge images. The 3D Gaussians are regularized to have their directions of largest variance along the edge they lie on, enabling clustering into separate edges. Backed by efficient training, the proposed method produces results better than or at-par with the current state-of-the-art methods, while being an order of magnitude faster. Code released at https://github.com/kunalchelani/EdgeGaussians.

Image keypoint descriptions that are discriminative and matchable over large changes in viewpoint are vital for 3D reconstruction. However, descriptions output by learned descriptors are typically not robust to camera rotation. While they can be made more robust by, e.g., data augmentation, this degrades performance on upright images. Another approach is test-time augmentation, which incurs a significant increase in runtime. Instead, we learn a linear transform in description space that encodes rotations of the input image. We call this linear transform a steerer since it allows us to transform the descriptions as if the image was rotated. From representation theory, we know all possible steerers for the rotation group. Steerers can be optimized (A) given a fixed descriptor, (B) jointly with a descriptor or (C) we can optimize a descriptor given a fixed steerer. We perform experiments in these three settings and obtain state-of-the-art results on the rotation invariant image matching benchmarks AIMS and Roto-360. We publish code and model weights at this https url.

In this paper we tackle the problem of learning Structure-from-Motion (SfM) through the use of graph attention networks. SfM is a classic computer vision problem that is solved though iterative minimization of reprojection errors, referred to as Bundle Adjustment (BA), starting from a good initialization. In order to obtain a good enough initial-ization to BA, conventional methods rely on a sequence of sub-problems (such as pairwise pose estimation, pose averaging or triangulation) which provide an initial solution that can then be refined using BA. In this work we re-place these sub-problems by learning a model that takes as input the 2D keypoints detected across multiple views, and outputs the corresponding camera poses and 3D key-point coordinates. Our model takes advantage of graph neural networks to learn SfM-specijic primitives, and we show that it can be used for fast inference of the reconstruction for new and unseen sequences. The experimental results show that the proposed model outperforms com-peting learning-based methods, and challenges COLMAP while having lower runtime. Our code is available at: https://github.com/lucasbrynte/gasfm/.

Open-set semi-supervised learning (OSSL) embodies a practical scenario within semi-supervised learning, wherein the unlabeled training set encompasses classes absent from the labeled set. Many existing OSSL methods assume that these out-of-distribution data are harmful and put effort into excluding data belonging to unknown classes from the training objective. In contrast, we propose an OSSL framework that facilitates learning from all unlabeled data through self-supervision. Additionally, we utilize an energy-based score to accurately recognize data belonging to the known classes, making our method well-suited for handling uncurated data in deployment. We show through extensive experimental evaluations that our method yields state-of-the-art results on many of the evaluated benchmark problems in terms of closed-set accuracy and open-set recognition when compared with existing methods for OSSL. Our code is available at https://github.com/walline/ssl-tf2-sefoss.

Visual localization is the task of estimating the camera pose from which a given image was taken and is central to several 3D computer vision applications. With the rapid growth in the popularity of AR/VR/MR devices and cloudbased applications, privacy issues are becoming a very important aspect of the localization process. Existing work on privacy-preserving localization aims to defend against an attacker who has access to a cloud-based service. In this paper, we show that an attacker can learn about details of a scene without any access by simply querying a localization service. The attack is based on the observation that modern visual localization algorithms are robust to variations in appearance and geometry. While this is in general a desired property, it also leads to algorithms localizing objects that are similar enough to those present in a scene. An attacker can thus query a server with a large enough set of images of objects, e.g., obtained from the Internet, and some of them will be localized. The attacker can thus learn about object placements from the camera poses returned by the service (which is the minimal information returned by such a service). In this paper, we develop a proof-of-concept version of this attack and demonstrate its practical feasibility. The attack does not place any requirements on the localization algorithm used, and thus also applies to privacy-preserving representations. Current work on privacy-preserving representations alone is thus insufficient.

Many data symmetries can be described in terms of group equivariance and the most common way of encoding group equivariances in neural networks is by building linear layers that are group equivariant. In this work we investigate whether equivariance of a network implies that all layers are equivariant. On the theoretical side we find cases where equivariance implies layerwise equivariance, but also demonstrate that this is not the case generally. Nevertheless, we conjecture that CNNs that are trained to be equivariant will exhibit layerwise equivariance and explain how this conjecture is a weaker version of the recent permutation conjecture by Entezari et al.\ [2022]. We perform quantitative experiments with VGG-nets on CIFAR10 and qualitative experiments with ResNets on ImageNet to illustrate and support our theoretical findings. These experiments are not only of interest for understanding how group equivariance is encoded in ReLU-networks, but they also give a new perspective on Entezari et al.'s permutation conjecture as we find that it is typically easier to merge a network with a group-transformed version of itself than merging two different networks.

In this paper, we are concerned with rotation equivariance on 2D point cloud data. We describe a particular set of functions able to approximate any continuous rotation equivariant and permutation invariant function. Based on this result, we propose a novel neural network architecture for processing 2D point clouds and we prove its universality for approximating functions exhibiting these symmetries. We also show how to extend the architecture to accept a set of 2D-2D correspondences as indata, while maintaining similar equivariance properties. Experiments are presented on the estimation of essential matrices in stereo vision.

In this work, we analyze linear operators on the space of square integrable functions on the sphere. Specifically, we characterize the operators which are equivariant to azimuthal rotations, that is, rotations around the z-axis. Several high-performing neural networks defined on the sphere are equivariant to azimuthal rotations, but not to full SO(3) rotations. Our main result is to show that a linear operator acting on band-limited functions on the sphere is equivariant to azimuthal rotations if and only if it can be realized as a block-diagonal matrix acting on the spherical harmonic expansion coefficients of its input. Further, we show that such an operation can be interpreted as a convolution, or equivalently, a correlation in the spatial domain. Our theoretical findings are backed up with experimental results demonstrating that a state-of-the-art pipeline can be improved by making it equivariant to azimuthal rotations.

Following the success of supervised learning, semi-supervised learning (SSL) is now becoming increasingly popular. SSL is a family of methods, which in addition to a labeled training set, also use a sizable collection of unlabeled data for fitting a model. Most of the recent successful SSL methods are based on pseudo-labeling approaches: letting confident model predictions act as training labels. While these methods have shown impressive results on many benchmark datasets, a drawback of this approach is that not all unlabeled data are used during training. We propose a new SSL algorithm, DoubleMatch, which combines the pseudo-labeling technique with a self-supervised loss, enabling the model to utilize all unlabeled data in the training process. We show that this method achieves state-of-the-art accuracies on multiple benchmark datasets while also reducing training times compared to existing SSL methods. Code is available at https://github.com/walline/doublematch.

Visual localization enables autonomous vehicles to navigate in their surroundings and augmented reality applications to link virtual to real worlds. Practical visual localization approaches need to be robust to a wide variety of viewing conditions, including day-night changes, as well as weather and seasonal variations, while providing highly accurate six degree-of-freedom (6DOF) camera pose estimates. In this paper, we extend three publicly available datasets containing images captured under a wide variety of viewing conditions, but lacking camera pose information, with ground truth pose information, making evaluation of the impact of various factors on 6DOF camera pose estimation accuracy possible. We also discuss the performance of state-of-the-art localization approaches on these datasets. Additionally, we release around half of the poses for all conditions, and keep the remaining half private as a test set, in the hopes that this will stimulate research on long-term visual localization, learned local image features, and related research areas. Our datasets are available at visuallocalization.net, where we are also hosting a benchmarking server for automatic evaluation of results on the test set. The presented state-of-the-art results are to a large degree based on submissions to our server.

Visual localization is the problem of estimating the camera pose of a given image with respect to a known scene. Visual localization algorithms are a fundamental building block in advanced computer vision applications, including Mixed and Virtual Reality systems. Many algorithms used in practice represent the scene through a Structure-from-Motion (SfM) point cloud and use 2D-3D matches between a query image and the 3D points for camera pose estimation. As recently shown, image details can be accurately recovered from SfM point clouds by translating renderings of the sparse point clouds to images. To address the resulting potential privacy risks for user-generated content, it was recently proposed to lift point clouds to line clouds by replacing 3D points by randomly oriented 3D lines passing through these points. The resulting representation is unintelligible to humans and effectively prevents point cloud-to-image translation. This paper shows that a significant amount of information about the 3D scene geometry is preserved in these line clouds, allowing us to (approximately) recover the 3D point positions and thus to (approximately) recover image content. Our approach is based on the observation that the closest points between lines can yield a good approximation to the original 3D points. Code is available at https://github.com/kunalchelani/Line2Point.

In this paper we study structure from motion problems for 1D radial cameras. Under this model the projection of a 3D point is a line in the image plane going through the principal point, which makes the model invariant to radial distortion and changes in focal length. It can therefore effectively be applied to uncalibrated image collections without the need for explicit estimation of camera intrinsics.We show that the reprojection errors of 1D radial cameras are examples of quasiconvex functions. This opens up the possibility to solve a general class of relevant reconstruction problems globally optimally using tools from convex optimization. In fact, our resulting algorithm is based on solving a series of LP problems. We perform an extensive experimental evaluation, on both synthetic and real data, showing that a whole class of multiview geometry problems across a range of different cameras models with varying and unknown intrinsic calibration can be reliably and accurately solved within the same framework.1

Camera pose estimation in known scenes is a 3D geometry task recently tackled by multiple learning algorithms. Many regress precise geometric quantities, like poses or 3D points, from an input image. This either fails to generalize to new viewpoints or ties the model parameters to a specific scene. In this paper, we go Back to the Feature: we argue that deep networks should focus on learning robust and invariant visual features, while the geometric estimation should be left to principled algorithms. We introduce PixLoc, a scene-agnostic neural network that estimates an accurate 6-DoF pose from an image and a 3D model. Our approach is based on the direct alignment of multiscale deep features, casting camera localization as metric learning. PixLoc learns strong data priors by end-to-end training from pixels to pose and exhibits exceptional generalization to new scenes by separating model parameters and scene geometry. The system can localize in large environments given coarse pose priors but also improve the accuracy of sparse feature matching by jointly refining keypoints and poses with little overhead. The code will be publicly available at github.com/cvg/pixloc.

Visual localization is the problem of estimating the position and orientation from which a given image (or a sequence of images) is taken in a known scene. It is an important part of a wide range of computer vision and robotics applications, from self-driving cars to augmented/virtual reality systems. Visual localization techniques should work reliably and robustly under a wide range of conditions, including seasonal, weather, illumination and man-made changes. Recent benchmarking efforts model this by providing images under different conditions, and the community has made rapid progress on these datasets since their inception. However, they are limited to a few geographical regions and often recorded with a single device. We propose a new benchmark for visual localization in outdoor scenes, using crowd-sourced data to cover a wide range of geographical regions and camera devices with a focus on the failure cases of current algorithms. Experiments with state-of-the-art localization approaches show that our dataset is very challenging, with all evaluated methods failing on its hardest parts. As part of the dataset release, we provide the tooling used to generate it, enabling efficient and effective 2D correspondence annotation to obtain reference poses.

In this paper we explore the role of duality principles within the problem of rotation averaging, a fundamental task in a wide range of applications. In its conventional form, rotation averaging is stated as a minimization over multiple rotation constraints. As these constraints are non-convex, this problem is generally considered challenging to solve globally. We show how to circumvent this difficulty through the use of Lagrangian duality. While such an approach is well-known it is normally not guaranteed to provide a tight relaxation. Based on spectral graph theory, we analytically prove that in many cases there is no duality gap unless the noise levels are severe. This allows us to obtain certifiably global solutions to a class of important non-convex problems in polynomial time. We also propose an efficient, scalable algorithm that outperforms general purpose numerical solvers by a large margin and compares favourably to current state-of-the-art. Further, our approach is able to handle the large problem instances commonly occurring in structure from motion settings and it is trivially parallelizable. Experiments are presented for a number of different instances of both synthetic and real-world data.

In this paper we present a study of global optimality conditions for Point Set Registration (PSR) with missing data. PSR is the problem of aligning multiple point clouds with an unknown target point cloud. Since non-linear rotation constraints are present the problem is inherently non-convex and typically relaxed by computing the Lagrange dual, which is a Semidefinite Program (SDP). In this work we show that given a local minimizer the dual variables of the SDP can be computed in closed form. This opens up the possibility of verifying the optimally, using the SDP formulation without explicitly solving it. In addition it allows us to study under what conditions the relaxation is tight, through spectral analysis. We show that if the errors in the (unknown) optimal solution are bounded the SDP formulation will be able to recover it.

In this paper, we present a method to utilize 2D-2D point matches between images taken during different image conditions to train a convolutional neural network for semantic segmentation. Enforcing label consistency across the matches makes the final segmentation algorithm robust to seasonal changes. We describe how these 2D-2D matches can be generated with little human interaction by geometrically matching points from 3D models built from images. Two cross-season correspondence datasets are created providing 2D-2D matches across seasonal changes as well as from day to night. The datasets are made publicly available to facilitate further research. We show that adding the correspondences as extra supervision during training improves the segmentation performance of the convolutional neural network, making it more robust to seasonal changes and weather conditions.

Long-term visual localization is the problem of estimating the camera pose of a given query image in a scene whose appearance changes over time. It is an important problem in practice that is, for example, encountered in autonomous driving. In order to gain robustness to such changes, long-term localization approaches often use segmantic segmentations as an invariant scene representation, as the semantic meaning of each scene part should not be affected by seasonal and other changes. However, these representations are typically not very discriminative due to the very limited number of available classes. In this paper, we propose a novel neural network, the Fine-Grained Segmentation Network (FGSN), that can be used to provide image segmentations with a larger number of labels and can be trained in a self-supervised fashion. In addition, we show how FGSNs can be trained to output consistent labels across seasonal changes. We show through extensive experiments that integrating the fine-grained segmentations produced by our FGSNs into existing localization algorithms leads to substantial improvements in localization performance.

In this paper we explore the role of duality principles within the problem of rotation averaging, a fundamental task in a wide range of computer vision applications. In its conventional form, rotation averaging is stated as a minimization over multiple rotation constraints. As these constraints are non-convex, this problem is generally considered challenging to solve globally. We show how to circumvent this difficulty through the use of Lagrangian duality. While such an approach is well-known it is normally not guaranteed to provide a tight relaxation. Based on spectral graph theory, we analytically prove that in many cases there is no duality gap unless the noise levels are severe. This allows us to obtain certifiably global solutions to a class of important non-convex problems in polynomial time. We also propose an efficient, scalable algorithm that outperforms general purpose numerical solvers and is able to handle the large problem instances commonly occurring in structure from motion settings. The potential of this proposed method is demonstrated on a number of different problems, consisting of both synthetic and real-world data.

Visual localization enables autonomous vehicles to navigate in their surroundings and augmented reality applications to link virtual to real worlds. Practical visual localization approaches need to be robust to a wide variety of viewing condition, including day-night changes, as well as weather and seasonal variations, while providing highly accurate 6 degree-of-freedom (6DOF) camera pose estimates. In this paper, we introduce the first benchmark datasets specifically designed for analyzing the impact of such factors on visual localization. Using carefully created ground truth poses for query images taken under a wide variety of conditions, we evaluate the impact of various factors on 6DOF camera pose estimation accuracy through extensive experiments with state-of-the-art localization approaches. Based on our results, we draw conclusions about the difficulty of different conditions, showing that long-term localization is far from solved, and propose promising avenues for future work, including sequence-based localization approaches and the need for better local features. Our benchmark is available at visuallocalization.net.

We study the relation between the correlation-based target functions of low-resolution and high-resolution intensity-based registration for the class of rigid transformations. Our results show that low-resolution target values can tightly bound the high-resolution target function in natural images. This can help with analyzing and better understanding the process of multiresolution image registration. It also gives a guideline for designing multiresolution algorithms in which the search space in higher resolution registration is restricted given the fitness values for lower resolution image pairs. To demonstrate this, we incorporate our multiresolution technique into a Lipschitz global optimization framework. We show that using the multiresolution scheme can result in large gains in the efficiency of such algorithms. The method is evaluated by applying to the problems of 2D registration, 3D rotation search, and the detection of reflective symmetry in 2D and 3D images.

Semantic segmentation and other pixel-level labeling tasks have made significant progress recently due to the deep learning paradigm. Many state-of-the-art structured prediction methods also include a random field model with a hand-crafted Gaussian potential to model spatial priors and label consistencies and feature-based image conditioning. These random field models with image conditioning typically require computationally demanding filtering techniques during inference. In this paper, we present a new inference and learning framework which can learn arbitrary pairwise conditional random field (CRF) potentials. Both standard spatial and high-dimensional bilateral kernels are considered. In addition, we introduce a new type of potential function which is image-dependent like the bilateral kernel, but an order of magnitude faster to compute since only spatial convolutions are employed. It is empirically demonstrated that such learned potentials can improve segmentation accuracy and that certain label-class interactions are indeed better modeled by a non-Gaussian potential. Our framework is evaluated on several public benchmarks for semantic segmentation with improved performance compared to previous state-of-the-art CNN+CRF models.

We consider the problem of localizing a novel image in a large 3D model, given that the gravitational vector is known. In principle, this is just an instance of camera pose estimation, but the scale of the problem introduces some interesting challenges. Most importantly, it makes the correspondence problem very difficult so there will often be a significant number of outliers to handle. To tackle this problem, we use recent theoretical as well as technical advances. Many modern cameras and phones have gravitational sensors that allow us to reduce the search space. Further, there are new techniques to efficiently and reliably deal with extreme rates of outliers. We extend these methods to camera pose estimation by using accurate approximations and fast polynomial solvers. Experimental results are given demonstrating that it is possible to reliably estimate the camera pose despite cases with more than 99 percent outlier correspondences in city-scale models with several millions of 3D points.

In computer vision, many problems can be formulated as finding a low rank approximation of a given matrix. Ideally, if all elements of the measurement matrix are available, this is easily solved in the L2-norm using factorization. However, in practice this is rarely the case. Lately, this problem has been addressed using different approaches, one is to replace the rank term by the convex nuclear norm, another is to derive the convex envelope of the rank term plus a data term. In the latter case, matrices are divided into sub-matrices and the envelope is computed for each subblock individually. In this paper a new convex envelope is derived which takes all sub-matrices into account simultaneously. This leads to a simpler formulation, using only one parameter to control the trade-of between rank and data fit, for applications where one seeks low rank approximations of multiple matrices with the same rank. We show in this paper how our general framework can be used for manifold denoising of several images at once, as well as just denoising one image. Experimental comparisons show that our method achieves results similar to state-of-the-art approaches while being applicable for other problems such as linear shape model estimation.

Previous work on estimating the epipolar geometry of two views relies on being able to reliably match feature points based on appearance. In this paper, we go one step further and show that it is feasible to compute both the epipolar geometry and the correspondences at the same time based on geometry only. We do this in a globally optimal manner. Our approach is based on an efficient branch and bound technique in combination with bipartite matching to solve the correspondence problem. We rely on several recent works to obtain good bounding functions to battle the combinatorial explosion of possible matchings. It is experimentally demonstrated that more difficult cases can be handled and that more inlier correspondences can be obtained by being less restrictive in the matching phase.

High computational cost is the main obstacle to adapting globally optimal branch-and-bound algorithms to intensity-based registration. Existing techniques to speed up such algorithms use a multiresolution pyramid of images and bounds on the target function among different resolutions for rigidly aligning two images. In this paper, we propose a dual algorithm in which the optimization is done in the Fourier domain, and multiple resolution levels are replaced by multiple frequency bands. The algorithm starts by computing the target function in lower frequency bands and keeps adding higher frequency bands until the current subregion is either rejected or divided into smaller areas in a branch and bound manner. Unlike spatial multiresolution approaches, to compute the target function for a wider frequency area, one just needs to compute the target in the residual bands. Therefore, if an area is to be discarded, it performs just enough computations required for the rejection. This property also enables us to use a rather large number of frequency bands compared to the limited number of resolution levels used in the space domain algorithm. Experimental results on real images demonstrate considerable speed gains over the space domain method in most cases.

Despite of having no explicit shape model, multi-atlas approaches to image segmentation have proved to be a top-performer for several diverse datasets and imaging modalities. In this paper, we show how one can directly incorporate shape regularization into the multi-atlas framework. Unlike traditional methods, our proposed approach does not rely on label fusion on the voxel level. Instead, each registered atlas is viewed as an estimate of the position of a shape model. We evaluate and compare our method on two public benchmarks: (i) the VISCERAL Grand Challenge on multi-organ segmentation of whole-body CT images and (ii) the Hammers brain atlas of MR images for segmenting the hippocampus and the amygdala. For this wide spectrum of both easy and hard segmentation tasks, our experimental quantitative results are on par or better than state-of-the-art. More importantly, we obtain qualitatively better segmentation boundaries, for instance, preserving fine structures.

Online 3D reconstruction has been an active research area for a long time. Since the release of the Microsoft Kinect Camera and publication of KinectFusion [11] attention has been drawn how to acquire dense models in real-time. In this paper we present a method to make online 3D reconstruction which increases robustness for scenes with little structure information and little texture information. It is shown empirically that our proposed method also increases robustness when the distance between the camera positions becomes larger than what is commonly assumed. Quantitative and qualitative results suggest that this approach can handle situations where other well-known methods fail. This is important in, for example, robotics applications like when the camera position and the 3D model must be created online in real-time.

Variations in the shape and appearance of anatomical structures in medical images are often relevant radiological signs of disease. Automatic tools can help automate parts of this manual process. A cloud-based evaluation framework is presented in this paper including results of benchmarking current state-of-the-art medical imaging algorithms for anatomical structure segmentation and landmark detection: the VISCERAL Anatomy benchmarks. The algorithms are implemented in virtual machines in the cloud where participants can only access the training data and can be run privately by the benchmark administrators to objectively compare their performance in an unseen common test set. Overall, 120 computed tomography and magnetic resonance patient volumes were manually annotated to create a standard Gold Corpus containing a total of 1295 structures and 1760 landmarks. Ten participants contributed with automatic algorithms for the organ segmentation task, and three for the landmark localization task. Different algorithms obtained the best scores in the four available imaging modalities and for subsets of anatomical structures. The annotation framework, resulting data set, evaluation setup, results and performance analysis from the three VISCERAL Anatomy benchmarks are presented in this article. Both the VISCERAL data set and Silver Corpus generated with the fusion of the participant algorithms on a larger set of non-manually-annotated medical images are available to the research community.

This paper describes a new method of finding thin, elongated structures in images and volumes. We use shortest paths to minimize very general functionals of higher-order curve properties, such as curvature and torsion. Our method uses line graphs to find the optimal path on a given discretization, often in the order of seconds on a single computer. The curves are then refined using local optimization making it possible to recover very smooth curves. We are able to place constraints on our curves such as maximum integrated curvature, or a maximum curvature at any point of the curve. To our knowledge, we are the first to perform experiments in three dimensions with curvature and torsion regularization. The largest graphs we process have over a hundred billion arcs. Experiments on medical images and in multi-view reconstruction show the significance and practical usefulness of higher order regularization.

It has long been recognized that one of the fundamental difficulties in the estimation of two-view epipolar geometry is the capability of handling outliers. In this paper, we develop a fast and tractable algorithm that maximizes the number of inlier under the assumption of a purely translating camera. Compared to classical random sampling methods, our approach is guaranteed to compute the optimal solution of a cost function based on reprojection errors and it has better time complexity. The performance is in fact independent of the inlier/outlier ratio of the data. This opens up for a more reliable approach to robust ego-motion estimation. Our basic translation estimator can be embedded into a system that computes the full camera rotation. We demonstrate the applicability in several difficult settings with large amounts of outliers. It turns out to be particularly well-suited for small rotations and rotations around a known axis (which is the case for cellular phones where the gravitation axis can be measured). Experimental results show that compared to standard RANSAC methods based on minimal solvers, our algorithm produces more accurate estimates in the presence of large outlier ratios.

In this paper, we study the problems of estimating relative pose between two cameras in the presence of radial distortion. Specifically, we consider minimal problems where one of the cameras has no or known radial distortion. There are three useful cases for this setup with a single unknown distortion: (i) fundamental matrix estimation where the two cameras are uncalibrated, (ii) essential matrix estimation for a partially calibrated camera pair, (iii) essential matrix estimation for one calibrated camera and one camera with unknown focal length. We study the parameterization of these three problems and derive fast polynomial solvers based on Gröbner basis methods. We demonstrate the numerical stability of the solvers on synthetic data. The minimal solvers have also been applied to real imagery with convincing results.

We consider the problem of localizing a novel image in a large 3D model. In principle, this is just an instance of camera pose estimation, but the scale introduces some challenging problems. For one, it makes the correspondence problem very difficult and it is likely that there will be a significant rate of outliers to handle. In this paper we use recent theoretical as well as technical advances to tackle these problems. Many modern cameras and phones have gravitational sensors that allow us to reduce the search space. Further, there are new techniques to efficiently and reliably deal with extreme rates of outliers. We extend these methods to camera pose estimation by using accurate approximations and fast polynomial solvers. Experimental results are given demonstrating that it is possible to reliably estimate the camera pose despite more than 99% of outlier correspondences.

One of the major research areas in computer vision is scene reconstruction from image streams. The advent of RGB-D cameras, such as the Microsoft Kinect, has lead to new possibilities for performing accurate and dense 3D reconstruction. There are already well-working algorithms to acquire 3D models from depth sensors, both for large and small scale scenes. However, these methods often break down when the scene geometry is not so informative, for example, in the case of planar surfaces. Similarly, standard image-based methods fail for texture-less scenes. We combine both color and depth measurements from an RGB-D sensor to simultaneously reconstruct both the camera motion and the scene geometry in a robust manner. Experiments on real data show that we can accurately reconstruct large-scale 3D scenes despite many planar surfaces.

This paper is concerned with model fitting in the presence of noise and outliers. Previously it has been shown that the number of outliers can be minimized with polynomial complexity in the number of measurements. This paper improves on these results in two ways. First, it is shown that for a large class of problems, the statistically more desirable truncated L2-norm can be optimized with the same complexity. Then, with the same methodology, it is shown how to transform multi-model fitting into a purely combinatorial problem-with worst-case complexity that is polynomial in the number of measurements, though exponential in the number of models. We apply our framework to a series of hard registration and stitching problems demonstrating that the approach is not only of theoretical interest. It gives a practical method for simultaneously dealing with measurement noise and large amounts of outliers for fitting problems with low-dimensional models.

This paper describes a method of finding thin, elongated structures in images and volumes. We use shortest paths to minimize very general functionals of higher-order curve properties, such as curvature and torsion. Our globally optimal method uses line graphs and its runtime is polynomial in the size of the discretization, often in the order of seconds on a single computer. To our knowledge, we are the first to perform experiments in three dimensions with curvature and torsion regularization. The largest graphs we process have almost one hundred billion arcs. Experiments on medical images and in multi-view reconstruction show the significance and practical usefulness of regularization based on curvature while torsion is still only tractable for small-scale problems.

We introduce a multi-region model for simultaneous segmentation of medical images. In contrast to many other models, geometric constraints such as inclusion and exclusion between the regions are enforced, which makes it possible to correctly segment different regions even if the intensity distributions are identical. We efficiently optimize the model using a combination of graph cuts and Lagrangian duality which is faster and more memory efficient than current state of the art. As the method is based on global optimization techniques, the resulting segmentations are independent of initialization. We apply our framework to the segmentation of the left and right ventricles, myocardium and the left ventricular papillary muscles in magnetic resonance imaging and to lung segmentation in full-body X-ray computed tomography. We evaluate our approach on a publicly available benchmark with competitive results.

Is the real problem in finding the relative orientation of two viewpoints the correspondence problem? We argue that this is only one difficulty. Even with known correspondences, popular methods like the eight point algorithm and minimal solvers may break down due to planar scenes or small relative motions. In this paper, we derive a simple, brute-force algorithm which is both robust to outliers and has no such algorithmic degeneracies. Several cost functions are explored including maximizing the consensus set and robust norms like truncated least-squares. Our method is based on parameter search in a four-dimensional space using a new epipolar parametrization. In principle, we do an exhaustive search of parameter space, but the computations are very simple and easily parallelizable, resulting in an efficient method. Further speed-ups can be obtained by restricting the domain of possible motions to, for example, planar motions or small rotations. Experimental results are given for a variety of scenarios including scenes with a large portion of outliers. Further, we apply our algorithm to 3D motion segmentation where we outperform state-of-the-art on the well-known Hopkins-155 benchmark database.

The number of applications in computer vision that model higher-order interactions has exploded over the last few years. The standard technique for solving such problems is to reduce the higher-order objective function to a quadratic pseudo-boolean function, and then use roof duality for obtaining a lower bound. Roof duality works by constructing the tightest possible lower-bounding submodular function, and instead of optimizing the original objective function, the relaxation is minimized. We generalize this idea to polynomials of higher degree, where quadratic roof duality appears as a special case. Optimal relaxations are defined to be the ones that give the maximum lower bound. We demonstrate that important properties such as persistency still hold and how the relaxations can be efficiently constructed for general cubic and quartic pseudo-boolean functions. From a practical point of view, we show that our relaxations perform better than state-of-the-art for a wide range of problems, both in terms of lower bounds and in the number of assigned variables.

Graph cuts methods are at the core of many state-of-the-art algorithms in computer vision due to their efficiency in computing globally optimal solutions. In this paper, we solve the maximum flow/minimum cut problem in parallel by splitting the graph into multiple parts and hence, further increase the computational efficacy of graph cuts. Optimality of the solution is guaranteed by dual decomposition, or more specifically, the solutions to the subproblems are constrained to be equal on the overlap with dual variables. We demonstrate that our approach both allows (i) faster processing on multi-core computers and (ii) the capability to handle larger problems by splitting the graph across multiple computers on a distributed network. Even though our approach does not give a theoretical guarantee of speedup, an extensive empirical evaluation on several applications with many different data sets consistently shows good performance. An open source implementation of the dual decomposition method is also made publicly available.

We study geometric reconstruction problems in one-dimensional retina vision. In such problems, the scene is modeled as a two-dimensional plane, and the camera sensor produces one-dimensional images of the scene. Our main contribution is an efficient method for computing the global optimum to the structure and motion problem with respect to the $L_{\infty}$ norm of the reprojection errors. One-dimensional cameras have proven useful in several applications, most prominently for autonomous vehicles, where they are used to provide inexpensive and reliable navigational systems. Previous results on one-dimensional vision are limited to the classification and solving of minimal cases, bundle adjustment for finding local optima, and linear algorithms for algebraic cost functions. In contrast, we present an approach for finding globally optimal solutions with respect to the $L_{\infty}$ norm of the angular reprojection errors. We show how to solve intersection and resection problems as well as the problem of simultaneous localization and mapping (SLAM). The algorithm is robust to use when there are missing data, which means that all points are not necessarily seen in all images. Our approach has been tested on a variety of different scenarios, both real and synthetic. The algorithm shows good performance for intersection and resection and for SLAM with up to five views. For more views the high dimension of the search space tends to give long running times. The experimental section also gives interesting examples showing that for one-dimensional cameras with limited field of view the SLAM problem is often inherently ill-conditioned.

We study the relative orientation problem for two calibrated cameras with outliers from the feature matching. In recent years there has been a growing interest in optimal algorithms for computer vision. Most people agree that to get accurate solutions to multiview geometry problems, an appropriate norm of the reprojection errors should be minimized. To this end local as well as global optimization methods have been employed. To handle outliers though, heuristic methods still dominate the field. In this paper we address the problem of estimating relative orientation from uncertain feature correspondences. We formulate this task as an optimization problem and propose a branchand-bound algorithm to find the optimal set of correspondences as well as the optimal relative orientation. The approach is based on geometric constraints for pairs of correspondences. The experimental results are promising, especially for omnidirectional cameras. An implementation of the algorithm is also made publicly available to facilitate further research.

Work in multiple view geometry has focused on obtaining globally optimal solutions at the price of computational time efficiency. On the other hand, traditional bundle adjustment algorithms have been found to provide good solutions even though there may be multiple local minima. In this paper we justify this observation by giving a simple sufficient condition for global optimality that can be used to verify that a solution obtained from any local method is indeed global. The method is tested on numerous problem instances of both synthetic and real data sets. In the vast majority of cases we are able to verify that the solutions are optimal, in particular for small-scale problems. We also develop a branch and bound procedure that goes beyond verification. In cases where the sufficient condition does not hold, the algorithm returns either of the following two results: (i) a certificate of global optimality for the local solution or (ii) the global solution.

Correspondence problems are of great importance in computer vision. They appear as subtasks in many applications such as object recognition, merging partial 3D reconstructions and image alignment. Automatically matching features from appearance only is difficult and errors are frequent. Thus, it is necessary to use geometric consistency to remove incorrect correspondences. Typically heuristic methods like RANSAC or EM-like algorithms are used, but they risk getting trapped in local optima and are in no way guaranteed to find the best solution. This paper illustrates how pairwise constraints in combination with graph methods can be used to efficiently find optimal correspondences. These ideas are implemented on two basic geometric problems, 3D-3D registration and 2D-3D registration. The developed scheme can handle large rates of outliers and cope with multiple hypotheses. Despite the combinatorial explosion, the resulting algorithm which has been extensively evaluated on real data, yields competitive running times compared to state of the art.

The concept of graph cuts is by now a standard method for all sorts of low level vision problems. Its popularity is largely due to the fact that globally or near globally optimal solutions can be computed using efficient max flow algorithms. On the other hand it has been observed that this method may suffer from metrication errors. Recent work has begun studying continuous versions of graph cuts, which give smaller metrication errors. Another advantage is that continuous cuts are straightforward to parallelize. In this paper we extend the class of functionals that can be optimized in the continuous setting to include anisotropic TV-norms. We show that there is a so called coarea formula for these functionals making it possible to minimize them by solving a convex problem. We also show that the concept of a-expansion moves can be reformulated to fit the continuous formulation, and we derive approximation bounds in analogy with the discrete case. A continuous version of the Potts model for multi-class segmentation problems is presented, and it is shown how to obtain provably good solutions using continuous α-expansions.

We consider a class of region-based energies for image segmentation and inpainting which combine region integrals with curvature regularity of the region boundary. To minimize such energies, we formulate an integer linear program which jointly estimates regions and their boundaries. Curvature regularity is imposed by respective costs on pairs of adjacent boundary segments. By solving the associated linear programming relaxation and thresholding the solution one obtains an approximate solution to the original integer problem. To our knowledge this is the first approach to impose curvature regularity in region-based formulations in a manner that is independent of initialization and allows to compute a bound on the optimal energy. In a variety of experiments on segmentation and inpainting, we demonstrate the advantages of higher-order regularity. Moreover, we demonstrate that for most experiments the optimality gap is smaller than 2% of the global optimum. For many instances we are even able to compute the global optimum.

One of the key factors for the success of recent energy minimization methods is that they seek to compute global solutions. Even for non-convex energy functionals, optimization methods such as graph cuts have proven to produce high-quality solutions by iterative minimization based on large neighborhoods, making them less vulnerable to local minima. Our approach takes this a step further by enlarging the search neighborhood with one dimension. In this paper we consider binary total variation problems that depend on an additional set of parameters. Examples include: (i) the Chan-Vese model that we solve globally (ii) ratio and constrained minimization which can be formulated as parametric problems, and (iii) variants of the Mumford-Shah functional. Our approach is based on a recent theorem of Chambolle which states that solving a one-parameter family of binary problems amounts to solving a single convex variational problem. We prove a generalization of this result and show how it can be applied to parametric optimization.

In this paper, we propose a practical and efficient method for finding the globally optimal solution to the problem of determining the pose of an object. We present a framework that allows us to use point-to-point, point-to-line, and point-to-plane correspondences for solving various types of pose and registration problems involving euclidean (or similarity) transformations. Traditional methods such as the iterative closest point algorithm or bundle adjustment methods for camera pose may get trapped in local minima due to the nonconvexity of the corresponding optimization problem. Our approach of solving the mathematical optimization problems guarantees global optimality. The optimization scheme is based on ideas from global optimization theory, in particular convex underestimators in combination with branch-and-bound methods. We provide a provably optimal algorithm and demonstrate good performance on both synthetic and real data. We also give examples of where traditional methods fail due to the local minima problem.

We present a framework for computing optimal transformations, aligning one point set to another, in the presence of outliers. Example applications include shape matching and registration (using, for example, similarity, affine or projective transformations) as well as multiview reconstruction problems (triangulation, camera pose etc.). While standard methods like RANSAC essentially use heuristics to cope with outliers, we seek to find the largest possible subset of consistent correspondences and the globally optimal transformation aligning the point sets. Based on theory from computational geometry, we show that this is indeed possible to accomplish in polynomial-time. We develop several algorithms which make efficient use of convex programming. The scheme has been tested and evaluated on both synthetic and real data for several applications.

This paper presents a new framework for solving geometric structure and motion problems based on Linfinity-norm. Instead of using the common sum-of-squares cost-function, that is, the L2-norm, the model-fitting errors are measured using the L-norm. Unlike traditional methods based on L2, our framework allows for efficient computation of global estimates. We show that a variety of structure and motion problems, for example, triangulation, camera resectioning and homography estimation can be recast as quasi-convex optimization problems within this framework. These problems can be efficiently solved using Second-Order Cone Programming (SOCP) which is a standard technique in convex optimization. The methods have been implemented in Matlab and the resulting toolbox has been made publicly available. The algorithms have been validated on real data in different settings on problems with small and large dimensions and with excellent performance.

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.

Where am I and what am I seeing? This is a classical vision problem and this paper presents a solution based on efficient use of a combination of 2D and 3D features. Given a model of a scene, the objective is to find the relative camera location of a new input image. Unlike traditional hypothesize-and-test methods that try to estimate the unknown camera position based on 3D model features only, or alternatively, based on 2D model features only, we show that using a mixture of such features, that is, a hybrid correspondence set, may improve performance. We use minimal cases of structure-from-motion for hypothesis generation in a RANSAC engine. For this purpose, several new and useful minimal cases are derived for calibrated, semi-calibrated and uncalibrated settings. Based on algebraic geometry methods, we show how these minimal hybrid cases can be solved efficiently. The whole approach has been validated on both synthetic and real data, and we demonstrate improvements compared to previous work.

In this paper we introduce two new methods for solving binary quadratic problems. While spectral relaxation methods have been the workhorse subroutine for a wide variety of computer vision problems - segmentation, clustering, image restoration to name a few - it has recently been challenged by semidefinite programming (SDP) relaxations. In fact, it can be shown that SDP relaxations produce better lower bounds than spectral relaxations on binary problems with a quadratic objective function. On the other hand, the computational complexity for SDP increases rapidly as the number of decision variables grows making them inapplicable to large scale problems. Our methods combine the merits of both spectral and SDP relaxations -better (lower) bounds than traditional spectral methods and considerably faster execution times than SDP. The first method is based on spectral subgradients and can be applied to large scale SDPs with binary decision variables and the second one is based on the trust region problem. Both algorithms have been applied to several large scale vision problems with good performance.

The structure and motion problem of multiple one-dimensional projections of a two-dimensional environment is studied. One-dimensional cameras have proven useful in several different applications, most prominently for autonomous guided vehicles, but also in ordinary vision for analysing planar motion and the projection of lines. Previous results on one-dimensional vision are limited to classifying and solving minimal cases, bundle adjustment for finding local minima to the structure and motion problem and linear algorithms based on algebraic cost functions. In this paper, we present a method for finding the global minimum to the structure and motion problem using the max norm of reprojection errors. We show how the optimal solution can be computed efficiently using simple linear programming techniques. The algorithms have been tested on a variety of different scenarios, both real and synthetic, with good performance. In addition, we show how to solve the multiview triangulation problem, the camera pose problem and how to dualize the algorithm in the Carlsson duality sense, all within the same framework.

Indisputably Normalized Cuts is one of the most popular segmentation algorithms in computer vision. It has been applied to a wide range of segmentation tasks with great success. A number of extensions to this approach have also been proposed, ones that can deal with multiple classes or that can incorporate a priori information in the form of grouping constraints. However, what is common for all these suggested methods is that they are noticeably limited and can only address segmentation problems on a very specific form. In this paper, we present a reformulation of Normalized Cut segmentation that in a unified way can handle all types of linear equality constraints for an arbitrary number of classes. This is done by restating the problem and showing how linear constraints can be enforced exactly through duality. This allows us to add group priors, for example, that certain pixels should belong to a given class. In addition, it provides a principled way to perform multi-class segmentation for tasks like interactive segmentation. The method has been tested on real data with convincing results.

This paper extends the set of problems for which a global solution can be found using modern optimization methods. In particular, the method is applied to estimation of the essential matrix, giving the first guaranteed optimal algorithm for estimating the relative pose under a geometric cost function, in this case, the L-infinity cost function. Convex optimization techniques has been shown to provide optimal solutions to many of the common problems in structure from motion. However, they do not apply to problems involving rotations. In this paper, we introduce a search method that allows such problems to be solved optimally. Apart from the essential matrix, the algorithm is applied to the camera pose problem, providing an optimal algorithm.

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 consider the problem of solving geometric reconstruction problems with the L∞-norm. Previous work has shown that globally optimal solutions can be computed reliably for a series of such problems. The methods for computing the solutions have relied on the property of quasiconvexity. For quasiconvex problems, checking if there exists a solution below a certain objective value can be posed as a convex feasibility problem. To solve the L∞-problem one typically employs a bisection algorithm, generating a sequence of convex problems. In this paper we present more efficient ways of computing the solutions. We derive necessary and sufficient conditions for a global optimum. A key property is that of pseudoconvexity, which is a stronger condition than quasiconvexity. The results open up the possibility of using local optimization methods for more efficient computations. We present two such algorithms. The first one is an interior point method that uses the KKT conditions and the second one is similar to the bisection method in the sense it solves a sequence of SOCP problems. Results are presented and compared to the standard bisection algorithm on real data for various problems and scenarios with improved performance.

In this paper we propose a practical and efficient method for finding the globally optimal solution to the problem of pose estimation of a known object. We present a framework that allows us to use both point-to-point, point-to-line and point-to-plane correspondences in the optimization algorithm. Traditional methods such as the iterative closest point algorithm may get trapped in local minima due to the non-convexity of the problem, however, our approach guarantees global optimality. The approach is based on ideas from global optimization theory, in particular, convex under-estimators in combination with branch and bound. We provide a provably optimal algorithm and demonstrate good performance on both synthetic and real data.

Prior work has argued that when a Lambertian surface in fixed pose is observed in multiple images under varying distant illumination, there is an equivalence class of surfaces given by the generalized bas-relief (GBR) ambiguity that could have produced these images. In contrast, this paper shows that for general nonconvex surfaces, interreflections completely resolve the GBR ambiguity. In turn, the full Euclidean geometry can be recovered from uncalibrated photometric stereo for which the light source directions and strengths are unknown. Further, we show that surfaces with a translational symmetry do not lend enough constraints to be disambiguated by inter reflections.

The problem of feature-based surface reconstruction is considered in this paper. Our main contribution is the ability to handle visibility constraints, obtained from the projections of points, curves and silhouettes, in the surface fitting process. While traditional methods often ignore such information, we show that visibility constraints not only give better initial surface estimates and faster convergence, but also provide an important cue for determining surface topology. The problem is cast as a variational problem with constraints within the level set framework. It is shown how to evolve the surface without violating the visibility constraints using methods from variational calculus. Applications of the theory are detailed for a number of important cases of geometric primitives: points, curves and visual hulls. Several experiments on real image sequences are given to demonstrate the performance of the approach.

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.

This paper presents a new framework for solving geometric structure and motion problems based on L/sub /spl infin//-norm. Instead of using the common sum-of-squares cost-function, that is, the L/sub /spl infin//-norm, the model-fitting errors are measured using the L/sub /spl infin//-norm. Unlike traditional methods based on L/sub 2/ our framework allows for efficient computation of global estimates. We show that a variety of structure and motion problems, for example, triangulation, camera resectioning and homography estimation can be recast as a quasiconvex optimization problem within this framework. These problems can be efficiently solved using second order cone programming (SOCP) which is a standard technique in convex optimization. The proposed solutions have been validated on real data in different settings with small and large dimensions and with excellent performance.

We introduce a framework for computing statistically optimal estimates of geometric reconstruction problems. While traditional algorithms often suffer from either local minima or nonoptimality - or a combination of both - we pursue the goal of achieving global solutions of the statistically optimal cost-function. Our approach is based on a hierarchy of convex relaxations to solve nonconvex optimization problems with polynomials. These convex relaxations generate a monotone sequence of lower bounds and we show how one can detect whether the global optimum is attained at a given relaxation. The technique is applied to a number of classical vision problems: triangulation, camera pose, homography estimation and last, but not least, epipolar geometry estimation. Experimental validation on both synthetic and real data is provided. In practice, only a few relaxations are needed for attaining the global optimum

We consider the problem of geometrical surface reconstruction from one or several images using learned shape models. While humans can effort- lessly retrieve 3D shape information, this inverse problem has turned out to be difficult to perform automatically. We introduce a framework based on level set surface reconstruction and shape models for achieving this goal. Through this merging, we obtain an efficient and robust method for reconstructing surfaces of an object category of interest. The shape model includes surface cues such as point, curve and silhou- ette features. Based on ideas from Active Shape Models, we show how both the geometry and the appearance of these features can be modelled consistently in a multi-view context. The complete surface is obtained by evolving a level set driven by a PDE, which tries to fit the surface to the inferred 3D features. In addition, an a priori 3D surface model is used to regularize the solution, in particular, where surface features are sparse. Experiments are demonstrated on a database of real face images.

We address the problem of aligning two reconstructions of lines and cameras in projective, affine, metric or Euclidean space. We propose several 3D (three-dimensional) and image-related linear algorithms. The result can be used to initialize the nonlinear minimization of several proposed error functions, as well as the maximum likelihood estimator that we derive. We evaluate and compare our algorithms to existing ones using simulated and real data.

This paper investigates critical configurations for projective reconstruction from multiple images taken by a camera moving in a straight line. Projective reconstruction refers to a determination of the 3D (three-dimensional) geometrical configuration of a set of 3D points and cameras, given only correspondences between points in the images. A configuration of points and cameras is critical if it cannot be determined uniquely (up to a projective transform) from the image coordinates of the points. It is shown that a configuration consisting of any number of cameras lying on a straight line, and any number of points lying on a twisted cubic constitutes a critical configuration. An alternative configuration consisting of a set of points and cameras all lying on a rational quartic curve exists.

Is the real problem in resolving correspondence using current stereo algorithms the lack of the "right" matching criterion? In studying the related task of reconstructing three-dimensional space curves from their projections in multiple views, we suggest that the problem is more basic: matching and reconstruction are coupled, and so reconstruction algorithms should exploit this rather than assuming that matching can be successfully performed before reconstruction. To realize this coupling, a generative model of curves is introduced which has two key components: (i) a prior distribution of general space curves and (ii) an image formation model which describes how 3D curves are projected onto the image plane. A novel aspect of the image formation model is that it uses an exact description of the gradient field of a piecewise constant image. Based on this forward model, a fully automatic algorithm for solving the inverse problem is developed for an arbitrary number of views. The resulting algorithm is robust to partial occlusion, deficiencies in image curve extraction and it does not rely on photometric information. The relative motion of the cameras is assumed to be given. Several experiments are carried out on various realistic scenarios. In particular, we focus on scenes where traditional correlation-based methods would fail.

Traditionally, building 3D reconstructions of large scenarios such as a museum or historical site has been costly, time consuming and required the contribution of expert personnel. Usually the results showed an artificial look and had little interactivity. However, newly developed technologies in the areas of video analysis, camera calibration and texture fusion allow us to think in a much more satisfying scenario where the user with the only aid of a domestic video camera is able to acquire all the information it is required to construct the 3D model of the desired environment in an easy and comfortable manner. In this paper, the results obtained in the EC funded project VISIRE are presented. VISIRE attempts to construct photorealistic 3D models of large scenarios using as input multiple freehand video sequences. Once acquired, the computer vision software processes the video information off-line in order to obtain the 3D mesh together with the textures required to obtain a 3D model highly resembling the original.

In this paper we examine the ambiguities between extrinsic and intrinsic parameters in the uncalibrated structure and motion problem. The Jacobian J of the reprojection error is considered, treating each camera separately. Ambiguities correspond to linear dependencies in the column space of J and we thus detect and quantify these by using the condition number of selected combinations of columns of J. When the presence of an ambiguity has been detected, we automatically select a constraint (e.g. constant principal point, or a regularity constraint on the camera motion) that resolves this ambiguity. As a by-product we also obtain a better separation between intrinsic and extrinsic parameters. The proposed method is demonstrated on both synthetic and real data, with good performance.

In this paper we give a characterization of critical configurations for projective reconstruction with any number of points and views. A set of cameras and points is said to be critical if the projected image points are insufficient to determine the placement of the points and the cameras uniquely, up to a projective transformation. For two views, the critical configurations are well-known. In this paper it is shown that a configuration of n 3 cameras and in points all lying on the intersection of two distinct ruled quadrics is critical. In distinction to the two-view case, which in general allows two alternative solutions, there is a family of ambiguous reconstructions for the n-view case. As a partial converse, it Is shown that for any critical configuration, all the points lie on the intersection of two ruled quadrics.

This paper deals with the problem of incorporating natural regularity conditions on the motion in an MAP estimator for structure and motion recovery from uncalibrated image sequences. The purpose of incorporating these constraints is to increase performance and robustness. Auto-calibration and structure and motion algorithms are known to have problems with (i) the frequently occurring critical camera motions, (ii) local minima in the non-linear optimization and (iii) the high correlation between different intrinsic and extrinsic parameters of the camera, e.g. the coupling between focal length and camera position. The camera motion (both intrinsic and extrinsic parameters) is modelled as a random walk process, where the inter-frame motions are assumed to be independently normally distributed. The proposed scheme is demonstrated on both simulated and real data showing the increased performance.

The minimal data necessary for projective reconstruction from image points is well-known when each object point is visible in all images. We formulate and propose solutions to a family of reconstruction problems for multiple images from minimal data, where there are missing points in some of the images. The ability to handle the minimal cases with missing data is of great theoretical and practical importance. It is unavoidable to use them to bootstrap robust estimation such as RANSAC and LMS algorithms and optimal estimation such as bundle adjustment. First, we develop a framework to parameterize the multiple view geometry needed to handle the missing data cases. Then, we present a solution to the minimal case of eight points in three images, where one different point is missing in each of the three images. We prove that there are, in general, as many as 11 solutions for this minimal case. Furthermore all minimal cases with missing data for three and four images are catalogued. Finally, we demonstrate the method on both simulated and real images and show that the algorithms presented in the paper can be used for practical problems.

This paper presents a novel method for structure and motion estimation from affine cameras, called direct affine reconstruction (DAR). The main contribution is a deeper theoretical understanding of multiple view geometry for affine cameras. This is accomplished by carefully selecting a specific coordinate system, based on relative affine coordinates. One consequence of the choice of coordinates is that it is possible to directly read out the camera matrices as well as the object coordinates from the image measurements. The proposed method is well suited for tracking purposes as well as robust estimation schemes, like RANSAC, since only four basis points are needed. Furthermore, since no costly calculations are involved, the method is very fast. Experiments are carried out on both simulated and real data, showing its relative performance against factorization.

We investigate the motions that lead to ambiguous Euclidean scene reconstructions under several common calibration constraints, giving a complete description of such critical motions for: (i) internally calibrated orthographic and perspective cameras; (ii) in two images, for cameras with unknown focal lengths, either different or equal. One aim of the work was to evaluate the potential of modern algebraic geometry tools for rigorously proving properties of vision algorithms, so we use ideal theoretic calculations as well as classical algebra and geometry. We also present numerical experiments showing the effects of near-critical configurations for the varying and fixed focal length methods.

The minimal data necessary for projective reconstruction from point correspondences is well-known when the points are visible in all images. In this paper, we formulate and propose solutions to a new family of reconstruction problems from multiple images with minimal data, where there are missing points in some of the images. The ability to handle the minimal cases with missing data is of great theoretical and practical importance. It is unavoidable to use them to bootstrap robust estimation such as RANSAC and LMS algorithms and optimal estimation such as bundle adjustment. First, we develop a framework to parametrize the multiple view geometry, needed to handle the missing data cases. Then we present a solution to the minimal case of 8 points in 3 images, where one of the points is missing in one of the three images. We prove that there are in general as many as 11 solutions for this minimal case. Furthermore, all minimal cases with missing data for 3 and 4 in images are catalogued. Finally we demonstrate the method on both simulated and real images and show that the algorithms presented in this paper can be used for practical problems.

The motions that lead to ambiguous Euclidean reconstructions in auto-calibration are investigated. Several auto-calibration constraints are considered: vanishing skew, known aspect ratio and internally calibrated cameras except for unknown focal lengths. We give a complete description of such critical motions in terms of algebraic manifolds and, in many cases, an explicit, geometric description for any number of cameras. For example, in the case of internally calibrated cameras except for unknown focal lengths, the only motions for which an affine reconstruction is ambiguous are either (i) rotations around (at most) two fired camera centres, or (ii) a planar motion on a conic with the optical axis tangent to the conic, or (iii) translation along the optical axis with arbitrary rotations around the optical axis. Moreover some practically important cases are also discussed.

The problem of determining the camera motion from apparent contours or silhouettes of a priori unknown curved 3D surfaces is considered. In a sequence of images, it is shown how to use the generalized epipolar constraint on apparent contours. One such constraint is obtained for each epipolar tangency point in each image pair. An accurate algorithm for computing the motion is presented based on a maximum likelihood estimate. It is shown how to generate initial estimates on the camera motion using only the tracked contours. It is also shown that in theory the motion can be calculated from the deformation of a single contour. The algorithm has been tested on several real image sequences, for both Euclidean and projective reconstruction. The resulting motion estimate is compared to motion estimates calculated independently using standard feature-based methods. The motion estimate is also used to classify the silhouettes as curves or apparent contours. The statistical evaluation shows that the technique gives accurate and stable results.

The problem of determining the camera motion from apparent contours or silhouettes of curved three-dimensional surfaces is considered. In a sequence of images is shown how to use the generalized epipolar constraint on apparent contours. One such constraint is obtained for each epipolar tangency point in each image pair. Thus in theory the motion can be calculated from the deformation of a single contour. A robust algorithm for computing the motion is presented based on the maximum likelihood estimate. It is shown how to generate initial estimates on the camera motion using only the tracked contours. It is also shown how to improve this estimate by maximizing the likelihood function. The algorithm has been tested on real image sequences. The result is compared to that of using only point features. The statistical evaluation shows that the technique gives accurate and stable results.

In this paper it is shown hour corresponding conics in two images can be used to estimate the epipolar geometry in terms of the fundamental/essential matrix. The corresponding conics can, be images of either planar celtics or silhouettes of quadrics. It is shown that one conic correspondence gives two independent constraints on the fundamental matrix and a method to estimate the fundamental matrix from at least four corresponding conics is presented. Furthermore, a new type of fundamental matrix for describing conic correspondences is introduced. Finally, it is shown that the problem of estimating the fundamental matrix from 5 point correspondences and 1 conic correspondence in general has 10 different solutions. A method to calculate these solutions is also given together with an experimental validation.

This paper outlines a new method that makes reconstruction from an image sequence taken by affine cameras. The method is based on the so called closure constraints that link the camera matrices to the different affine quasi-tensors. This method can easily handle missing data and not only points, but also lines and conics are used to constrain the reconstruction. The method works in three steps: 1) the second or third order affine quasi-tensors are estimated from corresponding points, lines and conics in two or three images; 2) all available quasi-tensor components are used to calculate the camera matrices using the closure constraints; and 3) the reconstruction is obtained by intersection. When using the second order quasi-tensors, it is sufficient to estimate the quasi-tensors between images i and i+1 and between images i and i+2. In the case of the third order quasi-tensors, it is sufficient to use every successive triplets of images. Finally, the method is illustrated on real data.

A new approach to self-calibration and Euclidean reconstruction from image sequences is presented. The key idea is to start with the affine camera model as a first approximation to obtain the affine 3D structure. It is then upgraded to an Euclidean structure and finally, refined by applying the full perspective camera model and bundle adjustment. The proposed scheme makes no assumption about the scene nor the camera motion. The only assumption required is that the camera has zero skew, which is a minimal condition in order to self-calibrate the camera. However, if other information is available about the camera, it can and should be incorporated. The method is robust and it also provides an estimate of the accuracy of the estimated parameters. Experiments are presented to illustrate the performance of the approach.