Method of estimating backward motion vectors within a video sequence
View Patent ↗A method of speeding the computation of backward motion vector estimates which are derived from fields which are available from forward motion vector estimates as based on nearest neighbor criterion. The method allows for the generation of multi-frame backwards motion vectors. The invention of the present method for estimating backward motion vectors is particularly well-suited for use with the MPEG-2 video standard.
1. A method of estimating multi-frame backward motion vectors in a sequence of video frames, comprising:
for any frame, deriving a backward motion vector from a nearest neighbor forward motion vector; and
linking said backward motion vector to multiple frame backward motion vectors within a video sequence;
wherein said linking comprises iterative linking to find the backward motion vectors b imn of the i-th macroblock of the m-th frame to the n-th frame by linking the motion vectors in between successive frames;
wherein b im represents the backward motion vector of the i-th macroblock of the m-th frame to the (m+1)-th frame; and
wherein b imn represents the backward motion vector of the i-th macroblock of the m-th frame to the n-th frame.
2. A method as recited in claim 1 , wherein said step of deriving said backward motion vector comprises:
identifying an area of the previous frame that when moved in a backward direction results in a given macroblock; and
assigning the backward motion vector of said area to the macroblock nearest to said area.
3. A method as recited in claim 2 , further comprising:
detecting the macroblocks associated with any backward motion vectors that could not be generated from forward motion vectors and generating them conventionally.
4. A method as recited in claim 1 , wherein said step of detecting the macroblocks associated with any backward motion vectors that could not be generated from forward motion vectors, comprises:
assigning a predetermined illegal backward motion vector to every macroblock in the current frame prior to determining backward motion vectors, wherein unassigned macroblocks retain the illegal backward motion vector and can be detected.
5. A method as recited in claim 1 , wherein said linking comprises:
initializing the iterative process;
designating the backward motion vector b im as b im(m+1) ;
assigning an invalid backward motion vector to b imn if b im is not invalid and terminating the linking process;
initializing k as k=(m+1);
continuing the iterative process until a valid backward motion vector b imk =(u imk ,v imk ) is found;
constructing a backward motion vector b im(k+1) from b imk , when a valid b imk is found, by using the backward motion vector b jk of the j-th macroblock of k-th frames where the j-th macroblock is located at (x jk ,y jk ) and y jk =16*((y im +v imk +8)/16), x jk =16*((x im +u imk +8)/16);
assigning an invalid backward motion vector to b imn if b jk is an invalid backward motion vector and terminating the linking process;
assigning backward motion vector b im(k+1) =b imk +b jk , if b jk is a valid backward motion vector; and
increasing the value of k and repeating the iterative process above until backward motion vector b imn is assigned;
wherein b im =b im(m+1) ; and wherein the i-th macroblock of the m-th frame is located at (x im ,y im ).
6. A method as recited in claim 1 , further comprising:
improving a valid backward motion vector b imn by replacing it with the backward motion vector which minimizes the sum of absolute differences (SAD).
7. A method as recited in claim 6 , further comprising:
minimizing the sum of absolute differences (SAD) within a +/−2 horizontal times +/−1 pels from b imn .
8. A method of estimating backward motion vectors from available forward motion vector fields between successive frames, comprising:
(a) identifying an area of a previous frame that when moved in a backward direction results in a given macroblock; and
(b) assigning a backward motion vector of said area to the macroblock nearest to said area;
(c) linking the backward motion vector to multiple frame distanced backward motion vectors:
wherein said linking comprises iterative linking to find the backward motion vectors b imn of the i-th macroblock of the m-th frame to the n-th frame by linking the motion vectors in between successive frames;
wherein b im represents the backward motion vector of the i-th macroblock of the m-th frame to the (m+1)-th frame; and
wherein b imn represents the backward motion vector of the i-th macroblock of the m-th frame to the n-th frame.
9. A method as recited in claim 8 , further comprising:
repeating steps (a) and (c) for each macroblock in the next frame to estimate backward motion vectors for a frame.
10. A method as recited in claim 9 , further comprising:
detecting the macroblocks associated with any backward motion vectors that could not be generated from forward motion vectors and generating them conventionally.
11. A method as recited in claim 10 , wherein said step of detecting the macroblocks associated with any backward motion vectors that could not be generated from forward motion vectors, comprises:
assigning a predetermined illegal backward motion vector to every macroblock in the current frame prior to determining backward motion vectors, wherein unassigned macroblocks retain the illegal backward motion vector and can be detected.
12. A method as recited in claim 8 , wherein said backward motion vector estimation is configured for being performed orthogonal to conventional computation speed enhancement methods.
13. A method as recited in claim 8 , wherein said backward motion vector estimation is performed for MPEG-2 encoding and decoding operations.
14. A method as recited in claim 8 , wherein said linking comprises:
initializing the iterative process;
designating the backward motion vector b im as b im(m+1) ;
assigning an invalid backward motion vector to b imn if b im is not invalid and terminating the linking process;
initializing k as k=(m+1);
continuing the above iterative process until a valid backward motion vector b imk =(u imk ,v imk ) is found;
constructing a backward motion vector b im(k+1) from b imk , when a valid b imk is found, by using the backward motion vector b jk of the j-th macroblock of k-th frame, where the j-th macroblock is located at (x jk ,y jk ) and y jk =16*((y im +v imk +8)/16, x jk =16*((x im +u imk +8)/16);
assigning an invalid backward motion vector to b imn if b jk is an invalid backward motion vector and terminating the linking process;
assigning backward motion vector b im(k+1) =b imk +b jk , if b jk is a valid backward motion vector; and
increasing the value of k and repeating the iterative process above until backward motion vector b imn is assigned;
wherein b im =b im(m+1) ; and
wherein the i-th macroblock of the m-th frame is located at (x im ,y im ).
15. A method of estimating backward motion vectors from forward motion vector fields between successive frames, comprising:
(a) for any frame, selecting a previously unselected macroblock at a location (x,y) in the next frame and obtaining a forward motion vector (u,v);
(b) selecting a macroblock in the current frame nearest to (x+u,y+v);
(c) assigning a backward motion vector for the macroblock nearest to (x+u, y+v) as the vector (−u,−v); and
(d) linking the backward motion vector to multiple frame backward motion vectors;
wherein said linking comprises iterative linking to find the backward motion vectors b imn of the i-th macroblock of the m-th frame to the n-th frame by linking the motion vectors in between successive frames;
wherein b im represents the backward motion vector of the i-th macroblock of the m-th frame to the (m+1)-th frame; and
wherein b imn represents the backward motion vector of the i-th macroblock of the m-th frame to the n-th frame.
16. A method as recited in claim 15 , further comprising repeating steps (a) through (d) for each macroblock in the next frame.
17. A method as recited in claim 15 , further comprising:
detecting the macroblocks associated with any backward motion vectors that could not be generated from forward motion vectors and generating them conventionally.
18. A method as recited in claim 17 , wherein said step of detecting the macroblocks associated with any backward motion vectors that could not be generated from forward motion vectors, comprises:
assigning a predetermined illegal backward motion vector to every macroblock in the current frame prior to determining backward motion vectors, wherein unassigned macroblocks retain the illegal backward motion vector.
19. A method as recited in claim 15 , wherein said backward motion vector estimation is configured for being performed orthogonal to conventional computation speed enhancement methods.
20. A method as recited in claim 15 , wherein said backward motion vector estimation is performed for MPEG-2 encoding and decoding operations.
21. A method as recited in claim 19 , wherein said linking comprises:
initializing an iterative process;
designating the backward motion vector b im as b im(m+1) ;
assigning an invalid backward motion vector to b imn if b im is not invalid and terminating the linking process;
initializing k as k=(m+1);
continuing the iterative process until a valid backward motion vector b imk =(u imk ,v imk ) is found;
constructing a backward motion vector b im(k+1) from b imk , when a valid b imk is found, by using the backward motion vector b jk of the j-th macroblock of k-th frame, where the j-th macroblock is located at (x jk ,y jk ) and y jk =16*((y im +v imk +8)/16), x jk =16*((x im +u imk +8)/16);
assigning an invalid backward motion vector to b imn if b jk is an invalid backward motion vector and terminating the linking process;
assigning backward motion vector b im(k+1) =b imk +b jk , if b jk is a valid backward motion vector; and
increasing the value of k and repeating the iterative process above until backward motion vector b imn is assigned;
wherein b im =b im(m+1) ;
wherein the i-th macroblock of the m-th frame is located at (x im ,y im ).
22. A method as recited in claim 15 , further comprising improving a valid motion vector b imn by replacing it with the motion vector which minimizes the sum of absolute differences (SAD).
23. A method as recited in claim 22 , further comprising minimizing the sum of absolute differences (SAD) within a +/−2 horizontal times +/−1 pels from b imn .
24. A method of estimating multi-frame backward motion vectors in a video sequence, comprising:
for any frame in a sequence of frames containing said frame and a previous frame, identifying an area of the previous frame that when moved in a backward direction results in a given macroblock;
assigning a backward motion vector of said area to the macroblock nearest to said area; and
linking said backward motion vector to multiple frame backward motion vectors;
wherein said linking comprises iterative linking to find the backward motion vectors b imn of the i-th macroblock of the m-th, frame to the n-th frame by linking the motion vectors in between successive frames;
wherein b im represents the backward motion vector of the i-th macroblock of the m-th frame to the (m+1)-th frame; and
wherein b imn represents the backward motion vector of the i-th macroblock of the m-th frame to the n-th frame.
25. A method as recited in claim 24 , wherein said backward motion vector estimation is performed for MPEG-2 encoding and decoding operations.
26. A method as recited in claim 24 , further comprising improving a valid backward motion vector b imn by replacing it with the motion vector which minimizes the sum of absolute differences (SAD).
27. A method as recited in claim 26 , further comprising minimizing the sum of absolute differences (SAD) within a +/−2 horizontal times +/−1 pels from b imn .
28. A method of estimating multi-frame backward motion vectors, comprising:
for any frame in a sequence of frames containing said frame and a previous frame, identifying an area of the previous frame that when moved in a backward direction results in a given macroblock; and
assigning a backward motion vector of said area to the macroblock nearest to the said area;
linking the backward motion vector to multiple frame backward motion vectors by iterative linking to find the backward motion vectors b imn of the i-th macroblock of the m-th frame to the n-th frame by linking the backward motion vectors in between successive frames;
wherein b im represents the backward motion vector of the i-th macroblock of the m-th frame to the (m+1)-th frame; and
wherein b imn represents the backward motion vector of the i-th macroblock of the m-th frame to the n-th frame.
29. A method of estimating multi-frame backwards motion vectors, comprising:
selecting an unselected macroblock at a location (x,y) in the next frame and obtaining an associated forward motion vector (u,v);
selecting a macroblock in the current frame nearest to (x+u,y+v); and
assigning a backward motion vector for the macroblock nearest to (x+u,y+v) as the vector (−u,−v);
linking the backward motion vector to multiple frame backward motion vectors by iterative linking to find the backward motion vectors b imn of the i-th macroblock of the m-th frame to the n-th frame by linking the backward motion vectors in between successive frames;
wherein b im represents the backward motion vector of the i-th macroblock of the m-th frame to the (m+1)-th frame; and
wherein b imn represents the backward motion vector of the i-th macroblock of the m-th frame to the n-th frame.
30. A method of estimating multi-frame backward motion vectors, comprising:
selecting an unselected macroblock at a location (x,y) in the next frame and obtaining its forward motion vector (u,v);
selecting a macroblock in the current frame nearest to (x+u,y+v); and
assigning a backward motion vector for the macroblock nearest to (x+u,y+v) as the vector (−u,−v);
linking the backward motion vector to multiple frame backward motion vectors by
initializing an iterative process;
designating the backward motion vector b im as b im(m+1) ;
assigning an invalid backward motion vector to b imn if b im is not invalid and terminating the linking process;
initializing k as k=(m+1)
continuing the iterative process until a valid backward motion vector b imk =(u imk ,v imk ) is found;
constructing a backward motion vector b im(k+1) from b imk , when a valid b imk is found, by using the backward motion vector b jk of the j-th macroblock of k-th frame, where the j-th macroblock is located at (x jk ,y jk ) and y jk =16*((y im +v imk +8)/16), x jk =16*((x im +u imk +8)/16);
assigning an invalid backward motion vector to b imn if b jk is an invalid backward motion vector and terminating the linking process;
assigning backward motion vector b im(k+1) =b imk +b jk , if b jk is a valid backward motion vector; and
increasing the value of k and repeating the iterative process above until backward motion vector b imn is assigned;
wherein b im represents the backward motion vector of the i-th macroblock of the m-th frame to the (m+1)-th frame;
wherein b imn represents the backward motion vector of the i-th macroblock of the m-th frame to the n-th frame;
wherein b im =b im(m+1) ;
wherein the i-th macroblock of the mm-th frame is located at (x im ,y im ).