Mathematical Foundations of Image Processing and Analysis 2 E-Book

Jean-Charles Pinoli

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 673

Veröffentlichungsjahr: 2014

Beschreibung

Mathematical Imaging is currently a rapidly growing field in applied mathematics, with an increasing need for theoretical mathematics.

This book, the second of two volumes, emphasizes the role of mathematics as a rigorous basis for imaging sciences. It provides a comprehensive and convenient overview of the key mathematical concepts, notions, tools and frameworks involved in the various fields of gray-tone and binary image processing and analysis, by proposing a large, but coherent, set of symbols and notations, a complete list of subjects and a detailed bibliography. It establishes a bridge between the pure and applied mathematical disciplines, and the processing and analysis of gray-tone and binary images. It is accessible to readers who have neither extensive mathematical training, nor peer knowledge in Image Processing and Analysis.

It is a self-contained book focusing on the mathematical notions, concepts, operations, structures, and frameworks that are beyond or involved in Image Processing and Analysis. The notations are simplified as far as possible in order to be more explicative and consistent throughout the book and the mathematical aspects are systematically discussed in the image processing and analysis context, through practical examples or concrete illustrations. Conversely, the discussed applicative issues allow the role of mathematics to be highlighted.

Written for a broad audience – students, mathematicians, image processing and analysis specialists, as well as other scientists and practitioners – the author hopes that readers will find their own way of using the book, thus providing a mathematical companion that can help mathematicians become more familiar with image processing and analysis, and likewise, image processing and image analysis scientists, researchers and engineers gain a deeper understanding of mathematical notions and concepts.

Leseprobe

Contents

Preface

Introduction

I.1. Imaging sciences and technologies

I.2. Historical elements on image processing and image analysis

I.3. Mathematical Imaging

I.4. Mathematical aspects of image processing and image analysis

I.5. Mathematical foundations of image processing and image analysis

PART 5 Twelve Main Geometrical Frameworks for Binary Images

21 The Set-Theoretic Framework

21.1. Paradigms

21.2. Mathematical concepts and structures

21.3. Main notions and approaches for IPA

21.4. Main applications for IPA

21.5. Additional comments

22 The Topological Framework

22.1. Paradigms

22.2. Mathematical concepts and structures

22.3. Main notions and approaches for IPA

22.4. Main applicationsto IPA

22.5. Additional comments

23 The Euclidean Geometric Framework

23.1. Paradigms

23.2. Mathematical concepts and structures

23.3. Main notions and approaches for IPA

23.4. Main applications to IPA

23.5. Additional comments

24 The Convex Geometric Framework

24.1. Paradigms

24.2. Mathematical concepts and structures

24.3. Main notions and approaches for IPA

24.4. Main applications to IPA

24.5. Additionalcomments

25 The Morphological Geometric Framework

25.1. Paradigms

25.2. Mathematical concepts and structures

25.3. Mathematicalnotions and approachesfor IPA

25.4. Main notions and approachesfor IPA

25.5. Main applications to IPA

25.6. Additional comments

26 The Geometric and Topological Framework

26.1. Paradigms

26.2. Mathematical concepts and structures

26.3. Mathematical approaches for IPA

26.4. Main applications to IPA

26.5. Additional comments

27 The Measure-Theoretic Geometric Framework

27.1. Paradigms

27.2. Mathematical concepts and structures

27.3. Main approaches for IPA

27.4. Applicationsto IPA

27.5. Additional comments

28 The Integral Geometric Framework

28.1. Paradigms

28.2. Mathematical concepts and structures

28.3. Main approaches for IPA

28.4. Applicationsto IPA

28.5. Additional comments

29 The Differential Geometric Framework

29.1. Paradigms

29.2. Mathematical concepts and structures

29.3. Main approaches for IPA

29.4. Mainapplications for IPA

29.5. Additional comments

30 The Variational Geometric Framework

30.1. Paradigms

30.2. Mathematical concepts and structures

30.3. Mainapprochesfor IPA

30.4. Mainapplicationsfor IPA

30.5. Additional comments

31 The Stochastic Geometric Framework

31.1. Paradigms

31.2. Mathematical concepts and structures

31.3. Main approaches for IPA

31.4. Applications to IPA

31.5. Additional comments

32 The Stereological Framework

32.1. Paradigms

32.2. Mathematical structures

32.3. Main approaches for IPA

32.4. Applications to IPA

32.5. Additional comments

PART 6 Four Specific Geometrical Frameworks for Binary Images

33 The Granulometric Geometric Framework

33.1. Paradigms

33.2. Mathematical concepts and structures

33.3. Mathematical notions and approaches for IPA

33.4. Main notions and approaches for IPA

33.5. Applications to IPA

33.6. Additional comments

34 The Morphometric Geometric Framework

34.1. Paradigms

34.2. Mathematical concepts and structures

34.3. Approaches for image analysis

34.4. Applications to IPA

34.5. Additional comments

35 The Fractal Geometric Framework

35.1. Paradigms

35.2. Mathematical structures

35.3. Main approaches for IPA

35.4. Applications to IPA

35.5. Additional comments

36 The Textural Geometric Framework

36.1. Paradigms

36.2. Mathematical concepts and structures

36.3. Main approaches for IPA

36.4. Applications to IPA

36.5. Additional comments

PART 7 Four ‘Hybrid’ Frameworks for Gray-Tone and Binary Images

37 The Interpolative Framework

37.1. Paradigms

37.2. Mathematical concepts and structures

37.3. Main approaches for IPA

37.4. Main applications for IPA

37.5. Additional comments

38 The Bounded-Variation Framework

38.1. Paradigms

38.2. Mathematical structures

38.3. Main approaches for IPA

38.4. Main applications for IPA

38.5. Additional comments

39 The Level Set Framework

39.1. Paradigms

39.2. Mathematical concepts and structures

39.3. Main approaches for IPA

39.4. Applications to IPA

39.5. Additional comments

40 The Distance-Map Framework

40.1. Paradigms

40.2. Mathematical structures

40.3. Main approaches for IPA

40.4. Applications to IPA

40.5. Additional comments

Concluding Discussion and Perspectives

C1.1. Concluding discussion

C1.2. Short-term perspectives

C1.3. Mid-term perspectives

C1.4. Color-tone images

Appendices

Tables of Notations and Symbols

Table of Acronyms

Table of Latin Phrases

Bibliography

Index of Authors

Index of Subjects

To Blandine, Flora and Pierre-CharlesBlandine, Flora and Pierre-Charles

First published 2014 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd

27–37 St George’s Road

London SW19 4EU

UK

www.iste.co.uk

John Wiley & Sons, Inc.

111 River Street

Hoboken, NJ 07030

USA

www.wiley.com

©ISTE Ltd 2014

The rights of Jean-Charles Pinoli to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2014939771

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN 978-1-84821-748-5

Preface

The era of imaging sciences and technologies

