Level Set Formulation

(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 Finite Element Algorithm for

Image Segmentation

Michael Fried

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

May 2005

(2)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

(3)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

The Task: Segmentation and Denoising

given:

I Ω ⊂ IR ⁿ rectangular domain, n = (1),2, 3

I g : Ω → [0, 1] ^N ^c multivalued intensity function, possibly noisy

goal:

I find homogeneous regions Ω ⁱ and its boundaries Γ

I Γ as simple as possible

I approximate g by piecewise smooth

u (with denoising...)

(4)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

The Ansatz: Mumford–Shah Functional

idea:

I minimize the functional

F _MS (u,Γ) = ^Z

Ω

1 N _c

N c

k=1 ∑

(g _k − u _k ) ² + Z

Ω\Γ

1 N _c

N c

k=1 ∑

λ k |∇u k | ² + µ|Γ|

u approximates g, is piecewise smooth and Γ has minimal

length

(5)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Minimizing with Respect to u _k

I for fixed Γ, i. e. fixed Ω ⁱ , minimizing F _MS with respect to u _k leads to Poisson equations



 



 



u _k − λ _k ∆u k = g _k in Ω ⁱ ,

∂ u _k

∂ ν = 0 on ∂ Ω ⁱ .

I heat equation like denoising −→ blurring

(6)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

An Alternative Functional

idea:

I “better” denoising via total variation, thus change F _MS to

F _TV (u, Γ) = ^Z

Ω

1 N _c

N c

k=1 ∑

(g _k − u _k ) ² + Z

Ω\Γ

1 N _c

N c

k=1 ∑

λ _k |∇u k |

1 + µ|Γ|

u approximates g, is piecewise smooth and Γ has minimal

length as befor... but less blurring.

(7)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

An Alternative Functional

idea:

I “better” denoising via total variation, thus change F _MS to

F _TV (u, Γ) = ^Z

Ω

1 N _c

N c

k=1 ∑

(g _k − u _k ) ² + Z

Ω\Γ

1 N _c

N c

k=1 ∑

λ _k |∇u k | ¹ + µ|Γ|

u approximates g, is piecewise smooth and Γ has minimal

length as befor... but less blurring.

(8)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Minimizing with Respect to u _k

I for fixed Γ, i. e. fixed Ω ⁱ , minimizing F _TV with respect to u _k leads to



 



 



u _k −λ _k ∇ · _|∇u ^∇u ^k

k | = g _k in Ω ⁱ ,

|∇u 1 _k |

∂ u _k

∂ ν = 0 on ∂ Ω ⁱ .

I TV like denoising −→ less blurring

(9)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

(10)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Minimizing with Respect to Γ

I follow an approach of Chan and Vese, 2001

I restriction to N = 2 ^M segments Ω ⁱ

I describe Ω ⁱ by M level set functions Φ = (φ _M−1 , . . . , φ 0 )

I using the Heaviside function H(z) we have

(H(φ _M−1 ), . . . , H(φ ₀ )) ∈ {(0, . . . , 0), . . . , (1, . . . , 1)}

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

(11)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Notations

I denote by a _j (i) the j-th digit of i in binary representation:

i =

M−1 ∑

j=0

2 ^j a j (i)

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

Π ⁱ ( Φ (x)) = ∏

j∈I(i)

H(φ _j (x)) ∏

j∈I(i)

(1 − H(φ _j (x)))

I define Ω ⁱ :=

x ∈ Ω | Π ⁱ ( Φ (x)) = 1

I link between u and Φ by introducing functions u ⁱ such that u =

N−1 ∑

i=0

u ⁱ Π ⁱ (Φ)

(12)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

The Length Term

I boundaries of Ω ⁱ :

Γ = {x ∈ Ω| ^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 )|,

(13)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Level Set Formulation

I using all the above

F(Φ) = ^N−1 ∑

i=0 Z

Ω

1 N _c

N c

k=1 ∑

(g _k − u ⁱ _k ) ² + λ k |∇u ⁱ _k | ^p Π ⁱ (Φ)

+µ

M−1 ∑

j=0 Z

Ω

|∇H(φ j )|

where u ⁱ on segments Ω ⁱ are given as solution to

p = 2: Poisson equations (Mumford–Shah)

p = 1: ‘Total Variation’

(14)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

First Regularization

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

H _ρ (z) = 1 2 + 1

π arctan( z ρ )

I set

δ ρ (z) := H _ρ ⁰ (z)

(15)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

First Regularization

I regularized functional

F _ρ ( Φ ) =

N−1 ∑

i=0 Z

Ω

1 N _c

N c

k=1 ∑

(g _k − u ⁱ _k ) ² + λ k | ∇ u ⁱ _k | ^p Π ⁱ _ρ ( Φ )

+µ

M−1 ∑

j=0 Z

Ω

δ ρ (φ _j )|∇φ j |

where Π ⁱ _ρ = ∏

j∈I(i)

H _ρ (φ _j (x)) ∏

j∈I(i)

(1 −H _ρ (φ _j (x)))

(16)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Euler–Lagrange Equations

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

−µ∇ · _|∇φ ^∇φ ^l

l | =

N−1 ∑

i=0

f _l (u ⁱ , ∇u ⁱ )Π ⁱ _l,ρ (Φ) in Ω,

δ ρ (φ _l )

|∇φ l |

∂ φ _l

∂ ν = 0 on ∂ Ω,

where

f _l (u ⁱ , ∇u ⁱ ) = ⁽⁻¹⁾ ⁽¹⁻ _N ^al ⁽ⁱ⁾⁾

c

N _c

∑

k=1

(g _k −u ⁱ _k ) ² + λ k |∇u ⁱ _k | ^p

and

Π ⁱ _l,ρ (Φ) = ∏

j∈I(i)\{l}

H _ρ (φ _j ) ∏

j∈I(i)\{l}

(1 −H _ρ (φ _j ))

(17)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Gradient Flow

I parametrize the descent direction by t:

∂ t φ l

δ _ρ (φ _l ) − µ∇ · ∇φ l

|∇φ l | =

N−1 ∑

i=0

f _l (u ⁱ , ∇u ⁱ ) Π ⁱ _l,ρ ( Φ ) in Ω ×(0,T ],

δ _ρ (φ _l )

|∇φ l |

∂ φ l

∂ ν = 0 on ∂ Ω × (0, T],

φ l (·, 0) = φ l 0 (·) in Ω

(18)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

A ’Simple’ Situation

I M = 1, = ⇒ only two segments

I λ _k = 0, = ⇒ no smoothness term

I N _c = 1, = ⇒ gray scale image g

I u constant on Ω ⁱ , i. e. Minimal Partition Problem:

u =

( c ₀ , φ ₀ > 0,

c ₁ , φ 0 < 0

(19)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Evolution Problem

I evolution equation is now



 



 



φ t

δ _ρ (φ) − µ∇ · _| ^∇φ _∇φ| = (g −c ₁ ) ² − (g − c ₀ ) ² in Ω ×(0, T ]

δ _ρ (φ)

|∇φ| ∂ φ

∂ ν = 0 on∂ Ω × (0, T]

φ (·,0) = φ ₀ (·) in Ω

I constants c _i are given by means

c _i = 1

|Ω ⁱ | Z

Ω ⁱ

g

(20)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Further Assumptions

given:

I Ω = [−1, 1] ² , ρ = 1

I g, φ ₀ depending only on x ₁ assume:

I RHS neither depends on t nor on φ

I solution φ keeps straight level lines

(21)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

ODE Solution

I PDE becomes an ODE

φ t 1 + φ ²

= (g −c ₁ ) ² − (g − c ₀ ) ²

=: R

I for fixed x ₁ ∈ (−1, 1) real valued solution

φ(t) = A ¹ ³ (t)

2 − 2

A ¹ ³ (t) where A(t) = 12R t +4 √

4 + 9R ² t ² + 6cR t + c ² +c ∼ C R t (t → ∞)

(22)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

ODE Solution

I PDE becomes an ODE

φ t 1 + φ ²

= (g −c ₁ ) ² − (g − c ₀ ) ²

=: R

I for fixed x ₁ ∈ (−1, 1) real valued solution

φ(t) = A ¹ ³ (t)

2 − 2

A ¹ ³ (t) where A(t) = 12R t +4 √

4 + 9R ² t ² + 6cR t + c ² +c ∼ C R t (t → ∞)

(23)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

(24)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Regularization II

I evolution equation looks similar to MCF of level sets

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

q

ε ² + |∇φ l | ² , ε ∈ (0, 1)

I partial differential equation:

∂ t φ l

δ ρ (φ _l ) − µ∇· ∇φ l

Q _ε (∇φ l ) =

N−1 ∑

i=0

f _l (u ⁱ , ∇u ⁱ )Π ⁱ _l,ρ (Φ)

(25)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Weak Formulation

I multiplication with a testfunction ϕ ∈ H ¹ (Ω), integration over Ω, integration by parts...

Z

Ω

∂ _t φ _l δ ρ (φ _l ) ϕ + µ

Z

Ω

∇φ l

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

Ω N−1 ∑

i=0

f _l (u ⁱ ,∇u ⁱ )Π ⁱ _l,ρ (Φ)ϕ

∀ϕ ∈ H ¹ ( Ω )

(26)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Discretization of the Evolution Problem

I simplicial meshes T h I linear finite elements

X _h :=

ϕ ∈ C ⁰ (Ω) | ϕ ∈ 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 + µ

Z

Ω

∇φ _h,l ^m

Q ε ( ∇φ _h,l ^m−1 ) · ∇ϕ h =

= Z

Ω N−1 ∑

i=0

f _l (u ⁱ , ∇u ⁱ )Π ⁱ _l,ρ (Φ ^m−1 _h )ϕ _h ∀ϕ _h ∈ X _h

(27)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Triangulation of the Segments

I approximation of u ⁱ via finite elements

I need to triangulate Ω ⁱ

I idea:

(28)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Discretizing u ⁱ

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

Z

Ω ⁱ

(u ⁱ _h,k −g _k )ϕ _h + λ k Z

Ω ⁱ

∇u ⁱ _h,k · ∇ϕ h = 0 ∀ϕ _h ∈ X ⁰ _h (Ω ⁱ )

I computation simultaneously on all segments

(29)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Extension of u ⁱ _h to all of Ω

I the term f _l (u ⁱ _h , ∇u ⁱ _h )Π ⁱ _l,ρ (Φ h ) lives on all of Ω.

I extend u ⁱ _h to Ω via solving a Laplace problem:



 



 



−∆u ⁱ _h = 0 in Ω \ Ω ⁱ ,

∂ u ⁱ _h

∂ ν = 0 on ∂ Ω \ ∂ Ω ⁱ ,

u ⁱ _h given in Ω ⁱ up to the boundary,

(30)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Adaptivity

’good’ data:

I adaption of initial grid via L ² – interpolation error kg − I _h gk ₂

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 ² – interpolation error

I ...

(31)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Combining Everything

I practical simplification: switch back to H(z) i. e. use Π ⁱ _l (Φ) instead of Π ⁱ _l,ρ (Φ)

Algorithm:

1. for all φ j : solve evolution equation using old u ^m−1 _h 2. triangulate new segments Ω ^i,m

3. compute u ⁱ _h on Ω ^i,m

4. extend u ⁱ _h to all of Ω

5. set m = m + 1, goto 1

(32)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

(33)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Experimental Order of Convergence

I recall ODE solution I test for convergence

ref kφ − φ h k _∞,2 EOC

3 6.62 · 10 ⁻² –

4 4.13 · 10 ⁻² 0.68

5 2.83 · 10 ⁻² 0.55

6 1.96 · 10 ⁻² 0.52

7 1.37 · 10 ⁻² 0.52

(34)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Minimal Partition in 3D: Data

I detect the skeleton in a noisy CT

I 55×128×128 voxel data

I 55 horizontal slices (left)

(35)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

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

(36)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

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 much faster computations...

segmented image with

λ k = 0.001, µ = 0.03

(37)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Multichannel: Segmenting and Denoising

I full RHS I extend u ⁱ to Ω

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

Poisson versus TV denoising

noisy original

Poisson Denoising

TV Denoising

(38)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Multichannel: Segmenting and Denoising

I full RHS I extend u ⁱ to Ω

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

Poisson versus TV denoising

noisy original

Poisson denoising

TV denoising

(39)

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

Introduction

Level Set Formulation

Discretization

Numerical Results

Conclusions

we have:

I algorithm for image segmentation and denoising

I can treat 2d/3d images, multichannel images

I easy switch between different denoising methods

I adaptive finite elements we need:

I better adaption in case of noisy data

I extension to 3d multichannel data

I numerical analysis...

Level Set Formulation

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

Introduction

Level Set Formulation

Discretization

Numerical Results

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

Level Set Formulation

Discretization

Numerical Results

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

Introduction

Level Set Formulation

Discretization

Numerical Results

The Task: Segmentation and Denoising

given:

I Ω ⊂ IR n rectangular domain, n = (1),2, 3

I g : Ω → [0, 1] N c multivalued intensity function, possibly noisy

goal:

I find homogeneous regions Ω i and its boundaries Γ

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

Level Set Formulation

Discretization

Numerical Results

The Ansatz: Mumford–Shah Functional

idea:

I minimize the functional

F MS (u,Γ) = Z

Ω

1 N c

N c

k=1 ∑

(g k − u k ) 2 + Z

Ω\Γ

1 N 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

Level Set Formulation

Discretization

Numerical Results

Minimizing with Respect to u k

I for fixed Γ, i. e. fixed Ω i , minimizing F MS with respect to u k leads to Poisson equations



 



 



u k − λ k ∆u k = g k in Ω i ,

∂ u k

∂ ν = 0 on ∂ Ω i .

I heat equation like denoising −→ blurring

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

Introduction

Level Set Formulation

Discretization

Numerical Results

An Alternative Functional

idea:

I “better” denoising via total variation, thus change F MS to

F TV (u, Γ) = Z

Ω

1 N c

N c

I Ω ⊂ IR ⁿ rectangular domain, n = (1),2, 3

I g : Ω → [0, 1] ^N ^c multivalued intensity function, possibly noisy

I find homogeneous regions Ω ⁱ and its boundaries Γ

F _MS (u,Γ) = ^Z

1 N _c

(g _k − u _k ) ² + Z

1 N _c

λ k |∇u k | ² + µ|Γ|

Minimizing with Respect to u _k

I for fixed Γ, i. e. fixed Ω ⁱ , minimizing F _MS with respect to u _k leads to Poisson equations

u _k − λ _k ∆u k = g _k in Ω ⁱ ,

∂ u _k

∂ ν = 0 on ∂ Ω ⁱ .

I “better” denoising via total variation, thus change F _MS to

F _TV (u, Γ) = ^Z

1 N _c

(g _k − u _k ) ² + Z

1 N _c

λ _k |∇u k |

I “better” denoising via total variation, thus change F _MS to

F _TV (u, Γ) = ^Z

1 N _c

(g _k − u _k ) ² + Z

1 N _c

λ _k |∇u k | ¹ + µ|Γ|

Minimizing with Respect to u _k

I for fixed Γ, i. e. fixed Ω ⁱ , minimizing F _TV with respect to u _k leads to

u _k −λ _k ∇ · _|∇u ^∇u ^k

k | = g _k in Ω ⁱ ,

|∇u 1 _k |

∂ u _k

∂ ν = 0 on ∂ Ω ⁱ .

I restriction to N = 2 ^M segments Ω ⁱ

I describe Ω ⁱ by M level set functions Φ = (φ _M−1 , . . . , φ 0 )

(H(φ _M−1 ), . . . , H(φ ₀ )) ∈ {(0, . . . , 0), . . . , (1, . . . , 1)}