Image Processing and Analysis with Graphs

Image Processing and Analysis with Graphs

by Olivier Lezoray, Leo Grady
Released July 2017
Publisher(s): CRC Press
ISBN: 9781439855089

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Covering the theoretical aspects of image processing and analysis through the use of graphs in the representation and analysis of objects, Image Processing and Analysis with Graphs: Theory and Practice also demonstrates how these concepts are indispensible for the design of cutting-edge solutions for real-world applications.

Explores new applications in computational photography, image and video processing, computer graphics, recognition, medical and biomedical imaging

With the explosive growth in image production, in everything from digital photographs to medical scans, there has been a drastic increase in the number of applications based on digital images. This book explores how graphs—which are suitable to represent any discrete data by modeling neighborhood relationships—have emerged as the perfect unified tool to represent, process, and analyze images. It also explains why graphs are ideal for defining graph-theoretical algorithms that enable the processing of functions, making it possible to draw on the rich literature of combinatorial optimization to produce highly efficient solutions.

Some key subjects covered in the book include:

  • Definition of graph-theoretical algorithms that enable denoising and image enhancement

  • Energy minimization and modeling of pixel-labeling problems with graph cuts and Markov Random Fields

  • Image processing with graphs: targeted segmentation, partial differential equations, mathematical morphology, and wavelets

  • Analysis of the similarity between objects with graph matching

  • Adaptation and use of graph-theoretical algorithms for specific imaging applications in computational photography, computer vision, and medical and biomedical imaging

Use of graphs has become very influential in computer science and has led to many applications in denoising, enhancement, restoration, and object extraction. Accounting for the wide variety of problems being solved with graphs in image processing and computer vision, this book is a contributed volume of chapters written by renowned experts who address specific techniques or applications. This state-of-the-art overview provides application examples that illustrate practical application of theoretical algorithms. Useful as a support for graduate courses in image processing and computer vision, it is also perfect as a reference for practicing engineers working on development and implementation of image processing and analysis algorithms.