The important place of images in the modern world is undeniable. They are intimately integrated into our organic life (“visual perception” is particularly well developed in human beings). They are frequently involved in our daily life (magazines, newspapers, telephones, televisions and video games, etc.), personal life (medical imaging, biological imaging and photographs, etc.), professional life (plant control, office automation, remote monitoring, scanners and video conferencing), etc. They are not confined to the various technological sectors, but they are vectors of observations and investigations of matter at very small scales (electron microscopes and scanning probe microscopes, etc.), or of the universe at very large scales (telescopes and space probes, etc.), sometimes leading major scientific discoveries. Mankind is now able to see images of other worlds without going there (e.g. distant planets, stars and galaxies, or the surface terrain of the Earth) and worlds within (e.g. human organs, geological imaging, or atomic and molecular structures at the nanoscale level). From a technological point of view, this importance is enhanced by the performance of the systems of investigation by imaging and the powers of calculation of computers, which expanded considerably in the second half of the 20th Century, and that are still progressing, with both hardware and software advances.

The scope of Imaging Sciences and Technologies is broad and multidisciplinary. It involves all the theories, methods, techniques, devices, equipment, applications, software and systems, etc. relating to images in order to obtain information and qualitative and/or quantitative knowledge, in order to investigate, analyze, measure, understand, interpret and finally to decide. The range of applications is broad in contemporary sciences and technologies. The scientific and technical disciplines that are concerned or that use it are numerous: Astronomy, Biology, Electronics, Metallurgy, Geology, Medicine, Neurology, Optics, Physics, Perceptual Psychology and Robotics, etc. and others too numerous to name, and of course Mathematics, with their strengths and their limitations.

Mathematical Imaging

When dealing with image processing and analysis, the most surprising point at first glance, not only for many engineers or scientists, but also for academics and mathematicians, is the key role of Mathematics. Although the image processing and analysis field was historically largely applied and still partly remains so, it is not limited to an engineering field. Indeed, it has attracted the attention of many scientists during the past three decades, and the fundamentals that it requires are becoming strong and of high-level, in particular from a mathematical viewpoint.

The so-called Mathematical Imaging is currently a rapidly growing field in applied Mathematics, with an increasing need for theoretical Mathematics. More and more mathematicians are interested in carrying out their research into image processing and analysis. In fact, image processing and analysis have created tremendous opportunities for Mathematics and mathematicians. The contemporary field of image processing and analysis is very attractive because it has very interesting application issues, is closely related to the fascinating Human Vision and requires advanced mathematical bases.

Historically, input from mathematicians has had a fundamental impact on many scientific, technological and engineering disciplines. When accurate, robust, stable and efficient models and tools were required in more traditional areas of science and technology, Mathematics often played an important role in helping to supply them. No doubt, the same will be true in the case of imaging sciences. Mathematical Imaging has become a critical, enthusiastic and even exciting, but still in-progress, branch in contemporary sciences.

Author claims

Nowadays, there exist several good books or monographs, each dealing with one or some mathematical fundamentals for image processing and analysis purposes, but a textbook completely focused on the mathematical foundations of image processing and analysis does not currently exist.

The proposed textbook is intended:

– to fill a niche by providing a self-contained, (relatively) complete and informative review of the mathematical foundations of image processing and analysis;

– to emphasize with an (as far as possible) accessible style, the role of Mathematics as a rigorous basis for imaging sciences;

– to be a review of mathematics that are necessary for imaging sciences, often existing only in the (generally hidden) background for non-mathematicians;

– to help mathematicians to become more familiar with image processing and analysis;

– to be a mathematical companion for image processing and analysis students, scientists, researchers, scholars, engineers and even practitioners.

Textbook aims

This textbook aims to provide a comprehensive and convenient overview of the key mathematical concepts, notions, tools and frameworks involved in the various fields of gray-tone and binary image processing and analysis. It establishes a bridge between pure and applied mathematical disciplines, and the processing and analysis of gray-tone and binary images. It is accessible to readers who have neither extensive mathematical training, nor peer knowledge in image processing and analysis. The notations will be simplified as much as possible in order to be more explicative and consistent throughout the textbook. The explanations provided will be sufficiently accurate for one such statement. The mathematical aspects will systematically be discussed in the image processing and analysis context, through practical examples or concrete illustrations. Conversely, the discussed applicative issues allow the role held by Mathematics to be highlighted.

The author would greatly appreciate if the present textbook could help mathematicians to become more familiar with image processing and analysis, and likewise, image processing and image analysis scientists and engineers to get a better understanding of mathematical notions and concepts.

The proposed book is not:

– an introductory book, treatise, or textbook on image processing and analysis;

– a long textbook with extensive treatments on Mathematical Imaging;

– a monograph or a textbook on some mathematical aspects for image processing and analysis;

– a mathematical book with too heavy a jargon and detailed technical developments or complete proofs.

The proposed book is:

– a two-volume, self-contained textbook on the mathematical notions, concepts, operations, structures and frameworks that constitute the foundations of image processing and analysis, emphasizing the role of Mathematics as a rigorous basis for imaging sciences.

Organization of the textbook

This textbook is organized into an introduction, a concluding discussion with perspectives, a textbody, appendices with two tables and three indexes and a detailed bibliography.

The textbook is split over two volumes, made up of 7 main parts divided into 40 chapters and sub-divided into 207 sections.

Part 1 entitled “An Overview of Image Processing and Analysis (IPA)” presents the basic terms and notions for gray-tone and binary imaging (Chapters 1 and 3, respectively), a first overview dealing with the main image processing and image analysis fields and subfields for gray-tone images (Chapter 2), and a second overview dealing with the main image processing and image analysis fields and subfields for binary images (Chapter 4). Then, the key notions and concepts for image processing and analysis are exposed, followed by comments on how and why mathematical imaging frameworks are presented in this textbook (Chapters 5 and 6, respectively).

Part 2 entitled “Basic Mathematical Reminders for Gray-Tone and Binary Image Processing and Analysis” is devoted to basic elements in Mathematics, mainly in set theory, algebra, topology and functional analysis, that can possibly be skipped by the reader well-versed in Mathematics.

Part 3 entitled “The Main Mathematical Notions for the Spatial and Tonal Domains” focuses on the first-level mathematical notions for the spatial and tonal domains (Chapters 9 and 10).

Parts 4, 5, 6 and 7 present the functional and geometrical mathematical frameworks for image processing and analysis, and comprise a total of 30 chapters.

Part 4 entitled “Ten Main Functional Frameworks for Gray Tone Images” focuses on the main mathematical (functional) frameworks for gray-tone image processing and analysis, detailed in 10 chapters.

Part 5 and 6, entitled “Twelve Main Geometrical Frameworks for Binary Images” and “Four Specific Geometrical Frameworks for Binary Images”, respectively, focus on the main mathematical (geometric) frameworks for binary image processing and analysis, detailed in 12 chapters and 4 chapters, respectively.

