Fast parametric non-rigid image registration based on feature correspondences
View Patent ↗A method and system for non-rigidly registering a fixed to a moving image utilizing a B-Spline based free form deformation (FFD) model is disclosed. The methodology utilizes sparse feature correspondences to estimate an elastic deformation field in a closed form. In a multi-resolution manner, the method is able to recover small to large non-rigid deformations. The resulting deformation field is globally smooth and guarantees one-to-one mapping between the images being registered. The method generally comprises the steps of: detecting feature points on the fixed image and feature points on the moving image; assigning a feature vector to each feature point; calculating the dissimilarity of each pair of feature vectors for feature pairs on the fixed image and the moving image; calculating the correspondence between feature pairs based on the dissimilarity measure; solving for a dense deformation field P using a closed form FFD model; and transforming the moving image and the feature points on the moving image using a current FFD deformation field estimate.
1. In a computer, a method of non-rigid image registration between a fixed image and a moving image, comprising the steps of:
(a) detecting feature points on the fixed image and feature points on the moving image;
(b) assigning a feature vector to each feature point;
(c) calculating the dissimilarity of each pair of feature vectors for feature pairs on the fixed image and the moving image;
(d) calculating the correspondence between feature pairs based on dissimilarity measure: Xi and Xi′;
(e) solving for a dense deformation field P using a closed form free from deformation (FFD) model; and
(f) transforming the moving image and the feature points on the moving image using a current FFD deformation field estimate.
2. The method recited in claim 1 , further comprising repeating steps (b) through (d) to minimize the deformation field estimate.
3. The method recited in claim 1 , wherein the selected feature points have the highest local entropy.
4. The method recited in claim 1 , wherein given a regular lattice of control points:
P m,n =( P m,n x ,P m,n y ); m= 1, . . . , M,n=1 , . . . ,N
overlaid to an image region
Γ={ x }={( x,y )|1≦ x≦X, 1 ≦y≦Y}
the initial configuration of a control lattice is denoted as P 0 , and the deforming control lattice as P=P 0 +dP, where the FFD parameters are the deformations of the control points in both directions (xy);
Θ={(δ P m,n x ,δP m,n y )};( m,n )∈[1 ,M]×[ 1 ,N]
and given the deformation of the control lattice from P 0 to P, the deformed location L(x)=(x′,y′) of a pixel x=(x,y), is defined in terms of a tensor product of a Cubic B-spline:
L
(
x
)
=
x
+
δ
L
(
x
)
=
∑
k
=
0
3
∑
l
=
0
3
B
k
(
u
)
B
l
(
v
)
(
P
i
+
k
,
j
+
l
0
+
δ
P
i
+
k
,
j
+
l
)
.
5. The method recited in claim 4 , wherein x i ′ is assumed to be the deformed location L(x), and the relationship between the two point sets can be represented as follows:
U=Sp
where, U is the displacement matrix between the correspondence pairs:
U
=
(
x
1
′
-
x
1
y
1
′
-
y
1
x
2
′
-
x
2
y
2
′
-
y
2
⋮
⋮
x
n
′
-
x
n
y
n
′
-
y
n
)
n
×
2
,
S is the Cubic B-spline basis matrix:
S
=
(
…
…
[
b
i
1
+
0
,
j
1
+
l
]
…
[
b
i
1
+
1
,
j
1
+
l
]
…
[
b
i
1
+
2
,
j
1
+
l
]
…
[
b
i
1
+
3
,
j
1
+
l
]
⋯
⋰
⋰
⋰
⋰
⋰
…
[
b
i
c
+
0
,
j
c
+
l
]
…
[
b
i
c
+
1
,
j
c
+
l
]
…
[
b
i
c
+
2
,
j
c
+
l
]
[
b
i
c
+
3
,
j
c
+
l
]
…
…
⋰
⋰
⋰
⋰
⋰
…
…
[
b
i
n
+
0
,
j
n
+
l
]
…
[
b
i
n
+
1
,
j
n
+
l
]
…
[
b
i
n
+
2
,
j
n
+
l
]
…
[
b
i
n
+
3
,
j
n
+
l
]
⋯
)
,
And p is comprised of the FFD parameters in a matrix:
(
δ
P
1
,
1
x
δ
P
1
,
1
y
δ
P
1
,
2
x
δ
P
1
,
2
y
⋮
⋮
[
δ
P
i
c
+
0
,
j
c
+
l
x
]
[
δ
P
i
c
+
0
,
j
c
+
l
y
]
⋮
⋮
[
δ
P
i
c
+
1
,
j
c
+
l
x
]
[
δ
P
i
c
+
1
,
j
c
+
l
y
]
⋮
⋮
[
δ
P
i
c
+
2
,
j
c
+
l
x
]
[
δ
P
i
c
+
2
,
j
c
+
l
y
]
⋮
⋮
[
δ
P
i
c
+
3
,
j
c
+
l
x
]
[
δ
P
i
c
+
3
,
j
c
+
l
y
]
⋮
⋮
δ
P
M
,
N
x
δ
P
M
,
N
y
)
(
M
×
N
)
×
2
,
in the B-Spline basis matrix S, c=1, . . . , n is the index of a corresponding pair, and [b i c +k,j c +l ] is the abbreviation for:
[ b i c +k,j c +l ]=(B k ( u c ) B 0 ( v c ) B k ( u c ) B 1 ( v c ) B k ( u c ) B 3 ( v c ) B k ( u c ) B 3 ( v c )),
in the FFD parameter p matrix, [δP i c +k,j c +l ] is the abbreviation for:
[
δ
P
i
c
+
k
,
j
c
+
l
]
=
(
δ
P
i
c
+
k
,
j
c
+
0
δ
P
i
c
+
k
,
j
c
+
1
δ
P
i
c
+
k
,
j
c
+
2
δ
P
i
c
+
k
,
j
c
+
3
)
,
wherein, a closed form solution for the control lattice deformation can be solved utilizing Singular value Decomposition as:
p
^
=
S
+
U
.
6. A computer readable memory medium containing program instructions which, when executed by a processor, enable a computer to non-rigidly register a fixed image to a moving image, by;
(a) detecting feature points on the fixed image and feature points on the moving image;
(b) assigning a feature vector to each feature point;
(c) calculating the dissimilarity of each pair of feature vectors for feature pairs on the fixed image and the moving image;
(d) calculating the correspondence between feature pairs based on dissimilarity measure: Xi and Xi′;
(e) solving for a dense deformation field P using a closed form free form deformation (FFD) model; and
(f) transforming the moving image and the feature points on the moving image using a current FFD deformation field estimate.
7. The computer readable memory medium recited in claim 6 , further comprising program instructions which, when executed by the processor, repeat steps (c) through (f) to minimize the deformation field estimate.
8. The computer readable memory medium recited in claim 6 , wherein given a regular lattice of control points:
P m,n =( P m,n x ,P m,n y ); m= 1, . . . , M,n=1 , . . . ,N
overlaid to an image region
Γ={ x }={( x,y )|1≦ x≦X, 1 ≦y≦Y}
the initial configuration of a control lattice is denoted at P 0 , and the deforming control lattice as P=P 0 +dP, where the FFD parameters are the deformations of the control points in both directions (x,y);
Θ={(δ P m,n x ,δP m,n y )};( m,n )∈[1 ,M]×[ 1 ,N]
and given the deformation of the control lattice from P 0 to P, the deformed location L(x)=(x′,y′) of a pixel x=(x,y), is defined in terms of a tensor product of a Cubic B-spline:
L
(
x
)
=
x
+
δ
L
(
x
)
=
∑
k
=
0
3
∑
l
=
0
3
B
k
(
u
)
B
l
(
v
)
(
P
i
+
k
,
j
+
l
0
+
δ
P
i
+
k
,
j
+
l
)
.
9. The computer readable medium recited in claim 8 , wherein x i ′ is assumed to be the deformed location L(x), and the relationship between the two point sets can be represented as follows:
U=Sp
where, U is the displacement matrix between the correspondence pairs:
U
=
(
x
1
′
-
x
1
y
1
′
-
y
1
x
2
′
-
x
2
y
2
′
-
y
2
⋮
⋮
x
n
′
-
x
n
y
n
′
-
y
n
)
n
×
2
,
S is the Cubic B-spline basis matrix:
S
=
(
…
…
[
b
i
1
+
0
,
j
1
+
l
]
…
[
b
i
1
+
1
,
j
1
+
l
]
…
[
b
i
1
+
2
,
j
1
+
l
]
…
[
b
i
1
+
3
,
j
1
+
l
]
…
⋰
⋰
⋰
⋰
⋰
…
[
b
i
c
+
0
,
j
c
+
l
]
…
[
b
i
c
+
1
,
j
c
+
l
]
…
[
b
i
c
+
2
,
j
c
+
l
]
[
b
i
c
+
3
,
j
c
+
l
]
…
…
⋰
⋰
⋰
⋰
⋰
…
…
[
b
i
n
+
0
,
j
n
+
l
]
…
[
b
i
n
+
1
,
j
n
+
l
]
…
[
b
i
n
+
2
,
j
n
+
l
]
…
[
b
i
n
+
3
,
j
n
+
l
]
…
)
,
and p is comprised of the FFD parameters in a matrix:
(
δ
P
1
,
1
x
δ
P
1
,
1
y
δ
P
1
,
2
x
δ
P
1
,
2
y
⋮
⋮
[
δ
P
i
c
+
0
,
j
c
+
l
x
]
[
δ
P
i
c
+
0
,
j
c
+
l
y
]
⋮
⋮
[
δ
P
i
c
+
1
,
j
c
+
l
x
]
[
δ
P
i
c
+
1
,
j
c
+
l
y
]
⋮
⋮
[
δ
P
i
c
+
2
,
j
c
+
l
x
]
[
δ
P
i
c
+
2
,
j
c
+
l
y
]
⋮
⋮
[
δ
P
i
c
+
3
,
j
c
+
l
x
]
[
δ
P
i
c
+
3
,
j
c
+
l
y
]
⋮
⋮
δ
P
M
,
N
x
δ
P
M
,
N
y
)
(
M
×
N
)
×
2
,
in the B-Spline basis matrix S, c=1, . . . , n is the index of a corresponding pair, and [b i c +k,j c +l ]is the abbreviation for:
[
b
i
c
+
k
,
j
c
+
l
]
=
(
B
k
(
u
c
)
B
0
(
v
c
)
B
k
(
u
c
)
B
1
(
v
c
)
B
k
(
u
c
)
B
2
(
v
c
)
B
k
(
u
c
)
B
3
(
v
c
)
)
,
in the FFD parameter p matrix, [δP i c +k,j c +l ] is the abbreviation for:
[
δ
P
i
c
+
k
,
j
c
+
l
]
=
(
δ
P
i
c
+
k
,
j
c
+
0
δ
P
i
c
+
k
,
j
c
+
1
δ
P
i
c
+
k
,
j
c
+
2
δ
P
i
c
+
k
,
j
c
+
3
)
,
wherein, a closed form solution for the control lattice deformation can be solved utilizing Singular value Decomposition as:
p
^
=
S
+
U
.