System and method for lattice-preserving multigrid method for image segmentation and filtering
View Patent ↗A method for segmenting a digitized image includes providing a digitized image comprising a plurality of intensities corresponding to a domain of points on an N-dimensional grid, defining a weight between each pair of adjacent points in the image based on the intensity difference of each said point pair, marking a subset of points in said image wherein each marked point is marked with one of a plurality of labels, determining the probability that an unmarked point should be marked with one of said plurality of labels using a multigrid method that uses a restriction operator to map said provided image to a coarse-level gird, and a prolongation operator to map said coarse-level image back to a fine-level grid, wherein said restriction operator is an adjoint of said prolongation operator, and wherein a fine-level segmentation is a prolongation of a coarse level segmentation.
1. A computer implemented method of segmenting a digitized image, comprising the steps of:
providing a digitized image comprising a plurality of intensities corresponding to a domain of points on an N-dimensional grid;
defining a weight between each pair of adjacent points in the image based on the intensity difference of each said point pair;
marking a subset of points in said image wherein each marked point is marked with one of a plurality of labels;
determining the probability that an unmarked point should be marked with one of said plurality of labels using a multigrid method that uses a restriction operator to map said provided image to a coarse-level grid, and a prolongation operator to map said coarse-level image back to a fine-level grid, wherein said restriction operator is an adjoint of said prolongation operator, and wherein a fine-level segmentation is a prolongation of a coarse level segmentation, wherein an unmarked point is marked with a label having a highest probability, wherein said image is segmented by the labels that mark each point, and
wherein said steps of defining a weight, marking a subset of points, and determining the probability are performed by a computer processor.
2. The method of claim 1 , wherein said prolongation operator is
P
v
i
c
j
=
{
1
,
if
v
i
=
c
j
,
1
,
if
c
j
is
the
MCN
v
i
,
0
,
otherwise
.
wherein v i is a point on said image, c i is a point on said coarse level grid image, and a most strongly connected neighbor of a point is an adjacent point having a largest weight between said pair of points.
3. The method of claim 1 , wherein said multigrid method comprises calculating an approximate solution to said probabilities on a fine level grid starting from said provided image, calculating a residual to the solution, restricting the residual to said coarse level grid with said restriction operator, calculating a correction for the residual on the coarse level grid, and correcting the approximate solution on said fine level grid with a prolongated correction using said prolongation operator.
4. The method of claim 1 , further comprising representing said image by a Laplacian matrix L indexed by point pairs, wherein an element L ij for points i and j is defined by
L
ij
=
{
d
i
,
if
i
=
j
,
-
w
ij
,
if
i
and
j
represent
adjacent
nodes
,
0
,
otherwise
,
wherein w ij is said weight associated with adjacent pairs of points and d i =Σw ij for all weights incident on point i, decomposing L as
L
=
[
L
M
B
B
T
L
U
]
,
wherein L M is the Laplacian for the marked points, L U is the Laplacian for the unmarked points, and B comprises those elements of L that are left over, representing the probability for each unmarked point i with respect to a marked point s by x i s , said unmarked probabilities forming a vector x U , wherein the probabilities for each unmarked point can be determined by solving L U x U =b, wherein b is a function.
5. The method of claim 1 , wherein each said weight w ij between a point v i adjacent to point v j on a fine level grid is determined by
w
ij
=
exp
(
-
β
(
g
i
-
g
j
)
2
)
,
where g i and g j are the intensities of points i and j, respectively, and β is a free parameter.
6. The method of claim 1 , wherein said weight between two adjacent coarse nodes v i , v j , on a coarse level grid includes a term proportional to
w
ij
=
∑
M
*
(
v
s
)
=
v
i
,
M
*
(
v
q
)
=
v
j
,
∀
v
s
,
v
j
w
sq
wherein w sq is the weight between fine level grid points v s , v q , the operator
M
*
(
v
i
∈
N
k
)
=
v
j
∈
N
0
produces a coarse node from k applications of operator
M
(
v
i
∈
N
k
)
=
v
j
∈
N
k
-
1
that maps each neighbor point in N k to its maximally connected neighbor point, and wherein N k is a set of points wherein a number of odd digits in a coordinate of each said point is equal to k and N 0 is the coarse level grid.
7. The method of claim 4 , wherein said probability that an unmarked point is be marked with one of said plurality of labels is determined by an initial linear system
Lx
f
=
b
f
,
wherein L is a Laplacian matrix with a fine-level probability solution, x f and fine-level grid function b f , and said coarse level grid linear system is
P
T
LPx
C
=
P
T
b
C
,
wherein P is a prolongation operator, P T is a restriction operator, and x c and b c are coarse level probability solutions and functions.
8. The method of claim 1 , wherein coarsening said image with said restriction operator further comprises assigning each k th -order neighbor of a point in an object to be segmented the same label on a fine-level grid as its most strongly connected (k−1) th -order neighbor point, and assigning a k th -order neighbor of a point in an object to be segmented that is equally connected to multiple (k−1) th -order neighbors the label of any one of these neighbors, wherein a point belongs to a k th order set if a number of odd digits in its coordinates are equal to k.
9. A computer implemented method of segmenting a digitized image, comprising the steps of:
providing a digitized image comprising a plurality of intensities corresponding to a domain of points on an N-dimensional grid;
marking a subset of points in said image wherein each marked point is marked with one of a plurality of labels;
determining the probability that an unmarked point should be marked with one of said plurality of labels solving a linear system
Lx
f
=
b
f
,
using a multigrid method wherein L is a Laplacian matrix representing said image with a probability solution x f for said provided image and grid function b f , and a coarse level grid linear system is
P
T
LPx
C
=
P
T
b
C
,
wherein P is a prolongation operator, P T is a restriction operator, and x c and b c are coarse level probability solutions and functions, wherein an unmarked point is marked with a label having a highest probability, wherein said image is segmented by the labels that mark each point, and
wherein said steps of marking a subset of points, and determining the probability are performed by a computer processor.
10. The method of claim 9 , wherein said multigrid method uses said restriction operator to map said provided image to said coarse-level gird, and said prolongation operator to map said coarse-level image back to a fine-level grid, wherein said restriction operator is an adjoint of said prolongation operator, and wherein a fine-level segmentation is a prolongation of a coarse level segmentation.
11. The method of claim 9 , wherein said Laplacian matrix L that represents said image is indexed by point pairs, wherein an element L ij for points i and j is defined by
L
ij
=
{
d
i
,
if
i
=
j
,
-
w
ij
,
if
i
and
j
represent
adjacent
nodes
,
0
,
otherwise
,
wherein w ij is a weight associated with adjacent pairs of points, said weight based on the intensity difference of each said point pair, and d i =Σw ij for all weights incident on point i, decomposing L as
L
=
[
L
M
B
B
T
L
U
]
,
wherein L M is the Laplacian for the marked points, L U is the Laplacian for the unmarked points, and B comprises those elements of L that are left over, representing the probability for each unmarked point i with respect to a marked point s by x i s , said unmarked probabilities forming a vector x U , wherein the probabilities for each unmarked point can be determined by solving L U x U =b, wherein b is a function.
12. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform the method steps for segmenting a digitized image, comprising the steps of:
providing a digitized image comprising a plurality of intensities corresponding to a domain of points on an N-dimensional grid;
defining a weight between each pair of adjacent points in the image based on the intensity difference of each said point pair;
marking a subset of points in said image wherein each marked point is marked with one of a plurality of labels;
determining the probability that an unmarked point should be marked with one of said plurality of labels using a multigrid method that uses a restriction operator to map said provided image to a coarse-level grid, and a prolongation operator to map said coarse-level image back to a fine-level grid, wherein said restriction operator is an adjoint of said prolongation operator, and wherein a fine-level segmentation is a prolongation of a coarse level segmentation.
13. The computer readable program storage device of claim 12 , wherein said prolongation operator is
P
v
i
c
j
=
{
1
,
if
v
i
=
c
j
,
1
,
if
c
j
is
the
MCN
v
i
,
0
,
otherwise
.
wherein v i is a point on said image, c i is a point on said coarse level grid image, and a most strongly connected neighbor of a point is an adjacent point having a largest weight between said pair of points.
14. The computer readable program storage device of claim 12 , wherein said multigrid method comprises calculating an approximate solution to said probabilities on a fine level grid starting from said provided image, calculating a residual to the solution, restricting the residual to said coarse level grid with said restriction operator, calculating a correction for the residual on the coarse level grid, and correcting the approximate solution on said fine level grid with a prolongated correction using said prolongation operator.
15. The computer readable program storage device of claim 12 , the method further comprising representing said image by a Laplacian matrix L indexed by point pairs, wherein an element L ij for points i and j is defined by
L
ij
=
{
d
i
,
if
i
=
j
,
-
w
ij
,
if
i
and
j
represent
adjacent
nodes
,
0
,
otherwise
,
wherein w ij is said weight associated with adjacent pairs of points and d i =Σw ij for all weights incident on point i, decomposing L as
L
=
[
L
M
B
B
T
L
U
]
,
wherein L M is the Laplacian for the marked points, L U is the Laplacian for the unmarked points, and B comprises those elements of L that are left over, representing the probability for each unmarked point i with respect to a marked points by x i s , said unmarked probabilities forming a vector x U , wherein the probabilities for each unmarked point can be determined by solving L U x U =b, wherein b is a function.
16. The computer readable program storage device of claim 12 , wherein each said weight w ij between a point v i adjacent to point v j on a fine level grid is determined by
w
ij
=
exp
(
-
β
(
g
i
-
g
j
)
2
)
,
where g i and g j are the intensities of points i and j, respectively, and β is a free parameter.
17. The computer readable program storage device of claim 12 , wherein said weight between two adjacent coarse nodes v i , v j , on a coarse level grid includes a term proportional to
w
ij
=
∑
M
*
(
v
s
)
=
v
i
,
M
*
(
v
q
)
=
v
j
,
∀
v
s
,
v
j
w
sq
wherein w sq is the weight between fine level grid points v s , V q , the operator
M
*
(
v
i
∈
N
k
)
=
v
j
∈
N
0
produces a coarse node from k applications of operator
M
(
v
i
∈
N
k
)
=
v
j
∈
N
k
-
1
that maps each neighbor point in N k to its maximally connected neighbor point, and wherein N k is a set of points wherein a number of odd digits in a coordinate of each said point is equal to k and N 0 is the coarse level grid.
18. The computer readable program storage device of claim 15 , wherein said probability that an unmarked point is be marked with one of said plurality of labels is determined by an initial linear system
Lx
f
=
b
f
,
wherein L is a Laplacian matrix with a fine-level probability solution, x f and fine-level grid function b f , and said coarse level grid linear system is
P
T
LPx
C
=
P
T
b
C
,
wherein P is a prolongation operator, P T is a restriction operator, and x c and b c are coarse level probability solutions and functions.
19. The computer readable program storage device of claim 12 , wherein coarsening said image with said restriction operator further comprises assigning each k th -order neighbor of a point in an object to be segmented the same label on a fine-level grid as its most strongly connected (k−1) th -order neighbor point, and assigning a k th -order neighbor of a point in an object to be segmented that is equally connected to multiple (k−1) th -order neighbors the label of any one of these neighbors, wherein a point belongs to a k th order set if a number of odd digits in its coordinates are equal to k.