Program
The program is available as pdf here
The summer school will contain lectures and exercises mainly covered by the four invited speakers. Local speakers will provide examples of graph-based methods in their research and relate the topic to the research at DIKU and DTU Informatics. In addition to the scientific program there will be social activities including outdoor events Wednesday afternoon and the summer school dinner Thursday evening.
Invited lecturers
Ali Shokoufandeh
Ali Shokoufandeh will be introducing the basic definitions of graphs as well as provide an overview of algorithmic graph theory; this will cover a diverse range, from basic topics and simple algorithms to more advanced topics, including shock graphs for shape matching.
In his Second lecture, he will talk about the geometry of graphs and an overview of basic results related to embedding graphs into metric spaces. He will discuss how basic embedding techniques can be used for solving the sparsest cut and flux minimization problems. He will continue this lecture by covering topics in spectral graph theory and their applications to graph matching, and image segmentation problems.
In his third lecture, Ali will talk about approximation algorithms and using semi-definite programming techniques for solving a variation of hitting sets known as the canonical set problem. He will discuss the applications of canonical sets to 3D view-based object recognition and image feature selection problem. A high-level formulation of the problem using nonlinear optimization will be followed by the overview of techniques for approximating the canonical set problem. Sample experimental results will conclude this lecture.
The topic of Ali Shokoufandeh's final lecture will be on the use of embedding techniques for graph matching problem. He will discuss how graphs can be embedded into geometric spaces, reducing the many-to-many graph matching problem to a weighted point matching problem, for which efficient many-to-many matching algorithms exist.
Slides:
- Lecture 1: Graphs: Introduction
- Lecture 2: Embedding and Spectrum of Graphs
- Lecture 3: Canonical Sets in Graphs
- Lecture 4: Many to Many Matching in Graphs
Suggested reading material:
- M. Fatih Demirci, Yusuf Osmanlioglu, Ali Shokoufandeh, Sven J. Dickinson: Efficient many-to-many feature matching under the l1 norm. Computer Vision and Image Understanding 115(7): 976-983 (2011)
- M. Fatih Demirci, Ali Shokoufandeh, Sven J. Dickinson, Yakov Keselman, Lars Bretzner: Many-to-Many Feature Matching Using Spherical Coding of Directed Graphs. ECCV (1) 2004: 322-335
- John Novatnack, Trip Denton, Ali Shokoufandeh, Lars Bretzner: Stable Bounded Canonical Sets and Image Matching. EMMCVPR 2005: 316-331
- M. Fatih Demirci, Ali Shokoufandeh, Yakov Keselman, Lars Bretzner, Sven J. Dickinson: Object Recognition as Many-to-Many Feature Matching. International Journal of Computer Vision 69(2): 203-222 (2006)
- M. Fatih Demirci, Bram Platel, Ali Shokoufandeh, Luc Florack, Sven J. Dickinson: The Representation and Matching of Images Using Top Points. Journal of Mathematical Imaging and Vision 35(2): 103-116 (2009)
- Frans Kanters, Trip Denton, Ali Shokoufandeh, Luc Florack, Bart M. ter Haar Romeny: Combining Different Types of Scale Space Interest Points Using Canonical Sets. SSVM 2007: 374-385
- Trip Denton. 2007. Subset Selection Using Nonlinear Optimization. Ph.D. Dissertation. Drexel University, Philadelphia, PA, USA. Advisor(s) Ali Shokoufandeh. AAI3259958
Martin Reuter
Laplace-Beltrami Eigenstuff
Martin Reuter will be talking about the Laplace operator and its properties, useful in many different applications. He will describe the relationship between the graph Laplacian, the mesh Laplacian and the FEM approach, which can be extended to higher order approximations. For the mesh and FEM approach surfaces or volumes are represented as simplices that may be understood as nodes/points connected by edges, i.e. graphs with additional geometric information. The Laplace-Beltrami operator (Laplace operator on manifolds) can be applied to these discretization, allowing for accurate computation of Eigenvalues and Eigenfunctions of the represented shapes. These spectral values are isometry invariant and therefore important in many applications dealing with non-rigid shapes such as shape matching, shape analysis and segmentation/correspondence.
Practical examples include statistical shape analysis of subcortical structures in the human brain between diseased and healthy subjects.
Slides:
Exercises
The exercises will be in Matlab and deal with the computation and application of spectral entities for triangle meshes. If you like bring some meshes (in OFF format, 2D manifolds with no boundary) to play with.
- Exercise slides and accompanying Matlab files (tar)
- Matlab script with solutions
Useful links:
- OFF format documentation can be found at http://www.geomview.org/docs/html/OFF.html
- Martin Reuter's shape DNA software http://reuter.mit.edu/software/shapedna/
- Shape retrieval contest with links to several shape databases http://www.itl.nist.gov/iad/vug/sharp/contest/2011/NonRigid/
Suggested reading material:
- Martin Reuter, Franz-Erich Wolter, Niklas Peinecke , Laplace-Beltrami spectra as 'Shape-DNA' of surfaces and solids, Computer-Aided Design 38(4), pp. 342-366, 2006.
- M. Reuter, F.-E. Wolter, M. Shenton, M. Niethammer. Laplace-Beltrami Eigenvalues and Topological Features of Eigenfunctions for Statistical Shape Analysis. Computer-Aided Design 41 (10), pp.739-755, 2009.
- M. Reuter. Hierarchical Shape Segmentation and Registration via Topological Features of Laplace-Beltrami Eigenfunctions. International Journal of Computer Vision 89 (2), pp. 287-308, 2010.
Marcello Pelillo
Game Theory in Graph-Based Computer Vision and Pattern recognition
The development of game theory in the early 1940's by John von Neumann was a reaction against the then dominant view that problems in economic theory can be formulated using standard methods from optimization theory. Indeed, most real- world economic problems typically involve conflicting interactions among decision-making agents that cannot be adequately captured by a single (global) objective function, thereby requiring a different, more sophisticated treatment. Accordingly, the main point made by game theorists is to shift the emphasis from optimality criteria to equilibrium conditions. As it provides an abstract theoretically-founded framework toelegantly model complex scenarios, game theory has found a variety of applications not only in economics and, more generally, social sciences but also in different fields of engineering and information technologies. In particular, in the past there have been various attempts aimed at formulating problems in computer vision, pattern recognition and machine learning from a game-theoretic perspective and, with the recent development of algorithmic game theory, the interest in these communities around game-theoretic models and algorithms is growing at a fast pace.
The goal of this short course is to offer an introduction to the basic concepts of game theory and to provide an overview of recent work on the use of game-theoretic models in graph-based computer vision and pattern recognition problems.
Slides:
- Lecture 1: Introduction to game theory
- Lecture 2: Evolutionary games and graph-based data clustering
- Lecture 3: Graph labeling problems and graph transduction
Exercises
At the end of the first lecture, the class will be asked to split in sub-groups each of which will be assigned a short paper, related to the contents of the course, to read and comment. To make the study more profitable and active, in the final part of the exercise slot, scheduled for the second day, a representative from each group will be asked to provide a mini-presentation (around 5 minutes) of the assigned paper.
Suggested reading material
- M. Pelillo. What is a Cluster? Perspectives from Game Theory. Proc. NIPS 2009: Neural Information Processing Systems Workshop on "Clustering: Science or Art?", Canada, 2009
- M. Pavan and M. Pelillo, Dominant sets and pairwise clustering. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 29(1):167-172, 2007
- A. Torsello, S. Rota Bulo', and M. Pelillo Grouping with asymmetric affinities: A game-theoretic perspective Proc. CVPR 2006 -- IEEE International Conference on Computer Vision and Pattern Recognition, New York, June 2006
- M. Pelillo, The dynamics of nonlinear relaxation labeling processes. > Journal of Mathematical Imaging and Vision, 7(4):309-323, 1997
- A. Erdem and M. Pelillo, Graph transduction as a non-cooperative game. > Proc GbR 2011, Munich, Germany, May 2011
Michael Gleicher
Motion Synthesis By Example
Michael Gleicher will give lectures on motion graphs, with the foundations of human movement synthesis for animation, on which he has done a considerable amount of work. This has become the dominant approach over the past decade. Michael Gleicher will give three lectures organized as follows:
First lecture will give an overview of the problems of motion synthesis, with a focus on application in computer games. The idea would be to motivate the idea of "synthesis by example" and to introduce the basic building blocks of most approaches: concatenation (graphs) and blending.
In his second lecture Gleicher will give an introduction to Motion Graphs, with some of the details and issues (like how matching is performed). Match webs and match graphs, linking together different motion sequences, will be treated. Also ideas of blending-based synthesis will be described. (in the style of Kovar&Gleicher 2002)
In his third and final lecture a survey of some of the more advanced approaches built on these basic building blocks are presented. Parametric Motion Graphs that show how graphs and blending can be put together will be presented. The talk lecture will also touch upon recent work in the field on making more effective use of graphs, improving control, and avoiding explicit graphs altogether. (e.g. the Motion Fields work at Washington) (Heck&Gleicher, Shin&Oh)
Slides:
- Lecture 0
- Lecture 1: Introduction: Synthesis-By-Example
- Lecture 2: Motion Graphs
- Lecture 3: Parametric Graphs & Open Questions
Exercises
Michael Gleicher will talk about the foundations of motion synthesis: character representations and rotations, how signal processing ideas connect to motions, etc. This session will aim at giving the students insights with rotations and kinematics. Students are also expected to gain basic intuitions on foundations such as rotation vectors, matrix logarithm, exponential coordinates, quaternions, etc.
Slides:
Suggested reading material:
- Lucas Kovar, Michael Gleicher Automated Extraction and Parameterization of Motions in Large Data Sets ACM Transcations on Graphics, Volume 23, Number 3, page 559--568 - aug 2004
- Michael Gleicher, More Motion Capture in Games: Can We Make Example-Based Approaches Scale? Motion in Games, 2008.
- Rachel Heck, Michael Gleicher Parametric Motion Graphs Proceedings of the Symposium on Interactive 3D Graphics - apr 2007
- Hyun Joon Shin, Hyun Seok Oh, Fat graphs: constructing an interactive character with continuous controls, Symposium on Computer Animation - SCA , pp. 291-298, 2006
Local lecturers
Aasa Feragen
Geometric trees are combinatorial trees with an additional geometric structure, such as branch length or branch shape. Geometric trees appear, for instance, as airway, vessel or dendrite trees in medical images, in protein folding or as phylogenetic trees describing the development of species. In this talk, we shall outline the properties of a desired statistical framework for analyzing such trees, and describe three different state-of-the-art approaches to defining such statistical theories for tree-structured data. We shall focus on the mathematical modeling aspects and geometric intuition of the three approaches rather than on theory, and discuss the pros and cons of all three methods. The talk will not require prior knowledge, but the main references are included below for the enthusiastic reader.
Slides: Statistical analysis of geometric trees
References:
- L. J. Billera, S. P. Holmes, and K. Vogtmann. Geometry of the space of phylogenetic trees. Advances in Applied Mathematics, 27(4):733-767, 2001.
- H. Wang and J. S. Marron. Object oriented data analysis: sets of trees. Annals of Statistics, 35(5):1849-1873, 2007.
- A. Feragen, S. Hauberg, M. Nielsen, F. Lauze: Means in spaces of treelike shapes, ICCV 2011.
Jens Petersen
The use of optimal net surface segmentation methods has been growing within medical image segmentation the last couple of years. The methods can find the globally optimal solution of multiple surfaces in multiple dimensions using surface cost functions and a wide range of geometric constraints in polynomial time using maximum flow algorithms. In this presentation the methods along with an application to human airway walls in CT images will be demonstrated.
Slides: Optimal Net Surface Segmentation - Application to Airway Walls in CT Images
References:
- X. Wu and D. Chen. Optimal Net Surface Problems with Applications Automata, Languages and Programming, Vol. 2380, pp. 775-775, 2002.
- J. Petersen, M. Nielsen, P. Lo, Z. Saghir, A. Dirksen and M. de Bruijne. Optimal graph based segmentation using flow lines with application to airway wall segmentation. Information Processing in Medical Imaging, pp. 49-60, 2011.
Marco Loog
Marco Loog works with Pattern Recognition Laboratory, Delft University of Technology and The Image Group, University of Copenhagen
He will present joint work with Wan-Jui Lee, Veronika Cheplygina, David Tax, and Bob Duin. Pattern Recognition Laboratory, Delft University of Technology.
Dissimilarity-based classification bridges the gap between between classification techniques using feature-based pattern recognition and machine learning and those based on structural approaches. Attributed graphs contain structural as well as feature-based information and can be considered a generalization of representations employed in so-called multiple instance learning--or multiset classification--on the one hand and of purely structural representations on the other. In my lecture, I will introduce the basics of the dissimilarity approach to classification. Subsequently, I will discuss the extreme cases of multiset and structural classification and their generalization through attributed graphs. Finally, I will provide some, maybe toyish, examples that demonstrate the performance improvements possible by combining the two extremes.
Slides: Bags, Graphs, and Dissimilarity-based Classification
References:
- R. Bunke. Graph Classification Based on Dissimilarity Space Embedding, S+SSPR 2008, Lecture Notes in Computer Science, 2008.
- Lee, Cheplygina, Tax, Loog and Duin. Bridging Structure and Feature Representations in Graph Matching. International Journal of Pattern Recognition and Artificial Intelligence, submitted, 2011.
- Pekalska and Duin. The Dissimilarity Representation for Pattern Recognition. World Scientific, 2005.
- Sørensen, Loog, Lo, Ashraf, Dirksen, Duin and de Bruijne. Dissimilarity-Based Quantification of Lung Disease from CT, MICCAI 2010, Lecture Notes in Computer Science, 2010.
- Tax, Loog and Duin. Bag Dissimilarities for Multiple Instance Learning, SIMBAD 2011, Lecture Notes in Computer Science, 2011.
Francois Anton
Delaunay graphs were introduced in Anton's Ph.D. thesis. They play a fundamental role in the construction of generalised Voronoi diagrams and in many different application areas, including homotopy continuation, cartography, GIS, GPS, robotics, material science, bioinformatics, crystallography and image analysis and computer graphics. We will present their definition, their properties, their relationships with the medial axis and the skeleton, as well as their applications in image analysis and computer graphics. The extension of homotopy continuation using barycentric coordinates based on a Delaunay graph plays a central role in some of the most recent applications.
Slides: Delaunay Graphs and their applications to Computer Graphics and Image Analysis
References:
- F. Anton, D. Mioc and C. Gold. The Voronoi diagram of circles and its application to the visualization of the growth of particles. Transactions On Computational Science III. 2009
- O. Sharma and F. Anton and D. Mioc. On the Isomorphism between the Medial Axis and a Dual of the Delaunay Graph. 2009 Sixth International Symposium on Voronoi Diagrams, 2009.
- C. Gold, D. Mioc, F. Anton, O. Sharma and M. DakowiczA Methodology for Automated Cartographic Data Input, Drawing and Editing Using Kinetic Delaunay/Voronoi Diagrams. Generalized Voronoi Diagram: A Geometry-Based Approach to Computational Intelligence, 2009.
- O. Sharma and F. AntonHomotopy-based surface reconstruction with application to acoustic signals. International Journal of Computer Graphics, 2011.
- O. Sharma and F. AntonHomotopic Object Reconstruction using Natural Neighbor Barycentric Coordinates. International Symposium on Voronoi Diagrams in Science and Engineering, 2010.
Posters
Andreas Kårsnäs - Learning histopathological patterns
Mads Ingerslew Ingwar - Find the Five Differences
Ole Thomsen Buus - Analysis of Seed Sorting Process by Estimation of Seed Motion Trajectories
Sara Sharifzadeh - Conditional Random Fields for Multispectral Data Analysis
Anders B. Beck - Spacio/Temporal Situation Assessment for Mobile Robots
Signe Thorup - 2D Single Image Super-Resolution
Deo Musiige - RF Power Consumption Emulation Optimized with Interval Valued Homotopies
Rasmus Ramsbøl Jensen - Removing that Annoying Hair g Growth!
Sudhakar Tummala - Diagnosis of OA by Automatic Quantification of Incongruity from Knee MRI
Gopal Karemore - Anatomic Breast Coordinate System for Mammogram Analysis
Program for the summer school: