Geometry of Locally Finite Spaces
by Vladimir A. Kovalevsky
Publishing House Dr. Baerbel Kovalevski, 2008
Reviewed by: Petra Wiederhold (Mexico)
The monograph by Professor Vladimir Kovalevsky presents an original self-contained digital approach to Topology and Geometry for modelling discrete sets, as appearing in Digital Image Processing and Analysis, and in Computer Graphics. The book is based on research of the author within theoretical and algorithmic aspects of digital topology and digital geometry during the last thirty years. The work not only assembles all contributions made by the author into a unique context, where methods and algorithms are consequently founded by and deduced from the theoretical base, but also extends previous investigations, presenting new definitions and theorems and new efficient algorithms for digital image processing and analysis.
The book is clearly written, well structured, and contains numerous good illustrations. In my opinion, it can serve as a textbook for teaching and guiding students, as well as a study base or reference book for researchers. I think, it is of interest for anyone interested in digital topology, digital geometry and computer imagery, but also in other fields where discrete sets are of importance.
The book is an important contribution to the development of a self-contained digital topology and geometry, whose necessity has been recognized by numerous authors. Pioneering proposals for digital topology and geometry were those based on graph theory, for example by the school of Rosenfeld. These models, at their origin, analogously as in the development of a topological space, start with describing local nearness, considering together with each space element, some neighborhood of it. Nevertheless, these models do not provide a topological space which is distinct from the discrete one, where all subsets are open, and which (as a topological space) is totally disconnected. Kovalevsky’s approach is based on the construction of a topological locally finite T0 Alexandroff space, which is related to posets (partially ordered sets) and to the cell complexes from combinatorial topology. This approach has been named by other authors the topological approach to digital topology. Kovalevsky develops geometrical concepts within cell complexes, and finally, the whole theoretical base is consequently applied to develop algorithms for digital image processing and analysis.
The 330-page book is subdivided into 14 chapters. The introductory chapter presents a short retrospect to the origin of the book followed by an overview of the contents and of the pursued aims.
In Chapter 2, Kovalevsky presents an interesting and original axiomatic way to deduce from suppositions "which are natural from the point of view of our intuition and of practical demands" (page 7) that a space suitable for describing topology in discrete sets, has to be a locally finite non-discrete topological space, which turns out to be a T0 Alexandroff space. The construction starts with a locally finite Fréchet space (a set with a local neighborhood system, which not necessarily defines a topological space), named here LF space. Kovalevsky proves that under the imposition of four axioms, where the concept of frontier plays a central role, that the neighborhood system of a LF space, named then ALF space, generates a T0 non-T1 Alexandroff space.
Chapter 3 is devoted to a detailed treatment of basics and topological properties of abstract cell complexes, defined as ALF spaces equipped with a local monotone dimension function. In particular, K-complexes are described, where the dimension function is the poset dimension known from lattice theory. Here we find interesting proposals of definitions of balls and spheres, without reference to any metric or to the Euclidean space, of combinatorial homeomorphisms based on elementary subdivisions of cells, of generalized notions of boundary, and of the orientation of abstract complexes. Most concrete algorithms presented in the book work on a special class of abstract cell complexes named cartesian complexes. Such a cartesian complex corresponds to an Alexandroff space which is homeomorphic to a cartesian product of bounded segments (probably of distinct length in each “coordinate axis”) of the Khalimsky line. This chapter also investigates combinatorial manifolds, and analyzes (m,n)-adjacencies due to Kong.
Chapter 4 considers a new approach to maps among ALF spaces, similar to continuous maps and homeomorphism, which turn out to be isomorphism between complexes. Kovalevsky suggests to use connectedness preserving correspondences (CPMs) which can map one space element to many elements, instead of single-valued functions. He shows that a combinatorial homeomorphism based on elementary subdivisions of space elements uniquely defines a continuous CPM whose inverse is also continuous. Chapter 5 investigates some problems concerning interlaced (interlinked) spheres of different dimensions in n-dimensional cell complexes.
Chapters 6 to 9 are devoted to the development of digital geometry. The author motivates and claims that all geometrical concepts in this book are independent of Euclidean geometry, and that "geometry must be constructed in a topological space which must be completely defined before starting with the construction of geometry. Such a topological space is an abstract cell complex .. " (page 107) . Arithmetics on cell complexes is introduced as on the rationals, and collinearity and convexity are carefully handled by using inequalities and arithmetics within rationals. However, when dealing with rotation as an isometry, Kovalevsky says, "It is easily seen that the only suitable metric is the Euclidean one. It is of course possible to employ Euclidean metric in a space which is not the Euclidean one!" (page 114). Well, at this point I felt "And here, poor fool! with all my lore, I stand, no wiser than before" [F], because, then, geometry has nothing to do with the topological space just constructed before. Actually, any metric would have this effect, because it would generate a Hausdorff topology which definitively cannot be the Alexandroff topology of our complex. Chapter 7 is devoted to digital straight segments (DSS) in two-dimensional complexes, which are consequently considered as one-dimensional complexes, and using rational calculus, and to digital plane patches (DPP) in three-dimensional complexes. (We recall, however, that DSS and DPP were invented in order to estimate geometrical properties of Euclidean objects, under the multi-grid convergence requirement, which has a strong relation to the Euclidean space). Chapter 8 deals with surfaces and manifolds, Chapter 9 with digital circular arcs.
In Chapters 10 to 13, Kovalevsky presents numerous algorithms for digital image processing, analysis, compression, and reconstruction from decodings, based on the modelling of (the domain of) digital images by cell complexes, many of them in full detail, with examples and C++-pseudocodes, others by presenting the main ideas. Data structures for handling the cell complexes in the computer are described, too, as well as ideas for visualization. Some chapters of the book contain problems to be solved that will stimulate further research. Additionally, Chapter 14 presents additional topics for discussion, containing ideas and questions about avoiding the usage of irrational numbers.
In conclusion, Kovalevsky’s book is interesting and important, and I am sure that it will have to be studied seriously. However, I would like to note that it could have been even more integrated in the context of actual research. For example, although deduced or motivated in other ways as by Kovalevsky, parts of the topological approach to topology and geometry, have been independently developed by other authors; for example by Khalimsky, Kopperman, Meyer, Kong, (Julian) Webster, Kronheimer, to mention just a few. Various works, strongly related to the topological approach to digital topology, are not mentioned or cited in Kovalevsky’s book. We have also no mention of Gabor Herman’s book "Geometry of Digital Spaces“ (Birkhäuser Boston, USA, 1998), and of the works of Li Chen, in relation to the modelling of surfaces. The reader of Kovalevsky’s book can get the impression that the topological approach is the unique reasonable one to develop digital topology. Nevertheless, recently several new investigation lines have appeared within the development of digital topology and geometry, based on structures distinct from graphs and topological spaces, for example, on lattices, domains and matroids.
With respect to the importance of Kovalevsky’s book, remember that Computer Science is not the only field interested in such digital models. Topology and Geometry, since their beginnings, have had as one principal aim to describe the earth and universe. At the moment that Newton invented the infinitesimal calculus in order to find good approximations for the calculation of tremendous expressions of sums and differences, continuous models as (locally) Euclidean spaces, began their triumphal procession for describing reality. Today we don’t know if a continuous or a digital space should model the universe; surely each of them describes distinct aspects of reality. On our way that we “may detect the innermost force which binds the world, and guides its course” [F], we are just at the beginning.
[F] J.W.v. Goethe, Faust, First Part of the Tragedy, Scene “Night” (Faust's Monologue), 1808.
Click above to go to the author's web page where you can read the abstract, see the Table of Contents, read about the author, and get ordering information.
Book Reviews Published in
the IAPR Newsletter
Close Range Photogrammetry: Principles, Methods, and Applications
by Luhmann, Robson, Kyle, and Harley
Classification and Learning Using Genetic Algorithms: Applications in Bioinformatics and Web Intelligence
by Bandyopadhyay and Pal
An Approximation Theory Viewpoint
by Cucker and Zhou
Character Recognition Systems—A Guide for Students and Practitioners
by Cheriet, Kharma, Liu, and Suen
Machine Learning in Document Analysis and Recognition
by Marinai and Fujisawa (Editors)
From Gestalt Theory to Image Analysis—A Probabilistic Approach
By Desolneux, Moisan, and Morel
Numerical Recipes: The art of scientific computing, 3rd ed.
by Press, Teukolsky, Vetterling and Flannery
Feature Extraction and Image Processing, 2nd ed.
by Nixon and Aguado
Digital Watermarking and Steganography:
Fundamentals and Techniques
Springer Handbook of Speech Processing
by Benesty, Sondhi, and Huang, eds.
Digital Image Processing: An Algorithmic Introduction Using Java
by Burger and Burge
Bézier and Splines in Image Processing and Machine Vision
by Biswas and Lovell
Practical Algorithms for Image Analysis, 2 ed.
by O’Gorman, Sammon and Seul
The Dissimilarity Representation for Pattern Recognition: Foundations and Applications
by Pekalska and Duin
Handbook of Biometrics
by Jain, Flynn, and Ross (Editors)
Advances in Biometrics –
Sensors, Algorithms, and Systems
by Ratha and Govindaraju, (Editors)
Dynamic Vision for Perception and Control of Motion
by Polanski and Kimmel
Introduction to clustering large and high-dimensional data
The Text Mining Handbook
by Feldman and Sanger
Information Theory, Inference,
and Learning Algorithms
“Foundations and Trends in Computer Graphics and Vision”
Curless, Van Gool, and Szeliski., Editors
Applied Combinatorics on Words
by M. Lothaire
Human Identification Based on Gait
by Nixon, Tan and Chellappar
Mathematics of Digital Images
by Stuart Hogan
Advances in Image and Video Segmentation
Graph-Theoretic Techniques for Web Content Mining
by Schenker, Bunke, Last and Kandel
Handbook of Mathematical Models in Computer Vision
by Paragios, Chen, and Faugeras (Editors)
The Geometry of Information Retrieval
by van Rijsbergen
Biometric Inverse Problems
by Yanushkevich, Stoica, Shmerko and Popel
Correlation Pattern Recognition
by Kumar, Mahalanobis, and Juday
Pattern Recognition 3rd Edition
by Theodoridis and Koutroumbas
Dictionary of Computer Vision and
by R.B. Fisher, et. Al
Kernel Methods for Pattern Analysis
by Shawe-Taylor and Cristianini
Machine Vision Books
CVonline: an overview
The Guide to Biometrics by Bolle, et al
Pattern Recognition Books
Jul. ‘04 [pdf]