Part 7, entitled “Four 'Hybrid' Frameworks for Gray-Tone and Binary Images”, is a further extension and supplementation focusing in 4 chapters on four mixed functional and geometric mathematical frameworks for gray-tone or/and binary images.

The textbook will be organized following two main entries:

–“The Imaging entry”: from an image processing and analysis viewpoint, the straightforward way to read this textbook is to start from Part 1 and then Part 3.

–“The Mathematics entry”: the reading of Part 2 is not required. The reader can refer to it if necessary. Part 4 is primarily based on the concepts and tools of functional analysis. Parts 5 and 6 rely primarily on the concepts and tools of geometry. The reading of Parts 5 and 6 are (almost) independent. Part 7 is mathematically advanced and needs the readings of Parts 4, 5 and 6.

The mathematical frameworks for image processing or analysis purposes are presented in separate chapters following a “generic organization form”, with four sections appearing successively: (1) paradigms, (2) mathematical notions and structures, (3) main approaches for image processing or analysis and (4) main applications to image processing or analysis.

Most chapters end with a section entitled “additional comments”, in which readers will find some historical comments, several main references: introductory or overview journal articles, seminal and historical articles, textbooks and monographs, bibliographic notes and additional readings, suggested further topics and recommended readings, and finally (often) some references on applications to image processing and analysis, all with short comments.

Important lists or tables are presented in the appendices as follows:

– a detailed and extended appendix on notation is organized in 23 tables of notations and symbols; special effort has been put into alleviating the notations and symbols, making them easier to read and understand, promoting genericity and declination, and avoiding confusion and inconsistencies;

– a table of acronyms;

– a table of Latin phrases;

– a complete list of referenced authors, with a few pieces of information (dates of birth and death, nationality, main discipline(s) of expertise). This list is of more cultural interest and will allow the readers to locate in time and space the cited scientists;

– a detailed and extended list of subjects and keyterms; this list will often be a real entry for any reader, who wants to search the meaning and use of a particular subject or keyterm.

A large bibliography is also proposed, including as far as possible historical references and seminal papers, current reviews, and cornerstone published works.

Intended audiences

This textbook is written for a broad audience: students, mathematicians, image processing and analysis specialists, and even for other scientists and practitioners.

The author hopes that the individual reader should come up with his or her own comfortable usage of the textbook.

Students

This textbook is primarily intended for 3rd/4th year undergraduate, graduate, postgraduate and doctorate students in image processing and analysis, and in Mathematics who are interested in the mathematical foundations of image processing and analysis. These students will be provided with a comprehensive and convenient summary of the mathematical foundations, that they should use or refer to throughout undergraduate, Master of Science (MSc), Master of Engineering (MEng), or PhD courses.

Mathematicians

This textbook is also intended for applied, but also 'pure' mathematicians. There are a still growing number of mathematicians in applied and computational Mathematics, but also in pure Mathematics, who have either little or no previous involvement in image processing and image analysis, but wish to broaden their own horizon of view, scope of knowledge, and fields of application. The author recommends that they follow the proposed logical structure of the current textbook. Those readers will find, on the one hand, an overview of image processing and analysis fields and subfields, and, on the other hand, a review of the main mathematical frameworks involved in imaging sciences.

Image processing and analysis specialists

This textbook will serve as a two-volume textbook for practitioners, researchers lecturers or scholars in image processing and analysis that aims at overviewing the mathematical foundations of image processing and analysis. It is hoped that this textbook will become the useful mathematical companion to anybody reading image processing and analysis books or articles, writing research or technical articles, preparing a lecture or a course, or for teaching.

Other scientists and practitioners

As secondary audiences, this textbook should also be of interest to many scientists of various disciplines too numerous to name who make use of images and are thus faced with image processing and analysis problems and tools. They may have an occasional need of this textbook for a better understanding of a mathematical notion.

The textbook is also intended for research and development, or industrial engineers, or project leaders, scientists, technical or scientific directors, wishing to discover or improve their knowledge of the scientific aspects of image processing and analysis, and the role of Mathematics in image processing and analysis.

Underlying matter

This textbook has been written starting from two scientific articles published in French by the Scientific and Technical Encyclopedia “Techniques de l'Ingénieur” in 2012:

– “Mathématiques pour le traitement et l'analyse d'images à tons de gris”, Techniques de l'Ingénieur, [E6610], 25 pages, February 2012 (Jean-Charles Pinoli) [PIN 12b];

– “Mathématiques pour le traitement et l'analyse d'images binaires”, Techniques de l'Ingénieur, [E6612], 25 pages, September 2012 (Jean-Charles Pinoli) [PIN 12c];

– Several extensions have been presented and new developments included (e.g. Parts 2, 6 and 7). Four unpublished chapters have been added, together with five important detailed and commented lists or tables: 23 tables of notations and symbols, a table of Latin phrases, a list of acronyms, a list of referenced authors and a list of subjects.

This textbook is also an outgrowth of PhD, Master of Engineering and Master of Science courses, which have been given for many years by the author.

Notes for the textbook reading

“Italics” will be used to mark a passage in a foreign language, including in particular Latin phrases, that are briefly defined and explained in the Table of Latin Phrases in Appendices.

Key terms and subject matters will appear in “slanted bold” in the body of the textbook. They are collected in the Appendices in the List of Subjects.

Quotation marks or inverted commas (informally referred to as quotes) are punctuation marks surrounding a word or phrase with a specific meaning or use. Single quotes ‘…’ will be used to indicate a different meaning, or a direct, rough or even abusive speech. Double quotes “…” will emphasize that an instance of a word refers to the word itself rather than its associated concept. The so-called “use-mention distinction” is necessary to make a clear distinction between using a word or phrase and mentioning it.

As a rule, a whole publication (e.g. a book title) would be both slanted and double quoted, while a citation will be both italicized and double quoted.

Jean-Charles PinoliJune , 2014

Introduction

I.1. Imaging sciences and technologies

The last few decades have largely been the dawning years of the era of Imaging Sciences and Technologies, which is a multidisciplinary field concerned with the (by alphabetical order) acquisition, analysis, collection, display, duplication, generation, modeling, modification, processing, reconstruction, recording, rendering, representation, simulation, synthesis and visualization, etc., of images.

From a computer science viewpoint, there are two dual fields: (1) Computer Vision, which tries to reconstruct the 3D world from observed 2D images, and (2) Computer Graphics, which pursues the opposite direction by designing suitable 2D scene images to simulate our 3D world. Image processing is the crucial middle way connecting the two. Image synthesis in the computer graphics field being the dual of image analysis treated in computer vision.

As the human visual system has been achieved by mother nature, there is nowadays a tremendous need for developing so-called Artificial Vision systems. Such systems consist of four more or less independent stages: (1) image acquisition, (2) image processing, (3) image analysis and (4) image interpretation.

