July 11, 2000.
2D-3D Registration Based on Shape Matching
Christopher M. Cyr, Thomas B. Sebastian, Benjamin B. Kimia
Division of Engineering
Brown University
Providence, RI 02912
- Clinical Problem
- Problem Formulation
- Efficiency and Robustness
- Proposed Solution
- Requirements on the Shape Similarity Measure
- Requirements on the Exemplar Resolution
- Shape Similarity Measures
- Monotinicity
- Results of Coarse Level Matching
- Results of Hierarchical Matching
- Conclusions
- A majority of adults eventually face back problems
[An, Riley III, "An Atlas of Surgery of the Spine"]
- Less invasive, image guided procedures can improve the "success" of treatment
- 3D CT or MR images are usually available
- Current practice verifies needle placement by intraoperative fluoroscopic/X-ray images.
- 3D MR/CT's used by surgeons as guides.
[An, Riley III, "An Atlas of Surgery of the Spine"]
- Goal: reduce the use of X-ray imaging to reduce radiation exposure to both patients and physicians.
- "Tactile" mapping of the back of spine vertebrae faces accuracy limitations for needle placement.
- Another Application: Measure 3D bone dynamics for 2D images
[Sebastian, et al.]
Study the motion of the thumb metacarpal from 2D X-ray images.
- Use a single X-ray image to register patient and imaging coordinates (2D-3D registration) between projected views and query views.
- Related approaches in computer vision:
- 3D Object recognition approaches from a collection of 2D view, e.g. aspect Graph representation
- Pose estimation
- Segment the structure of interest in the 3D data set, e.g. spine vertebra
- Project the 3D shape onto a dense sampling of the viewing sphere to the desired accuracy (i.e. 5 degree increments produce approximately 2500)
Illustration of the process of
projection based pose estimation
Example of projected views generated at a coarse level:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- Segment the outline of the structure of interest in the 2D image (the Query View) [Sebastian, et al:MICCA98]
- Among all projected views find the one (Target View) which best matches the Query View.
Given sufficient topological complexity, the similarity between the query view and projected views can be used to determine pose.
- Can the relative pose of a known 3D object in an image be recovered efficiently, robustly, and automatically using projected shape similarity?
- How accurate is the registration procedure?
- The large number of views to match to, renders brute force matching impractical
- The use of a gradient descent algorithm (e.g. ICP) requires user interaction to initialize the model [Besl, McKay : PAMI92]
- The user initialization usually prevents occurrence of local minima
Proposed Solution: Hierarchical Registration
- Sampling of views (exemplar views) at different resolutions
- Match the top exemplar and re-sample
- Repeat to convergence
Requirements on the Shape Similarity Metric:
- The shape similarity metric should be monotonically increasing, with geodesic distance on the viewing sphere, in some neighborhood U represented by an exemplar view Vi , i.e.,
d(V, Vi) should be monotonically increasing
with 
along each direction of the sphere.
Requirements on the exemplar resolution:
The coarse level exemplar view
representing the target view (Vi) should be closer to the query view then all
other coarse level exemplar views (Vi), i.e. d( Vio, Q) < d(Vi,
Q), i != io
We used two different measures:
1. Distance obtained by the "graduated assignment" graph matching method [Gold, Rangarajan : PAMI96] applied to shock graph matching [Sharvit, et al : JVCIP98].
Graduated assignment shock graph matching:
2. Distance obtained by the recent "Edit Distance" metric [Sebastian, Klein, Kimia : 2000]
Edit Distance shock graph matching:
An examination of these
distances reveals that for a large set of rotations, monotinicity holds.
|
This table illustrates that the distance
monotonically increases as the geodesic distance increases |
|||
|
ANGLE |
IMAGE |
d(T, Vi) x 10^2 |
d(Vi, Vi+1) x 10^2 |
|
|
|
00.00 |
08.03 |
|
|
|
08.03 |
06.78 |
|
. |
|
09.93 |
06.54 |
|
|
|
10.19 |
08.69 |
|
|
|
12.07 |
10.36 |
|
|
|
12.21 |
08.49 |
|
|
|
12.63 |
06.62 |
|
|
|
12.86 |
12.01 |
|
|
|
14.57 |
12.94 |
|
|
|
14.58 |
13.51 |
|
|
|
11.43 |
9.49 |
|
|
|
11.12 |
9.73 |
|
|
|
9.71 |
8.68 |
|
|
|
9.65 |
10.19 |
|
|
|
11.19 |
9.59 |
|
|
|
12.06 |
10.13 |
|
|
|
11.51 |
10.05 |
|
|
|
11.86 |
8.01 |
|
|
|
12.05 |
5.96 |
|
|
|
12.69 |
12.34 |
|
|
|
14.03 |
11.68 |
|
|
|
12.85 |
10.83 |
|
|
|
10.39 |
9.84 |
|
|
|
9.50 |
9.50 |
Results of Coarse Level Matching:
Query
View:
Images
and Shock representations of projections of a spine vertebra generated at a
coarse level:
Query
View:
The projections of a Carpal bone generated at
a coarse level:
Unknown
image (query view) and best two coarse level matches:
- Spine Model 1:
|
|
Unknown View (Query View)
[PHI= 19 THETA=162]
These
tables show an example of the results of focusing on a spine vertebra model,
using the best matches (shown in bold) to
form the boundaries of the next matching process.
1st Pass:
|
Rank |
Phi |
Theta |
Image |
|
1 |
000.00 |
135.00 |
|
|
2 |
000.00 |
180.00 |
|
|
3 |
045.00 |
180.00 |
|
2nd Pass:
|
Rank |
Phi |
Theta |
Image |
|
1 |
022.50 |
157.50 |
|
|
2 |
000.00 |
157.50 |
|
|
3 |
000.00 |
180.00 |
|
3rd Pass:
|
Rank |
Phi |
Theta |
Image |
|
1 |
022.50 |
157.50 |
|
|
2 |
011.25 |
168.75 |
|
|
3 |
011.25 |
157.50 |
|
4th Pass:
|
Rank |
Phi |
Theta |
Image |
|
1 |
022.50 |
157.50 |
|
|
2 |
017.00 |
157.50 |
|
|
3 |
017.00 |
163.00 |
|
5th Pass:
|
Rank |
Phi |
Theta |
Image |
|
1 |
020.00 |
160.00 |
|
|
2 |
017.00 |
160.00 |
|
|
3 |
017.00 |
163.00 |
|
6th Pass:
|
Rank |
Phi |
Theta |
Image |
|
1 |
019.00 |
162.00 |
|
|
2 |
018.00 |
160.00 |
|
|
3 |
018.00 |
162.00 |
|
- Spine Model 2:
|
Unknown View (Query View) |
|
|
These tables show an example of the results of
focusing on a second spine vertebra model,
using the best matches (shown in bold) to
form the boundaries of the next matching process.
1st Pass:
|
Rank |
Phi |
Theta |
Image |
|
1 |
045.00 |
180.00 |
|
|
2 |
000.00 |
135.00 |
|
|
3 |
000.00 |
045.00 |
|
2nd Pass:
|
Rank |
Phi |
Theta |
Image |
|
1 |
022.50 |
180.00 |
|
|
2 |
000.00 |
157.50 |
|
|
3 |
000.00 |
180.00 |
|
3rd Pass:
|
Rank |
Phi |
Theta |
Image |
|
1 |
011.25 |
168.75 |
|
|
2 |
022.50 |
168.75 |
|
|
3 |
011.25 |
180.00 |
|
4th Pass:
|
Rank |
Phi |
Theta |
Image |
|
1 |
011.25 |
168.75 |
|
|
2 |
017.00 |
174.00 |
|
|
3 |
023.00 |
168.75 |
|
5th Pass:
|
Rank |
Phi |
Theta |
Image |
|
1 |
011.00 |
168.75 |
|
|
2 |
014.00 |
171.00 |
|
|
3 |
011.00 |
171.00 |
|
6th Pass:
|
Rank |
Phi |
Theta |
Image |
|
1 |
013.00 |
170.00 |
|
|
2 |
014.00 |
170.00 |
|
|
3 |
014.00 |
171.00 |
|
- Carpal Bone:
|
Unknown View (Query View): [PHI= 80 THETA=15] |
|
|
These tables show an example of the results of
focusing on a carpal bone model,
using the best matches (shown in bold) to
form the boundaries of the next matching process.
1st Pass:
|
Rank |
Phi |
Theta |
Image |
|
1 |
090.00 |
000.00 |
|
|
2 |
045.00 |
000.00 |
|
|
3 |
045.00 |
045.00 |
|
2nd Pass:
|
Rank |
Phi |
Theta |
Image |
|
1 |
067.50 |
000.00 |
|
|
2 |
090.00 |
022.50 |
|
|
3 |
067.50 |
022.50 |
|
3rd Pass:
|
Rank |
Phi |
Theta |
Image |
|
1 |
078.75 |
022.50 |
|
|
2 |
090.00 |
011.25 |
|
|
3 |
078.75 |
011.25 |
|
4th Pass:
|
Rank |
Phi |
Theta |
Image |
|
1 |
078.75 |
011.25 |
|
|
2 |
084.00 |
017.00 |
|
|
3 |
084.00 |
011.25 |
|
5th Pass:
|
Rank |
Phi |
Theta |
Image |
|
1 |
081.00 |
017.00 |
|
|
2 |
078.00 |
014.00 |
|
|
3 |
078.00 |
017.00 |
|
6th Pass:
|
Rank |
Phi |
Theta |
Image |
|
1 |
080.00 |
014.00 |
|
|
2 |
080.00 |
016.00 |
|
|
3 |
079.00 |
015.00 |
|
To compute error, we used: 
where:
represents the actual
angles corresponding to the query views, and