Exponential families are widely used in machine learning, including many distributions in continuous and discrete domains (e.g., Gaussian, Dirichlet, Poisson, and categorical distributions via the softmax transformation). Distributions in each of these families have fixed support. In contrast, for finite domains, recent work on sparse alternatives to softmax (e.g., sparsemax, $\alpha$-entmax, and fusedmax), has led to distributions with varying support. This paper develops sparse alternatives to continuous distributions, based on several technical contributions: First, we define $\Omega$-regularized prediction maps and Fenchel-Young losses for arbitrary domains (possibly countably infinite or continuous). For linearly parametrized families, we show that minimization of Fenchel-Young losses is equivalent to moment matching of the statistics, generalizing a fundamental property of exponential families. When $\Omega$ is a Tsallis negentropy with parameter $\alpha$, we obtain “deformed exponential families,” which include $\alpha$-entmax and sparsemax ($\alpha=2$) as particular cases. For quadratic energy functions, the resulting densities are $\beta$-Gaussians, an instance of elliptical distributions that contain as particular cases the Gaussian, biweight, triweight, and Epanechnikov densities, and for which we derive closed-form expressions for the variance, Tsallis entropy, and Fenchel-Young loss. When $\Omega$ is a total variation or Sobolev regularizer, we obtain a continuous version of the fusedmax. Finally, we introduce continuous-domain attention mechanisms, deriving efficient gradient backpropagation algorithms for $\alpha \in \{1,\frac{4}{3}, \frac{3}{2}, 2\}$. Using these algorithms, we demonstrate our sparse continuous distributions for attention-based audio classification and visual question answering, showing that they allow attending to time intervals and compact regions.

The majority of current object detectors lack context: class predictions are made independently from other detections. We propose to incorporate context in object detection by post-processing the output of an arbitrary detector to rescore the confidences of its detections. Rescoring is done by conditioning on contextual information from the entire set of detections: their confidences, predicted classes, and positions. We show that AP can be improved by simply reassigning the detection confidence values such that true positives that survive longer (i.e., those with the correct class and large IoU) are scored higher than false positives or detections with small IoU. In this setting, we use a bidirectional RNN with attention for contextual rescoring and introduce a training target that uses the IoU with ground truth to maximize AP for the given set of detections. The fact that our approach does not require access to visual features makes it computationally inexpensive and agnostic to the detection architecture. In spite of this simplicity, our model consistently improves AP over strong pre-trained baselines (Cascade R-CNN and Faster R-CNN with several backbones), particularly by reducing the confidence of duplicate detections (a learned form of non-maximum suppression) and removing out-of-context objects by conditioning on the confidences, classes, positions, and sizes of the co-occurrent detections. Code is available at https://github.com/LourencoVazPato/seeing-without-looking/.

Exponential families are widely used in machine learning; they include many distributions in continuous and discrete domains (e.g., Gaussian, Dirichlet, Poisson, and categorical distributions via the softmax transformation). Distributions in each of these families have fixed support. In contrast, for finite domains, there has been recent work on sparse alternatives to softmax (e.g., sparsemax and alpha-entmax), which have varying support, being able to assign zero probability to irrelevant categories. These discrete sparse mappings have been used for improving interpretability of neural attention mechanisms. This paper expands that work in two directions: first, we extend alpha-entmax to continuous domains, revealing a link with Tsallis statistics and deformed exponential families. Second, we introduce continuous-domain attention mechanisms, deriving efficient gradient backpropagation algorithms for alpha in {1,2}. Experiments on attention-based text classification, machine translation, and visual question answering illustrate the use of continuous attention in 1D and 2D, showing that it allows attending to time intervals and compact regions.

We discuss the usage of symmetric polynomials for representing 2D shapes in their most general form, i.e., arbitrary sets of unlabeled points in the plane. Although particular families of these polynomials have been used in the past, we present general results that pave the way for the development of new representations that exhibit key properties for shape recognition. We show that all monomial symmetric polynomials satisfy homogeneity, which enables leveraging on previous work on spectral invariants to obtain invariance/completeness with respect to shape orientation. Representations based on symmetric polynomials are invariant to shape point relabeling. We single out elementary symmetric polynomials and power sums as particular families of polynomials that further enable obtaining completeness with respect to point labeling. We discuss the efficient computation of these polynomials and study how perturbations in the shape point coordinates affect their values.

