Image Processing and Analysis with Graphs

Olivier Lézoray received his B.Sc. in mathematics and computer science, as well as his M.Sc. and Ph.D. degrees from the Department of Computer Science, University of Caen, France, in 1992, 1996, and 2000, respectively. From September 1999 to August 2000, he was an assistant professor with the Department of Computer Science at the University of Caen. From September 2000 to August 2009, he was an associate professor at the Cherbourg Institute of Technology of the University of Caen, in the Communication Networks and Services Department. In July 2008, he was a visiting research fellow at the University of Sydney, Australia. Since September 2009, he has been a full professor at the Cherbourg Institute of Technology of the University of Caen, in the Communication Networks and Services Department. He also serves as Chair of the Institute Research Committee. In 2011 he cofounded Datexim and is a member of the scientific board of the company, which brought state-of-art image and data processing to market with applications in digital pathology. His research focuses on discrete models on graphs for image processing and analysis, image data classification by machine learning, and computer-aided diagnosis. Leo Grady received his B.Sc. degree in electrical engineering from the University of Vermont in 1999 and a Ph.D. degree from the Cognitive and Neural Systems Department at Boston University in 2003. Dr. Grady was with Siemens Corporate Research in Princeton, where he worked as a Principal Research Scientist in the Image Analytics and Informatics division. He recently left Siemens to become Vice President of R&D at HeartFlow. The focus of his research has been on the modeling of images and other data with graphs. These graph models have generated the development and application of tools from discrete calculus, combinatorial/continuous optimization, and network analytics to perform analysis and synthesis of the images/data. The primary applications of his work have been in computer vision and biomedical applications. Dr. Grady currently holds 30 granted patents with more than 40 additional patents currently under review. He has also contributed to more than 20 Siemens products that target biomedical applications and are used in medical centers worldwide.

Graph Theory Concepts and Definitions Used in Image Processing and Analysis, O. Lezoray and L. Grady


Introduction


Basic Graph Theory


Graph Representation


Paths, Trees, and Connectivity


Graph Models in Image Processing and Analysis






Graph Cuts—Combinatorial Optimization in Vision, H. Ishikawa


Introduction


Markov Random Field


Basic Graph Cuts: Binary Labels


Multi-Label Minimization


Examples






Higher-Order Models in Computer Vision, P. Kohli and C. Rother


Introduction


Higher-Order Random Fields


Patch and Region-Based Potentials


Relating Appearance Models and Region-Based Potentials


Global Potentials


Maximum a Posteriori Inference






A Parametric Maximum Flow Approach for Discrete Total Variation Regularization, A. Chambolle and J. Darbon


Introduction


Idea of the approach


Numerical Computations


Applications






Targeted Image Segmentation Using Graph Methods, L. Grady


The Regularization of Targeted Image Segmentation


Target Specification


Conclusion






A Short Tour of Mathematical Morphology on Edge and Vertex Weighted Graphs, L. Najman and F. Meyer


Introduction


Graphs and lattices


Neighborhood Operations on Graphs


Filters


Connected Operators and Filtering with the Component Tree


Watershed Cuts


MSF Cut Hierarchy and Saliency Maps


Optimization and the Power Watershed






Partial Difference Equations on Graphs for Local and Nonlocal Image Processing, A. Elmoataz, O. Lezoray, V.-T. Ta, and S. Bougleux


Introduction


Difference Operators on Weighted Graphs


Construction of Weighted Graphs


p-Laplacian Regularization on Graphs


Examples






Image Denoising with Nonlocal Spectral Graph Wavelets, D.K. Hammond, L. Jacques, and P. Vandergheynst


Introduction


Spectral Graph Wavelet Transform


Nonlocal Image Graph


Hybrid Local/Nonlocal Image Graph


Scaled Laplacian Model


Applications to Image Denoising


Conclusions


Acknowledgments






Image and Video Matting, J. Wang


Introduction


Graph Construction for Image Matting


Solving Image Matting Graphs


Data Set


Video Matting






Optimal Simultaneous Multisurface and Multiobject Image Segmentation, X. Wu, M.K. Garvin, and M. Sonka


Introduction


Motivation and Problem Description


Methods for Graph-Based Image Segmentation


Case Studies


Conclusion


Acknowledgments






Hierarchical Graph Encodings, L. Brun and W. Kropatsch


Introduction


Regular Pyramids


Irregular Pyramids Parallel construction schemes


Irregular Pyramids and Image properties






Graph-Based Dimensionality Reduction, J.A. Lee and M. Verleysen


Summary


Introduction


Classical methods


Nonlinearity through Graphs


Graph-Based Distances


Graph-Based Similarities


Graph embedding


Examples and comparisons






Graph Edit Distance—Theory, Algorithms, and Applications, M. Ferrer and H. Bunke


Introduction


Definitions and Graph Matching


Theoretical Aspects of GED


GED Computation


Applications of GED






The Role of Graphs in Matching Shapes and in Categorization, B. Kimia


Introduction


Using Shock Graphs for Shape Matching


Using Proximity Graphs for Categorization


Conclusion


Acknowledgment






3D Shape Registration Using Spectral Graph Embedding and Probabilistic Matching, A. Sharma, R. Horaud, and D. Mateus


Introduction


Graph Matrices


Spectral Graph Isomorphism


Graph Embedding and Dimensionality Reduction


Spectral Shape Matching


Experiments and Results


Discussion


Appendix: Permutation and Doubly- stochastic Matrices


Appendix: The Frobenius Norm


Appendix: Spectral Properties of the Normalized Laplacian






Modeling Images with Undirected Graphical Models, M.F. Tappen


Introduction


Background


Graphical Models for Modeling Image Patches


Pixel-Based Graphical Models


Inference in Graphical Models


Learning in Undirected Graphical Models






Tree-Walk Kernels for Computer Vision, Z. Harchaoui and F. Bach


Introduction


Tree-Walk Kernels as Graph Kernels


The Region Adjacency Graph Kernel as a Tree-Walk Kernel


The Point Cloud Kernel as a Tree-Walk Kernel


Experimental Results


Conclusion


Acknowledgments