Transcript Shape Indexing and Its Optimization in Medical Image Databases

Shape-based Similarity Retrieval for
Medical Image Databases
Xiaoning Qian
Yale University
A Different Retrieval Strategy
• Image content and semantics:
• Hard to describe by text; best described graphically.
• Hard to form meaningful queries using text by naive users
• Different Categorization for different users.
• Rich in geometry.
• Content-based Similarity Retrieval:
• A more flexible search strategy for image databases: define semantics
by image appearance directly.
• Image features:
• Low tolerance for errors for medical image databases.
• Technically difficult to index.
Motivation
• NHANES II – National health and nutrition examination surveys
• 17,000 cervical and lumbar spine images
• Vertebral shapes correlate with the presence and severity of
osteophyte (Sharp Protuberance)
• Shape-based similarity retrieval
cervical
lumbar
Motivation
Content-based similarity retrieval
• Feature space
• Feature distance
• Similarity retrievals
• Range queries {u | d (q, u)  rT , u  P}
• K-nearest neighbor queries
q:
d ( ):
query example
feature distance
Indexing
• Problem of content-based retrieval: Assessing similarity is complex.
Brute-force similarity retrieval is too expensive in large databases
• Indexing: a data structure and the corresponding retrieval algorithm
which quickly retrieves all similar feature points
Vertebra Boundaries
• Content-based retrieval based
on 2-d shapes in images
• Deformable template contour
detection algorithm using
orthogonal curves
• Each boundary is obtained as a
sequence of m points
• The correspondence of m
points is known
• When boundaries are given by
points, shapes can not be
represented by vectors
Problems in Shape Indexing
• Fact 1: Shape space is
a curved manifold.
• Fact 2: Coordinatebased indexing trees
usually outperform
metric-based trees.
• An optimal
embedding algorithm
to embed shape space
into a Euclidean space
Problems in Shape Indexing
from PhD Thesis “Efficiently
Indexing High-Dimensional Data
Spaces” by Christian Böhm
• Fact 3: Shape space and embedding space are high
dimensional.
• Curse of dimensionality
• Practical shapes are non-uniformly distributed.
• To overcome the curse, we adapt indexing trees to further
increase the efficiency of indexing trees.
Overview
segmentation
Image
2-D Boundary
??
Shape Space
• Content-based retrieval using 2-d shapes in images
• When boundaries are given by points, shapes can not be
represented by vectors
• Shape space is high dimensional
• Shape indexing is difficult because shape space is a high
dimensional curved manifold
Shape Space and Shape
Embedding
Shape space theory
• Object boundaries are represented by a fixed number of
sample points (object configurations).
z  [ x1  iy1 , x2  iy 2 ,, xm  iy m ]T
• Two boundaries have the same shape if they can be mapped
onto each other by translation, rotation and scaling.
z1 ~ z2 if z1  z2  t,  C \ {0} and t  C
• We can define a shape as an equivalence class.
[ z ]  {z  t z  C m ,  C \{0}, t  C}
• The set of all equivalence classes is a
shape space, which is a curved manifold.
Shape and pre-shape
Cm
Orbit under
translation and
scaling
zj
configuration
Cm
Each orbit
maps to a
point
Each orbit
maps to a
point
CPm-2
Pre-shape
space
Orbit
under
rotation


[ z j ] p  z j  z j 1m / z j  z j 1m
T
pre-shape
T

i
[ z j ]s  e j [ z j ] p

shape
1
1
1m   ,, 
m
m
T
Shape space and Procrustes distances
• Shape space of planar objects is a
complex projective space with
complex dimension m-2
• There are naturally defined distance
metrics
• Partial Procrustes distance
i
d p ( z1 , z2 )  min z1  e z2
2
2

Orbit
under
rotation
• Its extension to measure weighted distance
between shapes
• It is also a metric
i
d wp ( z1 , z2 )  min Wz1  e Wz 2
2

Cm
2
dp
Pre-shape
space
Shape embedding
• Embed shapes in a Euclidean space for shape
indexing
• Optimality: minimizing the difference between the
partial Procrustes distance and the Euclidean distance
after embedding
Shape embedding
Cm
CPm-2
Each orbit
maps to a
point
Pre-shape
space
Orbit
under
rotation
Procrustean mean
Embedding shape back
into pre-shape space
 ([ z]s )  ei [ z] p : embedding function
• Objective function:
Θ  {1 , 2 ,, n }
min   ([ zi ]s )   ([ z j ]s )  d p2 ([ zi ]s , [ zi ]s )
2

i, j
Shape embedding – Optimality
Lemma: The original problem is equivalent to minimizing
G    ([ zi ]s )   ([ z j ]s )
2
i, j
Proposition: If H    ([ zi ]s )  
2
has a minimizer (Θˆ , ˆ ) , then
i
Θˆ  {ˆ1 ,ˆ2 ,,ˆn } also minimizes G    ([ zi ]s )   ([ z j ]s ) .
2
i, j
min   ([ zi ]s )   ([ z j ]s )  d p2 ([ zi ]s , [ zi ]s )
2
1
iˆ j
ˆ   e [ z j ] p
n j
Procrustean mean
size-and-shape

i, j
min

  ([ zi ]s )   ([ z j ]s )
i, j
min
Θ,
  ([ zi ]s )  
i
2
2
Shape embedding – algorithm
Algorithm: Embedding
1. Embed shapes of configurations zi at pre-shapes [zi]p with 0
initial rotations ˆi ' s ;
2. Estimate the procrustean mean:
1
1
iˆ j
ˆ    ([ z j ]s )   e [ z j ] p
n j
n j
3. Estimate the embedding functions, that is, rotations:
ˆ  angle([z ]* ˆ )
i
i p
4. Iterate until the estimates converge.
Shape distances in embedding space
• Shape distance after embedding:
d e   ([ z j ]s )   ([ zk ]s )

e
i j

*
i k
i j
[ z j ] p  e [ zk ] p e [ z j ] p  eik [ zk ] p

• Its extension to measure partial shape
distances:
d we 
e
i j
i k

*

i
[ z j ] p  e [ zk ] p W *W e j [ z j ] p  ei k [ zk ] p

Experiments
• Small metric distortion after optimal shape embedding
• Shape proximity measured by different distances
vs.
dp or de
dwp or dwe
Experiments on metric distortion
• Fraction of distance difference
FD  d e  d p / d p
• Measure the relative difference between 2 metrics using 1000 vertebral shapes
• Mean: 4.59 x 10 -4
• Variance: 5.21 x 10-7
• Overlap of nearest neighbors
Experiments – weighted distances
• Expert-given severity grades: “0” to “5” (169 graded vertebrae)
• Average grade of nearest neighbors
• Query grade “0”
Experiments – weighted distances
• Average grade of nearest neighbors
• Query grade “3”
Conclusions
• Shapes can be embedded back in Euclidean
space optimally
• Object shape correlates with the expert-given
severity grades
• We can compare both complete and partial
shapes by extend the original shape distances
to the weighted shape distances in shape space
and embedding space
Indexing Tree Adaptation
Indexing trees
• Clustering tree
• Constructed by pairwise distances – metric
spherical covers
• Retrieval – recursive
node tests
• Kd-tree
• Constructed by spatial
positions – rectangular
covers
• Retrieval – recursive
node tests
Axiomatic properties of indexing trees
• In indexing trees, each tree node is a subset of
feature points (a hypercube or a metric sphere); all
tree nodes at the same level cover the feature space
• Containment: Each child node is contained (as a
subset) in the parent node
• Monotonic: If a feature space sub-set N intersects the
query sphere, then any super set of N also intersects
the query sphere
N
REVIEW
Node tests
• Similarity retrieval recursively applies node
tests from the root to leaves
• Note test checks whether query sphere
intersects tree node covers
• If it does not, the sub-tree rooted at the node can
not contain desired points and can be ignored
• Otherwise, the sub-tree needs to be explored
further
• The ability of rejecting subsets/nodes  sublinearity
Indexing trees – performance measure
• Computational cost – average number of node tests Q
• A recursive formula
if  is a leaf node
0

