papers

Publications
Timothee Cour, Chris Jordan, Eleni Miltsakaki, Ben Taskar. Movie/Script: Alignment and Parsing of Video and Text Transcription. Proceedings of the European Conference on Computer Vision (ECCV), 2008. (to appear)

Timothee Cour, Ben Taskar. Video Deconstruction: Revealing narrative structure through image and text alignment. NIPS 2007 Workshop on the Grammar of Vision: Probabilistic Grammar-Based Models for Visual Scene Understanding and Object Categorization.

Timothee Cour, Jianbo Shi. Recognizing objects by piecing together the Segmentation Puzzle. IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), 2007.
[pdf][abstract][bib][poster] [supplement: results on entire horse dataset (328 images)] new

Timothee Cour, Jianbo Shi. Solving Markov Random Fields with Spectral Relaxation. Eleventh International Conference on Artificial Intelligence and Statistics (AISTATS), 2007.
[pdf][abstract][bib]

Timothee Cour, Praveen Srinivasan, Jianbo Shi. Balanced Graph Matching. Advances in Neural Information Processing Systems (NIPS), 2006
[pdf][abstract][bib] [supplement: Affinely Constrained Rayleigh Quotients]new [code]new

Timothee Cour, Florence Benezit, Jianbo Shi. Spectral Segmentation with Multiscale Graph Decomposition. IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), 2005.
[pdf][abstract][bib][code]

Timothee Cour, Nicolas Gogin, Jianbo Shi. Learning spectral graph segmentation. Tenth International Workshop on Artificial Intelligence and Statistics (AISTATS), 2005.
[pdf][abstract][bib][Slides]

Timothee Cour, Jianbo Shi. A learnable spectral memory graph for recognition and segmentation. Technical Report MS-CIS-04-12, University of Pennsylvania CIS Technical Reports, Philadelphia, PA, June 2004.
[pdf][abstract][bib]

Abstracts

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:cvpr07,
author=         "Timothee Cour and Jianbo Shi",
title=          "Recognizing objects by piecing together the Segmentation Puzzle",
booktitle=      "Proceedings of the 2007 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 = {Proceedings of the 2005 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"
}