Numerical Algorithms For Two-phase Image Segmentation Based On Convex Models

In recent years, image segmentation methods based on variational/partial differential equation models have developed rapidly, and widely been paid attention by many internal and foreign researchers, which dues to their variable form, flexible structure and excellent performance. For the request of real time in practical applications, this thesis focuses on the fast numerical algorithms for two-phase image segmentation based on two convex models. The one proposed by Nikolova et.al. is constrained, and the other proposed by Berkels is unconstrained. According to the mechanism differences among these numerical algorithms, the content can be partitioned into the following three parts.Chapter 2 focuses on utilizing the gradient projection algorithms to solve the convex models for two-phase image segmentation. Gradient projection algorithms for the unconstrained model and constrained model are proposed, respectively based on the Bermdez-Moreno duality-based algorithm and the dual formulation of the constrained model. Both converge as O(1/k), and the conditions for choosing parameters are analysed. Combining the accelerating convergence strategy of the fast iterative shrinkage /thresholding algorithm, the convergence rate is improved from O(1/k) to O(1/k2).Chapter 3 proposes a Newton method based on block coordinate descent for the unconstrained model. According to the idea of the block coordinate descent, the unconstrained model's dual formulation is equal to a set of constrained quadratic minimization problems with at most two unknowns. And then, the Lagrange functions of the constrained problems, which have two unknows, are solved by Newton method. The proposed algorithm is not only global convergent, but also monotonically decreasing, and converges quadratically.Primal-dual alternating iterative algorithms applied to the constrained model are interested in Chapter 4. Based on the Fenchel primal-dual formulation, a new algorithm is proposed. It alternates between the primal and dual problems, fully utilizes the information from both the primal and dual variables, and therefore is able to converge faster than the pure primal or pure dual method. It is also a relaxed form of the alternating direction method of multipliers and the Split Bregman algorithm, and has same convergence rate with them. Because of avoiding the gradient operator and the divergence operator acting on unknows, its iterative formula is more simple.