If one direction of (three-dimensional) space is singled out, it makes sense to formulate the description of embedded curves and surfaces in a frame that is adapted both to the embedded manifold and to the special direction, rather than a frame based upon the curvature landscape. Such a case occurs often in computer vision, where the image plane plays a role that differs essentially from the direction of view. The classical case is that of geomorphology, where the vertical is the singled out dimension. In computer vision the `ridges' and `(water-)courses' are recognized as important entities and attempts have been made to make the intuitive notions precise. These attempts repeat the unfortunate misunderstandings that marked the course of the late 19th century struggle to define the `Talweg' (equals `valley path' or `(water-)course'). We elucidate the problems and their solution via novel examples.

We develop a multi-pole type method to form fast approximations of thin-plate spline fitting problems. Thin-plate splines, and generalizations of them, arise in the context of computer vision through a regularization or interpolation/approximation process.

Surface reconstruction from range data acquired using a variety of sources has been a very active area of research in computational vision over the past decade. Generalized splines have emerged as the single most popular approximation tool to this end. In this paper we present a new and fast algorithm for solving the surface reconstruction problem using the membrane spline which yields a C⁰ surface. Our algorithm for dense data constraints takes O(N) computational time, where N is the number of nodes in the discretization. For sparse data constraints, the algorithm requires O(log N/(pi) ²) iterations with each iteration taking O(N) time. The number of iterations in this case depends on a prespecified error tolerance. We demonstrate the algorithm performance on synthesized sparse range data.

Variational methods have been frequently used for surface reconstruction and contour extraction (snakes). We present a surface reconstruction method where we assume the surface composed of two regions of different types of smoothness. One region of the surface models a `lake' (constant height region with uphill borders). It is surrounded by the other background region which is reconstructed using classic surface regularization. The boundary between the two regions, represented by a closed curve, is determined with the help of an active contour model. Then the surface is reconstructed by minimizing the energy terms in each region. Minimizing a global energy defined on the couple of unknowns -- boundary curve and surface -- permits us to introduce other forces on the curve. The surface reconstruction and contour extraction tasks are then made together. We have applied this model for segmenting a synthetic digital terrain model (DTM) image which represents a noisy mountain and lake.

A particularly common step in visual reconstruction is to approximate the solution using a finite element discretization. A variation on the finite element scheme is the use of mixed finite elements, particularly for the systematic approximation of more than one quantity, and the incorporation of constraints into the problem formulation. Mixed finite elements can lead to increased accuracy. Standard finite elements (including the mixed elements) are usually derived by considering each quantity as a single scalar function and designates nodal lattices for each scalar function. Such an approach ignores the richer geometric structure and relationships between various quantities. Whitney Forms provide a systematic means of bringing to bear the machinery of differential geometry into the design of mixed finite element schemes.

A space curve, e.g., a parabolic line on a 2-dimensional surface in 3-dimensional Euclidean space, induces a plane curve under projective mapping. But 2-dimensional scalar input images of such an object are, normally, spatio-temporal slices through a luminance field caused by the interaction of an external field and that object. Consequently, the question arises how to obtain from those input images a consistent description of the space curve under projective transformations. By means of classical scale space theory, algebraic invariance theory, and classical differential geometry a new method of shape description for space curves from one or multiple views is proposed in terms of complete and irreducible sets of affine and projective differential geometric invariants. The method is based on defining implicitly connections for the observed curves that are highly correlated to the projected space curves. These projected curves are assumed to reveal themselves as coherent structures in the scale space representation of the differential structure of the input images. Several applications to stereo, optic flow, texture analysis, and image matching are briefly indicated.

We are interested in the applications of invariant theory to computer vision problems. A survey and clarification of the different invariant calculation methods are detailed in our extended technical report. In this paper, we concentrate on 3-D invariants from pairs of images instead of invariants related to the planar projective transformations from monocular image that have been already largely studied by many people. Especially invariants of different configurations coming from different combinations of 3-D points, 3-D lines and conics are under consideration, and the stabilities of the invariants computed differently are compared. We conclude by showing to what extent these invariant measures can be used for recognition and indexing.

Basic properties of 2-D-nonlinear scale-space representations of images are considered. First, local-energy filters are used to estimate the Hausdorff dimension, D_H, of images. A new fractal dimension, D_N, defined as a property of 2-D-curvature representations on multiple scales, is introduced as a natural extension of traditional fractal dimensions, and it is shown that the two types of fractal dimensions can give a less ambiguous description of fractal image structure. Since fractal analysis is just one (limited) aspect of scale-space analysis, some more general properties of curvature representations on multiple scales are considered. Simulations are used to analyze the stability of curvature maxima across scale and to illustrate that spurious resolution can be avoided by extracting 2-D-curvature features.

A notion of spherical image is described that serves as a basis for defining the various geometric edges in a uniform way, for distinguishing between different views of an object, and for recovering range. The notion proposed here augments the point set image with a tangent vector frame field which arises naturally from the gradient of range and the perspective projection process.

Our goal is to reconstruct both the shape and reflectance properties of surfaces from multiple images. We argue that an object-centered representation is most appropriate for this purpose because it naturally accommodates multiple sources of data, multiple images (including motion sequences of a rigid object), self-occlusions, and geometric constraints. We then present a specific object-centered reconstruction method. It begins with an initial estimate of surface shape that is iteratively adjusted to minimize an objective function that combines information from multiple input images. The objective function is a weighted sum of `stereo,' shading, and smoothness components, where the weight varies over the surface. For example, the stereo component is weighted more strongly where the surface projects onto highly textured areas in the images, and less strongly otherwise. Thus, each component has its greatest influence where its accuracy is likely to be greatest. Experimental results on both synthetic and real images are presented.

It is shown, through elementary differential geometry, how the shape of the isophotes on a smooth surface is related to the underlying object and the location of the light source. Taking advantage of the principal directions, several characteristics of the isophotes are expressed, among which the geodesic curvature is emphasized. From these results, a variational method is discussed to estimate the surface shape from the image irradiance, subject to a geodesicity constraint on the isophotes. Finally, a local solid shape characteristic based on the principal curvatures ratio is offered.

This paper considers the problem of 3-D surface reconstruction from the observation of the occluding contours where the view lines graze the surface. It has been shown that reconstruction of such a 3-D surface is possible when the camera motion is known, except for the fully concave parts where no view line can be tangent to the surface. We propose a direct method of global surface reconstruction which is based on the regularized uniform bicubic B- spline patches. The experimental results are presented on synthetic and real data.

In this research, we propose a new shape from texture (SFT) algorithm. Unlike most existing SFT algorithms, it takes all possible texture distortion effects and recovers the surface heights of curved objects directly. The basic idea of our approach is to use the semi-perspective projection model based on the solid angle concept and approximation of a curved surface with a triangular element surface model. With these models, we relate the densities of textural primitives in triangular domains to nodal height variables of the curved surface directly. This procedure leads to a nonlinear system of equations which are then solved via a global energy minimization scheme and a successive linearization scheme. Estimation of the local textural density using dots and line segment edges of texels is also discussed.

This paper presents a physics-based algorithm to efficiently represent shape using deformable models with locally adaptive finite elements. We implement our technique using our previously developed dynamic deformable models which support local and global deformations. We express global deformations with a few parameters which represent the gross shape of an object, while local deformations capture shape details of objects through their many local parameters. Using triangular finite elements to represent local deformations our algorithm ensures that during subdivision the desirable finite element mesh properties of conformity, non-degeneracy, and smoothness are maintained. Through our algorithm, we locally subdivide the triangles used for the local deformations based on the distance between the given datapoints and the model. Furthermore, to improve our results we use a new algorithm to calculate the forces that datapoints exert on the model which is based on the minimal distance to a finite element instead of to a model node. In this way not only can we represent more accurately an object surface, but also more efficiently because new model nodes are added only when necessary in a local fashion. We present model fitting experiments to 3-D range data.

This paper develops techniques to locally control curvature and continuity in particle-based surface models. Such models are a generalization of traditional spline surfaces built out of triangular patches. Traditional splines require the topology of the triangular mesh to be specified ahead of time. In contrast, particle-based surface models compute the topology dynamically as a function of the relative node positions, and can add or delete nodes as required. Such models are particularly important in computer vision and other inverse problems, where the topology of the surface being reconstructed is usually not known a priori. We develop techniques for both locally controlling the curvature of the surface (through additional state at each node), and for adapting the triangulation to surface curvature (by concentrating more particles in areas of high curvature). We show how the same ideas can also be applied to 3-D curves, which results in a flexible version of traditional dynamic contours (snakes).

We present a physically based deformable model which can be used to track and to analyze the non-rigid motion of dynamic structures in time sequences of 2-D or 3-D medical images. The model considers an object undergoing an elastic deformation as a set of masses linked by springs, where the natural lengths of the springs is set equal to zero, and is replaced by a set of constant equilibrium forces, which characterize the shape of the elastic structure in the absence of external forces. This model has the extremely nice property of yielding dynamic equations which are linear and decoupled for each coordinate, whatever the amplitude of the deformation. It provides a reduced algorithmic complexity, and a sound framework for modal analysis, which allows a compact representation of a general deformation by a reduced number of parameters. The power of the approach to segment, track, and analyze 2-D and 3-D images is demonstrated by a set of experimental results on various complex medical images.

In this paper we provide a very simple, yet efficient, scheme for modeling volume boundaries using patches which are B-spline surfaces. Given a noisy three dimensional cloud of points, we use constrained minimization using B-splines as basis functions to smooth the data and create a three dimensional model of the surface of the object. Such a method is useful for representing complete free-form surface models of objects. Instead of fitting one B-spline surface to the complete data set, the data is segmented into smaller sub-clouds that are single valued in a local frame of reference. This work builds upon our earlier work on surface fitting in a rectangular domain, and extends it to arbitrary domains. We divide the problem into three stages: (1) segmentation of the sensor data from 3-D world coordinates into data patches, (2) approximation of the data in this space to create B-spline surface patches, and (3) reconversion into the world coordinate system. We also describe a complete system, Surfacer, built around these ideas which includes a comprehensive set of tools to manipulate point sets and surfaces in a CAD framework.

A method is presented for building model data for CAD and manufacturing purposes from existing parts using range data. These techniques can be used as a design aid, especially for designing complicated free-form surfaces. Furthermore, they can be used for reverse engineering if there exists no design data for a needed part, e.g., old machine part. The goal is to construct procedural CAD models, i.e., the set of commands that generate the part geometry, to be able to convey global shape properties in addition to low level geometric data. Sensor noise is attenuated using non-liner filters based on robust estimation theory. The data interpretation is obtained by fitting models. The CAD model building strategy and modeling primitives are selected based on the obtained volumetric and surface data descriptions and their quality. A superellipsoid model is recovered for each data set. Sculptured surfaces are approximated by recovering a NURBS control point mesh for the surface. An approach is proposed for estimating the size of the control point mesh automatically from sensor data. Parameterization issues and methods to recover B-spline surfaces of arbitrary topology are also studied. The obtained surface is refined to meet a user defined tolerance value. The model data is represented both in a procedural modeling language and IGES product data exchange format. Experimental results for standard geometric shapes and for sculptured free-form surfaces are presented using both real and synthetic range data.

There are two classical approaches to approximating the shape of objects. We are developing a general theory of shape which unifies these two different approaches in the entropy scale space. The theory is organized around two basic intuitions: first, if a boundary were changed only slightly, then, in general, its shape would change only slightly. This leads us to propose an operational theory of shape based on incremental contour deformations. The second intuition is that not all contours are shapes, but rather only those that can enclose `physical' material. A novel theory of contour deformation is derived from these intuitions, based on abstract conservation principles and the Hamilton-Jacobi theory. The result is a characterization of the computational elements of shape: protrusions, parts, bends, and seeds (which show where to place the components of a shape); and leads to a space of shapes (the reaction-diffusion space) which places shapes within a neighborhood of `similar' ones. Previously, these elements of shape have been used for description. We now show how they can be used to generate another space for shapes, the entropy scale space, which is obtained from the reaction-diffusion space by running the `reaction' portion of the equations `backwards' in time. As a result distinct components of a shape can be removed by introducing a minimal disturbance to the remainder of the shape. Our technique is numerically stable, and several examples are shown.

We describe a geometric method for formulating planar curve evolution equations which are invariant under a certain transformation group. The approach is based on concepts from the classical theory of differential invariants. The flows we obtain are geometric analogues of the classical heat equation, and can be used to define invariant scale-spaces. We give a `high- level' general procedure for the construction of these flows. Examples are presented for viewing transformations.

Developing shape models is an important aspect of computer vision research. Geometric and differential properties of the surface can be computed from shape models. They also aid the tasks of object representation and recognition. In this paper we present an innovative new approach for shape modeling which, while retaining important features of the existing methods, overcomes most of their limitations. Our technique can be applied to model arbitrarily complex shapes, shapes with protrusions, and to situations where no a priori assumption about the object's topology can be made. A single instance of our model, when presented with an image having more than one object of interest, has the ability to split freely to represent each object. Our method is based on the level set ideas developed by Osher & Sethian to follow propagating solid/liquid interfaces with curvature-dependent speeds. The interface is a closed, nonintersecting, hypersurface flowing along its gradient field with constant speed or a speed that depends on the curvature. We move the interface by solving a `Hamilton-Jacobi' type equation written for a function in which the interface is a particular level set. A speed function synthesized from the image is used to stop the interface in the vicinity of the object boundaries. The resulting equations of motion are solved by numerical techniques borrowed from the technology of hyperbolic conservation laws. An added advantage of this scheme is that it can easily be extended to any number of space dimensions. The efficacy of the scheme is demonstrated with numerical experiments on synthesized images and noisy medical images.

An algorithm for computing the Euclidean distance from the boundary of a given digitized shape is presented. The distance is calculated with sub-pixel accuracy. The algorithm is based on an equal distance contour evolution process. The moving contour is embedded as a level set in a time varying function of higher dimension. This representation of the evolving contour makes possible the use of an accurate and stable numerical scheme, due to Osher and Sethian.

The idea presented here is to use the features of the Forstner interest operator to address problem areas. The Forstner interest operator can localize point type features (corners and intersections) as well as edge type features. A common frame is at hand that is based on the estimate of the position accuracy and the significance of a point or an edge element (edgel). The derived energy values based on these measures can be geometrically interpreted. Breakpoints (corners) are introduced via image energies. A theoretically well understood method is at hand that combines point and edge energies. In order to increase the area of attraction in one level of a resolution hierarchy an energy pit around each point/edgel is created, based on the interest measures. By placing the center of the area of attraction at the sub-pixel position it is to a certain extent possible to spatially refine the energy map. To avoid the setting of a single specific window size for the interest operator a sequence of windows is applied to the image. Image energies are derived that are summed up, weighted by the window size. This final energy map is used as an input for the active contour models. This report gives the necessary framework and describes the principle ideas. Some alternatives for the design of the energy map and ranges for the few parameters required are discussed. Examples on some real images show the potential of this approach which is going to be used for the application of snakes for automatic and semi-automatic cartographic feature extraction in aerial images.

Deformable contours, based on energy minimization, have been widely used for tracking purposes. This paper proposes a novel type of constraint for the energy minimization problem: the use of motion models. Such an approach greatly reduces the sliding effects occurring during tracking: thus tracking provides point-to-point correspondence between the tracked B- spline based curves and reliably estimates their apparent motion. For a calibrated camera system, the stereo correspondences provided by this matching method can be used to reconstruct a 3-D curve point by point. This set of 3-D points is then approximated and refined by a 3-D deformable curve, in order to improve consistency with image observations. Furthermore, the bases of this tracking approach, i.e., B-splines and the estimation of 2-D motion models, provide an efficient way of estimating time-to-collision, and recovering the spatio-temporal surface of a moving contour, which has been proven to supply valuable information about its 3-D structure and motion. A large set of experimental results illustrates the different parts of this work.

A new model of an adaptive adjacency graph (AAG) for representing a 2-D image or a 2-D view of a 3-D scene is introduced. The model makes use of image representation similar in form to a region adjacency graph. Adaptive adjacency graph, as opposed to region adjacency graph, is an active representation of the image. The AAG can adapt to the image or track features and maintain the topology of the graph. Adaptability of the AAG is achieved by incorporating active contours (`snakes') in the graph. Various methods for creating the AAGs are discussed. Results obtained for dynamic tracking of features in sequence of images and for registration of retinal images are presented.

This paper presents a new method for determining the minimal non-rigid deformation between two 3-D surfaces, such as those which describe anatomical structures in 3-D medical images. Although we match surfaces, we represent the deformation as a volumetric transformation. Our method performs a least squares minimization of the distance between the two surfaces of interest. To quickly and accurately compute distances between points on the two surfaces, we use a precomputed distance map represented using an octree spline whose resolution increases near the surface. To quickly and robustly compute the deformation, we use a second octree spline to model the deformation function. The coarsest level of the deformation encodes the global (e.g., affine) transformation between the two surfaces, while finer levels encode smooth local displacements which bring the two surfaces into closer registration. We present experimental results on both synthetic and real 3-D surfaces.

We present new deformable spline surfaces for segmentation of 3-D medical images. We explore parametric surfaces of the form x(u, v) with two different topologies, planar and cylindrical, that permit us to segment fine anatomical structures. With respect to earlier approaches that minimize the `energy' of a deformable surface in a potential field, we perform this optimization with successive approximations of dense data, and propose the following key improvements. First, we show that the Euler equation has a closed form solution in a quadratic potential field. Each approximation requires only one iteration. Second, we use tensor products of splines to solve independently the system along parameters u and v. This enables us to work with large meshes of control vertices, e.g., 10,000 vertices and more. Third, with a regularly sampled potential field, each point in the same image voxel is processed in the same way. We use a continuous potential field defined with 3-D volumetric splines to avoid this problem. When the deformation process stops, we end up with a smooth differentiable surface where we measure principle curvatures and directions. We describe next an original algorithm that extracts lines of extremal curvature on the surface. These lines can be matched from different views with an algorithm such as in.^GA92. We present experimental evidence with real medical images that illustrate all the previous points. Finally, we outline the spherical topology for spline surfaces. We use Ostrogradsky's formula to compute the exact volume bounded by such a surface.

In the past, recognition systems have relied solely on geometric properties of objects. This paper discusses the simultaneous use of geometric as well as reflectance properties for object recognition. Neighboring points on a smoothly curved surface have similar surface orientations and illumination conditions. Hence, their brightness values can be used to compute the ratio of their reflectance coefficients. Based on this observation, we develop an algorithm that estimates a reflectance ratio for each region in an image with respect to its background. The algorithm is computationally efficient as it computes ratios for all image regions in just two raster scans. The region reflectance ratio represents a physical property of a region that is invariant to the illumination conditions. The reflectance ratio invariant is used to recognize three-dimensional objects from a single brightness image. Object models are automatically acquired and represented using a hash table. Recognition and pose estimation algorithms are presented that use the reflectance ratios of scene regions as well as their geometric properties to index the hash table. The result is a hypothesis for the existence of an object in the image. This hypothesis is verified using the ratios and locations of other regions in the scene. The proposed approach to recognition is very effective for objects with printed characters and pictures. We conclude with experimental results on the invariance of reflectance ratios and their application to object recognition.

A recursive algorithm for building an orthogonal basis for n-degree spline space is developed. The basis functions, dubbed `O-splines,' can be computed symbolically for an arbitrary number of knots, preserving infinite precision in their rational coefficients. Using the O-spline basis, fitting can be accomplished via a single inner product for each O-spline. Furthermore, the fitting procedure is better conditioned when compared to conventional methods. Shape description of real images is shown as an application of this new technique.

Salient surface features play a central role in tasks related to 3-D object recognition and matching. There is a large body of psychophysical evidence demonstrating the perceptual significance of surface features such as local minima of principal curvatures in the decomposition of objects into a hierarchy of parts. Many recognition strategies employed in machine vision also directly use features derived from surface properties for matching. Hence, it is important to develop techniques that detect surface features reliably. Our proposed scheme consists of (1) a preprocessing stage, (2) a feature detection stage, and (3) a feature integration stage. The preprocessing step selectively smoothes out noise in the depth data without degrading salient surface details and permits reliable local estimation of the surface features. The feature detection stage detects both edge-based and region-based features, of which many are derived from curvature estimates. The third stage is responsible for integrating the information provided by the individual feature detectors. This stage also completes the partial boundaries provided by the individual feature detectors, using proximity and continuity principles of Gestalt. All our algorithms use local support and, therefore, are inherently parallelizable. We demonstrate the efficacy and robustness of our approach by applying it to two diverse domains of applications: (1) segmentation of objects into volumetric primitives and (2) detection of salient contours on free-form surfaces. We have tested our algorithms on a number of real range images with varying degrees of noise and missing data due to self-occlusion. The preliminary results are very encouraging.

We address the problem of automatically learning object models for recognition and pose estimation. In contrast to the traditional approach, we formulate the recognition problem as one of matching visual appearance rather than shape. The appearance of an object in a two- dimensional image depends on its shape, reflectance properties, pose in the scene, and the illumination conditions. While shape and reflectance are intrinsic properties of an object and are constant, pose and illumination vary from scene to scene. We present a new compact representation of object appearance that is parametrized by pose and illumination. For each object of interest, a large set of images is obtained by automatically varying pose and illumination. This large image set is compressed to obtain a low-dimensional subspace, called the eigenspace, in which the object is represented as a hypersurface. Given an unknown input image, the recognition system projects the image onto the eigenspace. The object is recognized based on the hypersurface it lies on. The exact position of the projection on the hypersurface determines the object's pose in the image. We have conducted experiments using several objects with complex appearance characteristics. We conclude with a discussion on various issues related to the learning and recognition techniques proposed in the paper.

In this paper, we propose a multi-scale approach to 3-D scene modeling and processing. The basic idea of the proposed technique is to acquire a minimum amount of 3-D information using a random access range finder. The 3-D data is used to build a triangulation which is a coarse planar model of the scene and is called the coarse scale map (CSM). The triangulation is used as a guide to acquire more data in the areas of the scene that look the most `interesting' without changing the orientation of the camera, or to choose the position of the 3-D camera for the acquisition of the next best view. The additional data is added to the CSM triangulation and forms what is called the fine scale map (FSM). The FSM is also structured as a triangulation and is processed in order to segment the various components of a scene. The typical 3-D scene of interest is made of a wooden beam, an electrical insulator, and an electric cable. The goal of the 3-D image processing is to use the triangulation to find the beam and the insulator in the scene.

In this paper, we consider the problem of tracking elastic objects with known material properties. That corresponds to utilization of specific a priori knowledge in nonrigid motion analysis. We propose the utilization of nonlinear finite element methods (FEM) for point correspondence recovery. We deal with range data, i.e., assume that surface points before and after motion are available from the sensing system. Nonlinear FEM not only allows for modeling of nonlinear material properties but also for large deformation between consecutive time frames (which are main limitations of widely utilized linear FEM). We propose a new algorithm for the point correspondence recovery in nonrigid motion using assumptions of known material properties and single (but not known) force applied to the object. Simulations and experimental results demonstrate the performance of the proposed algorithm.