Algorithms for Multiphase Partitioning

Abstract

Given a region D and a partition, S, of D into a number of distinct phases S=(S1,…, SN), a perimeter functional measures the area of the interfacial boundaries with respect to some measure on the surface normals. Perimeter functionals are at the heart of many important variational models, such as Mullins' model for grain boundary motion and the Mumford-Shah model for image segmentation. The gradient flow of perimeter functionals is a non-linear partial differential equation known as curvature motion or curvature flow. Our focus is threshold dynamics, an efficient and elegant algorithm for simulating curvature flow. Recently, Esedoglu and Otto, re-derived and significantly generalized the threshold dynamics algorithm using a variational framework based on the heat content energy. The main thrust of this work is to further explore, analyze and extend threshold dynamics through the heat content energy. We use this framework to derive several new threshold dynamics schemes; namely ``single growth'' schemes which promise unconditional stability for virtually any situation of interest, and ``auction'' schemes which extend threshold dynamics to volume preserving curvature flow. Along the way, we answer an important and long standing question in the threshold dynamics community, and present applications to problems in machine learning.