The main objective of the talk is to introduce people to the problem of image segmentation in Computer Vision and to bring to their attention a class of interesting and difficult problems from graph theory.
Informally, to "segment a 2-D image" means to separate image pixels into clusters (called regions) so that pixels in the same cluster come from the same "object". The main difficulty of the problem lies in the fact that "objects" are defined at "high-level", and the information at hand (pixel colors) is "low-level". The problem is usually approached in this way: first, partition the image into regions so that neighboring pixels of distant colors belong to different regions (the idea is that an abrupt change in color usually indicates the boundary of an object); second, check whether the resulting regions correspond to objects of interest (incidentally, this step is much more difficult to perform than one would think).
In this talk I will review several existing graph-based image partitioning algorithms (which view an image as a graph, with the pixels being nodes). The algorithms are based on normalized minimum cuts, minimum spanning trees, and minimum mean cycles respectively. I will also show the results of their application (yanked from the corresponding papers). Returning to the original problem of image segmentation, empirical observations show that a partition that is optimal with respect to a graph-based objective function is often not optimal from a higher-level prospective. This will motivate me to formulate the problem of finding several near-optimal solutions. To avoid generating regions that differ from each other by only few pixels, it makes sense to look for near-optimal solutions that differ from the optimal solution and from each other by "many nodes". A particular instance of this problem could be this: what are near-minimal mean cycles that differ from each other by at least 5% of nodes (or edges)? At this point I will take suggestions and pointers to relevant literature from the audience. I hope to present an overview of such algorithms (assuming I find them) sometime in June.
Links to the papers: