### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## A Level Set Based

## Adaptive Finite Element Algorithm for

## Image Segmentation

### Michael Fried

### Institute for Applied Mathematics Albert–Ludwigs–Universität Freiburg

### May 2005

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## The Task: Segmentation and Denoising

### given:

### I Ω ⊂ IR ^{n} rectangular domain, *n* = (1),2, 3

^{n}

### I *g :* Ω → [0, 1] ^{N} ^{c} multivalued intensity function, possibly noisy

^{N}

^{c}

### goal:

### I find homogeneous regions Ω ^{i} and its boundaries Γ

^{i}

### I Γ as simple as possible

### I approximate *g* by piecewise smooth

*u* (with denoising...)

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## The Ansatz: Mumford–Shah Functional

### idea:

### I minimize the functional

*F* _{MS} (u,Γ) = ^{Z}

_{MS}

### Ω

### 1 *N* _{c}

_{c}

*N* *c*

*k=1* ∑

### (g _{k} − *u* _{k} ) ^{2} + Z

_{k}

_{k}

### Ω\Γ

### 1 *N* _{c}

_{c}

*N* *c*

*k=1* ∑

### λ *k* |∇u *k* | ^{2} + µ|Γ|

*u* approximates *g, is piecewise smooth and* Γ has minimal

### length

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Minimizing with Respect to *u* _{k}

_{k}

### I for fixed Γ, i. e. fixed Ω ^{i} , minimizing *F* _{MS} with respect to *u* _{k} leads to Poisson equations

^{i}

_{MS}

_{k}

###

###

###

###

###

*u* _{k} − λ _{k} ∆u *k* = *g* _{k} in Ω ^{i} ,

_{k}

_{k}

_{k}

^{i}

### ∂ *u* _{k}

_{k}

### ∂ ν = 0 on ∂ Ω ^{i} .

^{i}

### I heat equation like denoising −→ blurring

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## An Alternative Functional

### idea:

### I “better” denoising via total variation, thus change *F* _{MS} to

_{MS}

*F* _{TV} (u, Γ) = ^{Z}

_{TV}

### Ω

### 1 *N* _{c}

_{c}

*N* *c*

*k=1* ∑

### (g _{k} − *u* _{k} ) ^{2} + Z

_{k}

_{k}

### Ω\Γ

### 1 *N* _{c}

_{c}

*N* *c*

*k=1* ∑

### λ _{k} |∇u *k* |

_{k}

### 1

### + µ|Γ|

*u* approximates *g, is piecewise smooth and* Γ has minimal

### length as befor... but less blurring.

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## An Alternative Functional

### idea:

### I “better” denoising via total variation, thus change *F* _{MS} to

_{MS}

*F* _{TV} (u, Γ) = ^{Z}

_{TV}

### Ω

### 1 *N* _{c}

_{c}

*N* *c*

*k=1* ∑

### (g _{k} − *u* _{k} ) ^{2} + Z

_{k}

_{k}

### Ω\Γ

### 1 *N* _{c}

_{c}

*N* *c*

*k=1* ∑

### λ _{k} |∇u *k* | ^{1} + µ|Γ|

_{k}

*u* approximates *g, is piecewise smooth and* Γ has minimal

### length as befor... but less blurring.

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Minimizing with Respect to *u* _{k}

_{k}

### I for fixed Γ, i. e. fixed Ω ^{i} , minimizing *F* _{TV} with respect to *u* _{k} leads to

^{i}

_{TV}

_{k}

###

###

###

###

###

*u* _{k} −λ _{k} ∇ · _{|∇u} ^{∇u} ^{k}

_{k}

_{k}

^{k}

*k* | = *g* _{k} in Ω ^{i} ,

_{k}

^{i}

### |∇u 1 _{k} |

_{k}

### ∂ *u* _{k}

_{k}

### ∂ ν = 0 on ∂ Ω ^{i} .

^{i}

### I TV like denoising −→ less blurring

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Minimizing with Respect to Γ

### I follow an approach of Chan and Vese, 2001

### I restriction to *N* = 2 ^{M} segments Ω ^{i}

^{M}

^{i}

### I describe Ω ^{i} by *M* level set functions Φ = (φ _{M−1} , . . . , φ 0 )

^{i}

_{M−1}

### I using the Heaviside function *H(z)* we have

### (H(φ _{M−1} ), . . . , *H(φ* _{0} )) ∈ {(0, . . . , 0), . . . , (1, . . . , 1)}

_{M−1}

### ∼ {0, 1, . . . , *N* − 1}

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Notations

### I denote by *a* _{j} (i) the *j-th digit of* *i* in binary representation:

_{j}

*i* =

*M−1* ∑

*j=0*

### 2 ^{j} *a* *j* (i)

^{j}

### I define index sets

*I(i)* := {j ∈ *IN* 0 | *j* < *M,a* *j* (i) = 1}, *I(i)* := {j ∈ *IN* 0 | *j* < *M,* *a* *j* (i) = 0}

### I denote

### Π ^{i} ( Φ (x)) = ∏

^{i}

*j∈I(i)*

*H(φ* _{j} (x)) ∏

_{j}

*j∈I(i)*

### (1 − *H(φ* _{j} (x)))

_{j}

### I define Ω ^{i} :=

^{i}

*x* ∈ Ω | Π ^{i} ( Φ (x)) = 1

^{i}

### I link between *u* and Φ by introducing functions *u* ^{i} such that *u* =

^{i}

*N−1* ∑

*i=0*

*u* ^{i} Π ^{i} (Φ)

^{i}

^{i}

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## The Length Term

### I boundaries of Ω ^{i} :

^{i}

### Γ = {x ∈ Ω| ^{M−1} ∏

^{M−1}

*j=0*

### φ *j* (x) = 0}

### I the length term is (in the sense of BV!)

### |Γ| = 1 2

*N−1* ∑

*i=0* Z

### Ω

### |∇χ _{Ω} *i* |

### I replaced by

### |Γ| =

*M−1* ∑

*j=0* Z

### Ω

### |∇H(φ *j* )|,

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Level Set Formulation

### I using all the above

*F(Φ) =* ^{N−1} ∑

^{N−1}

*i=0* Z

### Ω

### 1 *N* _{c}

_{c}

*N* *c*

*k=1* ∑

### (g _{k} − *u* ^{i} _{k} ) ^{2} + λ *k* |∇u ^{i} _{k} | ^{p} Π ^{i} (Φ)

_{k}

^{i}

_{k}

^{i}

_{k}

^{p}

^{i}

### +µ

*M−1* ∑

*j=0* Z

### Ω

### |∇H(φ *j* )|

### where *u* ^{i} on segments Ω ^{i} are given as solution to

^{i}

^{i}

*p* = 2: Poisson equations (Mumford–Shah)

*p* = 1: ‘Total Variation’

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## First Regularization

### I replace *H(z)* by a regularized Heaviside function (ρ > 0)

*H* _{ρ} (z) = 1 2 + 1

### π arctan( *z* ρ )

### I set

### δ ρ (z) := *H* _{ρ} ^{0} (z)

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## First Regularization

### I regularized functional

*F* _{ρ} ( Φ ) =

*N−1* ∑

*i=0* Z

### Ω

### 1 *N* _{c}

_{c}

*N* *c*

*k=1* ∑

### (g _{k} − *u* ^{i} _{k} ) ^{2} + λ *k* | ∇ *u* ^{i} _{k} | ^{p} Π ^{i} _{ρ} ( Φ )

_{k}

^{i}

_{k}

^{i}

_{k}

^{p}

^{i}

### +µ

*M−1* ∑

*j=0* Z

### Ω

### δ ρ (φ _{j} )|∇φ *j* |

_{j}

### where Π ^{i} _{ρ} = ∏

^{i}

*j∈I(i)*

*H* _{ρ} (φ _{j} (x)) ∏

_{j}

*j∈I(i)*

### (1 −H _{ρ} (φ _{j} (x)))

_{j}

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Euler–Lagrange Equations

### I minimizing *F* _{ρ} with respect to φ *l* , *l* = 0, . . . , *M* − 1