QT      1  p  Q  
otherwise ;

T
  CT  

Q  1  p QT  



 ,  ,  : tree nodes
T : tree rooted at node 
CT ( ) : set of child nodes of  in tree Tρ
p :
probabilit y of  passing node tests
p | :
conditiona l probabilit y of  passing node
tests given  passing them



Indexing trees – performance measure
• Main factor – conditional probability p 
• The nodes that have high probabilities of passing
node tests are “in-efficient”.
• Need to find an efficient indexing structure based on
this performance measure
• Note: Optimizing Binary Tree is an NP-complete
problem (Hyafil and Rivest)
Indexing tree adaptation
• Develop a procedure to improve the tree performance by
deleting those “in-efficient nodes”
• Find a more efficient indexing tree by reducing the average
number of node tests Q under the operation of “node elimination”
Node Elimination
Indexing tree adaptation
• “Markovian” property



Node Elimination

• Independence property

p  p   p 
• Eliminating  will not affect the contribution to the average
computations from the nonintersecting sub-trees with .
Greedy node elimination
Compare average costs before and after
node elimination:
1  p  QT ( ) ?


 (1  p  Q
 CT (
T (  ))

)
Proposition 1:
Average computational cost decreases if and
only if
p 
1
 1
| CT ( ) |


Greedy node elimination
• Simple breadth-first tree traversal
Check each node and eliminate in-efficient ones at this level
Then, check this level
FOR Level = root+1 : leaf-1
eliminate in-efficient nodes at this level
END
Optimal tree adaptation
• Objective function:
Q min    min QT   ; and
T Τ

T min    arg min QT  
T Τ

• Search space:
• To find the optimal sub-tree rooted at node :
Set of sub-trees obtained by eliminating nodes from the
sub-tree rooted
at  : Τ
Optimal tree adaptation
Proposition 2: Optimality
1  p  Q  


,..., T C

Q min    min
QT *    min
*
T Τ


