In image analysis and computer vision, graphs have emerged as a unified representation of discrete image data. 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. Many fundamental problems in image analysis and computer vision, such as image filtering, segmentation, registration, and stereo vision, are naturally formulated as optimization problems. In this course, we will specifically study combinatorial optimization problems, formulated on graphs, arising in a wide range of applications of image analysis and computer vision. Finding a globally optimal solution to such optimization problems is a challenging computational task – in the general case, this task is typically NP-hard. There are, however, restricted classes of such problems for which efficient algorithms can be formulated. In many cases, these algorithms are guaranteed to produce globally optimal solutions in low-order polynomial time. In other cases, they can be used to produce approximate solutions, with strong guarantees on local optimality. Throughout the course, applications from image analysis and computer vision are used as motivating examples, but the methods studied in the course are fairly general and should be of interest to a more general audience in computer science and applied mathematics.
To sign up for the course, send an email to Filip Malmberg.
PhD students who complete the course recieve 5 hp. The examination is in the form of a number of mandatory tasks that should be completed. Intructions for the tasks, and some code to get you started, can be found here.
All joint activities are in room 4306, ITC, unless otherwise stated. Participation in the joint activities is not mandatory. Preliminary schedule: