We investigate the notion of duality as it applies to digital surfaces, and in particular to those surfaces which are orthogonally connected. We show how to define and prove a Poincare duality theorem, which relates the homology groups of a surface to its cohomology groups, and how this can be generalized to relative surfaces--a Lefschetz-Poincare duality. We show how a surface can be `refined' to include more points, in such a way that orthogonal connectivity can be used for both the surface and its complement. We then show how to define and prove an Alexander duality theorem, which relates the homology of a surface to the cohomology of its complement, and discuss some of the results of this theorem.

There are papers describing measures of correspondence or similarity between two binary images or their parts, but only two papers suggest a measure for a comparison of objects of two grey-scale images. However, there are numerous applications of a measure for grey-scale images as whole entities. A useful application is the comparison of different algorithms devoted to the same task (edge detection, thresholding, image enhancement, segmentation and image reconstruction). This paper proposes some results to define such a measure. They are based on two different representations of grey-scale images: as `surfaces' and as `stacks' or umbra. We study an adaptation of some known formulas used for binary images to grey-scale images, and present a geometrical variant of such a measurement. We study different measures of diversity, based on different digital metrics, direct calculations of distances, and digital functions adapted to grey-scale images. We show that the `stack' representation needs more calculation time and that measures based on the representation are not sensitive to small image shifts, but very sensitive to noise.

In this paper we give an answer to the problem of enumerating the combinatorially distinct segments of given length in digital lines and rectangular blocks of given shape in digital planes. We also give a formula to locate a precise piece and study the distribution of all segments of digital lines. We deduce from these results a very simple algorithm to recognize the normal vector of a digital plane.

There are two different kinds of elements in binary images: object points and background points. A simple point is an object point whose conversion to a background point does not change the connectivity of the original image. Many operations in image processing can be applied only to convert simple points to background points. Finding an efficient method for determining the simplicity of an object point is an interesting research topic. Although 2D simplicity has been extensively studied recently, more work needs to be done for 3D simplicity. This paper studies important properties of 3D simplicity which may be useful in certain operations of image processing, for example, thinning.

This study results in a very general class of approximate convex measures for objects on grey- tone images. There measures are referred to as convexity indicators. They are based on fuzzy set theory, more precisely, on the fuzzy inclusion indicators defined by Sinha and Dougherty. Consideration is given to the fuzzy morphological operations which are used in the construction of inclusion and convexity indicators.

A simple point of an object is a point whose removal does not change the topology. However, the simultaneous deletion of simple points may change the topology. A popular way for overcoming this problem is to use a directional strategy. This method has good properties in 2D discrete spaces but it does not work in 3D. Through the notion of P-simple point we propose a general strategy for removing points in parallel without altering the topology of a 3D space. We derive some new sufficient conditions such that any parallel thinning algorithm satisfying these conditions is ensured to preserve topology.

We define the notions of strong convexity and strong visibility. These notions generalize standard convexity and visibility, as well as several types of nontraditional convexity, such as iso-oriented rectangles and C-oriented polygons. We explore the properties of strong convexity and strong visibility in two and three dimensions. In particular, we establish analogs of the following properties of standard convex sets: (1) Every two points of a convex set are visible to each other. (2) The intersection of convex sets is a convex set. (3) For every point in the boundary of a convex set, there exists a supporting plane through this point. (4) A closed convex set in three dimensions is the intersection of all halfspaces that contain it.

Polygonal approximations to skeletal or stroke-based representations of 2D objects may consume less storage and be sufficient to describe their shape for many applications. Multi- scale descriptions of object outlines are well established but corresponding methods for skeletal descriptions have been slower to develop. In this paper we offer a method of generating scale-based skeletal representation via the Voronoi diagram. The method has the advantages of less time complexity, a closer relationship between the skeletons at each scale and better control over simplification of the skeleton at lower scales. This is because the algorithm starts by generating the skeleton at the coarsest scale first, then it produces each finer scale, in an iterative manner, directly from the level below. The skeletal approximations produced by the algorithm also benefit from a strong relationship with the object outline, due to the structure of the Voronoi diagram.

Analyzing the 3D images of a given surface as viewed from different positions naturally leads to investigation of coordinate-independent geometric surface features reflecting its essential properties. In the present paper we study surface point features related to ridge and ravine lines on a surface. These lines introduced in our previous works are defined as curves corresponding to the boundary points of the skeleton of the distance transform of the surface. We show that the ridges and ravines can be extracted via the directional derivatives of the principal curvatures along the associated principal directions. However, even after this local description the direct extraction of the ridges and ravines is a time-consuming procedure. It turns out that the ridge and ravine lines contain some remarkable points (end points and others) that can be extracted relatively easily. After finding such points the procedure of ridge and ravine extraction becomes much simpler. Moreover, these points are closely connected with some singularities of caustics and wavefronts, and have an independent interest in image analysis as visual invariants. The paper is devoted to the investigation of such points and the accompanying geometry of singularities of wavefronts and caustics. We also demonstrate applicability of the ridges and ravines defined as above and related point features in image understanding.

This paper addresses the problem of line invariant features matching in a sequence of stereoscopic images of flat objects. The proposed approach is simple, but effective. It is essentially based on the computing of line features which are invariants under the geometrical transformation, such as projective or affine transformation. A line segment is represented by an invariant feature vector in a bi-dimensional parameter space. The line matching is achieved through two processes, the hypothesize and verification process. Each invariant feature vector is directly compared with the pre-registered feature vectors. A pair of lines which are represented by corresponding feature vectors must satisfy some pre-defined geometric constraints (relative angle and distance), in order to be considered matched. Our method is an efficient algorithm which is distinctly fast. Both computer generated and real data are included in experiments to show the stability of the computed features and the convergence speed of the matching system.

We consider the problem of illuminating a simple polygon by flood-lights. We show that the problem of placing the minimum number of 90 degree(s) flood-lights to illuminate the interior of a polygon is NP-hard.

We examine the importance of the definition of neighbors and neighborhoods for grouping in document understanding and list some previous definitions. We present a number of benefits to using the Voronoi neighborhood definition; however, we argue that definitions based upon the point Voronoi diagrams are insufficient in the general case (e.g. for grouping image elements in line drawings). We give the definition of a generalized (Euclidean distance measure, 2D Cartesian space, and an area based generator set) Voronoi tessellation and then present our algorithm for approximating this generalized tessellation. The algorithm is constructed from a normal point Voronoi tessellation algorithm. A parameterized Voronoi neighborhood graph (VNG) which can be derived from the tessellation is defined. A graph algorithm for grouping based on the VNG, its image elements, and Voronoi cell descriptors can then be easily derived. We show some results of how this algorithm was used in a map understanding system.

Often objects which are not convex in the mathematical sense are treated as `perceptually convex'. We present an algorithm for recognition of the perceptual convexity of a 2D contour. We start by reducing the notion of `a contour is perceptually convex' to the notion of `a contour is Y-convex'. The latter reflects an absence of large concavities in the OY direction of an XOY frame. Then we represented a contour by a G-graph and modify the slowest descent-- the small leaf trimming procedure recently introduced for the estimation of shape similarity. We prove that executing the slowest descent dow to a G-graph consisting of 3 vertices allows us to detect large concavities in the OY direction. This allows us to recognize the perceptual convexity of an input contour.

The paper addresses the problem of finding fast algorithms that accurately generate arbitrary curves on discrete lattices. The curves are supposed to have certain smoothness. No special assumption is made on their given representation (e.g. parametric, nonparametric, tabular). The proposed method consists of two stages, namely learning and drawing. In the learning stage, each curve is piecewise approximated by polynomials and then algorithms for generating the polynomials are derived. The algorithms are similar to those developed by Bresenham for straight lines and circular arcs. They are based on an integer decision variable and on an updating procedure. The decision process minimizes the error between the ideal curve and the digital one. The updating acts as an adaptive rounding off process that prevents the accumulation of errors. The drawing stage is very fast. Neither multiplies nor fractional integer operations are required. The entire curve is piecewise traced. The decision variable is initialized for each polynomial. Each new point is selected from two possible candidates, according to the sign of the decision variable. Two examples, the generation of a circular arc and of a sine-wave, are shown.

Active contours have become an attractive subject in computer vision. Connectivity and closure properties of these contours help to overcome some important difficulties in computer vision, (1) edge organization and (2) region merging. Consequently, using deformable contours brings additional knowledge in the form of curve properties, and thus reduces dramatically the search space dimension. Many researchers described a dynamic contour as a snake curve which is deformed so as to minimize the curvilinear integral of the sum of internal and external local energies. Here to fore, proposals were restricted to using a single deformable curve. In this paper, we present a probabilistic model of multiple dynamic non- parametric curve matching with 2D images. The model is made up of two parts: (1) image formation, and (2) high-level interactions, which measure consistency of the reconstructed object with the given image and the relational a priori information of the object, respectively. The model is conceived for a semitransparent scene such as additive projection imaging - planar radiographical transmission or planar emission imaging. The scene model represents a hierarchical structure of three processes: lines, regions and relational graphs. Thus, an object is modeled as a set of linked subobjects according to a 3D relational graph which can be projected from a known viewpoint as a 2D region relational graph. The graph represents high- level structural knowledge which reduces the search space dimension by conditioning the a posteriori probability to the a priori known graph. The resultant objective function is optimized using a descending search method with randomized sampling. Finally, successful results are presented for object matching in semitransparent noisy synthetic scenes.

A pair of stereo images can be viewed to perceive a 3D scene. For the human vision system this is an easy process for both real images and random dot stereograms. An equivalent 3D machine vision system using local correlation can be used for decoding of random dot stereograms and for producing edge images of stereo image pairs. If the objects in the stereo images have sharp edges, the depth of these can be revealed by local correlation and threshold. The depth contour of the connecting surface is more difficult to detect and is, with the current technique, absent or disrupted. In the present paper the local correlations technique and the estimation of the depth are discussed and results from real stereo images are shown.

Many techniques in machine vision require tangent estimation. The direction-dependent tangent (DDT) is introduced. The representation makes explicit the direction of curve following and the concavity, hence facilitating shape matching. The scheme is a simple but powerful enhancement to the standard tangent notation. However, discrete tangent and curvature estimations are very sensitive to noise and quantization errors, and the original DDT formulation is difficult to apply directly to digital curves. Based on the geometric property of DDT, we propose to detect zero curvature points to determine the DDT values. Traditional approaches to zero curvature detection rely heavily on discrete tangent and curvature estimations, which are difficult to approximate accurately. Hence, most researchers adopted the multi-scale solutions, which are costly to compute. In this paper, we put forth a new measure, which we called `turning angle', for zero curvature detection. Based on this measure, we develop an efficient conditioning algorithm to tackle the zero curvature detection problem. Although the conditioning algorithm is quite straightforward, the zero curvature points detected are quite stable across scales.

