Transcript Random Walker - Theory

RESEARCH
CORPORATE
SIEMENS
1
General Purpose Image Segmentation with
Random Walks
Leo Grady
Department of Imaging and Visualization
Siemens Corporate Research
Outline
SIEMENS
CORPORATE
RESEARCH
• Overview of Siemens Corporate Research (SCR)
• General purpose segmentation
• Random walker algorithm
2
– Concept
– Properties
– Theory
– Numerics
– Results
– New
• Conclusion
SIEMENS
CORPORATE
RESEARCH
Overview of SCR
3
• About 200 full time research staff
Princeton, USA
• 75+ people working on medical imaging
• Basic research  clinical products
• 1/3 mid/long term research - 2/3 applied projects
Siemens
Medical Solutions
SCR
Clinical & University
Partners
Overview of SCR
Clinical Imaging
SIEMENS
CORPORATE
RESEARCH
• Goals of clinical application software
4
•
Measures something that could not be measured
practically before
•
Makes diagnosis more accurate or treatment more
effective
•
Enables therapy that was not possible before
•
Increases patient control
•
Saves time
•
Reduces cost
Overview of SCR
SIEMENS
CORPORATE
RESEARCH
Core interests – Segmentation, registration, visualization
5
Overview of SCR
Offline & Online: Intervention
• So far: diagnostic radiology: offline problem
SIEMENS
CORPORATE
RESEARCH
• Interventional imaging: online problem
6
• Continuous imaging, constant human input
• Rich source of new problems
Outline
SIEMENS
CORPORATE
RESEARCH
• Overview of Siemens Corporate Research (SCR)
• General purpose segmentation
• Random walker algorithm
7
– Concept
– Properties
– Theory
– Numerics
– Results
– New
• Conclusion
General Purpose Segmentation
Goal:
SIEMENS
CORPORATE
RESEARCH
Input an image and output the desired segmentation
8
Why?
• Image editing, etc. (e.g., Magic Wand)
• Do not want to reinvent segmentation for each new
product
Problem:
Two users might want different objects from same image
SIEMENS
CORPORATE
RESEARCH
General Purpose Segmentation
Requires user interaction
9
NCuts, watershed,
mean shift
Snakes, level sets,
intelligent scissors
Graph cuts, magic wand
region growing
General Purpose Segmentation
Atomic methods:
• Semi-automatic
• Atoms must be subsets of true segmentation
SIEMENS
CORPORATE
RESEARCH
Boundary methods:
10
•
•
•
•
•
Easier to incorporate shape prior
Can be used to improve segmentation of another algorithm
Iterative – local minima
Difficult to initialize automatically and in higher dimension
Harder to generalize to point sets, surfaces, nonuniform sampling, etc.
Seeding methods:
• Leads naturally to steady-state and graph-based algorithms
• Easy to seed (even automatically) in arbitrary dimensions
• Generalizes easily to other data modalities
General Purpose Segmentation
Popular seeding algorithms
SIEMENS
CORPORATE
RESEARCH
Region growing: Grow segment from initial seed until
distance/contrast/etc. requirement is met
11
•
•
•
•
Simple
Fast
Leaks through weak boundaries
Killed by noise
General Purpose Segmentation
Popular seeding algorithms
SIEMENS
CORPORATE
RESEARCH
Graph cuts: Max-flow/min-cut found between seeds
12
•
•
•
•
•
Fast
Probabilistic interpretation
Requires lots of seeds to avoid “small cut” problem
Metrication artifacts
True minimum only for two objects (i.e., foreground/background)
Outline
SIEMENS
CORPORATE
RESEARCH
• Overview of Siemens Corporate Research (SCR)
• General purpose segmentation
• Random walker algorithm
13
– Concept
– Properties
– Theory
– Numerics
– Results
– New
• Conclusion
Random Walker - Concept
SIEMENS
CORPORATE
RESEARCH
Given labeled voxels, for each voxel ask: What is the
probability that a random walker starting from this voxel
first reaches each set of labels?
14
Do not despair – Can be computed analytically!
Random Walker - Concept
Segmented image
SIEMENS
CORPORATE
RESEARCH
Partially labeled image
15
Probabilities
Green
Red
Yellow
Blue
SIEMENS
CORPORATE
RESEARCH
Random Walker - Concept
16
Outline
SIEMENS
CORPORATE
RESEARCH
• Overview of Siemens Corporate Research (SCR)
• General purpose segmentation
• Random walker algorithm
17
– Concept
– Properties
– Theory
– Numerics
– Results
– New
• Conclusion
Random Walker - Properties
SIEMENS
CORPORATE
RESEARCH
Naturally respects weak object boundaries
18
Solid border
Weak border
Random Walker - Properties
SIEMENS
CORPORATE
RESEARCH
Naturally respects weak object boundaries
19
Random Walker - Properties
SIEMENS
CORPORATE
RESEARCH
Provably robust to identically distributed noise
20
No texture or filtering used – Based purely on intensity weighting
SIEMENS
CORPORATE
RESEARCH
Random Walker - Properties
21
1.
Segmented regions are connected to a seed
2.
The probabilities for a blank image (e.g., all black) yield a
Voronoi-like segmentation
3.
The expected segmentation for an image of pure noise (identical
r.v.s) is equal to the Voronoi-like segmentation obtained from a
blank image
Random Walker - Properties
SIEMENS
CORPORATE
RESEARCH
Graph cuts
22
Random walker
SIEMENS
CORPORATE
RESEARCH
Random Walker - Properties
23
Outline
SIEMENS
CORPORATE
RESEARCH
• Overview of Siemens Corporate Research (SCR)
• General purpose segmentation
• Random walker algorithm
24
– Concept
– Properties
– Theory
– Numerics
– Results
– New
• Conclusion
Random Walker - Theory
How to compute?
SIEMENS
CORPORATE
RESEARCH
Solution to random walk problem equivalent to minimization of
Z
the Dirichlet integral
25
1
D [u] =
2
(gr u(x; y)) 2
with appropriate boundary conditions.
The solution is given by a harmonic function, i.e., a function
satisfying
r ¢gr u = 0
Random Walker - Theory
SIEMENS
CORPORATE
RESEARCH
Discrete or continuous space?
26
Discrete
Continuous
• Finite
• Exact
• Generalizable
• Euclidean
• Approximate
• Convergence, etc.
4-connected
8-connected
Random Walker - Theory
Attractive numerical properties of a harmonic function
SIEMENS
CORPORATE
RESEARCH
• Mean value theorem: P
27
xi =
wi j (x i ¡ x j )
P
wi j
• Maximum/Minimum principle:
min (x B oundar y ) · x I nt er i or · max (x B oundar y )
Random Walker - Theory
Need to represent Laplacian on a graph:
In the notation of algebraic
2 topology, the Laplacian is given by
SIEMENS
CORPORATE
RESEARCH
r u = @±
28
0-coboundary operator (since we operate on nodes) is the
8
incidence matrix:
> + 1 if i = k;
<
Ae
ij
vk
=
>
:
¡ 1 if j = k;
0 ot herwise
With the constituitive matrix Ceij eij=wij playing the role of the
metric tensor, the combinatorial Laplace-Beltrami operator
T
is given as
L = A CA
Random Walker - Theory
Energy functional:
SIEMENS
CORPORATE
RESEARCH
1
D [u] =
2
29
Z
(gr u(x; y)) 2
¢
1¡
1
D [x] =
x T A T C (Ax) = x T L x
2
2
Subject to boundary conditions at seed locations
x F = 1; x B = 0
Euler-Lagrange:
r ¢gr u = 0
Lx = 0
Random Walker - Theory
SIEMENS
CORPORATE
RESEARCH
8
Laplacian matrix defined
by graph as:
>
< dv i if i = j ;
L v v = ¡ wi j if vi and vj are adjacent nodes;
>
i j
:
0 ot herwise
30
Decompose Laplacian matrix into labeled (marked) and unlabeled blocks
and
· define an¸indicator vector for( the marked nodes:
L =
LM
BT
B
LU
ms
j
=
1 if Q(vj ) = s;
0 if Q(vj ) 6
= s:
Must solve a sparse, SPD, system
of linear
equations for probabilities
s
s
LU x = ¡ Bm
Since probabilities must sum to unity, for X
K labels, only K-1 systems must be solved
xK = 1 ¡
xi
i< K
Random Walker - Concept
Random walk formulated on a lattice (graph) that represents the image
Overlaid graph (lattice)
Edge strength (line width) encodes image gradient
SIEMENS
CORPORATE
RESEARCH
Input image
31
wi j = e¡
¯(I i ¡ I j )2
Random Walker - Theory
Therefore, we can formulate
a¢combinatorial1Dirichlet integral:
1¡
D [x] =
2
x T A T C (Ax) =
2
xT L x
SIEMENS
CORPORATE
RESEARCH
Represents minimum power distribution of an electrical circuit
32
AT z =
Cp =
p =
f
z
Ax
(K irchho®'s Current Law);
(Ohm's Law);
(K irchho®'s Volt age Law);
We can analytically solve the equivalent circuit problem for
the random walker probabilities
Random Walker - Theory
Label 1 prob.
Label 2 prob.
Label 3 prob.
SIEMENS
CORPORATE
RESEARCH
Situation exactly analogous to DC circuit steady-state
Initial labeling
33
Labels
– Unit voltage sources or grounds
Weights
– Branch conductances
Probabilities – Steady-state potentials
Random Walker - Theory
SIEMENS
CORPORATE
RESEARCH
Algorithm summary:
34
1.
Generate weights based on image intensities
2.
Build Laplacian matrix
3.
Solve system of equations for each label
4.
Assign pixel (voxel) to label for which it has the
highest probability
Random Walker - Theory
SIEMENS
CORPORATE
RESEARCH
Equally valid interpretations of algorithm:
35
1.
What is the steady-state temperature distribution in the
inhomogeneous domain, given fixed temperatures at the seeds?
2.
What is the probability that a random walker leaving this node first
reaches a label of each color?
3.
What is the electrical potential at this node when the labeled nodes
are fixed to unity voltage (w.r.t. ground)?
4.
What is the (normalized) effective resistance between this node and
the labeled nodes?
Random Walker - Theory
Equally valid interpretations of algorithm:
SIEMENS
CORPORATE
RESEARCH
5. If a 2-tree (tree with a missing edge) is drawn randomly,
what is the probability that this node is connected to
each label?
36
Interpretation used to prove noise robustness
Outline
SIEMENS
CORPORATE
RESEARCH
• Overview of Siemens Corporate Research (SCR)
• General purpose segmentation
• Random walker algorithm
37
– Concept
– Properties
– Theory
– Numerics
– Results
– New
• Conclusion
Random Walker - Numerics
Main computational burden is solving the system of linear equations
SIEMENS
CORPORATE
RESEARCH
L U x s = ¡ B ms
38
Fortunately, system is sparse, symmetric, positive definite
For a lattice (or any regular graph), the sparsity structure of the matrix is
circulant
SIEMENS
CORPORATE
RESEARCH
Random Walker - Numerics
39
Advantages of a GPU implementation
• Structure of the Laplacian matrix allows for efficient storage and
operations – Off diagonals may be packed into RGBA
• Progressive visualization of solution possible
• Z-buffer allows masking out of seeds
Outline
SIEMENS
CORPORATE
RESEARCH
• Overview of Siemens Corporate Research (SCR)
• General purpose segmentation
• Random walker algorithm
40
– Concept
– Properties
– Theory
– Numerics
– Results
– New
• Conclusion
SIEMENS
CORPORATE
RESEARCH
Random Walker - Results
41
SIEMENS
CORPORATE
RESEARCH
Random Walker - Results
42
SIEMENS
CORPORATE
RESEARCH
Random Walker - Results
43
SIEMENS
CORPORATE
RESEARCH
Random Walker - Results
44
Random Walker - Results
SIEMENS
CORPORATE
RESEARCH
Cardiac segmentation across modalities
45
Random Walker - Results
SIEMENS
CORPORATE
RESEARCH
Segmentation of objects with varying size, shape and texture
46
Outline
SIEMENS
CORPORATE
RESEARCH
• Overview of Siemens Corporate Research (SCR)
• General purpose segmentation
• Random walker algorithm
47
– Concept
– Properties
– Theory
– Numerics
– Results
– New
• Conclusion
Random Walker - New
Possible to incorporate other terms – Intensity priors
SIEMENS
CORPORATE
RESEARCH
Useful for multiple, disconnected objects
48
Original image
Priors only
Random walker
only
Combined
Random Walker - New
Systematic study of weighting function
SIEMENS
CORPORATE
RESEARCH
Gaussian weighting
49
wi j = e¡
¯(I i ¡ I j )2
Reciprocal weighting
wi j =
1
1 + ¯ (I i ¡ I j ) 2
Run on 62 CT datasets with seeds
and manual segmentations
Random Walker - New
Systematic study of edge topology
SIEMENS
CORPORATE
RESEARCH
6-connected
50
10-connected
26-connected
Random Walker - New
SIEMENS
CORPORATE
RESEARCH
Formulate as special case of general segmentation approach Compare with other instances of algorithm
51
SIEMENS
CORPORATE
RESEARCH
Random Walker - New
Precomputation
52
• Precompute eigenvectors of Laplacian
• Input seeds
• Instant result (approximation)
5 eigs
20 eigs
40 eigs
60 eigs
80 eigs
100 eigs
Exact
Outline
SIEMENS
CORPORATE
RESEARCH
• Overview of Siemens Corporate Research (SCR)
• General purpose segmentation
• Random walker algorithm
53
– Concept
– Properties
– Theory
– Numerics
– Results
– New
• Conclusion
SIEMENS
CORPORATE
RESEARCH
Conclusion
Random walker algorithm is:
54
1.
2.
3.
4.
5.
6.
General-purpose
Robust to noise and weak boundaries
Has a single parameter (not adjusted for these results)
Stable
Accurate
Available
Conclusion – More Information
Writings and code
SIEMENS
CORPORATE
RESEARCH
My webpage:
http://cns.bu.edu/~lgrady
55
Random walkers paper:
http://cns.bu.edu/~lgrady/grady2006random.pdf
Random walkers MATLAB code:
http://cns.bu.edu/~lgrady/random_walker_matlab_code.zip
Random walker demo page:
http://cns.bu.edu/~lgrady/Random_Walker_Image_Segmentation.html
MATLAB toolbox for graph theoretic image processing at:
http://eslab.bu.edu/software/graphanalysis/
CVPR Short Course: Fundamentals linking discrete and continuous approaches to computer vision - A topological view
http://cns.bu.edu/~lgrady/Short_Course.html