Table of contents

  1. Cover
  2. Half Title
  3. Title Page
  4. Copyright Page
  5. Dedication
  6. Preface
  7. The Editors
  8. Contributors
  9. Table of Contents
  10. 1 Graph theory concepts and definitions used in image processing and analysis
    1. 1.1 Introduction
    2. 1.2 Basic Graph Theory
    3. 1.3 Graph Representation
    4. 1.4 Paths, Trees, and Connectivity
    5. 1.5 Graph Models in Image Processing and Analysis
    6. 1.6 Conclusion
    7. Bibliography
  11. 2 Graph Cuts—Combinatorial Optimization in Vision
    1. 2.1 Introduction
    2. 2.2 Markov Random Field
    3. 2.3 Basic Graph Cuts: Binary Labels
    4. 2.4 Multi-Label Minimization
    5. 2.5 Examples
    6. 2.6 Conclusion
    7. Bibliography
  12. 3 Higher-Order Models in Computer Vision
    1. 3.1 Introduction
    2. 3.2 Higher-Order Random Fields
    3. 3.3 Patch and Region-Based Potentials
    4. 3.4 Relating Appearance Models and Region-Based Potentials
    5. 3.5 Global Potentials
    6. 3.6 Maximum a Posteriori Inference
    7. 3.7 Conclusions and Discussion
    8. Bibliography
  13. 4 A Parametric Maximum Flow Approach for Discrete Total Variation Regularization
    1. 4.1 Introduction
    2. 4.2 Idea of the approach
    3. 4.3 Numerical Computations
    4. 4.4 Applications
    5. Bibliography
  14. 5 Targeted Image Segmentation Using Graph Methods
    1. 5.1 The Regularization of Targeted Image Segmentation
    2. 5.2 Target Specification
    3. 5.3 Conclusion
    4. Bibliography
  15. 6 A Short Tour of Mathematical Morphology on Edge and Vertex Weighted Graphs
    1. 6.1 Introduction
    2. 6.2 Graphs and lattices
    3. 6.3 Neighborhood Operations on Graphs
    4. 6.4 Filters
    5. 6.5 Connected Operators and Filtering with the Component Tree
    6. 6.6 Watershed Cuts
    7. 6.7 MSF Cut Hierarchy and Saliency Maps
    8. 6.8 Optimization and the Power Watershed
    9. 6.9 Conclusion
    10. Bibliography
  16. 7 Partial difference Equations on Graphs for Local and Nonlocal Image Processing
    1. 7.1 Introduction
    2. 7.2 Difference Operators on Weighted Graphs
    3. 7.3 Construction of Weighted Graphs
    4. 7.4 p-Laplacian Regularization on Graphs
    5. 7.5 Examples
    6. 7.6 Concluding Remarks
    7. Bibliography
  17. 8 Image Denoising with Nonlocal Spectral Graph Wavelets
    1. 8.1 Introduction
    2. 8.2 Spectral Graph Wavelet Transform
    3. 8.3 Nonlocal Image Graph
    4. 8.4 Hybrid Local/Nonlocal Image Graph
    5. 8.5 Scaled Laplacian Model
    6. 8.6 Applications to Image Denoising
    7. 8.7 Conclusions
    8. 8.8 Acknowledgments
    9. Bibliography
  18. 9 Image and Video Matting
    1. 9.1 Introduction
    2. 9.2 Graph Construction for Image Matting
    3. 9.3 Solving Image Matting Graphs
    4. 9.4 Data Set
    5. 9.5 Video Matting
    6. 9.6 Conclusion
    7. Bibliography
  19. 10 Optimal Simultaneous Multisurface and Multiobject Image Segmentation
    1. 10.1 Introduction
    2. 10.2 Motivation and Problem Description
    3. 10.3 Methods for Graph-Based Image Segmentation
    4. 10.4 Case Studies
    5. 10.5 Conclusion
    6. 10.6 Acknowledgments
    7. Bibliography
  20. 11 Hierarchical Graph Encodings
    1. 11.1 Introduction
    2. 11.2 Regular Pyramids
    3. 11.3 Irregular Pyramids Parallel construction schemes
    4. 11.4 Irregular Pyramids and Image properties
    5. 11.5 Conclusion
    6. Bibliography
  21. 12 Graph-Based Dimensionality Reduction
    1. 12.1 Summary
    2. 12.2 Introduction
    3. 12.3 Classical methods
    4. 12.4 Nonlinearity through Graphs
    5. 12.5 Graph-Based Distances
    6. 12.6 Graph-Based Similarities
    7. 12.7 Graph embedding
    8. 12.8 Examples and comparisons
    9. 12.9 Conclusions
    10. Bibliography
  22. 13 Graph Edit Distance—Theory, Algorithms, and Applications
    1. 13.1 Introduction
    2. 13.2 Definitions and Graph Matching
    3. 13.3 Theoretical Aspects of GED
    4. 13.4 GED Computation
    5. 13.5 Applications of GED
    6. 13.6 Conclusions
    7. Bibliography
  23. 14 The Role of Graphs in Matching Shapes and in Categorization
    1. 14.1 Introduction
    2. 14.2 Using Shock Graphs for Shape Matching
    3. 14.3 Using Proximity Graphs for Categorization
    4. 14.4 Conclusion
    5. 14.5 Acknowledgment
    6. Bibliography
  24. 15 3D Shape Registration Using Spectral Graph Embedding and Probabilistic Matching
    1. 15.1 Introduction
    2. 15.2 Graph Matrices
    3. 15.3 Spectral Graph Isomorphism
    4. 15.4 Graph Embedding and Dimensionality Reduction
    5. 15.5 Spectral Shape Matching
    6. 15.6 Experiments and Results
    7. 15.7 Discussion
    8. 15.8 Appendix: Permutation and Doubly- stochastic Matrices
    9. 15.9 Appendix: The Frobenius Norm
    10. 15.10 Appendix: Spectral Properties of the Normalized Laplacian
    11. Bibliography
  25. 16 Modeling Images with Undirected Graphical Models
    1. 16.1 Introduction
    2. 16.2 Background
    3. 16.3 Graphical Models for Modeling Image Patches
    4. 16.4 Pixel-Based Graphical Models
    5. 16.5 Inference in Graphical Models
    6. 16.6 Learning in Undirected Graphical Models
    7. 16.7 Conclusion
    8. Bibliography
  26. 17 Tree-Walk Kernels for Computer Vision
    1. 17.1 Introduction
    2. 17.2 Tree-Walk Kernels as Graph Kernels
    3. 17.3 The Region Adjacency Graph Kernel as a Tree-Walk Kernel
    4. 17.4 The Point Cloud Kernel as a Tree-Walk Kernel
    5. 17.5 Experimental Results
    6. 17.6 Conlusion
    7. 17.7 Acknowledgments
    8. Bibliography
  27. Index

Product information

  • Title: Image Processing and Analysis with Graphs
  • Author(s): Olivier Lezoray, Leo Grady
  • Release date: July 2017
  • Publisher(s): CRC Press
  • ISBN: 9781439855089