### −µ∇ · _{|∇φ} ^{∇φ} ^{l}

^{l}

*l* | =

*N−1* ∑

*i=0*

*f* _{l} (u ^{i} , ∇u ^{i} )Π ^{i} _{l,ρ} (Φ) in Ω,

_{l}

^{i}

^{i}

^{i}

_{l,ρ}

### δ ρ (φ _{l} )

_{l}

### |∇φ *l* |

### ∂ φ _{l}

_{l}

### ∂ ν = 0 on ∂ Ω,

### where

*f* _{l} (u ^{i} , ∇u ^{i} ) = ^{(−1)} ^{(1−} _{N} ^{al} ^{(i))}

_{l}

^{i}

^{i}

_{N}

^{al}

*c*

*N* _{c}

_{c}

### ∑

*k=1*

### (g _{k} −u ^{i} _{k} ) ^{2} + λ *k* |∇u ^{i} _{k} | ^{p}

_{k}

^{i}

_{k}

^{i}

_{k}

^{p}

### and

### Π ^{i} _{l,ρ} (Φ) = ∏

^{i}

_{l,ρ}

*j∈I(i)\{l}*

*H* _{ρ} (φ _{j} ) ∏

_{j}

*j∈I(i)\{l}*

### (1 −H _{ρ} (φ _{j} ))

_{j}

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Gradient Flow

### I parametrize the descent direction by *t:*

### ∂ *t* φ *l*

### δ _{ρ} (φ _{l} ) − µ∇ · ∇φ *l*

_{l}

### |∇φ *l* | =

*N−1* ∑

*i=0*

*f* _{l} (u ^{i} , ∇u ^{i} ) Π ^{i} _{l,ρ} ( Φ ) in Ω ×(0,T ],

_{l}

^{i}

^{i}

^{i}

_{l,ρ}

### δ _{ρ} (φ _{l} )

_{l}

### |∇φ *l* |

### ∂ φ *l*

### ∂ ν = 0 on ∂ Ω × (0, *T],*

### φ *l* (·, 0) = φ *l 0* (·) in Ω

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## A ’Simple’ Situation

### I *M* = 1, = ⇒ only two segments

### I λ _{k} = 0, = ⇒ no smoothness term

_{k}

### I *N* _{c} = 1, = ⇒ gray scale image *g*

_{c}

### I *u* constant on Ω ^{i} , i. e. Minimal Partition Problem:

^{i}

*u* =

### ( *c* _{0} , φ _{0} > 0,

*c* _{1} , φ 0 < 0

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Evolution Problem

### I evolution equation is now

###

###

###

###

###

###

###

###

###

### φ *t*

### δ _{ρ} (φ) − µ∇ · _{|} ^{∇φ} _{∇φ|} = (g −c _{1} ) ^{2} − (g − *c* _{0} ) ^{2} in Ω ×(0, *T* ]

### δ _{ρ} (φ)

### |∇φ| ∂ φ

### ∂ ν = 0 on∂ Ω × (0, *T]*

### φ (·,0) = φ _{0} (·) in Ω

### I constants *c* _{i} are given by means

_{i}

*c* _{i} = 1

_{i}

### |Ω ^{i} | Z

^{i}

### Ω ^{i}

^{i}

*g*

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Further Assumptions

### given:

### I Ω = [−1, 1] ^{2} , ρ = 1

### I *g,* φ _{0} depending only on *x* _{1} assume:

### I RHS neither depends on *t* nor on φ

### I solution φ keeps straight level lines

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## ODE Solution

### I PDE becomes an ODE

### φ *t* 1 + φ ^{2}

### = (g −c _{1} ) ^{2} − (g − *c* _{0} ) ^{2}

### =: R

### I for fixed *x* _{1} ∈ (−1, 1) real valued solution

### φ(t) = *A* ^{1} ^{3} (t)

### 2 − 2

*A* ^{1} ^{3} (t) where *A(t) =* *12R t* +4 √

### 4 + *9R* ^{2} *t* ^{2} + *6cR t* + *c* ^{2} +c ∼ *C R t* (t → ∞)

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## ODE Solution

