Mathematical Foundations of Image Processing and Analysis 1 E-Book

Jean-Charles Pinoli

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

Seitenzahl: 614

Veröffentlichungsjahr: 2014

Beschreibung

Image processing and image analysis are typically important fields in information science and technology. By “image processing”, we generally understand all kinds of operation performed on images (or sequences of images) in order to increase their quality, restore their original content, emphasize some particular aspect of the information or optimize their transmission, or to perform radiometric and/or spatial analysis. By “image analysis” we understand, however, all kinds of operation performed on images (or sequences of images) in order to extract qualitative or quantitative data, perform measurements and apply statistical analysis. Whereas there are nowadays many books dealing with image processing, only a small number deal with image analysis. The methods and techniques involved in these fields of course have a wide range of applications in our daily world: industrial vision, material imaging, medical imaging, biological imaging, multimedia applications, satellite imaging, quality control, traffic control, and so on

Leseprobe

Contents

Preface

Introduction

Elements of Mathematical Terminology

PART 1: An Overview of Image Processing and Analysis (IPA)

1 Gray-Tone Images

1.1. Intensity images, pixels and gray tones

1.2. Scene, objects, context, foreground and background

1.3. Simple intensity image formation process models

1.4. The five main requirements for a relevant imaging approach

1.5. Additional comments

2 Gray-Tone Image Processing and Analysis

2.1. Image processing

2.2. Image analysis

2.3. Image comparison

2.4. Importance of Human Vision

2.5. Additional comments

3 Binary Images

3.1. Scene, objects and context

3.2. Binary and multinary images

3.3. Additional comments

4 Binary Image Processing and Analysis

4.1. Binary image processing

4.2. Binary image analysis

4.3. Binary image and object description

4.4. Object comparison

4.5. Object analysis, recognition and formation

4.6. Additional comments

5 Key Concepts and Notions for IPA

5.1. Dimensionality

5.2. Continuity and discreteness

5.3. Scale, resolution and definition

5.4. Domains

5.5. Ranges

5.6. Additional comments

6 Mathematical Imaging Frameworks

6.1. Mathematical imaging frameworks

6.2. Image representation and image modeling

6.3. A mathematical imaging methodology

6.4. Additional comments

PART 2: Basic Mathematical Reminders for Gray-Tone and Binary Image Processing and Analysis

7 Basic Reminders in Set Theory

7.1. Mathematical disciplines

7.2. Sets and elements

7.3. Order and equivalence relations on sets

7.4. Mappings between sets

7.5. Mapping composition, involutions, and idempotent mappings

7.6. Cardinality

7.7. Cover

7.8. Additional comments

8 Basic Reminders in Topology and Functional Analysis

8.1. Mathematical disciplines

8.2. Topological spaces

8.3. Metric spaces

8.4. Some particular kinds of points in topological and metric spaces

8.5. Some particular kinds of subsets in topological and metric spaces

8.6. Some particular topological spaces

8.7. Lipschitz and Gromov–Hausdorff distances

8.8. Topological vector spaces

8.9. Additional comments

PART 3: The Main Mathematical Notions for the Spatial and Tonal Domains

9 The Spatial Domain

9.1. Paradigms

9.2. Mathematical structures

9.3. Main approaches for IPA

9.4. Main applications to IPA

9.5. Additional comments

10 The Tonal Domain

10.1. Paradigms

10.2. Mathematical concepts and structures

10.3. Main approaches for IPA

10.4. Main applications for IPA

10.5. Additional comments

PART 4: Ten Main Functional Frameworks for Gray Tone Images

11 The Algebraic and Order Functional Framework

11.1. Paradigms

11.2. Mathematical structures and notions for IPA

11.3. Main approaches for IPA

11.4. Main applications for IPA

11.5. Additional comments

12 The Morphological Functional Framework

12.1. Paradigms

12.2. Mathematical concepts and structures

12.3. Main approaches for IPA

12.4. Main applications for IPA

12.5. Additional comments

13 The Integral Functional Framework

13.1. Paradigms

13.2. Mathematical structures

13.3. Main approaches for IPA

13.4. Main applications for IPA

13.5. Additional comments

14 The Convolutional Functional Framework

14.1. Paradigms

14.2. Mathematical concepts and structures

14.3. Main approaches for IPA

14.4. Main applications for IPA

