Stochastic Geometry for Image Analysis E-Book

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

Seitenzahl: 358

Veröffentlichungsjahr: 2013

Beschreibung

This book develops the stochastic geometry framework for image analysis purpose. Two main frameworks are  described: marked point process and random closed sets models. We derive the main issues for defining an appropriate model. The algorithms for sampling and optimizing the models as well as for estimating parameters are reviewed.  Numerous applications, covering remote sensing images, biological and medical imaging, are detailed.  This book provides all the necessary tools for developing an image analysis application based on modern stochastic modeling.

Leseprobe

Table of Contents

Chapter 1. Introduction

Chapter 2. Marked Point Processes for Object Detection

2.1. Principal definitions

2.2. Density of a point process

2.3. Marked point processes

2.4. Point processes and image analysis

Chapter 3. Random Sets for Texture Analysis

3.1. Introduction

3.2. Random sets

3.3. Some geostatistical aspects

3.4. Some morphological aspects

3.5. Appendix: demonstration of Miles’ formulae for the Boolean model

Chapter 4. Simulation and Optimization

4.1. Discrete simulations: Markov chain Monte Carlo algorithms

4.2. Continuous simulations

4.3. Mixed simulations

4.4. Simulated annealing

Chapter 5. Parametric Inference for Marked Point Processes in Image Analysis

5.1. Introduction

5.2. First question: what and where are the objects in the image?

5.3. Second question: what are the parameters of the point process that models the objects observed in the image?

5.4. Conclusion and perspectives

5.5. Acknowledgments

Chapter 6. How to Set Up a Point Process?

6.1. From disks to polygons, via a discussion of segments

6.2. From no overlap to alignment

6.3. From the likelihood to a hypothesis test

6.4. From Metropolis–Hastings to multiple births and deaths

Chapter 7. Population Counting

7.1. Detection of Virchow–Robin spaces

7.2. Evaluation of forestry resources

7.3. Counting a population of famingos

7.4. Counting the boats at a port

Chapter 8. Structure Extraction

8.1. Detection of the road network

8.2. Extraction of building footprints

8.3. Representation of natural textures

Chapter 9. Shape Recognition

9.1. Modeling of a LIDAR signal

9.2. 3D reconstruction of buildings

Bibliography

List of Authors

Index

First published 2012 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

John Wiley&Sons, Inc.

27-37 St George’s Road

111 River Street

London SW19 4EU

Hoboken, NJ07030

UK

USA

www.iste.co.uk

www.wiley.com

© ISTE Ltd 2012

The rights of Xavier Descombes 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 Cataloging-in-Publication Data

Stochastic geometry for image analysis / edited by Xavier Descombes.

        p. cm.

  Summary: “This book develops the stochastic geometry framework for image analysis purpose. Two main frameworks are described: marked point process and random closed sets models. We derive the main issues for defining an appropriate model. The algorithms for sampling and optimizing the models as well as for estimating parameters are reviewed. Numerous applications, covering remote sensing images, biological and medical imaging, are detailed. This book provides all the necessary tools for developing an image analysis application based on modern stochastic modeling”-- Provided by publisher.

  Includes bibliographical references and index.

  ISBN 978-1-84821-240-4 (hardback)

  1. Image processing--Statistical methods. 2. Stochastic geometry. I. Descombes, Xavier.

  TA1637.S76 2011

  621.36′70151922--dc23

2011036864

British Library Cataloguing-in-Publication Data

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

ISBN 978-1-84821-240-4

Chapter 1

Introduction1

Mathematical techniques for modeling random phenomena have found a natural application in the field of image analysis. An image is itself a noisy signal, due to the characteristics of the imaging sensor and the conditions of image acquisition or transmission. Noise reduction techniques, low-pass filtering, and Kalman filters, all of which were initially developed in signal theory, have been easily generalized to apply to the case of two-dimensional (2D) images, and thereafter to higher dimensions. Nevertheless, the random phenomena within an image are not solely the result of noise. The content of the image itself can be regarded as the product of a random process. The texture present in an image cannot be directly interpreted from the set of pixel values, but is better understood through a set of stationary statistics that characterize the texture itself, or by a probabilistic model and the values of its parameters. Thus, it is in fact the statistics of the pixels forming Lena’s famous hat (see Figure 1.1) which enable it to be characterized. In the same way, a segmented image, representing, for example, some plots of agricultural land, contains a randomness, in the sense that different parts of the same area in the image have common properties but also show certain variations (see Figure 1.2).

