Optimisation in Signal and Image Processing

Patrick Siarry

• Publisher: Wiley-ISTE
• Year: 2013
• Print ISBN: 9781848210448
• eBook ISBN: 9781118623671
• Edition: 1
• Topic: Technology & Engineering
• Subtopic: Signals & Signal Processing
• Index: Technology & Engineering

This book describes the optimization methods most commonly encountered in signal and image processing: artificial evolution and Parisian approach; wavelets and fractals; information criteria; training and quadratic programming; Bayesian formalism; probabilistic modeling; Markovian approach; hidden Markov models; and metaheuristics (genetic algorithms, ant colony algorithms, cross-entropy, particle swarm optimization, estimation of distribution algorithms, and artificial immune systems).

Chapter 1

Modeling and Optimization in Image Analysis ^a

1.1. Modeling at the source of image analysis and synthesis

From its first days, image analysis has been facing the problem of modeling. Pioneering works on contour detection led their authors to refer to explicit models of edges and noise [PET 91], which they used as a conceptual basis in order to build their algorithms. With an opposite approach to these phenomenological models, a physical model of light diffusion on surfaces has been used as the basis for Horn’s works [HOR 75] on shape from shading. More generally, a phenomenological model aims at describing a directly computable property of the geometric configurations of gray levels on an image; the physical model then tries to use the knowledge corpus of physics, or even sometimes to create an ad-hoc conceptual system, as we will see later. Between these two extremes, there is a large number of approaches to modeling. Here, we shall try to illustrate them using some examples.

It is important to first show the links between image analysis and synthesis. For a number of years, these two domains have been undergoing largely independent development processes. In spite of their conceptual similarity, they have been dealt with by two separate scientific communities, with different origins and centers of interest, which did not address the same applications. Robotics is one of the few fields of application that has played an important role in moving them closer to one another. Image synthesis addresses another large panel of approaches to modeling, in particular in the fields of geometry, rendering and motion modeling – to such an extent that there are important international communities, journals and conferences that specialize in each of these approaches to modeling. One of the benefits of connecting image analysis and image synthesis comes from the fact these two domains often use common modeling techniques which they use as bridges to their constructive interaction.

1.2. From image synthesis to analysis

One of the difficult points in image analysis and machine vision is algorithm validation methods. In most cases it is not possible to access the “ground truth” that corresponds to the image or the image sequence on which we want to evaluate the quality of the analysis process. A frequent compromise consists of evaluating an algorithm by referring to another algorithm, which is seldom acceptable. The ideal, straightforward solution would consists of creating a synthesis tool – and therefore a model – able to build dependable test data from any ground truth.

Once the effort of building such a model has been carried out, we naturally arrive at the idea of incorporating into the image analysis algorithm, the knowledge of the physical world and its rules, following an “artificial intelligence” approach. This can be done implicitly (using the same knowledge corpus and coding it in a way suitable to the analysis algorithm) or alternatively by explicitly incorporating the model into the analysis process. Of course, this raises the delicate ethical question of mutually validating two algorithms running the same model, and therefore susceptible to containing the same errors or clumsy simplifications. In any case, this is, when pushed to its extreme, the basis of the so-called “analysis by synthesis” approaches where rather than the model (whether photometric, geometric, kinematic or physical), it is the whole image synthesis process that is embedded into the analysis algorithm. Between merely using general physical knowledge in the analysis process, and at the other end, embedding a complete synthesis process into the analysis algorithm, it appears that the image analysis techniques explicitly exploiting a model are undergoing an important development, particularly thanks to modern optimization techniques, as we will see in several examples.

First, we will examine the classical approaches to image segmentation and show how they have built their organization, often implicitly, after the way scene models used in image synthesis are naturally organized.

In the next section, we will revisit the Hough transform [HOU 62], which is probably the best known example of image analysis and model inversion, through deterministic, exhaustive search in a parameter space; the model used here is phenomenological (visual alignment). We show the Hough transform and its generalizations may be rewritten into an evolutionary optimization version; as a stochastic exploration of a parameter space, here each point represents a particular instance of a model. This considerably widens the field of potential applications of the original Hough transform.

The following part will quickly examine the contribution of physical models to image analysis. This is a promising yet little known topic we will discover through two examples using photometric and dynamic models.

In some applications, the model underlying the analysis technique may be taken apart into elementary objects whose collective behavior actually represents the object to be modeled. A specific evolutionary optimization method, called “Parisian Evolution”, can then be implemented. This is a change in the semantics of the evolved population but a classical evolutionary process is still applied to the elementary objects. This will be the subject of Chapter 2.

1.3. Scene geometric modeling and image synthesis

As discussed earlier, image contour segmentation took its foundations from hypotheses about image signals, resulting into a wide use of differential operators as main analysis tools. Region segmentation, which was developed later, probably because of its greater need for computational power, brought more evidence of the strong link between the structures of a 3D scene and the image entities directly accessible to calculation. It is therefore tempting to revisit the notion of image segmentation [COC 95, GON 92] through its possible interpretations in terms of scene models.

Seen from this point of view, segmentation into regions could be defined as any image partitioning technique such that each region entity it extracts is a good candidate image projection of a 3D or space-time varying physical object in the scene.

Similarly, it is possible to give a new definition of contour segmentation: it describes any image line extraction technique such that each line extracted is likely to be the image projection of an edge of a physical object present in the scene.

With each level of primitives in the polyhedral model (vertex, edge, facet, etc.) it is possible to associate a probable local property of the image, such as the contrast along a line, the homogenity of a region, etc., and a corresponding calculation technique. Classical segmentation techniques are often a decisive step in the process of instantiating the model as efficient model exploration heuristics; contours usually are the projection of the subset of the scene where the probability of finding an edge is highest, thus the knowledge of contours contributes to the efficiency of the exploration of the space of parameters which describe the possible positions of edges. Similarly, interest points give useful hints on where to look for polyhedron vertices, and so on.

One of the consequences is that the pertinence of a segmentation technique on a class of images essentially depends on whether it actually corresponds to an observable characteristic of the model underlying the class of scenes and how the images have been captured, An illustration of this is given by fluid flow imaging, where polyhedral models are irrelevant and classical contour or region segmentation techniques are just as irrelevant. Segmentation techniques are the translation of the scene-specific description language.

The primary role of image analysis is to instantiate or identify the parameters of a general scene model. If we consider scenes made from opaque objects, which is not too bad in most familiar scenes, the most widely used modeling language in image analysis, as in synthesis, is based on polyhedral objects. The ultimate goal of image segmentation should ideally be to provide a description of the scene using the same primitives and language as in image synthesis: a geometrical description (polyhedra, facets, edges, vertices), completed (if useful to the application) with a photometric description (light sources, radiance factors, diffusion coefficients, etc.). In the case of time-dependent sequences, it will be necessary to include object motion and deformations, and the analysis may even include the building of a description of the scene in terms of agents, individual behaviors and physical interaction [LUC 91].

In all these cases, “informing the model” means optimizing the likeness between real data and data synthesized from the scene model, and therefore will generally involve the optimization of a cost or resemblance function.

1.4. Direct model inversion and the Hough transform

1.4.1. The deterministic Hough transform

One of the main motivations of the development of image segmentation techniques is the difficulty of directly resolving the problem of optimizing a scene model using classical methods. However, a well known exception to the rule is given by the Hough transform [HOU 62, B...

Table of contents

• Cover
• Title Page
• Copyright
• Introduction
• Chapter 1: Modeling and Optimization in Image Analysis
• Chapter 2: Artificial Evolution and the Parisian Approach. Applications in the Processing of Signals and Images
• Chapter 3: Wavelets and Fractals for Signal and Image Analysis
• Chapter 4: Information Criteria: Examples of Applications in Signal and Image Processing
• Chapter 5: Quadratic Programming and Machine Learning – Large Scale Problems and Sparsity
• Chapter 6: Probabilistic Modeling of Policies and Application to Optimal Sensor Management
• Chapter 7: Optimizing Emissions for Tracking and Pursuit of Mobile Targets
• Chapter 8: Bayesian Inference and Markov Models
• Chapter 9: The Use of Hidden Markov Models for Image Recognition: Learning with Artificial Ants, Genetic Algorithms and Particle Swarm Optimization
• Chapter 10: Biological Metaheuristics for Road Sign Detection
• Chapter 11: Metaheuristics for Continuous Variables. The Registration of Retinal Angiogram Images
• Chapter 12: Joint Estimation of the Dynamics and Shape of Physiological Signals through Genetic Algorithms
• Chapter 13: Using Interactive Evolutionary Algorithms to Help Fit Cochlear Implants
• List of Authors
• Index