Transcript Geen diatitel

Edge focusing
• toppoints

scale
• graph
theory
MR slice hartcoronair
ter Haar Romeny, ICPR 2010
Structures exist at their own scale:
Original
 = e0 px
 = e1 px
 = e2 px
 = e3 p
Noise edges
ter Haar Romeny, ICPR 2010
10
8
6
4
2
100
200
300
400
2
4
500
The graph of the sign-change of
the
first derivative of a signal as a
function of scale is denoted the
scale-space signature of the signal.
Zero-crossings
of the second
order derivative
= max of first
order derivative,
as a function
of scale
ter Haar Romeny, ICPR 2010
The notion of longevity can be viewed of a measure of
importance for singularities [Witkin83].
The semantical notions of prominence and conspicuity now get
a clear meaning in scale-space theory.
In a scale-space we see the emergence of the hierarchy of
structures. Positive and negative edges come together and
annihilate in singularity points.
ter Haar Romeny, ICPR 2010
Example:
Lysosome
segmentation
in noisy 2-photon
microscopy
3D images of
macrophages.
ter Haar Romeny, ICPR 2010
Marching-cubes isophote surface of
the macrophage.
Preprocessing:
- Blur with  = 3 px
- Detect N strongest maxima
slice 24
slice 23
slice 24
slice 20
slice 18
slice 24
slice 24
slice 21
slice 25
slice 18
slice 22
slice 21
ter Haar Romeny, ICPR 2010
We interpolate
with cubic splines
interpolation
35 radial tracks
in 35 3D
orientations
ter Haar Romeny, ICPR 2010
The profiles are extremely noisy:
Observation: visually we can reasonably point the steepest edgepoints.
ter Haar Romeny, ICPR 2010
Edge focusing
over all profiles.
Choose a start
level based on
the task, i.e. find
a single edge.
ter Haar Romeny, ICPR 2010
Detected 3D points per maximum.
We need a 3D shape fit function.
ter Haar Romeny, ICPR 2010
The 3D points are least square fit with 3D spherical harmonics:
1
2
1
2
1
2
1
,
2
3
sin
2
3
sin
2
15
cos
2
1
2
15
cos
2
1
,
2
1
,
4
2
sin
1
,
4
sin
1
,
4
3
cos
15
sin2
2
5
2
,
,
3 cos2
1,
15
sin2
2
ter Haar Romeny, ICPR 2010
Resulting detection:
ter Haar Romeny, ICPR 2010
An efficient way to detect maxima and saddlepoints is found in
the theory of vector field analysis (Stoke’s theorem)
ter Haar Romeny, ICPR 2010
Topological winding numbers
N-D
2-D
p
Li d Li
1
p
2
...
d Lin
i1 i2... in
Lj p Lj p
n2
L1 d L2
L2 d L1
L1 2 L22
 is the wedge product (outer product for functionals)
ter Haar Romeny, ICPR 2010
In 2D: the surrounding of the point P is a closed path around P.
The winding number  of a point P is defined as the number of times the image
gradient vector rotates over 2 when we walk over a closed path around P.
maximum:
minumum:
regular point:
saddle point:
monkey saddle:
=1
=1
=0
 = -1
 = -2
ter Haar Romeny, ICPR 2010
Winding number = +1
 extremum
Winding number = -1
 saddle
The notion of scale appears in the size of the path.
ter Haar Romeny, ICPR 2010
Generalised saddle point (5th order): (x+i y)5
Winding number = - 4
 monkey saddle
The winding numbers add within a closed contour, e.g.
A saddle point (-1) and an extremum (+1) cancel, i.e. annihilate.
Catastrophe theory
ter Haar Romeny, ICPR 2010
ter Haar Romeny, ICPR 2010
Decrease of structure over scale scales with the dimensionality.
Slopefor MR image: 1.66555
Slopefor white noise: 1.91549
1000
2000
700
1500
500
1000
300
200
10
2
4
6
8
10
10
2
4
6
8
10
The number of extrema and saddlepoints decrease as e-N over scale
ter Haar Romeny, ICPR 2010
Application:
Computer-Assisted Human Follicle
Analysis for Fertility Prospects with 3D
Ultrasound
Fertility Prospects
In most developed countries a postponement of childbearing is
seen.
E.g. in the Netherlands: Average age of bearing first child is 30 years.
ter Haar Romeny et al., IPMI 1999
ter Haar Romeny, ICPR 2010
Female
reproductive
anatomy
ter Haar Romeny, ICPR 2010
Ovary
Endometrium
Oviduct
Uterus wall
Uterus
Uterus neck
ter Haar Romeny, ICPR 2010
The number of follicles decreases during lifetime
ter Haar Romeny, ICPR 2010
1. As female fecundicity decreases with advancing age, an increasing
number of couples is faced with unexpected difficulties in conceiving.
• Approx. 15000 couples visit fertility clinics annually
• In 70% of these cases age-related fecundicity decline
may play a role
• A further increase is expected
Menopausal age
2. In our emancipated society a tension between family planning and
career exists.
• Being young, till what age can I safely postpone childbearing?
• Getting older, at what age am I still likely to be able to conceive
spontaneously?
• A further increase is expected
ter Haar Romeny, ICPR 2010
A follicle’s life
Resting
0.03 mm
Early growing
0.03 - 0.1 mm
Preantral
0.1 - 0.2 mm
Antral
0.2 - 2 mm
Selectable
2 - 5 mm
Selected
5 - 10 mm
Dominance
10 - 20 mm
initiation of growth
> 120 days?
basal growth
~ 65 days
rescued by FSH window
~ 5 days
maturation
~ 15 days
Ovulation
ter Haar Romeny, ICPR 2010
3D Ultrasound is a safe, cheap and versatile appropriate modality
Kretz Medicor 530D
ter Haar Romeny, ICPR 2010
Two 3D acquisition strategies:
1. Position tracker on regular probe
2. Sweep of 2D array in transducer
Regular sampling from irregularly space
slices
Trans-vaginal probe
ter Haar Romeny, ICPR 2010
ter Haar Romeny, ICPR 2010
ter Haar Romeny, ICPR 2010
Manual counting is very cumbersome
 Automated follicle assessment
• 2-5 mm hypodense structures
• structured noise
• vessels may look like follicles
• ovary boundary sometimes missing
ter Haar Romeny, ICPR 2010
Automated method:
1. Detection of intensity minima by 3D ‘winding numbers’
2. Isotropic ray tracing (500 directions) from detected centra
3. Edge detection by 1D winding numbers
4. Edge focusing to detect most prominent edge
5. Fit spherical harmonics to edgepoints
6. Calculate follicle shape/size parameters and visualize
ter Haar Romeny, ICPR 2010
Detection of a singularity (i.e. a minimum)
From theory of vector fields several important theorems (Stokes,
Gauss) exist that relate something happening in a volume with just
its surface.
We can detect singularities by measurements around the
singularity.
i
i
P
1-D: difference of signs of the gradient  i  zero crossing or extremum
The surrounding of the point P are just 2 points
left and right of P  1D sphere.
   
i   , 
 x y 
ter Haar Romeny, ICPR 2010
 
W
i d j
ij
0  1
 

1 0 
ij
ij
d



d


In subscript notation:
i
j
where ij is the antisymmetric tensor.
1d 2   2 d1
d 
.
2
2
1   2
We consider a unit
gradient vector, so
12+22=1.
ter Haar Romeny, ICPR 2010
For regular points, i.e. when no singularity is present in
W, the winding number is zero, as we see from the
Stokes’ theorem:
  i1 di2  di3 did  i1i2id