Figure 1.1.Lena and her feathered hat

Figure 1.2.Two examples of the Beauce countryside (© IGN)

The stochastic models developed for image analysis have therefore been rapidly applied to model the noise, but are equally modeling the information content of the images. This content is primarily based on the concept of pixel interaction. It is a question of modeling the respective values of the neighboring pixels. How does one pixel influence its neighbors? The concept of texture is clearly related to this paradigm since, in this case, we are concerned with a pattern of pixels, characterized by the properties of correlation, isotropy, and principal direction. In the same way, the characteristic properties of a segmented scene are contextual. For example, a pixel is more likely to belong to the same region as its neighbors than to define a region by itself. Markov fields have therefore had a prominent role to play since the 1980s [GEM 84]. They make it possible for global laws to be defined on the image using local conditional probabilities, and can be represented by a Gibbs field, thanks to the equivalence established by the Hammersley–Clifford theorem [BES 74]. In practice, the model is created from local interactions defined by potential functions. These models thus enable the modeling of local phenomena which characterize textures [CRO 83] as well as “cartoon” images that are segmented (images that are piecewise constant) [GEM 84]. In classification, Markov modeling is used in a Bayesian context, through the definition of a likelihood, modeling the sensor, and of a prior, modeling the knowledge we have on the solution, in the form of a Markov field. Most of the time, interactions are modeled between the closest pixels, with more large-scale effects being covered by a multiscale or hierarchical models. Over the years, this approach has been generalized, notably with the aim of being freed from the dichotomy between likelihood and prior. Thus, the constraints on the solution sought can interact with the data. The simplest example is when a spatial regularization term between two pixels is scaled according to the image gradient between them pixels (with greater scaling for smaller image gradients). The solutions then consist of either directly modeling the joint law, as, for example, for field pairs or triplets [BEN 05], or else directly modeling the a posteriori law, such as, for example, for conditional random fields [KUM 06]. These various different models rely on local specifications, which lead to a global representation. They are therefore highly adapted to account for the contextual properties. Knowing the value of a random variable gives information about its neighbors. Regularization constraints or texture descriptors are therefore part of the application of such models. On the other hand, they prove to be much more limited for modeling geometric information. For example, they do not make it possible to impose constraints on the shape of the segmentation regions, without leading to prohibitive complexity. In the same way, macro-textures are not adapted to these models, which are based on local interactions.

Figure 1.3.Urban zone as pictured by SPOT (© CNES)

With high resolution and very high resolution, geometric information tends to dominate. Let us look at the urban area as seen by SPOT (see Figure 1.3). It is distinguished from its surroundings by its texture. Indeed, the various fields have a homogeneous radiometry whereas the urban zone shows greater radiometric variation. Contextual information is therefore required to differentiate the urban zone. Consequently, Markov fields have proved to be an effective tool for segmenting the urban area (see Figure 1.4). On the other hand, they are not suitable for processing the Ikonos image, an excerpt from which is shown in Figure 1.5. In the same way, on the road network shown in Figure 1.6, we can see interruptions of several tens of pixels due to the shadows of the trees. The contextual information in the close vicinity is therefore insufficient for fully characterizing the network for such an image (an aerial image, with a resolution of one pixel representing 25 cm by 25 cm on the ground).

Figure 1.4.Segmentation of the urban zone by a Markov texture model

Figure 1.5.Urban zone as pictured by Ikonos

Figure 1.6.Aerial image with a resolution of one pixel representing 25 cm by 25 cm on the ground (© IGN)

With high resolution and very high resolution, the essential information for analyzing the scene is geometric information. The city is no longer considered to be a texture but rather an ensemble of geometric entities (buildings, roads, trees, etc.). In the same way, the road network is not uniquely characterized by a homogeneous radiometry along the roads and is a strong contrast perpendicular to these roads. Rather, it is described by a succession of segments or long rectangles. To discover and record this information, it is therefore desirable to be freed from the pixel level and to model the scene at the scale of the objects. To model aspects of the texture, it is necessary to turn to macro-texture models that control sets of random objects. The formalism of random fields is not restricted to the concept of pixels, nor even to the image lattice. Indeed, rather than defining a random variable per pixel, it is possible to define a random field on an unspecified graph. Each node of the graph can then represent an object, and the edges represent the relations of proximity or overlap between the objects. The interactions between objects, to support certain configurations, can then be modeled by a Markovian density. A good example of such a model is described in [TUP 98]. To extract the road network, a set of candidate segments is extracted using local operators. This set is completed using heuristics, including the various possible connections between the segments of the first set. A node of the graph is then associated with each segment of the second set. A binary random variable corresponds to each node, indicating the presence or absence of the segment in the road network. The edges in the graph represent the connectivity between segments. Interactions modeling the continuity and curvature of the network are then introduced. The results of this modeling on a radar image are shown in Figure 1.7. The radar images are extremely noisy and the noise is correlated. Therefore, the object-based approach shows its advantages in this case.