Current methods for line segment extraction often fail in challenging scenarios that abound in real-life images, e.g., those containing corrupted lines, of various widths, with multiple crossings, and immersed in clutter. We propose a method that tackles these issues by combining multiscale edges while taking line segment connectivity into account. In particular, we use two scales originating what we call contextual and local edges, obtained with filters of, respectively, large and small footprints. Contextual edges are robust to noise and our method uses them validate local edges, i.e., to only select the local edges that correspond to the same intensity transition (dark-to-bright or vice-versa). Line segment connectivity is enforced by joining the valid local edges whose distance does not exceed a threshold. To enable dealing with situations where the edges divide regions of non-uniform intensity distributions, e.g., textures, the contextual edges are decided by using a two-sample statistical test. We present experiments that illustrate how our method is efficient in extracting complete segments in several situations where current methods fail.

We address the representation of two-dimensional shape in its most general form, i.e., arbitrary sets of points, that may arise in multiple situations, e.g., sparse sets of specific landmarks, or dense sets of image edge points. Our goal are recognition tasks, where the key is balancing two contradicting demands: shapes that differ by rigid transformations or point re-labeling should have the same representation (invariance) but geometrically distinct shapes should have different representations (completeness). In the paper, we introduce a new shape representation that marries properties of the elementary symmetric polynomials and the bispectrum. Like the power spectrum, the bispectrum is insensitive to signal shifts; however, unlike the power spectrum, the bispectrum is complete. The elementary symmetric polynomials are complete and invariant to variable relabeling. We show that the elementary symmetric polynomials of the shape points depend on the shape orientation in a way that enables interpreting them in the frequency domain and building from them a bispectrum. The result is a shape representation that is complete and invariant to rigid transformations and point-relabeling. The paper also reports experiments that illustrate the proved properties.

We propose a distributed, decentralized algorithm for solving separable optimization problems over a connected network of compute nodes. In a separable problem, each node has its own private function and its own private constraint set. Private means that no other node has access to it. The goal is to minimize the sum of all nodes' private functions, constraining the solution to be in the intersection of all the private sets. Our algorithm is based on the alternating direction method of multipliers (ADMM) and requires a coloring of the network to be available beforehand. We perform numerical experiments of the algorithm, applying it to compressed sensing problems. These show that the proposed algorithm requires in general less iterations, and hence less communication between nodes, than previous algorithms to achieve a given accuracy.

We address the problem of 6D pose estimation of a textureless and shiny object from single-view 2D images, for a bin-picking task. For a textureless object like a mechanical part, conventional visual feature matching usually fails due to the absence of rich texture features. Hierarchical template matching assumes that few templates can cover all object appearances. However, the appearance of a shiny object largely depends on its pose and illumination. Furthermore, in a bin-picking task, we must cope with partial occlusions, shadows, and inter-reflections.

Global voting schemes based on the Hough transform (HT) have been widely used to robustly detect lines in images. However, since the votes do not take line connectivity into account, these methods do not deal well with cluttered images. On the other hand, the so-called local methods enforce connectivity but lack robustness to deal with challenging situations that occur in many realistic scenarios, e.g., when line segments cross or when long segments are corrupted. We address the critical limitations of the HT as a line segment extractor by incorporating connectivity in the voting process. This is done by only accounting for the contributions of edge points lying in increasingly larger neighborhoods and whose position and directional information agree with potential line segments. As a result, our method, which we call segment extraction by connectivity-enforcing HT (STRAIGHT), extracts the longest connected segments in each location of the image, thus also integrating into the HT voting process the usually separate step of individual segment extraction. The usage of the Hough space mapping and a corresponding hierarchical implementation make our approach computationally feasible. We present experiments that illustrate, with synthetic and real images, how STRAIGHT succeeds in extracting complete segments in situations where current methods fail.

