We address the question of color-space interactions in the brain, by proposing a neural field model of color perception with spatial context for the visual area V1 of the cortex. Our framework reconciles two opposing perceptual phenomena, known as simultaneous contrast and chromatic assimilation. They have been previously shown to act synergistically, so that at some point in an image, the color seems perceptually more similar to that of adjacent neighbors, while being more dissimilar from that of remote ones. Thus, their combined effects are enhanced in the presence of a spatial pattern, and can be measured as larger shifts in color matching experiments. Our model supposes a hypercolumnar structure coding for colors in V1, and relies on the notion of color opponency introduced by Hering. The connectivity kernel of the neural field exploits the balance between attraction and repulsion in color and physical spaces, so as to reproduce the sign reversal in the influence of neighboring points. The color sensation at a point, defined from a steady state of the neural activities, is then extracted as a nonlinear percept conveyed by an assembly of neurons. It connects the cortical and perceptual levels, because we describe the search for a color match in asymmetric matching experiments as a mathematical projection on color sensations. We validate our color neural field alongside this color matching framework, by performing a multi-parameter regression to data produced by psychophysicists and ourselves. All the results show that we are able to explain the nonlinear behavior of shifts observed along one or two dimensions in color space, which cannot be done using a simple linear model.

We show how a Hopfield network with modifiable recurrent connections undergoing slow Hebbian learning can extract the underlying geometry of an input space. First, we use a slow and fast analysis to derive an averaged system whose dynamics derives from an energy function and therefore always converges to equilibrium points. The equilibria reflect the correlation structure of the inputs, a global object extracted through local recurrent interactions only. Second, we use numerical methods to illustrate how learning extracts the hidden geometrical structure of the inputs. Indeed, multidimensional scaling methods make it possible to project the final connectivity matrix onto a Euclidean distance matrix in a high-dimensional space, with the neurons labeled by spatial position within this space. The resulting network structure turns out to be roughly convolutional. The residual of the projection defines the nonconvolutional part of the connectivity, which is minimized in the process. Finally, we show how restricting the dimension of the space where the neurons live gives rise to patterns similar to cortical maps. We motivate this using an energy efficiency argument based on wire length minimization. Finally, we show how this approach leads to the emergence of ocular dominance or orientation columns in primary visual cortex via the self-organization of recurrent rather than feedforward connections. In addition, we establish that the nonconvolutional (or long-range) connectivity is patchy and is co-aligned in the case of orientation learning.

In this letter, we propose a general framework for studying neural mass models defined by ordinary differential equations. By studying the bifurcations of the solutions to these equations and their sensitivity to noise, we establish an important relation, similar to a dictionary, between their behaviors and normal and pathological, especially epileptic, cortical patterns of activity. We then apply this framework to the analysis of two models that feature most phenomena of interest, the Jansen and Rit model, and the slightly more complex model recently proposed by Wendling and Chauvel. This model-based approach allows us to test various neurophysiological hypotheses on the origin of pathological cortical behaviors and investigate the effect of medication. We also study the effects of the stochastic nature of the inputs, which gives us clues about the origins of such important phenomena as interictal spikes, interictal bursts, and fast onset activity that are of particular relevance in epilepsy.

Measuring erythrocyte velocity in individual microvessels has important applications for biomedical and functional imaging. Recent multiphoton fluorescence microscopy approaches require injecting fluorescent tracers; moreover, only one or few vessels can be imaged at a time. To overcome these shortcomings, we used CCD-based optical imaging of intrinsic absorption changes in macroscopic vascular networks to record erythrocytes' trajectories over several mm (2) of cortical surface. We then demonstrate the feasibility of erythrocyte velocity estimation from such wide-field data, using two robust, independent, algorithms. The first one is a recently published Radon transform-based algorithm that estimates erythrocyte velocity locally. We adapt it to data obtained in wide-field imaging and show, for the first time, its performance on such datasets. The second ("fasttrack") algorithm is novel. It is based on global energy minimization techniques to estimate the full spatiotemporal erythrocytes' trajectories inside vessels. We test the two algorithms on both simulated and biological data, obtained in rat cerebral cortex in a spreading depression experiment. On vessels with medium-slow erythrocyte velocities both algorithms performed well, allowing their usage as benchmark one for another. However, our novel fasttrack algorithm outperformed the other one for higher velocities, as encountered in the arterial network.

We address here the use of EEG and fMRI, and their combination, in order to estimate the full spatiotemporal patterns of activity on the cortical surface in the absence of any particular assumptions on this activity such as stimulation times. For handling such a high-dimension inverse problem, we propose the use of (1) a global forward model of how these measures are functions of the "neural activity" of a large number of sources distributed on the cortical surface, formalized as a dynamical system, and (2) adaptive filters, as a natural solution to solve this inverse problem iteratively along the temporal dimension. This estimation framework relies on realistic physiological models, uses EEG and fMRI in a symmetric manner, and takes into account both their temporal and spatial information. We use the Kalman filter and smoother to perform such an estimation on realistic artificial data and demonstrate that the algorithm can handle the high dimensionality of these data and that it succeeds in solving this inverse problem, combining efficiently the information provided by the two modalities (this information being naturally predominantly temporal for EEG and spatial for fMRI). It performs particularly well in reconstructing a random temporally and spatially smooth activity spread over the cortex. The Kalman filter and smoother show some limitations, however, which call for the development of more specific adaptive filters. First, they do not cope well with the strong nonlinearity in the model that is necessary for an adequate description of the relation between cortical electric activities and the metabolic demand responsible for fMRI signals. Second, they fail to estimate a sparse activity (i.e., presenting sharp peaks at specific locations and times). Finally their computational cost remains high. We use schematic examples to explain these limitations and propose further developments of our method to overcome them.

Neural continuum networks are an important aspect of the modeling of macroscopic parts of the cortex. Two classes of such networks are considered: voltage and activity based. In both cases, our networks contain an arbitrary number, n, of interacting neuron populations. Spatial nonsymmetric connectivity functions represent cortico-cortical, local connections, and external inputs represent nonlocal connections. Sigmoidal nonlinearities model the relationship between (average) membrane potential and activity. Departing from most of the previous work in this area, we do not assume the nonlinearity to be singular, that is, represented by the discontinuous Heaviside function. Another important difference from previous work is that we relax the assumption that the domain of definition where we study these networks is infinite, that is, equal to [Formula: see text] or [Formula: see text]. We explicitly consider the biologically more relevant case of a bounded subset Ω of [Formula: see text], a better model of a piece of cortex. The time behavior of these networks is described by systems of integro-differential equations. Using methods of functional analysis, we study the existence and uniqueness of a stationary (i.e., time-independent) solution of these equations in the case of a stationary input. These solutions can be seen as ‘persistent’; they are also sometimes called bumps. We show that under very mild assumptions on the connectivity functions and because we do not use the Heaviside function for the nonlinearities, such solutions always exist. We also give sufficient conditions on the connectivity functions for the solution to be absolutely stable, that is, independent of the initial state of the network. We then study the sensitivity of the solutions to variations of such parameters as the connectivity functions, the sigmoids, the external inputs, and, last but not least, the shape of the domain of existence Ω of the neural continuum networks. These theoretical results are illustrated and corroborated by a large number of numerical experiments in most of the cases 2 ⩽ n ⩽ 3, 2 ⩽ q ⩽ 3.

We propose to use bifurcation theory and pattern formation as theoretical probes for various hypotheses about the neural organization of the brain. This allows us to make predictions about the kinds of patterns that should be observed in the activity of real brains through, e.g., optical imaging, and opens the door to the design of experiments to test these hypotheses. We study the specific problem of visual edges and textures perception and suggest that these features may be represented at the population level in the visual cortex as a specific second-order tensor, the structure tensor, perhaps within a hypercolumn. We then extend the classical ring model to this case and show that its natural framework is the non-Euclidean hyperbolic geometry. This brings in the beautiful structure of its group of isometries and certain of its subgroups which have a direct interpretation in terms of the organization of the neural populations that are assumed to encode the structure tensor. By studying the bifurcations of the solutions of the structure tensor equations, the analog of the classical Wilson and Cowan equations, under the assumption of invariance with respect to the action of these subgroups, we predict the appearance of characteristic patterns. These patterns can be described by what we call hyperbolic or H-planforms that are reminiscent of Euclidean planar waves and of the planforms that were used in previous work to account for some visual hallucinations. If these patterns could be observed through brain imaging techniques they would reveal the built-in or acquired invariance of the neural organization to the action of the corresponding subgroups.

We introduce an original approach for the cerebral white matter connectivity mapping from diffusion tensor imaging (DTI). Our method relies on a global modeling of the acquired magnetic resonance imaging volume as a Riemannian manifold whose metric directly derives from the diffusion tensor. These tensors will be used to measure physical three-dimensional distances between different locations of a brain diffusion tensor image. The key concept is the notion of geodesic distance that will allow us to find optimal paths in the white matter. We claim that such optimal paths are reasonable approximations of neural fiber bundles. The geodesic distance function can be seen as the solution of two theoretically equivalent but, in practice, significantly different problems in the partial differential equation framework: an initial value problem which is intrinsically dynamic, and a boundary value problem which is, on the contrary, intrinsically stationary. The two approaches have very different properties which make them more or less adequate for our problem and more or less computationally efficient. The dynamic formulation is quite easy to implement but has several practical drawbacks. On the contrary, the stationary formulation is much more tedious to implement; we will show, however, that it has many virtues which make it more suitable for our connectivity mapping problem. Finally, we will present different possible measures of connectivity, reflecting the degree of connectivity between different regions of the brain. We will illustrate these notions on synthetic and real DTI datasets.

We propose a new approach to compute non-linear, intrinsic shape statistics and to incorporate them into a shape prior for an image segmentation task. Given a sample set of contours, we first define their mean shape as the one which is simultaneously closest to all samples up to rigid motions, and compute it in a gradient descent framework. We consider here a differentiable approximation of the Hausdorff distance between shapes. Statistics on the instantaneous deformation fields that the mean shape should undergo to move towards each sample lead to sensible characteristic modes of deformation that convey the shape variability. Contour statistics are turned into a shape prior which is rigid-motion invariant. Image segmentation results show the improvement gained by the shape prior.

We propose a novel, fast and robust technique for the computation of anatomical connectivity in the brain. Our approach exploits the information provided by Diffusion Tensor Magnetic Resonance Imaging (or DTI) and models the white matter by using Riemannian geometry and control theory. We show that it is possible, from a region of interest, to compute the geodesic distance to any other point and the associated optimal vector field. The latter can be used to trace shortest paths coinciding with neural fiber bundles. We also demonstrate that no explicit computation of those 3D curves is necessary to assess the degree of connectivity of the region of interest with the rest of the brain. We finally introduce a general local connectivity measure whose statistics along the optimal paths may be used to evaluate the degree of connectivity of any pair of voxels. All those quantities can be computed simultaneously in a Fast Marching framework, directly yielding the connectivity maps. Apart from being extremely fast, this method has other advantages such as the strict respect of the convoluted geometry of white matter, the fact that it is parameter-free, and its robustness to noise. We illustrate our technique by showing results on real and synthetic datasets. OurGCM(Geodesic Connectivity Mapping) algorithm is implemented in C++ and will be soon available on the web.

This article deals with statistics on sets of shapes. The approach is based on the Hausdorff distance between shapes, The choice of the Hausdorff distance between shapes is itself not fundamental since the same framework could be applied with another distance. We first define a smooth approximation of the Hausdorff distance and build non-supervised warpings between shapes by a gradient descent of the approximation. Local minima can be avoided by changing the scalar product in the tangent space of the shape being warped. When non-supervised warping fails, we present a way to guide the evolution with a small number of landmarks. Thanks to the warping fields, we can define the mean of a set of shapes and express statistics on them. Finally, we come back to the initial distance between shapes and use it to represent a set of shapes by a graph, which with the technique of graph Laplacian leads to a way of projecting shapes onto a low dimensional space

We present a mathematical model of a neural mass developed by a number of people, including Lopes da Silva and Jansen. This model features three interacting populations of cortical neurons and is described by a six-dimensional nonlinear dynamical system. We address some aspects of its behavior through a bifurcation analysis with respect to the input parameter of the system. This leads to a compact description of the oscillatory behaviors observed in Jansen and Rit (1995) (alpha activity) and Wendling, Bellanger, Bartolomei, and Chauvel (2000) (spike-like epileptic activity). In the case of small or slow variation of the input, the model can even be described as a binary unit. Again using the bifurcation framework, we discuss the influence of other parameters of the system on the behavior of the neural mass model.

In this paper, we present a new variational method for multi-view stereovision and non-rigid three-dimensional motion estimation from multiple video sequences. Our method minimizes the prediction error of the shape and motion estimates. Both problems then translate into a generic image registration task. The latter is entrusted to a similarity measure chosen depending on imaging conditions and scene properties. In particular, our method can be made robust to appearance changes due to non-Lambertian materials and illumination changes. It results in a simpler, more flexible, and more efficient implementation than existing deformable surface approaches. The computation time on large datasets does not exceed thirty minutes. Moreover, our method is compliant with a hardware implementation with graphics processor units. Our stereovision algorithm yields very good results on a variety of datasets including specularities and translucency. We have successfully tested our scene flow algorithm on a very challenging multi-view video sequence of a non-rigid scene.

