System and method for image segmentation by solving an inhomogenous dirichlet problem
View Patent ↗A method of segmenting a digitized image includes marking a subset of pixels in an image, defining edge conductances between each pair of adjacent pixels in the image based on the intensity difference of each said pixel pair, associating a probability potential with each unmarked pixel, and using a multigrid method to solve for the probability potentials for each unmarked pixel, wherein a restriction operator from the image grid to a coarse grid is calculated from a conductance-weighted average of the conductances on the image grid, the coarse grid conductances are calculated from the image grid conductances using a Δ-Y conversion, and the multigrid prolongation operator is calculated using a conductance-weighted interpolation of the coarse grid conductances.
1. A method of segmenting a digitized image comprising the steps of:
providing a digitized image comprising a plurality of intensities corresponding to a domain of pixels on a grid;
marking a subset of pixels in the image;
defining edge conductances between each pair of adjacent pixels in the image based on the intensity difference of each said pixel pair;
associating a probability potential with each unmarked pixel; and
using a multigrid method and a computer to solve for the probability potentials for each unmarked pixel, wherein a restriction operator from the image grid to a coarse grid is calculated from a conductance-weighted average of the edge conductances on the image grid, coarse grid conductances are calculated from the edge conductances using a Δ-Y conversion, and a prolongation operator is calculated using a conductance-weighted interpolation of the coarse grid conductances.
2. The method of claim 1 , wherein the probability potential for each unmarked pixel represents the probability that a random walker starting from said pixel reaches a marked pixel.
3. The method of claim 2 , wherein the probability that a random walker starting from an unmarked pixel reaches a marked pixel is calculated for each marked pixel.
4. The method of claim 1 , wherein each said edge conductance w ij for an edge connecting a pixel v i to pixel v j is determined by
w ij =exp(−β( g i −g j ) 2 ),
where g i and g j are the intensities of pixels i and j, respectively, and β is a free parameter.
5. The method of claim 4 , further comprising representing said image by a Laplacian matrix L indexed by pixel pairs, wherein an element L ij for pixels i and j is defined by
L
ij
=
{
d
i
if
i
=
j
,
-
w
ij
if
i
and
j
represent
adjacent
nodes
,
0
otherwise
,
where d i =Σw ij for all edges incident on pixel i, decomposing L as
L
=
[
L
M
B
B
T
L
U
]
,
wherein L M is the Laplacian for the marked pixels, L U is the Laplacian for the unmarked pixels, and B comprises those elements of L that are left over, representing the probability potential for each pixel i with respect to a marked pixel s by x i s , representing each marked pixel j by a label function Q(j)=s where s is an integer in the range 0<s≦K where K is the number of marked pixels, defining a marked vector for each label s at each marked pixel j by
m
j
s
=
{
1
if
Q
(
j
)
=
s
,
0
if
Q
(
j
)
≠
s
,
wherein the probability potentials for each unmarked pixel can be determined by solving L U x s =−Bm s .
6. The method of claim 5 , wherein the probability potentials for each unmarked pixel can be determined by solving L U X=−BM, wherein X is a matrix whose columns are defined by each vector x s , and M is a matrix whose rows are given by each vector m s .
7. The method of claim 6 , wherein a pixel is assigned to a segment of a marked node with a maximum probability potential.
8. The method of claim 1 , wherein said grid is a 2-dimensional grid indexed by i and j, wherein said prolongation operator from a point x 1 (i, j) on the coarse grid to a point on a 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 node and their corresponding weights w E , w w , w N , w S .
9. The method of claim 1 , wherein said grid is a 2-dimensional grid indexed by i and j, wherein said restriction operator from a point on a 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 node and their corresponding weights, w E , w w , w N , w S , and the factors d E , d W , d N , d S denote corresponding degrees of the neighboring nodes.
10. The method of claim 1 , wherein the coarse grid conductance c AB between nodes A and B in the coarse grid is defined by selecting every other node from a fine grid is defined to be:
c
AB
=
p
1
p
2
α
+
p
3
p
4
β
+
(
c
6
+
p
1
c
4
α
+
p
3
c
9
β
)
(
c
7
+
c
4
p
2
α
+
c
9
p
4
β
)
c
4
+
c
6
+
c
7
+
c
9
-
c
4
2
α
-
c
9
2
β
where c 1 , . . . , c 12 are conductances between nodes A and B on a 3×3 grid subset of the fine grid,
p
1
=
c
1
c
3
c
1
+
c
3
,
p
2
=
c
2
c
5
c
2
+
c
5
,
p
3
=
c
8
c
11
c
8
+
c
11
,
p
4
=
c
12
c
10
c
12
+
c
10
,
and
α
=
p
1
+
c
4
+
p
2
,
β
=
p
3
+
c
9
+
p
4
.
11. A method of segmenting a digitized image comprising the steps of:
providing a digitized image comprising a plurality of intensities corresponding to a domain of pixels on a 2-dimensional grid;
defining edge conductances between each pair of adjacent pixels in the image based on the intensity difference of each said pixel pair;
using a multigrid method and a computer to solve for a probability potential for each pixel, wherein a restriction operator from a point on a fine grid x 0 to a point x 1 on a coarse grid is calculated from a conductance-weighted average of the edge conductances 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 i, j are grid indices, the labels E, W, N, S indicate, respectively, the east/west/north/south neighbors of a node and their corresponding weights, w E , w W , W N , w S and the factors d E , d w , d N , d S , denote corresponding degrees of the neighboring nodes;
wherein a prolongation operator from a point x I (i, j) on the coarse grid to a point on the fine grid x 0 is calculated from a conductance-weighted interpolation of coarse grid conductances 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 node and their corresponding weights W E , W W , W N , W S ;
and wherein a conductance c AB between nodes A and B in the coarse grid are calculated from the edge conductances using a Δ-Y conversion defined by selecting every other node from the fine grid according to the formula
c
AB
=
p
1
p
2
α
+
p
3
p
4
β
+
(
c
6
p
1
c
4
α
+
p
3
c
9
β
)
(
c
7
+
c
4
p
2
α
+
c
9
p
4
β
)
c
4
+
c
6
+
c
7
+
c
9
-
c
4
2
α
-
c
9
2
β
wherein c 1 , . . . , c 12 are the conductances between nodes A and B on a 3×3 grid subset of the fine grid,
p
1
=
c
1
c
3
c
1
+
c
3
,
p
2
=
c
2
c
5
c
2
+
c
5
,
p
3
=
c
8
c
11
c
8
+
c
11
,
p
4
=
c
12
c
10
c
12
+
c
10
,
and
α
=
p
1
+
c
4
+
p
2
,
β
=
p
3
+
c
9
+
p
4
.
12. The method of claim 11 , further comprising marking a subset of pixels in the image, wherein said probability potential is associated with each unmarked pixel, and wherein the probability potential for each unmarked pixel represents the probability that a random walker starting from said pixel reaches a marked pixel.
13. 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 pixels on a grid;
marking a subset of pixels in the image;
defining edge conductances between each pair of adjacent pixels in the image based on the intensity difference of each said pixel pair;
associating a probability potential with each unmarked pixel; and
using a multigrid method to solve for the probability potentials for each unmarked pixel, wherein a restriction operator from the image grid to a coarse grid is calculated from a conductance-weighted average of the edge conductances on the image grid, coarse grid conductances are calculated from the edge conductances using a Δ-Y conversion, and a prolongation operator is calculated using a conductance-weighted interpolation of the coarse grid conductances.
14. The computer readable program storage device of claim 13 , wherein the probability potential for each unmarked pixel represents the probability that a random walker starting from said pixel reaches a marked pixel.
15. The computer readable program storage device of claim 14 , wherein the probability that a random walker starting from an unmarked pixel reaches a marked pixel is calculated for each marked pixel.
16. The computer readable program storage device of claim 13 , wherein each said edge conductance w ij for an edge connecting a pixel v i to pixel v j is determined by
w ij =exp(−β( g i −g j ) 2 ),
where g i and g j are the intensities of pixels i and j, respectively, and β is a free parameter.
17. The computer readable program storage device of claim 15 , the method further comprising representing said image by a Laplacian matrix L indexed by pixel pairs, wherein an element L ij for pixels i and j is defined by
L
ij
=
{
d
i
if
i
=
j
,
-
w
ij
if
i
and
j
represent
adjacent
nodes
,
0
otherwise
,
where d i =Σw ij for all edges incident on pixel i, decomposing L as
L
=
[
L
M
B
B
T
L
U
]
,
wherein L M is the Laplacian for the marked pixels, L U is the Laplacian for the unmarked pixels, and B comprises those elements of L that are left over, representing the probability potential for each pixel i with respect to a marked pixel s by x i s , representing each marked pixel j by a label function Q(j)=s where s is an integer in the range 0<s≦K where K is the number of marked pixels, defining a marked vector for each label s at each marked pixel j by
m
j
s
=
{
1
if
Q
(
j
)
=
s
,
0
if
Q
(
j
)
≠
s
,
wherein the probability potentials for each unmarked pixel can be determined by solving L U x s =−Bm s .
18. The computer readable program storage device of claim 17 , wherein the probability potentials for each unmarked pixel can be determined by solving L U X=−BM, wherein X is a matrix whose columns are defined by each vector x s , and M is a matrix whose rows are given by each vector m s .
19. The computer readable program storage device of claim 18 , wherein a pixel is assigned to a segment of a marked node with a maximum probability potential.
20. The computer readable program storage device of claim 13 , wherein said grid is a 2-dimensional grid indexed by i and j, wherein said prolongation operator from a point x 1 (i, j) on the coarse grid to a point on a 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 node and their corresponding weights W E , W W , W N , W S .
21. The computer readable program storage device of claim 13 , wherein said grid is a 2-dimensional grid indexed by i and j, wherein said restriction operator from a point on a 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 node and their corresponding weights W E , W W , W N , W S , and the factors d E , d W , d N , d S denote corresponding degrees of the neighboring nodes.
22. The computer readable program storage device of claim 13 , wherein the coarse grid conductance c AB between nodes A and B in the coarse grid is defined by selecting every other node from a fine grid is defined to be:
c
AB
=
p
1
p
2
α
+
p
3
p
4
β
+
(
c
6
p
1
c
4
α
+
p
3
c
9
β
)
(
c
7
+
c
4
p
2
α
+
c
9
p
4
β
)
c
4
+
c
6
+
c
7
+
c
9
-
c
4
2
α
-
c
9
2
β
where c 1 , . . . , c 12 are the conductances between nodes A and B on a 3×3 grid subset of the fine grid,
p
1
=
c
1
c
3
c
1
+
c
3
,
p
2
=
c
2
c
5
c
2
+
c
5
,
p
3
=
c
8
c
11
c
8
+
c
11
,
p
4
=
c
12
c
10
c
12
+
c
10
,
and
α
=
p
1
+
c
4
+
p
2
,
β
=
p
3
+
c
9
+
p
4
.