Basis Pursuit (BP) finds a minimum ℓ1-norm vector z that satisfies the underdetermined linear system Mz = b, where the matrix M and vector b are given. Lately, BP has attracted attention because of its application in compressed sensing, where it is used to reconstruct signals by finding the sparsest solutions of linear systems. In this paper, we propose a distributed algorithm to solve BP. This means no central node is used for the processing and no node has access to all the data: the rows of M and the vector b are distributed over a set of interconnected compute nodes. A typical scenario is a sensor network. The novelty of our method is in using an optimal first-order method to solve an augmented Lagrangian-based reformulation of BP. We implemented our algorithm in a computer cluster, and show that it can solve problems that are too large to be stored in and processed by a single node.

Although global voting schemes, such as the Hough Transform (HT), have been widely used to robustly detect lines in images, they fail when the line segments at hand are short, particularly if the underlying edge maps are cluttered. Line segment detection in these scenarios has been addressed using local methods, which lack robustness to missing data (interrupted lines) and typically fail when line segments cross. We propose a new method that tackles these problems: first, rough estimates of plural candidate directions at each edge point are obtained through a directional local HT; then, the parameters determining the line segments are globally estimated by maximizing a quality measure that depends on all the edge points. Our experiments illustrate that the proposed method outperforms current methods in challenging situations.

When comparing 2-D shapes, a key issue is their normalization. Translation and scale are easily taken care of by removing the mean and normalizing the energy. However, defining and computing the orientation of a 2-D shape is not so simple. In fact, although for elongated shapes the principal axis can be used to define one of two possible orientations, there is no such tool for general shapes. As we show in the paper, previous approaches fail to compute the orientation of even noiseless observations of simple shapes. We address this problem and show how to uniquely define the orientation of an arbitrary 2-D shape, in terms of what we call its Principal Moments. We start by showing that a small subset of these moments suffices to describe the underlying 2-D shape, i.e., that they form a compact representation, which is particularly relevant when dealing with large databases. Then, we propose a new method to efficiently compute the shape orientation: Principal Moment Analysis. Finally, we discuss how this method can further be applied to normalize gray-level images. Besides the theoretical proof of correctness, we describe experiments demonstrating robustness to noise and illustrating with real images.

Most approaches to learn classifiers for structured objects (e.g., images) use generative models in a classical Bayesian framework. However, state-of-the-art classifiers for vectorial data (e.g., support vector machines) are learned discriminatively. A generative embedding is a mapping from the object space into a fixed dimensional score space, induced by a generative model, usually learned from data. The fixed dimensionality of these generative score spaces makes them adequate for discriminative learning of classifiers, thus bringing together the best of the discriminative and generative paradigms. In particular, it was recently shown that this hybrid approach outperforms a classifier obtained directly for the generative model upon which the score space was built. Using a generative embedding involves two steps: (i) defining and learning the generative model and using it to build the embedding; (ii) discriminatively learning a (maybe kernel) classifier on the adopted score space. The literature on generative embeddings is essentially focused on step (i), usually using some standard off-the-shelf tool for step (ii). In this paper, we adopt a different approach, by focusing also on the discriminative learning step. In particular, we combine two very recent and top performing tools in each of the steps: (i) the free energy score space; (ii) non-extensive information theoretic kernels. In this paper, we apply this methodology in scene recognition. Experimental results on two benchmark datasets shows that our approach yields state-of-the-art performance.

When comparing 2D shapes, a key issue is their normalization. Translation and scale are easily taken care of by removing the mean and normalizing the energy. However, defining and computing the orientation of a 2D shape is not so simple. In fact, although for elongated shapes the principal axis can be used to define one of two possible orientations, there is not such a tool for general shapes. As we show in the paper, previous approaches fail to compute the orientation of even noiseless observations of simple shapes. We address this problem. In the paper, we show how to uniquely define the orientation of an arbitrary 2D shape, in terms of what we call its principal moments. We further propose a new method to efficiently compute the shape orientation: Principal Moments Analysis. Besides the theoretical proof of correctness, we describe experiments demonstrating robustness to noise and illustrating with real images.