Shape from shading is known to be an ill-posed problem. We show in this paper that if we model the problem in a different way than it is usually done, more precisely by taking into account the 1/r/sup 2/ attenuation term of the illumination, shape from shading becomes completely well-posed. Thus the shading allows to recover (almost) any surface from only one image (of this surface) without any additional data (in particular, without the knowledge of the heights of the solution at the local intensity "minima", contrary to [P. Dupuis et al. (1994), E. Prados et al. (2004), B. Horn (1986), E. Rouy et al. (1992), R. Kimmel et al. (2001)]) and without regularity assumptions (contrary to [J. Oliensis et al. (1993), R. Kimmel et al. (1995)], for example). More precisely, we formulate the problem as that of solving a new partial differential equation (PDE), we develop a complete mathematical study of this equation and we design a new provably convergent numerical method. Finally, we present results of our new shape from shading method on various synthetic and real images.

We propose a new approach to deal with the first and second order statistics of a set of images. These statistics take into account the images characteristic deformations and their variations in intensity. The central algorithm is based on nonsupervised diffeomorphic image matching (without landmarks or human intervention). As they convey the notion of the mean shape and colors of an object and the one of its common variations, such statistics of sets of images may be relevant in the context of object recognition, both in the segmentation of any of its representations and in the classification of them. The proposed approach has been tested on a small database of face images to compute a mean face and second order statistics. The results are very encouraging since, whereas the algorithm does not need any human intervention and is not specific to face image databases, the mean image looks like a real face and the characteristic modes of variation (deformation and intensity changes) are sensible.

This paper tackles an important aspect of the variational problems involving active contours, which has been largely overlooked so far: the optimization by gradient flows. Classically, the definition of a gradient depends directly on the choice of an inner product structure. This consideration is largely absent from the active contours literature. Most authors, overtly or covertly, assume that the space of admissible deformations is ruled by the canonical L2inner product. The classical gradient flows reported in the literature are relative to this particular choice. In this paper, we investigate the relevance of using other inner products, yielding other gradient descents, and some other minimizing flows not deriving from any inner product. In particular we, show how to induce different degrees of spatial coherence into the minimizing flow, in order to decrease the probability of getting trapped into irrelevant local minima. We show with some numerical experiments that the sensitivity of the active contours method to initial conditions, which seriously limits its applicability and its efficiency, is alleviated by our application-specific spatially coherent minimizing flows

The forward electroencephalography (EEG) problem involves finding a potential V from the Poisson equation inverted Delta x (sigma inverted Delta V) f, in which f represents electrical sources in the brain, and sigma the conductivity of the head tissues. In the piecewise constant conductivity head model, this can be accomplished by the boundary element method (BEM) using a suitable integral formulation. Most previous work uses the same integral formulation, corresponding to a double-layer potential. In this paper we present a conceptual framework based on a well-known theorem (Theorem 1) that characterizes harmonic functions defined on the complement of a bounded smooth surface. This theorem says that such harmonic functions are completely defined by their values and those of their normal derivatives on this surface. It allows us to cast the previous BEM approaches in a unified setting and to develop two new approaches corresponding to different ways of exploiting the same theorem. Specifically, we first present a dual approach which involves a single-layer potential. Then, we propose a symmetric formulation, which combines single- and double-layer potentials, and which is new to the field of EEG, although it has been applied to other problems in electromagnetism. The three methods have been evaluated numerically using a spherical geometry with known analytical solution, and the symmetric formulation achieves a significantly higher accuracy than the alternative methods. Additionally, we present results with realistically shaped meshes. Beside providing a better understanding of the foundations of BEM methods, our approach appears to lead also to more efficient algorithms.

We consider the problem of image segmentation using active contours through the minimization of an energy criterion involving both region and boundary functionals. These functionals are derived through a shape derivative approach instead of classical calculus of variation. The equations can be elegantly derived without converting the region integrals into boundary integrals. From the derivative, we deduce the evolution equation of an active contour that makes it evolve towards a minimum of the criterion. We focus more particularly on statistical features globally attached to the region and especially to the probability density functions of image features such as the color histogram of a region. A theoretical framework is set for the minimization of the distance between two histograms for matching or tracking purposes. An application of this framework to the segmentation of color histograms in video sequences is then proposed. We briefly describe our numerical scheme and show some experimental results.

In this paper, we overcome a major drawback of the level set framework: the lack of point correspondences. We maintain explicit backward correspondences from the evolving interface to the initial one by advecting the initial point coordinates with the same speed as the level set function. Our method leads to a system of coupled Eulerian partial differential equations. We show in a variety of numerical experiments that it can handle both normal and tangential velocities, large deformations, shocks, rarefactions and topological changes. Applications are many in computer vision and elsewhere since our method can upgrade virtually any level set evolution. We complement our work with the design of non zero tangential velocities that preserve the relative area of interface patches; this feature may be crucial in such applications as computational geometry, grid generation or unfolding of the organs' surfaces, e.g. brain, in medical imaging.

We present a common variational framework for dense depth recovery and dense three-dimensional motion field estimation from multiple video sequences, which is robust to camera spectral sensitivity differences and illumination changes. For this purpose, we first show that both problems reduce to a generic image matching problem after backprojecting the input images onto suitable surfaces. We then solve this matching problem in the case of statistical similarity criteria that can handle frequently occurring nonaffine image intensities dependencies. Our method leads to an efficient and elegant implementation based on fast recursive filters. We obtain good results on real images.

This article proposes a solution of the Lambertian shape from shading (SFS) problem in the case of a pinhole camera model (performing a perspective projection). Our approach is based upon the notion of viscosity solutions of Hamilton-Jacobi equations. This approach allows us to naturally deal with nonsmooth solutions and provides a mathematical framework for proving correctness of our algorithms. Our work extends previous work in the area in three aspects. First, it models the camera as a pinhole whereas most authors assume an orthographic projection, thereby extending the applicability of shape from shading methods to more realistic images. In particular it extends the work of E. Prados et al. (2002) and E. Rouy et al. (1992). Second, by adapting the brightness equation to the perspective problem, we obtain a new partial differential equation (PDE). Results about the existence and uniqueness of its solution are also obtained. Third, it allows us to come up with a new approximation scheme and a new algorithm for computing numerical approximations of the "continuous" solution as well as a proof of their convergence toward that solution.

Approximations of shape metrics, such as the Hausdorff distance, to define similarity measures between shapes are proposed. Our approximations being continuous and differentiable, they provide an obvious way to warp a shape onto another by solving a partial differential equation (PDE), in effect a curve flow, obtained from their first order variation. This first order variation defines a normal deformation field for a given curve. We use the normal deformation fields induced by several sample shape examples to define their mean, their covariance "operator", and the principal modes of variation. Our theory, which can be seen as a nonlinear generalization of the linear approaches proposed by several authors, is illustrated with numerous examples. Our approach being based upon the use of distance functions is characterized by the fact that it is intrinsic, i.e. independent of the shape parametrization.

