The mathematics of shape has a long history in the fields of differential geometry and topology. But does this theory of shape address the central problem of vision: finding the best data structure plus algorithm for storing a shape and later recognizing the same and similar shapes. Several criteria may be used to evaluate this: does the data structure capture our intuitive idea of 'similarity'? does it allow reconstruction of typical shapes to compare with new input? One direction in which mathematics and vision have converged is toward multiscale analyses of visual signals and shapes. In other respects, however, the recognition process in animals shows features that still defy mathematical modeling.

This paper presents a physically-based approach to the recovery of shape and nonrigid 3-D motion and the tracking of nonrigid objects. The approach makes use of deformable superquadrics (with additional parameterized tapering and bending deformations), dynamic models that offer global deformation parameters which capture large scale features and local deformation parameters that capture the details of complex shapes. We further present a generalization of the formulation to handle physically-based point-to-point constraints between models and to formally account for noise in the data using a recursive estimation technique based on Kalman filtering. such constraints enable us to automatically assemble object models from interconnected deformable superquadric parts. The equations of motion governing the behavior of the models make them responsive to externally applied forces. These composite models can be used to track the motions of articulated, flexible objects. Models are fitted to visual data by transforming the data into forces and simulating the equations of motion through time to adjust the translational, rotational, global, and local deformational degrees of freedom of the models. We present model fitting and motion tracking experiments involving 2-D and 3- D data.

This paper presents a technique for constructing shape representation from images using free- form deformable surfaces. We model an object as a closed surface that is deformed subject to attractive fields generated by input data points and features. Features affect the global shape of the surface while data points control its local shape. The authors' approach is used to segment objects even in cluttered or unstructured environment. The algorithm is general in that it makes few assumptions on the type of features, the nature of the data, and the type of objects. This paper presents results in a wide range of applications reconstruction of smooth isolated objects such as human faces, reconstruction of structured objects such as polyhedra, and segmentation of complex scenes with mutually occluding objects. We have successfully tested the algorithm using data from different sensors including gray-coding range finders and video cameras, using one or several images.

In this paper, we propose a new scheme for sensor data fusion in machine vision. The proposed scheme uses Kalman filter as the sensor data integration tool and hierarchical B- spline surface as the recording data structure. Kalman filter is used to obtain statistically optimal estimations of the imaged surface structure based on external sensor measurements. Hierarchical B-spline surface maintains high-order surface derivative continuity, may be adaptively refined, possesses desirable local control property, and is storage efficient. Hence, it is used to record the reconstructed surface structure.

Efficient solutions to spatial interpolation problems (e.g., regularization) and spatio-temporal interpolation problems (e.g., regularization plus Kalman filtering) can be obtained by using wavelet bases either for problem discretization or for preconditioning. Good approximate solutions can be obtained in only O(n) operations and O(n) storage locations, so that rear-real- time implementations are possible on standard microprocessors.

One of the reasons for creating a global energy-minimizing thin-plate fit in the surface- reconstruction-from-scattered-data problem is to find the differential properties of the surface and use these to characterize the surface. The author has also used the thin-plate surface to create a mesh of principal curvature lines on the surface to find a viewpoint invariant representation for the data. This paper examines what effect the changing of parameters in the surface fitting stage has on the differential properties of the surface, and thereby on the canonical surface representation based on the lines of principal curvature.

This research deals with the decomposition and description of curved objects. In ongoing work, a new part description for curves and surfaces using a set of curvature-based minimization operators has been developed. The decomposition operation simultaneously performs data interpolation, data smoothing, and segmentation. The unification of these three stages results in a smoothing operation that is tightly coupled with the primitives to be used in subsequent object description. Each of the minimization operators, in addition to having a curvature tuning, has a different spatial sensitivity function. As a result, different possible descriptions of an object are produced and these capture information at multiple spatial scales. Each object is described by a small number of tokens based on differential geometric properties. The set of descriptors produced for a given object can be organized into an unusual form of nonlinear scale-space. The utility of such a scale-based description by way of two methods for the characterization (i.e., recognition) of two-dimensional objects via their multi- scale signature in terms of curvature-scale-space features is demonstrated. One method is based on graph matching by dynamic programming and the other based on statistical properties of scale space ('shape texture').

