We present nonlinear formulations to Shape-from-Template (SfT) and Non-Rigid Structure-from-Motion (NRSfM) faithfully exploiting the isometric, conformal and equiareal deformation models. Existing work uses relaxations such as inextensibility or requires knowing the optic flow field around the correspondences, an impractical assumption. In contrast, the proposed formulations only require point correspondences and resolve all ambiguities using the notions of maximal depth and maximal isometry heuristics. We propose solution methods using Semi-Definite Programming (SDP) for all formulations. We show that straightforward SDP models conflict with the usual maximal depth heuristic and propose an adapted opposite-depth parameterisation demonstrating a lesser relaxation gap. Experimental results on many real-world benchmark datasets demonstrate superior accuracy over existing methods.

Augmented reality for laparoscopic liver resection is a visualisation mode that allows a surgeon to localise tumours and vessels embedded within the liver by projecting them on top of a laparoscopic image. Preoperative 3D models extracted from Computed Tomography (CT) or Magnetic Resonance (MR) imaging data are registered to the intraoperative laparoscopic images during this process. Regarding 3D-2D fusion, most algorithms use anatomical landmarks to guide registration, such as the liver's inferior ridge, the falciform ligament, and the occluding contours. These are usually marked by hand in both the laparoscopic image and the 3D model, which is time-consuming and prone to error. Therefore, there is a need to automate this process so that augmented reality can be used effectively in the operating room. We present the Preoperative-to-Intraoperative Laparoscopic Fusion challenge (P2ILF), held during the Medical Image Computing and Computer Assisted Intervention (MICCAI 2022) conference, which investigates the possibilities of detecting these landmarks automatically and using them in registration. The challenge was divided into two tasks: (1) A 2D and 3D landmark segmentation task and (2) a 3D-2D registration task. The teams were provided with training data consisting of 167 laparoscopic images and 9 preoperative 3D models from 9 patients, with the corresponding 2D and 3D landmark annotations. A total of 6 teams from 4 countries participated in the challenge, whose results were assessed for each task independently. All the teams proposed deep learning-based methods for the 2D and 3D landmark segmentation tasks and differentiable rendering-based methods for the registration task. The proposed methods were evaluated on 16 test images and 2 preoperative 3D models from 2 patients. In Task 1, the teams were able to segment most of the 2D landmarks, while the 3D landmarks showed to be more challenging to segment. In Task 2, only one team obtained acceptable qualitative and quantitative registration results. Based on the experimental outcomes, we propose three key hypotheses that determine current limitations and future directions for research in this domain.

In mini-invasive surgery, the laparoscopic ultra-sound probe is visible in the laparoscopic image. We address the problem of estimating the probe pose with respect to the laparoscope without using markers and additional sensors. We propose the first method using a single standard laparoscopic monocular RGB image. It is robust, initialization-free and runs at 10 fps, thus forming a promising tool to improve robotic and augmented reality-based surgery.

Non-Rigid Structure-from-Motion (NRSfM) reconstructs the time-varying 3D shape of a deforming object from 2D point correspondences in monocular images. Despite promising use-cases such as the grasping of deformable objects and visual navigation in a non-rigid environment, NRSfM has had limited applications in robotics due to a lack of accuracy. To remedy this, we propose a new method which boosts the accuracy of NRSfM using sparse surface normals. Surface normal information is available from many sources, including structured lighting, homography decomposition of infinitesimal planes and shape priors. However, these sources are not always available. We thus propose a widely available new source of surface normals: the specularities. Our first technical contribution is a method which detects specular highlights and reconstructs the surface normals from it. It assumes that the light source is approximately localised, which is widely applicable in robotics applications such as endoscopy. Our second technical contribution is an NRSfM method which exploits a sparse surface normal set. For that, we propose a novel convex formulation and a globally optimal solution method. Experiments on photo-realistic synthetic data and real household and medical data show that the proposed method outperforms existing NRSfM methods.1 2 3

We give an effective solution to the regularized optimization problem$g (\boldsymbol{x}) + h (\boldsymbol{x})$, where$\boldsymbol{x}$is constrained on the unit sphere$\Vert \boldsymbol{x} \Vert _{2} = 1$. Here$g (\cdot )$is a smooth cost with Lipschitz continuous gradient within the unit ball$\lbrace \boldsymbol{x} : \Vert \boldsymbol{x} \Vert _{2} \le 1 \rbrace$whereas$h (\cdot )$is typically non-smooth but convex and absolutely homogeneous,e.g.,norm regularizers and their combinations. Our solution is based on the Riemannian proximal gradient, using an idea we callproxy step-size– a scalar variable which we prove is monotone with respect to the actual step-size within an interval. The proxy step-size exists ubiquitously for convex and absolutely homogeneous$h(\cdot )$, and decides the actual step-size and the tangent update in closed-form, thus the complete proximal gradient iteration. Based on these insights, we design a Riemannian proximal gradient method using the proxy step-size. We prove that our method converges to a critical point, guided by a line-search technique based on the$g(\cdot )$cost only. The proposed method can be implemented in a couple of lines of code. We show its usefulness by applying nuclear norm,$\ell _{1}$norm, and nuclear-spectral norm regularization to three classical computer vision problems. The improvements are consistent and backed by numerical experiments.

Cameras on portable devices are manufactured with a rolling-shutter (RS) mechanism, where the image rows (aka. scanlines) are read out sequentially. The unknown camera motions during the imaging process cause the so-called RS effects which are solved by motion assumptions in the literature. In this work, we give a solution to the absolute pose problem free of motion assumptions. We categorically demonstrate that the only requirement is motion smoothness instead of stronger constraints on the camera motion. To this end, we propose a novel mathematical abstraction for RS cameras observing a planar scene, called the scanline-homography, a 3 × 2 matrix with 5 DOFs. We establish the relationship between a scanline-homography and the corresponding plane-homography, a 3 × 3 matrix with 6 DOFs assuming the camera is calibrated. We estimate the scanline-homographies of an RS frame using a smooth image warp powered by B-Splines, and recover the plane-homographies afterwards to obtain the scanline-poses based on motion smoothness. We back our claims with various experiments. Code and new datasets: https://bitbucket.org/clermontferrand/planarscanlinehomography/src/master/.

Shape-from-Template (SfT) solves 3D vision from a single image and a deformable 3D object model, called a template. Concretely, SfT computes registration (the correspondence between the template and the image) and reconstruction (the depth in camera frame). It constrains the object deformation to quasi-isometry. Real-time and automatic SfT represents an open problem for complex objects and imaging conditions. We present four contributions to address core unmet challenges to realise SfT with a Deep Neural Network (DNN). First, we propose a novel DNN called DeepSfT, which encodes the template in its weights and hence copes with highly complex templates. Second, we propose a semi-supervised training procedure to exploit real data. This is a practical solution to overcome the render gap that occurs when training only with simulated data. Third, we propose a geometry adaptation module to deal with different cameras at training and inference. Fourth, we combine statistical learning with physics-based reasoning. DeepSfT runs automatically and in real-time and we show with numerous experiments and an ablation study that it consistently achieves a lower 3D error than previous work. It outperforms in generalisation and achieves great performance in terms of reconstruction and registration error with wide-baseline, occlusions, illumination changes, weak texture and blur.

Non-Rigid Structure-from-Motion (NRSfM) reconstructs a deformable 3D object from keypoint correspondences established between monocular 2D images. Current NRSfM methods lack statistical robustness, which is the ability to cope with correspondence errors. This prevents one to use automatically established correspondences, which are prone to errors, thereby strongly limiting the scope of NRSfM. We propose a three-step automatic pipeline to solve NRSfM robustly by exploiting isometry. Step (i) computes the optical flow from correspondences, step (ii) reconstructs each 3D point's normal vector using multiple reference images and integrates them to form surfaces with the best reference and step (iii) rejects the 3D points that break isometry in their local neighborhood. Importantly, each step is designed to discard or flag erroneous correspondences. Our contributions include the robustification of optical flow by warp estimation, new fast analytic solutions to local normal reconstruction and their robustification, and a new scale-independent measure of 3D local isometric coherence. Experimental results show that our robust NRSfM method consistently outperforms existing methods on both synthetic and real datasets.

Background and objective: Surgical tool detection, segmentation, and 3D pose estimation are crucial components in Computer-Assisted Laparoscopy (CAL). The existing frameworks have two main limitations. First, they do not integrate all three components. Integration is critical; for instance, one should not attempt computing pose if detection is negative. Second, they have highly specific requirements, such as the availability of a CAD model. We propose an integrated and generic framework whose sole requirement for the 3D pose is that the tool shaft is cylindrical. Our framework makes the most of deep learning and geometric 3D vision by combining a proposed Convolutional Neural Network (CNN) with algebraic geometry. We show two applications of our framework in CAL: tool-aware rendering in Augmented Reality (AR) and tool-based 3D measurement. Methods: We name our CNN as ART-Net (Augmented Reality Tool Network). It has a Single Input Multiple Output (SIMO) architecture with one encoder and multiple decoders to achieve detection, segmentation, and geometric primitive extraction. These primitives are the tool edge-lines, mid-line, and tip. They allow the tool’s 3D pose to be estimated by a fast algebraic procedure. The framework only proceeds if a tool is detected. The accuracy of segmentation and geometric primitive extraction is boosted by a new Full resolution feature map Generator (FrG). We extensively evaluate the proposed framework with the EndoVis and new proposed datasets. We compare the segmentation results against several variants of the Fully Convolutional Network (FCN) and U-Net. Several ablation studies are provided for detection, segmentation, and geometric primitive extraction. The proposed datasets are surgery videos of different patients. Results: In detection, ART-Net achieves 100.0 % in both average precision and accuracy. In segmentation, it achieves 81.0 % in mean Intersection over Union (mIoU) on the robotic EndoVis dataset (articulated tool), where it outperforms both FCN and U-Net, by 4.5 p p and 2.9 p p , respectively. It achieves 88.2 % in mIoU on the remaining datasets (non-articulated tool). In geometric primitive extraction, ART-Net achieves 2.45 ∘ and 2.23 ∘ in mean Arc Length (mAL) error for the edge-lines and mid-line, respectively, and 9.3 pixels in mean Euclidean distance error for the tool-tip. Finally, in terms of 3D pose evaluated on animal data, our framework achieves 1.87 mm, 0.70 mm, and 4.80 mm mean absolute errors on the X , Y , and Z coordinates, respectively, and 5 . 94 ∘ angular error on the shaft orientation. It achieves 2.59 mm and 1.99 mm in mean and median location error of the tool head evaluated on patient data. Conclusions: The proposed framework outperforms existing ones in detection and segmentation. Compared to separate networks, integrating the tasks in a single network preserves accuracy in detection and segmentation but substantially improves accuracy in geometric primitive extraction. Overall, our framework has similar or better accuracy in 3D pose estimation while largely improving robustness against the very challenging imaging conditions of laparoscopy. The source code of our framework and our annotated dataset will be made publicly available at https://github.com/kamruleee51/ART-Net .

A major research area in Computer Assisted Intervention (CAI) is to aid laparoscopic surgery teams with Augmented Reality (AR) guidance. This involves registering data from other modalities such as MR and fusing it with the laparoscopic video in real-time, to reveal the location of hidden critical structures. We present the first system for AR guided laparoscopic surgery of the uterus. This works with pre-operative MR or CT data and monocular laparoscopes, without requiring any additional interventional hardware such as optical trackers. We present novel and robust solutions to two main sub-problems: the initial registration, which is solved using a short exploratory video, and update registration, which is solved with real-time tracking-by-detection. These problems are challenging for the uterus because it is a weakly-textured, highly mobile organ that moves independently of surrounding structures. In the broader context, our system is the first that has successfully performed markerless real-time registration and AR of a mobile human organ with monocular laparoscopes in the OR.

Monocular simultaneous localization and mapping (SLAM) algorithms perform robustly when observing rigid scenes; however, they fail when the observed scene deforms, for example, in medical endoscopy applications. In this article, we present DefSLAM, the first monocular SLAM capable of operating in deforming scenes in real time. Our approach intertwines Shape-from-Template (SfT) and Non-Rigid Structure-from-Motion (NRSfM) techniques to deal with the exploratory sequences typical of SLAM. A deformation tracking thread recovers the pose of the camera and the deformation of the observed map, at frame rate, by means of SfT processing a template that models the scene shape-at-rest. A deformation mapping thread runs in parallel with the tracking to update the template, at keyframe rate, by means of an isometric NRSfM processing a batch of full perspective keyframes. In our experiments, DefSLAM processes close-up sequences of deforming scenes, both in a laboratory-controlled experiment and in medical endoscopy sequences, producing accurate 3-D models of the scene with respect to the moving camera.

We address the monocular visual shape servoing problem. This pushes the challenging visual servoing problem one step further from rigid object manipulation towards deformable object manipulation. Explicitly, it implies deforming the object towards a desired shape in 3D space by robots using monocular 2D vision. We specifically concentrate on a scheme capable of controlling large isometric deformations. Two important open subproblems arise for implementing such a scheme. (P1) Since it is concerned with large deformations, perception requires tracking the deformable object's 3D shape from monocular 2D images which is a severely underconstrained problem. (P2) Since rigid robots have fewer degrees of freedom than a deformable object, the shape control becomes underactuated. We propose a template-based shape servoing scheme in which we solve these two problems. The template allows us to both infer the object's shape using an improved Shape-from-Template algorithm and steer the object's deformation by means of the robots' movements. We validate the scheme via simulations and real experiments.

3D reconstruction of deformable objects using inter-image visual motion from monocular images has been studied under Shape-from-Template (SfT) and Non-Rigid Structure-from-Motion (NRSfM). Most methods have been developed for simple deformation models, primarily isometry. They may treat a surface as a discrete set of points and draw constraints from the points only or they may use a non-parametric representation and use both points and differentials to express constraints. We propose a differential framework based on Cartan's theory of connections and moving frames. It is applicable to SfT and NRSfM, and to deformation models other than isometry. It utilises infinitesimal-level assumptions on the surface's geometry and mappings. It has the following properties. 1) It allows one to derive existing solutions in a simpler way. 2) It models SfT and NRSfM in a unified way. 3) It allows us to introduce a new skewless deformation model and solve SfT and NRSfM for it. 4) It facilitates a generic solution to SfT which does not require deformation modeling. Our framework is complete: it solves deformable 3D reconstruction for a whole class of algebraic deformation models including isometry. We compared our solutions with the state-of-the-art methods and show that ours outperform in terms of both accuracy and computation time.

We present a global and convex formulation for the template-less 3D reconstruction of a deforming object with the perspective camera. We show for the first time how to construct a Second-Order Cone Programming (SOCP) problem for Non-Rigid Structure-from-Motion (NRSfM) using the Maximum-Depth Heuristic (MDH). In this regard, we deviate strongly from the general trend of using affine cameras and factorization-based methods to solve NRSfM, which do not perform well with complex nonlinear deformations. In MDH, the points' depths are maximized so that the distance between neighbouring points in camera space are upper bounded by the geodesic distance. In NRSfM both geodesic and camera space distances are unknown. We show that, nonetheless, given point correspondences and the camera's intrinsics the whole problem can be solved with SOCP. This is the first convex formulation for NRSfM with physical constraints. We further present how robustness and temporal continuity can be included in the formulation to handle outliers and decrease the problem size, respectively. We show with extensive experiments that our methods accurately reconstruct quasi-isometric objects from partial views under articulated and strong deformations. Compared to the previous methods, our approach gives better or similar accuracy. It naturally handles missing correspondences, non-smooth objects and is very simple to implement compared to previous methods, with only one free parameter (the neighbourhood size).

We study Isometric Non-Rigid Shape-from-Motion (Iso-NRSfM): given multiple intrinsically calibrated monocular images, we want to reconstruct the time-varying 3D shape of a thin-shell object undergoing isometric deformations. We show that Iso-NRSfM is solvable from local warps, the inter-image geometric transformations. We propose a new theoretical framework based on the Riemmanian manifold to represent the unknown 3D surfaces as embeddings of the camera's retinal plane. This allows us to use the manifold's metric tensor and Christoffel Symbol (CS) fields. These are expressed in terms of the first and second order derivatives of the inverse-depth of the 3D surfaces, which are the unknowns for Iso-NRSfM. We prove that the metric tensor and the CS are related across images by simple rules depending only on the warps. This forms a set of important theoretical results. We show that current solvers cannot solve for the first and second order derivatives of the inverse-depth simultaneously. We thus propose an iterative solution in two steps. 1) We solve for the first order derivatives assuming that the second order derivatives are known. We initialise the second order derivatives to zero, which is an infinitesimal planarity assumption. We derive a system of two cubics in two variables for each image pair. The sum-of-squares of these polynomials is independent of the number of images and can be solved globally, forming a well-posed problem for $N\geq 3$ images. 2) We solve for the second order derivatives by initialising the first order derivatives from the previous step. We solve a linear system of $4N-4$ equations in three variables. We iterate until the first order derivatives converge. The solution for the first order derivatives gives the surfaces' normal fields which we integrate to recover the 3D surfaces. The proposed method outperforms existing work in terms of accuracy and computation cost on synthetic and real datasets.

Specularities are often problematic in computer vision since they impact the dynamic range of the image intensity. A natural approach would be to predict and discard them using computer graphics models. However, these models depend on parameters which are difficult to estimate (light sources, objects' material properties and camera). We present a geometric model called JOLIMAS: JOint LIght-MAterial Specularity, which predicts the shape of specularities. JOLIMAS is reconstructed from images of specularities observed on a planar surface. It implicitly includes light and material properties, which are intrinsic to specularities. This model was motivated by the observation that specularities have a conic shape on planar surfaces. The conic shape is obtained by projecting a fixed quadric on the planar surface. JOLIMAS thus predicts the specularity using a simple geometric approach with static parameters (object material and light source shape). It is adapted to indoor light sources such as light bulbs and fluorescent lamps. The prediction has been tested on synthetic and real sequences. It works in a multi-light context by reconstructing a quadric for each light source with special cases such as lights being switched on or off. We also used specularity prediction for dynamic retexturing and obtained convincing rendering results. Further results are presented as supplementary video material, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/10.1109/TVCG.2017.2677445.

The aim of Diminished Reality (DR) is to remove a target object in a live video stream seamlessly. In our approach, the area of the target object is replaced with new texture that blends with the rest of the image. The result is then propagated to the next frames of the video. One of the important stages of this technique is to update the target region with respect to the illumination change. This is a complex and recurrent problem when the viewpoint changes. We show that the state-of-the-art in DR fails in solving this problem, even under simple scenarios. We then use local illumination models to address this problem. According to these models, the variation in illumination only affects the specular component of the image. In the context of DR, the problem is therefore solved by propagating the specularities in the target area. We list a set of structural properties of specularities which we incorporate in two new models for specularity propagation. Our first model includes the same property as the previous approaches, which is the smoothness of illumination variation, but has a different estimation method based on the Thin-Plate Spline. Our second model incorporates more properties of the specularity's shape on planar surfaces. Experimental results on synthetic and real data show that our strategy substantially improves the rendering quality compared to the state-of-the-art in DR.

Significant progress has been recently made in Non-Rigid Structure-from-Motion (NRSfM). However, existing methods do not handle poorly-textured surfaces that deform non-smoothly. These are nonetheless common occurrence in real-world applications. An important unanswered question is whether shading can be used to robustly handle these cases. Shading is complementary to motion because it constrains reconstruction densely at textureless regions, and has been used in several other reconstruction problems. The challenge we face is to simultaneously and densely estimate non-smooth, non-rigid shape from each image together with non-smooth, spatially-varying surface albedo (which is required to use shading). We tackle this using an energy-based formulation that combines a physical, discontinuity-preserving deformation prior with motion, shading and contour information. This is a large-scale, highly non-convex optimization problem, and we propose a cascaded optimization that converges well without an initial estimate. Our approach works on both unorganized and organized small-sized image sets, and has been empirically validated on four real-world datasets for which all state-of-the-art approaches fail.

The specularity prediction task in images, given the camera pose and scene geometry, is challenging and ill-posed. A recent approach called JOint LIght-MAterial Specularity (JOLIMAS) addresses this problem using a geometric model under the assumption that specularities have an elliptical shape. We address the most recent version of the model, Dual JOLIMAS, which is limited to planar and convex surfaces where the local surface's curvature under the specularity is constant. We propose a canonical representation of the JOLIMAS model that is independent of the local surface curvature. To reconstruct our model represented by a 3D quadric, we use at least 3 ellipses fitted to specularities and transform their shape to fit a planar surface and simulate a planar mirror which does not distort the image of the reflected object. After reconstruction, we project the 3D quadric into an ellipse and transform it to fit the current local curvature of the surface on a new viewpoint. We assessed this method on both synthetic and real sequences, and compared it to the previous approach Dual JOLIMAS.

Dense motion field estimation is a key computer vision problem. Many solutions have been proposed to compute small or large displacements, narrow or wide baseline stereo disparity, or non‐rigid surface registration, but a unified methodology is still lacking. The authors introduce a general framework that robustly combines direct and feature‐based matching. The feature‐based cost is built around a novel robust distance function that handles keypoints and weak features such as segments. It allows us to use putative feature matches to guide dense motion estimation out of local minima. The authors’ framework uses a robust direct data term. It is implemented with a powerful second‐order regularisation with external and self‐occlusion reasoning. Their framework achieves state‐of‐the‐art performance in several cases (standard optical flow benchmarks, wide‐baseline stereo and non‐rigid surface registration). Their framework has a modular design that customises to specific application needs.

Shape-from-Template (SfT) reconstructs the shape of a deforming surface from a single image, a 3D template and a deformation prior. For isometric deformations, this is a well-posed problem. However, previous methods which require no initialization break down when the perspective effects are small, which happens when the object is small or viewed from larger distances. That is, they do not handle all projection geometries. We propose stable SfT methods that accurately reconstruct the 3D shape for all projection geometries. We follow the existing approach of using first-order differential constraints and obtain local analytical solutions for depth and the first-order quantities: the depth-gradient or the surface normal. Previous methods use the depth solution directly to obtain the 3D shape. We prove that the depth solution is unstable when the projection geometry tends to affine, while the solution for the first-order quantities remain stable for all projection geometries. We therefore propose to solve SfT by first estimating the first-order quantities (either depth-gradient or surface normal) and integrating them to obtain shape. We validate our approach with extensive synthetic and real-world experiments and obtain significantly more accurate results compared to previous initialization-free methods. Our approach does not require any optimization, which makes it very fast.

Planar Structure-from-Motion (SfM) is the problem of reconstructing a planar object or surface from a set of 2D images using motion information. The problem is well-understood with the perspective camera model and can be solved with Homography Decomposition (HD). However when the structure is small and/or viewed far from the camera the perspective effects diminish, and in the limit the projections become affine. In these situations HD fails because the problem itself becomes ill-posed. We propose a stable alternative using affine camera models. These have been used extensively to reconstruct non-planar structures, however a general, accurate and closed-form method for planar structures has been missing. The problem is fundamentally different with planar structures because the types of affine camera models one can use are more restricted and it is inherently more ambiguous and non-linear. We provide a closed-form method for the orthographic camera model that solves the general problem (three or more views with three or more correspondences and missing correspondences) and returns all metric structure solutions and corresponding camera poses. The method does not require initialisation, and optimises an objective function that is very similar to the reprojection error. In fact there is no clear benefit in refining its solutions with bundle adjustment, which is a remarkable result. We also present a new theoretical analysis that deepens our understanding of the problem. The main result is the necessary and sufficient geometric conditions for the problem to be degenerate with the orthographic camera. We also show there can exist up to two solutions for metric structure with four or more views (previously it was assumed to be unique), and we give the necessary and sufficient geometric conditions for disambiguation. Other theoretical results include showing that in the case of three images the optimal reconstruction (with respect to reprojection error) can usually be found in closed-form, and additional prior knowledge needed to solve with non-orthographic affine cameras.

Predicting specularities in images, given the camera pose and scene geometry from SLAM, forms a challenging and open problem. It is nonetheless essential in several applications such as retexturing. A recent geometric model called JOLIMAS partially answers this problem, under the assumptions that the specularities are elliptical and the scene is planar. JOLIMAS models a moving specularity as the image of a fixed 3D quadric. We propose dual JOLIMAS, a new model which raises the planarity assumption. It uses the fact that specularities remain elliptical on convex surfaces and that every surface can be divided in convex parts. The geometry of dual JOLIMAS then uses a 3D quadric per convex surface part and light source, and predicts the specularities by a means of virtual cameras, allowing it to cope with surface's unflatness. We assessed the efficiency and precision of dual JOLIMAS on multiple synthetic and real videos with various objects and lighting conditions. We give results of a retexturing application. Further results are presented as supplementary video material.

We present a global and convex formulation for template-less 3D reconstruction of a deforming object with the perspective camera. We show for the first time how to construct a Second-Order Cone Programming (SOCP) problem for Non-Rigid Shape-from-Motion (NRSfM) using the Maximum-Depth Heuristic (MDH). In this regard, we deviate strongly from the general trend of using affine cameras and factorization-based methods to solve NRSfM. In MDH, the points' depths are maximized so that the distance between neighbouring points in camera space are upper bounded by the geodesic distance. In NRSfM both geodesic and camera space distances are unknown. We show that, nonetheless, given point correspondences and the camera's intrinsics the whole problem is convex and solvable with SOCP. We show with extensive experiments that our method accurately reconstructs quasi-isometric surfaces from partial views under articulated and strong deformations. It naturally handles missing correspondences, non-smooth objects and is very simple to implement compared to previous methods, with only one free parameter (the neighbourhood size).

We study Isometric Non-Rigid Shape-from-Motion (Iso-NRSfM): given multiple intrinsically calibrated monocular images, we want to reconstruct the time-varying 3D shape of an object undergoing isometric deformations. We show that Iso-NRSfM is solvable from the warps (the inter-image geometric transformations). We propose a new theoretical framework based on Riemmanian manifolds to represent the unknown 3D surfaces, as embeddings of the camera's retinal planes. This allows us to use the manifolds' metric tensor and Christoffel Symbol fields, which we prove are related across images by simple rules depending only on the warps. This forms a set of important theoretical results. Using the infinitesimal planarity formulation, it then allows us to derive a system of two quartics in two variables for each image pair. The sum-of-squares of these polynomials is independent of the number of images and can be solved globally, forming a well-posed problem for N ≥ 3 images, whose solution directly leads to the surface's normal field. The proposed method outperforms existing work in terms of accuracy and computation cost on synthetic and real datasets.

Specularities, which are often visible in images, may be problematic in computer vision since they depend on parameters which are difficult to estimate in practice. We present an empirical model called JOLIMAS: JOint LIght-MAterial Specularity, which allows specularity prediction. JOLIMAS is reconstructed from images of specular reflections observed on a planar surface and implicitly includes light and material properties which are intrinsic to specularities. This work was motivated by the observation that specularities have a conic shape on planar surfaces. A theoretical study on the well known illumination models of Phong and Blinn-Phong was conducted to support the accuracy of this hypothesis. A conic shape is obtained by projecting a quadric on a planar surface. We showed empirically the existence of a fixed quadric whose perspective projection fits the conic shaped specularity in the associated image. JOLIMAS predicts the complex phenomenon of specularity using a simple geometric approach with static parameters on the object material and on the light source shape. It is adapted to indoor light sources such as light bulbs or fluorescent lamps. The performance of the prediction was convincing on synthetic and real sequences. Additionally, we used the specularity prediction for dynamic retexturing and obtained convincing rendering results. Further results are presented as supplementary material.

We have developed a technique to study how good computers can be at diagnosing gastrointestinal lesions from regular (white light and narrow banded) colonoscopic videos compared to two levels of clinical knowledge (expert and beginner). Our technique includes a novel tissue classification approach which may save clinician's time by avoiding chromoendoscopy, a time-consuming staining procedure using indigo carmine. Our technique also discriminates the severity of individual lesions in patients with many polyps, so that the gastroenterologist can directly focus on those requiring polypectomy. Technically, we have designed and developed a framework combining machine learning and computer vision algorithms, which performs a virtual biopsy of hyperplastic lesions, serrated adenomas and adenomas. Serrated adenomas are very difficult to classify due to their mixed/hybrid nature and recent studies indicate that they can lead to colorectal cancer through the alternate serrated pathway. Our approach is the first step to avoid systematic biopsy for suspected hyperplastic tissues. We also propose a database of colonoscopic videos showing gastrointestinal lesions with ground truth collected from both expert image inspection and histology. We not only compare our system with the expert predictions, but we also study if the use of 3D shape features improves classification accuracy, and compare our technique's performance with three competitor methods.

Shape-from-Template (SfT) is the problem of inferring the shape of a deformable object as observed in an image using a shape template. We call 2DSfT the `usual' instance of SfT where the shape is a surface embedded in 3D and the image a 2D projection. We introduce 1DSfT, a novel instance of SfT where the shape is a curve embedded in 2D and the image a 1D projection. We focus on isometric deformations, for which 2DSfT is a well-posed problem, and admits an analytical local solution which may be used to initialize nonconvex refinement. Through a complete theoretical study of 1DSfT with perspective projection, we show that it is related to 2DSfT, but may have very different properties: (i) 1DSfT cannot be exactly solved locally and (ii) 1DSfT cannot be solved uniquely, as it has a discrete amount of at least two solutions. We then propose two convex initialization algorithms, a local analytical one based on infinitesimal planarity and a global one based on inextensibility. We show how nonconvex refinement can be implemented where, contrarily to current 2DSfT methods, one may enforce isometry exactly using a novel angle-based parameterization. Finally, our method is tested with simulated and real data.

We cast SfT (Shape-from-Template) as the search of a vector field (X, δX), composed of the pose X and the displacement δX that produces the deformation. We propose the first fully linear least-squares SfT method modeling elastic deformations. It relies on a set of Solid Boundary Constraints (SBC) to position the template at X in the deformed frame. The displacement is mapped by the stiffness matrix to minimize the amount of force responsible for the deformation. This linear minimization is subjected to the Reprojection Boundary Constraints (RBC) of the deformed shape X + δX on the deformed image. Compared to state-of-the-art methods, this new formulation allows us to obtain accurate results at a low computation cost.

The objective of Shape-from-Template (SfT) is to infer an object's shape from a single image and a 3D object template. Existing methods are called thin-shell SfT as they represent the object by its outer surface. This may be an open surface for thin objects such as a piece of paper or a closed surface for thicker objects such as a ball. We propose volumetric SfT, which specifically handles objects of the latter kind. Volumetric SfT uses the object's full volume to express the deformation constraints and reconstructs the object's surface and interior deformation. This is a challenging problem because for opaque objects, only a part of the outer surface is visible in the image. Inspired by mesh-editing techniques, we use an As-Rigid-As-Possible (ARAP) deformation model that softly imposes local rigidity. We formalise ARAP isometric SfT as a constrained variational optimisation problem which we solve using iterative optimisation. We present strategies to find an initial solution based on thin-shell SfT and volume propagation. Experiments with synthetic and real data show that our method has a typical maximum relative error of 5% in reconstructing the deformation of an entire object, including its back and interior for which no visual data is available.

An important yet unsolved problem in computer vision and Augmented Reality (AR) is to compute the 3D shape of nonrigid objects from live 2D videos. When the object's shape is provided in a rest pose, this is the Shape-from-Template (SfT) problem. Previous realtime SfT methods require simple, smooth templates, such as flat sheets of paper that are densely textured, and which deform in simple, smooth ways. We present a realtime SfT framework that handles generic template meshes, complex deformations and most of the difficulties present in real imaging conditions. Achieving this has required new, fast solutions to the two core sub-problems: robust registration and 3D shape inference. Registration is achieved with what we call Deformable Render-based Block Matching (DRBM): a highly-parallel solution which densely matches a time-varying render of the object to each video frame. We then combine matches from DRBM with physical deformation priors and perform shape inference, which is done by quickly solving a sparse linear system with a Geometric Multi-Grid (GMG)-based method. On a standard PC we achieve up to 21fps depending on the object. Source code will be released.

Time‐of‐flight (TOF) sensors provide real‐time depth information at high frame‐rates. One issue with TOF sensors is the usual high level of noise (i.e . the depth measure's repeatability within a static setting). However, until now, TOF sensors’ noise has not been well studied. The authors show that the commonly agreed hypothesis that noise depends only on the amplitude information is not valid in practice. They empirically establish that the noise follows a signal‐dependent Gaussian distribution and varies according to pixel position, depth and integration time. They thus consider all these factors to model noise in two new noise models. Both models are evaluated, compared and used in the two following applications: depth noise removal by depth filtering and uncertainty (repeatability) estimation in three‐dimensional measurement.

We study a problem that we call Shape-from-Template, which is the problem of reconstructing the shape of a deformable surface from a single image and a 3D template. Current methods in the literature address the case of isometric deformations, and relax the isometry constraint to the convex inextensibility constraint, solved using the so-called maximum depth heuristic. We call these methods zeroth-order since they use image point locations (the zeroth-order differential structure) to solve the shape inference problem from a perspective image. We propose a novel class of methods that we call first-order. The key idea is to use both image point locations and their first-order differential structure. The latter can be easily extracted from a warp between the template and the input image. We give a unified problem formulation as a system of PDEs for isometric and conformal surfaces that we solve analytically. This has important consequences. First, it gives the first analytical algorithms to solve this type of reconstruction problems. Second, it gives the first algorithms to solve for the exact constraints. Third, it allows us to study the well-posedness of this type of reconstruction: we establish that isometric surfaces can be reconstructed unambiguously and that conformal surfaces can be reconstructed up to a few discrete ambiguities and a global scale. In the latter case, the candidate solution surfaces are obtained analytically. Experimental results on simulated and real data show that our isometric methods generally perform as well as or outperform state of the art approaches in terms of reconstruction accuracy, while our conformal methods largely outperform all isometric methods for extensible deformations.

It has been recently shown that reconstructing an isometric surface from a single 2D input image matched to a 3D template was a well-posed problem. This however does not tell us how reconstruction algorithms will behave in practical conditions, where the amount of perspective is generally small and the projection thus behaves like weak-perspective or orthography. We here bring answers to what is theoretically recoverable in such imaging conditions, and explain why existing convex numerical solutions and analytical solutions to 3D reconstruction may be unstable. We then propose a new algorithm which works under all imaging conditions, from strong to loose perspective. We empirically show that the gain in stability is tremendous, bringing our results close to the iterative minimization of a statistically-optimal cost. Our algorithm has a low complexity, is simple and uses only one round of linear least-squares.

An active research objective in Computer Assisted Intervention (CAI) is to develop guidance systems to aid surgical teams in laparoscopic Minimal Invasive Surgery (MIS) using Augmented Reality (AR). This involves registering and fusing additional data from other modalities and overlaying it onto the laparoscopic video in realtime. We present the first AR-based image guidance system for assisted myoma localisation in uterine laparosurgery. This involves a framework for semi-automatically registering a pre-operative Magnetic Resonance Image (MRI) to the laparoscopic video with a deformable model. Although there has been several previous works involving other organs, this is the first to tackle the uterus. Furthermore, whereas previous works perform registration between one or two laparoscopic images (which come from a stereo laparoscope) we show how to solve the problem using many images (e.g. 20 or more), and show that this can dramatically improve registration. Also unlike previous works, we show how to integrate occluding contours as registration cues. These cues provide powerful registration constraints and should be used wherever possible. We present retrospective qualitative results on a patient with two myomas and quantitative semi-synthetic results. Our multi-image framework is quite general and could be adapted to improve registration in other organs with other modalities such as CT.

Intra-operative imaging techniques for obtaining the shape and morphology of soft-tissue surfaces in vivo are a key enabling technology for advanced surgical systems. Different optical techniques for 3-D surface reconstruction in laparoscopy have been proposed, however, so far no quantitative and comparative validation has been performed. Furthermore, robustness of the methods to clinically important factors like smoke or bleeding has not yet been assessed. To address these issues, we have formed a joint international initiative with the aim of validating different state-of-the-art passive and active reconstruction methods in a comparative manner. In this comprehensive in vitro study, we investigated reconstruction accuracy using different organs with various shape and texture and also tested reconstruction robustness with respect to a number of factors like the pose of the endoscope as well as the amount of blood or smoke present in the scene. The study suggests complementary advantages of the different techniques with respect to accuracy, robustness, point density, hardware complexity and computation time. While reconstruction accuracy under ideal conditions was generally high, robustness is a remaining issue to be addressed. Future work should include sensor fusion and in vivo validation studies in a specific clinical context. To trigger further research in surface reconstruction, stereoscopic data of the study will be made publically available at www.open-CAS.com upon publication of the paper.

We propose a novel and fast multiscale feature detection and description approach that exploits the benefits of nonlinear scale spaces. Previous attempts to detect and describe features in nonlinear scale spaces such as KAZE [1] and BFSIFT [6] are highly time consuming due to the computational burden of creating the nonlinear scale space. In this paper we propose to use recent numerical schemes called Fast Explicit Diffusion (FED) [3, 4] embedded in a pyramidal framework to dramatically speed-up feature detection in nonlinear scale spaces. In addition, we introduce a Modified-Local Difference Binary (M-LDB) descriptor that is highly efficient, exploits gradient information from the nonlinear scale space, is scale and rotation invariant and has low storage requirements. Our features are called Accelerated-KAZE (A-KAZE) due to the dramatic speed-up introduced by FED schemes embedded in a pyramidal framework.

International audience

This paper studies the problem of surface reconstruction from a single image, given a template of the surface. We investigate the variational structure of the reconstruction problem for isometric and conformal deformations and weak-perspective camera projections. We give analytical solutions for the surface shape given that the registration warp between the template and the input image meets specific differential constraints. We explore those constraints, giving an optimization strategy to compute warps that comply with isometric and conformal deformations under weak-perspective projection. We study the performance of the proposed algorithms with synthetic and real datasets. The experiments show that surface reconstruction with weak-perspective is accurate when using cameras with large focal lengths and improves state of the art methods.

It has been shown that a surface deforming isometric ally can be reconstructed from a single image and a template 3D shape. Methods from the literature solve this problem efficiently. However, they all assume that the camera model is calibrated, which drastically limits their applicability. We propose (i) a general variational framework that applies to (calibrated and uncalibrated) general camera models and (ii) self-calibrating 3D reconstruction algorithms for the weak-perspective and full-perspective camera models. In the former case, our algorithm returns the normal field and camera's scale factor. In the latter case, our algorithm returns the normal field, depth and camera's focal length. Our algorithms are the first to achieve deformable 3D reconstruction including camera self-calibration. They apply to much more general setups than existing methods. Experimental results on simulated and real data show that our algorithms give results with the same level of accuracy as existing methods (which use the true focal length) on perspective images, and correctly find the normal field on affine images for which the existing methods fail.

We propose a new approach for template-based extensible surface reconstruction from a single view. We extend the method of isometric surface reconstruction and more recent work on conformal surface reconstruction. Our approach relies on the minimization of a proposed stretching energy formalized with respect to the Poisson ratio parameter of the surface. We derive a patch-based formulation of this stretching energy by assuming local linear elasticity. This formulation unifies geometrical and mechanical constraints in a single energy term. We prevent local scale ambiguities by imposing a set of fixed boundary 3D points. We experimentally prove the sufficiency of this set of boundary points and demonstrate the effectiveness of our approach on different developable and non-developable surfaces with a wide range of extensibility.

We study the uncalibrated isometric Shape-from-Template problem, that consists in estimating an isometric deformation from a template shape to an input image whose focal length is unknown. Our method is the first that combines the following features: solving for both the 3D deformation and the camera's focal length, involving only local analytical solutions (there is no numerical optimization), being robust to mismatches, handling general surfaces and running extremely fast. This was achieved through two key steps. First, an `uncalibrated' 3D deformation is computed thanks to a novel piecewise weak-perspective projection model. Second, the camera's focal length is estimated and enables upgrading the 3D deformation to metric. We use a variational framework, implemented using a smooth function basis and sampled local deformation models. The only degeneracy -which we easily detect- for focal length estimation is a flat and fronto-parallel surface. Experimental results on simulated and real datasets show that our method achieves a 3D shape accuracy slightly below state of the art methods using a precalibrated or the true focal length, and a focal length accuracy slightly below static calibration methods.

Dense motion field estimation (typically optical flow, stereo disparity and surface registration) is a key computer vision problem. Many solutions have been proposed to compute small or large displacements, narrow or wide baseline stereo disparity, but a unified methodology is still lacking. We here introduce a general framework that robustly combines direct and feature-based matching. The feature-based cost is built around a novel robust distance function that handles key points and ``weak'' features such as segments. It allows us to use putative feature matches which may contain mismatches to guide dense motion estimation out of local minima. Our framework uses a robust direct data term (AD-Census). It is implemented with a powerful second order Total Generalized Variation regularization with external and self-occlusion reasoning. Our framework achieves state of the art performance in several cases (standard optical flow benchmarks, wide-baseline stereo and non-rigid surface registration). Our framework has a modular design that customizes to specific application needs.

ABSTRACT Developable surfaces have been extensively studied in computer graphics because they are involved in a large body of applications. This type of surfaces has also been used in computer vision and document processing in the context of three‐dimensional (3D) reconstruction for book digitization and augmented reality. Indeed, the shape of a smoothly deformed piece of paper can be very well modeled by a developable surface. Most of the existing developable surface parameterizations do not handle boundaries or are driven by overly large parameter sets. These two characteristics become issues in the context of developable surface reconstruction from real observations. Our main contribution is a generative model of bounded developable surfaces that solves these two issues. Our model is governed by intuitive parameters whose number depends on the actual deformation and including the “flat shape boundary”. A vast majority of the existing image‐based paper 3D reconstruction methods either require a tightly controlled environment or restricts the set of possible deformations. We propose an algorithm for reconstructing our model's parameters from a general smooth 3D surface interpolating a sparse cloud of 3D points. The latter is assumed to be reconstructed from images of a static piece of paper or any other developable surface. Our 3D reconstruction method is well adapted to the use of keypoint matches over multiple images. In this context, the initial 3D point cloud is reconstructed by structure‐from‐motion for which mature and reliable algorithms now exist and the thin‐plate spline is used as a general smooth surface model. After initialization, our model's parameters are refined with model‐based bundle adjustment. We experimentally validated our model and 3D reconstruction algorithm for shape capture and augmented reality on seven real datasets. The first six datasets consist of multiple images or videos and a sparse set of 3D points obtained by structure‐from‐motion. The last dataset is a dense 3D point cloud acquired by structured light. Our implementation has been made publicly available on the authors' web home pages. Copyright © 2012 John Wiley & Sons, Ltd.

Deformable 3D reconstruction from 2D images requires prior knowledge on the scene structure. Template-free methods use generic prior knowledge such as piecewise smoothness but require multiple images with significant baseline. Template-based methods require only one image but handle only one object for which they need specific prior knowledge, namely a 3D template. We here propose a novel method that alleviates the strong assumptions of both the template-free and template-based methods: our method uses multiple templates to achieve deformable 3D reconstruction from only one image and for multiple objects. It uses object recognition to automatically discover what objects are visible in the input image and to select the appropriate templates for deformable 3D reconstruction. The object database is built offline. Crucially, this database does not only contain appearance descriptors as in existing object recognition frameworks, but also material properties to facilitate deformable 3D reconstruction. We show successful experimental results with objects made of various materials such as paper, cloth and plastic.

Depth cameras open new possibilities in fields such as 3D reconstruction, Augmented Reality and video-surveillance since they provide depth information at high frame-rates. However, like any sensor, they have limitations related to their technology. One of them is depth distortion. In this paper, we present a method to estimate depth correction for depth cameras. The proposed method is based on two steps. The first one is a nonplanarity correction that needs depth measurement of different plane views. The second one is an affinity correction that,contrary to state of the art approaches, requires a very small set of ground truth measurements. Thus, it is more easy to use compared to other methods and does not need a large set of accurate ground truth that is extremely difficult to obtain in practice. Experiments on both simulated and real data show that the proposed approach improve also the depth accuracy compare to state of the art methods.

Recovering a deformable surface's 3D shape from a single view registered to a 3D template requires one to provide additional constraints. A recent approach has been to constrain the surface to deform quasi-isometrically. This is applicable to surfaces of materials such as paper and cloth. Current `closed-form' solutions solve a convex approximation of the original problem whereby the surface's depth is maximized under the isometry constraints (this is known as the maximum depth heuristic). No such convex approximation has yet been proposed for the conformal case. We give a unified problem formulation as a system of PDEs for developable, isometric and conformal surfaces that we solve analytically. This has important consequences. First, it gives the first analytical algorithms to solve this type of reconstruction problems. Second, it gives the first algorithms to solve for the exact constraints. Third, it allows us to study the well-posedness of this type of reconstruction: we establish that isometric surfaces can be reconstructed unambiguously and that conformal surfaces can be reconstructed up to a few discrete ambiguities and a global scale. In the latter case, the candidate solution surfaces are obtained analytically. Experimental results on simulated and real data show that our methods generally perform as well as or outperform state of the art approaches in terms of reconstruction accuracy.

Time-of-Flight (TOF) cameras measure, in real-time, the distance between the camera and objects in the scene. This opens new perspectives in different application fields: 3D reconstruction, Augmented Reality, video-surveillance, etc. However, like any sensor, TOF cameras have limitations related to their technology. One of them is distance distortion. In this paper, we present a new depth calibration method (estimation of distance distortion) for TOF cameras. Our approach has several advantages. First, it is based on a non-parametric model, contrary to most of the other methods. Second, it models under the same formalism the distortion variation according to the distance and the pixel position in the image. This improves calibration accuracy even at the image boundaries which are typically more distorted than the image center. A comparison with two state of the art parametric methods is presented.

International audience

This paper deals with generalized procrustes analysis. This is the problem of registering a set of shape data by estimating a reference shape and a set of rigid transformations given point correspondences. The transformed shape data must align with the reference shape as best possible. This is a difficult problem. The classical approach computes alternatively the reference shape, usually as the average of the transformed shapes, and each transformation in turn. We propose a global approach to generalized procrustes analysis for two- and three-dimensional shapes. It uses modern convex optimization based on the theory of Sum Of Squares functions. We show how to convert the whole procrustes problem, including missing data, into a semidefinite program. Our approach is statistically grounded: it finds the maximum likelihood estimate. We provide results on synthetic and real datasets. Compared to classical alternation our algorithm obtains lower errors. The discrepancy is very high when similarities are estimated or when the shape data have significant deformations.

Image registration and 3D reconstruction are fundamental computer vision and medical imaging problems. They are particularly challenging when the input data are images of a deforming body obtained by a single moving camera. We propose a new modelling framework, the multiview 3D warps. Existing models are twofold: they estimate inter-image warps which are often inconsistent between the different images and do not model the underlying 3D structure, or reconstruct just a sparse set of points. In contrast, our multiview 3D warps combine the advantages of both; they have an explicit 3D component and a set of 3D deformations combined with projection to 2D. They thus capture the dense deforming body's time-varying shape and camera pose. The advantages over the classical solutions are numerous: thanks to our feature-based estimation method for the multiview 3D warps, one can not only augment the original images but also retarget or clone the observed body's 3D deformations by changing the pose. Experimental results on simulated and real data are reported, confirming the advantages of our framework over existing methods.

The quality of a mosaic depends on the projective alignment of the images involved. After point-correspondences between the images have been established, bundle adjustment finds an alignment considered optimal under certain hypotheses. This procedure minimizes a nonlinear cost and has to be initialized with care. It is very common to compose inter-frame homographies which have been computed with standard methods in order to get an initial global alignment. This technique is suboptimal if there is noise or missing ho-mographies as it typically uses a small part of the available data. We propose four new closed-form solutions. They all provide non-heuristic initial alignments using all the known inter-frame homographies. Our methods are tested with synthetic and real data and are compared to the standard method. These experiments reveal that our methods are more accurate, taking advantage of the redundant information available in the set of inter-frame homographies.

In many different problems, data analysis requires one to first compensate for a global transformation between the different datasets of shape data. This is known as procrustes analysis in the statistics and shape analysis literature [1, 3]. More precisely, it is called generalized procrustes analysis when more than two shape data are to be registered. In this problem, one global transformation per observed shape has to be computed, so that the shapes are mapped to a common coordinate frame whereby they look as ‘similar ’ as possible. This process is called also rigid registration. The classical approach to generalized procrustes analysis is to select one of the shapes as a reference shape, and register each of the other shapes to the reference in turn by solving the absolute orientation problem. It is common to then alternate a re-estimation of the reference shape, as the average of the registered shapes, with shape registration. We call this general paradigm the alternation approach to generalized procrustes analysis. Both iterative [2] and algebraic closed-form solutions [4] were

This paper presents an algorithm for segmenting the hair region in uncontrolled, real life conditions images. Our method is based on a simple statistical hair shape model representing the upper hair part. We detect this region by minimizing an energy which uses active shape and active contour. The upper hair region then allows us to learn the hair appearance parameters (color and texture) for the image considered. Finally, those parameters drive a pixel-wise segmentation technique that yields the desired (complete) hair region. We demonstrate the applicability of our method on several real images.

The registration problem for images of a deforming surface has been well studied. External occlusions are usually well handled. In 2D image-based registration, self-occlusions are more challenging. Consequently, the surface is usually assumed to be only slightly self-occluding. This paper is about image-based nonrigid registration with self-occlusion reasoning. A specific framework explicitly modeling self-occlusions is proposed. It is combined with an intensity-based, "direct" data term for registration. Self-occlusions are detected as shrinkage areas in the 2D warp. Experimental results on several challenging data sets show that our approach successfully registers images with self-occlusions while effectively detecting the self-occluded regions.

Point-to-point matching is a crucial stage of 3D shape analysis. It is usually solved by using descriptors that summarize the most characteristic and discriminative properties of each point. Combining local and global context information in the point descriptor is a promising approach. We propose a new approach based on what we call semantic shape context to combine effectively local descriptors and global context information by exploiting the Bag of Words (BoW) paradigm for the representation of a single 3D point. Several local point descriptors are collected and quantized from the training set, by defining the visual vocabulary composed by a fixed number of visual words. Each point is then represented by a set of BoWs which encode the inter-relationship with all the other points of the object (i.e., the context). Experiments were carried out on several 3D models. The proposed approach makes fully automatic 3D registration of partial views possible, and generally outperforms stateof-the-art methods in terms of robustness and accuracy.

Bundle Adjustment is based on nonlinear least squares minimization techniques, such as Levenberg-Marquardt and Gauss-Newton. It iteratively computes local parameter increments. Line Search techniques aim at providing an efficient magnitude for these increments, called the step length. In this paper, a new ad hoc Line Search technique for solving bundle adjustment is proposed. The main idea is to determine an efficient step length using an approximation of the cost function based on an algebraic distance. We use the Wolfe conditions to show that our Line Search preserves the convergence properties of the original algorithm. Our method is compared to different nonlinear optimization algorithms and Line Search techniques under several conditions, on real and synthetic data. The method improves the minimization process, decreasing the reprojection error significantly faster than the other techniques.

This purely theoretical work investigates the problem of artificial singularities in camera self-calibration. Self-calibration allows one to upgrade a projective reconstruction to metric and has a concise and well-understood formulation based on the Dual Absolute Quadric (DAQ), a rank-3 quadric envelope satisfying (nonlinear) ‘spectral constraints’: it must be positive of rank 3. The practical scenario we consider is the one of square pixels, known principal point and varying unknown focal length, for which generic Critical Motion Sequences (CMS) have been thoroughly derived. The standard linear self-calibration algorithm uses the DAQ paradigm but ignores the spectral constraints. It thus has artificial CMSs, which have barely been studied so far. We propose an algebraic model of singularities based on the confocal quadric theory. It allows to easily derive all types of CMSs. We first review the already known generic CMSs, for which any self-calibration algorithm fails. We then describe all CMSs for the standard linear self-calibration algorithm; among those are artificial CMSs caused by the above spectral constraints being neglected. We then show how to detect CMSs. If this is the case it is actually possible to uniquely identify the correct self-calibration solution, based on a notion of signature of quadrics. The main conclusion of this paper is that a posteriori enforcing the spectral constraints in linear self-calibration is discriminant enough to resolve all artificial CMSs.

We present a monocular 3D reconstruction algorithm for inextensible deformable surfaces. It is based on point correspondences between the actual image and a template. Since the surface is inextensible, its deformations are isometric to the template, for which the surface shape is known. We exploit the underlying distance constraints to recover the 3D shape. Though these constraints have already been investigated in the literature, we propose a new way to handle them. As opposed to previous methods, ours does not require a known initial deformation. Spatial and temporal smoothness priors are easily incorporated. The reconstruction can be used for 3D augmented reality purposes thanks to a fast implementation. We report results on synthetic and real data. Some of them are faced to stereo-based 3D reconstructions to demonstrate the efficiency of our method.

Fitting a single generic AAM on an unseen face (that is not in the training set) under any pose and expression is very difficult. The v ariability of the data is so high that the fitting process usually gets stuck into one of the numerous local minima. We show that a solution to this problem consists to separate the variability sources. We build a pool of specialized AAMs. Each AAM is trained over multiple identities, all shown under the same pose and expression. We then retain the AAM that shows the smallest residual error when fitted to the input image. The fitting obtained in th is manner is very accurate on unseen faces. The ultimate goal is to automatically train a person-specific AAM. In addition, the pool of specialized AA Ms allows us to recognize the face pose and expression at each frame of the video with good performances. The proposed method has potential applications in Human Computer Interaction and driving surveillance, to name just but a few.

We address the problem of deformable shape and motion recovery from point correspondences in multiple perspective images. We use the low-rank shape model, i.e. the 3D shape is represented as a linear combination of unknown shape bases. We propose a new way of looking at the low-rank shape model. Instead of considering it as a whole, we assume a coarse-to-fine ordering of the deformation modes, which can be seen as a model prior. This has several advantages. First, the high level of ambiguity of the original low-rank shape model is drastically reduced since the shape bases can not anymore be arbitrarily re-combined. Second, this allows us to propose a coarse-to-fine reconstruction algorithm which starts by computing the mean shape and iteratively adds deformation modes. It directly gives the sought after metric model, thereby avoiding the difficult upgrading step required by most of the other methods. Third, this makes it possible to automatically select the number of deformation modes as the reconstruction algorithm proceeds. We propose to incorporate two other priors, accounting for temporal and spatial smoothness, which are shown to improve the quality of the recovered model parameters. The proposed model and reconstruction algorithm are successfully demonstrated on several videos and are shown to outperform the previously proposed algorithms.

This paper deals with shading and AAMs. Shading is created by lighting change. It can be of two types: self- shading and external shading. The effect of self-shading can be explicitly learned and handled by AAMs. This is not however possible for external shading, which is usually dealt with by robustifying the cost function. We take a different approach: we measure the fitting cost in a so-called Light-Invariant space. This approach naturally handles self-shading and external shading. The framework is based on mild assumptions on the scene reflectance and the cameras. Some photometric camera response parameters are required. We propose to estimate these while fitting an existing color AAM in a photometric 'self-calibration' manner. We report successful results with a face AAM with test images taken indoor under simple lighting change.

Building an accurate three dimensional map is an important task for autonomous localisation and navigation. In a sequential approach to reconstruction from video streams, we show how adding prior knowledge about camera motion improves reconstruction accuracy, obtaining a more precise trajectory estimation and preventing failures over time. We add a smoothing penalty on camera trajectory and the smoothing parameter, usually fixed by trial and error, is automatically estimated using Cross-Validation. The method is substantiated by experimental results on synthetic and real data. They show that it improves accuracy and stability in the reconstruction process, preventing several failure cases.

Abstract Imagine an object such as a paper sheet being waved in front of some sensor. Reconstructing the time‐varying 3D shape of the object finds direct applications in computer animation. The goal of this paper is to provide such a deformation capture system for surfaces. It uses temporal range data obtained by sensors such as those based on structured light or stereo. So as to deal with many different kinds of material, we do not make the usual assumption that the object surface has textural information. This rules out those techniques based on detecting and matching keypoints or directly minimizing color discrepancy. The proposed method is based on a planar mesh that is deformed so as to fit each of the range images. We show how to achieve this by minimizing a compound cost function combining several data and regularization terms, needed to make the overall system robust so that it can deal with low quality datasets. Carefully examining the parameter to residual relationship shows that this cost function can be minimized very efficiently by coupling nonlinear least squares methods with sparse matrix operators. Experimental results for challenging datasets coming from different kinds of range sensors are reported. The algorithm is reasonably fast and is shown to be robust to missing and erroneous data points. Copyright © 2008 John Wiley & Sons, Ltd.

Image registration consists in estimating geometric and photometric transformations that align two images as best as possible. The direct approach consists in minimizing the discrepancy in the intensity or color of the pixels. The inverse compositional algorithm has been recently proposed by Baker et al. for the direct estimation of groupwise geometric transformations. It is efficient in that it performs several computationally expensive calculations at a pre-computation phase. Photometric transformations act on the value of the pixels. They account for effects such as lighting change. Jointly estimating geometric and photometric transformations is thus important for many tasks such as image mosaicing. We propose an algorithm to jointly estimate groupwise geometric and photometric transformations while preserving the efficient pre-computation based design of the original inverse compositional algorithm. It is called the dual inverse compositional algorithm. It uses different approximations than the simultaneous inverse compositional algorithm and handles groupwise geometric and global photometric transformations. Its name stems from the fact that it uses an inverse compositional update rule for both the geometric and the photometric transformations. We demonstrate the proposed algorithm and compare it to previous ones on simulated and real data. This shows clear improvements in computational efficiency and in terms of convergence.

The direct registration problem for images of a deforming surface has been well studied. Parametric flexible warps based, for instance, on the Free-Form Deformation or a Radial Basis Function such as the Thin-Plate Spline, are often estimated using additive Gauss-Newton-like algorithms. The recently proposed compositional framework has been shown to be more efficient, but cannot be directly applied to such non-groupwise warps. Our main contribution in this paper is the Feature-Driven framework. It makes possible the use of compositional algorithms for most parametric warps such as those above mentioned. Two algorithms are proposed to demonstrate the relevance of our Feature-Driven framework: the Feature-Driven Inverse Compositional and the Feature-Driven Learning-based algorithms. As another contribution, a detailed derivation of the Feature-Driven warp parameterization is given for the Thin-Plate Spline and the Free-Form Deformation. We experimentally show that these two types of warps have a similar representational power. Experimental results show that our Feature-Driven registration algorithms are more efficient in terms of computational cost, without loss of accuracy, compared to existing methods.

This paper describes how the generalization ability of methods for non-rigid Structure-from-Motion can be improved by using priors. Most point tracks are often visible only in some of the images; predicting the missing data can be important. Previous Maximum-Likelihood (ML)-approaches on implicit non-rigid Structure-from-Motion generalize badly. Although the estimated model fits well to the visible training data, it often predicts the missing data badly. To improve generalization we propose to add a temporal smoothness prior and a continuous surface shape prior to an ML-approach. The temporal smoothness prior constrains the camera trajectory and the configuration weights to behave smoothly. The surface shape prior constrains consistently close image point tracks to have a similar implicit structure. We propose an algorithm for achieving a Maximum A Posteriori (MAP)-solution and show experimentally that the MAP-solution generalizes far better than the MLsolution. The proposed method is fully automatic: it handles a substantial amount of missing data as well as outlier contaminated data, and automatically estimates the rank of the measurement matrix.

An Active Appearance Model (AAM) is a variable shape and appearance model built from annotated training images. It has been largely used to synthesize or fit face images. Person-independent face AAM fitti ng is a challenging open issue. For standard AAMs, fitting a face image fo r an individual which is not in the training set is often limited in accuracy, thereby restricting the range of application. As a first contribution, we show that the limitation mainly co mes from the inability of the AAM appearance counterpart to generalize, i.e. to accurately generate previously unseen visual data. As a second contribution, we propose an efficient person-independent face fitting framework based on what we call multi-level segmented AAMs. Each segment encodes a physically meaningful part of the face, such as an eye. A coarse-to-fine fi tting strategy with a gradually increasing number of segments is used in order to ensure a large convergence basin. Fitting accuracy is assessed by comparison with manual labelling statistics constructed from multiple data annotations. Experimental results support the claim that standard AAMs are well-adapted to person-specific fitting while segmented AAMs outperform the classical AAMs in a personindependent context in terms of accuracy, and ability to generate new faces.

Recent work shows that recovering pose and velocity from a single view of a moving rigid object is possible with a rolling shutter camera, based on feature point correspondences. We extend this method to line correspondences. Owing to the combined effect of rolling shutter and object motion, straight lines are distorted to curves as they get imaged with a rolling shutter camera. Lines thus capture more information than points, which is not the case with standard projection models for which both points and lines give two constraints. We extend the standard line reprojection error, and propose a nonlinear method for retrieving a solution to the pose and velocity computation problem. A careful inspection of the design matrix in the normal equations reveals that it is highly sparse and patterned. We propose a blockwise solution procedure based on bundle-adjustment-like sparse inversion. This makes nonlinear optimization fast and numerically stable. The method is validated using real data.

Thin-plate spline warps have been shown to be very effective as a parameterized model of the optic flow field between images of various deforming surfaces. Examples include a sheet of paper being manually handled. Recent work has used such warps for images of smooth rigid surfaces. Standard thin-plate spline warps are not rigid, in the sense that they do not satisfy the epipolar geometry constraint, and are intrinsically affine, in the sense of the affine camera model. We propose three types of warps based on the thin-plate spline. The first one is a flexible rigid warp. It describes the optic flow field induced by a smooth rigid surface, and satisfies the affine epipolar geometry constraint. The second and third ones extend the standard thin-plate spline and the proposed rigid flexible warp to the perspective camera model. The properties of these warps are studied in details, and a hierarchy is defined. Experimental results on simulated and real data are reported, showing that the proposed warps outperform the standard one in several cases of interest.

We investigate the problem of finding the metric structure of a general 3D scene viewed by a moving camera with square pixels and constant unknown focal length. While the problem has a concise and well-understood formulation in the stratified framework thanks to the absolute dual quadric, two open issues remain. The first issue concerns the generic Critical Motion Sequences, i.e. camera motions for which self-calibration is ambiguous. Most of the previous work focuses on the varying focal length case. We provide a thorough study of the constant focal length case. The second issue is to solve the nonlinear set of equations in four unknowns arising from the dual quadric formulation. Most of the previous work either does local nonlinear optimization, thereby requiring an initial solution, or linearizes the problem, which introduces artificial degeneracies, most of which likely to arise in practice. We use interval analysis to solve this problem. The resulting algorithm is guaranteed to find the solution and is not subject to artificial degeneracies. Directly using interval analysis usually results in computationally expensive algorithms. We propose a carefully chosen set of inclusion functions, making it possible to find the solution within few seconds. Comparisons of the proposed algorithm with existing ones are reported for simulated and real data.

Smoothly bent paper-like surfaces are developable. They are however difficult to minimally parameterize since the number of meaningful parameters is intrinsically dependent on the actual deformation. Previous generative models are either incomplete, i.e. limited to subsets of developable surfaces, or depend on huge parameter sets. We propose a generative model governed by a quasi-minimal set of intuitive parameters, namely rules and angles. More precisely, a flat mesh is bent along guiding rules, while a number of extra rules controls the level of smoothness. The generated surface is guaranteed to be developable. A fully automatic multi-camera three dimensional reconstruction algorithm, including model-based bundle-adjustment, demonstrates our model on real images.

Matrix factorization is a key component for solving several computer vision problems. It is particularly challenging in the presence of missing or erroneous data, which often arise in structure-from-motion. We propose batch algorithms for matrix factorization. They are based on closure and basis constraints, that are used either on the cameras or the structure, leading to four possible algorithms. The constraints are robustly computed from complete measurement sub-matrices with e.g. random data sampling. The cameras and 3D structure are then recovered through linear least squares. Prior information about the scene such as identical camera positions or orientations, smooth camera trajectory, known 3D points and coplanarity of some 3D points can be directly incorporated. We demonstrate our algorithms on challenging image sequences with tracking error and more than 95% missing data.

The registration problem for images of a deforming surface has been well studied. External occlusions are usually well-handled. In 2D image-based registration, self- occlusions are more challenging. Consequently, the surface is usually assumed to be only slightly self-occluding. This paper is about image-based non-rigid registration with self-occlusion reasoning. A specific framework explicitly modeling self-occlusions is proposed. It is combined with an intensity-based, i.e. direct, data term for registration. Self-occlusions are detected as shrinking areas in the 2D warp. Experimental results on several challenging datasets show that our approach successfully registers images with self-occlusions while effectively detecting the occluded regions.

The augmentation problem for images of a deforming surface has been studied since recently. The surface is usually assumed not to be self-occluding. Two dimensional deformation estimation in the presence of self-occlusions is very challenging. This paper proposes a specific framework explicitly modeling self-occlusions for augmented reality applications. The basic idea is to detect self-occlusions as warp shrinkage areas. Deformations are initially estimated via direct non-rigid image registration. Temporal smoothness is then used to refine the warps and the image are augmented. Experimental results on several challenging datasets show that our approach convincingly augments self-occluded surfaces. Associated videos are available on the first author's Web homepage.

Image registration consists in estimating geometric and photometric transformations that align two images as best as possible. The direct approach consists in minimizing the discrepancy in the intensity or color of the pixels. The inverse compositional algorithm has been recently proposed by Baker et al. for the direct estimation of groupwise geometric transformations. It is efficient in that it performs several computationally expensive calculations at a pre-computation phase. Photometric transformations act on the value of the pixels. They account for effects such as lighting change. Jointly estimating geometric and photometric transformations is thus important for many tasks such as image mosaicing. We propose an algorithm to jointly estimate groupwise geometric and photometric transformations while preserving the efficient pre-computation based design of the original inverse compositional algorithm. It is called the dual inverse compositional algorithm. It uses different approximations than the simultaneous inverse compositional algorithm and handles groupwise geometric and global photometric transformations. Its name stems from the fact that it uses an inverse compositional update rule for both the geometric and the photometric transformations. We demonstrate the proposed algorithm and compare it to previous ones on simulated and real data. This shows clear improvements in computational efficiency and in terms of convergence.

Registering images of a deforming surface is a well-studied problem. It is common practice to describe the image deformation fields with thin-plate splines. This has the advantage to involve small numbers of parameters, but has the drawback that the 3D surface is not explicitly reconstructed. We propose an image deformation model combining thin-plate splines with 3D entities-a 3D control mesh and a camera-overcoming the above mentioned drawback. An original solution to the non-rigid image registration problem using this model is proposed and demonstrated on simulated and real data.

Estimating the pose of an imaging sensor is a central research problem. Many solutions have been proposed for the case of a rigid environment. In contrast, we tackle the case of a non-rigid environment observed by a 3D sensor, which has been neglected in the literature. We represent the environment as sets of time-varying 3D points explained by a low-rank shape model, that we derive in its implicit and explicit forms. The parameters of this model are learnt from data gathered by the 3D sensor. We propose a learning algorithm based on minimal 3D non-rigid tensors that we introduce. This is followed by a maximum likelihood nonlinear refinement performed in a bundle adjustment manner. Given the learnt environment model, we compute the pose of the 3D sensor, as well as the deformations of the environment, that is, the non-rigid counterpart of pose, from new sets of 3D points. We validate our environment learning and pose estimation modules on simulated and real data

Registering images of a deforming surface is a well-studied problem. Solutions include computing optic flow or estimating a parameterized motion model. In the case of optic flow it is necessary to include some regularization. We propose an approach based on representing the induced transformation between images using Radial Basis Functions (RBF). The approach can be viewed as a direct, i.e. intensity-based, method, or equivalently, as a way of using RBFs as non-linear regularizers on the optic flow field. The approach is demonstrated on several image sequences of deforming surfaces. It is shown that the computed registrations are sufficiently accurate to allow convincing augmentations of the images. 1

Standard bundle adjustment techniques for Euclidean reconstruction consider camera intrinsic parameters as unknowns in the optimization process. Obviously, the speed of an optimization process is directly related to the number of unknowns and to the form of the cost function. The scheme proposed in this paper differs from previous standard techniques since unknown camera intrinsic parameters are not considered in the optimization process. Considering fewer unknowns in the optimization process produces a faster algorithm, which is more adapted to time-dependent applications such as robotics. Computationally expensive metric reconstruction, using for example several zooming cameras, considerably benefits from an intrinsics-free bundle adjustment.

Abstract In this paper we describe a method for analysing video sequences and for representing them as mosaics or panoramas. Previous work on video mosaicking essentially concentrated on static scenes. We generalize these approaches to the case of a rotating camera observing both static and moving objects where the static portions of the scene are not necessarily dominant, as it has been often hypothesized in the past. We start by describing a robust technique for accurately aligning a large number of video frames under unknown camera rotations and camera settings. The alignment technique combines a feature‐based method (initialization and refinement) with rough motion segmentation followed by a colour‐based direct method (final adjustment). This precise frame‐to‐frame alignment allows the dynamic building of a background representation as well as an efficient segmentation of each image such that moving regions of arbitrary shape and size are aligned with the static background. Thus a motion panorama visualizes both dynamic and static scene elements in a geometrically consistent way. Extensive experiments applied to archived videos of track‐and‐field events validate the approach. Copyright © 2004 John Wiley & Sons, Ltd.

The purpose of this paper is to give a very simple method for nonlinearly estimating the fundamental matrix using the minimum number of seven parameters. Instead of minimally parameterizing it, we rather update what we call its orthonormal representation, which is based on its singular value decomposition. We show how this method can be used for efficient bundle adjustment of point features seen in two views. Experiments on simulated and real data show that this implementation performs better than others in terms of computational cost, i.e., convergence is faster, although methods based on minimal parameters are more likely to fall into local minima than methods based on redundant parameters.

Using the so-called closure constraints, it is possible to estimate the projection matrices of the cameras observing a static scene given correspondences between multiple views. We present a batch algorithm for recovering all the cameras based on the closure constraints. The approach is motivated by the necessity of including as much information as possible in the initial recovery of the motion, as is done in factorisation schemes. The main advantage of the proposed method over factorisation is that it naturally deals with missing data. Compared to other algorithms, the method is very fast and flexible in terms of the selection of input data.

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.

Bundle adjustment is used to obtain accurate visual reconstructions by minimizing the reprojection error. The coordinate frame ambiguity, or more generality the gauge freedoms, has been dealt with in different manners. It has often been reported that standard bundle adjustment algorithms were not gauge invariant: two iterations within different gauges can lead to geometrically very different results. Surprisingly, most algorithms do not exploit gauge freedoms to improve performances. We consider this issue. We analyze theoretically the impact of the gauge on standard algorithms. We show that a sufficiently general damping matrix in Levenberg-Marquardt iteration can be used to implicitly reproduce a gauge transformation. We show that if the damping matrix is chosen such that the decrease in the reprojection error is maximized, then the iteration is gauge invariant. Experimental results on simulated and real data show that our gauge invariant bundle adjustment algorithm outperforms existing ones in terms of stability.

We address the problem of camera motion and structure reconstruction from line correspondences across multiple views, from initialization to final bundle adjustment. One of the main difficulties when dealing with line features is their algebraic representation. First, we consider the triangulation problem. Based on Plucker coordinates to represent the lines, we propose a maximum likelihood algorithm, relying on linearising the Plucker constraint, and on a Plucker correction procedure to compute the closest Plucker coordinates to a given 6-vector. Second, we consider the bundle adjustment problem. Previous overparameterizations of 3D lines induce gauge freedoms and/or internal consistency constraints. We propose the orthonormal representation, which allows handy nonlinear optimization of 3D lines using the minimum 4 parameters, within an unconstrained nonlinear optimizer. We compare our algorithms to existing ones on simulated and real data.

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 consider structure and motion recovery for scenes consisting of static and dynamic features.More particularly, we consider a single moving uncalibrated camera observing a scene consisting of points moving along straight lines converging to a unique point and lying on a motion plane.This scenario may describe a roadway observed by a moving camera whose motion is unknown.We show that there exist matching tensors similar to fundamental matrices.We derive the link between dynamic and static structure and motion and show how the equation of the motion plane (or equivalently the plane homographies it induces between images) may be recovered from dynamic features only.Experimental results on real images are provided, in particular on a 60-frames video sequence.

In this paper, we investigate the problem of the automatic creation of 3D models of man-made environments that we represent as collections of textured planes. A typical approach is to automatically compute a sparse feature reconstruction and to manually give their plane-memberships as well as the delineation of the planes. Textures are then extracted from the images while optimizing the model, typically the disparity between marked and predicted edges. We propose a means to automatically estimate the model of the scene, in terms of the number of planes and their parameters from a point feature reconstruction. The method is based on random sampling of reconstructed points to generate plane hypotheses. Each of these is then evaluated using a measure of approximate photoconsistency while recovering the corresponding plane delineation. We then compute the maximum likelihood estimate of all scene parameters, i.e. the set of planes and reconstructed points as well as relative camera pose, with respect to actual images. The approach is validated on simulated data and real images.

We study the problem of aligning two 3D line reconstructions expressed in Plucker line coordinates. We introduce the 6/spl times/6 3D line motion matrix that acts on Plucker coordinates in projective, affine or Euclidean space. We characterize its algebraic properties and its relation to the usual 4/spl times/4 point motion matrix, and propose various methods for estimating 3D motion from line correspondences, based on image-related and 3D cost functions. We assess the quality of the different estimation methods using simulated data and real images.