Graph Based Image Processing and Combinatorial Optimization

Course description

Graphs have emerged as a unified representation for image analysis and processing. Many powerful image processing methods have been formulated on pixel adjacency graphs, i.e., a graph whose vertex set is the set of image elements (pixels), and whose edge set is determined by an adjacency relation among the image elements. Due to its discrete nature and mathematical simplicity, this graph based image representation lends itself well to the development of efficient, and provably correct, methods for image processing. In this course, we will give an overview of recent developments in this field. Topics covered include graph-based methods for:

• Combinatorial optimization
• Image segmentation
• Image registration and stereo matching
• Classification and clustering

Contact and registration

To sign up for the course, send an email to Filip Malmberg.

Examination

PhD students who complete the course recieve 3 hp.

Schedule

The course will start on September 3. All joint activities (lectures labs) are in room 4307, ITC, unless otherwise stated. Participation in the joint activities is not mandatory.

• 3/9, 10:15-12:00, Basic Graph Theory, Images as graphs. Introduction to combinatorial optimization. Notes1, Notes2
• 4/9, 10:15-12:00, Optimal spanning forests, shortest paths and Dijkstra's algorithm. Notes
• 10/9, 14:15 - 15:00, Vi2 seminar by professor Chris Ciesielski, "Hierarchical segmentation in a directed graph setting which optimizes a graph cut energy". Notes
• 11/9, 12:15-13:00, CoSy seminar by professor Chris Ciesielski, "Path-value functions for which Dijkstra's algorithm returns optimal mapping". Ångström 4003. Notes.
• 12/9, 10:15-12:00 Maximal flows, minimal cuts and energy minimization.Notes 1, Notes 2.
• 18/9, 13:15-15:00 Computer excercises. (Instructions,Source code, Linux/Mac build instructions..)
• 26/9, 10:15-12:00, Random walks and anisotropic interpolation on graphs. Notes.
  13:15-15:00, A unifying framework for energy minimization on graphs. Notes.

Recommended reading

• Ahuja, Ravindra K., et al. "A survey of very large-scale neighborhood search techniques." Discrete Applied Mathematics 123.1-3 (2002): 75-102.
• Allène, Cédric, et al. "Some links between min-cuts, optimal spanning forests and watersheds." Mathematical Morphology and its Applications to Image and Signal Processing (2007): 253-264.
• Boykov, Yuri, Olga Veksler, and Ramin Zabih. "Fast approximate energy minimization via graph cuts." IEEE Transactions on pattern analysis and machine intelligence 23.11 (2001): 1222-1239.
• Ciesielski, Krzysztof Chris, et al. "Efficient algorithm for finding the exact minimum barrier distance." Computer Vision and Image Understanding 123 (2014): 53-64.
• Couprie, Camille, et al. "Power watershed: A unifying graph-based optimization framework." IEEE transactions on pattern analysis and machine intelligence 33.7 (2011): 1384-1399..
• Cousty, Jean, et al. "Watershed cuts: Minimum spanning forests and the drop of water principle." IEEE Transactions on Pattern Analysis and Machine Intelligence 31.8 (2009): 1362-1374..
• Cousty, Jean, et al. "Watershed cuts: Thinnings, shortest path forests, and topological watersheds." IEEE Transactions on Pattern Analysis and Machine Intelligence 32.5 (2010): 925-939..
• Falcão, Alexandre X., Jorge Stolfi, and Roberto de Alencar Lotufo. "The image foresting transform: Theory, algorithms, and applications." IEEE transactions on pattern analysis and machine intelligence 26.1 (2004): 19-29.
• Falcao, Alexandre X., and Felipe PG Bergo. "Interactive volume segmentation with differential image foresting transforms." IEEE Transactions on Medical Imaging 23.9 (2004): 1100-1108..
• Grady, Leo. "Random walks for image segmentation." IEEE transactions on pattern analysis and machine intelligence 28.11 (2006): 1768-1783..
• Grady, Leo, and Eric Schwartz. "Anisotropic interpolation on graphs: The combinatorial Dirichlet problem". Boston University Center for Adaptive Systems and Department of Cognitive and Neural Systems, 2003..
• Kappes, Joerg, et al. "A comparative study of modern inference techniques for discrete energy minimization problems." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2013.
• Kolmogorov, Vladimir, and Ramin Zabih. "What energy functions can be minimized via graph cuts?." IEEE Transactions on Pattern Analysis & Machine Intelligence 2 (2004): 147-159.
• Najman, Laurent, and Jean Cousty. "A graph-based mathematical morphology reader." Pattern Recognition Letters 47 (2014): 3-17.
• Strand, Robin, et al. "The minimum barrier distance." Computer Vision and Image Understanding 117.4 (2013): 429-437.
• Wolf, Steffen, et al. "Learned Watershed: End-to-End Learning of Seeded Segmentation." ICCV. 2017.
• Wolf, Steffen, et al. "The Mutex Watershed: Efficient, Parameter-Free Image Partitioning." Proceedings of the European Conference on Computer Vision (ECCV). 2018.