Current texture analysis methods enable good discrimination but are computationally too expensive for applications which require high frame rates. This occurs because they use redundant calculations, failing in capturing the essence of the texture discrimination problem. In this paper we use a learning approach to obtain simple filters for this task. Although others have proposed learning-based methods, we are the first to simultaneously achieve discrimination rates comparable with state-of-the art methods at high frame rates. We particularize the general methodology to different filter structures, e.g., rotationally discriminant filters and rotationally invariant ones. We use Genetic Algorithms for learning and test our method against state-of-the-art ones, using the Brodatz album.

In this paper, a novel approach for contour based 2D shape recognition is proposed, using a class of information theoretic kernels recently introduced. This kind of kernels, based on a non-extensive generalization of the classical Shannon information theory, are defined on probability measures. In the proposed approach, chain code representations are first extracted from the contours; then n-gram statistics are computed and used as input to the information theoretic kernels. We tested different versions of such kernels, using support vector machine and nearest neighbor classifiers. An experimental evaluation on the Chicken pieces dataset shows that the proposed approach significantly outperforms the current state-of-the-art methods.

The analytic signature is a recently proposed 2D shape representation scheme. It is tailored to the representation of shapes described by arbitrary sets of unlabeled points, or landmarks, because its most distinctive feature is the maximal invariance to a permutation of those points. The shape similarity of two point clouds can then be obtained from a direct comparison of their representations. However, since the analytic signature is a continuous function, performing the comparison of their densely sampled versions may result excessively time-consuming, e.g., when dealing with large databases, even of simple shapes. In this paper we address the problem of efficiently storing and comparing such powerful representations. We start by showing that their frequency spectrum is related to particular complex moments of the shape. From this relation, we derive the bandwidth of the representation in terms of the shape complexity. Using this result, we show that the analytic signature can be described by a small set of complex moments. We call this compact description the principal moments (PMs) of a shape and show how to efficiently compare shapes using PMs. Our experiments illustrate that the gain in efficiency comes at no cost in performance.

From the recovery of structure from motion to the separation of style and content, many problems in computer vision have been successfully approached by using bilinear models. The reason for the success of these models is that a globally optimal decomposition is easily obtained from the singular value decomposition (SVD) of the observation matrix. However, in practice, the observation matrix is often incomplete, the SVD can not be used, and only suboptimal solutions are available. The majority of these solutions are based on iterative local refinements of a given cost function, and lack any guarantee of convergence to the global optimum. In this paper, we propose a globally optimal solution, for particular patterns of missing entries. To achieve this goal, we re-formulate the problem as the minimization of the spectral norm of the matrix of residuals, i.e., we seek the completion of the observation matrix such that the largest singular value of its difference to a low rank matrix is the smallest possible. The class of patterns of missing entries we deal with is known as the Young diagram, which includes, as particular cases, many relevant situations, such as the missing of an entire submatrix. We describe experiments that illustrate how our globally optimal solution has impact in practice.

Many applications require a computer representation of 2D shape, usually described by a set of 2D points. The challenge of this representation is that it must not only capture the characteristics of the shape but also be invariant to relevant transformations. Invariance to geometric transformations, such as translation, rotation and scale, has received attention in the past, usually under the assumption that the points are previously labeled, i.e., that the shape is characterized by an ordered set of landmarks. However, in many practical scenarios the landmarks are obtained from an automatic process, e.g., edge/corner detection, thus without natural ordering. In this paper, we represent 2D shapes in a way that is invariant to the permutation of the landmarks. Within our framework, a shape is mapped to an analytic function on the complex plane, leading to what we call its analytic signature (ANSIG). We show that different shapes lead to different ANSIGs but that shapes that differ by a permutation of the landmarks lead to the same ANSIG, i.e., that our representation is a maximal invariant with respect to the permutation group. To store an ANSIG, it suffices to sample it along a closed contour in the complex plane. We further show how easy it is to factor out geometric transformations when comparing shapes using the ANSIG representation. We illustrate the ANSIG capabilities in shape-based image classification.

