US8249369B2ActiveUtilityPatentIndex 51
Method and apparatus of tile-based belief propagation
Est. expiryDec 2, 2028(~2.4 yrs left)· nominal 20-yr term from priority
G06V 10/457
51
PatentIndex Score
2
Cited by
9
References
21
Claims
Abstract
A method and apparatus of tile-based belief propagation are disclosed. An image is split into a number of tiles. Messages are iteratively generated within each of the tiles based on the messages from neighboring pixels to the tile at a previous iteration, wherein each message represents information of a state of the pixel. The generated messages for sending out of the tiles are stored. Labels are then determined based on the stored messages, wherein each label represents the state of the pixel.
Claims
exact text as granted — not AI-modified1. A method of tile-based belief propagation, comprising:
splitting an image into a plurality of tiles each including a plurality of pixels;
iteratively generating messages within each of the tiles based on messages from neighboring pixels to the tile at a previous iteration, wherein each message represents information of a state of the pixel;
storing generated messages for sending out of the tiles; and
determining labels based on the stored messages, wherein each label represents the state of the pixel;
wherein the messages are generated further based on a data energy term E d and a smoothness energy term E s in energy minimization on a Markov Random Field (MRF); and
wherein the step of iteratively generating messages within each of the tiles is performed according to a brief propagation (BP) equation:
M
pq
t
(
l
p
)
=
min
l
′
∈
L
{
E
s
(
l
q
,
l
′
)
+
E
d
(
l
′
)
+
∑
(
p
,
p
′
)
∈
N
p
\
q
M
p
′
p
t
-
1
(
l
′
)
}
in which N p is a set of neighbors of a pixel p,
M pq t is the generated message at iteration t, and
M p′p t−1 is the message at the previous iteration t−1.
2. The method. of claim 1 , further comprising a step of generating a. label map according to the determined labels.
3. The method of claim 1 , wherein the iterative steps of generating messages within each of the tiles are performed in a raster scan order.
4. The method. of claim. 3 , further performing the iterative steps of generating messages within each of the tiles in an inverse-raster scan order.
5. The method of claim 1 , wherein the iterative steps of generating messages within each of the tiles are performed on a portion of the image.
6. The method. of claim. 1 , wherein the labels are determined further based on a data energy term E d in energy minimization on a Markov Random Field (MRF).
7. The method of claim 6 , wherein the step of determining labels is performed according to an equation:
l
p
=
arg
min
l
∈
L
{
E
d
(
l
)
+
∑
(
p
,
p
′
)
∈
N
(
p
)
M
p
′
p
T
(
l
)
}
where L is a set of all labels l, and
M p′p T is the message after a specified number of iterations T.
8. The method. of claim 1 , wherein, the iterative generating of messages is performed on at least a first level and a second level, wherein each node in the first level corresponds to a block of a plurality of nodes in the second level, wherein each of the nodes includes one or more pixels.
9. The method of claim 8 , wherein the iterative generating of messages is performed on the first level, followed by being performed on the second level.
10. The method of claim 9 , wherein each message between or among adjacent nodes on the first level is duplicated into a plurality of messages for the adjacent pairs of nodes on the second level.
11. An apparatus of tile-based belief propagation, comprising:
means for splitting an image into a plurality of tiles each including a plurality of pixels;
a message computing device for iteratively generating messages within. each of the tiles based on messages from neighboring pixels to the tile at a previous iteration, wherein each message represents information of a state of the pixel;
a memory for storing generated messages for sending out of the tiles; and
a belief decision device for determining labels based on the stored messages, wherein each label represents the state of the pixel;
wherein the messages are generated in the message computing device further based on a data energy term E d and a smoothness energy term E s in energy minimization on a Markov Random Field (MRF); and
wherein the messages are generated in the message computing device according to a brief propagation (BP) equation:
M
pq
t
(
l
p
)
=
min
l
′
∈
L
{
E
s
(
l
q
,
l
′
)
+
E
d
(
l
′
)
+
∑
(
p
,
p
′
)
∈
N
p
\
q
M
p
′
p
t
-
1
(
l
′
)
}
with N p being a set of neighbors of a pixel p,
M pq t being the generated message at iteration t, and
M p′p t−1 , the message at the previous iteration t−1.
12. The apparatus of claim 11 , further comprising an output device for generating a label map according to the determined labels.
13. The apparatus of claim 11 , wherein the messages are generated in the message computing device in a raster scan order.
14. The apparatus of claim 13 , wherein the messages are generated in the message computing device further in an inverse-raster scan order.
15. The apparatus of claim 11 , wherein the message computing device is a parallel processor.
16. The apparatus of claim 11 , wherein the labels are determined in the belief decision device further based on a data energy term E d in energy minimization on a Markov Random Field (MRF).
17. The apparatus of claim 16 , wherein the labels are determined in the belief decision device according to an equation:
l
p
=
arg
min
l
∈
L
{
E
d
(
l
)
+
∑
(
p
,
p
′
)
∈
N
(
p
)
M
p
′
p
T
(
l
)
}
where L is a set of all labels l, and
M p′p T is the message after a specified number of iterations T.
18. The apparatus of claim 11 , wherein the generating of messages is performed on at least a first level and a second level, wherein each node in the first level corresponds to a block of a plurality of nodes in the second level, wherein each of the nodes includes one or more pixels.
19. The apparatus of claim 18 , wherein the generating of messages is performed on the first level, followed by being performed on the second level.
20. The apparatus of claim 19 , wherein each message between or among adjacent nodes on the first level is duplicated into a plurality of messages for the adjacent pairs of nodes on the second level.
21. A method of tile-based belief propagation, comprising:
splitting an image into a plurality of tiles each including a plurality of pixels;
iteratively generating messages within each of the tiles based on messages from neighboring pixels to the tile at a previous iteration, wherein each message represents information of a state of the pixel;
storing generated messages for sending out of the tiles; and
determining labels based on the stored messages, wherein each label represents the state of the pixel;
wherein the labels are determined further based on a data energy term E d in energy minimization on a Markov Random Field (MRF); and
wherein the step of determining labels is performed according to an equation:
l
p
=
arg
min
l
∈
L
{
E
d
(
l
)
+
∑
(
p
,
p
′
)
∈
N
(
p
)
M
p
′
p
T
(
l
)
}
where L is a set of all labels l, and
M p′p T is the message after a specified number of iterations T.Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.