| Abstract |
A large variety of important tasks in low-level vision, image analysis and pattern recognition can be formulated as discrete labeling problems where one seeks to optimize some measure of the quality of the labeling. For example such is the case in optical flow estimation, stereo matching, image restoration to mention only a few of them. Discrete Markov Random Fields are ideal candidates for modeling these labeling problems and, for this reason, they are ubiquitous in computer vision. Therefore, an issue of paramount importance, that has attracted a significant amount of computer vision research over the past years, is how to optimize discrete Markov Random Fields efficiently and accurately. The main theme of this thesis is concerned exactly with this issue. Two novel MRF optimization schemes are thus presented, both of which manage to extend current state-of-the-art techniques in significant ways. On one hand, a novel framework is proposed that is based on the duality theory of Linear Programming (LP) and provides an alternative as well as more general view of existing graph-cut methods such as the alpha-expansion technique, which is included merely as a special case. Moreover, unlike alpha-expansion which is valid only for MRFs with metric potentials, the derived algorithms provably generate almost optimal solutions for a much wider class of MRFs that are frequently encountered in computer vision, which is an important advance. Results on a variety of low level vision tasks demonstrate the efficacy of our approach. On the other hand, a novel optimization scheme, called Priority-BP, is proposed which carries two very important extensions over standard Belief Propagation (BP): “priority-based message scheduling” and “dynamic label pruning”. For the first time, these two extensions work in cooperation in order to deal with one of the major limitations of BP: its inefficiency in handling MRFs with very large discrete state-spaces. Moreover, both extensions are generic and do not make any use of domain-specific knowledge. They are therefore applicable to any discrete Markov Random Field i.e. a very wide class of problems in computer vision. In order to demonstrate the effectiveness of Priority-BP, a novel exemplar-based framework (based on Priority-BP) is also proposed which treats the problems of image completion, texture synthesis and image inpainting in a unified manner, while managing to compare favorably with related state-of-the-art methods. According to our framework, all of the above mentioned tasks are posed as discrete MRF optimization problems with a well-defined global objective function. Thanks to our Priority-BP algorithm, the intolerable (due to the huge number of labels) computational cost of optimizing the resulting MRF is drastically reduced. Furthermore, visually inconsistent results due to greedy patch assignments are avoided, since our method always manages to maintain many candidate source patches for each block of missing pixels. Numerous results on a wide variety of difficult image completion cases prove the efficacy of our framework. Finally, as another application of our LP-based MRF optimization techniques, we turn our attention to a research topic that lies at the convergence of the fields of computer vision and computer graphics: the virtual reconstruction of 3D environments based on image sequences. Contrary to most of the existing image-based-modeling-and-rendering (IBMR) methods, which typically require large amount of image data and are thus suitable mostly for small scale scenes, here we propose a novel hybrid (geometry & image based) framework that is capable of providing photorealistic walkthroughs of very large, complex outdoor scenes at interactive frame rates. Furthermore, our framework is fully automatic and takes as input only a sparse set of stereoscopic image pairs from the scene. Based on these image pairs, a novel hybrid data representation of a 3D scene, called morphable 3D-mosaics, is then automatically extracted. According to it, a 3D scene is represented as a series of enhanced local 3D models that allow a continuous morphing between each successive two of them to be taking place during rendering. The morphing is both photometric as well geometric and always proceeds in a physically valid way. MRFs play a crucial role for the correct estimation of the morphing and, for optimizing these MRFs, we make use of our LP-based optimization methods. Our framework has already been successfully applied to the virtual 3D reconstruction of the Samaria gorge in Crete and a sample from the results that have been obtained is shown as well.
|
Collections