We present two novel algorithms for multimodal, dense matching of two images using a variational approach. These algorithms complete and generalise our previous work by treating the case of semi-local energy functionals (G. Hermosillo et al., 2001). In brief, they are derived from the maximization of two statistical criteria (mutual information and correlation ratio) estimated from corresponding regions around each pixel (or voxel in the 3D case). As a second contribution, we present a result of existence and uniqueness of the solution of the abstract evolution problems associated to these algorithms, as well as those of the corresponding global algorithms. This is important since it shows the well-posedness of the problems to solve. We finish by showing some applications of our methods to one synthetic and four real examples.

A novel method of incorporating shape information into the image segmentation process is presented. We introduce a representation for deformable shapes and define a probability distribution over the variances of a set of training shapes. The segmentation process embeds an initial curve as the zero level set of a higher dimensional surface, and evolves the surface such that the zero level set converges on the boundary of the object to be segmented. At each step of the surface evolution, we estimate the maximum a posteriori (MAP) position and shape of the object in the image, based on the prior shape information and the image information. We then evolve the surface globally; towards the MAP estimate, and locally based on image gradients and curvature. Results are demonstrated on synthetic data and medical imagery in 2D min 3D.

Curve evolution schemes for segmentation, implemented with level set methods, have become an important approach in computer vision. Previous work has modeled evolving contours which are curves in 2D or surfaces in 3D. Our objective is to explore recent mathematical work enabling the evolution of manifolds of higher co-dimension. We consider 1D curves in 3D (codimension-two) for the application of automatically, segmenting blood vessels in volumetric magnetic resonance angiography (MRA) images. This paper describes the theoretical foundations of our system, CURVES, then provides segmentation results compared against segmentation obtained interactively by a neurosurgeon. Segmentation of bronchi in lung computed tomography (CT) scans are also presented. The new experiments, comparisons to manual segmentation, and sample comparison to the use of a codimension-one regularization force are the primary contributions of this report.

We introduce the concept of self-calibration of a 1D projective camera from point correspondences, and describe a method for uniquely determining the two internal parameters of a 1D camera, based on the trifocal tensor of three 1D images. The method requires the estimation of the trifocal tensor which can be achieved linearly with no approximation unlike the trifocal tensor of 2D images and solving for the roots of a cubic polynomial in one variable. Interestingly enough, we prove that a 2D camera undergoing planar motion reduces to a 1D camera. From this observation, we deduce a new method for self-calibrating a 2D camera using planar motions. Both the self-calibration method for a 1D camera and its applications for 2D camera calibration are demonstrated on real image sequences.

We propose a method to estimate the motion of a person filmed by two or more fixed cameras. The novelty of our technique is its ability to cope with fast movements, self-occlusions and noisy images. Our algorithms are based on the latest works on calibration and image segmentation developed in our lab. We compare the projections of a 3D model of a person on the images to the detected silhouettes of the person, and by creating forces that will move the 3D model towards the final estimation of the real pose. We developed a fast algorithm that computes the motion of the articulated 3D model. We show that our results are good, even if the cameras are not synchronized.

Studies the computation of projective invariants in pairs of images from uncalibrated cameras and presents a detailed study of the projective and permutation invariants for configurations of points and/or lines. Two basic computational approaches are given, one algebraic and one geometric. In each case, invariants are computed in projective space or directly from image measurements. Finally, we develop combinations of those projective invariants which are insensitive to permutations of the geometric primitives of each of the basic configurations.

This article deals with the problem of recovering the three trifocal tensors between three views from a set of point correspondences. We give a new way of deriving the trifocal tensor based on Grassmann-Cayley algebra that sheds some new light on its structure and leads to a complete characterization of its geometric and algebraic properties which is fairly institute, i.e. geometric. We give a set of algebraic constraints satisfied by the 27 coefficients of the trifocal tensor which allow to parameterize it minimally with 18 coefficients. We then describe a robust method for estimating the trifocal tensor from point and line correspondences that uses this minimal parameterization. Experimental results show that this method as superior to the linear methods which had been previously published.