This paper considers how basic geometrical properties like curvature, rigidity, and possible embeddings can be related to efficient image encoding and the statistical concept of redundancy. In particular, the redundancy of planar and parabolic patches of images as surfaces is revealed by reconstructing the original image from curvature measures that are zero for non-elliptic regions. This approach also gives a new perspective on encoding principles in biological vision.

Orientation-based representations (OBR) have many advantages. Three orientation-based differential geometric representations in computer vision literature are critically examined. The three representations are the extended Gaussian image (EGI),3 the support function based representation (SFBR),5 and the generalized Gaussian image (GGI).4 The scope of unique representation, invariant properties from matching considerations, computation and storage requirements, and relations between the three representations are analyzed. It is shown that an OBR using any combination of local descriptors is insufficient to uniquely characterize a surface. It must contain either global descriptors or connectivity information. The GGI as it was introduced4 requires the mapping of one principal vector onto the unit sphere. It is shown in this paper that this is unnecessary. This reduces the storage requirement of a GGI by half, therefore, making it a more attractive representation. It is also concluded that if the intention is to reconstruct surfaces from their representations, a SFBR should be used. If the intention is recognition, a truly orientation-based representation such as the GGI should be used.

Energy functions used for regularization algorithms measure the smoothness of a curve or surface. In order, to render acceptable solutions, these energies have to verify certain properties such as invariance with Euclidean transformations or invariance with parametrization. This paper extends the notion of smoothness energy to the notion of differential stabilizer. If an analogy is made with mechanics, smoothness energy corresponds to potential energy while differential stabilizers correspond to forces. To avoid the systematic underestimation of curvature for planar curve fitting, it is necessary that circles be the curves of maximum smoothness. Finally a set of stabilizers is proposed that meets this condition as well as invariance with rotation and parametrization.

A new approach to shape from shading is described based on a connection with a calculus of variations/optimal control problem. The approach leads naturally to an algorithm for shape reconstruction that is simple, fast, provably convergent, and, in many cases, provably convergent to the correct solution. In particular, if the surface is known to be locally concave (or convex) at a singular point in the image, then the algorithm provably reconstructs the correct surface in a region around the singular point. The algorithm is robust against noise and, in contrast with standard variational algorithms, does not require regularization. An explicit representation is given for the surface: its height is expressed as the minimal cost for an optimally controlled trajectory. This representation makes the convergence analysis for the algorithm transparent, and allows it to be easily adapted to different situations in practice. Uniqueness of the reconstruction (under suitable conditions) is an immediate consequence. We focus primarily on the case of illumination from the camera direction. For this case, if the singular points at which the surface is locally concave have been identified, and their heights are known, then the algorithm provably reconstructs the original imaged surface. For general direction of illumination, there is a representation of the surface in terms of a differential game, and a slightly modified surface reconstruction algorithm. Finally, given a continuous image, the algorithm can be proven to converge to the continuous surface solution as the image sampling frequency is taken to infinity.

The reconstruction of quantities from a scene can be formulated using regularization. The regularization formulation can be reduced to a formulation involving coupled sub-problems by considering the problem a one of simultaneously estimating different orders of derivatives. The starting point of the author's work is to ensure correspondence between the sub-problems by Augmented Lagrangian techniques. The finite element discretization of such problems is now firmly placed within a 'mixed finite element' formalism. For digital solution of these problems there are many iterative methods (including Uzawa's method, Arrow/Hurwicz method, conjugate directions) and associated pre-condition strategies. For future, real-time operation, it is often suggested that an analog network implementation be developed. A previous model for this is the Harris coupled depth-slope approach. As an analog implementation strategy, the 'neural network' optimization method of Platt is used to derive an analog resistive networks within the most general framework. Modifications to the basic approach to implement segmentation and viewpoint invariance are also discussed.

