Motion estimation
View Patent ↗A technique of motion estimation in video compression is described, the technique including: determining, in one or more reference frames of a video picture, the best full-pixel motion vector F for a block in a current frame of the video picture, wherein m and n are signed numbers and integer multiples of the distance between two adjacent full-pixels; selecting the best half-pixel motion vector candidates from a set of half-pixel motion vectors based on the best full-pixel motion vector; determining the best half-pixel motion vector H; selecting the best quarter-pixel motion vector candidates from a set of quarter-pixel motion vectors based on the best full-pixel motion vector and the best half-pixel motion vector; determining the best quarter-pixel motion vector Q; and determining the best motion vector for the block as BMV.
1. A method of efficiently reducing complexity of sub pixel motion estimation in video compression for limiting degradation, comprising:
determining, in one or more reference frames of a video picture, a best full-pixel motion vector F=(m, n) for a block in a current frame of the video picture, wherein m and n are signed numbers and integer multiples of the distance between two adjacent full-pixels;
selecting the best half-pixel motion vector candidates from a set of half-pixel motion vectors based on the best full-pixel motion vector;
determining the best half-pixel motion vector H;
selecting the best quarter-pixel motion vector candidates from a set of quarter-pixel motion vectors based on the best full-pixel motion vector and the best half-pixel motion vector;
determining the best quarter-pixel motion vector Q;
determining the best motion vector for the block as BMV=F+H+Q; and
determining full-pixel motion estimation based on the best motion vector.
2. The method of claim 1 , wherein the set of half-pixel motion vectors is S1={H1=(2u, 2u), H2=(0, 2u), H3=(−2u, 2u), H4=(2u, 0), H5=(−2u, 0), H6=(2u, −2u), H7=(0, −2u), H8=(−2u, −2u)}; wherein the set of quarter-pixel motion vectors is S2={Q1=(u, u), Q2=(0, u), Q3=(−u, u), Q4=(u, 0), Q5=(−u, 0), Q6=(u, −u), Q7=(0, −u), Q8=(−u, −u)}; and
wherein u is a real number greater than zero, and 4u is the distance between two adjacent full-pixels.
3. The method of claim 2 , wherein selecting the best half-pixel motion vector candidates comprising:
if the best full-pixel motion vector is a zero vector, selecting all of S1 as the best half-pixel motion vector candidates.
4. The method of claim 2 , wherein selecting the best half-pixel motion vector candidates comprising:
if the best full-pixel motion vector is a non-zero vector and m*n=0, selecting the half-pixel motion vectors in a same and opposite directions of the best full-pixel motion vector as the best half-pixel motion vector candidates.
5. The method of claim 2 , wherein selecting the best half-pixel motion vector candidates comprising:
if the best full-pixel motion vector is a non-zero vector and m*n≠0, selecting the half-pixel motion vectors in a same trend direction of the best full-pixel motion vector and the half-pixel motion vector in an opposite trend direction of the best full-pixel motion vector as the best half-pixel motion vector candidates;
wherein the half-pixel motion vectors in the same trend direction of the best full-pixel motion vector are
(
m
m
2
u
,
n
n
2
u
)
,
(
m
m
2
u
,
0
)
,
and
(
0
,
n
n
2
u
)
and the half-pixel motion vector in the opposite trend direction of the best full-pixel motion vector is
(
-
m
m
2
u
,
-
n
n
2
u
)
,
and wherein each of the best half-pixel motion vector candidates belongs to S1.
6. The method of claim 1 , wherein determining the best half-pixel motion vector comprising:
determining the one of the best half-pixel motion vector candidates, whose corresponding block best matches the block in the current frame, as the best half-pixel motion vector.
7. The method of claim 2 , wherein selecting the best quarter-pixel motion vector candidates comprising:
determining which of the block corresponding to the best full-pixel motion vector and the block corresponding to the best half-pixel motion vector better matches the block in the current frame.
8. The method of claim 7 , wherein selecting the best quarter-pixel motion vector candidates comprising:
if the block corresponding to the best full-pixel motion vector better matches the block in the current frame and the best full-pixel motion vector is a zero vector, selecting the quarter-pixel motion vector in the opposite direction of the best half-pixel motion vector as the best quarter-pixel motion vector candidate.
9. The method of claim 7 , wherein selecting the best quarter-pixel motion vector candidates comprising:
if the block corresponding to the best full-pixel motion vector better matches the block in the current frame and the best full-pixel motion vector is a non-zero vector, selecting all of S2 as the best quarter-pixel motion vector candidates.
10. The method of claim 7 , wherein selecting the best quarter-pixel motion vector candidates comprising:
if the block corresponding to the best half-pixel motion vector better matches the block in the current frame, selecting the quarter-pixel motion vectors in the same trend direction of the best half-pixel motion vector, each of which is at an angle less than 90 degrees with the best half-pixel motion vector, as the best quarter-pixel motion vector candidates, wherein each of the best quarter-pixel motion vector candidates belongs to S2.
11. The method of claim 1 , wherein, determining the best quarter-pixel motion vector comprising:
determining the one of the best quarter-pixel motion vector candidates, whose corresponding block best matches the block in the current frame, as the best quarter-pixel motion vector.
12. A system of efficiently reducing complexity of sub pixel motion estimation for limiting degradation, comprising:
a first determination module adapted for determining, in one or more reference frames of the video picture, a best full-pixel motion vector F=(m, n) for a block in a current frame of a video picture, wherein m and n are signed numbers and integer multiples of the distance between two adjacent full-pixels;
a first selection module adapted for selecting the best half-pixel motion vector candidates from a set of half-pixel motion vectors based on the best full-pixel motion vector;
a second determination module adapted for determining the best half-pixel motion vector H;
a second selection module adapted for selecting the best quarter-pixel motion vector candidates from a set of quarter-pixel motion vectors based on the best full-pixel motion vector and the best half-pixel motion vector;
a third determination module adapted for determining the best quarter-pixel motion vector Q;
a fourth determination module adapted for determining the best motion vector for the block as BMV=F+H+Q; and
a fifth usage module adapted for determining full-pixel motion estimation based on the best motion vector.
13. The motion estimation system of claim 12 , wherein the set of half-pixel motion vectors is S1={H1=(2u, 2u), H2=(0, 2u), H3=(−2u, 2u), H4=(2u, 0), H5=(−2u, 0), H6=(2u, −2u), H7=(0, −2u), H8=(−2u, −2u)}; wherein the set of quarter-pixel motion vectors is S2={Q1=(u, u), Q2=(0, u), Q3=(−u, u), Q4=(u, 0), Q5=(−u, 0), Q6=(u, −u), Q7=(0, −u), Q8=(−u, −u)}; and
wherein u is a real number greater than zero, and 4u is the distance between two adjacent full-pixels.
14. The motion estimation system of claim 13 , wherein the first selection module selects the best half-pixel motion vector candidates by:
if the best full-pixel motion vector is a zero vector, selecting all of S1 as the best half-pixel motion vector candidates.
15. The motion estimation system of claim 13 , wherein the first selection module selects the best half-pixel motion vector candidates by:
if the best full-pixel motion vector is a non-zero vector and m*n=0, selecting the half-pixel motion vectors in a same and opposite directions of the best full-pixel motion vector as the best half-pixel motion vector candidates.
16. The motion estimation system of claim 13 , wherein the first selection module selects the best half-pixel motion vector candidates by:
if the best full-pixel motion vector is a non-zero vector and m*n≠0, selecting the half-pixel motion vectors in a same trend direction of the best full-pixel motion vector and the half-pixel motion vector in an opposite trend direction of the best full-pixel motion vector as the best half-pixel motion vector candidates;
wherein the half-pixel motion vectors in the same trend direction of the best full-pixel motion vector are
m
m
2
u
,
n
n
2
v
(
m
m
2
u
,
n
n
2
u
)
,
(
m
m
2
u
,
0
)
m
m
2
u
·
0
,
and
0
·
n
n
2
v
(
0
,
n
n
2
u
)
and the half-pixel motion vector in the opposite trend direction of the best full-pixel motion vector is
(
-
m
m
2
u
,
-
n
n
2
u
)
,
and wherein each of the best half-pixel motion vector candidates belongs to S1.
17. The motion estimation system of claim 12 , wherein the second determination module determines the best half-pixel motion vector by:
determining the one of the best half-pixel motion vector candidates, whose corresponding block best matches the block in the current frame, as the best half-pixel motion vector.
18. The motion estimation system of claim 12 , wherein the second determination module determines the best half-pixel motion vector by:
determining the one of the best half-pixel motion vector candidates, whose corresponding block best matches the block in the current frame, as the best half-pixel motion vector.
19. The motion estimation system of claim 18 , wherein the second selection module selects the best quarter-pixel motion vector candidates by:
if the block corresponding to the best full-pixel motion vector better matches the block in the current frame and the best full-pixel motion vector is a zero vector, selecting the quarter-pixel motion vector in the opposite direction of the best half-pixel motion vector as the best quarter-pixel motion vector candidate.
20. The motion estimation system of claim 18 , wherein the second selection module selects the best quarter-pixel motion vector candidates by:
if the block corresponding to the best full-pixel motion vector better matches the block in the current frame and the best full-pixel motion vector is a non-zero vector, selecting all of S2 as the best quarter-pixel motion vector candidates.
21. The motion estimation system of claim 18 , wherein the second selection module selects the best quarter-pixel motion vector candidates comprising:
if the block corresponding to the best half-pixel motion vector better matches the block in the current frame, selecting the quarter-pixel motion vectors in the same trend direction of the best half-pixel motion vector, each of which is at an angle less than 90 degrees with the best half-pixel motion vector, as the best quarter-pixel motion vector candidates, wherein each of the best quarter-pixel motion vector candidates belongs to S2.
22. The motion estimation system of claim 12 , wherein, the third determination module determines the best quarter-pixel motion vector by:
determining the one of the best quarter-pixel motion vector candidates, whose corresponding block best matches the block in the current frame, as the best quarter-pixel motion vector.
23. One or more non-transitory computer-readable media for efficiently reducing complexity of sub pixel motion estimation having computer-executable instructions embodied thereon that, when executed by at least one processor, cause at least one processor to:
determine, in one or more reference frames of a video picture, a best full-pixel motion vector F=(m, n) for a block in a current frame of the video picture, wherein m and n are signed numbers and integer multiples of the distance between two adjacent full-pixels;
select the best half-pixel motion vector candidates from a set of half-pixel motion vectors based on the best full-pixel motion vector;
determine the best half-pixel motion vector H;
select the best quarter-pixel motion vector candidates from a set of quarter-pixel motion vectors based on the best full-pixel motion vector and the best half-pixel motion vector;
determine the best quarter-pixel motion vector Q;
determining the best motion vector for the block as BMV=F+H+Q; and
determining full-pixel motion estimation based on the best motion vector.
24. The one or more computer readable media of claim 23 , wherein the set of half-pixel motion vectors is S1={H1=(2u, 2u), H2=(0, 2u), H3=(−2u, 2u), H4=(2u, 0), H5=(−2u, 0), H6=(2u, −2u), H7=(0, −2u), H8=(−2u, −2u)}; wherein the set of quarter-pixel motion vectors is S2={Q1=(u, u), Q2=(0, u), Q3=(−u, u), Q4=(u, 0), Q5=(−u, 0), Q6=(u, −u), Q7=(0, −u), Q8=(−u, −u)}; and
wherein u is a real number greater than zero, and 4u is the distance between two adjacent full-pixels.
25. The one or more computer readable media of claim 24 , wherein execution of the instructions causes the processor to select the best half-pixel motion vector candidates by:
if the best full-pixel motion vector is a zero vector, selecting all of S1 as the best half-pixel motion vector candidates.
26. The one or more computer readable media of claim 24 , wherein execution of the instructions causes the processor to select the best half-pixel motion vector candidates by:
if the best full-pixel motion vector is a non-zero vector and m*n=0, selecting the half-pixel motion vectors in a same and opposite directions of the best full-pixel motion vector as the best half-pixel motion vector candidates.
27. The one or more computer readable media of claim 24 , wherein execution of the instructions causes the processor to select the best half-pixel motion vector candidates by:
if the best full-pixel motion vector is a non-zero vector and m*n≠0, selecting the half-pixel motion vectors in a same trend direction of the best full-pixel motion vector and the half-pixel motion vector in an opposite trend direction of the best full-pixel motion vector as the best half-pixel motion vector candidates;
wherein the half-pixel motion vectors in the same trend direction of the best full-pixel motion vector are
m
m
2
u
,
n
n
2
v
(
m
m
2
u
,
n
n
2
u
)
,
(
m
m
2
u
,
0
)
m
m
2
u
·
0
,
and
0
·
n
n
2
v
(
0
,
n
n
2
u
)
and the half-pixel motion vector in the opposite trend direction of the best full-pixel motion vector is
(
-
m
m
2
u
,
-
n
n
2
u
)
,
and wherein each of the best half-pixel motion vector candidates belongs to S1.
28. The one or more computer readable media of claim 23 , wherein execution of the instructions causes the processor to determine the best half-pixel motion vector by: determining the one of the best half-pixel motion vector candidates, whose corresponding block best matches the block in the current frame, as the best half-pixel motion vector.
29. The one or more computer readable media of claim 24 , wherein execution of the instructions causes the processor to select the best quarter-pixel motion vector candidates by:
determining which of the block corresponding to the best full-pixel motion vector and the block corresponding to the best half-pixel motion vector better matches the block in the current frame.
30. The one or more computer readable media of claim 29 , wherein execution of the instructions causes the processor to select the best quarter-pixel motion vector candidates by:
if the block corresponding to the best full-pixel motion vector better matches the block in the current frame and the best full-pixel motion vector is a zero vector, selecting the quarter-pixel motion vector in the opposite direction of the best half-pixel motion vector as the best quarter-pixel motion vector candidate.
31. The one or more computer readable media of claim 29 , wherein execution of the instructions causes the processor to select the best quarter-pixel motion vector candidates by:
if the block corresponding to the best full-pixel motion vector better matches the block in the current frame and the best full-pixel motion vector is a non-zero vector, selecting all of S2 as the best quarter-pixel motion vector candidates.
32. The one or more computer readable media of claim 29 , wherein execution of the instructions causes the processor to select the best quarter-pixel motion vector candidates by:
if the block corresponding to the best half-pixel motion vector better matches the block in the current frame, selecting the quarter-pixel motion vectors in the same trend direction of the best half-pixel motion vector, each of which is at an angle less than 90 degrees with the best half-pixel motion vector, as the best quarter-pixel motion vector candidates, wherein each of the best quarter-pixel motion vector candidates belongs to S2.
33. The one or more computer readable media of claim 23 , wherein, execution of the instructions causes the processor to determine the best quarter-pixel motion vector by:
determining the one of the best quarter-pixel motion vector candidates, whose corresponding block best matches the block in the current frame, as the best quarter-pixel motion vector.