Widely used SVD-based matrix factorization approaches to the recovery of 3D rigid structure from motion (SFM), require a set of feature points to be visible in a set of images. When there is occlusion, several feature points disappear, the observation matrix misses some entries, there is not equivalent to the SVD, and only suboptimal solutions have been proposed to exploit rigidity. In this paper, we propose a method to complete the trajectories that correspond to a rigid scene, in an optimal way. Our algorithm is not iterative (thus avoiding problems like sensitivity to initialization and local optima); it rather computes in a finite number of steps the globally optimal completion of the observation matrix. We describe experiments that illustrate the gain in accuracy of SFM.

We address two-dimensional shape-based classification, considering shapes described by arbitrary sets of unlabeled points, or landmarks. This is relevant in practice because, in many applications, the points describing the shapes come from automatic processes, e.g., edge detection, thus without labels. Rather than attempting to compute point correspondences (a quagmire, when dealing with nontrivial shapes), we use what we call the analytic signature (ANSIG) of the shapes, a representation that has the key feature of being invariant to point labeling. Geometric transformations, such as translation, rotation, and scale, and different cardinality of point sets, are also dealt with by this representation. We demonstrate the capabilities of our representation with several shape classification experiments.

Positive definite kernels on probability measures have been recently applied in structured data classification problems. Some of these kernels are related to classic information theoretic quantities, such as mutual information and the Jensen-Shannon divergence. Meanwhile, driven by recent advances in Tsallis statistics, nonextensive generalizations of Shannon's information theory have been proposed. This paper bridges these two trends. We introduce the Jensen-Tsallis q-difference, a generalization of the Jensen-Shannon divergence. We then define a new family of nonextensive mutual information kernels, which allow weights to be assigned to their arguments, and which includes the Boolean, Jensen-Shannon, and linear kernels as particular cases. We illustrate the performance of these kernels on text categorization tasks.

Recent approaches to classification of text, images, and other types of structured data, launched the quest for positive definite (p.d.) kernels on probability measures. In particular, kernels based on the Jensen-Shannon (JS) divergence and other information-theoretic quantities have been proposed. We introduce new JS-type divergences, by extending its two building blocks: convexity and Shannon’s entropy. These divergences are then used to define new information-theoretic kernels on measures. In particular, we introduce a new concept of q-convexity, for which a Jensen q-inequality is proved. Based on this inequality, we introduce the Jensen-Tsallis q-difference, a nonextensive generalization of the Jensen-Shannon divergence. Furthermore, we provide denormalization formulae for entropies and divergences, which we use to define a family of nonextensive information-theoretic kernels on measures. This family, grounded in nonextensive entropies, extends Jensen-Shannon divergence kernels, and allows assigning weights to its arguments.

When the scene background is known and the intensity of moving objects contrasts with the intensity of the background, the objects are easily captured by exploiting occlusion, e.g., background-subtraction. However, when processing general scenes, the background is not known and researchers have mostly attempted to segment moving objects by using motion cues rather than occlusion. Since motion can only be accurately computed at highly textured regions, current motion segmentation methods either fail to segment low textured objects, or require expensive regularization techniques. We present a computationally simple algorithm and test it with segmentation of moving objects in low texture / low contrast videos that are obtained in low-light scenes. The images in the sequence are modeled taking into account the rigidity of the moving object and the occlusion of the background. We formulate the problem as the minimization of a penalized likelihood cost. Relaxation of the weight of the penalty term leads to a simple solution to the nonlinear minimization. We describe experiments that illustrate the good performance of our method.

Early approaches to building mosaics by composing photographic images, assume the input images have similar exposures. Since this is unlikely to happen in practice, it became common to compensate for different exposures in the blending step, after the images have been registered, or aligned. However, registration methods usually assume brightness constancy and fail to align images with different exposures. Recent approaches to this problem lead to computationally complex solutions that require either robust statistics or nonlinear optimization. In this paper we propose a computationally simple method to jointly estimate the registration parameters and the parameters describing the exposure correction, directly from the image intensity values. We obtain closed-form solutions for the estimates of the exposure parameters. This enables the derivation of a simple two-step iterative algorithm to minimize the global cost. Our experiments show that this algorithm succeeds to register real images exhibiting simultaneously very distinct orientations and exposures.

The majority of the approaches to the automatic recovery of a panoramic image from a set of partial views are suboptimal in the sense that the input images are aligned, or registered, pair by pair, e.g., consecutive frames of a video clip. These approaches lead to propagation errors that may be very severe, particularly when dealing with videos that show the same region at disjoint time intervals. Although some authors have proposed a post-processing step to reduce the registration errors in these situations, there have not been attempts to compute the optimal solution, i.e., the registrations leading to the panorama that best matches the entire set of partial views. This is our goal. In this paper, we use a generative model for the partial views of the panorama and develop an algorithm to compute in an efficient way the maximum likelihood estimate of all the unknowns involved: the parameters describing the alignment of all the images and the panorama itself.

The problem of inferring 3D orientation of a camera from video sequences has been mostly addressed by first computing correspondences of image features. This intermediate step is now seen as the main bottleneck of those approaches. In this paper, we propose a new 3D orientation estimation method for urban (indoor and outdoor) environments, which avoids correspondences between frames. The scene property exploited by our method is that many edges are oriented along three orthogonal directions; this is the recently introduced Manhattan world (MW) assumption. The main contributions of this paper are: the definition of equivalence classes of equiprojective orientations, the introduction of a new small rotation model, formalizing the fact that the camera moves smoothly, and the decoupling of elevation and twist angle estimation from that of the compass angle. We build a probabilistic sequential orientation estimation method, based on an MW likelihood model, with the above-listed contributions allowing a drastic reduction of the search space for each orientation estimate. We demonstrate the performance of our method using real video sequences.

Layered video representations are increasingly popular; see [2] for a recent review. Segmentation of moving objects is a key step for automating such representations. Current motion segmentation methods either fail to segment moving objects in low-textured regions or are computationally very expensive. This paper presents a computationally simple algorithm that segments moving objects, even in low-texture/low-contrast scenes. Our method infers the moving object templates directly from the image intensity values, rather than computing the motion field as an intermediate step. Our model takes into account the rigidity of the moving object and the occlusion of the background by the moving object. We formulate the segmentation problem as the minimization of a penalized likelihood cost function and present an algorithm to estimate all the unknown parameters: the motions, the template of the moving object, and the intensity levels of the object and of the background pixels. The cost function combines a maximum likelihood estimation term with a term that penalizes large templates. The minimization algorithm performs two alternate steps for which we derive closed-form solutions. Relaxation improves the convergence even when low texture makes it very challenging to segment the moving object from the background. Experiments demonstrate the good performance of our method.

We address the automatic recovery of complete 3-D object models from video streams. Usually, complete 3-D models are built by fusing several depth maps, each computed from a small set of consecutive video frames, using structure from motion techniques. However, since from a small number of similar views, it is very difficult to obtain accurate depth maps, their fusion becomes nontrivial and human interaction is in general required to assemble the complete 3-D model. Instead of using intermediate depth maps, we propose a method to recover complete 3-D models directly from the 2-D motions in the entire set of available video frames. The difficulty that arises when processing long videos is that different regions of the object are seen at different time instants. Our method decides whether a region that has become visible is a region that was seen before, or a previously unseen region, by seeking the simplest rigid object that describes well the observed 2-D motions. This global approach increases significantly the accuracy of the estimates of the 3-D shape of the object and the 3-D motion of the camera. Experiments with artificial data and real video demonstrate the good performance of our method.

We address the problem of building a mosaic from uncalibrated images. The key issue in this problem is the registration of the images, i.e., the estimation of the parameters describing the global motion of the brightness pattern between them. Current approaches to global motion estimation avoid preprocessing steps, e.g., feature detection and matching, by inferring the motion parameters directly from the image intensities, through the minimization of the sum of the square error over a fixed window. This window is usually chosen as a large rectangle within the region where it is expected that the original images overlap. Although this leads to good results when the images to register have a large overlap, it often fails when the images exhibit only a small overlap, due to the requirement of choosing a priori a very small window. To overcome this limitation, we propose in this paper an adaptive window.

The problem of inferring 3D orientation of a camera from video sequences has been mostly addressed by first computing correspondences of image features. This intermediate step is now seen as the main bottleneck of those approaches. In this paper, we propose a new 3D orientation estimation method for urban (indoor and outdoor) environments, which avoids correspondences between frames. The basic scene property exploited by our method is that many edges are oriented along three orthogonal directions; this is the recently introduced Manhattan world (MW) assumption. In addition to the novel adoption of the MW assumption for video analysis, we introduce the small rotation (SR) assumption, that expresses the fact that the video camera undergoes a smooth 3D motion. Using these two assumptions, we build a probabilistic estimation approach. We demonstrate the performance of our method using real video sequences.

The paper describes the rank 1 weighted factorization solution to the structure from motion problem. This method recovers the 3D structure from the factorization of a data matrix that is rank 1 rather than rank 3. This matrix collects the estimates of the 2D motions of a set of feature points of the rigid object. These estimates are weighted by the inverse of the estimates error standard deviation so that the 2D motion estimates for "sharper" features, which are usually well-estimated, are given more weight, while the noisier motion estimates for "smoother" features are weighted less. We analyze the performance of the rank 1 weighted factorization algorithm to determine what are the most suitable 3D shapes or the best 3D motions to recover the 3D structure of a rigid object from the 2D motions of the features. Our approach is developed for the orthographic camera model. It avoids expensive singular value decompositions by using the power method and is suitable to handle dense sets of feature points and long video sequences. Experimental studies with synthetic and real data illustrate the good performance of our approach.

The majority of methods available to recover 3D structure from video assume that a set of feature points are tracked across a large number of frames. This is not always possible in real videos because the images overlap only partially, due to occlusion and limited field of view. The paper describes a new method to recover 3D structures from videos with partially overlapping views. The well known factorization method recovers 3D rigid structures by factoring an observation matrix that collects the trajectories of feature points (see Tomasi, C. and Kanade, T., Int. J. of Computer Vision, vol.9, no.2, 1992). We extend this method to the more challenging scenario of observing incomplete trajectories. In this way, we accommodate not only features that disappear, but also features that, although not visible in the first image, become available later. Under this scenario, the observation matrix has missing entries. We develop three new algorithms to factor out matrices with missing data. Experiments with synthetic data and real video images demonstrate the viability of our approach to recover 3D structure.

The paper computes the reliability of estimates of image motion parameters. The use of such measures of reliability to weight motion estimates improves significantly the performance of motion analysis tasks such as the recovery of 3D structure (see Irani, M. and Anandan, R., ECCV, vol.1, p.539-53, 2000; Aguiar, P.M.Q. and Moura, J.M.F., IEEE ICIP, vol.1, p.549-52, 2000). The paper relates both the estimation error variance and the stability of the estimation algorithm with the spatial gradient of the image brightness pattern. We illustrate the predictions of our expressions with several image brightness patterns.

This paper presents the surface-based factorization method to recover three-dimensional (3-D) structure, i.e., the 3-D shape and 3-D motion, of a rigid object from a two-dimensional (2-D) video sequence. The main ingredients of our approach are as follows: 1) we describe the unknown shape of the 3-D rigid object by polynomial patches; 2) projections of these patches in the image plane move according to parametric 2-D motion models; 3) we recover the parameters describing the 3-D shape and 3-D motion from the 2-D motion parameters by factorizing a matrix that is rank 1 in a noiseless situation. Our method is simultaneously an extension and a simplification of the original factorization method of Tomasi and Kanade (1992). We track regions where the 2-D motion in the image plane is described by a single set of parameters, avoiding the need to track a large number of pointwise features, in general, a difficult task. Then our method estimates the parameters describing the 3-D structure by factoring a rank 1 matrix, not rank 3 as in Tomasi and Kanade. This allows the use of fast iterative algorithms to compute the 3-D structure that best fits the data. Experimental results with real-life video sequences illustrate the good performance of our approach.

