**Prof.
Dr. Vladimir A. Kovalevsky**

(German transcription: Wladimir A. Kovalevski )

Updated on August 31, 2006

Finite Topology as Applied to Image Analysis

**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.

[ Full text] (PDF 654 Kb)
[back to the list of publications]

Digital Geometry Based on the Topology of Abstract Cell Complexes

**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.

[ Full text] (PDF 162 Kb)
[back to the list of publications]

A new approach to Shape from Shading

**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.

[ Full text] (PDF 165 Kb)
[back to the list of publications]

Applications of Digital Straight Segments to Economical Image Encoding

**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.

[ Full text] (PDF 372 Kb)
[back to the list of publications]

A Topological Method of Surface Representation

**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.

[ Full text] (PDF 188 Kb)
[back to the list of publications]

On the Length Estimation of Digital Curves

**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.

[ Full text] (PDF 372 Kb)
[back to the list of publications]

**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.

[ Full text] (PDF 277 Kb) [back to the list of publications]

**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.

[ Full text] (PDF 277 Kb) [back to the list of publications]

**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.

[ Full text] (PDF 184 Kb) [back to the list of publications]

[ Full text] (PDF 216 Kb) [back to the list of publications]

**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.

[ Full text] (PDF 302 Kb) [back to the list of publications]

**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.

[ Full text] (PDF 279 Kb) [back to the list of publications]

**
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.

[ Full text] (PDF 513 Kb) [back to the list of publications]

**
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).

[ Full text] (PDF 269 Kb) [back to the list of publications]

**
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^{n}-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..

[ Full text] (PDF 155 Kb) [back to the list of publications]

last update: August 31, 2006