EigenTracking: Robust Matching and Tracking of Articulated Objects Using a View-Based Representation

This paper describes an approach for tracking rigid and articulated objects using a view-based representation. The approach builds on and extends work on eigenspace representations, robust estimation techniques, and parameterized optical flow estimation. First, we note that the least-squares image reconstruction of standard eigenspace techniques has a number of problems and we reformulate the reconstruction problem as one of robust estimation. Second we define a subspace constancy assumption that allows us to exploit techniques for parameterized optical flow estimation to simultaneously solve for the view of an object and the affine transformation between the eigenspace and the image. To account for large affine transformations between the eigenspace and the image we define a multi-scale eigenspace representation and a coarse-to-fine matching strategy. Finally, we use these techniques to track objects over long image sequences in which the objects simultaneously undergo both affine image motions and changes of view. In particular we use this EigenTracking technique to track and recognize the gestures of a moving hand.     

A Multibody Factorization Method for Independently Moving Objects

The structure-from-motion problem has been extensively studied in the field of computer vision. Yet, the bulk of the existing work assumes that the scene contains only a single moving object. The more realistic case where an unknown number of objects move in the scene has received little attention, especially for its theoretical treatment. In this paper we present a new method for separating and recovering the motion and shape of multiple independently moving objects in a sequence of images. The method does not require prior knowledge of the number of objects, nor is dependent on any grouping of features into an object at the image level. For this purpose, we introduce a mathematical construct of object shapes, called the shape interaction matrix, which is invariant to both the object motions and the selection of coordinate systems. This invariant structure is computable solely from the observed trajectories of image features without grouping them into individual objects. Once the matrix is computed, it allows for segmenting features into objects by the process of transforming it into a canonical form, as well as recovering the shape and motion of each object. The theory works under a broad set of projection models (scaled orthography, paraperspective and affine) but they must be linear, so it excludes projective cameras.     

Head Movements for Depth Perception: Praying Mantis versus Pigeon

Inspired by the abilities of both the praying mantis and the pigeon to judge distance by use of motion-based visually mediated odometry, we create miniature models for depth estimation that are similar to the head movements of these animals. We develop mathematical models of the praying mantis and pigeon visual behavior and describe our implementations and experimental environment. We investigate structure from motion problems when images are taken from a camera whose focal point is translating according to each of the biological models. This motion in the first case is reminiscent of a praying mantis peering its head left and right, apparently to obtain depth perception, hence the moniker mantis head camera. In the second case this motion is reminiscent of a pigeon bobbing its head back and forth, also apparently to obtain depth perception, hence the moniker pigeon head camera. We present the performance of the mantis head camera and pigeon head camera models and provide experimental results and error analysis of the algorithms. We provide the comparison of the definitiveness of the results obtained by both models. The precision of our mathematical model and its implementation is consistent with the experimental facts obtained from various biological experiments.     

A Direct Interpretation of Dynamic Images with Camera and Object Motions for Vision Guided Robot Control

A general scheme to represent the relation between dynamic images and camera and/or object motions is proposed for applications to visual control of robots. We consider the case where a moving camera observes moving objects in a static scene. The camera obtains images of the objects moving within the scene. Then, the possible combinations of the camera and the objects' poses and the obtained images are not arbitrary but constrained to each other. Here we represent this constraint as a lower dimensional hypersurface in the product space of the whole combination of their motion control parameters and image data. The visual control is interpreted as to find a path on this surface leading to their poses where a given goal image will be obtained. In this paper, we propose a visual control method to utilize tangential properties of this surface. First, we represent images with a composition of a small number of eigen images by using K-L (Karhunen-Loève) expansion. Then, we consider to reconstruct the eigen space (the eigen image space) to achieve efficient and straightforward controls. Such reconstruction of the space results in the constraint surface being mostly flat within the eigen space. By this method, visual control of robots in a complex configuration is achieved without image processing to extract and correspond image features in dynamic images. The method also does not need camera or hand-eye calibrations. Experimental results of visual servoing with the proposed method show the feasibility and applicability of our newly proposed approach to a simultaneous control of camera self-motion and object motions.     

3-D interpretation of optical flow by renormalization

This article studies 3-D interpretation of optical flow induced by a general camera motion relative to a surface of general shape. First, we describe, using the image sphere representation, an analytical procedure that yields an exact solution when the data are exact: we solve theepipolar equation written in terms of theessential parameters and thetwisted optical flow. Introducing a simple model of noise, we then show that the solution is statistically biased. In order to remove the statistical bias, we propose an algorithm calledrenormalization, which automatically adjusts to unknown image noise. A brief discussion is also given to thecritical surface that yields ambiguous 3-D interpretations and the use of theimage plane representation.     