CV
T min      T min C1,min
• Proof by contradiction
min
C
min
m , min
Optimal tree adaptation
• Dynamic programming procedure:
• Tree traversal embedded in another tree traversal
THEN, Check every node below this Level
Obtain the optimal sub-tree rooted at their parent
Check every node at this Level
Obtain the optimal sub-tree rooted at their parent
• Computational complexity:
• Greedy node elimination: O(N)
• Optimal tree adaptation: O(NlogN)
Experiments
• Construct tree for the given data set
• Coordinate-based indexing tree: kd tree
• Metric-based indexing tree: clustering tree
• Compare the average computational cost
between the original tree and adapted trees
• Scalability
• Effect of dimension (intrinsic dimension)
Experiments
• Average computational cost vs. database size
Experiments
• Average computational cost vs. dimension
• D – exterior dimension
• d – intrinsic dimension
• Cost – average number of node tests
D
d
cost
2
2
89.2083
10
2
88.0517
20
2
88.6447
shape
?
314.5052
4
4
464.9511
10
10 3234.954
Conclusions
• Tree adaptation can increase the efficiency of
indexing trees by eliminating in-efficient nodes
• We can achieve the optimality under the operation of “node
elimination”
• The performance of indexing trees depends on the
distribution of feature points
• In general, coordinate-based indexing trees (kd trees)
appear to be more efficient than metric-based
indexing trees (clustering trees)
Compare Different
Shape Indexing Strategies
Shape indexing
vs.
• Constructed using
pair-wise distances
• Overlapped tree nodes
• Cannot support
different distances
equally efficiently
• Constructed using
spatial positions
(coordinates)
• Disjoint tree nodes
• Support different
distances efficiently
Performance Comparison
• Indexing performance
• Computation: average number of node tests
• Complete shape queries
• Partial shape queries
Comparison of retrievals
• Extended to partial shape retrieval
• Euclidean distance after embedding
• Weighted Euclidean distance after embedding
Conclusions
• Shape indexing after embedding gives better
performance
• Shape embedding supports efficient complete
as well as partial shape indexing
Cardiac Ultrasound Database
Query
k nearest neighbors
Dolphin Database
Query
k nearest neighbors
Summary and Future Directions
Shape-based Similarity Retrieval
Query
Future work
User
Indexing
Structure
Browsing
Relevance
Feedback
Index
based
on
shapes
Image
Database
Results
Current work
Combine results
Other Features
Searching
Indexing
Text Database
Indexing using intrinsic dimension
• Construct efficient indexing structures based on the proposed performance
measure
Practical data is not uniform
Relevance Feedback
• Update weighting matrix W for the proposed partial shape distances
• Learn the meaningful adaptive distance metric for multiple features
integrated in medical image databases
• Unify image semantics and text semantics
Similarity:
Procrustes Distance
Is there a way of providing feedback
to achieve effective retrieval?
Other Image Features
Other Distances
Patient Records
Browsing
• What are effective interactive interfaces for image databases?
• How can we construct indexing structures for efficient browsing?
Move along a path
Big Picture
BRIC
SILS
IR system
Low or middle
level features
Images
Patient Records
Image processing/analysis;
Learning/mining;
Indexing & searching;
…
(appropriate formulation)
Clinical Decisions
Treatment Plans
…
Documents
High level
knowledge
User Interface
Information model
User behaviors
Metadata
NLP
…
Acknowledgements
•
•
•
•
•
•
•
Prof. Hemant D. Tagare
Prof. James S. Duncan
Prof. Larry Staib
Prof. Robert Fulbright
Dr. Carl Jaffe
Mr. Rodney Long
Dr. Sameer Antani
Supported by R01-LM06911 from NLM
Image Processing and Analysis Group, Yale University
Finding Endocardium
Experiments
• Improvement over the original indexing trees
• Clustering tree
Average Number of Node Tests
10,000
Data Points
Dim = 2
Dim = 10
Test
Ttest
Orig.
NE
Opt.
0.0
0.0
75.85
68.14
67.46
1968.72 1302.12 1301.53
0.0
0.05,0.5
301.81
272.75
272.02
5484.99 3807.02 3807.10
0.05,0.5
0.0
75.85
76.52
70.31
1968,72 2435.49 2435.49
301.81
253.21
241.93
5484.99 3736.14 3736.14
0.05,0.5 0.05,0.5
Orig.
NE
Opt.
Experiments
• Improvement over the original indexing trees
• Kd-tree
Average Number of Node Tests
10,000
Data Points
Dim = 2
Dim = 10
Test
Ttest
Orig.
NE
Opt.
Orig.
NE
Opt.
0.0
0.0
27.13
26.3
26.24
27.14
26.29
26.24
0.0
0.05,0.5
227.69
198.44
199.86
0.05,0.5
0.0
27.13
34.78
29.18
227.69
186.97
171.71
0.05,0.5 0.05,0.5
1310.91 1225.57 1230.49
27.14
142.06
50.42
1310.91 1163.25 1134.10
Optimal tree adaptation
• Optimality
• If the sub-tree rooted at  is optimal, all of sub-trees rooted
at its child nodes are optimal
• Outer loop:
FOR Depth = leaf-2 : root
FOR each node at this depth
find the minimum cost tree
END
END
Optimal tree adaptation
• Collection of all possible children configurations of 
after node elimination :
V   CT  
T
 Τ

• Independence property
• Average computations J(X, ) for the sub-tree rooted
at  and set of sub-trees rooted at set of child nodes X
J  X ,  
1  p  Q  


min
X
Proposition 3:
min QT   
T Τ

min
J (C ,  ) 
C {  i }V i
i

i
min
Ci {  i }V i
J (Ci ,  )
Optimal tree adaptation
• From the independence property, we know the minimizing
children configuration for the sub-tree rooted at  is:
Cmin     arg
i
min
Ci {{  i }, Cmin (  i )}
J (Ci ,  )
• Inner loop:
FOR Depth = leaf-2 : depth of 
FOR each node at this depth
compare J({i}, ) and J(Cmin (i), );
find Cmin ();
END
END
Curved Manifold
N
M
A

2
• Vector Space:

• Curved Space:
  ??
B