Models of 2-D and 3-D objects are an essential aspect of computer vision. Physically-based models represent object shape and motion through dynamic differential equations and provide mechanisms for fitting and tracking visual data using simulated forces. Probabilistic models allow the incorporation of prior knowledge about shape and the optimal extraction of information from noisy sensory measurements. In this paper we propose a framework for combining the essential elements of both the physically-based and probabilistic approaches. The combined model is a Kalman filter which incorporates physically-based models as part of the prior and system dynamics and is able to integrate noisy data over time. In particular, through a suitable choice of parameters models can be built which either return to a rest shape when external data are removed or remember shape cues seen previously. The proposed framework shows promise in a number of computer vision applications.

Energy-based surface models are commonly used in computer vision to interpolate sparse data, to smooth noisy depth estimates, and to integrate measurements from multiple sensors and viewpoints. Traditionally, a single surface estimate is produced with such models. Probabilistic surface modeling, which describes distributions over possible surfaces, enables us to integrate such measurements in a statistically optimal fashion, to model the uncertainty in the surfaces, and to develop sequential estimation algorithms. When applied to 2-1/2-D surfaces, probabilistic modeling allows us to incrementally estimate depth maps from motion image sequences and to integrate sparse range data using elevation maps. How to jointly model depth and intensity images to obtain more accurate models of depth, is shown. To better represent the structure of the visual world, full 3-D surface models must be used. These are usually represented using parametric surfaces, which can create difficulties when the surface topology is unknown. To overcome these problems, an incremental patch-based 3-D surface estimation algorithm is developed. Surface and feature-based methods are compared and a unified representation which encompasses both methods is proposed.

Deformable templates provide a method for feature extraction and object recognition. There are two basic ingredients to these templates: (i) a priori knowledge about the features to be extracted, which is embedded in the parameterized form of the template and by prior probabilities on the parameter values, and (ii) a matching criterion between the template and the image. In addition an algorithm must be specified to determine the optimal fit of the template. This paper defines deformable templates within a theoretical framework based on ideas from statistical physics. This framework enables one to incorporate standard techniques from robust statistics in a straightforward manner. These techniques are desirable since they allow the matching criteria to be robust and independent of outliers in the data. Matching criteria will then typically correspond to mixtures of distributions. It is then proved that by using the robust matching criteria and taking the limit of the statistical system as the temperature goes to zero, the standard Hough/Radon transform can be redriven. This can be used as a starting point for a deterministic annealing algorithm for matching the template. These ideas are illustrated with an example on detecting particle tracks in high energy physics experiments.

Toward the development of an object recognition and positioning system, able to deal with arbitrary shaped objects in cluttered environments, methods for matching two arbitrarily shaped regions of different objects are introduced, and how to efficiently compute the coordinate transformation which makes two matching regions coincide is shown. In both cases, matching and positioning, the results are invariant with respect to viewer coordinate system, and these techniques apply to both 2-D and 3-D problems, under either Euclidean or affine coordinate transformations. The 3-D Euclidean case is useful for the recognition and positioning of solid objects from range data, and the 2-D affine case for the recognition and positioning of solid objects from projections, e.g., from curves in a single image, and in motion estimation. The matching of arbitrarily shaped regions is done by computing for each region a vector of centered moments. These vectors are viewpoint-dependent, but the dependence on the viewpoint is algebraic and well known. This paper presents a new family of computationally efficient algorithms based on matrix computations, for the evaluation of both Euclidean and affine algebraic moment invariants of data sets. The use of algebraic moment invariants greatly reduces the computation required for the matching and, hence, initial object recognition. The approach to determining and computing these moment invariants is different than those used by the vision community previously. The method for computing the coordinate transformation which makes the two matching regions coincide provides an estimate of object position. The estimation of the matching transformation is based on the same matrix computation techniques introduced for the computation of invariants. It involves simple manipulations of the moment vectors. It neither requires costly iterative methods, nor going back to the data set. These geometric invariant methods appear to be very important for dealing with the situation of a large number of different possible objects in the presence of occlusion and clutter, and the approach to computing these moment invariants is different than those used by the vision community previously.

