Method for motion estimation
View Patent ↗A method for motion estimation. The method includes a) dividing a search area into sub-areas with different densities, b) deriving distortions of a currently selected macro-block and its neighbors determined by the density of the current sub-area, c) if one of the distortions of the neighbors is smallest, identifying the neighbor as the current macro-block, d) repeating steps b) and c) until the current macro-block has the smallest distortion, e) if the current macro-block having the smallest distortion is not located in the sub-area having the largest density, re-defining the search area according to the density of the current sub-area, and f) repeating steps a), b), c), d) and e) until the current macro-block having the smallest distortion is located in the sub-area having the largest density, identified as the reference macro-block.
1. A method for motion estimation to determine a motion vector from a macro-block to be encoded to a reference macro-block, comprising the steps of:
a) dividing a search area into sub-areas respectively having different densities;
b) deriving distortions respectively between the macro-block to be encoded and a currently selected macro-block, and the macro-block to be encoded and neighbors of the currently selected macro-block, wherein the neighbors are determined according to the density of the sub-area in which the currently selected macro-block is located;
c) if one of the distortions between the neighbors and the macro-block to be encoded is smallest, identifying the neighbor having the smallest distortion as the currently selected macro-block;
d) repeating steps b) and c) until the currently selected macro-block has the smallest distortion among the neighbors thereof;
e) if the currently selected macro-block having the smallest distortion is located in one of the sub-areas other than that having the largest density, re-defining the search area according to the density of the sub-area in which the currently selected macro-block is located;
f) repeating steps a), b), c), d) and e) until the currently selected macro-block having the smallest distortion is located in the sub-area having the largest density; and
g) identifying the currently selected macro-block having the smallest distortion and located in the sub-area having the largest density as the reference macro-block.
2. The method as claimed in claim 1 , wherein the encoded and reference macro-blocks reside in different frames.
3. The method as claimed in claim 1 , wherein the distortion is a sum of absolute distortion or mean square error.
4. The method as claimed in claim 1 , wherein the search area is divided so that the sub-areas are ring-like and concentric at the center of the search area.
5. The method as claimed in claim 4 , wherein the sub-areas closer to the center of the search area have larger densities.
6. A method for motion estimation to determine a motion vector from a macro-block to be encoded to a reference macro-block, comprising the steps of:
a) dividing a search area into sub-areas respectively having different densities;
b) deriving distortions respectively between the macro-block to be encoded and a currently selected macro-block (X,Y), and the macro-block to be encoded and eight neighbors (X+D m ,Y−D m ), (X+D m ,Y), (X+D m , Y+D m ), (X, Y−D m ), (X, Y+D m ), (X−D m , Y−D m ), (X−D m ,Y), (X−D m ,Y+D m ) of the currently selected macro-block, wherein 1/D m is the density of the sub-area in which the currently selected macro-block (X,Y) is located;
c) if one of the distortions between the neighbors and the macro-block to be encoded is smallest, identifying the neighbor having the smallest distortion as the currently selected macro-block;
d) repeating the steps b) and c) until the currently selected macro-block has the smallest distortion among the neighbors thereof;
e) if the currently selected macro-block having the smallest distortion is located in one of the sub-areas other than that having the largest density, re-defining the search area and dividing the re-defined search area into sub-areas respectively having densities 1/D 1 , . . . ,1/D p , wherein 1/D m ′ is the density of the sub-area in which the currently selected macro-block is located and D 1 + . . . +D p ≦D m ′≦D 1 + . . . +D (p+1) ;
f) repeating steps b), c), d) and e) until the currently selected macro-block having the smallest distortion is located in the sub-area having the largest density; and
g) identifying the currently selected macro-block having the smallest distortion and located in the sub-area having the largest density as the reference macro-block.
7. The method as claimed in claim 6 , wherein the encoded and reference macro-blocks reside in different frames.
8. The method as claimed in claim 6 , wherein the distortion is a sum of absolute distortion or mean square error.
9. The method as claimed in claim 6 , wherein the search area is divided so that the sub-areas are ring-like and concentric at the currently selected macro-block.
10. The method as claimed in claim 9 , wherein a sub-area having a density 1/D m (1≦m≦n) comprises macro-blocks (X,Y) conforming to the equations:
{
[
x
i
+
(
D
1
+
…
+
D
(
m
-
1
)
)
+
1
≤
X
≤
x
i
+
(
D
1
+
…
+
D
m
)
]
or
[
x
i
-
(
D
1
+
…
+
D
(
m
-
1
)
)
-
1
≥
X
≥
x
i
-
(
D
1
+
…
+
D
m
)
]
[
y
i
+
(
D
1
+
…
+
D
(
m
-
1
)
)
+
1
≤
Y
≤
y
i
+
(
D
1
+
…
+
D
m
)
]
or
[
y
i
-
(
D
1
+
…
+
D
(
m
-
1
)
)
-
1
≥
Y
≥
y
i
-
(
D
1
+
…
+
D
m
)
]
11. The method as claimed in claim 9 , wherein the sub-areas closer to the currently selected macro-block have the larger densities.
12. The method as claimed in claim 6 , wherein the search area is re-defined as an area comprising macro-blocks (X,Y) conforming to equations x c −D m ≦X≦x c +D m and y c −D m ≦Y≦y c +D m , if the currently selected macro-block is located at (x c ,y c ) and in a sub-area having a density 1/D m .