Preface
The last two decades have witnessed the explosive growth of image production from digital photographs to the medical scans, satellite images, and video films. Consequently, the number of applications based on digital images has drastically increased, including multimedia integration, computer animation, video games, communication and digital arts, medicine, biometry, etc. Although being very different from one another, all these application areas rely on similar image processing and analysis techniques. The field of image or video processing analysis is very broad, encompassing a wide variety of research issues from low-level processing (such as image enhancement, restoration, and segmentation) to high-level analysis (semantic object extraction, indexing databases of images, and computer-human interaction).
Recently, graphs have emerged as a unified representation for the processing and the analysis of images. The number of concepts that can be defined with graphs is very large. In particular, many real-world problems have been successfully modeled using graphs. Consequently, graph theory has found many developments and applications for image processing and analysis, particularly due to the suitability of graphs to represent any discrete data by modeling neighborhood relationships. Different graph models have been proposed for image analysis, depending on the structures to analyze. However, graphs are not only of interest for representing the data to process, but also for defining graph-theoretical algorithms that enable the processing of functions associated with graphs. Additionally, representing problems with graphs makes it possible to draw on the rich literature of combinatorial optimization to produce highly efficient solutions. This research topic is timely, very influential in computer science and has led to many applications in denoising, enhancement, restoration, and object extraction. Consequently, graphs have become indispensable for the development of cutting-edge research and applications in image processing and analysis.
With the rapid development of graphs in image processing and analysis, the book aims at providing a comprehensive overview of the current state-of-the-art. The book not only covers the theoretical aspects of image processing with graphs but also demonstrates how these concepts can be used to design cutting-edge solutions to real world applications. Due to the wide variety of problems being solved with graphs in image processing and computer vision, the book has the form a contributed volume in which each chapter addresses a specific technique or application and is written by renowned experts in the field.
The intended audience for the book is graduate and postgraduate students, researchers, and practitioners. The aim is first to provide students and researchers with a state-of-the-art view of the important ideas involved in the use of graphs in image processing and analysis. Secondly, the book provides application examples showing how the theoretical algorithms can be applied in practice. Therefore, the book can serve as a support for graduate courses in image processing and computer vision as well as a reference for practicing engineers for the development and implementation of image processing and analysis algorithms.
The book begins with an introduction chapter to graph theory basics to make the book self-contained, establish notation and address some particulars of how graphs are used to model images. The rest of the book contains chapters that focus on either techniques for representing images with graphs or on the use of graph-based algorithms to solve problems in image processing and computer vision.
The first part of the book therefore starts with chapters on low level processing with graph-based image processing.
Many of the problems that arise in machine vision can be naturally expressed in terms of energy minimization. For instance, many computer vision problems require the assignment of labels to pixels (e.g., image restoration, disparity estimation and object recognition) and finding the best labelling can be seen as an optimization problem. Minimum cut/maximum network flow algorithms have emerged as an efficient and useful tool for exact or approximate energy minimization. Chapters 2, 3, and 4 are dedicated to this topic. Chapter 2 describes a class of combinatorial optimization methods called graph cuts. After introducing the energy minimization formalisms used in the image-related areas, the graph-cut algorithm is described for the binary case, which is the most fundamental one where the energy-minimization problem directly translates to the minimum-cut problem. Next, the case of graph cuts where there are more than two labels to be assigned to each pixel is considered. Chapter 3 considers labeling problems modeled via Markov Random Fields (MRF). The standard MRF formulations for such problems employ pair-wise potentials defined over pairs of random variables and are often insufficient to completely model the complexities of a problem. Novel families of higher order potentials, i.e., potentials defined over multiple variables, have therefore higher modeling power and lead to more accurate models. This chapter presents provides an overview of various types of higher-order random field models that have been considered in the past. Patch or region-based potentials, and global potentials enforcing topology constraints and label statistics are described, as well as methods to perform inference in these models. Chapter 4 presents an efficient algorithm for minimizing the total variation plus a convex and separable data fidelity term (not necessarily differentiable). The approach relies on mapping the original problem into a parametric network flow problem that can be solved using efficient maximum-flow algorithms. Extension to non separable convex data fidelity terms, such as the convolution with a linear operator (for deconvolution problems), is also considered.
Chapters 5, 6, 7, and 8 focus on defining graph-theoretical algorithms that enable the processing of functions associated with graph vertices and/or edges for image processing tasks. Chapter 5 deals with targeted image segmentation to localize a single, particular object. Methods for specifying the target object fit naturally with graph techniques, which optimize a combination of a unary term and a binary term. The chapter reviews alternative methods for specifying a target object from known information in the context of a graph algorithm and the use of graph-based algorithms for producing the segmentation from the target information. Chapter 6 describes how mathematical morphology can be defined on edge-weighted graphs. First, lattices making it possible to compare weighted and non weighted edges and vertices are introduced, and morphological operators and filters on graphs are detailed. Second, it is shown that the watershed has very strong links with the minimum spanning tree and can be used for building hierarchies of segmentations as well as an optimization tool. Chapter 7 presents a framework called partial difference equations on graphs to solve partial differential equations (PDEs) on graphs. The proposed framework mimics on graphs well-known PDEs variational formulations under a functional analysis point of view, and unifies local and nonlocal processing. In particular, a nonlocal discrete regularization on graphs of arbitrary topologies is introduced as a framework for data simplification and interpolation (label diffusion, inpainting, colorisation). Chapter 8 focuses on constructing wavelet transforms of functions defined on graph and introduce the spectral graph wavelet transform (SGWT). The SGWT construction is based on defining scaling using the the graph analogue of the Fourier domain, namely, the spectral decomposition of the discrete graph Laplacian. Using the SGWT construction with a nonlocal image graph gives a nonlocal graph wavelet transform well-suited to solve inverse problems such as denoising.
Chapters 9 and 10 present how the graph-theoretical algorithms can be adapted and used in practice for specific imaging applications in computational photography and medical imaging. Chapter 9 considers image and video matting, which is the problem of accurate foreground estimation. Matting is one of the key techniques in various image editing and film production applications. A comprehensive review of recent state-of-the-art approaches are described and how they use various graph regularization methods to achieve accurate and stable results. Chapter 10 describes a general methodology for optimal segmentation of single or multiple interacting surfaces that is applicable to n-D image data. The utility of the reported segmentation methods is demonstrated in practical examples from medical image analysis in which accurate and reliable image segmentation is of paramount importance.
The second part of the book continues with chapters on high-level processing using graph-based image analysis.
Chapter 11 presents a rigorous review of regular and irregular pyramids to encode image content with hierarchical graph encoding. The search for efficient data structures encoding pyramids is vital, as the complexity of the data structure is a limiting factor to the utility of pyramids in applications. After describing the main properties and drawbacks of regular pyramids, irregular pyramids are introduced as well as the associated construction schemes (e.g., maximal independent set, maximal independent directed edge set, and data-driven decimation). The construction scheme of a pyramid determines its decimation ratio and can be understood as the pyramids vertical dynamic. Then, three types of irregular pyramids are described using a generic notion of contraction kernel: simple graphs, dual graphs, and combinatorial pyramids. The choice of a given graph model determines which set of topological and geometrical image properties can be encoded at each level.
Graphs are a general and powerful data structure for the representation of objects and concepts. In a graph representation, the nodes typically represent objects or parts of objects, while the edges describe relations between objects or object parts (as detailed in Chapter 11). In applications such as pattern recognition and computer vision, object similarity is an important issue. If graphs are used for object representation this problem turns into determining the similarity of graphs, which is generally referred to as graph matching. For large graphs, graph matching often relates to graph embedding, which is a mapping from a graph or a set of graphs to a vectorial space. The purpose of graph embedding and more generally of graph-based methods for dimensionality reduction is to represent each vertex of a graph as a low-dimensional vector that preserves similarities between the vertex pairs, where similarity is measured by a graph similarity matrix that characterizes certain statistical or geometric properties of the data set. Chapters 12, 13, 14, and 15 deal with both graph-based dimensionality reduction and graph matching. Chapter 12 reviews some of the most prominent dimensionality reduction methods that rely on graphs. These include several techniques based on geodesic distances, such as Isomap and its variants. Spectral methods involving a graph Laplacian are described as well. More biologically inspired techniques, such as the self-organizing map, identify a topographic mapping between a predefined graph and the data manifold. Chapter 13 reviews the graph edit distance (GED) from three different points of view, namely, theory, algorithms, and applications. Indeed, two approaches to graph matching can be found: exact and inexact (or error-tolerant) graph matching. The graph edit distance (GED) is the basis of inexact graph matching, and has emerged as an important way to measure the similarity between pairs of graphs in an error-tolerant fashion. The chapter introduces fundamental concepts related to GED with an emphasis on the theory underlying the edit distance cost function, gives an introduction to GED computation (exact and approximate), and concludes with some GED applications. Chapter 14 reviews the role of graphs in matching shapes and in categorization. This chapter explores the value of graphs in computer vision from the perspective of representing both structural quantum variations as well as metric changes, as applied to the matching and categorization problems. It provides an overview on the use of shock graphs in matching and recognition, and proximity graphs in categorization. Chapter 15 addresses the problem of 3D shape registration and presents a technique based on spectral graph theory and probabilistic matching. This chapter extends the spectral graph matching methods to very large graphs by combining spectral graph matching with Laplacian embedding.
Chapters 16 and 17 conclude the book and concentrate on Graphical Models and Kernels methods in computer vision. Chapter 16 discusses mathematical models of images that can be represented with graphs, known as graphical models. The chapter reviews the fundamental theory, problems, and algorithms involved in using graphical models to solve computer vision problems. Graphical models are a powerful tool for constructing mathematical models that are rich enough to express to the complexity of the world pictured in each image, but are also computationally tractable and easy to design. Moreover, they make it possible to construct global models out of a collection of local relationships. Kernel-based methods have also proven to be highly effective in many applications because of their wide generality. As soon as a similarity measure leading to a symmetric positive-definite kernel can be designed, a wide range of learning algorithms working on Euclidean dot-products of the examples can be used, such as support vector machines. A recent line of research consists in designing kernels for structured data such as graphs. Chapter 17 presents a family of positive-definite kernels between images, making it possible to compute image similarity measures respectively in terms of color and of shape. The kernels consist of matching subtree-patterns called “tree-walks” of graphs extracted from the images. Computationally efficient kernels that can be computed in polynomial-time in the size of the graphs are also detailed.
Complementary material is available on the book companion website at
http://greyc.stlo.unicaen.fr/lezoray/IPAG
We would like to thank all the contributors for their effort in preparing chapters as well as incorporating suggestions from us and colleagues in the field who served as reviewers. We also thank CRC Press for giving us the opportunity to edit a book on image processing and analysis with graphs. In particular, we would like to thank Dr. Rastislav Lukac, editor of the Digital Imaging and Computer Vision book series, for initiating this project, and Nora Konopka for her support and assistance.
Olivier Lézoray and Leo Grady
Université de Caen Basse-Normandie
Siemens Corporate Research