Image Registration, Optical Flow and Local Rigidity

We address the theoretical problems of optical flow estimation and image registration in a multi-scale framework in any dimension. Much work has been done based on the minimization of a distance between a first image and a second image after applying deformation or motion field. Usually no justification is given about convergence of the algorithm used. We start by showing, in the translation case, that convergence to the global minimum is made easier by applying a low pass filter to the images hence making the energy convex enough. In order to keep convergence to the global minimum in the general case, we introduce a local rigidity hypothesis on the unknown deformation. We then deduce a new natural motion constraint equation (MCE) at each scale using the Dirichlet low pass operator. This transforms the problem to solving the energy minimization in a finite dimensional subspace of approximation obtained through Fourier Decomposition. This allows us to derive sufficient conditions for convergence of a new multi-scale and iterative motion estimation/registration scheme towards a global minimum of the usual nonlinear energy instead of a local minimum as did all previous methods. Although some of the sufficient conditions cannot always be fulfilled because of the absence of the necessary a priori knowledge on the motion, we use an implicit approach. We illustrate our method by showing results on synthetic and real examples in dimension 1 (signal matching, Stereo) and 2 (Motion, Registration, Morphing), including large deformation experiments.     

Analog hardware for detecting discontinuities in early vision

The detection of discontinuities in motion, intensity, color, and depth is a well-studied but difficult problem in computer vision [6]. We discuss the first hardware circuit that explicitly implements either analog or binary line processes in a deterministic fashion. Specifically, we show that the processes of smoothing (using a first-order or membrane type of stabilizer) and of segmentation can be implemented by a single, two-terminal nonlinear voltage-controlled resistor, the resistive fuse; and we derive its current-voltage relationship from a number of deterministic approximations to the underlying stochastic Markov random fields algorthms. The concept that the quadratic variation functionals of early vision can be solved via linear resistive networks minimizing power dissipation [37] can be extended to non-convex variational functionals with analog or binary line processes being solved by nonlinear resistive networks minimizing the electrical co-content.We have successfully designed, tested, and demonstrated an analog CMOS VLSI circuit that contains a 1D resistive network of fuses implementing piecewise smooth surface interpolation. We furthermore demonstrate the segmenting abilities of these analog and deterministic line processes by numerically simulating the nonlinear resistive network computing optical flow in the presence of motion discontinuities. Finally, we discuss various circuit implementations of the optical flow computation using these circuits.     

Destination Driven Motion Planning via Obstacle Motion Prediction and Multi-State Path Repair

This paper presents a real-time navigating system named Destination Driven Navigator for a mobile robot operating in unstructured static and dynamic environments. We have designed a new obstacle representation method named Cross-Line Obstacle Representation and a new concept work space to reduce the robot's search space and the environment storage cost, an Adapted Regression Model to predict dynamic obstacles' motion, Multi-State Path Repair rules to quickly translate an infeasible path into feasible one, and the path-planning algorithm to generate a path. A high-level Destination Driven Navigator uses these methods, models and algorithms to guide a mobile robot traveling in various environments while avoiding static and dynamic obstacles. A group of experiments has been conducted. The results exhibit that the Destination Driven Navigator is a powerful and effective paradigm for robot motion planning and obstacle avoidance.     

Closed-form solutions to image flow equations for 3D structure and motion

A major source of three-dimensional (3D) information about objects in the world is available to the observer in the form of time-varying imagery. Relative motion between textured objects and the observer generates a time-varying optic array at the image, from which image motion of contours, edge fragments, and feature points can be extracted. These dynamic features serve to sample the underlying image flow field. New, closed-form solutions are given for the structure and motion of planar and curved surface patches from monocular image flow and its derivatives through second order. Both planar and curved surface solutions require at most, the solution of a cubic equation. The analytic solution for curved surface patches combines the transformation of Longuet-Higgins and Prazdny [25] with the planar surface solution of Subbarao and Waxman [43]. New insights regarding uniqueness of solutions also emerge. Thus, the structure-motion coincidence of Waxman and Ullman [54] is interpreted as the duality of tangent plane solutions. The multiplicity of transformation angles (up to three) is related to the sign of the Gaussian curvature of the surface patch. Ovoid patches (i.e., bowls) are shown to possess a unique transform angle, though they are subject to the local structure-motion coincidence. Thus, ovoid patches almost always yield a unique 3D interpretation. In general, ambiguous solutions can be resolved by requiring continuity of the solution over time.The support of the Defense Advanced Research Projects Agency and the U.S. Army Night Vision Laboratory under Contract DAAK70-83-K-0018 (DARPA Order 3206) is gratefully acknowledged.     

