Abstract not available.

We show how algebraic methods can be used to provide a mathematical framework suitable for the definition of multidimensional hypersurfaces in digital space, and for proofs of separation theorems. Our work is motivated by the need for a mathematical basis to provide a strong foundation for the creation of image processing algorithms in multidimensions; multidimensional images have been shown to arise naturally in areas as diverse as medical diagnosis and agricultural imaging. Whereas previous work in the area has been either combinatorial or has used the tools of point-set topology, we show how homology and cohomology groups can be defined in digital space. Our definitions are of a broad nature encompassing many of the standard adjacencies used to define digital objects. Given that in Euclidean space these groups satisfy conditions which provide for very neat proofs of separation theorems, we conjecture that an analogous theorem is true in digital space. We further show that the concept of orientability can be given a meaning in digital space more closely analogous to its classical meaning than definitions given previously in the image processing literature.

When an area is measured digitally, by the pixels it encloses or by the lattice points it overlaps, there is invariably an error in the recorded value. The determination of that error is a long-standing problem in the field of geometric probability and a relatively recent problem in applications of computer vision. This paper deals with the errors associated with the digital measurement of rectangles, including squares; it is presented as a contribution to digital geometry, but its relevance is to automated visual inspection. The results show that for a rectangle aligned on the co-ordinate lattice at a fixed angle, the error varies with size of rectangle according to a near-parabola function; and for a rectangle of fixed size rotated by a small amount about that initial angle, the error varies according to a near-sinc function.

A distance transform will convert a bi-level image into a gray scale image, where the intensity of the object pixels is proportional to their distance from the nearest back-ground pixel. This can be computed in two passes through an image, and has been used to encode all binary erosions and dilations into one `globally eroded' image. It is also possible to encode all possible binary openings and closings as gray levels, allowing any particular opening or closing to be achieved through a simple thresholding operation, or by non-destructive comparisons. We define nodal points in the distance transform as those which have no neighbors having the maximum possible value (For example, 7 for diagonal pixels, and 12 for others using Euclidean distance). At each of these points a digital circle can be drawn, whose values equal that of the significant point. A simple histogram of the thus encoded image yields the roughness spectrum, but the spectrum found using only the significant points may be just as useful.

in this paper we solve several geometric and image problems using the BSR (broadcasting with selective reduction) model of parallel computation. All of the solutions presented are constant time algorithms. The computational geometry problems are based on city block distance metrics: all nearest neighbors and furthest pairs of m points in a plane are computed on a two criteria BSR with m processors, the all nearest foreign neighbors and the all furthest foreign pairs of m points in the plane problems are solved on three criteria BSR with m processors while the area and perimeter of m iso-oriented rectangles are found on a one criterion BSR with m² processors. The problems on an nxn binary image which are solved here all use BSR with n² processors and include: histogramming (one criterion), distance transform (one criterion), medial axis transform (three criteria) and discrete Voronoi diagram of labeled images (two criteria).

Shape features characterizing patterns represented by their distance transform are illustrated. The role they can play in pattern decomposition is described with reference to a process based on the detection of a number of pixels significant for shape interpretation. Suitable sets of these pixels are regarded as feature sets, and used as seeds to be expanded into regions. After a merging phase, the regions originate a meaningful decomposition.

A special class of subsets of binary digital images called `well-composed sets' are defined. The sets of this class have very nice topological properties; for example, the Jordan Curve Theorem holds, the Euler characteristic is locally computable, and there is only one connectedness relation, since 4- and 8-connectedness are equivalent. This implies that properties of algorithms used in Computer Vision can be stated and proved in a clear way, and that the algorithms themselves become simpler and faster.

Loosely speaking, a simple set of a finite binary image is a set of 1s whose deletion `preserves topology.' This concept can be made precise in different (and inequivalent) ways. Ronse established results which imply that, for finite 2-D binary images on a Cartesian grid and three different definitions of simple set, a set S of 1s is simple if every subset of S that lies in a 2- point by 2-point square is simple. In fact this is a special case of a general result which applies to arbitrary finite binary images -- not just 2-D images on a Cartesian grid -- and any definition of simple set which satisfies three axioms stated in this paper. For finite binary images on an n-dimensional Cartesian grid, we give appropriate definitions of simple set which satisfy all the axioms. When these definitions of simple set are used, verification that a parallel reduction operator for n-dimensional binary images preserves the topology of all possible input images may be achievable by checking only a finite number of cases.

In this paper, we study pattern recognition using Probabilistic Iterated Function Systems (PIFS). A learning system can be defined by three rules: the encoding rule, the rule of internal change, and the quantization rule. In our system, the data encoding is to store an image in a stable distribution of a PIFS. Given an input image f (epsilon) F, one can find a PIFS t (epsilon) T such that the equilibrium distribution of this PIFS is the given image f. Therefore, the input image, f, is encoded into a specification of a PIFS, t. This mapping from F (image space) to T (parameter space of PIFS) defines fractal transformation. Fractal transformation encodes an input image into a relatively small vector which catches the characteristics of the input vector. The internal space T is the parameter space of PIFS. The internal change rule of our system uses a local minima algorithm to encode the input data. The output data of the encoding stage is a specification of a stochastic dynamical system. The quantization rule divides the internal data space T by sample data.

This paper describes the implementation of a non-linear 2D shape abstraction technique. The abstraction procedure systematically simplifies the shape's description using a group of predefined `rewrite rules.' This procedure operates on a new compact and efficient two dimensional shape representation. The abstraction technique generates a detailed scale space representation of the shape being abstracted. This paper provides a method for analyzing this representation to determine the significant shape descriptions. These significant descriptions are used to produce a reduced scale space description of the shape, for use by an object recognition module. The work described in this paper forms a module in a system being developed at Kingston University, to inspect surface mounted technology circuit boards for defects.

Phase shifting methods are greatly used in photomechanics to analyze fringe patterns coming from interferometry, moire, etc. The phase is then determined by modulo 2(pi) and an unwrapping process is needed. An algorithm is presented which avoids most of the inconsistency of the phase field. It can be applied to the relief determination of any shape object. In this paper, an application is performed using the projection of a parallel line grating having a pitch equal to 4 mm. The accuracy is shown to be around 0.1 mm.

In this paper, we present an object recognition technique using scanline information. Objects are scanned using a small number of on/off light sensors. The times when the beams break and unbreak constrain the object's identity, position, and orientation. We study this type of sensor because they are inexpensive, compact, very precise, and insensitive to ambient light, and so well-adapted to manufacturing environments. The information provided by the sensor is very sparse however, consisting of isolated points on the object boundary without normal information. Conventional model-based matching techniques, such as the alignment method, take O(n³) time for this problem. We describe an O(A + n) correspondence algorithm for objects with convex polygonal silhouettes, where n is the silhouette's complexity, and A is the total number of consistent edge pair matches for pairs of scanline points, which is O(n²) in the worst case, but typically O(n). Our algorithm works also for non-convex objects, but the quantity A has a somewhat larger typical value, and a worst case value of O(n³). The object's position and orientation can be easily computed given the correspondence information.

For the image understanding and patten recognitions, it is important to extract invariant features from given images corresponding to various transformations. Once the invariant features are obtained, we can estimate motion parameters and/or categorize objects into equivalent classes based on some criterions. So many techniques to extract invariant features are proposed, and most of them need exact matching between an image before transformation and another image after transformation. But this matching process is not easy to perform. Then we propose a group theoretical method, which does not require a matching process. In this paper, we show the bases of the representation of the perspective projected motion group and those of the spherical projected motion group explicitly.

This paper presents a mathematical digital surface definition. This definition is able to deal with boundary points as well as `inner' points. Namely, it is able to distinguish inner points from boundary points. The definition is intuitive and provides a basis for designing fast algorithms for surface decision, boundary search, and surface tracking problems. This definition is equivalent to Morgenthaler and Rosenfeld's definition on simple closed digital surfaces. The definition can be extended to the problem of defining a digital manifold.

In this paper, we present two theorems: classification theorem and corner point theorem for closed digital surfaces. The classification theorem deals with the categorization of simple surface points and states that there are exactly six different types of simple surface points. On the basis of the classification theorem and Euler formula on planar graph, we have proved the corner point theorem: Any simple closed surface has at least eight corner points, where a corner point of a closed surface is a point in the surface which has exactly three adjacent points in the closed surface. Another result reported in this paper is that any simple closed surface has at least fourteen points.

Given a point q in the presence of polygonal obstacles, the set of points visible from q is the visibility polygon from q. We consider the problem of computing visibility polygon under stair-case visibility (s-visibility, in short). We show that the s-visibility polygon from a point inside a simple orthogonal polygon of n sides can be computed in O(n) time. When the polygon contains holes the algorithm runs in O(n log n) time, which we prove to be optimal by linear time reduction from sorting. We also consider the problem of recognizing stair-case star polygons (s-star, in short) and present an algorithm which recognizes simple s-star polygons in O(n) time.

Abstract not available.

In computer vision, one of the major problems is how to identify an observed object in an image by comparing it to a set of models in a library. The comparison is made using a shape metric which measures the similarity between different shapes. The observed object is classified as the library object with which it minimizes the shape metric. This paper looks at algorithms for efficiently searching a geometric library to identify an observed object in the image. All objects are modeled as points and (epsilon) -congruence is used as the shape metric. Algorithms are presented for searching two classes of geometric libraries, ordered linear libraries and convex linear libraries. The complexity of the algorithms is expressed in terms of the number of objects in the library, the size of the objects, the error in the optimal match, and the geometric structure.

This paper presents a new method of curve-fitting to a set of noisy samples. In the case of fitting a curved line (or a curved surface) to given sample points, it seems natural the curve is decided so as to minimize the mean square of perpendicular distances from the sample points. However, it is difficult to get the optimal curve in the sense of this criterion. In this paper, the perpendicular distance is approximated by local linear approximation of function, and the algorithm for getting the near-optimal curve is proposed. Some simulation results are also shown.

Digital polynomial curves and surfaces arise from the digitization of algebraic surfaces such as lines, parabolas, planes, or paraboloids. It is known that the n-th difference of a digital polynomial curve of degree n is periodic for polynomials that have rational coefficients. In this paper we consider the following problem: Suppose we have a digital curve S whose n-th difference is known to be periodic. When is S a digital rational polynomial curve? As a solution to this problem we state a simple criterion that can be checked in linear time. As a first application of this criterion we describe a linear time algorithm for the recognition of digital straight lines. In comparison to other algorithms, the advantages of the new algorithm are its simplicity, and its ability to actually find the coefficients of the rational polynomial representing the line. We then go on to discuss the applicability of this criterion to the recognition of digital curves and surfaces of arbitrary degree.

Given two simple polygons P and Q in the plane and a translation vector t (epsilon) R², the area-of-overlap function of P and Q is the function A(t) equals Area[P (t + Q)], where t + Q denotes Q translated by t. This function has a number of applications and interpretations. We present a number of mathematical and computational results regarding this function.

Abstract not available.

The paper extends the analyses of ideal discrete straight line segments to estimate the parameters of real images of straight lines obtained by digitizing hand-drawn lines by using commonly available digitizers. Two methods of estimation have been proposed and their inter- relation has been investigated.

A thinning algorithm must `preserve topology,' but in the case of a parallel thinning algorithm it can be hard to prove that it does so. Ronse has given sufficient conditions which can be used to simplify such proofs in the 2D case. By Ronse's results, the fact that a parallel thinning algorithm is topology preserving can be verified by checking only a rather small number of configurations. This paper introduces Ronse-like sufficient conditions for 3D binary images.

A common task in cytogenetic tests is the classification of human chromosomes. Successful separation of touching chromosomes is vital for correct classification. Current systems for automatic chromosome classification are mostly interactive and require human intervention for correct separation of touching chromosomes. Common methods for separation of touching chromosomes tend to fail where ambiguity or incomplete information are involved. We developed a method for the separation of touching objects which encompasses a low-level knowledge about the objects and uses only extracted information. This method is fast and does not depend on the existence of a separating path. Finally the complete process of separation is demonstrated, including cases which are not separable by other methods.

It has been shown recently that discrete, non-decreasing subadditive functions are value functions of pure integer programs and so belong to the class of Gomory functions. Some consequences of this result for discrete metrics are reported in this paper. If a discrete metric in the digital plane is invariant under translations and reflections in the axes, then it is determined by a subadditive function on the first quadrant. If it is also non-decreasing in each coordinate then its values in each finite block are determined by a Gomory function. If the values of the function throughout the first quadrant are determined by the values in a finite block, either by shift-periodicity or by a Hilbert basis, then the subadditive function is determined in the whole of the first quadrant by a unique Gomory function.

Image processing often involves operations using `neighbor' pixels. This paper combines the usual definition of 4 or 8 connected neighbors with image information to produce local neighbor definitions that are signal dependent. These generalized neighbors, G-neighbors, can be used for a variety of image processing tasks. The paper examines their use for detail preserving smoothing and morphology. The simple/local nature of G-neighbor definitions make them ideal for implementation on low-level pixel parallel hardware. A near real-time parallel implementation of the G-neighbor computation, including G-neighbor-based detail preserving smoothing and G-neighbor morphology, is discussed. The paper also provides a qualitative comparison of G-neighbor-based algorithms to previous work.