14.5. Additional comments

15 The Differential Functional Framework

15.1. Paradigms

15.2. Mathematical concepts and structures

15.3. Main approaches for IPA

15.4. Main applications for IPA

15.5. Additional comments

16 The Generalized Functional Framework

16.1. Paradigms

16.2. Mathematical concepts and structures

16.3. Main approaches for IPA

16.4. Main applications for IPA

16.5. Additional comments

17 The Frequential Functional Framework

17.1. Paradigms

17.2. Mathematical concepts and structures

17.3. Main approaches for IPA

17.4. Main applications to IPA

17.5. Additional comments

18 The Multiscale Functional Framework

18.1. Paradigms

18.2. Mathematical concepts and structures

18.3. Main approaches for IPA

18.4. Main applications for IPA

18.5. Additional comments

19 The Variational Functional Framework

19.1. Paradigms

19.2. Mathematical structures

19.3. Main approaches for IPA

19.4. Main applications for IPA

19.5. Additional comments

20 The Probabilistic Functional Framework

20.1. Paradigms

20.2. Mathematical concepts and structures

20.3. Main approaches for IPA

20.4. Main applications for IPA

20.5. Additional comments

Appendices

Tables of Notations and Symbols

Table of Acronyms

Table of Latin Phrases

Bibliography

Index of Authors

Index of Subjects

ToBlandine, 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 Ltd27-37 St George’s RoadLondon SW19 4EUUK

www.iste.co.uk

John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA

www.wiley.com

© ISTE Ltd 2014The 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: 2014939770

British Library Cataloguing-in-Publication DataA CIP record for this book is available from the British LibraryISBN 978-1-84821-546-7

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 12a];

– “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 12b];

– 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 PINOLIMay, 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–Poincaré’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.

Elements of Mathematical Terminology

The purpose of this short, preliminary chapter is to introduce and define some of the key elements of general mathematical terminology which will be used in this book. Indeed, a clear and precise vocabulary is essential for a good understanding of concepts and ideas.

Axiom–Postulate–Conjecture–Paradox

An axiom is simply a premise or starting point from which other statements are logically derived. A postulate is a closely related notion, but slightly distinguished from the axiom, the latter will not seek to demonstrate. Euclidean Geometry is built from four axioms and a postulate (called the parallel postulate, or also Euclid’s fifth postulate that can be expressed as “At most one line can be drawn through any point not on a given line parallel to the given line in a plane”).

A theorem is a true statement that has been proven on the basis of previously established statements, and basically axioms/postulates.

A paradox is a statement that apparently contradicts itself and yet might be true. One example is (Zermelo)-Russell’s paradox, discovered in 1900-01 [ZEM 08, RUS 03], which can be expressed as whether a “list of all lists that do not contain themselves” would include itself, and showed that naive Set Theory was flawed.

Collection – class – family – indexed family

In Mathematics, a collection is not formally defined, but it may refer to various terms, depending on the context, such as set, class, family, etc. A class is a collection of mathematical entities which can be unambiguously defined by a property that all its members share, for example the class of continuous functions or the class of convex sets, in specific contexts. Generally, a family is a collection less proper as a class, but it is often used in a synonymic manner. An indexed family, often simply called family, is a collection of mathematical entities that are associated with indexes, that is to say a collection indexed by an ordered set, that is generally a finite integer set or infinite integer set (e.g. ), or the real number set .

Formalization – formulation – representation – modeling

Formalization means the reduction in formal structures. Thus, mathematical formalization can be defined as “to give a definite and precise mathematical form to”. Mathematical formulation is a particular case of mathematical formalization, which means stricto sensu “to reduce to or to express in a mathematical formula”. This will be the use in this book.

Mathematical representation means the determination of the proper way to mathematically express or describe a mathematical entity (something that mathematically exists by itself). In Mathematical Imaging, it will be primarily a question of pixels, gray tones, spatial and frequency domains, gray-tone images, binary images, objects, contours, etc. The purpose of mathematical modeling refers to the process of formalization of a model. A mathematical model is a description of a problem, process, system, etc., using mathematical concepts and language. In Mathematical Imaging, it is often implemented by a computer program. The concepts of representation and modeling are not always distinguished, and are quite often used one instead of the other.

Variable – constant – parameter – argument

