| Early vision has been one of the most fundamental research topic in computer vision. The task of early vision is to recover physical properties of three-dimensional objects (such as shape) from two-dimensional sensed data. Example tasks consist of surface reconstruction, optical flow computation, shape from shading, shape from stereo, edge detection, lightness problem, segmentation problem, ..., etc. Early vision problems may be formulated either in a deterministic or a probabilistic framework. A popular technique in the deterministic framework is based on the regularization theory, and the probabilistic formulation exploits the Markov random field (MRF) model to characterize the function being estimated. Both formulations lead to minimization of equivalent energy functions. When discontinuity detection is involved in the formulation, the energy functions to be minimized become nonconvex. In this thesis, we propose efficient computational algorithms for minimizing these energy functions with and without discontinuity detection.; This thesis contains the following four main contributions: (1) A new theoretical and algorithmic framework based on the capacitance matrix method for solving elliptic partial differential equations arising in early vision and engineering problems. (2) A novel adaptive preconditioning algorithm using a wavelet transform for solving ill-conditioned large sparse linear systems arising in regularized solutions of ill-posed problems in early vision and other domains. (3) Two new, robust and efficient algorithms for accurate optical flow computation namely, a modified gradient-based formulation and an SSD-based regularization formulation. (4) A new hybrid (stochastic + deterministic) search algorithm involving an informed genetic algorithm (GA) and either one of the two aforementioned fast numerical algorithms, for solving nonconvex optimization problems in early vision.; The efficiency of the proposed algorithms are demonstrated through experiments on several early vision problems, including surface reconstruction, shape from shading, and optical flow computation. In addition to computer vision applications, the theory and algorithms developed in this thesis can also be applied to other areas such as cartography/terrain mapping, reverse engineering, MPEG image sequence compression, material science applications (velocity estimation of dry granular flows), engineering applications and mathematical physics. |