We present a novel geometric approach for solving the stereo problem for an arbitrary number of images (= or >2). It is based upon the definition of a variational principle that must be satisfied by the surfaces of the objects in the scene and their images. The Euler-Lagrange equations that are deduced from the variational principle provide a set of partial differential equations (PDE's) that are used to deform an initial set of surfaces which then move toward the objects to be detected. The level set implementation of these PDE's potentially provides an efficient and robust way of achieving the surface evolution and to deal automatically with changes in the surface topology during the deformations, i.e., to deal with multiple objects. Results of an implementation of our theory also dealing with occlusion and visibility are presented on synthetic and real images.

The main problem for building a mosaic is the computation of the warping functions (homographies). In fact two cases are to be distinguished. The first is when the homography is mainly a translation (i.e. The rotation around the optical axis and the zooming factor are small). The second is the general case (when the rotation around the optical axis and zooming are arbitrary). Some efficient methods have been developed to solve the first case. But the second case is more difficult, in particular, when the rotation around the optical axis is very large (90 degrees or more). Often in this case human interaction is needed to provide a first approximation of the transformation that will bring one back to the first case. The authors present a method to solve this problem without human interaction for any rotation around the optical axis and fairly large zooming factors.

To make a Euclidean reconstruction of the world seen through a stereo rig, we can either use a calibration grid, and the results will rely on the precision Of the grid and the extracted points of interest, or use self-calibration. Past work on self-calibration is focussed on the use of only one camera, and gives sometimes very unstable results. In this paper, we use a stereo rig which is supposed to be weakly calibrated using a method such as the one described in Deriche et al. (1994). Then, by matching two sets of points of the same scene reconstructed from different points of view, we try to find both the homography that maps the projective reconstruction to the Euclidean space and the displacement from the first set of points to the second set of points. We present results of the Euclidean reconstruction of a whole object from uncalibrated cameras using the method proposed here.

REALISE was designed to extract from sequences of images, acquired with a moving camera, the information necessary for determining the 3D (CAD-like) structure of a real-life scene together with information about the radiometric signatures of surfaces bounding the extracted 3D objects (e.g. reflectance behaviour). The retrieved information is then integrated in a virtual reality (VR) software environment. The R&D work is been performed principally in the following areas of computer vision and computer graphics: structure from motion, recovery of geometries, recovery of photometric and texture information, highly realistic rendering on the basis of empirically-based reflectance models, and the design and development of improved rendering processes together with a new VR system. Beside this innovative R&D work another key aspect of REALISE is to have computer vision & computer graphics cooperate to produce realistic 3D data efficiently.

We address in this paper the problem of self-calibration and metric reconstruction (up to a scale factor) from one unknown motion of an uncalibrated stereo rig. The epipolar constraint is first formulated for two uncalibrated images. The problem then becomes one of estimating unknowns such that the discrepancy from the epipolar constraint, in terms of sum of squared distances between points and their corresponding epipolar lines, is minimized. Although the full self-calibration is theoretically possible, we assume in this paper that the coordinates of the principal point of each camera are known. Then, the initialization of the unknowns can be done based on our previous work on self-calibration of a single moving camera, which requires to solve a set of so-called Kruppa equations. Redundancy of the information contained in a sequence of stereo images makes this method more robust than using a sequence of monocular images. Real data has been used to test the proposed method, and the results obtained are quite good. We also show experimentally that it is very difficult to estimate precisely the coordinates of the principal points of cameras. A variation of as high as several dozen pixels in the principal point coordinates does not affect significantly the 3-D reconstruction.

We explore the geometric and algebraic relations that exist between correspondences of points and lines in an arbitrary number of images. We propose to use the formalism of the Grassmann-Cayley algebra as the simplest way to make both geometric and algebraic statements in a very synthetic and effective way (i.e. allowing actual computation if needed). We have a fairly complete picture of the situation in the case of points; there are only three types of algebraic relations which are satisfied by the coordinates of the images of a 3-D point: bilinear relations arising when we consider pairs of images among the N and which are the well-known epipolar constraints, trilinear relations arising when we consider triples of images among the N, and quadrilinear relations arising when we consider four-tuples of images among the N. In the case of lines, we show how the traditional perspective projection equation can be suitably generalized and that in the case of three images there exist two independent trilinear relations between the coordinates of the images of a 3-D line.>

Recently, different approaches for uncalibrated stereo have been suggested which permit projective reconstruction from multiple views. These use weak calibration which is represented by the epipolar geometry, and so no knowledge of the intrinsic or extrinsic camera parameters is required. We consider projective reconstructions from pairs of views, and compare a number of the available methods. Consequently we conclude which methods are most likely to be of use in applications that are dependent on 3D uncalibrated reconstructions.>

In the present paper we address the problem of computing structure and motion, given a set point correspondences in a monocular image sequence, considering small motions when the camera is not calibrated. We first set the equations defining the calibration, rigid motion and scene structure. We then review the motion equation, the structure from equation and the depth evolution equation, including the particular case of planar structures, considering a discrete displacement between two frames. A step further, we develop the first order expansion of these equations and analyse the observability of the related infinitesimal quantities. It is shown that we obtain a complete correspondence between these equations and the equation derived in the discrete case. However, in the case of infinitesimal displacements, the projection of the translation (focus of expansion or epipole) is clearly separated from the rotational component of the motion. This is an important advantage of the present approach. Using this last property, we propose a mechanism of image stabilization in which the rotational disparity is iteratively canceled. This allows a better estimation of the focus of expansion, and simplifies different aspects of the analysis of the equations: structure from motion equation, analysis of ambiguity, geometrical interpretation of the motion equation.>

In this paper, we begin to explore the evolution of curves of the projective plane according to a family of intrinsic equations generalizing a "projective heat equation". This is motivated by previous work for the Euclidean and the affine case, as well as by applications in the perception of two-dimensional shapes. We establish the projective arclength evolution and the projective curvature evolution. Among this family of equations, we point out the ones preserving an important property of the Euclidean and affine heat equations that was not preserved in the projective case: a curve with constant curvature should remain such a curve during its evolution.

We are considering the problem of recovering the three-dimensional geometry of a scene from binocular stereo disparity. Once a dense disparity map has been computed from a stereo pair of images, one often needs to calculate some local differential properties of the corresponding 3-D surface such as orientation or curvatures. The usual approach is to build a 3-D reconstruction of the surface(s) from which all shape properties will then be derived without ever going back to the original images. In this paper, we depart from this paradigm and propose to use the images directly to compute the shape properties. We thus propose a new method extending the classical correlation method to estimate accurately both the disparity and its derivatives directly from the image data. We then relate those derivatives to differential properties of the surface such as orientation and curvatures.>

We address the problem of the prediction of new views of a given scene from existing weakly or fully calibrated views called reference views. Our method does not make use of a three-dimensional model of the scene, but of the existing relations between the images. The new views are represented in the reference views by a viewpoint and a retinal plane, i.e. by four points which can be chosen interactively. From this representation and from the constraints between the images, we derive an algorithm to predict the new views. We discuss the advantages of this method compared to the commonly used scheme: 3D reconstruction-projection.

Studies experimentally the problem of computing the position of the epipoles in a pair of uncalibrated images. The approach, which is based on the definition of the epipolar transformation, exploits algebraic constraints obtained from point correspondences and provides a direct solution in which only the epipoles are involved. This is in opposition with the methods based on the computation of the fundamental matrix. In order to obtain a robust solution, three families of methods are successively considered: the first one uses statistics on closed-form solutions provided by the so-called Sturm method, the second one finds the intersection of plane cubics by deterministic procedures, and the third one is based on non-linear minimizations of a difference of cross-ratios. The authors discuss the shortcomings of each of these and show, using numerous experimental comparisons, that a drastic improvement can be obtained.

The problem of calibrating a camera is extremely important for practical applications. While classical work is based on the use of a calibration pattern whose 3D model is a priori known, self-calibration methods have also been investigated. These methods require only point matches obtained during unknown motions, without any a priori knowledge of the scenes. However, the method initially presented by Faugeras, Luong and Maybank (1992) was computationally expensive and sensitive to noise. In this paper, we propose an alternative method to compute at the same time camera calibration and motion, which is robust and efficient. This method allows also to take into account the important trinocular constraints. The practical applicability of our algorithm is illustrated with numerous real examples, which includes 3D reconstruction.

This paper intends to show that the second order spatio-temporal derivatives of de-forming image curves can be computed quite accurately from image sequences. These quantities, related to the second order optical flow parameters, are useful in the computation of the motion and the structure of a 3-D rigid curve from monocular image sequences. We show that they can be estimated directly from the points of the spatio-temporal surface generated by the image curve using polynomial approximation, and that the accuracy is at least comparable and often much better than that obtained using the other standard techniques. We consider particularly the special case of curvature because the estimation of that quantity has been studied before and show the results obtained using different methods. We then propose a "pseudo scale-space" method that should improve further the accuracy of the results.

Presents a stratification of geometric information available from stereovision in three levels: Euclidean, affine and projective, depending upon the kind of calibration that has been obtained for the stereo rig. The authors then focus on the last two levels: they show how affine calibration can be achieved from real images without the need of calibration patterns and how to use projective and affine information to determine, for example, whether an obstacle is coming too close to the stereo rig or the middle of a corridor or a road.

We address in this paper the problem of self-calibration and metric reconstruction (up to a scale) from one unknown motion of an uncalibrated stereo rig. The epipolar constraint is first formulated for two uncalibrated images. The problem then becomes one of estimating unknowns such that the discrepancy from the epipolar constraint, in terms of sum of squared distances between points and their corresponding epipolar lines, is minimized. Redundancy of the information contained in a sequence of stereo images makes this method more robust than using a sequence of monocular images. Real data have been used to test the proposed method, and the results obtained are quite good.

The fundamental matrix is a key concept when working with uncalibrated images and multiple viewpoints. It contains all the available geometric information and enables recovery of the epipolar geometry from uncalibrated perspective views. The problem of its determination from points which lie in several planes is discussed. In that case, there is an homography between coordinates of points in the two images. The use of different criteria to compute the homography is investigated. A very simple and important relation between the homography matrices obtained from the observation of planar surfaces and the fundamental matrix is then established. Using simulations and real images to validate this analysis, it is shown that as a first consequence of this relation, the general methods to compute the fundamental matrix are unstable when the points lie close to planes. New algorithms are proposed to exploit this situation through the use of the previous relation. Their performance is compared to the performance of the general algorithm using a large number of noisy synthetic data and real images.>

A subpart of the following problem is considered. It is assumed that a set of known three-dimensional lines with an unknown pose and orientation are observed with a camera. The problem is to recover the position and orientation of the camera from the observed image lines, assuming that a correspondence has been established between the 2-D and the 3-D lines. It is shown that there exist infinite sets of three-dimensional lines such that no matter how many lines are observed in these sets the solution to the orientation or pose determination problem is not unique. The maximum number of possible solutions is given. These results clearly define the domain of validity of algorithms which solve the orientation or pose determination problem.>

The authors consider the problem of recovering the relative displacements of a camera by using line matches in three views. In particular, they try to find whether there exist sets of 3-D lines such that irrespective of how many lines are observed there will always be several solutions to the relative displacement estimation problem. Recently, T. Buchanan (1992) provided a first analysis of the problem in which he gave a positive answer. Here, an attempt is made to build on his work and extend it in several directions. First, his purely projective analysis is cast in a more Euclidean framework better suited to applications. Second, his critical set is related to those of previously published algorithms. Third, the algebraic equations are introduced and an effective, i.e., computational, approach is provided for describing these critical sets in terms of simple geometric properties. This has allowed analysis of the structure of the critical sets.>

The authors show some very recent results using the weak-calibration idea. Assuming that only the epipolar geometry is known of a pair of stereo images, encoded in the so-called fundamental matrix, it is shown that some useful three-dimensional information such as relative positions of points and planes and 3-D convex hulls can be computed. The notion of visibility is introduced, which allows deriving those properties. Results of both synthetic and real data are shown.>

This paper describes the development and implementation of a reactive visual module utilized on an autonomous mobile robot to automatically correct in trajectory. The authors use a multisensorial mechanism based on inertial and visual cues. The authors report only on the implementation and the experimentation of this module, whereas the main theoretical aspects have been developed elsewhere.

Three-dimensional edge detection in voxel images is used to locate points corresponding to surfaces of 3-D structures, and the local geometry of these surfaces is characterized in order to extract points or lines which may be used by registration and tracking procedures. Typically, second-order differential characteristics of the surfaces must be calculated. To avoid the problem of establishing links between 3-D edge detection and local surface approximation it is proposed to compute the curvatures at locations designated as edge points, using the partial derivatives of the image directly. By assuming that the surface is defined locally by an iso-intensity-contour, it is possible to calculate directly the curvatures and characterize the local curvature extrema (ridge points) from the first, second, and third derivatives of the gray-level function. These partial derivatives can be computed using the operators of the edge detection. Experimental results obtained using real X-ray scanner data are presented.>

The problem of calibrating cameras is extremely important in computer vision. Existing work is based on the use of a calibration pattern whose 3D model is known a priori. The authors present a complete method for calibrating a camera, which requires only point matches from image sequences. The authors show, using experiments with noisy data, that it is possible to calibrate a camera just by pointing it at the environment, selecting points of interests, and tracking them in the image while moving the camera with an unknown motion. The camera calibration is computed in two steps. In the first step the epipolar transformation is found via the estimation of the fundamental matrix. The second step of the computation uses the so-called Kruppa equations, which link the epipolar transformation to the intrinsic parameters. These equations are integrated in an iterative filtering scheme.>

The authors present some of the work currently being conducted at CEA, CNRS, INRIA, ONERA, and CNES in the framework of the Autonomous Planetary Rover program (VAP). A system concept approach for the VAP application is first presented. Attention is then given to the VAP perception system: some results obtained with stereovision by a correlation algorithm on outdoor simulated Mars terrain scenes are shown.>

In this article, we describe some of the algorithms for depth and motion analysis which have been developed within ESPRIT project 940. Specifically we discuss edge detection, token tracking in sequences of images, and trinocular stereo. These processes have been implemented in hardware to form the core of the Depth and Motion Analysis (DMA) machine which has been developed to provide sophisticated real time vision capabilities for a large variety of robotics tasks.

The extremal boundaries, of 3-D curved objects are the images of special curves drawn on the object and are called rims. They are viewpoint dependent and characterized by the fact that the optical rays of their points are tangential to the surface of the object. The mathematics of the relationship between the extremal boundaries and the surface of the object is studied. This study makes it possible to design an algorithm for detecting those boundaries in the images that are likely to be extremal. Once this has been done, one can reconstruct the rims and compute the differential properties of the surface of the object along them up to the second order. If a qualitative description is sufficient, the sign of the Gaussian curvature of the surface along the rim can be computed in a much simpler way. Experimental results are presented on synthetic and real images. The work provides a better understanding of the relationship between the apparent and real shape of a 3-D object as well as algorithms for reconstructing the local shape of such an object along the rims.>

A method for estimating 3D displacements from two stereo frames is presented. It is based on the hypothesize-and-verify paradigm used to match 3D line segments between the two frames. In order to reduce the complexity of the method, an assumption is made that objects are rigid. The formulate a set of complete rigidity constraints for 3D line segments and integrate the uncertainty of measurements in this formation. The hypothesize-and-verify stages of the method use an extended Kalman filter to produce estimates of the displacements and of their uncertainty. The algorithm is shown to work on indoor and natural scenes. It is also shown to be easily extended to the case in which several mobile objects are present. The method is quite robust, fast, and has been thoroughly tested on hundreds of real stereo frames.>

An edge-based trinocular stereovision algorithm is presented. The primitives it works on are cubic B-spline approximations of the 2-D edges. This allows one to deal conveniently with curvature and to extend to some nonpolyhedral scenes to previous stereo algorithms. To build a matching primitive, the principle of the algorithm is, first, to find a triplet of corresponding points on three splines. This is provided by the bootstrapping part. Second, the algorithm propagates along the three supporting splines to find other matching points. This provides a set of ordered point triplets along these three splines, for which all the matching constraints are verified. This primitive constitutes a trinocular hypothesis. The set of all hypotheses is obtained by propagating from all the point triplets provided by the bootstrapping process. A criterion based on the size of the hypotheses is then used to choose among them a compatible set with respect to the uniqueness constraint. Results of several 3-D reconstructed scenes are shown.>

Abstract Motion estimation is a very important problem in dynamic scene analysis. Although it is easier to estimate motion parameters from 3D data than from 2D images, it is not trivial, since the 3D data we have are almost always corrupted by noise. A comparative study on motion estimation from 3D line segments is presented. Two representations of line segments and two representations of rotation are described. With different representations of line segments and rotation a number of methods for motion estimation are presented, including the extended Kalman filter a general minimization process and the singular value decomposition. These methods are compared using both synthetic and real data obtained by a trinocular stereo. It is observed that the extended Kalman filter with the rotation axis representation of rotation is preferable. Note that all methods discussed can be directly applied to 3D point data.

An investigation is conducted of the relationships that exist between the three-dimensional structure and kinematics, of a line moving rigidly in space and the two-dimensional structure and kinematics (optical flow) of its image in one or two cameras. The authors establish the fundamental equations that relate its three-dimensional motion to its observed image motion. They then assume that stereo matches have been established between image segments and show how the estimation of the optical flows in the two images can be used to compute part of the kinematic screw of the corresponding 3-D line. The equations are linear and provide a very simple way to estimate the full kinematic screw, if several lines of the same object are available. Experimental results using synthetic and real data are presented.>

A description is given of the development and implementation of a line segments based module of recovery of self-motion and 3-D structure. Given a monocular sequence of time-varying images and 2-D-lines matches in this sequence, the goal is to recover the camera motion and the 3-D-lines structure. A feedforward approach which combines prediction and correction is presented, and the equations are given and discussed in the case of small rigid motions. Algorithms, based on the minimization of the Mahalanobis distance between two estimates, are given and their implementations carefully discussed. The efficiency of the proposed approach is illustrated through experimental tests carried out considering noisy synthetic data and a real indoor scene.>

The authors address the motion tracking problem that arises in the context of a mobile vehicle navigating in an unknown environment where other mobile bodies such as human beings or robots may also be moving. A stereo rig mounted on the mobile vehicle provides a sequence of 3-D maps of the environment. The current stereo system is trinocular and the 3-D tokens used at the moment are line segments corresponding to significant intensity discontinuities in the images. Although the framework to solve the motion tracking problem developed in this work arises in this specific context, the authors believe it should be applicable in other contexts; in particular they could use other 3-D primitives, for example, points, combinations of points and lines, curves.>

The authors present an efficient approach for reliably matching a set of points extracted from the environment of a mobile robot by means of passive stereo vision using two or three cameras. First, feature points corresponding to points with high curvature are extracted from each image using an efficient approach. The epipolar geometry and some powerful configuration constraints are then combined to match these points. A correspondence between curves is then established using the figural continuity. Results obtained on real images are given.>

A system whereby a mobile robot in an unknown environment can incrementally build a world model is described. The model discussed is segment-based. A trinocular system is used to build a local map of the environment. A global map is obtained by integrating a sequence of stereo frames taken while the robot navigates in the environment. Emphasis is on the representation of the uncertainty of 3D segments from stereo and on the integration of segments from multiple views. The representation is simple and very convenient for characterizing the uncertainty of segments. A Kalman filter is used to merge matched line segments. An important characteristic of the integration strategy is that a segment observed by the stereo system corresponds only to one part of the segment in space, so that the union of different observations gives a better estimate on the segment in space. The integration of 35 stereo frames taken in a robot room is described.>

A method for the determination of camera location from two-dimensional (2-D) to three-dimensional (3-D) straight line or point correspondences is presented. With this method, the computations of the rotation matrix and the translation vector of the camera are separable. First, the rotation matrix is found by a linear algorithm using eight or more line correspondences, or by a nonlinear algorithm using three or more line correspondences, where the line correspondences are either given or derived from point correspondences. Then, the translation vector is obtained by solving a set of linear equations based on three or more line correspondences, or two or more point correspondences. Eight 2-D to 3-D line correspondences or six 2-D to 3-D point correspondences are needed for the linear approach; three 2-D to 3-D line or point correspondences for the nonlinear approach. Good results can be obtained in the presence of noise if more than the minimum required number of correspondences are used.>

In the eight-point linear algorithm for determining 3D motion/structure from two perspective views using point correspondences, the E matrix plays a central role. The E matrix is defined as a skew-symmetrical matrix (containing the translation components) postmultiplied by a rotation matrix. The authors show that a necessary and sufficient condition for a 3*3 matrix to be so decomposable is that one of its singular values is zero and the other two are equal. Several other forms of this property are presented. Some applications are briefly described.>

A novel method for the determination of camera location from 2-D to 3-D line or point correspondences is presented. Using this method, the computation of the rotation matrix and the translation vector of the camera are separable. First, the rotation matrix is found by a linear algorithm using eight or more line correspondences, or by a nonlinear algorithm using three of more line correspondences, where the line correspondences are either given or derived from point correspondences. Then, the translation vector can be obtained by solving a set of linear equations based on three or more line correspondences, or two or more point correspondences. Eight 2-D-to-3-D line or point correspondences or six 2-D-to-3-D point correspondences are needed for the linear approach; three 2-D-to-3-D line or point correspondences for the nonlinear approach. Good results can be obtained in the presence of noise if more than the minimum required number of correspondences are used.>

This article proposes a coherent method of interpolating 3D data obtained for example by stereo, with a polyhedral surface by means of the Delaunay Triangulation. We first give some theoretical properties concerning the approximations of sampled objects we obtain when the sampling rate increases, based on the study of their skeleton using some tools of Mathematical Morphology. Then, we present the algorithms and their complexity analysis which yield both a surface representation of objects and a volume representation of free space which may be useful in Robotics. This goal is achieved by means of a simple visibility criterion. The method is intrinsically discontinuity preserving and can be used for the integration of multiple viewpoints.

Iri this paper, we describe a method for comput.ing the rriovc~rrient. of objects as well as that of a mobile robot from ii scqiicrice of stereo frames. Stereo frames are obtained at ~iifl’(~reiit, instants by a stereo rig, when the mobile robot rIilvigat(>s in an unknown environment possibly containing ~)iiit: rrioving rigid objects. An approach based on rigidity ( oiihlraiiit,s is presented for registering two stereo frames. Wcs dernoristrate how the uncertainty of measurements can IN^ integrated with the formalism of the rigidity constraints. A iiew technique is described to match very noisy segments. ‘1‘11~ iiifluence of egomotion on observed movement:; of ob,j(~ 1,s is discussed in detail. Egomotion is fir:jt determined itiid then eliminated before determination of the motion of o1)jt:cl.s. The proposed algorithm is completely automatic. I~:xperirnerital results are provided. Some remarks conclude ths paper.

A brief review is given of the current formulations of the problem of recovering 3D structure and motion from image line correspondences, and their minimum requirement is formally established in terms of the number of views and lines. Only general rigid motion is considered. Computation of the rotational component and translation component of general motion can be separated. When the rotational component is determined, computation of the translation component is straightforward.>

A coherent way of interpolating 3-D data obtained by stereo, for example, with a simplicial polyhedral surface is discussed. The method is based on constrained Delaunay triangulation; the polyhedral surface is obtained by using a simple visibility property to mark tetrahedra likely to be empty. The method is intrinsically discontinuity-preserving and yields both a surface representation of objects and a volume representation of free space which may be useful in robotics. Algorithms to implement the method are described and their complexity analyzed in the worst case and average case situations where tools of probabilistic geometry are used.>

We show in this article that when the environment is piecewise linear, it provides a powerful constraint on the kind of matches that exist between two images of the scene when the camera motion is unknown. For points and lines located in the same plane, the correspondence between the two cameras is a collineation. We show that the unknowns (the camera motion and the plane equation) can be recovered, in general, from an estimate of the matrix of this collineation. The two-fold ambiguity that remains can be removed by looking at a second plane, by taking a third view of the same plane, or by using a priori knowledge about the geometry of the plane being looked at. We then show how to combine the estimation of the matrix of collineation and the obtaining of point and line matches between the two images, by a strategy of Hypothesis Prediction and Testing guided by a Kalman filter. We finally show how our approach can be used to calibrate a system of cameras.

An acute problem of determining the motion from two perspective views has to be solved in order to make mobile robot navigation work. Structure from motion is needed in many applications including monitoring dynamic industrial processes and image processing. It is known [14,15] that existing techniques for motion estimation perform poorly on real images, when the image-point feature are noisy. This paper describes new, robust techniques to recover structure and movement from noisy images. Closed-form solutions are derived for the case of general three-dimensional motion. These solutions are used as initial estimate for another technique, called reconstruction and reprojection. We also present a solution for the case of planar motion, which is the case of a mobile robot moving over a flat surface. These techniques have been tested on synthetic as well as real images and the test results are described and compared with an improved version of LONGUET-HIGGINS [18] technique.

This paper deals with the problem of coping with noise disturbing data in Stereo, 3-D modelling and navigation. We introduce the idea of a Realistic Uncertain Description of the Environment (RUDE) which is local, i.e attached to a specific reference frame, and incorporates both, information about the geometry and about the parameters measuring this geometry. We also relate this uncertainty to the pixel uncertainty and show how the RUDE corresponding to different frames can be used to relate these frames by a rigid displacement which we describe both by a rotation and translation and a measure of their uncertainty. Finally, we use the relations between frames to update the associated RUDE and decrease their uncertainty.

A new method has been designed to identify and locate objects lying on a flat surface. The merit of the approach is to provide strong robustness to partial occlusions (due for instance to uneven lighting conditions, shadows, highlights, touching and overlapping objects) thanks to a local and compact description of the objects boundaries and to a new fast recognition method involving generation and recursive evaluation of hypotheses named HYPER (HY potheses Predicted and Evaluated Recursively). The method has been integrated within a vision system coupled to an indutrial robot arm, to provide automatic picking and repositioning of partially overlapping industrial parts.

In this paper we present results in the areas of shape matching of nonoccluded and occluded two-dimensional objects. Shape matching is viewed as a ``segment matching'' problem. Unlike the previous work, the technique is based on a stochastic labeling procedure which explicitly maximizes a criterion function based on the ambiguity and inconsistency of classification. To reduce the computation time, the technique is hierarchical and uses results obtained at low levels to speed up and improve the accuracy of results at higher levels. This basic technique has been extended to the situation where various objects partially occlude each other to form an apparent object and our interest is to find all the objects participating in the occlusion. In such a case several hierarchical processes are executed in parallel for every object participating in the occlusion and are coordinated in such a way that the same segment of the apparent object is not matched to the segments of different actual objects. These techniques have been applied to two-dimensional simple closed curves represented by polygons and the power of the techniques is demonstrated by the examples taken from synthetic, aerial, industrial and biological images where the matching is done after using the actual segmentation methods.

We show that one of the key problems in Image Understanding is the matching of two symbolic structures, a model and the result of a segmentation. These symbolic structures are conveniently represented as labeled graphs and we present on two examples a formalism which can deal with the inexact or fuzzy matching of such structures in a highly parallel fashion.

We show how the techniques of Digital Image Analysis can be efficiently used to help in the interpretation of seismic cross-sections. The problem of automatically finding homogeneous facies is in fact directly tied to Image Processing problems such as edge detection, texture analysis, segmentation and classification. We briefly overview some existing tools, outline some new techniques which had to be invented to cope with the characteristics of seismic signals and demonstrate on many examples the power of our approach.

A gradient relaxation method based on maximizing a criterion function is studied and compared to the nonlinear probabilistic relaxation method for the purpose of segmentation of images having unimodal distributions. Although both methods provide comparable segmentation results, the gradient method has the additional advantage of providing control over the relaxation process by choosing three parameters which can be tuned to obtain the desired segmentation results at a faster rate. Examples are given on two different types of scenes.

We approach the problem of labeling a set of objects from a quantitative standpoint. We define a world model in terms of transition probabilities and propose a definition of a class of global criteria that combine both ambiguity and consistency. A projected gradient algorithm is developed to minimize the criterion. We show that the minimization procedure can be implemented in a highly parallel manner. Results are shown on several examples and comparisons are made with relaxation labeling techniques.

This paper discusses the application of stochastic labeling to a general symbolic image description problem. A method used to compute initial likelihoods and compatibilities is described. It was derived from an earlier symbolic matching procedure, but was modified to provide the data needed for application of the labeling method. This labeling procedure differs from simpler ones, in that it minimizes a global criterion at each iteration. This technique is compared to other matching methods, and results on two scenes are presented.

This paper presents the development and evaluation of a visual texture feature extraction method based on a stochastic field model of texture. Results of recent visual texture discrimination experiments are reviewed in order to establish necessary and sufficient conditions for texture features that are in agreement with human discrimination. A texture feature extraction technique involving autocorrelation function measurement of a texture field, combined with histogram representation of a statistically decorrelated version of the texture field, is introduced. The texture feature extraction method is evaluated in terms of a Bhattacharyya distance measure.

We present and compare two design techniques for a large class of 2-D FIR filters. They can be implemented by means of sequential convolutions with small size kernels. Design methods are based upon the minimization of either the mean square or the maximum error between the synthesized filter and a design prototype in the Fourier domain.

Earlier experiments by Julesz et al. on visual discrimination are reviewed and extended in the context of texture analysis of natural images. Stochastic methods are developed for the generation of pairs of synthetic texture fields possessing multiple gray levels, significant spatial correlation, and joint moments or probability densities of controllable form. Results of several visual discrimination experiments with these computer generated texture fields are then presented. It is demonstrated, for the stochastic models investigated, that humans cannot effortlessly discriminate between pairs of spatially correlated texture fields with differing third-order probability densities when their lower order densities are pairwise equal. This is a further verification of Julesz's conjecture. Also, it is shown that human observers are sensitive to relatively small changes in the spatial autocorrelation function. Examples are presented of discriminable texture fields with identical means, variances, autocorrelation functions, and third-order nearest neighbor moments.