For pattern recognition and image understanding, it is important to take invariance and/or covariance of features extracted from given data under some transformation into consideration. This makes various problems in pattern recognition and image understanding clear and easy. In this article, we present two autoregressive models which have proper transformation properties under rotations: one is a 2D autoregressive model (2D AR model) which has invariance under any 2D rotations and the other is a 3D autoregressive model (3D AR model) which has covariance under any 3D rotations. Our 2D AR model is based on a matrix representation of complex number. It is shown that our 2D AR model is equivalent to Otsu's complex AR model. On the other hand, our 3D autoregressive model is based on the representation theory of rotation group such as the fundamental representation of Lie algebra of SU(2)(Special Unitary group in 2D which includes rotation group), which is called Pauli's matrices.

In this paper, we present a new approach for quadric curves based stereo vision. We use the decomposability of the quadric form to establish the correspondence of two quadric curves which are the projections of a planar conic and to globally reconstruct the conic in space. An experimental result is given.

A special class of subsets of binary digital 3D pictures called `well-composed pictures' is defined by two simple conditions on a local voxel level. The pictures of this class have very nice topological and geometrical properties; for example, a very natural definition of a continuous analog leads to regular properties of surfaces, a digital version of the 3D separation theorem has a simple proof, and there is only one connectedness relation in a well-composed picture, since 6-, 18-, and 26-connectedness are equivalent. This implies that many algorithms used in computer vision and computer graphics and their descriptions can be simpler, and the algorithms can be faster.

This paper considers the reconstruction of the boundary of a 2D object from one or more digital representations that have been obtained by successive displacements of a digital image sensor. We explain how the reconstruction can be done for known displacements as well as for unknown random displacements that are uniformly distributed. In the latter case we assume that we can solve a certain correspondence problem. The reconstructed boundary can be characterized by a sliding ruler property of which the well-known Lagrange interpolation is a special case. It is also shown that the reconstruction can be exact under certain circumstances. Although we only consider the reconstruction of functions of one variable, the technique can be extended to functions of two or more variables. The technique can also be applied to measurements generated by other digital sensors such as range sensors.

Organ definition in computed tomography (CT) is of interest for treatment planning and response monitoring. We present a method for organ definition using a priori information about shape encoded in a set of biometric organ models--specifically for the liver and kidney-- that accurately represents patient population shape information. Each model is generated by averaging surfaces from a learning set of organ shapes previously registered into a standard space defined by a small set of landmarks. The model is placed in a specific patient's data set by identifying these landmarks and using them as the basis for model deformation; this preliminary representation is then iteratively fit to the patient's data based on a Bayesian formulation of the model's priors and CT edge information, yielding a complete organ surface. We demonstrate this technique using a set of fifteen abdominal CT data sets for liver surface definition both before and after the addition of a kidney model to the fitting; we demonstrate the effectiveness of this tool for organ surface definition in this low-contrast domain.

In the current work we integrate well established techniques from finite deformation continuum mechanics with concepts from pattern recognition and image processing to develop a new finite element (FE) tool that combines image-based data with mechanics. Results track the deformation of material continua in the presence of unknown forces and/or material properties by using image-based data to provide the additional required information. The deformation field is determined from a variational problem that combines both the mechanics and models of the imaging sensors. A nonlinear FE approach is used to approximate the solution of the coupled problem. Results can be applied to (1) track the motion of deforming material and/or, (2) morphological warping of template images or patterns. 2D example results are provided for problems of the second type. One of the present examples was motivated primarily by a problem in medical imaging--mapping intersubject geometrical differences in human anatomical structures--with specific results given for the mapping 2D slices of the human distal femur based on X-ray computed tomographic images.

In this paper we present a coarse-to-fine approach for the transformation of digital anatomical textbooks from the ideal to the individual that unifies the work on landmark deformations and volume based transformation. The Hierarchical approach is linked to the Biological problem itself, coming out of the various kinds of information which is provided by the anatomists. This information is in the form of points, lines, surfaces and sub-volumes corresponding to 0, 1, 2, and 3 dimensional sub-manifolds respectively. The algorithm is driven by these sub- manifolds. We follow the approach that the highest dimensional transformation is a result from the solution of a sequence of lower dimensional problems driven by successive refinements or partitions of the images into various Biologically meaningful sub-structures.

There are well established techniques for the biomathematical analysis of sets of homologous images with landmarks. These include the construction of the average configuration of landmarks, the statistical analysis of the procrustes residuals of the landmark positions and the averaging of the images themselves. This paper outlines a method of performing similar steps on sets of images with homologous 1D features as well as landmarks. The basis of the method is the expanded and consistent application of the thin-plate spline, a tool already used in the analysis of landmark images.

The cortical fold is one of the most striking features of the brain and it plays a tremendously important role in understanding brain function. In this paper we build a precise mathematical representation of a typical cortical surface. This representation will allow us to make statements about the geometry of the surface and will enable us to compute intrinsic geometrical properties such as the Mean and the Gaussian curvature of the surface.

Recent advances in computational geometry have greatly extended the range of neuroanatomical questions that can be approached by rigorous quantitative methods. One of the major current challenges in this area is to describe the variability of human cortical surface form and its implications for individual differences in neurophysiological functioning. Existing techniques for representation of stochastically invaginated surfaces do not conduce to the necessary parametric statistical summaries. In this paper, following a hint from David Van Essen and Heather Drury, I sketch a statistical method customized for the constraints of this complex data type. Cortical surface form is represented by its Riemannian metric tensor and averaged according to parameters of a smooth averaged surface. Sulci are represented by integral trajectories of the smaller principal strains of this metric, and their statistics follow the statistics of that relative metric. The diagrams visualizing this tensor analysis look like alligator leather but summarize all aspects of cortical surface form in between the principal sulci, the reliable ones; no flattening is required.

In this paper, we present a method for simultaneous registration and surface fitting, using multiple sets of 3d points. Our motivating application is the automatic construction of CAD models from 3d surface measurements of physical objects. A wide variety of technologies are currently used to measure 3d shape [1] , and our method is applicable to the data collected by many of them. However, to simplify the discussion, we will describe the problem in terms of an idealized laser range scanner. This idealized laser range scanner captures the shape of a physical object as a set of range images. Each range image is a sample of 3d locations from those parts of the surface of the object which are visible from a single scanner viewpoint. Although single range images are adequate for some applications, in general, to model the entire surface, it is necessary to collect range images from multiple viewpoints. At some point in the processing, each range image is a set of 3d points measured relative to the corresponding scanner viewpoint. To get consistent 3d data for the entire surface of the object, the range images then need to be regisiered into a common 3d coordinate system.

Current visualization techniques cannot provide very useful tools for quantitative analysis, high level geometric and topological representations, and structural understanding of the anatomical objects. Geometric modeling approach can be more effective for such applications. This paper describes our initial effort in modeling the geometric shapes of branched tubular structures. A model reconstruction algorithm is developed to generate bicubic C¹ B_spline surface models for branched structures based on cross section data. Such surface models can then be systematically operated and manipulated in a geometric modeler being developed in CI_EMED.

The explicit use of partial differential equations (PDE's) in image processing became a major topic of study in the last years. In this work we present an algorithm for histogram modification via PDE's. We show that the histogram can be modified to achieve any given distribution. The modification can be performed while simultaneously reducing noise. This avoids the noise sharpening effect in classical algorithms. The approach is extended to local contrast enhancement as well. A variational interpretation of the flow is presented and theoretical results on the existence of solutions are given.

We show how geometry-driven diffusion based on the Nordstrom-functional can be used to crystallize the geometric content of a closed contour by simultaneously suppressing noise while enhancing the salient features. Furthermore, we propose a robust and highly parallelizable method that will automatically group edge-segments to produce a set of fully connected contours. The result could be used e.g., as input for recognition programs based on aspect graphs, or as a good initial guess for snakes and active contours.

A novel scheme for performing detection and measurements in medical images is presented. The technique is based on active contours evolving in time according to intrinsic geometric measures of the image. The evolving contours naturally split and merge, allowing the simultaneous detection of several objects and both interior and exterior boundaries. The proposed approach is based on the relation between active contours and the computation of geodesics or minimal distance curves. The minimal distance curve lays in a Riemannian space whose metric is defined by the image content. Measurements are performed after the object is detected. Due to the high accuracy achieved by the proposed geodesic approach, it is natural to use it to compute area or length of the detected object, which are of extreme value for diagnosis. Open curves with fix boundaries are computed as well. This addition to the deformable model adds flexibility, allowing the user to choose guiding points in the image or to select regions for measurements. Experimental results of applying the scheme to real medical images demonstrate its potential. The results may be extended to 3D object segmentation as well.

This paper describes a complete recognition system for planar objects, using semi-local projectively invariant information on the contours to be identified. The system combines two different canonical descriptions of these segments. Using semi-local information makes it possible to recognize objects which are only partially visible. This allows for realistic imaging situations. By doing recognition up to only a projective transformation, nothing has to be known about the camera position or focal length, which makes the system applicable in a wide range of applications. Classification of training data is done by BUCA, a new supervised classification algorithm which is both fast and reliable. BUCA incorporates the idea of the `minimal description length' principle by the use of splitting entropy. The final assembling of recognized segments tries to avoid polynomial running time by first combining the most certain matches, and subsequently eliminating all segments that are compatible with such a match.

