Level-Set Optimization

Level-set methods [118,153,117] deform implicitly-defined surfaces, i.e., boundaries of regions, using PDEs and have applications in wide-ranging fields including computer vision [88,179,97], image processing [181,101,178,51], visualization [180,177,96,95], graphics [58,164], and computational physics [153,117]. Level-set methods form a powerful tool in modeling surface deformations because they avoid many problems associated with deformations using parametric surfaces. For instance, the deformation of parametric surfaces often requires frequent regularization of surface elements without which the deterioration of the surface can lead to numerical inaccuracies and instabilities [117]. Moreover, handling topological changes like merging and splitting of parametrically-represented surfaces can be complicated and computationally expensive.

The level-set method represents the deforming surface using a scalar function $\Phi (t,\tau) : \Re^n \times \Re \rightarrow \Re$ of (a) $t \in \Re^n$: the pixel coordinate in an $n$D Cartesian space and (b) $\tau$: the time variable corresponding to the process of deformation. This function is called the embedding. In this chapter, we consider $2$D images and therefore $n=2$. The level sets in our case are curves that are the boundaries of regions and can be defined, with loss of generality, as the zero level set of the embedding $\Phi (\cdot)$, i.e., the set $\{ t : \Phi (t,\tau) = 0 \}$. The motion of the surface is computed by solving a corresponding PDE on the embedding

$$\frac {\partial \Phi (t,\tau)} {\partial \tau} = F (t,\tau),$$ (155)

where $F (t,\tau)$ is typically a data-driven location-dependent term that is dictated by the optimization problem--in this chapter we need to solve (7.3).

A straightforward strategy for computing the surface deformation is to solve the level-set PDE on the entire embedding, and in this way the nested family of level sets evolve simultaneously. If one is interested in just a single level set (i.e., a single curve or surface--in our case, the region boundary), this strategy is inefficient, because each level set evolves independently from the others. The narrow band approach [3] exploits this fact and solves the level-set PDE in a band of grid points around the level set of interest, generating a computational speedup of an order of magnitude. Whitaker [179] proposed the sparse-field method, which restricts the computational domain to a few layers around the designated level set. The layers are visited via a linked-list data structure, and the domain is updated as the surface moves. This approach, and the related approach of [126], have a computational complexity like that of parametric surfaces, which is proportional to the area of the surface rather than the volume of the space in which the surface is embedded.

The level-set framework is an attractive option for solving variational problems of the form (7.5), because it restricts neither the shapes nor the topologies of regions. However, classical level-set evolution schemes for front-tracking based on narrow-band strategies entail some significant computational costs--in particular, the Courant-Friedrichs-Lewy (CFL) condition for numerical stability [153,117] limits the motion of the moving wavefront (region boundaries) to a distance of one grid pixel per iteration. The literature presents several approaches to address this computational issue including multiresolution approaches [28,147], graphics-processor-based schemes [95,96], and shared-memory multiprocessor schemes [7]. Recently, Esedoglu and Tsai introduced a fast level-set algorithm based on threshold dynamics [54,53] for minimizing Mumford-Shah type energies. The proposed method adopts their approach for the level-set evolution but relies on a multiphase extension of the basic formulation to enable multiple-texture segmentation [105,168].