Simultaneous stabilizability of three linear systems is rationally undecidable

We show that the simultaneous stabilizability of three linear systems, that is the question of knowing whether three linear systems are simultaneously stabilizable, is rationally undecidable. By this we mean that it is not possible to find necessary and sufficient conditions for simultaneous stabilization of the three systems in terms of expressions involving the coefficients of the three systems and combinations of arithmetical operations (additions, subtractions, multiplications, and divisions), logical operations (and and or), and sign test operations (equal to, greater than, greater than or equal to,...).     

Linearly Combining Density Estimators via Stacking

This paper presents experimental results with both real and artificial data combining unsupervised learning algorithms using stacking. Specifically, stacking is used to form a linear combination of finite mixture model and kernel density estimators for non-parametric multivariate density estimation. The method outperforms other strategies such as choosing the single best model based on cross-validation, combining with uniform weights, and even using the single best model chosen by Cheating and examining the test set. We also investigate (1) how the utility of stacking changes when one of the models being combined is the model that generated the data, (2) how the stacking coefficients of the models compare to the relative frequencies with which cross-validation chooses among the models, (3) visualization of combined effective kernels, and (4) the sensitivity of stacking to overfitting as model complexity increases.     

A semi-automatic system for edge tracking with snakes

Active contour models, or snakes, developed in (Kass et al. 1988), use a simple physical model to track edges in image sequences. Snakes as originally defined however, tend to shrink, stretch and slide back and forth in unwanted ways along a tracked edge and are also confused by multiple edges, always grabbing the nearest one. In this paper a semi-automatic system is presented that combines motion estimation techniques with snakes to overcome these problems. An algorithm is presented that uses a block matching technique to guide the endpoints of the snake, optical flow to push the snake in the direction of the underlying motion, followed by the traditional snake edge-fitting minimization process. We use this technique for tracking facial features of an actor for driving computer animated characters.     

Observability of 3D Motion

This paper examines the inherent difficulties in observing 3D rigid motion from image sequences. It does so without considering a particular estimator. Instead, it presents a statistical analysis of all the possible computational models which can be used for estimating 3D motion from an image sequence. These computational models are classified according to the mathematical constraints that they employ and the characteristics of the imaging sensor (restricted field of view and full field of view). Regarding the mathematical constraints, there exist two principles relating a sequence of images taken by a moving camera. One is the epipolar constraint, applied to motion fields, and the other the positive depth constraint, applied to normal flow fields. 3D motion estimation amounts to optimizing these constraints over the image. A statistical modeling of these constraints leads to functions which are studied with regard to their topographic structure, specifically as regards the errors in the 3D motion parameters at the places representing the minima of the functions. For conventional video cameras possessing a restricted field of view, the analysis shows that for algorithms in both classes which estimate all motion parameters simultaneously, the obtained solution has an error such that the projections of the translational and rotational errors on the image plane are perpendicular to each other. Furthermore, the estimated projection of the translation on the image lies on a line through the origin and the projection of the real translation. The situation is different for a camera with a full (360 degree) field of view (achieved by a panoramic sensor or by a system of conventional cameras). In this case, at the locations of the minima of the above two functions, either the translational or the rotational error becomes zero, while in the case of a restricted field of view both errors are non-zero. Although some ambiguities still remain in the full field of view case, the implication is that visual navigation tasks, such as visual servoing, involving 3D motion estimation are easier to solve by employing panoramic vision. Also, the analysis makes it possible to compare properties of algorithms that first estimate the translation and on the basis of the translational result estimate the rotation, algorithms that do the opposite, and algorithms that estimate all motion parameters simultaneously, thus providing a sound framework for the observability of 3D motion. Finally, the introduced framework points to new avenues for studying the stability of image-based servoing schemes.     

Modular Robot Motion Planning Using Similarity Metrics

In order for a modular self-reconfigurable robotic system to autonomously change from its current state to a desired one, it is critical to have a cost function (or metric) that reflects the effort required to reconfigure. A reconfiguration sequence can consist of single module motions, or the motion of a branch of modules. For single module motions, the minimization of metrics on the set of sets of module center locations serves as the driving force for reconfiguration. For branch motions, the question becomes which branches should be moved so as to minimize overall effort. Another way to view this is as a pattern matching problem in which the desired configuration is viewed as a void, and we seek branch motions that best fill the void. A precise definition of goodness of fit is therefore required. In this paper, we address the fundamental question of how closely geometric figures can be made to match under a given group of transformations (e.g., rigid-body motions), and what it means to bisect two shapes. We illustrate these ideas in the context of applications in modular robot motion planning.     

Driving saccade to pursuit using image motion

