Transcript Presentation slides

A New Method of Probability Density
Estimation for Mutual Information Based
Image Registration
Ajit Rajwade,
Arunava Banerjee,
Anand Rangarajan.
Dept. of Computer and Information Sciences &
Engineering,
University of Florida.
Image Registration: problem
definition
• Given two images of an object, to find the
geometric transformation that “best” aligns
one with the other, w.r.t. some image
similarity measure.
Mutual Information for Image
Registration
• Mutual Information (MI) is a well known
image similarity measure ([Viola95],
[Maes97]).
• Insensitive to illumination changes; useful
in multimodality image registration.
Mathematical Definition for MI
MI ( I1 , I 2 )  H ( I1 )  H ( I1 | I 2 )
MI ( I1 , I 2 )  H ( I1 )  H ( I 2 )  H ( I1 , I 2 )
H ( I1 | I 2 )
H ( I1 )
H(I 1,I 2 )
MI( I1 , I 2 )
H ( I1 )
H ( I1 , I 2 )
Marginal entropy
Joint entropy
H ( I 2 | I1 )
H (I 2 )
H ( I1 | I 2 )
Conditional entropy
Calculation of MI
• Entropies calculated as follows:
H ( I1 )   p1 (1 ) log p1 (1 )
1
H ( I 2 )   p2 ( 2 ) log p2 ( 2 )
2
H ( I1 , I 2 )   p12 (1 ,  2 ) log p12 (1 ,  2 )
1  2
p12(1 ,  2 )
p1 (1 )
Joint Probability p ( )
2
2
Marginal
Probabilities
Joint Probability
I1
I2
Functions of Geometric
Transformation
p12(i, j)
H ( I1 , I 2 )
MI( I1 , I 2 )
Estimating probability
distributions
Histograms
How do we select
bin width?
Too large bin width:
Over-smooth distribution
Too small bin width:
Sparse, noisy distribution
Estimating probability
distributions
Parzen Windows
Choice of kernel
Choice of kernel width
Too large:
Over-smoothing
Too small:
Noisy, spiky
Estimating probability
distributions
Mixture Models
[Leventon98]
How many
components?
Local optima
Difficult optimization in every step of
registration.
Direct (Renyi) entropy estimation
Minimal Spanning
Trees, Entropic kNN Graphs
[Ma00, Costa03]
Requires creation of MST
from complete graph of all samples
Cumulative Distributions
Entropy defined
on cumulatives
[Wang03]
Extremely Robust,
Differentiable
A New Method
What’s common to all
previous approaches?
Take samples
More samples
Obtain approximation
to the density
More accurate
approximation
A New Method
Assume uniform distribution
on location
Transformation
Location
Intensity
Distribution on intensity
Uncountable infinity
of samples taken
Each point in the
continuum contributes
to intensity
distribution
Image-Based
Other Previous Work
• A similar approach presented in [Kadir05].
• Does not detail the case of joint density of
multiple images.
• Does not detail the case of singularities in density
estimates.
• Applied to segmentation and not registration.
A New Method
Continuous image representation (use some interpolation
scheme)
No pixels!
Trace out iso-intensity level curves of the image
at several intensity values.
Level
Curves
Intensity
 and
  region

P(
 I Level

 Curves
at
 Intensity
) at
area
of
brown
Analytical Formulation: Marginal
Density
• Marginal density expression for image I(x,y)
of area A:
 dxdy
1
p ( )  lim[   0 ]  I   
A

• Relation between density and local image gradient
(u is the direction tangent to the level curve):
1
du
p( ) 
A I  | I ( x, y) |
Joint Probability
Joint Probability
P(1Level
 I1 Curves
 1  at


 )
Intensity
21 ,
1 ,  2  (I
2
1
1 ) in2 I1
Level
Curves
at Intensity 1 in I1 and  2 in I2
area and
of black
region
( ,    ) in I
2
2
2
2
Analytical Formulation: Joint
Density
• The joint density of images I 1( x, y) and I 2( x, y) with area
of overlap A is related to the area of intersection of the
regions between level curves at 1 and 1  1 of I 1,
and at  2 and  2   2 of I 2 as 1  0,  2  0 .
• Relation to local image gradients and the angle 
between them ( u1 and u2 are the level curve tangent
vectors in the two images):
1
p(1 ,  2 ) 
A I  , I
1
1
2  2
du1du2
| I1 ( x, y )I 2 ( x, y ) sin  |
Practical Issues
1
1
dudu1du2
p(1 ,  2 ) p( )  
A I  , I A I | |I
I,(yx),yI)2 |( x, y ) sin  |
1(x
1
1
2
2
• Joint
density
diverges
Marginal
density
diverges to infinity, in
 inareas
areasofofzero
zerogradient
gradient(level
of either
curve
ordoes
both
not exist!).
image(s).
 in areas where gradient vectors of the
two images are parallel.
Work-around
• Switch from densities (infinitesimal bin
width) to distributions (finite bin width).
• That is, switch from an analytical to a
computational procedure.
Binning without the binning problem!
More bins = more (and closer) level curves.
Choose as many bins as desired.
1024
128
256
512
32 bins
64
Standard histograms
Our Method
Pathological Case: regions in 2D space where
both images have constant intensity
Pathological Case: regions in 2D space where
only one image has constant intensity
Pathological Case: regions in 2D space
where gradients from the
two images run locally parallel
Registration Experiments: Single
Rotation
• Registration between a face image and its
15 degree rotated version with noise of
variance 0.1 (on a scale of 0 to 1).
• Optimal transformation obtained by a bruteforce search for the maximum of MI.
• Tried on a varied number of histogram bins.
MI Trajectory versus rotation:
noise variance 0.1
Our Method
Standard Histograms
128
16 bins
32
64
MI Trajectory versus rotation:
noise variance 0.8
Our Method
Standard Histograms
128
16 bins
32
64
Affine Image Registration
BRAINWEB
PD slice
Warped
Warped
and
T2 slice
Noisy
T2 slice
T2 slice
Brute force search for the
maximum of MI
Affine Image Registration
MI with standard
histograms
MI with our method
Directions for Future Work
• Our distribution estimates are not
differentiable as we use a computational
(not analytical) procedure.
• Differentiability required for non-rigid
registration of images.
Directions for Future Work
• Simultaneous registration of multiple
images: efficient high dimensional density
estimation and entropy calculation.
• 3D Datasets.
References
• [Viola95] “Alignment by maximization of mutual
information”, P. Viola and W. M. Wells III, IJCV
1997.
• [Maes97] “Multimodality image registration by
maximization of mutual information”, F. Maes, A.
Collignon et al, IEEE TMI, 1997.
• [Wang03] “A new & robust information theoretic
measure and its application to image alignment”,
F. Wang, B. Vemuri, M. Rao & Y. Chen, IPMI 2003.
• [BRAINWEB]
http://www.bic.mni.mcgill.ca/brainweb/
References
• [Ma00] “Image registration with minimum spanning tree
algorithm”, B. Ma, A. Hero et al, ICIP 2000.
• [Costa03] “Entropic graphs for manifold learning”, J.
Costa & A. Hero, IEEE Asilomar Conference on Signals,
Systems and Computers 2003.
• [Leventon98] “Multi-modal volume registration using
joint intensity distributions”, M. Leventon & E.
Grimson, MICCAI 98.
• [Kadir05] “Estimating statistics in arbitrary regions of
interest”, T. Kadir & M. Brady, BMVC 2005.
Acknowledgements
• NSF IIS 0307712
• NIH 2 R01 NS046812-04A2.
Questions??