Factorization methods use linear subspace constraints to recover 3D rigid structures from 2D motion. Usually, these methods give equal weight to the contribution of each region (or feature) to the estimates of the 3D structure. In this paper, we accommodate different confidence weights for the 2D motion parameter estimates of each region, by rewriting the problem as the factorization of a modified matrix. This incurs no additional computational cost.

Vaidyanathan (1999) and Ferreira (1999) reported on nonlinear systems with exponential eigenfunctions. In this letter, we introduce a larger class of such systems, generated from a special family of exponential-input/constant-output operators that capture exponential signals from general inputs. In particular, we extend the classes of systems with exponential eigenfunctions defined in Vaidyanathan and Ferreira to include causal nonhomogeneous time-varying systems.

Tomasi and Kanade (1992) introduced the factorization method for recovering 3D structure from 2D video. In their formulation, the 3D shape and 3D motion are computed by using an SVD to approximate a matrix that is rank 3 in a noiseless situation. In this paper we reformulate the problem using the fact that the x and y coordinates of each feature are known from their projection onto the image plane in frame 1. We show how to compute the 3D shape, i.e., the relative depths z, and the 3D motion by a simple factorization of a matrix that is rank 1 in a noiseless situation. This allows the use of very fast algorithms even when using a large number of features and large number of frames. We also show how to accommodate confidence weights for the feature trajectories. This is done without additional computational cost by rewriting the problem as the factorization of a modified matrix.

The factorization method is a feature-based approach to recover 3D rigid structure from motion. In 1998, we extended their framework to recover a parametric description of the 3D shape. The 3D shape and 3D motion are computed by using an SVD to approximate a matrix that is rank 3 in a noiseless situation. In this paper, we develop a new algorithm that has two relevant advantages over the previous algorithms. First, instead of imposing a common origin for the parametric representation of the 3D surface patches, we allow the the specification of different origins for different patches. This improves the numerical stability of the image motion estimation algorithm and the accuracy of the 3D structure recovery algorithm. Second, we show how to compute the 3D shape and 3D motion by a simple factorization of a modified matrix that is rank 1 in a noiseless situation, instead of a rank 3 matrix. This allows the use of very fast algorithms even when using a large number of features (or regions) number of frames.

We build 3D models of rigid bodies from video sequences. The algorithm we use is simple and robust. It recovers the 3D shape parameters and the 3D motion parameters by first estimating the parameters of the induced optical flow representation. To estimate the 3D shape and 3D motion from the optical flow, we use a fast algorithm that is based on the factorization of a matrix that is rank 1 in a noiseless situation. We demonstrate our approach with a piecewise planar object shape built from a real life video clip. We highlight some of the potential applications of the 3D models obtained.

We generalize to 3D shaped mosaics the generative video representation of video sequences introduced by Jasinschi and Moura (see Proceedings of the IEEE International Conference on Image Processing, Washington DC, USA, October 1995). Using a parametric representation of the 3D shape, we recover the 3D shape and 3D motions from the 2D motions in the video sequence. We consider piecewise planar object shapes under orthography and demonstrate our approach with a real life video clip.

When the color or gray level of a moving object is very similar to that of the background, motion-based segmentation methods fail. This leads to ambiguous templates for the moving objects. We propose a method that segments unambiguously from motion the templates of the moving objects. Our method, which we call incremental motion segmentation integrates over time the small differences between the gray level of the moving object and that of the background. Our experiments with segmenting a robot soccer video clip show the quality of our results.

The paper studies segmentation of moving objects with low texture in a low textured background. We describe an algorithm that resolves the difficulties associated with other approaches by integrating over time the information in the video sequence. We motivate and demonstrate our approach by building the background and moving object world images, important constructs in generative video.