System and method for image segmentation by a weighted multigrid solver
View Patent ↗A method of segmenting a digitized image includes providing a digitized image on a domain of points on an N%N 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 the image, associating a probability potential with each unmarked point, and using a multigrid method to solve for the probability potentials for each unmarked point, wherein a restriction operator for the image is applied to an (N−1)%(N−1) image wherein each image weight is treated as a function of an adjoining point for application of the restriction operator, wherein said restriction operator determines weights of a coarse level grid.
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×N grid wherein N is a positive integer;
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 the image;
associating a probability potential with each unmarked point; and
using a multigrid method and a computer to solve for the probability potentials for each unmarked point, wherein a restriction operator for the image is applied to an (N−1)×(N−1) image wherein each said weight in the image is associated with an adjoining point to define a weight for applying said restriction operator, wherein said restriction operator determines weights of a coarse level grid.
2. The method of claim 1 , wherein the probability potential for each unmarked point represents the probability that a random walker starting from each said unmarked point reaches a marked point.
3. The method of claim 2 , wherein the probability that a random walker starting from an unmarked point reaches a marked point is calculated for each marked point,
4. The method of claim 1 , wherein each said weight w ij between a point v i adjacent to point v j 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.
5. 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
points
,
0
otherwise
where 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 potential for each unmarked point i with respect to a marked point s by x i s , said unmarked probability potentials forming a vector x U , wherein the probability potentials for each unmarked point can be determined by solving L U x U =ƒ, wherein ƒ is a function.
6. The method of claim 5 , wherein a point is assigned to a segment of a marked point according to max s ( i s ).
7. The method of claim 1 , wherein said multigrid method comprises calculating an approximate solution to the probability potentials on a fine level grid, calculating a residual to the approximate 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 a prolongation operator, wherein said prolongation operator is an adjoint of said restriction operator.
8. The method of claim 7 , wherein said prolongation operator from a point x 1 (i, j) on the coarse grid to a point on the fine grid x 0 is defined by the transformations
x
0
(
2
i
,
2
j
)
=
x
1
(
i
,
j
)
∀
i
,
j
x
0
(
2
i
+
1
,
2
j
)
=
W
E
x
E
0
+
w
W
x
W
0
w
E
+
w
W
x
0
(
2
i
+
1
,
2
j
+
1
)
=
w
N
x
N
0
+
w
E
x
E
0
+
w
S
x
S
0
+
w
W
x
W
0
w
N
+
w
E
+
w
S
+
w
W
,
wherein the labels E, W, N, S indicate, respectively, the east/west/north/south neighbors of a point and their corresponding weights.
9. The method of claim 7 , wherein said restriction operator from a point on the fine grid x 0 to a point x 1 (i, j) on the coarse grid is defined by the transformations
x
0
(
2
i
+
1
,
2
j
)
=
x
0
(
2
i
+
1
,
2
j
)
+
w
E
x
E
0
d
E
+
w
W
x
W
0
d
W
x
0
(
2
i
,
j
+
1
)
=
x
0
(
2
i
,
2
j
+
1
)
+
w
N
x
N
0
d
N
+
w
S
x
S
0
d
S
x
0
(
2
i
,
2
j
)
=
x
0
(
2
i
,
2
j
)
+
w
N
x
N
0
d
N
+
w
E
x
E
0
d
E
+
w
S
x
S
0
d
S
+
w
W
x
W
0
d
W
x
1
(
i
,
j
)
=
x
0
(
2
i
,
2
j
)
wherein the labels E, W, N, S indicate, respectively, the east/west/north/south neighbors of a point and their corresponding weights, and the factors d E , d W , d N , d S denote the corresponding degrees of the neighboring points.
10. The method of claim 1 , wherein a coarse level point is marked if any of its fine level neighbor points are marked.
11. 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×N grid wherein N is a positive integer;
defining a weight w ij between each pair of adjacent points indexed by i, j in the image based on the intensity difference of each said point pair;
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
points
,
0
otherwise
,
where d i =Σw ij for all weights incident on point i,
using a multigrid method and a computer to solve a potential for each point on said image, wherein a restriction operator for the image is applied to an (N−1)×(N−1) image wherein each said weight in the image is associated with an adjoining point to define a weight for applying said restriction operator, wherein said restriction operator determines weights of a coarse level grid.
12. The method of claim 11 , further comprising marking a subset of points in the image, wherein said potential is associated with each unmarked point and represents the probability that a random walker starting from each said unmarked point reaches a marked point.
13. A program storage device readable by a computer, tangibly embod ng a program of instructions executable by the computer to perform method steps for segmenting a digitized image, the method comprising the steps of:
providing a digitized image comprising a plurality of intensitie corresponding to a domain of points on an N×N 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 the image;
associating a probability potential with each unmarked point; and
using a multigrid method to solve for the probability potentials for each unmarked point, wherein a restriction operator for the image is applied to an (N−1)×(N−1) image wherein each said weight in the image is associated with an adjoining point to define a weight for applying said restriction operator, wherein said restriction operator determines weights of a coarse level grid.
14. The computer readable program storage device of claim 13 , wherein the probability potential for each unmarked point represents the probability that a random walker starting from each said unmarked point reaches a marked point.
15. The computer readable program storage device of claim 14 , wherein the probability that a random walker starting from an unmarked point reaches a marked point is calculated for each marked point.
16. The computer readable program storage device of claim 13 , wherein each said weight w ij between a point v i adjacent to point v j 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 13 , the method further comprising representing said image by a Laplacian matrix L indexed by point pairs, wherein an element L ij for point i and j is defined by
L
ij
=
{
d
i
-
w
ij
if
i
=
j
,
0
if
i
and
j
represent
adjacent
points
,
where 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 potential for each unmarked point i with respect to a marked point s by x i s , said unmarked probability potentials forming a vector x U , wherein the probability potentials for each unmarked point can be determined by solving L U x U =ƒ, wherein ƒ is a function.
18. The computer readable program storage device of claim 17 , wherein a point is assigned to a segment of a marked point according to max s (x i s ).
19. The computer readable program storage device of claim 13 , wherein said multigrid method comprises calculating an approximate solution to the probability potentials on a fine level grid, calculating a residual to the approximate 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 a prolongation operator, wherein said prolongation operator is an adjoint of said restriction operator.
20. The computer readable program storage device of claim 19 , wherein said prolongation operator from a point x 1 (i, j) on the coarse grid to a point on the fine grid x 0 is defined by the transformations
x
0
(
2
i
,
2
j
)
=
x
1
(
i
,
j
)
∀
i
,
j
x
0
(
2
i
+
1
,
2
j
)
=
w
E
x
E
0
+
w
W
x
W
0
w
E
+
w
W
x
0
(
2
i
+
1
,
2
j
+
1
)
=
w
N
x
N
0
+
w
E
x
E
0
+
w
S
x
S
0
+
w
W
x
W
0
w
N
+
w
E
+
w
S
+
w
W
,
wherein the labels E, W, N, S indicate, respectively, the east/west/north/south neighbors of a point and their corresponding weights.
21. The computer readable program storage device of claim 19 , wherein said restriction operator from a point on the fine grid x 0 to a point x 1 (i, j) on the coarse grid is defined by the transformations
x
0
(
2
i
+
1
,
2
j
)
=
x
0
(
2
i
+
1
,
2
j
)
+
w
E
x
E
0
d
E
+
w
W
x
W
0
d
W
x
0
(
2
i
,
2
j
+
1
)
=
x
0
(
2
i
,
2
j
+
1
)
+
w
N
x
N
0
d
N
+
w
S
x
S
0
d
S
x
0
(
2
i
,
2
j
)
=
x
0
(
2
i
,
2
j
)
+
w
N
x
N
0
d
N
+
w
E
x
E
0
d
E
+
w
S
x
S
0
d
S
+
w
W
x
W
0
d
W
x
1
(
i
,
j
)
=
x
0
(
2
i
,
2
j
)
wherein the labels E, W, N, S indicate, respectively, the east/west/north/south neighbors of a point and their corresponding weights, and the factors d E , d W , d N , d S denote the corresponding degrees of the neighboring points.
22. The computer readable program storage device of claim 13 , wherein a coarse level point is marked if any of its fine level neighbor points are marked.