NASA scenarios for lunar and planetary missions include robotic vehicles that function in both teleoperated and semi-autonomous modes. Under teleoperation, on-board stereo cameras may provide 3-D scene information to human operators via stereographic displays; likewise, under semi-autonomy, machine stereo vision may provide 3-D information for obstacle avoidance. In the past, the slow speed of machine stereo vision systems has posed a hurdle to the semi- autonomous scenario; however, recent work at JPL and other laboratories has produced stereo vision systems with high reliability and near real-time performance for low-resolution image pairs. In particular, JPL has taken a significant step by achieving the first autonomous, cross- country robotic traverses (of up to 100 meters to use stereo vision, with all computing on- board the vehicle. This paper describes the stereo vision system, including the underlying statistical model and the details of the implementation. The statistical and algorithmic aspects employ random field models of the disparity map, Bayesian formulations of single-scale matching, and area-based image comparisons. The implementations builds Laplacian image pyramids and produces disparity maps from the 60X64 level of the pyramids at rates of up to two seconds per image pair. All vision processing is done on one 68020 augmented with Datacube image processing boards. The author argues that the overall approach provides a unifying paradigm for practical, domain-independent stereo ranging.

The stability of active contour models or 'snakes' is studied. It is shown that the modification of snake parameters using adaptive systems improves both the stability of the snakes and the boundaries obtained. The adaptive snakes perform better with images of varying contrasts, noisy images, and images with different curvatures along the boundaries. The computational costs at each iteration for the adaptive snakes is still of order (Nu) , where (Nu) is the number of points on the snakes. Comparisons of the results for non-adaptive and adaptive snakes are shown using both computer simulations and satellite images.

Steps are taken toward the automatic, intensity-based recognition of human faces by constructing a vision system to automatically detect frontally-viewed human eyes in real data. The eye is modeled using a deformable template that specifies a parameterized geometry and an intensity model. The fit of the template is measured by a cost-functional employing robust estimators, i.e., (alpha) -trimmed means and variances, to overcome highlights, shadows, nonrigid boundaries, noise, and other such difficulties. Recognition proceeds in three stages. First, candidate eyes are located by matching a simplified eye model against the responses of a robust, general purpose detector of intensity valleys and peaks. Second, the best fit of each candidate eye is found by minimizing the energy of a cost functional. Third, each candidate is accepted or rejected based on the amount of variance in the image data it explains.

This paper describes an object contour approximation method and its applications. It is assumed there is a rule R that locally estimates the boundaries of objects. Given a specified set of parameters, p1, ..., pn, and an index t (epsilon) {1, ..., M}, an object is abstracted as a closed curve described by a function C(p1, ..., pn, t) or simply C(t) where the other parameters are understood. An image strip centered at C(ti) and oriented along the normal to the curve at C(ti) is denoted by S(i). Boundary estimation further requires the specification of a function f(i), which is interpreted as a force applied to C(ti). F denotes the force vector (f(1), ..., f(m)). Given a initial curve C(p1(0), ..., pn(0), t), estimates for p1, ..., pn are refined iteratively by minimizing a nonnegative quantity (Epsilon) until pi(n) - 1) < (epsilon) for all i. In this paper, (Epsilon) takes the form: (omega) F2 + (1 - (omega) )F(infinity) , where the 2-norm favors point-group energy minimization fitting of the curve, and to (infinity) -norm favors individual point energy minimization fitting, and 0 ≤ w ≤ determines the relative importance of each type of fitting. A sequence of such curves initialized near an object will move and deform to fit the object and become fixed during the minimization process. Furthermore, we propose a method to describe the object contour when C(t) is stabilized. We also compare this method with the traditional curve fitting method, Fourier descriptors, dynamic splines, and deformable templates. Details are given for a simple form of this method using elliptical approximation. Finally, we present two applications of this method. The first one is for real-time object tracking, exploring the global shape. The other is for 2-D shape description using the feature vector once the global shape has been determined.

