Mumford-Shah type variational models and fast algorithms for image segmentation

Image segmentation, which aims to extract interesting objects from a given image, is one fundamental task in image processing and computer vision. Among several popular variational models for this purpose, we focus on the seminal Mumford and Shah (MS) model in this thesis. Build upon the MS model, we present various modifications that adapt to different segmentation tasks, and develop efficient minimization algorithms for the proposed modified models. Below, we guide you through the main contents and contributions of this dissertation. (i) We develop efficient dual-algorithm for two-phase image segmentation using TV-Allen-Cahn model (see Chapter 2). The main purpose is to overcome the difficulties resulted from the non-differentiability of the total variation (TV) term, and effectively handle the constraints of the binary level-set function. The use of a splitting-penalty method results in TV-Allen-Cahn type models associated with a very attractive “double-well” potential, which allows for the implementation of the Chambolle’s dual algorithm. Moreover, we present a new dual algorithm based on an edge-featured penalty of the dual variable, which only requires to solve a vectorial Allen-Cahn type equation with linear ∇(div)-diffusion rather than fully nonlinear diffusion in the Chambolle’s approach. Consequently, efficient numerical algorithms such as time-splitting method and Fast Fourier Transform (FFT) can be implemented. Various numerical tests show that two dual algorithms are much faster and stabler than the primal gradient descent approach, and the new dual algorithm is at least as efficient as the Chambolle’s algorithm and is relatively accurate. We demonstrate that the new method also provides a viable alternative for image restoration. (ii) We propose a direct global minimization method for multiclass labeling and multiphase image segmentation (see Chapter 3). Different from the existing methods, we work directly with the binary setting without using convex relaxation, which is thereby termed as a direct approach. We provide the sufficient and necessary conditions to guarantee a global optimum, and present efficient algorithms based on a reduction of the intermediate unknowns from the augmented Lagrangian formulation. As a result, the underlying algorithms involve significantly fewer parameters and unknowns than the naive use of augmented Lagrangian-based methods, so they are fast and easy to implement. Furthermore, they can produce a global optimum under mild conditions. (iii) We present a robust edge detection method by using the modified MumfordShah model (see Chapter 4). This model immerses an edge into a narrow band surrounding it, and measures the edge length by TV of the associated binary level-set function. The situation that the edge set could be of measure zero in the limiting process presents significant challenges for minimization. We propose several ideas to surmount the obstacles, which include the convex relaxation technique, splitting-penalty method, the proximity algorithm and split Bregman method. The approach can also be extended to color image processing, where limited results are available. (iv) We propose a new decomposition model for multiphase piecewise smooth image segmentation (see Chapter 5). By decomposing an image into an interpolation of piecewise constant part, smooth component and noise part, we incorporate these components into the Mumford-Shah model. This only requires to solve the smooth component on the whole domain. With the entropy penalization, we construct efficient algorithms which include the Fourier method, smoothed Chambolle-dual algorithm and proximity algorithm. Numerical results are provided to show the advantages over the existing method.DOCTOR OF PHILOSOPHY (SPMS