## Introduction

It is well known that the so-called level set equation [42,43,54,55]

for curvature-driven motion as well as its nontrivial generalizations are well suited to image processing applications and they are often used nowadays. In this chapter we deal with a specific equation of mean curvature flow type [48-50], namely, where u(t, x) is an unknown (segmentation) function defined in QT = [0, T] x ^ c IRd is a bounded domain with a Lipschitz continuous boundary 3^, [0, T] is a time interval, I0 is a given image, and e > 0 is a parameter. The equation is accompanied with zero Dirichlet boundary conditions and initial

1 Department of Mathematics, Slovak University of Technology, Radlinskeho 11, 813 68 Bratislava, Slovakia, E-mail: [email protected]

2 DEIS, University of Bologna, Via Risorgimento 2, 40136 Bologna, Italy, E-mail: [email protected]

3 Department of Mathematics, University of Bologna, Piazza di Porta S. Donato 5, 40127 Bologna, Italy, E-mail: [email protected]

Without loss of generality, we may assume uD = 0. The Perona-Malik function g : 1R+ ^ 1R+ is nonincreasing, g(0) = 1, admitting g(s) ^ 0 for s . Usually we use the function g(s) = 1/(1 + Ks2), K > 0. G* e C<(1Rd) is a smoothing kernel, e.g. the Gauss function

which is used in presmoothing of image gradients by the convolution

Rd with being the extension of 10 to 1Rd given by periodic reflection through the boundary of image domain. The computational domain ^ is usually a subdomain of the image domain; it should include the segmented object. In fact, in most situations ^ corresponds to image domain itself. We assume that an initial state of the segmentation function is bounded, i.e. u0 e LFor shortening notations, we will use the abbreviation g0 = g(|VG* * I0|). (11.7)

Due to smoothing properties of convolution, we always have 1 > g0 > v* > 0

Equation (11.2) is a regularization, in the sense |Vu| « | Vu|s = ^s2 + |Vu|2 , of the segmentation equation suggested in [7-9,30,31], namely,

However, while in  the s-regularization was used just as a tool to prove the existence of a viscosity solution of the level set equation (see also [10,12]), in our work s is a modeling parameter. As we will see later, it can help in suitable denoising and completion of missing boundaries in images. Such regularization can be interpreted as a mean curvature flow of graphs with respect to a specific Riemann metric given by the image features .

The idea to use Riemannian mean curvature flow of graphs to compute the so-called subjective contours  originates in [48-50]. The subjective surfaces method, developed there, has been successfully used to complete missing boundaries of objects in digital 2D and 3D data sets and thus it is a powerful method for segmentation of highly noisy, e.g. medical, images. In this chapter we follow the same idea.

Initially, a "point-of-view" surface, given by an observer (user) chosen fixation point inside the image, is taken as u0 (see e.g. Fig. 11.11 (top right)). Then this initial state of the segmentation function is evolved by Eq. (11.2), until the so-called subjective surface arises (see e.g. Fig. 11.11 (bottom) right or Fig. 11.14 (top row)). For small e, the subjective surface closes gaps in image object boundaries and is stabilized, i.e. almost does not change by further evolution, so it is easy to stop the segmentation process. The idea to follow evolution of the graph of segmentation function [48-50] and not to follow evolution of a particular level set of u is new in comparison with other level set methods used in image segmentation (cf. [6-9,30,31,36]). In standard level set approach, the redistancing [42, 55] is used to keep unit slope along the level set of interest (e.g. along segmentation curve). In such an approach the evolution of u itself is forgotten at every redistancing step. Such solution prevents steepening of u and one cannot obtain the subjective surfaces. In our computational method we do not impose any specific requirements (e.g., redistancing) to solution of the level set equation, the numerically computed segmentation function can naturally evolve to a "piecewise constant steady state" result of the segmentation process.

For numerical solution of the nonlinear diffusion equation (11.2), governing Riemannian mean curvature flow of graphs, we use semi-implicit complementary volume (called also co-volume or finite volume-element) method. Since (11.2) is regularization of (11.8), for the curvature driven level set flow (11.8) or for some other form of the level set equation (11.1), the method can be used as well (cf. [21,25]).

For time discretization of nonlinear diffusion equations, there are basically three possibilities: implicit, semi-implicit, or explicit schemes. For spatial discretization usually finite difference, finite volume, or finite element method is used. The co-volume technique is a combination of finite element and finite volume methods. Implicit, i.e. nonlinear, time discretization, and co-volume techniques for solution of the level set equation were introduced in . The efficient co-volume level set method based on semi-implicit, i.e. linear, time discretization was given and studied in . In , the method was applied to image smoothing nonlinear diffusion level set equation; here we apply the method to image segmentation and completion of missing boundaries.

Let us note that Eq. (11.8) can be rewritten into an advection-diffusion form as

Various finite difference schemes [7-9,30,31,48-50] are usually based on this form using upwinding in advection term and explicit time stepping. Our co-volume technique relies on discretization of the basic form (11.8), or more precisely on its regularization (11.2), and we use its integral (weak, variational) formulation. In such a way, the discretization scheme naturally respects a variational structure of the problem, it gives clear discrete form of local mass balance, and it naturally fulfills discrete minimum-maximum principle (LTO-stability). The semi-implicit discretization in time yields such stability property (i.e. no spurious oscillations appear in our solution) for any length of discrete time step. This is a main advantage in comparison with explicit time stepping, where the stability is often achieved only under severe time step restriction. Since in nonlinear diffusion problems (such as the level set equation), the coefficients depend on the solution itself and thus they must be recomputed in every discrete time update, an overall CPU time for explicit scheme can be tremendous. On the other hand, the implicit time stepping as in , although unconditionally stable, leads to solution of nonlinear systems in every discrete time update. For the level-set-like problems, there is no guarantee for convergence of a fast Newton solver, and fixed-point-like iterations are very slow . From this point of view, the semi-implicit method seems to be optimal regarding stability and efficiency. In every time update we solve linear system of equations which can be done efficiently using, e.g., suitable preconditioned iterative linear solvers.

In Section 11.2 we discuss various curve evolution and level set models leading to segmentation Eqs. (11.8) and (11.2). In Section 11.3 we introduce our semi-implicit co-volume level set method for solving these equations and discuss some of its theoretical properties and implementation aspects. In Section 11.4 we discuss numerical experiments. Figure 11.1: Image corrupted by a structural noise (left), and result of filtering by level set equation after two (middle) and ten (right) discrete scale steps.