### I PDE becomes an ODE

### φ *t* 1 + φ ^{2}

### = (g −c _{1} ) ^{2} − (g − *c* _{0} ) ^{2}

### =: R

### I for fixed *x* _{1} ∈ (−1, 1) real valued solution

### φ(t) = *A* ^{1} ^{3} (t)

### 2 − 2

*A* ^{1} ^{3} (t) where *A(t) =* *12R t* +4 √

### 4 + *9R* ^{2} *t* ^{2} + *6cR t* + *c* ^{2} +c ∼ *C R t* (t → ∞)

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Regularization II

### I evolution equation looks similar to MCF of level sets

### I same regularization idea: replace |∇φ *l* | by *Q* _{ε} (∇φ *l* ) :=

### q

### ε ^{2} + |∇φ *l* | ^{2} , ε ∈ (0, 1)

### I partial differential equation:

### ∂ *t* φ *l*

### δ ρ (φ _{l} ) − µ∇· ∇φ *l*

_{l}

*Q* _{ε} (∇φ *l* ) =

*N−1* ∑

*i=0*

*f* _{l} (u ^{i} , ∇u ^{i} )Π ^{i} _{l,ρ} (Φ)

_{l}

^{i}

^{i}

^{i}

_{l,ρ}

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Weak Formulation

### I multiplication with a testfunction ϕ ∈ *H* ^{1} (Ω), integration over Ω, integration by parts...

### Z

### Ω

### ∂ _{t} φ _{l} δ ρ (φ _{l} ) ϕ + µ

_{t}

_{l}

_{l}

### Z

### Ω

### ∇φ *l*

*Q* _{ε} (∇φ *l* ) · ∇ϕ = Z

### Ω *N−1* ∑

*i=0*

*f* _{l} (u ^{i} ,∇u ^{i} )Π ^{i} _{l,ρ} (Φ)ϕ

_{l}

^{i}

^{i}

^{i}

_{l,ρ}

### ∀ϕ ∈ *H* ^{1} ( Ω )

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Discretization of the Evolution Problem

### I simplicial meshes T *h* I linear finite elements

*X* _{h} :=

_{h}

### ϕ ∈ *C* ^{0} (Ω) | ϕ ∈ P 1 (S) ∀S ∈ T *h* ,

### I semi–implicit discretization in time

### 1 τ Z

### Ω

### φ _{h,l} ^{m} − φ _{h,l} ^{m−1} δ ρ (φ _{h,l} ^{m−1} ) ϕ _{h} + µ

_{h,l}

^{m}

_{h,l}

^{m−1}

_{h,l}

^{m−1}

_{h}

### Z

### Ω

### ∇φ _{h,l} ^{m}

_{h,l}

^{m}

*Q* ε ( ∇φ _{h,l} ^{m−1} ) · ∇ϕ *h* =

_{h,l}

^{m−1}

### = Z

### Ω *N−1* ∑

*i=0*

*f* _{l} (u ^{i} , ∇u ^{i} )Π ^{i} _{l,ρ} (Φ ^{m−1} _{h} )ϕ _{h} ∀ϕ _{h} ∈ *X* _{h}

_{l}

^{i}

^{i}

^{i}

_{l,ρ}

^{m−1}

_{h}

_{h}

_{h}

_{h}

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Triangulation of the Segments

### I approximation of *u* ^{i} via finite elements

^{i}

### I need to triangulate Ω ^{i}

^{i}

### I idea:

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Discretizing *u* ^{i}

^{i}

### I ’standard’ weak formulations, standard finite element approximation (linear, quadratic,...), e. g.

### Z

### Ω ^{i}

^{i}

### (u ^{i} _{h,k} −g _{k} )ϕ _{h} + λ *k* Z

^{i}

_{h,k}

_{k}

_{h}

### Ω ^{i}

^{i}

### ∇u ^{i} _{h,k} · ∇ϕ *h* = 0 ∀ϕ _{h} ∈ *X* ^{0} _{h} (Ω ^{i} )

^{i}

_{h,k}

_{h}

_{h}

^{i}