This paper explores the representation of the human face by features based on the curvature of the face surface. Curature captures many features necessary to accurately describe the face, such as the shape of the forehead, jawline, and cheeks, which are not easily detected from standard intensity images. Moreover, the value of curvature at a point on the surface is also viewpoint invariant. Until recently range data of high enough resolution and accuracy to perform useful curvature calculations on the scale of the human face had been unavailable. Although several researchers have worked on the problem of interpreting range data from curved (although usually highly geometrically structured) surfaces, the main approaches have centered on segmentation by signs of mean and Gaussian curvature which have not proved sufficient in themselves for the case of the human face. This paper details the calculation of principal curvature for a particular data set, the calculation of general surface descriptors based on curvature, and the calculation of face specific descriptors based both on curvature features and a priori knowledge about the structure of the face. These face specific descriptors can be incorporated into many different recognition strategies. A system that implements one such strategy, depth template comparison, giving recognition rates between 80% and 90% is described.

A suite of model-driven techniques for identification of 3-D quadric surfaces (cones, cylinders, and spheres) in segmented range imagery is presented. These techniques use range data, surface normal calculated on that data, knowledge of geometric characteristics of the various surfaces, and known model parameters to perform the classification. Second derivative quantities such as curvature, which are unreliable in the presence of noise, are avoided. Model information such as radii and vertex angles are used to guide the classification. Hough-based techniques are employed for extraction of spherical and cylindrical parameters, while conic parameters are presented for numerous scenes of both real and synthetic objects including part jumbles, objects in many poses, and noiseless and noisy synthetic objects. Empirical tests reveal that these methods have advantages (e.g. they appear to be very accurate) over previous methods.

This paper addresses the problem of obtaining natural (intuitive) descriptions of planar shapes. Shape description is a major problem in machine perception and is the basis for recognition. Many approaches have been suggested, but none provide a complete and natural solution. This paper suggests a method for producing an axial representation of a shape based on a hierarchical decomposition of the shape into its parts. The novelty of this approach lies in the combination of several competing approaches and tools, into a unified scheme and an efficient implementation producing natural descriptions. Smooth local symmetries are used for the axial representation of parts. Parallel symmetries are used to provide information on global relationships within the shape. This information is used for parsing the shape. A tree of all possible parsings under our interpretation is generated. Currently it is assumed that the shape is a closed smooth curve. This approach uses both region and contour information, and addresses the issues of local and global information, the issue of scale, and the notion of part. This method is computationally efficient, parameter free, stable, and results show that it provides an intuitive shape description.

This paper studies geometric features of surfaces that can be computed directly from stereo, motion, and shading. In the first part it is shown that the sign of the Gaussian curvature and the direction of motion can be computed directly from motion disparities. First, the sign of the normal curvature in a given direction at a given point in the image is obtained without the computation of the depth or slant/tilt map, given any two matched images, taken from stereo or general motion. The curvature sign is obtained from a 2-D geometrical relation, which involves the difference of slopes of line-segments in one image. Using this result local surface patches are classified as convex, concave, parabolic (cylindrical), hyperbolic (saddle point), or planar with a simple computation. This classification can be useful for the segmentation of objects into parts and for the construction of a concise object representation. When three (or more) such points are used, the focus of expansion, or the point toward which the motion is directed, is computed. In the second part the computation of geometric features from local shading analysis is studied. Local shading is ambiguous. For example, concave, convex, and saddle-like surfaces exist that appears the same from certain viewpoints. The shading approximation to shape, i.e., the relationship between the shape of the shading, the surface whose depth at each point equals the brightness in the image, and the shape of the original surface are discussed. This approximation is shown to be exact for more families of surfaces than other known local shape from shading techniques. It is obtained in the coordinate system of the light source. Without knowledge of the light source direction, it is shown that this approximation can be used to obtain some geometrical properties of surfaces, such as the sign of the Gaussian curvature.

