de LInformation
Nikos Paragios
http://cermics.enpc.fr/~paragios
et Systemes
Centre
dEeignement et de Recherche en Technologies
Level Set Methods in Medical Image
Analysis: Segmentation
CERTIS
Ecole Nationale des Ponts et Chaussees
Paris, France
de LInformation
Http://cermics.enpc.fr/~paragios/book/book.html
http://cermics.enpc.fr/~paragios
Atlantis Research Group
Ecole Nationale des Ponts et Chaussees
Paris, France
Stanley Osher
http://math.ucla.edu/~sjo
Department of Mathematics
University of California, Los Angeles
USA
et Systemes
Centre
dEeignement et de Recherche en Technologies
Nikos Paragios
de LInformation
Outline
Introduction/Motivation
the Propagation of Curves
The snake model
The
level set method
Basic Derivation, algorithms
Boundary-driven and Region-driven model free segmentation
The
et Systemes
Centre
dEeignement et de Recherche en Technologies
On
Level Set Method as a Direct Optimization Space
Multiphase Motion
Region-driven model free image segmentation
Knowledge-based Object Extraction
Shape Registration
Discussion
de LInformation
Motivation
Segmentation and image registration are core components
of medical imaging
et Systemes
Centre
dEeignement et de Recherche en Technologies
Image
2002
The word Segmentation appears 34 times at MICCAI02 program
The word Registration appears 22 times at MICCAI02 program
2003:
The word Segmentation appears 47 times at MICCAI03 program ~ 25%
The word Registration appears 53 times at MICCAI03 program ~ 25%
2004:
The word Segmentation appears 51 times at MICCAI04 program ~ 25%
The word Registration appears 67 times at MICCAI04 program ~ 35%
de LInformation
Overview of Segmentation Techniques
et Systemes
Centre
dEeignement et de Recherche en Technologies
Boundary-driven
Edge Detectors (model free)
Active Contours/snakes (model free + knowledge-based)
Active Shape Models (knowledge-based)
Region-driven
Deformable templates (knowledge-based)
Statistical/clustering techniques (model free + knowledge-based)
MRF-based techniques (model free)
Active Appearance Models (knowledge-based)
Boundary + Region-driven
Active Contours (model free + knowledge-based)
Graph-based Techniques (model free)
Level Set Methods (model free + knowledge-based)
et Systemes
Centre
dEeignement et de Recherche en Technologies
On the propagation of Curves
de LInformation
de LInformation
On the Propagation of Curves
Model (1987) [Kass-Witkin-Terzopoulos]
Planar parameterized curve C:R-->RxR
A cost function defined along that curve
et Systemes
Centre
dEeignement et de Recherche en Technologies
Snake
The internal term stands for regularity/smoothness along the curve
and has two components (resisting to stretching and bending)
The image term guides the active contour towards the desired image
properties (strong gradients)
The external term can be used to account for user-defined
constraints, or prior knowledge on the structure to be recovered
The lowest potential of such a cost function refers to an equilibrium
of these terms
de LInformation
Active Contour Components
internal term
The first order derivative makes the snake behave as a membrane
The second order derivative makes the snake act like a thin plate
The
et Systemes
Centre
dEeignement et de Recherche en Technologies
The
image term
Can guide the snake to
Iso-photes
and terminations
Numerous
, edges
Provisions: balloon models, region-snakes, etc
de LInformation
Optimizing Active Contours
the Euler-Lagrange equations:
That
are used to update the position of an initial curve towards
the desired image properties
et Systemes
Centre
dEeignement et de Recherche en Technologies
Taking
Initial the curve, using a certain number of control points as well as a
set of basic functions,
Update the positions of the control points by solving the above
equation
Re-parameterize the evolving contour, and continue the process until
convergence of the process
de LInformation
Pros/Cons of such an approach
Low complexity
Easy to introduce prior knowledge
Can account for open as well as closed structures
A well established technique, numerous publications it works
User Interactivity
Demetri Terzopoulos is a very good friend
Cons
et Systemes
Centre
dEeignement et de Recherche en Technologies
Pros
Selection on the parameter space and the sampling rule affects the
final segmentation result
Estimation of the internal geometric properties of the curve in
particular higher order derivatives
Quite sensitive to the initial conditions,
Changes of topology (some efforts were done to address the problem)
et Systemes
Centre
dEeignement et de Recherche en Technologies
Level Set: The basic Derivation
de LInformation
de LInformation
The Level Set Method
Osher-Sethian
Earlier: Dervieux, Thomassett, (1979, 1980)
Introduced
Vision
in the area of fluid dynamics
and image segmentation
Caselles-Catte-coll-Dibos (1992)
Malladi-Sethian-Vermuri (1994)
Level
et Systemes
Centre
dEeignement et de Recherche en Technologies
(1987)
Set Milestones
Faugeras-keriven (1998) stereo reconstruction
Paragios-Deriche (1998), active regions and grouping
Chan-Vese (1999) mumford-shah variant
Leventon-Grimson-Faugeras-etal (2000) shape priors
Zhao-Fedkiew-Osher (2001) computer graphics
de LInformation
The Level Set Method
us consider in the most general case the following form of
curve propagation:
Addressing
the problem in a higher dimension
The
level set method represents the curve in the form of an
implicit surface:
That
is derived from the
initial contour according
to the following condition:
et Systemes
Centre
dEeignement et de Recherche en Technologies
Let
de LInformation
Construction of the implicit function
And taking the derivative with respect to time (using the chain rule)
(1)
et Systemes
Centre
dEeignement et de Recherche en Technologies
The Level Set Method
And we are DONE
de LInformation
The Level Set Method
us consider the arc-length (c) parameterization of the curve,
then taking the directional derivative of
in that direction we will observe no change:
leading
to the conclusion that the
the following expression
Embedding
the
et Systemes
Centre
dEeignement et de Recherche en Technologies
Let
is ortho-normal to C where
for the normal vector
the expression of the normal vector to:
following flow for the implicit function is recovered:
(2)
de LInformation
Level Set Method (the basic derivation)
a connection between the curve propagation flow and the
flow deforming the implicit function was established
Given
an initial contour, an implicit function is defined and
deformed at each pixel according to the equation (2) where the
zero-level set corresponds to the actual position of the curve at a
given frame
Euclidean
distance transforms are used in most of the cases as
embedding function
et Systemes
Centre
dEeignement et de Recherche en Technologies
Where
de LInformation
Overview of the Method
level set flow can be re-written in the following form
where
H is known to be the Hamiltonian. Numerical approximations
is then done according to the form of the Hamiltonian
Determine
the initial implicit function (distance transform)
Evolve it locally according to the level set flow
Recover the zero-level set iso-surface (curve position)
Re-initialize the implicit function and Go to step (1) of the loop
Computationally
Open
et Systemes
Centre
dEeignement et de Recherche en Technologies
The
expensive
Questions: re-initializationand numerical approximations
et Systemes
Centre
dEeignement et de Recherche en Technologies
Implementation Details
de LInformation
de LInformation
Level Set Method and Internal Curve Properties
et Systemes
Centre
dEeignement et de Recherche en Technologies
The normal to the curve/surface can be determined directly from
the level set function:
The curvature can also be recovered from the implicit function, by
taking the second order derivative at the arc length
Where we observe no variation since the implicit function has
constant zero values, and given that
as well
as
one can easily prove that:
That can also be extended to higher dimensions
de LInformation
Examples: Mean/Gaussian Curvature Flow
et Systemes
Centre
dEeignement et de Recherche en Technologies
Minimize the Euclidean length of a
curve/surface:
The corresponding level set variant with a
distance transform as an implicit function:
Things become little bit more complicated at
3D (Gaussian Curvature)
Results are courtesy Prof. J. Sethian
(Berkeley) & G. Hermosillo (INRIA)
de LInformation
From theory to Practice (Narrow Band)
[Chop:93, Adalsteinsson-Sethian:95]
idea: we are interested on the motion of the zero-level
set and not for the motion of each iso-phote of the surface
Extract the latest position
Define a band within a certain distance
Update the level set function
Check new position with respect
the limits of the band
Update the position of the band
regularly, and re-initialize the implicit function
Significant
et Systemes
Centre
dEeignement et de Recherche en Technologies
Central
decrease on the computational complexity, in
particular when implemented efficiently and can account for any
type of motion flows
et Systemes
Centre
dEeignement et de Recherche en Technologies
de LInformation
Narrow Band (the basic derivation)
Results are courtesy: R. Deriche
de LInformation
Handling the Distance Function
The
Extraction of the curve position & re-initialization:
Using the marching cubes one can recover the current position of the curve,
set it to zero and then re-initialize the implicit function: the Borgefors
approach, the Fast Marching method, explicit estimation of the distance
for all image pixels
Preserving the curve position and refinement of the existing function
(Susman-smereka-osher:94)
Modification on the level set flow such that the distance transform
property is preserved (gomes-faugeras:00)
et Systemes
Centre
dEeignement et de Recherche en Technologies
distance function has to be frequently re-initialized
Extend the speed of the zero level set to all iso-photes, rather complicated
approach with limited added value?
de LInformation
From theory to Practice (Fast Marching)
[Tsitsiklis:93,Sethian:95]
idea: move the curve one pixel in a progressive manner
according to the speed function while preserving the nature of
the implicit function
Consider
the stationary equation
Such
an equation can be recovered for all
flows where
the speed function has one sign (either positive or negative),
propagation takes place at one direction
If
et Systemes
Centre
dEeignement et de Recherche en Technologies
Central
T(x,y) is the time when the implicit function reaches (x,y):
de LInformation
Fast Marching (continued)
et Systemes
Centre
dEeignement et de Recherche en Technologies
Consider
the stationary equation
in its discrete form:
And using the assumption
that the surface propagates in one direction, the solution can be obtained by
outwards propagation from
the smallest T value
active pixels, the curve has already reached them
alive pixels, the curve could reach them at the next stage
far away pixels, the curve cannot reach them at this stage
de LInformation
Fast Marching (continued)
INITIAL
Initialize
for the all pixels of the front (active), their first
order neighbors alive and the rest far away
For the first order neighbors,
estimate the arrival time according to:
While for the rest the crossing time is set to infinity
PROPAGATION STEP
Select the pixel with the lowest arrival time from the alive ones
et Systemes
Centre
dEeignement et de Recherche en Technologies
STEP
Change his label from alive to active and for his first order neighbors:
If they are alive, update their T value according to
If they are far away, estimate the arrival time according to:
de LInformation
Fast Marching Pros/Cons, Some Results
et Systemes
Centre
dEeignement et de Recherche en Technologies
Fast approach for a level set
implementation
Very efficient technique for re-setting the
embedding function to be distance
transform
Single directional flows, great importance
on initial placement of the contours
Absence of curvature related terms or
terms that depend on the geometric
properties of the curve
Results are courtesy: J. Sethian, R. Malladi,
T. Deschamps, L. Cohen
et Systemes
Centre
dEeignement et de Recherche en Technologies
Level Sets in imaging and vision
the edge-driven case
de LInformation
de LInformation
Emigration from Fluid Dynamics to Vision
(Caselles-Cate-Coll-Dibos:93,Malladi-Sethian-Vemuri:94) have
proposed geometric flows to boundary extraction
Where g(;) is a function that accounts for strong image
gradients
Malladi-Sethian-Vemuri:94
et Systemes
Centre
dEeignement et de Recherche en Technologies
And the other terms are application specificthat either
expand or shrink constantly the initial curve
Distance transforms have been used as embedding functions
de LInformation
Geodesic Active Contours
[Caselles-Kimmel-Sapiro:95, Kichenassamy-Kumar-etal95]
between level set methods and snake driven
optimization
The
geodesic active contour consists of a simplified snake model
without second order smoothness
That
can be written in a more general form as
Where
the image metric has been replaced with a monotonically
decreasing function:
et Systemes
Centre
dEeignement et de Recherche en Technologies
Connection
de LInformation
Geodesic Active Contours
[Caselles-Kimmel-Sapiro:95, Kichenassamy-Kumar-etal95]
to the following more general framework
,
One
can assume that smoothness as well as image terms are
equally important and with some basic math
That
et Systemes
Centre
dEeignement et de Recherche en Technologies
Leading
seeks a minimal length geodesic curve attracted by the
desired image properties
de LInformation
Geodesic Active Contours
By
when minimized leads to the following geometric flow:
Data-driven constrained by the curvature force
Gradient driven term that adjusts the position of the contour when
close to the real 0bject boundaries
embedding this flow to a level set framework and using a
distance transform as implicit function,
et Systemes
Centre
dEeignement et de Recherche en Technologies
That
de LInformation
et Systemes
Centre
dEeignement et de Recherche en Technologies
Geodesic Active Contours
That has an extra term when
compared with the flow proposed
by Malladi-Sethian-Vemuri.
Single directional flowrequires
the initial contour to either
enclose the object or to be
completely inside...
Results are courtesy: R. Deriche
de LInformation
Gradient Vector Flow Geometric Contours
[paragios-mellina-ramesh:01]
conditions are an issue at the active contours since they
are propagated mainly at one direction
Region
terms (later introduced) is
a mean to overcome this limitation
an
alternative is somehow to extend
the boundary-driven speed function to account for directionality,
thus recovering a field (u,v)
One
et Systemes
Centre
dEeignement et de Recherche en Technologies
Initial
can estimate this field close to the object boundarieswhere
The image gradient at the boundaries is tangent to the curve
While the inward normal normal points towards the object boundaries
de LInformation
Gradient Vector Flow Geometric Contours
[paragios-mellina-ramesh:01]
et Systemes
Centre
dEeignement et de Recherche en Technologies
Let (f) be a continuous edge detector with values close to 1 at the
presence of noise and 0 elsewhere
The flow can be determined in areas with important boundary
information (Important f)
And areas where there changes on f, |Gradient(f)|
While elsewhere recovering such a field is not possible and the only
way to be done is through diffusion
This can be done through an approximation of image gradient at the
edges and diffusion of this information for the rest of the image
plane
de LInformation
Gradient Vector Flow Geometric Contours
This
flow can be used within a geometric flow towards image
segmentation
The direction of the propagation should be the same with the one
proposed by the recovered flow, therefore one can penalize the
orientation between these two vectors.
That is integrated within the classical
Geodesic active contour equation and is
implemented using the level set function
using the Additive Operator Splitting
et Systemes
Centre
dEeignement et de Recherche en Technologies
The inner product between the curve
normal and the vector field guides the curve propagation
de LInformation
Additive Operator Splitting
Introduced for fast non-linear diffusion
Applied to the flow of the geodesic active contour
et Systemes
Centre
dEeignement et de Recherche en Technologies
[Weickert:98, Goldenberg-Kimmel:01]
Where one can consider a signed Euclidean distance function to be
the implicit function, leading to:
That can be written as:
That can be solved in an explicit form:
Or a semi-implicit one:
de LInformation
Additive Operator Splitting
in a semi-implicit one
That
refers to a triagonal system of equations and can be done
using the Thomas algorithmat O(N) and has to be done once
et Systemes
Centre
dEeignement et de Recherche en Technologies
Or
(Weickert:02)
et Systemes
Centre
dEeignement et de Recherche en Technologies
de LInformation
Some Comparison
(Weickert:02)
et Systemes
Centre
dEeignement et de Recherche en Technologies
Level Sets in imaging and vision
the region-driven case
de LInformation
de LInformation
The Mumford-Shah framework
[chan-vese:99, yezzi-tsai-willsky-99]
original Mumford-Shah framework aims at partitioning the
image into (multiple) classes according to a minimal length
curve and reconstructing the noisy signal in each class
Let
us consider - a simplified version - the binary case and the
fact that the reconstructed signal is piece-wise constant
Where
the objective is to reconstruct
the image, using the mean values for the
inner and the outer region
et Systemes
Centre
dEeignement et de Recherche en Technologies
The
Tractable
problem, numerous solutions
de LInformation
The Mumford-Shah framework
[chan-vese:99, yezzi-tsai-willsky-99]
the derivatives with respect to piece-wise constants, it
straightforward to show that their optimal value corresponds to
the means within each region:
While
taking the derivatives with respect and using the stokes
theorem, the following flow is recovered for the evolution of the
curve:
An adaptive (directional/magnitude)-wise balloon force
A smoothness force aims at minimizing the length of the partition
That
can be implemented in a straightforward manner within the
level set approach
et Systemes
Centre
dEeignement et de Recherche en Technologies
Taking
de LInformation
The Mumford-Shah framework
Criticism & Results
for multiple classes?
Quite simplistic model, quite often the means are not a good
indicator for the region statistics
Absence of use on the edges, boundary information
et Systemes
Centre
dEeignement et de Recherche en Technologies
Account
de LInformation
Geodesic Active Regions
[paragios-deriche:98]
a frame partition paradigm within the level set space
that can account for boundary and global region-driven
information
KEY
et Systemes
Centre
dEeignement et de Recherche en Technologies
Introduce
ASSUMPTIONS
Optimize the position and the geometric form of the curve by
measuring information along that curve, and within the regions that
compose the image partition defined by the curve:
(input image)
(boundary)
(region)
de LInformation
Geodesic Active Regions
assume that prior knowledge on the positions of the objects
to be recovered is available - as well as on the expected
intensity properties of the object and the background
et Systemes
Centre
dEeignement et de Recherche en Technologies
We
de LInformation
Geodesic Active Regions
Such
The geodesic active contour
A region-driven partition module that aims at separating the
intensities properties of the two classes (see later analogy with the
Mumford-Shah)
And
can be minimized using a gradient descent method leading to:
Which
et Systemes
Centre
dEeignement et de Recherche en Technologies
a cost function consists of:
can be implemented using the level set method as follows
et Systemes
Centre
dEeignement et de Recherche en Technologies
de LInformation
Geodesic Active Regions
et Systemes
Centre
dEeignement et de Recherche en Technologies
de LInformation
Some Results
et Systemes
Centre
dEeignement et de Recherche en Technologies
REMINDER
de LInformation
de LInformation
Level Set & Geometric Flows
evolving moving interfaces with the level set method is
quite attracting, still it has the limitation of being a static
approach
The motion equations are derived somehow,
The level set is used only as an implementation tool
et Systemes
Centre
dEeignement et de Recherche en Technologies
While
That is equivalent with saying that the problem has been somehow
already solvedsince there is not direct connection between the
approach and the level set methodology
et Systemes
Centre
dEeignement et de Recherche en Technologies
Level Set: Optimization space
de LInformation
de LInformation
Level Set Dictionary
us consider distance transforms
as embedding function
Then
following ideas introduced in
[evans-gariepy:96], one can introduce the Dirac distribution
et Systemes
Centre
dEeignement et de Recherche en Technologies
Let
de LInformation
Level Set Dictionary
the Dirac function and integrating within the image domain,
one can estimate the length of the curve:
While integrating the Heaviside Distribution within the image
domain
Such
observations can be used to define regional partition
modules as follows according to some descriptors
That
et Systemes
Centre
dEeignement et de Recherche en Technologies
Using
can be optimized with respect to the level set function
(implicitly with respect to a curve position)
de LInformation
And
given that :
An
adaptive (directional & magnitude wise) flow is recovered for
the propagation of an initial surface towards a partition that is
optimal according to the regional descriptors
The
et Systemes
Centre
dEeignement et de Recherche en Technologies
Level Set Optimization
same idea can be used to introduce contour-driven terms
de LInformation
Level Set Optimization
and optimize them directly on the level set space
Global
terms:
region-driven terms:
According
to some image metricsdefined along the curve and
within the regions obtained through the image partition according
to the position of the curve, that can be multi-component but is
representing only one class
et Systemes
Centre
dEeignement et de Recherche en Technologies
Curve-driven
de LInformation
Multiphase Motion
Up
to now statistics and image information have been used to
partition image into two classes,
dEeignement et de Recherche en Technologies
Often,
we need more than object/background separation, and
therefore the case of multi-phase motion is to be considered
objects/curves, represented by N level set functions
How to deal with occlusions,
one image pixel cannot be
assigned to more than one curve
How to constrain the solution
such that the obtained partition
et Systemes
Centre
[zhao-chan-merinman-osher:96]
consists of all image data
de LInformation
Multi-Phase Motion (continued)
et Systemes
Centre
dEeignement et de Recherche en Technologies
For each class, boundary, smoothness as well as region components
can be considered
Subject to the constraint at each pixel:
a hard and local constraint difficult to be imposed that could be
replaced with a more convenient
That can be optimized through Lagrange multipliers method
de LInformation
Multiphase Motion & Mumford-Shah
[samson-aubert-blanc-feraud:99]
Image
the (zhao-chan-merinman-osher:96) within the Mumford Shah
formulation)
dEeignement et de Recherche en Technologies
Separate the image into regions with consistent intensity properties
Recover a Gaussian distribution that expresses the intensity
properties of each class, or force the intensity properties of each
class to follow some predefined image characteristics
That
when optimized leads to a set of equations that deforming
simultaneously the initial curves according to:
et Systemes
Centre
Segmentation and Signal Reconstruction (direct application of
et Systemes
Centre
dEeignement et de Recherche en Technologies
de LInformation
Multiphase Motion & Mumford-Shah
[samson-aubert-blanc-feraud:99]
de LInformation
Multi-Phase Motion
Taking the level set method to another level
Dealing with multiple (multi-component) objects, and multiple tasks
Introducing interactions between shape structures that evolve in
parallel
CONS
Computationally expensive
Difficult to guarantee convergence
Numerically unstable & hard to implement
et Systemes
Centre
dEeignement et de Recherche en Technologies
PROS
Prior knowledge required on the number of classes and in some cases
on their properties
PARTIAL
SOLUTION: The multi-phase Chan-Vese model
de LInformation
Multi-Phase Motion
[vese-chan:02]
classification according to a combination of all level
sets at a given pixel
LEVEL SET DICTIONARY
et Systemes
Centre
dEeignement et de Recherche en Technologies
Introduce
Class 1:
Class 2:
Class 3:
Class 4:
And therefore by taking these products one can define a modified version
of the mumford-shah approach to account with four classes while using
two level set functions
et Systemes
Centre
dEeignement et de Recherche en Technologies
de LInformation
Multi-Phase Motion
The
assumption of piece-wise constant is rather weak in particular
in medical imaging
Several authors have proposed more advanced statistical
formulations that are recovered on the fly to determine the
statistics of each class
The case of non-parametric approximations of the histogram
within each region is a promising direction
et Systemes
Centre
dEeignement et de Recherche en Technologies
de LInformation
Multi-Phase Motion with more advanced datadriven terms
et Systemes
Centre
dEeignement et de Recherche en Technologies
Knowledge-based Object Extraction
de LInformation
de LInformation
Knowledge-based Object Extraction
recover from the image a structure
of a particular known to some extend
dEeignement et de Recherche en Technologies
geometric form
Methodology
Consider a set of training examples
Register these examples to a common pose
Construct a compact model that expresses the
variability of the training set
Given a new image, recover the area where the
underlying object looks like that one learnt
et Systemes
Centre
Objective:
Advantages of doing that on the LS space:
Preserve the implicit geometry
Account with multi-component objects
all wonderful staff you can do with the LS
de LInformation
Knowledge-based Segmentation
[leventon-faugeras-grimson-etal:00]
Alternate between segmentation
& imposing prior knowledge
Learn a Gaussian distribution of the
shape to be recovered from a training
set directly at the space of implicit functions
The elements of the training set are registered
A principal component analysis is use to recover
the covariance matrix of probability density function of this set
ALTERNATE
Evolve a let set function according to the geodesic active contour
Given its current form, deform it locally using a MAP criterion so it fits
better with the prior distribution
et Systemes
Centre
dEeignement et de Recherche en Technologies
Concept:
Until convergence
de LInformation
Knowledge-based Segmentation
Limitations:
et Systemes
Centre
dEeignement et de Recherche en Technologies
[leventon-faugeras-grimson-etal:00]
Data driven & prior term are decoupled
Building density functions on high dimensional spaces is an ill posed
problem,
Dealing with scale and pose variations (they are not explicitely
addressed)
de LInformation
Knowledge-based Segmentation
[chen-etal:01]
dEeignement et de Recherche en Technologies
Use an average model as prior in its implicit function
For a given curve find the transformation that projects it closer to the
zero-level set of the implicit representation of the prior
For a given transformation evolve the curve locally towards better
fitting with the prior
Couple prior with the image driven term in a direct form
Issues to be addressed:
Model is very simplistic (average shape) opposite to the leventons case
where it was too much complicated
et Systemes
Centre
Concept level:
Estimation of the projection between the curve and the model space is
trickynot enough supportdata term can be improved
et Systemes
Centre
dEeignement et de Recherche en Technologies
de LInformation
Knowledge-based Segmentation
[chen-etal:01]
de LInformation
Knowledge-based Segmentation
[tsai-yezzi-etal:01]
a concept level, prior knowledge is modeled through a Gaussian
distribution on the space of distance functions by performing a
singular value decomposition on the set of registered training set,
The
mumford-shah framework determined at space of the model
is used to segment objects according to various data-driven terms
The
parameters of the projection are recovered at the same time
with the segentation result
et Systemes
Centre
dEeignement et de Recherche en Technologies
At
A more convenient approach than the one of Leventon-etal
Which suffers from not comparing directly the structure that is
recovered with the model
de LInformation
Knowledge-based Segmentation
[paragios-rousson:02]
is imposed by direct comparison between the model and
evolving contour modulo a similarity transformation
The
model consists of a stochastic level set with two components,
A distance map that refers to the average model
And a confidence map that dictates the accuracy of the model
Objective:
Recover a level set that pixel-wise looks like the prior
modulo some transformation
et Systemes
Centre
dEeignement et de Recherche en Technologies
Prior
de LInformation
Model Construction
From
If
we assume N samples on the training set, then the distribution
that expresses at a given point most of these samples is the one
recovered through MAP
dEeignement et de Recherche en Technologies
Where
at a given pixel, we recover the mean and the variance that
best describes the training set composed of implicit functions at
this point, where the mean corresponds to the average value
Constraints
assumption
et Systemes
Centre
a training set recover the most representative model;
on the variance to be locally smooth is a natural
de LInformation
Model Construction (continued)
calculus of variations can lead to the estimation of the mean
and variance (confidence measure) of the model at et each pixel,
However,
the resulting model will not be an implicit function in the
sense of distance transform (averaging distance transforms
doesnt necessary produce one)
One
can seek for a solution of the previously defined objective
function subject to the constraint the means field forms a
distance transform using Lagrange multipliers
An
alternative is to consider the process in repeated steps where
first a solution that fits the data is recovered and then is
projected to the space of distance functions
et Systemes
Centre
dEeignement et de Recherche en Technologies
The
de LInformation
Imposing the (Static) Prior
et Systemes
Centre
dEeignement et de Recherche en Technologies
Define/recover a morphing function A that creates
correspondence between the model and the prior
In the absence of scale variations, and in the case of global
morphing functions one can compare the evolving contour with the
model according to
That modulo the morphing function will evolve the contours towards
a better fit with the model
One can prove that scale variations introduce a multiplicative factor
and they have to be explicitly taken into account
de LInformation
Where
the unknowns are the morphing function and the position
of the level set
Calculus
of variations with respect to the position of the
interface are straightforward:
The
et Systemes
Centre
dEeignement et de Recherche en Technologies
Static Prior (continued)
second term is a constant inflation term aims at minimizing
the area of the contour and eventually the cost function and can
be ignoredsince it has no physical meaning.
et Systemes
Centre
dEeignement et de Recherche en Technologies
de LInformation
Static Prior, Concept Demonstration
de LInformation
Static Prior (continued)
One can also optimize the cost function with respect to the unknown
parameters of the morphing function
Leading to a nice self-sufficient system of motion equations that
update the global registration parameters between the evolving
curve and the model
However, the variability of the model was not considered up to this
point and areas with high uncertainties will have the same impact on
the process
et Systemes
Centre
dEeignement et de Recherche en Technologies
et Systemes
Centre
dEeignement et de Recherche en Technologies
de LInformation
Some Results (non-medical)
de LInformation
Taking Into Account the Model Uncertainties
the joint posterior (segmentation/morphing) is a quite
attractive criterion in inferencing
Where
the Bayes rule was considered and given that the
probability for a given prior model is fixed and we can assume
that all (segmentation/morphing) solutions are equally probable,
we get
Under
the assumption of independence...within pixelsand then
finding the optimal implicit function and its morphing
transformations is equivalent with
et Systemes
Centre
dEeignement et de Recherche en Technologies
Maximizing
de LInformation
Taking Into Account the Model Uncertainties
can be further developed using the Gaussian nature of the
model distribution at each image pixel
term that aims at recovering a transformation and a level set
that when projected to the model, it is projected to areas with
low variance (high confidence)
A term that aims at minimizing the actual distance between the
level set function and the model and is scaled according to the
model confidence
would prefer have a better match between the model and level set in areas
where the variability is low,
et Systemes
Centre
dEeignement et de Recherche en Technologies
That
while in areas with important deviation of the training set, this term will be
less important
de LInformation
Taking the derivatives
of variations regarding the level set and the morphing
function:
The
et Systemes
Centre
dEeignement et de Recherche en Technologies
Calculus
level set deformation flow consists of two terms:
that is a constant deflation force (when the level set function
collapses, eventually the cost function reaches the lowest potential)
An adaptive balloon (directional/magnitude-wise) force that
inflates/deflates the level set so it fits better with the prior after
its projection to the model spaceIn areas with high variance this
term become less significant and data-terms guide the level set to the
real object boundaries...
et Systemes
Centre
dEeignement et de Recherche en Technologies
de LInformation
Comparative Results
et Systemes
Centre
dEeignement et de Recherche en Technologies
de LInformation
Some Videos(again non-medical)
et Systemes
Centre
dEeignement et de Recherche en Technologies
de LInformation
Some medical results
de LInformation
Implicit Active Shapes
[rousson-paragios:03]
Active Shape Model of Cootes et al. is quite popular to object
extraction. Such modeling consists of the following steps:
Let us consider a training set
of
registered surfaces
(implicit representations can also be used for registration [4]).
Distance maps are computed for each surface:
The
samples
are centered with respect to the average
representation
:
et Systemes
Centre
dEeignement et de Recherche en Technologies
The
de LInformation
Implicit Active Shapes
[rousson-paragios:03]
The
set:
principal modes of variation
are recovered through
Principal Component Analysis (PCA). A new shape can be
generated from the (m) retained modes:
et Systemes
Centre
dEeignement et de Recherche en Technologies
Training
et Systemes
Centre
dEeignement et de Recherche en Technologies
de LInformation
The model
de LInformation
The prior
level set function that has minimal distance from a linear from
the model space
The
unknown consist of:
The form of the implicit function
The global transformation between the average mode and the image,
The set of linear coefficients that when applied to the set of basis
functions provides the optimal match of the current contour with the
model space
And
et Systemes
Centre
dEeignement et de Recherche en Technologies
are recovered in a straightforward manner using a gradient
descent method
et Systemes
Centre
dEeignement et de Recherche en Technologies
de LInformation
Some nice results
de LInformation
Conclusions
PROS
Elegant tool to track moving interfaces
Implicit Curve Parameterization & estimation of the geometric
Properties
Able to account with topological changes, able to describe multicomponent objects
CONS
et Systemes
Centre
dEeignement et de Recherche en Technologies
Computational complexity
Numerical approximations, redundancy
Open Curves, sorry we CANNOT do anything about that
de LInformation
Http://cermics.enpc.fr/~paragios/book/book.html
http://cermics.enpc.fr/~paragios
Atlantis Research Group
Ecole Nationale des Ponts et Chaussees
Paris, France
Stanley Osher
http://math.ucla.edu/~sjo
Department of Mathematics
University of California, Los Angeles
USA
et Systemes
Centre
dEeignement et de Recherche en Technologies
Nikos Paragios
de LInformation
Resources
Books
James Sethian (1996,1999): Level Set & Fast Marching Methods,
Cambridge, Introductory.
Stan Osher & Ronald Fedkiw (2002): Level Set Methods and Dynamic
Implicit Surfaces, Springer, Introductory.
Stan Osher & Nikos Paragios (2003): Geometric Level Set in Imaging
Vision and Graphics, Springer, Mostly Visionbit advanced
People
et Systemes
Centre
dEeignement et de Recherche en Technologies
[non-exclusive list]
Laurent Cohen (medical), David Breen (graphics), Rachid Deriche
(segmentation, tracking, DTI), Eric Grimson (medical), Olivier Faugeras
(stereo), Renaud Keriven (stereo, segmentation), Ron Kimmel
(segmentation, shape from shading, tracking), Jerry Prince (topology
preserving), Guillermo Sapiro (segmentation, tracking, implicit surfaces),
James Sethian, Baba Vemuri (Diffusion, Segmentation, Registration)
Joachim Weickert (diffusion, segmentation), Ross Whitaker (Graphics),
Allan Willsky (medical), Anthony Yezzi (medical),