Stokes:     d  0
W
W
where the fact that the (d-1)-form  is a closed form was
used.
So, as most of our datapoints are regular, we detect
singularities very robustly as
integer values embedded in a space of zero's.
ter Haar Romeny, ICPR 2010
Example of a result:
1 cm
Dataset 2563, radius Stokes’ sphere 1 pixel, blurring scale 3 pixels
ter Haar Romeny, ICPR 2010
The winding number has nice properties:
• a conservation of winding number within the closed contour.
We measure the sum of the winding numbers.
E.g. enclosing a saddlepoint and a minimum adds up to zero.
• the winding number is independent of the shape of W.
It is a topological entity.
• the winding number only takes integer values.
Multiples of the full rotation angle.
Eeven when the numerical addition of angles does not sum up to
precisely an integer value, we may rightly round off to the
nearest integer.
ter Haar Romeny, ICPR 2010
• the winding number is a scaled notion
The neighbourhood defines the scale.
• the behaviour over scale generates a tree-like structure
Typical annihilations, creations and collisions, from which much
can be learned about the ‘deep structure’ of images.
• the winding number is easy to compute, in any dimension.
• the WN is a robust characterisation of the singular points in the
image: small deformations have a small effect.
ter Haar Romeny, ICPR 2010
Detection of follicle boundaries:
US intensity
Scale
Scale
• generation of 200 - 500 rays in a homogeneous orientation distribution
• determine most pronounced edge along ray by winding number focusing
• fit spherical harmonics to get an analytical description of the shape
• calculate volume and statistics on shape
Distance along ray
Distance along ray
Distance along ray
ter Haar Romeny, ICPR 2010
3D scatterplot of
detected endpoints
3D visualisation of fitted
spherical harmonics function
ter Haar Romeny, ICPR 2010
ter Haar Romeny, ICPR 2010
Validation with 2 bovine ovaria
• anatomincal coupes
• high resolution MR
• 3D ultrasound
Follicle
x
y
z
distance to
volume from
volume
volume
#
center center center neighbor spherical harmonicsfrom MRI
from
3
(pixels)
(mm )
anatomy
v00
99
51
35
25.4
259.7
250.0
262.1
93
28
44
45.0
28.4
27.0
29.8
113
55
74
41.6
56.2
54.9
59.3
v01
33
41
66
25.3
242.3
47
22
75
44.5
34.0
64
49
44
38.9
54.7
v44
72
49
84
25.4
239.7
69
28
70
45.2
28.4
32
51
82
40.1
59.3
ter Haar Romeny, ICPR 2010
Patient studies:
Patient #
1
2
3
manual
17
10
7
Computer
15
8
5
Patient #
4
5
6
Manual
14
9
9
computer
9
7
7
Performance of the algorithm compared with a human expert.
Number of follicles found. Data for 6 patients. The datasets
are cut off to contain only the ovary. Scales used:  = 3.6,
4.8, 7.2 and 12 pixels.
ter Haar Romeny, ICPR 2010
Conclusions:
• 3D ultrasound is a feasible modality for follicle-based fertilitiy
state estimation
• automated CAD is feasible, more clinical validation needed
• winding numbers are robust (scaled) singularity detectors
• a robust class of topological properties emerges
ter Haar Romeny, ICPR 2010
Multi-scale watershed segmentation
Watershed are the boundaries of merging water basins, when the
image landscape is immersed by punching the minima.
At larger scale the boundaries get blurred, rounded and dislocated.
ter Haar Romeny, ICPR 2010
Regions of different scales can be linked by calculating the
largest overlap with the region in the scales just above.
ter Haar Romeny, ICPR 2010
The method is often combined with nonlinear diffusion schemes
E. Dam, ITU
ter Haar Romeny, ICPR 2010
Nabla Vision is an interactive 3D watershed segmentation tool
developed by the University of Copenhagen.
Sculpture the 3D shape by successively clicking precalculated
finer scale watershed details.
ter Haar Romeny, ICPR 2010
ter Haar Romeny, ICPR 2010
2
2  2
tan  , tan(   ) 
1
1  1
3D winding number
We expand the left and right hand side of the
last equation in a Taylor series up to first
order in  and 1 respectively. For the left
hand side we obtain
1
2
tan(   )  tan 



O
(


)
2
cos 1
And for the righthand side
 2   2  2   2  2   2
2





O
(


1
1 )
2
1  1
1
1
     
2
 2  1 2 2 2 1  O( 1 ).
1
1
1d2  2d1
d 
.
2
2
1  1
ter Haar Romeny, ICPR 2010
In n-D:
In 3-D:
 
W
i di  di  di 
1
2
3
i1i2 id
d
  i d j  dk ijk  i l j mk dxl  dxm ijk
Contraction of indices:    ijki (( x j  y k   y j  x k ) dx  dy
 ( y j  z k   z j  y k ) dy  dz
 ( z j  x k   x j  z k ) dz  dx)
This expression has to be evaluated for all voxels of our
closed surface. We can do this e.g. for the 6 planes of the
surrounding cube. On the surface z = constant the previous
equation reduces to
   ijki ( x j yk   y j xk ) dx  dy
ter Haar Romeny, ICPR 2010
   ijki ( x j yk   y j xk ) dx  dy
Performing the contraction on the indices i, j and k gives
  2 x ( x y  y z   x z  y y )
 2 y ( y x  x z   x x  y z )
 2 z ( x x  y y   x y  y x )
Calculation of
• the gradient vector elements i = { x,  y,  z}
• the derivatives of the gradient field, e.g.  x  y =  y/x
is done by neighbour subtraction.
The single pixel steps dx and dy are unity.
ter Haar Romeny, ICPR 2010