“Image acquisition” mainly focuses on the physical and technological mechanisms and systems by which imaging devices generate spatial observations, but it also involves mathematical and computational models and methods implemented on computers, integrated into and/or associated to such imaging systems. The term “image processing”, is usually understood as all kinds of operations or transformations performed onto images (or sequences of images), in order to increase their quality, restore their original content, emphasize some particular aspects of the information content, optimize their transmission, or perform radiometric and/or spatial analysis. The term “image analysis” is usually understood as all kinds of operations or operators performed on images (or sequences of images), in order to extract qualitative and/or quantitative information content, perform various measurements, and apply statistical analysis. All these methods and techniques have of course a wide range of applications in our daily world: biological imaging, industrial vision, materials imaging, medical imaging, multimedia applications, quality control, satellite imaging, traffic control and so on. “Image interpretation” is roughly speaking, the inverse stage of image acquisition. The latter deals with the 2D or 3D imaging of spatial structures that are investigated. The former, however, aims at understanding the observed 3D world from generally 2D images.

I.2. Historical elements on image processing and image analysis

The first digital pictures dated back to the early 1920s [MCF 72]. Then, practical works and more theoretical research mainly focused on picture coding and compression for transmission applications, and then for television image signals (see, e.g. [MER 34, GOL 51]) [SCH 67].

Historically, the “Image Processing and Analysis (IPA)” field has emerged early from the 1950s (see, e.g. [KOV 55] or [KIR 57]), and mainly from the 1960s (see, e.g. [GRA 67, SCH 67, ROS 69a, ROS 69b, ROS 73c] and many references therein), in works carried out and published by researchers and engineers belonging to several academic and professional communities, and from different scientific trainings, mainly “Applied Physics” (Electrical Engineering and Signal Processing), “Computer Sciences” (Computer Vision, Pattern Recognition and Artificial Intelligence), and “Mathematics” (mainly, Statistics, Applied Functional Analysis and (generally discrete) Geometry and Topology).

The first textbook entitled “Picture Processing by Computer” [ROS 69a] was written in 1969 by Azriel Rosenfeld, a mathematician, who was then regarded as a pioneer, and even “the” pioneer of image processing and image analysis, and as a leading researcher in the world in the field of computer image processing and analysis. Another book appeared soon after, with a similar title “Computer Techniques in Image Processing” [AND 72], by Harry C. Andrews, an applied physicist and computer scientist.

Several other pioneering textbooks were published later in the 1970s and early 1980s, mainly: “Digital Image Restoration” (1977) [AND 77] by Harry C. Andrews, and Bobby R. Hunt, applied physicists and computer scientists, “Digital Image Processing” (1977) [GON 87; 1st ed., 1977], by Rafael C. Gonzalez and Paul Wintz, electrical engineering specialists, “Digital Image Processing” (1978) [PRA 07; 1st ed., 1978] by William K. Pratt, an applied physicist, “A Computational Investigation into the Human Representation and Processing of Visual Information” (1982) [MAR 82] by David Marr, a computer scientist, “Algorithms for Graphics and Image Processing” (1982) [PAV 12; 1st ed., 1982] by Theo Pavlidis, a computer scientist, “Image Analysis and Mathematical Morphology” (1982) [SER 82] by Jean Serra, an applied mathematician.

Concerning technical, engineering and scientific journals, deserving of special mention are two journals that early on published papers on picture processing. One of these journals, the “Proceedings of the IRE” (the journal of the “Institute of Radio Engineers”), was founded in 1913 and was renamed in 1963 as the “Proceedings of the IEEE” (the journal of the “Institute of Electrical and Electronics Engineers (IEEE)”), when the “American Institute of Electrical Engineers (AIEE)” and the “Institute of Radio Engineers (IRE)” merged to form the “Institute of Electrical and Electronic Engineers (IEEE)”). The other journal, “Pattern Recognition” (the journal of the “Pattern Recognition Society”), was founded in 1968. In this connection, The Journal of the ACM (the journal of the Association for Computing Machinery (ACM), established in 1954) should also be mentioned, which published several papers on image processing and analysis in the 1960s and 1970s. The series of volumes on “Machine Intelligence”, initiated in 1967, and of the journal “Artificial Intelligence”, founded in 1970, should also be noted.

The first scientific journals dedicated to, completely or partially, image processing and analysis were published during the 1970s (e.g. “Computer Graphics, Vision and Image Processing” in 1972 and “IEEE Transactions on Pattern Analysis and Machine Intelligence” in 1979). After that period of pioneers, the field of image processing and analysis started its growth from about the middle of the 1980s. In Europe, “Acta Stereologica” was founded in 1982 by the “International Society for Stereology” and was renamed “Image Analysis and Stereology” in 1999. Many papers dealing with image analysis were and still are currently published.

In addition, significant contributions to image processing and even more to image analysis were also made by researchers or practitioners from other disciplines, such as for example the cytometrists, geologists, metallographs and mineralogists, just to name a few (e.g. [COS 86, WEI 81, RIG 89]).

The first international scientific conferences focusing only on image processing and analysis appeared at end of the 1980s (i.e. “International Conference on Computer Vision (ICCV)” in 1987) and at the beginning of the 1990s (i.e. “International Conference on Image Processing (ICIP)” in 1994).

The first mathematical imaging journal explicitly on both Mathematics and Image Processing and Analysis only appeared in the early 1990s (i.e. “Journal of Mathematical Imaging and Vision” in 1992). Very recently, the SIAM society (“Society for Industrial and Applied Mathematics”) published its first mathematical journal in Mathematical Imaging (i.e. “SIAM Journal on Imaging Sciences”) in 2008.

However, although presented in this short introductory, historical discussion under the joint name “Image Processing and Image Analysis”, it is important to note that on one side “Image Processing”, and on the other side “Image Analysis” have been addressed by researchers and engineers generally from different scientific communities. This is still often the case even if an interpenetration of the two fields is in progress. Earlier, some mathematicians focused on Image Analysis in the 1960s and 1970s. More mathematicians became interested in Image Processing from the 1980s, and even more in the 1990s. One of the main scientific reasons, if not the most important, is that image analysis required knowledge of geometry and topology, that were and still are often too poorly taught in MSc courses, and therefore are less prevalent than those most used in mathematical analysis, especially due to the strong interest in Mathematical Physics in general, during the 1980s, and in particular for image problem modeling using partial differential equations and their numerical resolutions. The following statement then appears as a logical consequence:

There exist nowadays a (relatively) large number of books dealing with image processing, but mainly on a or some particular field(s), and often in the form of edited books rather than monographs. On the contrary, only a small number of books are dealing with image analysis.

I.3. Mathematical Imaging

Early mathematical contributions and/or reviews were authored by researchers of the Electrical Engineering and Signal Processing community (see, e.g. [JAI 81]), and Discrete Geometry community (see, e.g. [ROS 66, GRA 71]).

Several areas of Mathematics have contributed to and in fact increasingly contribute to essential progress of Image Processing and Image Analysis. Mathematics provide the fundamentals for image processing and image analysis frameworks, operations, models, techniques and methods.