### I computation simultaneously on all segments

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Extension of *u* ^{i} _{h} to all of Ω

^{i}

_{h}

### I the term *f* _{l} (u ^{i} _{h} , ∇u ^{i} _{h} )Π ^{i} _{l,ρ} (Φ *h* ) lives on all of Ω.

_{l}

^{i}

_{h}

^{i}

_{h}

^{i}

_{l,ρ}

### I extend *u* ^{i} _{h} to Ω via solving a Laplace problem:

^{i}

_{h}

###

###

###

###

###

### −∆u ^{i} _{h} = 0 in Ω \ Ω ^{i} ,

^{i}

_{h}

^{i}

### ∂ *u* ^{i} _{h}

^{i}

_{h}

### ∂ ν = 0 on ∂ Ω \ ∂ Ω ^{i} ,

^{i}

*u* ^{i} _{h} given in Ω ^{i} up to the boundary,

^{i}

_{h}

^{i}

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Adaptivity

### ’good’ data:

### I adaption of initial grid via *L* ^{2} – interpolation error kg − *I* _{h} *gk* _{2}

_{h}

### I during timesteps: local

### ’guesstimator’, usually not neccessary noisy data:

### I first level denoising e. g. via extrema killer

### I adaption of initial grid via *L* ^{2} – interpolation error

### I ...

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Combining Everything

### I practical simplification: switch back to *H(z)* i. e. use Π ^{i} _{l} (Φ) instead of Π ^{i} _{l,ρ} (Φ)

^{i}

_{l}

^{i}

_{l,ρ}

### Algorithm:

### 1. for all φ *j* : solve evolution equation using old *u* ^{m−1} _{h} 2. triangulate new segments Ω ^{i,m}

^{m−1}

_{h}

^{i,m}

### 3. compute *u* ^{i} _{h} on Ω ^{i,m}

^{i}

_{h}

^{i,m}

### 4. extend *u* ^{i} _{h} to all of Ω

^{i}

_{h}

### 5. set *m* = *m* + 1, goto 1

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Experimental Order of Convergence

### I recall ODE solution I test for convergence

### ref kφ − φ *h* k _{∞,2} EOC

### 3 6.62 · 10 ^{−2} –

### 4 4.13 · 10 ^{−2} 0.68

### 5 2.83 · 10 ^{−2} 0.55

### 6 1.96 · 10 ^{−2} 0.52

### 7 1.37 · 10 ^{−2} 0.52

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Minimal Partition in 3D: Data

### I detect the skeleton in a noisy CT

### I 55×128×128 voxel data

### I 55 horizontal slices (left)

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Minimal Partition in 3D: Results

### I 11 time steps

### I original image: 901.120 voxel

### I final segmentation: 137.651 nodes

### I subvoxel resolution around surface

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Multichannel: Segmenting RGB Images

### using a ‘mixed method’:

### I RHS as for the minimal partition problem

### original showing boundaries of the segments

### I but solving Poisson equations for *u* ^{i}

^{i}

### I much faster computations...

### segmented image with

### λ *k* = 0.001, µ = 0.03

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Multichannel: Segmenting and Denoising

### I full RHS I extend *u* ^{i} to Ω

^{i}

### I here: λ *k* = 0.0035, µ = 0.03 I comparison:

### Poisson versus TV denoising

### noisy original

### Poisson Denoising

### TV Denoising

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising

## Multichannel: Segmenting and Denoising

### I full RHS I extend *u* ^{i} to Ω

^{i}

### I here: λ *k* = 0.0035, µ = 0.03 I comparison:

### Poisson versus TV denoising

### noisy original

### Poisson denoising

### TV denoising

### A Level Set Based Adaptive FE Algorithm for Image Segmentation Michael Fried

### Introduction

The Task The Ansatz An Alternative Approach

### Level Set Formulation

A Level Set Approach An Evolution Problem ODE Solutions

### Discretization

Weak Regulatized Formulation Discretization of the Evolution Problem Discretizingu Adaptivity

### Numerical Results

Convergence Minimal Partition in 3D Multichannel Data Segmentation and Denoising