Abstracts

Learning from Ambiguously Labeled Images

In many image and video collections, we have access only to partially labeled data. For example, personal photo collections often contain several faces per image and a caption that only specifies who is in the picture, but not which name matches which face. Similarly, movie screenplays can tell us who is in the scene, but not when and where they are on the screen. We formulate the learning problem in this setting as partially-supervised multiclass classification where each instance is labeled ambiguously with more than one label.  We show theoretically that effective learning is possible under reasonable assumptions even when all the data is weakly labeled. Motivated by the analysis, we propose a general convex learning formulation based on minimization of a surrogate loss appropriate for the ambiguous label setting.  We apply our framework to identifying faces culled from web news sources and to naming characters in TV series and movies. We experiment on a very large dataset consisting of 100 hours of video, and in particular achieve 6% error for character naming on 16 episodes of LOST.

Movie/Script: Alignment and Parsing of Video and Text Transcription

Movies and TV are a rich source of diverse and complex video of people, objects, actions and locales “in the wild”. Harvesting automatically labeled sequences of actions from video would enable creation of large-scale and highly varied datasets. To enable such collection, we focus on the task of recovering scene structure in movies and TV series for object tracking and action retrieval. We present a weakly supervised algorithm that uses the screenplay and closed captions to parse a movie into a hierarchy of shots and scenes. Scene boundaries in the movie are aligned with screenplay scene labels and shots are reordered into a sequence of long continuous tracks or threads which allow for more accurate tracking of people, actions and objects. Scene segmentation, alignment, and shot threading are formulated as inference in a unified generative model and a novel hierarchical dynamic programming algorithm that can handle alignment and jump-limited reorderings in linear time is presented. We present quantitative and qualitative results on movie alignment and parsing, and use the recovered structure to improve character naming and retrieval of common actions in several episodes of popular TV series.

Recognizing objects by piecing together the Segmentation Puzzle

We present an algorithm that recognizes objects of a given category using a small number of hand segmented images as references. Our method first over segments an input image into superpixels, and then finds a shortlist of optimal combinations of superpixels that best fit one of  template parts, under affine transformations.  Second, we develop a contextual interpretation of the parts, gluing image segments using top-down fiducial points, and checking overall shape similarity. In contrast to previous work, the search for candidate superpixel combinations is not exponential in the number of segments, and in fact leads to a very efficient detection scheme. Both the storage and the detection of templates only require space and time proportional to the length of the template boundary, allowing us to store potentially millions of templates, and to detect a template anywhere in a large image in roughly 0.01 seconds. We apply our algorithm on the Weizmann horse database, and show our method is comparable to the state of the art while offering a simpler and more efficient alternative compared to previous work.

Solving Markov Random Fields with Spectral Relaxation

Markov Random Fields (MRFs) are used in a large array of computer vision and maching learning applications. Finding the Maximum Aposteriori (MAP) solution of an MRF is in general intractable, and one has to resort to approximate solutions, such as Belief Propagation, Graph Cuts, or more recently, approaches based on quadratic programming. We propose a novel type of approximation, Spectral relaxation to Quadratic Programming (SQP). We show our method offers tighter bounds than recently published work, while at the same time being computationally efficient. We compare our method to other algorithms on random MRFs in various settings.

Balanced Graph Matching

Graph matching is a fundamental problem in Computer Vision and Machine Learning. We present two contributions. First, we give a new spectral relaxation technique for approximate solutions to matching problems, that naturally incorporates one-to-one or one-to-many constraints within the relaxation scheme. The second is a normalization procedure for existing graph matching scoring functions that can dramatically improve the matching accuracy. It is based on a reinterpretation of the graph matching compatibility matrix as a bipartite graph on edges for which we seek a bistochastic normalization. We evaluate our two contributions on a comprehensive test set of random graph matching problems, as well as on image correspondence problem. Our normalization procedure can be used to improve the performance of many existing graph matching algorithms, including spectral matching, graduated assignment and semidefinite programming.
 
Spectral Segmentation with Multiscale Graph Decomposition

