Many authors, e.g., Rosenfeld and Pfaltz, Borgefors..., have proposed efficient and/or accurate approximations of euclidian distance on a 2D or 3D grid with methods which are connected, more or less directly, to norm derived distances, e.g., with L_p norms. This paper enlarges the scope in a continuous and m-dimensional framework. It presents a new broad class of distances, called 'sandwich' or 'periodic' distances. They are obtained by compounding in a periodic manner a certain number of norm-derived distances. The main result of this paper is the proof of a sufficient condition under which the triangular inequality is fulfilled, i.e., that the unit balls of the compounded distances belong to an ascending chain. Moreover, the theory includes weighted distances, giving this tool a high degree of flexibility.

We introduce a new Euclidian distance transformation (EDT) for binary images in Zⁿ, n >= 3 by combining our sufficient propagation EDT with the method of Saito and Toriwaki. Test in Z³ show that this new method is always faster than the well known EDTs and, especially, faster than the raster-scanning chamfer distance transformation. Moreover, we can efficiently implement it in parallel using a divide-and-conquer strategy.

In previous work, we presented algorithms for the analysis of maps and line-drawing images which are based on the processing of directional edge planes by directional morphological operations. This paper discusses the problem of efficient morphological processing of directional edge planes on a serial computer, where it is assumed that arbitrary kernels may be used. The proposed approach is based on a compact representation of the edge planes, which is obtained by using directional interval coding, where the direction of the interval as is adapted individually in each directional edge plane. In a broader sense, the proposed approach provides a general framework for efficient processing of binary images which as based on a directional interval coding. This framework supports basic morphological operations with arbitrary kernels and basic logical operations between any number of images.

A method to construct new pseudo-distances for the size function space based on the formal series representation of size function is introduced. These new pseudo-distances allow to measure quantitatively the differences in shapes by comparing size functions. Some experiments on digital images are shown.

One of the main tasks of digital image analysis is to recognize the properties of real objects based on their digital images. These images are obtained by some sampling device, like a CCD camera, and are represented as finite sets of points that are assigned some value in a gray-level or color scale. A fundamental question in image understanding is which features in the digital image correspond, under a given set of conditions, to certain properties of the underlying objects. In many practical applications this question is answered empirically by visually inspecting the digital images. In this paper, a mathematically comprehensive answer is presented to this question with respect to topological properties. In particular, conditions are derived relating properties of real objects to the grid size of the sampling device which guarantee that a real object and its digital image are topologically equivalent. Moreover, we prove that a topology preserving digitization must result in well-composed or strongly connected sets. Consequently, only certain local neighborhoods are realizable for such a digitization. Using the derived topological model of a well-composed digital image, we demonstrate the effectiveness of this model with respect to the digitization, thresholding, correction, and compression of digital document images.

Scientific data is frequently classified by using a presumed underlying model. A best fit approach can produce a set of residual values, and the minimum residual gives the classification. What is suggested here is a more visual approach - a characterization of the shape of the input curve, and a comparison against the shapes of the model histograms to collect gross shape information of various types. The example under consideration is that of respirogram curves, data collected from wastewater treatment plants, but the method applies to many other data acquisition processes.

We discuss measurement of properties in digitized images. We give an overview of the most accurate as well as practical feature estimation methods, particularly of geometry measurement on straight lines and circular arcs. The theory offered here gives an upper bound to the accuracy of measurement and characterization of any figure due to digitization.

The goal of segmentation is to partition a digital image or curve into segments such that the points in each segment share a common property. For example, we can partition a curve into connected subsets such that the points of each subset lie on a common straight line, or we can partition an image such that intensity function is linearly varying when restricted to ne part. A region growing algorithm starts from a small seed segment, and then repeatedly tries to add new points to this segment. Each time a point is added seed segment, whether the segmentation criterion is still satisfied for the enlarge segment, otherwise a new segment is started. In general, the verification of the segmentation criterion becomes increasingly more difficult when the segment gets larger. We propose new linear-time algorithms for region growing. These algorithms are related to the economical design of mechanical frameworks, where the goal is to make a rigid construction with as few bars as possible. According to this analogy, the region growing algorithm tries to attach each new point as firmly as possible to the existing region with a minimal amount of computation. We illustrate this technique for the segmentation of digital curves into straight or parabolic line segments, and for image segmentation with segments of linearly varying intensity.

A novel method for simultaneous image segmentation and shape decomposition is presented. The method may be applied directly to grayscale images. The is based on the analysis of the level curves of an 'edge-strength' function which is a measure of boundaryness of the image at each point.

Strong visibility is a generalization of standard visibility, defined with respect to a fixed set of line orientations. We investigate computational properties of this generalized visibility, as well as the related notion of strong convexity. In particular, we describe algorithms for the following tasks: (1) Testing the strong visibility of two points in a polygon and the strong convexity of a polygon; (2) Finding the strong convex hull of a point set and that of a simple polygon; (3) Constructing the strong kernel of a polygon; (4) Identifying the set of points that are strongly visible from a given point.

On a smooth generic surface we define ridges to be the local positive maxima of the maximal principal curvature along its associated curvature line and ravines. We investigate relationships between the ridges and ravines, singularities of the caustic generated by the surface normals, and singularities of the distance function from the surface. Stable numerical extraction of the ridges and ravines from range data is achieved via adaptive smoothing that preserves sharp ridges and ravines. We demonstrate applicability of the ridges and ravines for range image segmentation purposes.

A fast, simple and memory saving algorithm for stereogram generation is presented in this paper. It is a ray-tracing like algorithm making use of the cross-talk effect in stereoscopic computer graphics for generating single-image random-dot stereogram. It actively looks for the smallest equivalent class of points with the same color so that it gives the greatest freedom of coloring for artistic design with stereogram.

Identifying the projective group for patterns by developing the camera model, the projective Fourier transform and its inverse are obtained in analogy with the classical, that is, Euclidean Fourier analysis. Projectively adapted properties are demonstrated in a numerical test. Using the expression of the projective Fourier integral by a standard Fourier integral in the coordinates given by the complex principal logarithm, the discrete projective Fourier transform and its inverse are constructed showing that FFT algorithms can be adapted for their computations.

We propose an original approach to the watershed problem, based on topology. We introduce a 1D topology for grayscale images, and more generally for weighted graphs. This topology allows us to precisely define a topological grayscale transformation that generalizes the action of a watershed transformation. Furthermore, we propose an efficient algorithm to compute this topological grayscale transformation,a nd we give an example of application to image segmentation.

This paper describes a new method to register serial, volumetric x-ray computed tomography (CT) data sets for tracking soft-tissue deformation caused by insertion of intracavity brachytherapy applicators to treat cervical cancer. 3D CT scans collected from the same patient with and without a brachytherapy applicator are registered to aid in computation of the radiation dose to tumor and normal tissue. The 3D CT image volume of pelvic anatomy with the applicator. Initial registration is accomplished by rigid alignment of the pelvic bones and non-rigid alignment of gray scale CT data and hand segmentations of the vagina, cervix, bladder, and rectum. A viscous fluid transformation model is used for non-rigid registration to allow for local, non-linear registration of the vagina, cervix, bladder, and rectum without disturbing the rigid registration of the bony pelvis and adjacent structures. Results are presented in which two 3D CT data sets of the same patient - imaged with and without a brachytherapy applicator - are registered.

In this paper, we investigate a method of representing convex regions of the plane based on the sinusoidal transform and its associated Fourier descriptors. We analyze the derivatives of the sinusoidal transform and establish an inverse transform. We obtain a characterization of the set of periodic functions of one variable which are the sinusoidal transforms of 'well-behaved' convex regions of the plane. We derive negative results concerning the prospects for extending the sinusoidal representation scheme to non-convex regions. We show how various geometrical quantities and relations can be extracted from the sinusoidal transforms of regions, and hence from their sinusoidal Fourier descriptors.

We consider deformations of a silhouette while its boundary evolves according to a function of the curvature. The functions assumed to satisfy some general conditions of monotonicity and positiveness. For all such deformations we prove the following qualitative properties: convexity preservation, reduction of the number of the curvature extrema, and finite time disappearing. For some curvature- driven deformations we investigate the limiting shapes of the shrinking parts of the silhouette. A discrete polygon evolution scheme is used to demonstrate our theoretical.

Thinning on two-tone images is widely discussed. Two-tone images can be obtained by thresholding gray-level images. One major advantage of using two-tone images is that a binary image can be transformed into a continuous image to which many properties of topology can be applied. However, its tradeoff is that the thresholding function may lose some information of the original gray-level images. Rosenfeld introduced digital topology in early 1970's and fuzzy digital topology in late 1970's by the stimulation of Zadeh's fussy theory in 1965. It may be natural to process thinning directly on gray-level images. This paper proposes a template-based thinning algorithm on gray-level images and generates gray-level skeletons.

This paper presents a general-purpose definition for discrete curves, surfaces, and manifolds. We also focus on their tracking algorithms and implementations. This definition only refers to a simple graph, G equals (V,E), which is a generalized discrete space. The idea presented in this paper is to recursively define discrete curves, surfaces, solid objects and so forth. Obviously, a vertex is a point- unit-cell, and an edge is a line-unit-cell. A surface-unit- cell is a simple; closed path C if there is no pure subset of C can be a cycle. Based on this intuitive idea, n-D unit- cells can be defined in G for n > 2. For a graph G, i-D unit-cells, i equals 0,..., n + 1, provide a topological structure to the discrete space G. A n-D discrete manifold M is defined as (1) M consists of n-D unit-cells and any two n-D unit-cells are (n - 1)-D connected, (2) each (n - 1)-D unit-cell in M is contained by one or two n-D unit- cells, and (3) there is no (n + 1)-D unit-cell in M. This definition extends a definition extends a definition of digital manifolds. We have developed an linear time algorithm to decide if a subset is a discrete n-D manifold, a linear time algorithm to obtain the k-D boundary for n-D manifold. Such algorithms have been implemented in (Sigma) ₃, a space containing all integer points. This paper also discusses the non-orientable surface, quadtree surface-unit- cell representation, and an octree solid-unit-cell representation.

This paper introduces the concept of detection function for assessing recognition algorithms. A detection function specifies the probability that a particular recognition algorithm will detect the target, given the camera viewing direction and angle size and the target position. The detection function thus determines the region of space in which the target can be detected with high probability using certain specified camera parameters. For this reason, it provides a natural language for discussion of the task of tracking an object moving in 3D using a camera with adjustable pan, tilt, and zoom. Most previous studies on visual tracking involve the use of a camera with fixed viewing direction and viewing angle size. We advocate, however, an algorithm wherein these camera parameters are actively controlled to keep the target in the field of view and to maintain its image quality. In this paper we study geometrical issues related to the detection function and describe a novel tracking algorithm.

The factorization method has been sued for recovering both the shape of an object and the motion of a camera from sequential images. This method consist of two steps. The first step is to decompose measurement matrix into a product of two matrices. And the second step is to determine a non- singular matrix to revise these matrices. Mathematical consideration of this method is not paid much attention. In this paper, we elucidate the mathematical meaning of the second step. This gives intuitive interpretation of many facts of shape from motion problem. It makes clear to understand why we need three distinct affine projection images to determine the shape and motion of camera and what information we can get from two affine projection images. We also consider the factorization method for two images.

In an earlier work, Bennett et al. proposed an algebraic condition for four point pairs over two images to be projected by a rigid object. However, the condition is valid only if the images are projected orthographically and from exactly the same viewing distance. As a sequel to two previous attempts in extending the rigidity condition to more general cases, this paper shows how a similar condition can be constructed in the case when the camera projection processes can be described by paraperspective projection. This paper also shows how the rigidity conditions is related to the well-known epipolar constraint under that class of camera projection models. The rigidity condition has potential applications in stereo matching, motion correspondence, and object segmentation.

We show in this paper how it is possible to digitize a wide class of plane compacta in such a way that their digitization shave the same shape, in the sense of Borsuk, as the original set. This class is formed by all those compacta having the shape of finite polyhedra. As a corollary we get that for a still wide subclass, that whose elements are also absolute neighborhood retracts, the homotopy properties are also preserved under appropriate digitizations. Our results are based in approximation results by finite polyhedra and on the fact that the usual digitizations, when applied to finite polyhedra, preserve the homotopy type. Moreover, we show that if a set does not have the shape of a finite polyhedron, then there is not any possible way to digitize it while having its shape preserved.

In computer science there ha been increasing interest in development of matching measures for gray scale images. This problem has lots of applications from pure image matching to image retrieving from an image data base. There are various strategies and approaches to image comparison. In the paper we summarize many of them and give a short overview. Various types of low-level measures are studied and their properties are described. We show that measures based on our idea presented in 'vision geometry-95' is the best choice for the low-level image matching SOme new properties of this measure are explored. Several applications for matching strategy based on the measure are given.