In Mathematics, a variable is a value that may change within the scope of a given problem, system, model or any situation. In contrast, a constant is a value that remains unchanged; this should not be confused with the term mathematical constant which is a specific number, independent of the scope of the given problem, system or situation (e.g. the number π or the Napier–Euler’s numbere). A parameter is another important value to take into consideration, which plays a complementary role. Indeed, although this value may change, it does not play the same role as a variable. In its common meaning, the term is used to identify a measurable characteristic or factor that can help in defining a particular problem, system, model or any situation. An indeterminate is a variable in formal Algebra, but the term indeterminate has other meanings, such as an indeterminate system of equations that has more than one solution.

Mathematical functions have one or more arguments (i.e. specific inputs) that are designated in the definition by variables, while their definitions can also contain parameters. The variables are mentioned in the list of arguments that the function takes, but the parameters are generally not. When parameters are present, the definition designates a whole family of functions, one for every valid particular set of values of the parameters.

A parametric (or parameterized) family is a family of entities whose definitions depend on some parameters. Common examples are parameterized (families of) functions, probability distributions, geometric sets (e.g. curves or surfaces), etc. A parametric model is a model that can be described using a finite number of parameters.

A variable or a parameter need not be a scalar or a vector, but may refer to a function or a set. For example, a functional is a function of functions, or a function of (geometric) sets. Another example is set-parameterized functions, that is to say functions parameterized by sets (e.g. indicator functions or distance-map functions), or function-parameterized sets, namely sets parameterized by functions (e.g. level sets).

Well/ill-posed and forward/inverse problems

The mathematical concept of well-posed problem refers to mathematical problems that should have the following properties [HAD 02]: (1) existence of a solution, (2) uniqueness of a solution and (3) stability of the solution (i.e. the solution’s behavior is slightly sensitive to small changes in the initial condition). On the contrary, an ill-posed problem fails to respect one of those properties, in particular stability. In other words, an arbitrary small perturbation in the data can correspond to (arbitrarily) large perturbations in the results. An ill-posed problem needs to be reformulated for numerical treatment and analysis, typically by involving additional assumptions (i.e. by the so-called regularization; see below). With a more modern definition, a problem is said to be well-posed if the collection of data/observations is a closed set in a suitable space [NAS 87].

A close concept is that of numerical conditioning, which measures the dependence of the solution of a numerical problem compared to the data of the problem in order to check the validity of the solution calculated from these data. A numerical problem is then said to be well-conditioned if the numerical solution behaves well; on the contrary, it is called ill-conditioned.

A forward problem relates the model parameters to the observed measured data, while conversely an inverse problem aims at retrieving the data from the model parameters. Inverse problems are generally ill-posed.

Regularization and relaxation

Regularization theory is often used to solve ill-posed problems [TIK 43, TIK 77, LAV 67]. Regularization involves introducing additional information in order to solve an associated ill-posed problem, whose solution will yield meaningful answers and approximation to the ill-posed problem. The mathematical formulation of such a regularized problem often takes the form of two terms: the first term is the so-called fidelity term (which expresses the proximity to the observed or given data, e.g. a gray-tone image) and the second term is the regularization term (in conflict with the first term), parameterized by one or more weighting parameters to be controlled or even optimized.

Relaxation is an approximation of a difficult problem (or even a problem for which no general solution exists) by a nearby problem that is easier to solve (or even at least solvable). A relaxation technique is a method of optimization that replaces a strict constraint with a less strict constraint (i.e. a hard constraint by an easier one). Therefore, a solution of the relaxed problem provides information about the original problem.

Adaptive/fixed and intrinsic/extrinsic notions

An adaptive notion is a notion that includes local information content, instead of a fixed notion that involves no adaptivity at all. These terms can also be described as a feature, a property, a quantity, a law, a test, a transformation, or a measure, etc. For example, in gray-tone imaging, a threshold may be fixed (e.g. imposed by the user) or adaptive (e.g. it can adapt to the varying conditions of illumination).

An intrinsic notion is inherent to an entity (e.g. a structure or a system), instead of an extrinsic notion which is predetermined (e.g. by the observer). For example, in gray-tone imaging, spatial scales used will be extrinsic (e.g. by using wavelet transformations) or intrinsic (e.g. within the anisotropic diffusion model).

Method – technique – algorithm – implementation