We present a multiscale spectral image segmentation algorithm. In contrast to most multiscale image processing, this algorithm works on multiple scales of the image in parallel, without iteration, to capture both coarse and fine level details. The algorithm is computationally efficient, allowing to segment large images. We use the Normalized Cut graph partitioning framework of image segmentation. We construct a graph encoding pairwise pixel affinity, and partition the graph for image segmentation. We demonstrate that large image graphs can be compressed into multiple scales capturing image structure at increasingly large neighborhood. We show that the decomposition of the image segmentation graph into different scales can be determined by ecological statistics on the image grouping cues. Our segmentation algorithm works simultaneously across the graph scales, with an inter-scale constraint to ensure communication and consistency between the segmentations at each scale. As the results show, we incorporate long-range connections with linear-time complexity, providing high-quality segmentations efficiently. Images that previously could not be processed because of their size have been accurately segmented thanks to this method. 

Learning spectral graph segmentation

We present a general graph learning algorithm for spectral graph partitioning, that allows direct supervised learning of graph structures using hand labeled training examples. The learning algorithm is based on gradient descent in the space of all feasible graph weights. Computation of the gradient involves finding the derivatives of eigenvectors with respect to the graph weight matrix. We show the derivatives of eigenvectors exist and can be computed in an exact analytical form using the theory of implicit functions. Furthermore, we show for a simple case, the gradient converges exponentially fast. In the image segmentation domain, we demonstrate how to encode top-down high level object prior in  a bottom-up shape detection process.


A learnable spectral memory graph for recognition and segmentation

Image segmentation is often treated as an unsupervised task. Segmentation by human, in contrast, relies heavily on memory to produce an object-like clustering, through a mechanism of controlled hallucination. This paper presents a learning algorithm for memory-driven object segmentation and recognition. We propose a general spectral graph learning algorithm based on gradient descent in the space of graph weight matrix using derivatives of eigenvectors. The gradients are efficiently computed using the theory of implicit functions. This algorithm effectively learns a graph network capable of memorizing and retrieving multiple patterns given noisy inputs. We demonstrate the validity of this approach on segmentation and recognition tasks, including geometric shape extraction, and hand-written digit recognition.

Keywords: segmentation, recognition, learning spectral graph, derivative of eigenvectors, normalized cuts

Bib entries 
 
@inproceedings{Cour:cvpr09,
author=         "Timothee Cour and Ben Sapp and Chris Jordan and Ben Taskar",
title=          "Learning from Ambiguously Labeled Images",
booktitle=      "IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'09)",
year=           "2009"
}

@inproceedings{Cour:eccv08,
author=         "Timothee Cour and Chris Jordan and Eleni Miltsakaki and Ben Taskar",
title=          "Movie/Script: Alignment and Parsing of Video and Text Transcription",
booktitle=      "Proceedings of 10th European Conference on Computer Vision, Marseille, France",
year=           "2008"
}
@inproceedings{Cour:cvpr07,
author=         "Timothee Cour and Jianbo Shi",
title=          "Recognizing objects by piecing together the Segmentation Puzzle",
booktitle=      "IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'07)",
year=           "2007"
}

@inproceedings{Cour:aistats07,
author=         "Timothee Cour and Jianbo Shi",
title=          "Solving Markov Random Fields with Spectral Relaxation",
booktitle=      "Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics",
volume=         "11",
year=           "2007"
}
@incollection{Cour:nips06,
 author = {Timothee Cour and Praveen Srinivasan and Jianbo Shi},
 title = {Balanced Graph Matching},
 booktitle = {Advances in Neural Information Processing Systems 19},
 editor = {B. Sch\”{o}lkopf and J.C. Platt and T. Hofmann},
 publisher = {MIT Press},
 address = {Cambridge, MA},
 year = {2007}
}
@inproceedings{Cour:cvpr05,
 author = {Timothee Cour and Florence Benezit and Jianbo Shi},
 title = {Spectral Segmentation with Multiscale Graph Decomposition},
 booktitle = {IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2},
 year = {2005},
 isbn = {0-7695-2372-2},
 pages = {1124--1131},
 doi = {http://dx.doi.org/10.1109/CVPR.2005.332},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
}
@inproceedings{Cour:aistats05, 
author = "Timothee Cour and Nicolas Gogin and Jianbo Shi",
title = "Learning Spectral Graph Segmentation",
booktitle = "Proceedings of the 10th International Workshop on
Artificial Intelligence and Statistics",
year = "2005"
}
@inproceedings{Cour:TR04,
author = "Timothee Cour and Jianbo Shi",
title = "A Learnable Spectral Memory Graph for Recognition and Segmentation",
institution = "University of Pennsylvania CIS Technical Reports",
month = "June",
year = "2004",
number = "MS-CIS-04-12",
address = "Philadelphia, PA"
}