Abstract. The notion of a cellular complex which is well known in the topology is applied to describe the structure of images. It is shown that the topology of cellular complexes is the only possible topology of finite sets. Under this topology no contradictions or paradoxes arise when defining connected subsets and their boundaries. Ways of encoding images as cellular complexes are discussed. The process of image segmentation is considered as splitting (in the topological sense) a cellular complex into blocks of cells. The notion of a cell list is introduced as a precise and compact data structure for encoding segmented images. Some applications of this data structure to image analysis are demonstrated.

Abstract. A concept for geometry in a locally finite topological space without use of infinitesimals is presented. The topological space under consideration is an abstract cell complex which is a particular case of a T0-space. The concept is in accordance with classical axioms and therefore free of contradictions an paradoxes. Coordinates are introduced independently of a metric, of the straight lines and of the scalar product. These are the topological coordinates. Definitions of a digital half-plane, digital line, collinearity, and convexity are directly based on the notion of topological coordinates. Also the notions of metric, congruence, perimeter, area, volume etc. are considered. The classical notion of continuous mappings is generalized to that of connectivity-preserving mappings which are applicable to locally finite spaces. A new concept of the n-isomorphism is introduced with the aim to quantitatively estimate the deviation of geometric transformations used in computer graphics and image processing from isomorphic transformations.

Abstract. The generally accepted approach to Shape from Shading is based on solving partial differential equations. To avoid the discrepancy between a continuous model on the one hand and digitized images as well as numerical solutions of equations on the other hand, the author suggests a polyhedron as the model of the surface to be reconstructed. The image then consists of plane polygons having each a constant gray value. The problem reduces to finding the heights of the polyhedron’s vertices while minimizing the discrepancy between the given gray values and those computed from the heights. An improved version of the nonlinear least-squares method is applied to get the solution.

Abstract. A new classification of digital curves into boundary curves and visual curves of different thickness is suggested. A fast algorithm for recognizing digital straight line segments in boundary curves is presented. The algorithm is applied to encode the boundaries of homogeneous regions in digitized images. The code is economical and enables an exact reconstruction of the original image.

Abstract. A new method of representing a surface in the 3D space as a single digitally continuous sequence of faces is described. The method is based on topological properties of quasi-manifolds. It is realized as tracing the boundary of a growing set of labeled faces. As the result the surface is encoded as a single sequence of mutually adjacent faces. Each face is encoded by one byte. The code of the surface of a three-dimensional object takes much less memory space then the raster representation of the object. The object may be exactly reconstructed from the code. Surfaces of a genus greater that zero (e.g. that of a torus) may also be encoded by a single continuous sequence. The traversal algorithm recognizes the genus of the surface.

Abstract. The paper details two linear-time algorithms, one for partitioning the boundary of a digital region into digital straight segments, and another for calculating the minimum length polygon within the open boundary of a digital region. Both techniques allow to estimate the length of a digital curve or the perimeter of a digital region due to the known multigrid convergence theorem. The algorithms are compared with respect to their convergence speed and to the number of generated segments.

Abstract. A new method of investigating topological properties of three-dimensional manifolds by means of computers is presented. Manifolds are represented as finite abstract complexes. The method is based on subdividing a given complex into blocks in such a way, that a k-dimensional block be homeomorphic to a k-dimensional topological ball. The block structure is described by the data structure known as "cell list" which is generalized here for the three-dimensional case and for non-Cartesian spaces. The generalized cell list contains a substructure which in the 2D-case is identical with the classical normal form. This structure serves in the 3D-case as a generalization of the normal form for three-dimensional manifolds. Some experimental results are presented.

Abstract. The paper presents an analysis of sources of errors when estimating derivatives of numerical or noisy functions. A method of minimizing the errors is suggested. When being applied to the estimation of the curvature of digital curves, the analysis shows that under the conditions typical for digital image processing the curvature can rarely be estimated with a precision higher than 50%. Ways of overcoming the difficulties are discussed and a new method for estimating the curvature is suggested and investigated as to its precision. The method is based on specifying boundaries of regions in gray value images with sub-pixel precision. The method has an essentially higher precision than the known methods.

Abstract. The paper presents some theorems about interlaced spheres of different dimensions in multidimensional spaces. Two spheres are called interlaced with each other if their intersection is empty, however, one of them crosses each topological ball whose boundary is the other sphere. The spheres S^k and S^m embedded in an n-dimensional space may be interlaced with each other iff k+m+1=n. We describe a method of simulating interlaced spheres in a computer. We demonstrate the connection between the notion of a tunnel in a multidimensional "body", i.e. in a connected subset of a multidimensional space, and that of interlaced spheres. Examples of multidimensional tunnels in four- and five-dimensional spaces are demonstrated.

Abstract. The paper presents an introduction to computer topology with applications to image processing and computer graphics. Basic topological notions such as connectivity, frontier, manifolds, surfaces, combinatorial homeomorphism etc. are recalled and adapted for locally finite topological spaces. The paper describes data structures for explicitly representing classical topological spaces in computers and presents some algorithms for computing topological features of sets. Among them are: boundary tracing (n=2,3), filling of interiors (n=2,3,4), labeling of components, computing of skeletons and others.

Abstract. The paper presents a new method of investigating topological properties of three-dimensional manifolds by means of computers. Manifolds are represented as block complexes. The paper contains definitions and a theorem necessary to transfer some basic knowledge of the classical topology to finite topological spaces. The method is based on subdividing the given set into blocks of cells in such a way, that a k-dimensional block be homeomorphic to a k-dimensional ball. The block structure is described by the data structure known as "cell list" which is generalized here for the multidimensional case. Results of computer experiments are presented.

Abstract. This paper describes a new algorithm of computing the convex hull of a 3-dimensional object. The convex hull generated by this algorithm is an abstract polyhedron being described by a new data structure, the cell list, suggested by one of the authors. The correctness of the algorithm is proved and experimental results are presented.

Abstract. The paper presents some algorithms in digital geometry based on the topology of cell complexes. The paper contains an axiomatic justification of the necessity of using cell complexes in digital geometry. Algorithms for solving the following problems are presented: tracing of curves and surfaces, recognition of digital straight line segments (DSS), segmentation of digital curves into longest DSS, recognition of digital plane segments, computing the curvature of digital curves, filling of interiors of n-dimensional regions (n=2,3,4), labeling of components (n=2,3), computing of skeletons (n=2, 3).

Abstract. The paper presents a new set of axioms of digital topology, which are easily understandable for application developers. They define a class of locally finite (LF) topological spaces. An important property of LF spaces satisfying the axioms is that the neighborhood relation is antisymmetric and transitive. Therefore any connected and non-trivial LF space is isomorphic to an abstract cell complex. The paper demonstrates that in an n-dimensional digital space only those of the (a, b)-adjacencies commonly used in computer imagery have analogs among the LF spaces, in which a and b are different and one of the adjacencies is the "maximal" one, corresponding to 3ⁿ-1 neighbors. Even these (a, b)-adjacencies have important limitations and drawbacks. The most important one is that they are applicable only to binary images. The way of easily using LF spaces in computer imagery on standard orthogonal grids containing only pixels or voxels and no cells of lower dimensions is suggested..