Figure 1.7.SAR image (left) and detection of the road network using a Markov field graph (right) [TUP 98]

The approach using random fields on a graph allows analysis of the image at the object level. All the same, this assumes a defined graph. For that it is necessary to know a superset of the objects being detected. That is, a preprocessing step that partially solves the problem must be applied. It is therefore interesting to be able to dynamically evolve the number of objects and their localization in the scene for a recognition or detection task. To characterize a macro-texture, it is equally desirable to consider random models of sets of objects. The objective of this book is to present the approaches that result from stochastic geometry, which enable this problem to be tackled. The idea shared by these approaches is to manage random configurations of objects. Our ambition is not to give an exhaustive mathematical description, but rather to provide the reader with the necessary tools for constructing models that can solve image analysis problems, as well as the algorithms required for these models to function, that is, to simulate or optimize them, or else to estimate their parameters. The two main frameworks that we describe here are marked point processes and random ensembles. Chapter 2 tackles modeling using marked point processes. The various elements required to define a model are presented briefly therein. The issues covered concern the detection of a set of geometrically similar objects in a scene. Chapter 3 tackles the problem of modeling macro-texture from the point of view of random ensembles. Geostatistical and morphological aspects are also detailed in this chapter. The optimization of marked point processes is the subject of Chapter 4. Discrete dynamics, based on the generalization of the Metropolis– Hastings algorithm, and continuous dynamics, based on diffusion and birth-and-death processes, are described in this chapter. The problem of estimating parameters, to obtain unsupervised algorithms, is addressed in Chapter 5. Moving from theory to practice, a range of applications related to multiple object detection are presented in Chapter 6. Some population counting applications are detailed in Chapter 7, and extraction of structured cartographic items is described in Chapter 8. Finally, Chapter 9 covers object recognition.

1 Chapter written by X. DESCOMBES.

Chapter 2

Marked Point Processes for Object Detection1

In this chapter we introduce the essential concepts that define a marked point process. Only the tools that are necessary for image analysis problems are presented. A detailed description of point processes can be found in [STO 95, BAR 99, LIE 00].

2.1. Principal definitions

Consider K, a compact subset of represents the image support, that is, the image coordinates are projected in a continuous space. A configuration of points, denoted by x, is a finite unordered set of points in K, such as {x1, … xn}. The configuration space, denoted by Ω, is therefore written as:

Let be a probability space, and let X be an application of to Ω.

For every element of the Borel set A in K, let NX (A) be the number of points of X that fall in the set A. A point process is then defined as follows:

DEFINITION 2.1.– X is a point process on K if and only if, for every element of the Borel set A in K, NX (A) is a random variable that is almost surely finite.

Later we will see that simulation of such processes is not, in theory, straightforward. Nevertheless, at this level we may note that to simulate this kind of process, it is “enough” to be given a discrete probability distribution, , to fix the number of points in the configuration, and a family of symmetric probability densities on Kn, to distribute the points in K. According to this information, we can model a classical process, namely the Poisson process:

DEFINITION 2.2.– A point process X on K is called a Poisson process with intensity measureν(.) if and only if:

– NX(A) follows a discrete Poisson distribution with expectation ν (A) for every limited Borel set A in K, and

– for κ non-intersecting Borel sets A1, A2,…, Aκ, the corresponding random variables NX(A1), NX(A2),…, NX(Aκ) are independent.

In the case of a homogeneous process (when ν(.) is proportional to the Lebesgue measure), it is sufficient to draw the number of points from a Poisson distribution with expectation λν(K), where is the intensity of the process, and then distribute the points independently using a uniform distribution on K. Figure 2.1 shows the realization of such a process.