Motion estimation method and system for MPEG video streams
View Patent ↗The present invention discloses a motion estimation method for MPEG video sequences. The method makes use of a global motion estimation algorithm to determine a set of dominant motion components. A simultaneous Full Search Block Matching (FSBM) search is conducted utilizing each dominant component for every block in a current frame. The results of each FSBM search are then compared to determine the best motion vector.
1. A method for motion estimation comprising the steps of:
a) acquiring pixel data for a current frame and pixel data for a reference frame;
b) generating a plurality of dominant motion component offset vectors;
c) searching within a plurality of search windows, one search window associated with each dominant motion component offset vector, for a block in a current frame;
d) determining a best result from step c); and
e) repeating steps c) and d) for each block in said current frame.
2. The method according to claim 1 wherein step b) comprises the steps of:
i) sub-sampling said current frame to create a plurality of first sub-sampled blocks and sub-sampling said reference frame to create a plurality of second sub-sampled blocks;
ii) comparing each first sub-sampled block with each second sub-sampled block to determine a best match for each of said plurality of first sub-sampled blocks and storing said best match for each of said plurality of first sub-sampled blocks; and
iii) analyzing each best match for each of said plurality of first sub-sampled blocks to determine said plurality of dominant motion component offset vectors.
3. The method according to claim 1 , wherein said searching at step c) utilizes Full Search Block Matching (FSBM).
4. The method according to claim 1 , wherein step d) utilizes a block matching cost function.
5. The method according to claim 4 , wherein said block matching cost function comprises a measurement of an amount of distortion between said block in said current frame and a block in one of said plurality of search windows in said reference frame.
6. The method according to claim 4 , wherein said block matching cost function comprises a measurement of a penalty based on a candidate motion vector and the dominant motion component offset vector associated with a search window.
7. The method according to claim 2 , wherein said sub-sampling comprises sub-sampling by a first factor in a horizontal direction and a second factor in a vertical direction.
8. The method according to claim 7 , where said first factor and said second factor each have a value of eight.
9. The method according to claim 2 , wherein said sub-sampling creates a sub-sampled element having a first dimension in a horizontal direction and a second dimension in a vertical direction.
10. The method according to claim 9 , wherein said first dimension and said second dimension each have a value of two.
11. The method according to claim 2 , wherein step ii) utilizes a Sum of Absolute Differences (SAD) to determine said best match.
12. The method according to claim 11 , wherein said SAD is defined as:
SAD
=
∑
i
=
0
N
∑
j
=
0
M
a
(
i
,
j
)
-
b
(
i
,
j
)
.
13. The method according to claim 2 , wherein step iii) comprises entering said best match for each of said plurality of first sub-sampled blocks into a histogram.
14. The method according to claim 13 , further comprising the step of scaling said dominant motion component offset vectors by a first factor in a horizontal direction and by a second factor in a vertical direction.
15. The method according to claim 4 , wherein said block matching cost function comprises a sum of a distortion measurement and a penalty associated with selection of a particular motion vector.
16. The method according to claim 5 , wherein said measurement of said amount of distortion between said block in said current frame and said block in one of said plurality of search windows in said reference frame comprises a Sum of Absolute Differences (SAD).
17. The method according to claim 6 , wherein said measurement of said penalty comprises an estimate of a number of bits to encode prediction parameters for said block in said current frame.
18. The method according to claim 13 , wherein step iii) further comprises detecting peaks in said histogram to determine said dominant motion component offset vectors.
19. The method according to claim 1 , wherein said plurality of search windows are searched simultaneously.
20. A computer readable medium containing computer instructions, when executed by a computer to perform the method according to claim 1 .