Contents

1    Graph theory concepts and definitions used in image processing and analysis

Olivier Lézoray and Leo Grady

1.1  Introduction

1.2  Basic Graph Theory

1.3  Graph Representation

1.4  Paths, Trees, and Connectivity

1.5  Graph Models in Image Processing and Analysis

1.6  Conclusion

Bibliography

2    Graph Cuts—Combinatorial Optimization in Vision

Hiroshi Ishikawa

2.1  Introduction

2.2  Markov Random Field

2.3  Basic Graph Cuts: Binary Labels

2.4  Multi-Label Minimization

2.5  Examples

2.6  Conclusion

Bibliography

3    Higher-Order Models in Computer Vision

Pushmeet Kohli and Carsten Rother

3.1  Introduction

3.2  Higher-Order Random Fields

3.3  Patch and Region-Based Potentials

3.4  Relating Appearance Models and Region-Based Potentials

3.5  Global Potentials

3.6  Maximum a Posteriori Inference

3.7  Conclusions and Discussion

Bibliography

4    A Parametric Maximum Flow Approach for Discrete Total Variation Regularization

Antonin Chambolle and Jérôme Darbon

4.1  Introduction

4.2  Idea of the approach

4.3  Numerical Computations

4.4  Applications

Bibliography

5    Targeted Image Segmentation Using Graph Methods

Leo Grady

5.1  The Regularization of Targeted Image Segmentation

5.2  Target Specification

5.3  Conclusion

Bibliography

6    A Short Tour of Mathematical Morphology on Edge and Vertex Weighted Graphs

Laurent Najman and Fernand Meyer

6.1  Introduction

6.2  Graphs and lattices

6.3  Neighborhood Operations on Graphs

6.4  Filters

6.5  Connected Operators and Filtering with the Component Tree

6.6  Watershed Cuts

6.7  MSF Cut Hierarchy and Saliency Maps

6.8  Optimization and the Power Watershed

6.9  Conclusion

Bibliography

7    Partial difference Equations on Graphs for Local and Nonlocal Image Processing

Abderrahim Elmoataz, Olivier Lézoray, Vinh-Thong Ta, and Sébastien Bougleux

7.1  Introduction

7.2  Difference Operators on Weighted Graphs

7.3  Construction of Weighted Graphs

7.4  p-Laplacian Regularization on Graphs

7.5  Examples

7.6  Concluding Remarks

Bibliography

8    Image Denoising with Nonlocal Spectral Graph Wavelets

David K. Hammond, Laurent Jacques, and Pierre Vandergheynst

8.1  Introduction

8.2  Spectral Graph Wavelet Transform

8.3  Nonlocal Image Graph

8.4  Hybrid Local/Nonlocal Image Graph

8.5  Scaled Laplacian Model

8.6  Applications to Image Denoising

8.7  Conclusions

8.8  Acknowledgments

Bibliography

9    Image and Video Matting

Jue Wang

9.1  Introduction

9.2  Graph Construction for Image Matting

9.3  Solving Image Matting Graphs

9.4  Data Set

9.5  Video Matting

9.6  Conclusion

Bibliography

10  Optimal Simultaneous Multisurface and Multiobject Image Segmentation

Xiaodong Wu, Mona K. Garvin, and Milan Sonka

10.1  Introduction

10.2  Motivation and Problem Description

10.3  Methods for Graph-Based Image Segmentation

10.4  Case Studies

10.5  Conclusion

10.6  Acknowledgments

Bibliography

11  Hierarchical Graph Encodings

Luc Brun and Walter Kropatsch

11.1  Introduction

11.2  Regular Pyramids

11.3  Irregular Pyramids Parallel construction schemes

11.4  Irregular Pyramids and Image properties

11.5  Conclusion

Bibliography

12  Graph-Based Dimensionality Reduction

John A. Lee and Michel Verleysen

12.1  Summary

12.2  Introduction

12.3  Classical methods

12.4  Nonlinearity through Graphs

12.5  Graph-Based Distances

12.6  Graph-Based Similarities

12.7  Graph embedding

12.8  Examples and comparisons

12.9  Conclusions

Bibliography

13  Graph Edit Distance—Theory, Algorithms, and Applications

Miquel Ferrer and Horst Bunke

13.1  Introduction

13.2  Definitions and Graph Matching

13.3  Theoretical Aspects of GED

13.4  GED Computation

13.5  Applications of GED

13.6  Conclusions

Bibliography

14  The Role of Graphs in Matching Shapes and in Categorization

Benjamin Kimia

14.1  Introduction

14.2  Using Shock Graphs for Shape Matching

14.3  Using Proximity Graphs for Categorization

14.4  Conclusion

14.5  Acknowledgment

Bibliography

15  3D Shape Registration Using Spectral Graph Embedding and Probabilistic Matching

Avinash Sharma, Radu Horaud, and Diana Mateus

15.1  Introduction

15.2  Graph Matrices

15.3  Spectral Graph Isomorphism

15.4  Graph Embedding and Dimensionality Reduction

15.5  Spectral Shape Matching

15.6  Experiments and Results

15.7  Discussion

15.8  Appendix: Permutation and Doubly- stochastic Matrices

15.9  Appendix: The Frobenius Norm

15.10  Appendix: Spectral Properties of the Normalized Laplacian

Bibliography

16  Modeling Images with Undirected Graphical Models

Marshall F. Tappen

16.1  Introduction

16.2  Background

16.3  Graphical Models for Modeling Image Patches

16.4  Pixel-Based Graphical Models

16.5  Inference in Graphical Models

16.6  Learning in Undirected Graphical Models

16.7  Conclusion

Bibliography

17  Tree-Walk Kernels for Computer Vision

Zaid Harchaoui and Francis Bach

17.1  Introduction

17.2  Tree-Walk Kernels as Graph Kernels

17.3  The Region Adjacency Graph Kernel as a Tree-Walk Kernel

17.4  The Point Cloud Kernel as a Tree-Walk Kernel

17.5  Experimental Results

17.6  Conlusion

17.7  Acknowledgments

Bibliography

Index