Surface reconstruction methods exist for 2 1/2-D data given in the form of regular depth maps. This paper presents a method designed for building triangulated surfaces from less structured data given by irregularly sampled surface points forming a 'cloud of points' in space. Examples are given of the method applied to real stereo imagery as, for example, acquired by a mobile robot.

This paper examines the combination of the Hough transform with geometric hashing as a technique for object recognition. Geometric hashing is a technique for fast indexing into object-model databases by creating multiple invariant indices from model features; yet its description applies to objects that are modeled by point sets. Extracting points locally from image data is a noise sensitive process, and the analysis of geometric hashing on point sets shown that it is very sensitive to noise. The use of the Hough transform as a first layer for extracting features imposes constraints on the image data, and in domains in which the constraints are appropriate, there is a significant reduction in noise effects on geometric hashing. The use of arbitrary primitive features in geometric hashing schemes also has other advantages. As a concrete example, experiments are performed with objects modeled by lines. The output of the line-Hough transform on intensity images is used to directly encode invariant geometric properties of shapes. points in Hough space that have high counts are combined to yield invariant geometric indices. Objects containing lines are modeled as a collection of points in dual space, and invariant indices in dual space are found by computing invariant dual space transformations. The combination of the Hough transform and geometric hashing is shown by experiments to be noise resistant and suitable for cluttered environments.

This paper presents a model for flexible extruded objects such as wires, tubes, or grommets, and demonstrates a novel, self-adjusting seven-dimensional Hough transform that derives and analyzes their three-space curved axes from position and surface normal information. The method is purely local and is very cheap to compute. The model considers such objects as piecewise toroidal, and decomposes the seven parameters of a torus into three nested subspaces, the structure of which counteracts the errors implicit in the analysis of objects of great size and/or small curvature. It is the first example of a parameter space structure designed to cluster ill-conditioned hypotheses together so that they can be easily detected and ignored. This work complements existing shape-from-contour approaches for analyzing tori: it uses no edge information, and it does not require the solution of high-degree non-linear equations by iterative techniques. Most of the results including the conditions for the existence of more that one solution (phantom 'anti-tori'), have been verified using a symbolic mathematical analysis system. This paper presents, in the environment of the IBM ConVEx system, robust results on both synthetic CAD-CAM range data (the hasp of a lock), and actual range data (a knotted piece of coaxial cable), and discusses several system tuning issues.

The matching of 3-D anatomical surfaces to 2-D x-ray projections is an important problem in computer and robot assisted surgery. This paper presents a new method for determining the rigid body transformation that describes this match. The method performs a least squares minimization of the distance between the camera-contour projection lines and the surface. To correctly deal with projection lines that penetrate the surface, the square of the minimum signed distance along each line (distances inside the object are negative) is minimized. To quick and accurately compute distances to the surface, the precomputed distance map is represented using an octree spline whose resolution increases near the surface. The octree allows for quickly finding the minimum distance along each line using best-first search. This paper presents experimental results of 3-D surface to 2-D projection matching, and also shows how our method works for 3-D to 3-D surface matching.

Intrinsic signal dimensionality, a property closely related to Gaussian curvature, is shown to be an important conceptual tool in multi-dimensional image processing for both biological and engineering sciences. Intrinsic dimensionality can reveal the relationship between recent theoretical developments in the definition of optic flow and the basic neurophysiological concept of 'end-stopping' of visual cortical cells. It is further shown how the concept may help to avoid certain problems typically arising from the common belief that an explicit computation of a flow field has to be the essential first step in the processing of spatio- temporal image sequences. Signals which cause difficulties in the computation of optic flow, mainly the discontinuities of the motion vector field, are shown to be detectable directly in the spatio-temporal input by evaluation of its three-dimensional curvature. The relevance of the suggested concept is supported by the fact that fast and efficient detection of such signals is of vital importance for ambulant observers in both the biological and the technical domain.