However:

– there is no single “mathematical theory of image processing and image analysis”. Quite often, different approaches exist to model the same problem, using notions coming from different disciplines of Mathematics. Those disciplines underlying and/or involved in Image Processing and Analysis range from Algebra to Analysis, from Set Theory and Topology to Geometry, from Functional Analysis to Calculus of Variations, from Probability Theory to Statistics, and so on;

– the ties between Image Sciences and Mathematics are still not strong enough. International conferences are very often organized by a specific scientific community. Very few symposiums are organized to promote interaction between researchers of image sciences and mathematicians.

The term “Mathematical Imaging” is emerging, but remains too specialized for a wide range of scholars, researchers, scientists and engineers, as well as for theoreticians and practioners.

I.4. Mathematical aspects of image processing and image analysis

Mathematics have a crucial role to play in Image Processing and Image Analysis, since the radiometric images can be regarded as numerical functions, spatially defined on pixels and with values of the so-called intensities, known as gray-tones in the image processing community. This includes, of course, applied Mathematics (such as numerical analysis and matrix analysis, since gray-tone images are often digital images, and are encoded in the form of matrices in digital imaging softwares), but also a priori less obviously mathematical disciplines called fundamentals or even “pures”. Hence, almost paradoxically, pure Mathematics thus operate in practical areas where they were not expected in view of their application-oriented type, as it seems at first sight. Algebra, which provides the terms for the definition of the basic operations for combining images (i.e. the addition and the subtraction of two images: what to do without these two operations?), or Topology, the theoretic mathematical discipline by excellence, which is essential to clearly define what is a connected region and how to address the notion of a contour. Differential Calculus, for the study of the local variations of an image, and Integral Calculus, for the study of the average behavior of an image, are two strong pillars in image processing and analysis, allowing the introduction of useful differential operators (e.g. gradient and Laplacian for the detection of transitions) and integral operators (e.g. Fourier transform and wavelet transform for frequency and multiscale analysis, respectively). In fact, the mathematical discipline of reference is Functional Analysis, dedicated to the study of functions, since images to be processed and analyzed will be represented in spaces of functions. Moreover, the Calculus of Variations that enables us to relevantly formalize some problems of image restoration and image segmentation. Finally, the Theory of Probabilities is of great interest, since it provides random models for spatial structures, patterns or textures, and for unwanted phenomena such as random perturbations (e.g. noises or damage, etc.).

