System and method for image segmentation using continuous valued MRFs with normed pairwise distributions
View Patent ↗A method for segmenting a digital image includes initializing object and background seed nodes in an image, where the image is represented as a graph G=(V, E) whose nodes iεV correspond to image points and whose edges eεE connect adjacent points, where set M⊂V contains locations of nodes marked as seeds, set U⊂V contains locations of unmarked nodes, set O⊂M contains locations of object seed nodes, and set B⊂M contains locations of background seed nodes, assigning to each seed node a membership value such that ∀iεO,x i =1 and ∀iεB,x i =0, where each node iεV is associated with a membership x i ε[0,1], and finding a membership vector xε , whose i th entry is given by x i that minimizes E p ( x ) = ∑ eij ∈ E w ij x i - x j pij , where each edge e ij εE connecting nodes i and j in V is associated with a weight w ij and an exponent p ij , and ∀e ij εE,1≦p ij <∞, such that x i =1 if iεO and x i =0 if iεB.
1. A computer implemented method for segmenting a digital image, the method performed by the computer comprising the steps of:
initializing object and background seed nodes in an image, wherein the image is represented as a graph G=(V, E) whose nodes iεV correspond to image points and whose edges eεE connect adjacent points, wherein set M⊂V contains locations of nodes marked as seeds, set U⊂V contains locations of unmarked nodes, set O⊂M contains locations of object seed nodes, and set B⊂M contains locations of background seed nodes;
assigning to each seed node a membership value such that ∀iεO,x i =1 and ∀iεB,x i =0, wherein each node iεV is associated with a membership x i ε[0,1; and
finding a membership vector xε , whose i th entry is given by x i that minimizes
E
p
(
x
)
=
∑
eij
∈
E
w
ij
x
i
-
x
j
pij
,
wherein each edge e ij εE connecting nodes i and j in V is associated with a weight w ij and an exponent p ij , and ∀e ij εE,1≦p ij <∞ such that x i =1 if iεO and x i =0 if iεB
wherein E p (x) is an energy of a weighted graph formed by a function associated to nodes x, e ij εE are edges in a weighted graph between nodes i and j, w ij is a weight of an edge e ij , and x i and x j are the values of node i and node j, respectively; and
generating an image that contains a segmentation of the object according to the membership value.
2. The method of claim 1 , wherein the membership x i of an unmarked node iεU takes the value
x
i
=
arg
min
x
i
(
∑
j
∈
N
i
w
ij
x
i
-
x
j
pij
)
,
wherein N i is a set of all nodes j that share an edge e ij with node i.
3. The method of claim 1 , wherein said image comprises a plurality of intensities associated with an N-dimensional grid of points.
4. The method of claim 1 , wherein said image comprises a plurality of vectors associated with an N-dimensional grid of points.
5. The method of claim 1 , wherein said image comprises a plurality of intensities associated with collection of points.
6. The method of claim 1 , wherein
E
p
(
x
)
=
∑
eij
∈
E
w
ij
x
i
-
x
j
pij
is minimized using an iteratively reweighted least squares algorithm.
7. The method of claim 1 , wherein nodes i with potential x i >0.5 are assigned to the object, and the remaining to background.
8. 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 digital image, the method comprising the steps of:
initializing object and background seed nodes in an image, wherein the image is represented as a graph G=(V, E) whose nodes iεV correspond to image points and whose edges eεE connect adjacent points, wherein set M⊂V contains locations of nodes marked as seeds, set U⊂V contains locations of unmarked nodes, set O⊂M contains locations of object seed nodes, and set B⊂M contains locations of background seed nodes;
assigning to each seed node a membership value such that ∀iεO,x i =1 and ∀iεB,x i =O, wherein each node iεV is associated with a membership x i ε[0,1]; and
finding a membership vector xε , whose i th entry is given by x i that minimizes
E
p
(
x
)
=
∑
eij
∈
E
w
ij
x
i
-
x
j
pij
,
wherein each edge e ij εE connecting nodes i and j in V is associated with a weight w ij and an exponent p ij , and ∀e ij εE,1≦p ij <∞, such that x i =1 if iεO and x i =0 if iεB
wherein E(x) is an energy of a weighted graph formed by a function associated to nodes x, e ij εE are edges in a weighted graph between nodes i and j, w ij is a weight of an edge e ij , and x i and x j are the values of node i and node j, respectively; and
generating an image that contains a segmentation of the object according to the membership value.
9. The computer readable program storage device of claim 8 , wherein the membership x i of an unmarked node iεU takes the value
x
i
=
arg
min
x
i
(
∑
j
∈
N
i
w
ij
x
i
-
x
j
pij
)
,
wherein N i is a set of all nodes j that share an edge e ij with node i.
10. The computer readable program storage device of claim 8 , wherein said image comprises a plurality of intensities associated with an N-dimensional grid of points.
11. The computer readable program storage device of claim 8 , wherein said image comprises a plurality of vectors associated with an N-dimensional grid of points.
12. The computer readable program storage device of claim 8 , wherein said image comprises a plurality of intensities associated with collection of points.
13. The computer readable program storage device of claim 8 , wherein
E
p
(
x
)
=
∑
eij
∈
E
w
ij
x
i
-
x
j
pij
is minimized using an iteratively reweighted least squares algorithm.
14. The computer readable program storage device of claim 8 , wherein nodes i with potential x i >0.5 are assigned to the object, and the remaining to background.