In this paper we present an algorithm for locating the parabolic curves in a scene using multiple light sources. The core of the algorithm is a detailed analysis of the critical points of image intensity and a robust critical point detector. The gradient of image intensity is characterized in terms of the Weingarten map and the critical points are classified by this characterization. They are detected and evaluated by means of the rotation index of the gradient vector field. Three computer simulations on synthetic data illustrate the algorithm.

Infrared search and track systems are important to the Navy as early warning devices to detect fast moving sea-skimming threats. Sensors must be able to analyze severely distorted images since the propagation medium consists of long horizontal paths that are near the ocean surface. The thermodynamics of this configuration foster the formation of gradients in the refractivity, which in turn can create striking and puzzling anomalies in the perceived image. An accurate simulation of the propagation characteristics of signals is crucial to help elucidate possible errors. We describe work to develop simple topological methods to understand propagation distortions in the marine and coastal environment.

Vision algorithms are proposed for an automated robot assembly task. The goal is to insert cylindrical objects with arbitrary cross-section shapes into narrowly matching holes. Scenes have variable compositions and the viewpoint of the camera is rather arbitrary. An affinely invariant shape description is used to compare inflection bounded segments of the image contours with similar segments describing a set of shapes in a model database. The comparison is a simple distance calculation between invariant segment signatures following a crude index-based preselection procedure. Once all matching image-model segment pairs have been found, they are grouped into complete model instances found in the image, by a consistency check algorithm. The typical shapes considered have no salient features, which moreover are small in number. This complicates the task of robust recognition. Besides recognition, the determination of object pose and position is described. A new method for determining camera focal length using image features is presented. Experimental results are discussed.

A novel approach for the computation of optical flow based on an L¹ type minimization is presented. It is shown that the approach has inherent advantages since it does not smooth the flow-velocity across the edges and hence preserve edge information. A numerical approach based on computation of evolving curves is proposed for computing the optical flow field. Computations carried out on a number of real image sequences in order to illustrate the theory as well as the numerical approach.

A hierarchical scheme for chain encoded digital contours is introduced. If the contour represents the boundary of a binary image, a true digitization of the image is realized as the pyramid structure goes from the fine to coarser resolution levels. A progressive transmission system is designed to go from a coarse resolution level to finer levels which uses essentially the same number of bits as transmission of the contour at the finest resolution.

The thin-plate spline can unwarp a data set of landmark-labelled medical images so that their landmarks are exactly superposed over an average landmark configuration. This pixel relabeling is highly nonlinear in the original image data. Nevertheless, for most biostatistical purposes, the resulting unwarped images can be treated as if they arose from raw measurements (in this case, pixel-by-pixel gray levels) by a covariate adjustment suppressing unwanted variation. Tasks of discrimination and classification of images can benefit greatly from the augmented precision of subsequent quantitative comparisons. These `adjusted mean differences'--pixelwise group mean differences of the unwarped images--may be combined with differences of landmark shape in prescriptions for new landmark locations that further sharpen the unwarping or classification. These considerations are exemplified in a detailed analysis of some midsagittal brain images of medical students and schizophrenics.

The most widely accepted representation of an image is the matrix representation in which each element has numerical information such as a color or a gray level. However, as long as such representation is used, it is not so easy to have operations based on global information. This paper proposes an alternative representation of an image called `contour representation.' For each gray level i we compute boundaries of connected regions of pixels with gray levels greater than or equal to i. It is easy to reconstruct an original image from those boundaries. Representation of an image as a collection of those boundary lines (contour lines) associated with gray levels is the contour representation of an image. We first give an output-sensitive algorithm for computing all those contour lines and a compact way of such representation. Then, an image can be dealt with as a set of geometric objects. This leads to several advantageous features such as improving resolution or restoration of flaw regions, which cannot be accomplished in conventional pixel-based approaches. Experimental results are also included.