* Faculty       * Staff       * Contact       * Institute Directory
* Undergraduate       * Graduate       * Institute Admissions: Undergraduate | Graduate      
* Events       * Institute Events      
* Lab Manual       * Institute Computing      
No Menu Selected

* Research

Ph.D. Theses

Combinatorial Optimization for Tracking and Low-Level Computer Vision Problems

By Matthew Turek
Advisor: Daniel Freedman
July 3, 2007

One common theme in this thesis is the use of combinatorial optimization techniques. Combinatorial optimization deals with problems whose solutions are drawn from a finite solution space. In the context of computer vision, this typically means that model parameters are drawn from a finite set. The use of combinatorial optimization techniques is a powerful choice, even for more continuous problems, because there are combinatorial techniques which can efficiently find global minima. In contrast, the techniques employed in computer vision for continuous optimization tend to produce local optima, and therefore require strong initializations. We first apply combinatorial techniques to the problem of illumination invariant motion estimation. The goal is to estimate a motion field between frames that have undergone unknown illumination changes. We propose a new, illumination invariant technique for matching regions in images. We then incorporate the new matching technique into a Markov Random Field to estimate a motion field. We apply our motion estimation algorithm to the problem of tracking targets under varying, unknown illumination. Next we approach the problem of using a better smoothness prior in Markov Random Fields. We use max-flow/min-cut energy minimization techniques to solve Markov Random Fields for interactive segmentation, image restoration, and optical flow. In the case of interactive segmentation, we take advantage of the multiscale formulation to also introduce a more general texture model to better characterize regional appearance. We show that our new multiscale techniques lead to quantifiably better results. Finally, we introduce a new labeling paradigm for multi-object tracking. A combinatorial optimization technique, max-flow/min-cut energy minimization, is used to solve a Markov Random Field that manages object level dynamics in the tracking algorithm. We also use another combinatorial optimization technique, dynamic programming, to estimate discrete correspondences, or motion, between the frames in a tracking sequence. We show that this approach produces nice results across several disparate tracking sequences without prior knowledge of the scene or the objects in the scene.

* Return to main PhD Theses page