Optimization Methods for Non-convex Problems with Applications to Image Segmentation

The subject of this dissertation is the development of optimization methods to solve non-convex problems that arise from applications in image processing and computer vision defined as variational models. On the one hand, we seek to develop algorithms that are computationally efficient, since fast methods are required for many applications. On the other hand, we want to find global solutions, or at least sufficiently close approximations, since suboptimal results are often unsatisfactory. Following this viewpoint, the material in the dissertation is divided into two parts.;In the first part, we study fast methods for optimization problems, extending previous ideas of Song and Chan [SC02] and providing a unifying theory with other related optimization techniques. We establish some convergence results and exhibit applications for certain multi-channel segmentation models, but acknowledge the limitations of this direction.;The second part provides the nucleus of this work. The goal is to globally solve non-convex optimization problems, primarily with image segmentation problems in mind. Non-convex problems are difficult due to their numerous local minima, which causes traditional algorithms to produce suboptimal results. The common theme of our methods is to attempt to reformulate the problems as convex optimization problems. Our development of various techniques in this direction leads to several new methods for multi-phase image segmentation based on the Mumford-Shah model. The two main tools for our methods are the two-phase segmentation approach of Chan, Esedog¯lu, and Nikolova [CEN06] and the reformulation technique of Pock, Cremers, and their collaborators [PSG08].;We begin with a relaxation approach that naturally extends the work of [CEN06] for the purpose of globally minimizing the Vese-Chan multi-phase model. This yields our separately convex Vese-Chan (SCVC) algorithm, so called since the minimization problem is convex in each variable but not globally convex. We then develop an approach that reformulates the piecewise constant Mumford-Shah multi-phase segmentation problem in a higher dimensional space, which combines an array of existing methods (e.g., [PSG081) to yield an effective algorithm. This convex algorithm adds to the quickly developing literature for this problem. Next, we investigate a generalization of the reformulation method for the case of vector-valued minimization problems and establish some important results about conditions under which global minimizers can be guaranteed. This general framework yields two important convex multi-phase segmentation techniques: one method for solving the Vese-Chan model and another (albeit more complicated) method for solving piecewise constant Mumford-Shah. Finally, we use the general framework once more, but this time extend the work of [CEN06] in a different, seemingly unexplored, direction, resulting in our globally convex Chan-Vese algorithm (GCCV) for two-phase segmentation with unknown region constants.