3D image modeling system is highly demanded for automated visual inspection and non-destructive testing. It also can be useful to biomedical research, medical therapy, surgery planning, and simulation of critical surgery. Image processing and image analysis are used to enhance and classify the medical volumetric data. Analyzing medical volumetric data is very difficult. In this paper, we propose a new image modeling method based on least squares fitting by adaptive sub-division of tetrahedron. First, each pixel of the given medical image is enhanced through image processing. next, initial tetrahedral domain is constructed based on sphere criterion with the selected pixels. Finally, refining process is performed through sub-division of tetrahedron based on least squares fitting. User can specify the tolerance. Sub-division is continued until difference between approximation and measured value is less than specified tolerance.

In this paper we explore the general problem of recognizing 3D geometric configurations from a single 2D view.Of necessity the approach must be viewpoint independent, forcing us to characterize configurations by their 3D or 2D geometric invariants. Our results make use of several advanced mathematical techniques from algebraic geometry, notably the theory of correspondences and a novel 'equivariant' invariant theory, that clarify the relationship that exists between the 3D geometry and its 'residual' in a 2D image. This relationship has been shown to be a correspondence in the technical sense of algebraic geometry. Exploiting this, one can compute for a particular set of features a set of fundamental equations, which generate the ideal of the correspondence, and which completely describe the mutual 3D/2D constraints. We have chosen to call these equations 'object/image equations'. They can be used in a number of ways. For example, from a given 2D configuration we can determine a set of non-linear polynomial constraints on the geometric invariants of those 3D configurations capable of producing that given 2D configuration as an image; thereby arriving at a test for determining which object is being viewed. Conversely, given a 3D geometric configuration, we can derive a set of equations which constrain the images of that object, telling us which images contain a view of that particular object configuration. Methods to compute a complete set of generating object/image equations will be discussed. These include symbolic computational techniques like resultants, sparse resultants, and KSY resultants. The calculations have been carried out in a number of important cases, and the resulting object/image equations used in industrial and defense applications.

The paper continues the research in the area of the recently emerged optical computational geometry where geometric problems would be soled not by means of numerical computation but by means of construction solution on the screen of an optical device.

We will demonstrate for central-projection imaging systems a natural progression of cross-ratio invariant theorems extending from one through three dimensions. In each dimensions there is an invariant quantitative relationship between combinations of geometric entities in image space, and combinations of corresponding geometric entities in object space. In one dimension, when the object points and image points are co-linear, these entities are line segments formed by corresponding paris of object and image points. The 'mother of all invariants' is the invariant relationship between cross-ratios of products of the lengths of these corresponding line segments in object and image. In two dimensions these geometric entities are triangles formed by corresponding triplets of points in the object and in the image. There exists an invariant relationship between cross- ratios of products of areas of these corresponding triangles in object and image. The one- and two-dimensional results are well known. Not so well-known is the fact that for the case of multiple images of 3D scenes and objects the geometric entities are triangles and tetrahedra, and that there exist invariant linear relationships between cross- ratios of products of the areas of image-triangles and volumes of object-tetrahedra. One objective of our paper is to demonstrate that these linear relationships are established by a uniform pattern of algebraic arguments that extends the cross-ratio invariants in a natural progression from lower to higher dimensions. A second objective is to demonstrate that the resulting cross-ratio invariants can be interpreted as metric properties of geometric entities. A third objective is to demonstrate that these cross-ratios of points in the images, which we can observe directly, are equal to the corresponding cross-ratios of points in the objects, which may not be directly accessible. We will use computer simulations to validate the algebraic results we derive in this paper, and 3D graphics to visualize them.

The purpose of this note is to describe the degenerate critical point behavior of illumination functions as function of light direction and to use this description to characterize the set of light source directions whose image intensities have no degenerate critical points. A relationship, the accidental axis theorem, between certain degeneracies and the intrinsic geometry of the scene is established.

Based on the representation of the projected rotation group, we can construct the well-behaved quantity, which is called quasi moment, under the projected rotation. The representation of the projected rotation group is obtained, through the infinitesimal 3D rotation followed by the projection onto an image plane, by Lie group theory. Thus the representation of the projected rotation group has good transformation property under projected rotation,but whether the constructed quasi moment shares similar good transformation property or not is not so trivial. Therefore, in this paper, we will present the effect of the finite transformation on quasi moment explicitly and show that the quasi moment also has good transformation property under the projected rotation group.