Within the context of active vision, scant attention has been paid to the execution of motion saccades—rapid re-adjustments of the direction of gaze to attend to moving objects. In this paper we first develop a methodology for, and give real-time demonstrations of, the use of motion detection and segmentation processes to initiate capture saccades towards a moving object. The saccade is driven by both position and velocity of the moving target under the assumption of constant target velocity, using prediction to overcome the delay introduced by visual processing. We next demonstrate the use of a first order approximation to the segmented motion field to compute bounds on the time-to-contact in the presence of looming motion. If the bound falls below a safe limit, a panic saccade is fired, moving the camera away from the approaching object. We then describe the use of image motion to realize smooth pursuit, tracking using velocity information alone, where the camera is moved so as to null a single constant image motion fitted within a central image region. Finally, we glue together capture saccades with smooth pursuit, thus effecting changes in both what is being attended to and how it is being attended to. To couple the different visual activities of waiting, saccading, pursuing and panicking, we use a finite state machine which provides inherent robustness outside of visual processing and provides a means of making repeated exploration. We demonstrate in repeated trials that the transition from saccadic motion to tracking is more likely to succeed using position and velocity control, than when using position alone.     

The Least-Squares Error for Structure from Infinitesimal Motion

We analyze the least-squares error for structure from motion with a single infinitesimal motion (structure from optical flo). We present asymptotic approximations to the noiseless error over two, complementary regions of motion estimates: roughly forward and non-forward translations. Our approximations are powerful tools for understanding the error. Experiments show that they capture its detailed behavior over the entire range of motions. We illustrate the use of our approximations by deriving new properties of the least-squares error. We generalize the earlier results of Jepson/Heeger/Maybank on the bas-relief ambiguity and of Oliensis on the reflected minimum. We explain the error's complexity and its multiple local minima for roughly forward translation estimates (epipoles within the field of view) and identify the factors that make this complexity likely. For planar scenes, we clarify the effects of the two-fold ambiguity, show the existence of a new, double bas-relief ambiguity, and analyze the error's local minima. For nonplanar scenes, we derive simplified error approximations for reasonable assumptions on the image and scene. For example, we show that the error tends to have a simpler form when many points are tracked. We show experimentally that our analysis for zero image noise gives a good model of the error for large noise. We show theoretically and experimentally that the error for projective structure from motion is simpler but flatter than the error for calibrated images.     

Fast Local and Global Projection-Based Methods for Affine Motion Estimation

The demand for more effective compression, storage, and transmission of video data is ever increasing. To make the most effective use of bandwidth and memory, motion-compensated methods rely heavily on fast and accurate motion estimation from image sequences to compress not the full complement of frames, but rather a sequence of reference frames, along with differences between these frames which results from estimated frame-to-frame motion. Motivated by the need for fast and accurate motion estimation for compression, storage, and transmission of video as well as other applications of motion estimation, we present algorithms for estimating affine motion from video image sequences. Our methods utilize properties of the Radon transform to estimate image motion in a multiscale framework to achieve very accurate results. We develop statistical and computational models that motivate the use of such methods, and demonstrate that it is possible to improve the computational burden of motion estimation by more than an order of magnitude, while maintaining the degree of accuracy afforded by the more direct, and less efficient, 2-D methods.     

Optimal experiment design for estimating stochastic regression coefficients

The paper examines minimum-standard-error linear unbiased estimators of unknown stochastic regression coefficients using observations, of a noisy linear regression in a Hilbert space. Some, optimal design issues are considered for such estimators.Translated from Kibernetika, No. 2, pp. 98–104, March–April, 1990.     

Systematic Verb Polysemy in MT: A Study of Danish Motion Verbs with Comparisons with Spanish

In this paper we propose a semantic apparatus based on Frame Semanticswhich enables us to treat the systematic polysemy of Danish motionverbs in a satisfactory way in relation to Machine Translation (MT).Abandoning the strategy applied in more traditional MT systems whererelated and unrelated meanings are in essence treated alike, i.e. asunrelated, we suggest an approach where relatedness in meaning isexpressed via frame element assignments and where systematicallyderived senses can thus be generated on the basis of prototypicalsenses. By contrasting Danish data with Spanish, we demonstrate thatthe identified meaning variations in Danish motion verbs are crucialnot only for analysis but also in the transfer phase where deviationsin evoked frame elements prove to trigger translations which differfrom the prototypical translations of the relevant verbs.     

Test Signal Amplitude Optimization for Identification of the Volterra Kernels

The extremal problems of choosing the amplitudes of test signals used to construct the mathematical models of nonlinear dynamic systems in the form of Volterra polynomials of the second and third degrees were considered with an example of some reference dynamic systems.