In Mathematics and Computer Sciences, a technique is the systematic ‘procedure’ by which a specific task is generally automatically accomplished. A method is a way less or more automatized (i.e. the intervention of a human expert is needed, at least partly) by which a sequence of techniques is performed, and hence the aim of specific tasks is accomplished. An algorithm is a step-by-step procedure encoding a technique or a method in a computer-oriented language (e.g. for performing calculations, or resulting in simulations). Implementation is the realization or execution of an algorithm with a particular computer language and on a specific computer machine.

Invariance and compatibility

Invariance and compatibility are two important, but different concepts.

An invariant property, or for short an invariant, is a property of a class of entities that remains unchanged when the operations, transformations or measurements of a certain type are applied. For example, in gray-tone imaging, the scale invariance describes a property that does not change if the scales of observation and/or measurement are multiplied or divided by a common factor (e.g. by applying a zoom-out or a zoom-in, i.e. a magnification or demagnification, respectively). In binary imaging, the invariance of a measurement (e.g. the area, volume, or a shape descriptor) under a certain type of transformation (e.g. translations, rotations, or similitudes) expresses the fact that the resulting value remains unchanged for a given object.

The notion of compatibility is a different concept, which is often confused with that of invariance. A property of a class of entities is said to be compatible with a certain type of operations, transformations or measurements when it commutes or when it is homogeneous. For example, the convolution operation commutes with translations and rotations, while the volume measurement is homogeneous of degree equal to the dimension of the ambient space (e.g. 2 in planar binary imaging).

Magnitude and multitude

Magnitude designates the ‘size’ of a measurable mathematical entity, a property by which the entity can be compared as larger or smaller than other entities of the same kind. In Mathematical Imaging, the first example is the intensity located on a pixel, which is the amount of a measured physical quantity (e.g. photon and electron energy). The second example is the size, e.g. the area (respectively, volume) of a planar (respectively, volume) geometric object.

Multitude is sometimes used as the ‘opposite’, or better named ‘dual notion’ with respect to magnitude. In fact, the right mathematical notion is that of cardinality. The cardinality of an arbitrary set is a measure of its ‘number of elements’. A set is said to be (1) “finite” if its cardinality is strictly less than that of the set of all natural numbers , (2) “countably infinite” if its cardinality is equal to that of the set of all natural numbers and (3) “uncountable” if its cardinality is strictly greater than that of the set of natural numbers . A discrete set is either finite or infinite (e.g. or ), while a continuous set is infinite (e.g. ). In Mathematical Imaging, the first example of a finite set is the pixel frame on which a digital image is defined (e.g. a 520 × 480 pixels image) and the second example is the gray-level range where it takes its values (e.g. the integer range [0 … 255] for an 8-bit image).

Well-behaved/pathological and exceptional/extremal

A pathological entity is one whose properties are considered unusual, or undesirable, or atypically bad, and often counterintuitive. The opposite case is well-behaved.

Many branches of Mathematics study entities of a given type and prove a classification theorem following an equivalence relation. Exceptional entities are those that cannot be classified. Extremal entities that fall into a given family or class are the most extreme examples and by some measure are of interest. They are not unusual in the way exceptional entities are.

PART 1

An Overview of Image Processing and Analysis (IPA)

1

Gray-Tone Images

In this textbook, the term image will have a physical meaning and will refer to a one-, two- or threedimensional (3D), continuous or discrete (including the digital form) radiometric spatial distribution of light (or another radiation) intensities.

1.1. Intensity images, pixels and gray tones

Radiometric images are spatially defined on pixels (contraction of “picture elements”) with intensity values called gray tones. Such images are often abusively called “black and white” images in the common language (panchromatic images is better suited and sometimes used in relation to the visible light and the human eye) [ALL 10; Original 1st ed., 1890]. In this book, they will be naturally designated as gray-tone images. Color images (e.g. three colors according to the human visual perception), multispectral images (e.g. four or five colors as in satellite imagery) [LEE 05] [PET 10; p. 665] and hyperspectral images (i.e. numerous almost monochromatic channels) [CHA 03b] will not be discussed because they require specific frameworks and approaches, still subject to particular mathematical research works.

The term illumination designates the incident light (or another radiation, such as an electromagnetic or nuclear radiation, e.g. gamma rays and X-rays) [DAI 74, HEN 02, BAR 04, HOR 06].