Combinatorial optimization for tracking and low-level computer vision problems

This thesis addresses several problems in computer vision, including low-level motion estimation under varying illumination, interactive image segmentation, image restoration, optical flow, and deformable multi-object tracking. Our new approaches to these problems have two common themes: the use of combinatorial optimization techniques and the use of generalized models. Combinatorial problems have solutions drawn from a finite set of possible solutions. In the context of computer vision, this means that model parameters are drawn from a finite set, implying a discrete formulation of the problem. A discrete problem formulation is natural for some computer vision problems, such as labeling, where the solution is inherently discretized. In other contexts, for instance finding a motion field, the discrete formulation is more artificial. The combination of a discrete formulation and combinatorial optimization techniques is a powerful choice because there are combinatorial optimization techniques which can efficiently find global minima or strong local minima. In contrast, the techniques employed in computer vision for continuous optimization tend to produce local optima and therefore require strong initialization.; Our other common theme is the use of general models. We make weak assumptions about the structure of the problem, relying on both new, general models and the strong minimization properties of combinatorial techniques to produce good results. One could use learning techniques or even a combination of general models and learning techniques to solve computer vision problems. However, learning approaches are only as good as the training data and, for many problems, for instance general illumination invariant matching, it seems very difficult to characterize the problem in terms of training data.; The goal of using general models is to develop techniques which are useful in a wide variety of situations, allowing computer vision systems to move beyond being tailored to very specific problems. This generalization of computer vision algorithms enables new applications or makes it easier to deploy computer vision systems. For instance, tracking algorithms which do not require calibrated cameras enable rapid deployment and use of surveillance systems because there is lower installation overhead. Another reason it is important to attempt to generalize computer vision algorithms is to expand the knowledge of the field. In developing more general algorithms that expand the capabilities of state-of-the-art vision, we hope to learn about common, underlying structure in computer vision problems.; These common themes are first applied 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. The Markov Random Field is solved using max-flow/min-cut energy minimization. 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...