This course is an introduction to the fundamentals of graph theory, graph algorithms, and mathematical morphology. Each graph notion/algorithm is used to define/implement a morphological operator that solves a practical problem of 2D or 3D image analysis. It aims to provide attendees with the ability to:
- formalize a given (image analysis) problem in
terms of graphs;
- identify whether the problem has a known solution or not; and
- in case there is no known solution, suggest a new algorithm to solve it and
evaluate its complexity.
Lectire 0 - Introduction
Lecture 1 - Graphs: basic notions
Lecture 2 - Mathematical morphology: basic operators
Practical session 1 - Dilation and Erosion: implementation and first applications
Lecture 3 - Connectivity in graphs
Exercises 1 - Cyber-profiler
Practical session 2 - Friends, bipartite graphs and cycles of odd length
Lecture 4 - Shortest paths
Exercises 2 - Back tracking a shortest path (lecture 4, slide 20) - Floyd algorithm
Practical session 3 - A journey in the metro
Lecture 5 - Distance maps, dilations and medial axis
Lecture 6 - Introduction to morphological filtering - Introduction to grayscale image processing by mathematical morphology
Practical session 4 - Application of morphological operators by structuring elements to binary and grayscale image processing
Lecture 7 - Trees
Lecture 8 - Connected operators
Practical session 5 - Application of morphological connected operators to binary and grayscale images
Lecture 9 - Minimum spanning tree
Exercise 3 - In the wood - Spy games - Analysis of trajectories
Practical session 6 - Analysis of trajectories in a bubble chamber
Lecture 10 - Watershed segmentation
On a windows operating system, the working environment settled at ESIEE for the practical sessions can be reproduced through the Linux virtual machine whose image is provided here.
In order to play this virtual machine you need to install a VMware player such as the one that can be downloaded here.
In order to uncompress it , any archiving program such as 7-zip, which can be downloaded here, can be used.
Once your virtual machine is running, you can use the account whose user id is "user" and password is "azerty".
This course is proposed by Jean
Cousty.
A part of it is inspired by the courses "Graphes et algorithmes" and
"Algorithmique
et applications en imagerie" given by Michel Couprie and Gilles Bertrand
at ESIEE Paris.