Preface
Digital geometry deals with the geometric properties of subsets of digital pictures and with the approximation of geometric properties of objects by making use of the properties of the digital picture subsets that represent the objects. It emerged in the second half of the 20th century with the initiation of research in the fields of computer graphics and digital image analysis. It has its mathematical roots in graph theory and discrete topology; it deals with sets of grid points which are also studied in number theory (since C.F. Gauss) and the geometry of numbers, or with cell complexes (which have been studied in topology since the middle of the 19th century). Studies of gridding techniques, such as those by Gauss, Dirichlet, or Jordan (for measuring the content of a set), also provide historic context for digital geometry. Digitizations on regular grids are also frequently used in numeric computation in science and engineering.
This book uses the term “picture” rather than “image,” because pictures can be the result of drawing, painting, stitching, or other technologies that do not involve imaging processes. The book deals with digital geometry in the context of picture analysis. The medium on which digital pictures reside is called a grid which is a finite set of grid points, grid cells, or other types of discrete elements; the book discusses the geometric and topologic properties of subsets of grids.
Digital geometry can be viewed as a special branch of discrete geometry that deals with graph-theoretical or combinatorial concepts. It can also be viewed as approximate Euclidean geometry on the basis of the fact that picture analysis generally makes use of ideas about Euclidean space. However, digital geometry differs from approximation theory in its use of digitized input data (grid points that are not necessarily on the original curve) rather than sampled input data (sample points that are on the curve but that are not necessarily grid points) and in its focus on understanding the data in digital terms rather than approximating the data with the use of polynomials. Digital geometry also differs from computational geometry, which deals with finite sets of geometric objects in Euclidean space.
The book is intended to be a text that can be used in advanced undergraduate or graduate courses about image analysis in fields such as computer science or engineering. Selections from the material in this book should be sufficient to fill a one-semester course; see the course proposals in the section called “Structure of this Book” for suggested selections. Prerequisites to the use of this book are a basic knowledge of set theory and graph theory and programming experience for the suggested experimental exercises (course assignments). It should be pointed out that some of the exercises are quite difficult; see the references provided in the Commented Bibliography sections at the ends of the chapters for additional information.
The book is also designed to be a comprehensive review of research in digital geometry. The authors have chosen a mathematic viewpoint rather than a practitioner’s viewpoint. However, the fundamentals of digital geometry are also of value to those who work on applications of image analysis or computer graphics, especially if they are concerned with theoretical foundations. Each chapter concludes with exercises and has references to related or more advanced work. When proofs are not given, references to the relevant literature are provided.
This book provides discussions and citations of important mathematic ideas and methodologies that are important to digital geometry and date back, in some cases, to previous centuries or even to ancient times. This information should give students and researchers a better understanding of where the subject fits into a long-term historic process of knowledge acquisition, which began long before their own work or that of their supervisors.
The authors acknowledge comments by (in alphabetical order) Valentin Brimkov, David Coeurjolly, Isabelle Debled-Rennesson, David Eberly, Atsushi Imiya, Gisela Klette, T. Yung Kong, Longin Jan Latecki, Majed Marji, Lyle Noakes, Theo Pavlidis, Christian Ronse, Garry Tee, Klaus Voss, and Jovisa Zuni
. The help of Janice Perrone and Cecilia Lourdes in preparing the manuscript and providing library contacts was very important, and it is appreciated by the authors.
I greatly regret that Professor Rosenfeld did not live to see our book published in final form. I have lost not just a friend, but an outstanding teacher and scientist colleague. I shall miss him.