System and method for 3D volume segmentation using exact minimal surfaces given a boundary
View Patent ↗A method for 3D volume segmentation in digitized medical images includes providing a digitized medical image defined on an N-dimensional lattice, obtaining an oriented closed 2-dimensional contour on one or more 2-dimensional slices from said image, defining face weights w from said image intensities by forming a dual lattice of said image lattice, minimizing ∑ i w i z i summed over all faces subject to the constraint Bz=r wherein vector z is an indicator vector indicating whether a face is present in a minimum-weight surface, vector r is an indicator vector of said 2-D contour, and wherein B is an edge-face incidence matrix, and segmenting said 3-D image into distinct regions separated by the minimum-weight surface indicated by said vector z.
1. A method for 3D volume segmentation in digitized medical images comprising the steps of:
providing a digitized medical 3D image, said image comprising a plurality of intensities corresponding to a domain of points on an N-dimensional lattice;
obtaining an oriented closed 2-dimensional contour on one or more 2-dimensional slices from said image;
defining face weights w from said image intensities by forming a dual lattice of said image lattice;
minimizing
∑
i
w
i
z
i
summed over all faces subject to the constraint Bz=r wherein vector z is an indicator vector indicating whether a face is present in a minimum-weight surface, vector r is an indicator vector of said 2-D contour, and wherein B is an edge-face incidence matrix; and
segmenting said 3-D image into distinct regions separated by the minimum-weight surface indicated by said vector z.
2. The method of claim 1 , wherein the weight of an outside face is assigned arbitrarily.
3. The method of claim 1 , wherein said edge-face incidence matrix B is defined by
B
e
,
f
=
{
+
1
if
the
edge
borders
the
face
with
coherent
orientation
,
-
1
if
the
edge
borders
the
face
with
anti
-
coherent
orientation
,
0
otherwise
.
4. The method of claim 1 , wherein said contour indicator vector r is defined by
r
i
=
{
+
1
if
the
edge
e
i
belongs
to
the
contour
with
coherent
orientation
,
-
1
if
the
edge
e
i
belongs
to
the
contour
with
anti
-
coherent
orientation
,
0
otherwise
.
5. The method of claim 1 , wherein every point in said primal lattice is associated with a volume in said dual lattice, and further comprising associating the intensity value of each primal lattice point with a point at the center of the corresponding dual lattice volume.
6. The method of claim 5 , wherein said weights w i are proportional to exp(−β(I j −I k ) 2 ), wherein I j and I k represent the values associated with dual lattice points j and k, respectively, and β is a predefined constant.
7. The method of claim 1 , wherein the minimization of
∑
i
w
i
z
i
subject to Bz=r is performed by a linear programming solver.
8. The method of claim 1 , further comprising obtaining a plurality of contours from said image, wherein each said contour extends over one or more 2-dimensional slices in said image, and wherein said vector r is an indicator vector for all of said plurality of contours.
9. A method for 3D volume segmentation in digitized medical images comprising the steps of:
providing a digitized medical 3D image, said image comprising a plurality of intensities corresponding to a domain of points on an N-dimensional lattice;
obtaining one or more 2-dimensional closed contours from said image;
forming a dual lattice from said image, wherein every point is said dual lattice is associated with a point of said image and said value associated with a dual lattice point is the intensity associated with said image point;
defining face weights w proportional to exp(−β(I j −I k ) 2 ), wherein I j and I k represent the values associated with dual lattice points j and k, respectively, and β is a predefined constant;
forming a minimum-weight surface from said face weights having said one or more contours as boundaries; and
segmenting said 3-D image into distinct regions separated by said minimum-weight surface.
10. The method of claim 9 , wherein each said closed contour is oriented.
11. The method of claim 9 , wherein each said closed contour extends over one or more 2-dimensional slices in said image.
12. The method of claim 9 , wherein forming a minimum-weight surface further comprises minimizing
∑
i
w
i
z
i
summed over all faces subject to the constraint Bz=r wherein vector z is an indicator vector indicating whether a face is present in said minimum-weight surface, vector r is an indicator vector of said one or more 2-D contours, and wherein B is an edge-face incidence matrix.
13. The method of claim 9 , wherein said one or more contours are obtained from a 2-dimensional segmentation procedure.
14. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform the method steps for 3D volume segmentation in digitized medical images, said method comprising the steps of:
providing a digitized medical 3D image, said image comprising a plurality of intensities corresponding to a domain of points on an N-dimensional lattice;
obtaining an oriented closed 2-dimensional contour on one or more 2-dimensional slices from said image;
defining face weights w from said image intensities by forming a dual lattice of said image lattice;
minimizing
∑
i
w
i
z
i
summed over all faces subject to the constraint Bz=r wherein vector z is an indicator vector indicating whether a face is present in a minimum-weight surface, vector r is an indicator vector of said 2-D contour, and wherein B is an edge-face incidence matrix; and
segmenting said 3-D image into distinct regions separated by the minimum-weight surface indicated by said vector z.
15. The computer readable program storage device of claim 14 , wherein the weight of an outside face is assigned arbitrarily.
16. The computer readable program storage device of claim 14 , wherein said edge-face incidence matrix B is defined by
B
e
,
f
=
{
+
1
if
the
edge
borders
the
face
with
coherent
orientation
,
-
1
if
the
edge
borders
the
face
with
anti
-
coherent
orientation
,
0
otherwise
.
17. The computer readable program storage device of claim 14 , wherein said contour indicator vector r is defined by
r
i
=
{
+
1
if
the
edge
e
i
belongs
to
the
contour
with
coherent
orientation
,
-
1
if
the
edge
e
i
belongs
to
the
contour
with
anti
-
coherent
orientation
,
0
otherwise
.
18. The computer readable program storage device of claim 14 , wherein every point in said primal lattice is associated with a volume in said dual lattice, and further comprising associating the intensity value of each primal lattice point with a point at the center of the corresponding dual lattice volume.
19. The computer readable program storage device of claim 18 , wherein said weights w i are proportional to exp(−β(I j −I k ) 2 ), wherein I j and I k represent the values associated with dual lattice points j and k, respectively, and β is a predefined constant.
20. The computer readable program storage device of claim 14 , wherein the minimization of
∑
i
w
i
z
i
subject to Bz=r is performed by a linear programming solver.
21. The computer readable program storage device of claim 14 , the method further comprising obtaining a plurality of contours from said image, wherein each said contour extends over one or more 2-dimensional slices in said image, and wherein said vector r is an indicator vector for all of said plurality of contours.