The paper introduces the concept of the primary set of characteristic vies for general quadric- surfaced solids. A characteristic view (CV) is a representative view of a characteristic-view domain (CVD). The CVDs represent a partitioning of the viewing space of a solid based on the isomorphism of the labeled line-junction graphs of perspective-projection views. The primary set of CVs is a minimal subset of the set of CVs that is sufficient to represent all object surfaces and their relationships to each other in the most general viewing positions. Results indicate that the primary set of CVs can be used for efficiently guiding object recognition based on CV modeling. This paper discusses a scheme for computing some practical viewing constraints, describes the method for determining the primary set of CVs, and outlines a procedure for using the primary set of CVs for efficient object recognition.

A method for representing images by integrating curvatures and Delaunay triangulations is presented in this paper. The images to be represented include both range images and illuminated images. A plane or triangle is most often used to represent a surface in the images. The Delaunay triangulation is adopted in this paper for its numerical stability in computation. By segmenting the images in some regions before triangulation, the number of triangles represented will be reduced largely. Gaussian and mean curvatures are used for the segmentation and B-spline surface smoothing is performed before the curvature computation. The experimental results on a number of range and illuminated images are given. The results show that the integrating method for representing both range and illuminated images is effective.

This paper presents some theoretical results useful in 3-D reconstruction from disparity stereo maps. A practical implementation of the theory confirms the possibility of computing a fast spatial transposition of the observed scene without passing through an explicit computation of depth maps. Moreover, as the stereo pair moves, controlling the vergence and maintaining the fixation point, it is possible to integrate spatial information and refine gradually a simple volumetric model of the scene. A straight generalization of the approach suggests the introduction of the horopters theory, this is discussed in its weak and strong aspects. Some basic ideas related to the active vision paradigm are proposed and some experimental results on real data are presented.

Modern medical image techniques, such as magnetic resonance image (MRI) or x-ray computed tomography provide three dimensional images of internal structures of the body, usually by means of a stack of tomographic images. The first stage in the automatic analysis of such data is 3-D edge detection1,2 which provides points corresponding to the boundaries of the surfaces forming the 3-D structure. The next stage is to characterize the local geometry of these surfaces in order to extract points or lines on which registration and/or tracking procedures can rely.3,4,5,6 This paper presents a pipeline of processes which define a hierarchical description of the second order differential characteristics of the surfaces. The focus is on the theoretical coherence of these levels of representation. Using uncertainty, a link is established between the edge detection and the local surface approximation by addressing the uncertainties inherent to edge detection in 2-D or 3-D images; and how to incorporate these uncertainties into the computation of local geometric models. In particular, calculate the uncertainty of edge location, direction, and magnitude for the 3-D Deriche operator is calculated.1,2 Statistical results are then used as a solid theoretical foundation on which to base subsequent computations, such as the determination of local surface curvature using local geometric models for surface segmentation. From the local fitting, for each edge point the mean and Gaussian curvature, principal curvatures and directions, curvature singularities, lines of curvature singularities, and covariance matrices defining the uncertainties are calculated. Experimental results for real data using two 3-D scanner images of the same organ taken at different positions demonstrate the stability of the mean and Gaussian curvatures. Experimental results for real data showing the determination of local curvature extremes of surfaces extracted from MR images are presented.

Reconstruction of objects from a scene may be viewed as a data fitting problem using energy minimizing splines as the basic shape. The process of obtaining the minimum to construct the "best" shape can sometimes be important. Recently, [AWJ9O] brought to light some of the potential problems in the Euler-Lagrangian variational solution proposed in the original formulation [KWT87], and suggested a dynamic programming method. In this paper we further develop the dynamic programming solution. We show that in certain cases, the discrete form of the solution in [AWJ9O] may also produce local minimums, and develop a strategy to avoid this. In the continuous domain, we provide a stronger form of the conditions necessary to derive a solution when the energy depends on the second derivative, as in the case of "active contours."