Binary images mostly come from prior processings on gray-tone images. They consist of functions defined spatially on pixels and taking only two values, namely: 0 and 1. The value 1 represents the informative pixels and 0 the other pixels. As for gray-tone images, Mathematics are important, because binary images will be considered to be composed of spatial objects (in a broad sense). It is thus especially Geometry, a discipline (in fact a set of disciplines) too often forgotten in the current higher education, which plays a central role in binary imaging. Remarkably, binary imaging has allowed a return to the “hit parade” of many “old” results (e.g. from the 19th Century: Cauchy and Crofton's theorems for the measurement of the perimeter of an object), or even medieval (from the 16th Century: Cavalieri's principle on the measurement of the volume of a solid object by “cutting” it into parallel small slices). It is based on two pillars: Differential Geometry (19th Century: i.e. the study of local variations of the contours of an object) and Integral Geometry (19th and 20th Centuries: i.e. the study of the measures of the contour or the content of an object). Binary imaging promoted the emergence in the second half of the 20th Century of specific mathematical branches, such as Stereology (i.e. the study of the transition of spatial measures in one or two dimension(s) to the third dimension) or Stochastic Geometry (i.e. the study of spatial distributions of objects from a probabilistic point of view). The Theory of Sets provides the foundations on which the other mathematical disciplines are based and is also of great interest for computer processing. Convex Geometry (e.g. Steiner's formula stated in the middle of the 18th Century, or the Minkowski addition in the early 20th Century) also found a new youth as a founding basis for mathematical morphology in the second half of the 20th Century (enabling the definition of the concepts of erosion and dilation of objects).

Topology, Algebra and Measure Theory associated with Geometry gave rise to new branches of Mathematics (Topologic Geometry, Algebraic Geometry, Geometric Measure Theory) during the 20th Century. These disciplines have a strong interest in binary imaging, especially for the characterization of objects (e.g. connectedness, contour orientation, Descartes-Euler-Poincar6's number, as well as volumes, areas or lengths). Fractal Geometry was also (re)developed to the taste of the day in the last decades of the 20th Century, with a passion, even a fascination, still intact nowadays, although the seminal works were published more than a century ago (the early works on space-filling curves date back to the end of the 19th Century). Finally, it should be noted that the (re)emergence of “Discrete Geometry” (appeared as early as the 16th Century) and “Discrete Topology” (discrete spaces were already studied during the third decade of the 20th Century) resulted in Imaging Sciences by the neologism of “Digital Geometry.

I.5. Mathematical foundations of image processing and image analysis

In the past five decades, mathematicians have been able to make substantial contributions in all these areas of Mathematical Imaging, mainly for image processing and image analysis.

This textbook will focus in a two-volume, self-contained monograph on the mathematical foundations of image processing and analysis that are currently in sparse state in a large number of references, by proposing a large, but coherent set of symbols and notations, a complete list of subjects and a detailed bibliography.

PART 5

Twelve Main Geometrical Frameworks for Binary Images

21

The Set-Theoretic Framework

The set-theoretic framework is not really a geometric framework, but it is of key importance for studying the stricto sensu geometrical frameworks that will be useful for Mathematical Imaging.

21.1. Paradigms

In the set-theoretic framework, a binary image is regarded as made up of distinct subsets of pixels with the same value, that is to say either 0 or 1 (or, either 0 or for multinary imaging). Each subset of pixels is taken as own entity (i.e. considered as a whole) and thus becomes a (geometric) object that will be studied with the concepts and tools of Set Theory.

21.2. Mathematical concepts and structures

The reader is invited to refer to Chapter 7 “Basic Reminders in Set Theory” for basic elements on Set Theory.

21.2.1.Mathematical disciplines

The basic mathematical discipline of reference is the theory of sets, or for short Set Theory [RUB 67, DEV 93, BOU 04c]. The notion of set is fundamental in modern mathematics, because most mathematical entities (numbers, relations, operations, functions, etc.) are defined in terms of sets.

21.3. Main notions and approaches for IPA

21.3.1.Pixels and objects

In the set-theoretic framework, the objects will be represented by sets and subsets for mathematical imaging purpose.

An object, denoted X, Y, Z, . . . is a subset of the spatial support D or of the spatial domain (see section 9.3.1).

A pixel, denoted as x, y, z . . . is an element of an object (‘foreground pixel’) or not (‘background pixel’) (see section 1.2).

21.3.2.Pixel and object separation

From a set-theoretic viewpoint, the pixel separation is a very poor concept. Two pixels x and y are separated iff they are distinct, i.e.:

[21.1]

The set separation of two objects X and Y in the spatial domain is expressed by their disjunction, that is to say:

[21.2]

where Ø denotes the empty set.

Two such objects X and Y are thus said to be disjoint, and called disjoint objects. If the two objects have a non-empty intersection, then it is impossible to identify them within the single set-theoretic framework.

21.3.3.Local finiteness

In Mathematical Imaging, a family of objects is supposed to be locally finite in order to be tractable. That means that the number of objects belonging to is finite on any bounded subset (see section 8.5.3) of [MUN 00]:

[21.3]

In practice, the number of objects within the spatial support D is finite, since D is bounded. Separate objects can be treated either individually, or by cluster (e.g. within a particular part of the spatial support) or by class (i.e. those of the same type).

21.3.4.Set transformations

A set transformation is said to be invertible on the power set or on a particular class of objects in if its inverse transformation exists [SER 82, COS 86]:

[21.4]

A set transformation is said to be increasing (resp., strictly increasing) on or on a particular class of objects in if [SER 82, COS 86]:

[21.5a]

[21.5b]

On contrary, a set transformation is said to be decreasing (resp., strictly decreasing) on or on a particular class of objects in if [SER 82, COS 86]:

[21.6a]

[21.6b]

A set transformation is said to be extensive (resp., strictly extensive) on or on a particular class of objects in if [SER 82, COS 86]:

[21.7a]

[21.7b]

On contrary, a set transformation is said to be anti-extensive (resp., strictly anti-extensive) on or on a particular class of objects if:

[21.8a]

[21.8b]

A set transformation is said to be idempotent on or on a particular class of objects if [SER 82, COS 86]:

[21.9]

21.4. Main applications for IPA

21.4.1.Object partition and object components

The set components of an object X are its constituting separable (i.e. disjoint) subsets that constitute a family of sub-objects of X, where is an index set (see section 7.6), finite in practice (i.e. card < ∞), whose union is the object X itself, that is to say a partition of the object X:

[21.10]

where the notation denotes the disjoint set union (see equation [7.11]).

Roughly speaking, a partition of an object X is a ‘division’ of X into non-overlapping and non-empty parts, i.e. covers all of X (see section 7.7), these parts being collectively exhaustive and mutually exclusive (i.e. pairwise disjoint).

An object not separable into two disjoint subsets thus corresponds commonly speaking to a ‘one-piece object’.

21.4.2.Set-theoretic separation of objects and object removal

The first application issue is the set-theoretic separation of objects in the spatial domain relative to their context (see section 3.1), or for short object separation. The context of a family of objects in a binary image is defined as being the complementary set to their union relative to the spatial support D in , namely:

[21.11]

The removal of a family of set-theoretically-separated objects , called object removal for short, is expressed simply as follows:

[21.12]

where D0 is the set of background-pixels (i.e. the 0-valued pixels within the spatial support D) (see section 1.2).

Set-theoretically, the object separation is a poor concept and coincides with the distinctness (i.e. , which is not sufficient for mathematical imaging purpose.

21.4.3.Counting of separate objects

Counting of separate objects within a family of objects is restricted in practice to the number of distinct objects, namely:

[21.13]

where s indexes the distinct objects.

In Mathematical Imaging, a family of objects is supposed to be locally finite in order to be tractable (see section 21.3.3). It means that the number of objects belonging to is finite on any bounded subset of , in particular within the spatial support D.

21.4.4.Spatial supports border effects

The most annoying constraint comes from objects that partially overlap the border of the spatial support D (i.e. its topological boundary ∂D), which must be considered in order to avoid as far as possible the border effects that lead to errors or biases.

21.5. Additional comments

Historical comments and references

Set-theoretical tools in IPA date back to the beginning of the use of computers in those fields, see e.g. [UNG 59].

Bibliographic notes and additional readings

There are no references dealing only with classical Set Theory as applied to Image Processing and Analysis. A large involvement of set-theoretical notions was next performed in the 1960s for setting up the so-called Discrete Geometry (see [KLE 04b] and references therein), generally in close relation with Topology (see Chapter 22, “The Topological Framework”), and in the 1970s by [SER 82] when developing the so-called Mathematical Morphology (see Chapter 25, “The Morphological Geometric Framework”).

Further topics and readings

Fuzzy Set Theory [ZAD 65, KLA 65] and its applications are treated in, e.g. [ZIM 01].

Some references on applications to IPA

For fuzzy image processing and analysis see, e.g. [KER 00] and [CHA 10].

22

The Topological Framework

The topological framework is not really a geometric framework, but it is of key importance in addition to Set Theory (see Chapter 21 “The Set-Theoretic Framework”) for studying the stricto sensu geometrical frameworks that will be useful for Mathematical Imaging.

22.1. Paradigms

In the topological framework, a binary image is regarded as made up of distinct subsets of pixels with the same value, that is to say either 0 or 1 (or, either 0 or for multinary imaging). Each subset of pixels is taken as its own entity (i.e. considered as a whole) and thus becomes a (geometric) object that will be studied with the concepts and tools of Topology.

22.2. Mathematical concepts and structures

The reader is invited to refer to Chapter 8 “Basic Reminders in Topology and Functional Analysis” for basic elements on Topology.

22.2.1.Mathematical disciplines

The basic mathematical discipline is Topology [CHO 66, KEL 75, STE 78, JÄN 84], historically developed from concepts issued from Geometry and Set Theory. It deals with abstract ‘spatial’ properties, primarily for continuity based on the central concept of neighborhood (see section 8.2.1).

22.2.2.Special classes of subsets of

The class of open subsets of is denoted as , or as for short. The class of closed subsets of is denoted as , or as for short. The class of all compact subsets of is denoted as , or as for short. Such classes are called hyperspaces in Topology [NAD 78], and topologies on such classes are called hypertopologies [NAI 03b]. These topologies are all of the hit-or-miss type, built from various modifications of the historical Vietoris topology [VIE 21, VIE 22]. They can be introduced by describing their topological bases (see section 8.2.4).

For a set and designate the collections of subsets of that hit S and miss S, respectively [MOL 05; p. 398] [SCH 08; p. 563]:

[22.1a]

[22.1b]

22.2.3.Fell topology for closed subsets

The class of closed subsets is usually equipped with the so-called Fell topology [FEL 62, BEE 93a], denoted as , sometimes called the topology of closed convergence or the topology of point-wise convergence, or the vague topology [MOL 05].

A subbasis for the Fell topology is provided by all closed subsets of that hit a non-empty open subset of (i.e. belonging to where U is open), plus all closed subsets of that miss a non-empty compact subset (i.e. belonging to where K is compact), namely [MOL 05; p. 398, SCH 08; p. 563]. This topological space is compact with a countable basis, and hence is metrizable (see section 8.3.1) [MAT 75a] [SCH 08; p. 563].

[22.2]

where d2 is the Euclidean metric in (see section 9.4.1.2).

The Fell topology on is Hausdorff (see section 8.2.6.1), separable, metrizable, and compact (see section 8.6.1).

22.2.4.Hausdorff topology for compact subsets

The class of all non-empty, compact subsets denoted as is usually equipped with the so-called Hausdorff topology, denoted by , sometimes called the topology of compact convergence or the topology of uniform convergence, and induced by the Pompeiu–Hausdorff metric [POM 05, HAU 14] denoted as dPH, defined for two non-empty compact sets X and Y in by [SCH 08; p. 571]:

[22.3]

[22.4]

The space of non-empty compact sets in equipped with the Pompeiu–Hausdorff metric is called the Hausdorff metric space, or better the Hausdorff metric hyperspace. It inherits several nice geometrical properties from the Euclidean space . It is a complete, separable, Hausdorff and locally compact metric space since (,d2) is complete, separable, Hausdorff and locally compact (see section 8.6.1) for the Euclidean metric d2 on [SCH 93a; pp. 48-49] [STO 95; p. 6] [BUR 01; p. 253]. The Hausdorff metric (hyper)-space is hence a Polish space (see section 8.6.4) [STO 95; p. 6]. In addition, it is a Baire space (see section 8.6.3) [SCH 93a; p. 125].

The Hausdorff topology on is strictly finer (see section 8.2.4) than the topology induced by the Fell topology [SCH 08; p. 572]:

[22.5]

NOTE 22.1 (Hausdorff metric induced by equivalent metrics on ).– When working with compact sets, the Pompeiu–Hausdorff dPH is classicaly induced by the Euclidean metric d2 on , but the latter could be replaced by any metric generating the topology of , without changing the topology on (, dPH) [SCH 08; p. 572]. In Mathematical Imaging, this is the special case of the Minkowski metrics, e.g. the Manhattan metric d1 and the Chebyshev metric d∞ (see section 9.4.1.2).

22.2.5.Continuity and semi-continuity of set transformations

[22.6]

[22.7]

22.2.6.Continuity of basic set-theoretic and topological operations

Endowing the class of all closed subsets of with the Fell topology, and the class of all compact subsets of with the Hausdorff topology, the following set-theoretic, Euclidean or topological operations satisfy various properties of continuity or semi-continuity [MAT 75a, AUB 90, SCH 94], [SCH 08; sections 12.2 and 12.3]:

– the union of two closed sets is continuous (the result is a closed set);

– the intersection of two closed sets is u.s.c. (the result is a closed set);

– the union of two compact sets is continuous (the result is a compact set);

– the union of a closed set with a compact set is continuous (the result is a closed set);

– the closed complementary operation of two closed sets is l.s.c. (the result is a closed set);

– the boundarization of a closed set is l.s.c. (the result is a closed set).

22.3. Main notions and approaches for IPA

22.3.1.Topologies in the spatial domain

The spatial domain can be endowed with the Minkowski p-norms (p ∈ [1,+∞]) (see section 9.4.1.3).

All metrics dp on induced by the Minkowski p-norms, including the Euclidean metric d2, the taxicab metric d1, and the Chebyshev distance d∞, are strongly equivalent [SCH 08; p. 572], and therefore induced the same topology on , namely the Euclidean topology [SCH 08; p. 572].

22.3.2.The Lebesgue–(Čech) dimension

More generally, there exist three classical notions of topological dimension [ENG 78]: (1) the Lebesgue–Čech covering dimension, (2) the Menger–Urysohn’s small inductive dimension [URY 22] [MEN 23], and (3) the Brouwer–Čech large inductive dimension [BRO 13] [ČEC 31]. As is known from General Topology, all of them are the same for separable metric spaces (see section 8.6.2) [ENG 78]. This is the case for the spatial domain equipped with any of the Minkowski metrics dp (p ∈ [1, + ∞]).

22.3.3.Interior and exterior boundaries

The interior topological boundary of an object, denoted as ∂Xi, is defined by [DEL 11; p. 434]:

[22.8]

The exterior topological boundary of an object, denoted as ∂Xe, is defined by [DEL 11; p. 434]:

[22.9]

22.3.3.1.Topologically regular objects

An object in is called topologically regular closed, called topologically regular for short, if it is the closure of its interior, namely [STE 78; p. 6]:

[22.10]

An object in is called topologically regular open, if it is the interior of its closure, namely [STE 78; p. 6]:

[22.11]

A topologically regular object in does not have any lower-dimensional parts.

22.3.4.Path-connectedness

The concept of connectedness formalizes the intuitive expression ‘of a single piece’. In fact, the path-connectedness is the useful (stronger) concept. An object X is connected by path, path-connected for short, if two any distinct pixels x and y of X can be connected by a path entirely contained in X. In continuous imaging, a path between the initial pixel x and the terminal pixel y is represented by a continuous mapping, denoted as p, from the unit real number interval [0, 1] in X, namely:

[22.12]

NOTE 22.2 (Digital path).– In discrete imaging, a path is defined by adjacency (see section 9.4.2) from the initial pixel x up to the terminal pixel y. The term “digital path” is then used [KLE 04b].

A path is said to be simple if it is injective, i.e. the path has no double pixels, but only simple pixels (hence its name), and closed if the initial pixel is also its terminal pixel. A Jordan path is both a simple and closed path. It is sometimes called a loop.

22.3.5.Homeomorphic objects

A homeomorphism (see section 8.2.5) is a bijective and bicontinuous mapping between two objects, which are then said to be homeomorphic objects. Two homeomorphic objects share the same topological properties.

22.4. Main applicationsto IPA

22.4.1.Topological separation of objects and object removal

The first application issue is the topological separation of objects (see section 8.2.6.1.) in the spatial domain relatively to their context (see section 3.1). The context of a family of objects in a binary image is defined as being the complementary set to their union relative to the spatial support D in , namely:

[22.13]

The removal of a family of topologically-separated objects , called object removal for short, is expressed simply as follows:

[22.14]

where D0 is the set of background-pixels (i.e. the 0-valued pixels within the spatial support D) (see section 1.2).

The topological separation is stronger than the set-theoretic separation that coincides with the set-theoretic distinctness notion (see section 21.4.2).

22.4.1.1.(Path)-connected components

Topologically, the separation of two distinct objects X and Y (see section 8.2.6) means the absence of any way from one pixel in X up to another pixel in Y. An object X is connected by a path (i.e. a path-connected object) if there is a path from each pair of its pixels. The maximal (path)-connected subsets of an object X are called the (path)-connected components of X. These components make up a partition of X (i.e. they are disjoint, non-empty, and their union is equal to X).

22.4.2.Counting of separate objects

Counting of separate objects within a family of objects is restricted in practice to the number of topologically separate objects, namely:

[22.15]

where indexes the topologically separate objects.

In Mathematical Imaging, a family of topologically separate objects is supposed to be locally finite in order to be tractable (see section 21.3.3). That means that the number of topologically separate objects belonging to is finite on any bounded subset of , in particular within the spatial support D (in the case when it is itself bounded).

22.4.3.Contours of objects

From a topological viewpoint, the contours of an object X is modeled by its topological boundary, denoted as ∂X (see section 8.2.2). An object is closed if it contains all its boundary pixels and open if it contains none. An open object is sometimes called a ‘no-boundary object’. The topological boundary is a closed set, but is not necessarily connected even if the object X is (e.g. in the case of an object X having proper cavities; see section 26.4.2). In practice, a nice definition is as follows:

[22.16]

A pixel will be a boundary pixel of an object X if it is member of both X and Xc, i.e. roughly speaking ‘nearby’ X and its complementary Xc.

22.4.4.Metric diameter

The (metric) diameter of a non-empty object X in for the metric d, denoted as d(X), is the least upper bound of the distances between pairs of pixels belonging to X, namely:

[22.17]

Jung’s theorem [JUN 01] states that the Euclidean diameter (X) of a non-empty compact object X in is related to the radius of the minimum enclosing ball of X, denoted as B (X), by the following inequality [KLE 71]:

[22.18]

The extremal case of equality is attained if and only if X is a regular n-simplex (see section 24.3.5).

22.4.5.Skeletons of proper objects

A topological (more precisely metric) set-descriptor of an object X is provided by its skeleton [MOT 35b, MOT 35a, CAL 68], that has been justified from a human vision viewpoint [BLU 62, BLU 67, BLU 73, KIM 03].

The topological skeleton of a proper object X in (see section 7.2.2) is defined as the related object, denoted as Ske(X), consisting of pixels belonging to X which are the centers of the maximum balls included in X for a given metric d in :

[22.19]

where Bn(x, d(x, ∂X) [ designates the open n-dimensional ball around x of radius d(x, ∂X).

NOTE 22.3 (Topological skeleton).– A well-known result states that the set of pixels belonging to X equidistant from two or more closest pixels on the boundary ∂X is dense in the skeleton [WOL 79, MAT 88a].

If the object X is an open bounded, connected set, then the closure of its skeleton is also a connected set [FRE 97]. Moreover, the skeleton is locally path-connected, and indeed includes many paths of finite length [FRE 97] [SHE 96]. Nevertheless, there are plenty of objects with a smooth boundary (even , i.e. infinitely smooth) that have a pathological behavior, in the sense that their skeletons may have an infinite number of branches.

The topological dimension of Ske(X) (see section 22.3.2) is at most n – 1 [FRE 97].

The topological skeleton is Lebesgue-measurable (see section 27.2.9) and has Lebesgue measure zero [FRE 97].

When the object X consists of a locally finite union (i.e. finite on every compact set in , and in practice often the spatial support D itself) of compact, (path)-connected objects , pairwise disjoint, it is possible to associate with each object Xi its zone of influence, or its influence zone for short [DIR 50], denoted as InfZ(Xi), defined by [BER 09; 1st ed., 1987]:

[22.20]

which actually consists of all pixels strictly closer to Xi than to other objects Xj.

NOTE 22.4 (Influence zone).– It is important both theoretically and practically to define an influence zone as an open set and not as a closed set (i.e. by using < and not ≤ in the previous equation [22.20]) [FAB 02].

The skeleton by influence zone [LAN 78], denoted as Skiz(X), of the object X is then constituted by all of the pixels in the spatial support D that do not belong to any zone of influence of , namely [SCH 94; p. 76]:

[22.21]

that is to say a subset of the skeleton of Xc.

The skeleton of Xc is sometimes called the exoskeleton. It is a superset (see equation [7.9a]) of the skeleton by influence zone Skiz(X) of X, namely [COS 86; p. 168]:

[22.22]

22.4.6.Dirichlet–Voronoi’s diagrams

In the special case where the aforementioned objects are reduced to single distinct pixels , the resulting spatial partition is called Dirichlet–Voronoi’s diagram [DIR 50, VOR 08] of X, and denoted as DiaDV (X), namely [AUR 91] [BER 09; 1st ed., 1987] [FAB 02]:

[22.23]

that is to say a subset of the skeleton of Xc, i.e. the exoskeleton of X.

The so-called dual to Dirichlet–Voronoi’s diagram is the Delaunay triangulation [DEL 34] in the plane, which is the triangulation which maximizes the minimum angle of all the angles of the triangles [BER 08b]. A triangulation [ALE 11; Original ed., 1956] is a subdivision of an object into simplices (see section 24.3.5). In particular, in the plane it is a subdivision into triangles. The notion of Delaunay triangulation extends to three and higher dimensions [RAJ 94]. Generalizations are possible to metrics other than Euclidean. However, in these cases a Delaunay triangulation is not guaranteed to exist or be unique.

22.4.7.Distance maps

In the spatial domain and for a metric d, the distance map of a non-empty open object X whose closure is compact, denoted as mapd(X; x), is defined by:

[22.24]

See Chapter 40 “The Distance-Map Framework” for a detailed account on distance maps.

22.4.8.Distance between objects

In addition to the topology on pixels, i.e. on the spatial domain , based on the concept of neighborhood of pixels, it is also necessary to use relevant (hyper)-topologies (see section 22.2.2) on the classes of specific objects (e.g. the family of closed objects or the familly of compact objects), based on the concept of neighborhood of objects (i.e. sets of pixels). The interest is to make sense of the continuity of the operations and transformations on such a class of objects, and even to define distances between objects themselves. Such distance functions are called object distance functions. Starting from a given metric d on pixels, i.e. on the spatial domain , they measure how far two objects are from each other, giving a meaning to the distance between two objects X and Y.

Given a metric d on the spatial domain , the Pompeiu–Hausdorff semi-metric (see section 8.3.1), or more often simply called the Hausdorff semi-metric, denoted as dPH, on the power set , is defined by [BUR 01; p. 252]:

[22.25]

In particular, the distance between an object X and its topological closure is zero, namely [BUR 01; p. 252]:

[22.26]

The Pompeiu–Hausdorff metric turns the family of non-empty compact subsets of , i.e. , into a metric space in its own right [BUR 01; p. 252].

22.4.9.Spatial support’s border effects

As in the set-theoretic framework, the most annoying constraint comes from objects that partially overlap the border of the spatial support D (i.e. its topological boundary ∂D), which must be considered in order to avoid as far as possible the border effects that lead to errors or biases. Generally, the spatial support is an open bounded or compact subset of with a simple shape (e.g. a rectangle in dimension 2).

22.5. Additional comments

Historical comments and references

Hyper-topologies have been introduced by L. Vietoris [VIE 21, VIE 22]. The Fell topology was introduced in [FEL 62] as a compact topology on the hyperspace of all closed subsets, with the empty set as infinity and an isolated point.

Informal use of Dirichlet–Voronoi’s diagrams can be traced back to R. Descartes in 1664 [DES 64]. Such diagrams are also called Thiessen polygons (in dimension 2) in Meteorology [THI 11], and particular Dirichlet cells are also known as Wigner–Seitz cells