A basic property of a simple closed surface is the Jordan property: the complement of the surface has two connected components. We call back-component any such component, and the union of a back-component and the surface is called the closure of this back-component. In an earlier work, we introduced the notion of strong surface as a surface which satisfies a global homotopy property: the closure of a back- component is strongly homotopic to that back-component. It means that we can homotopically remove any subset of a strong surface from the closure of a back-component. It was proved that the simple closed 26-surfaces defined by Morgenthaler and Rosenfeld, and the simple closed 18- surfaces defined by one of the authors are both strong surfaces. In this paper, some necessary local conditions for strong 26-surfaces are present. This is a first step towards a complete local characteristics of these surfaces.

The representation process of 3D objects in Euclidean space for computers is divided into the following two stages; approximation of an object as a polyhedron which is bounded by a number of planes, and digitization of points on the approximate polyhedron. In this paper, we focus on planes which form the boundary of polyhedra, and clarify the process of digitization of planes. We also analyze the geometric and topological properties of digitized plane as the resolutions increase.

One of the important problems related to image classification and compression is finding repeated structures in the image. This problem of finding regular structure is especially important with respect to document image analysis, where mismatches necessitate a residual map for symbolic compression. Although the focus of this paper is developing digital geometric models and methods for finding regular structure in digital document images, the applicability of the digital geometric approach is also demonstrated on images taken under affine and perspective projection. First, a fast linear-time algorithm is given to compute the static threshold that minimizes the non-well- composedness or weak connectivity of the document image. Next, a new digital similarity measure is introduced that outperforms the standard similarity measures, including the Hausdorff distance, with respect to determining if two discrete objects in the image are digitizations of the same prototype. This similarity measure is the minimum of four restricted Hausdorff distances. This measure is then used in a model-based compression algorithm. The compressed document image is not only much more compact than the original, but is also much closer to a actual monotonic digitization. Finally, we demonstrate that the same methods can be extended to finding structure in images taken under affine and perspective projection.

There are tow different kinds of elements in binary images: object pixels and background pixels. Many operations in image processing can be applied only to convert simple; pixels to background pixels. Some of these operations require such conversions must not change the connectivity structures of original images. Thinning is one of these operations. This paper established theoretical results. Such results are implemented into a computer package. The package is useful in designing new 2D thinning algorithms and is helpful in establishing 3D computerized thinning systems.

The recovery of motion for non-rigid and rigid bodies is addressed. Tracking the behavior of the object-generalized- coordination with time reveals important information about motion. The problem is presented in a physically based framework. However, many simplifications are introduced without sacrificing the required accuracy. A generic model for a class of objects is first decided on. Then, for a specific object, the generalized coordinates are tracked over time to detect different kinds of motions. This technique overcomes the difficulties in feature matching techniques, especially for smoothed objects.

The problem and its resolvent about redundancy of co-linear points in estimating the fundamental matrix (FM) which is a basic tool in scene analysis are developed, based on the application in computer vision of epipolar geometry and perspective geometric invariants. The redundancy means that, on a line, there are at most three points that can be used as matching points to estimate the FM, the others are the redundant points. Its proof in theory and experimental results show that the accuracy and stability of FM are distinctly improved by eliminating the redundant points.

This work continues the research presented. There we defined a general class of approximate convexity measures, referred to a s convexity indicators. Their definition was based on the fuzzy inclusion indicators, introduced by Sinha and Dougherty. A special attention was paid to the convexity indicator c. Although this convexity indicator has good theoretical properties, for instance to characterize the fuzzy compact convex sets, in the latter work it has been examined that it is not applicable to crisp sets and is very sensitive to random noise. Therefore, a new convexity indicator c_K has been proposed. It can be applied both to binary and grey-tone images and it is not sensitive to random noise.

We introduce a class of planar arcs and curves, called tame arcs, which is general enough to describe the boundaries of planar real objects. A tame arc can have smooth parts as well as sharp corners; thus a polygonal arc is tame. On the other hand, this class of arcs is restrictive enough to rule out pathological arcs which have infinitely many inflections or which turn infinitely often: a tame arc can have only finitely many inflections, and its total absolute turn must be finite. In order to relate boundary properties of discrete objects obtained by segmenting digital images to the corresponding properties of their continuous originals, the theory of tame arcs is based on concepts that can be directly transferred from the continuous to the discrete domain. A tame arc is composed of a finite number of supported arcs. We define supported digital arcs and motivate their definition by the fact that hey can be obtained by digitizing continuous supported arcs. Every digital arc is tame, since it contains a finite number of points, and therefore it can be decomposed into a finite number of supported digital arcs.