Adaptive step-size motion estimation based on statistical sum of absolute differences

• US 6,014,181 A
• Filed: 10/13/1997
• Issued: 01/11/2000
• Est. Priority Date: 10/13/1997
• Status: Expired due to Term

• Current Assignee: Sharp Laboratories of America Incorporated (Hon Hai Precision Industry Co., Ltd.)
• Original Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.), Sharp Laboratories of America Incorporated (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Sun, Kai
• Primary Examiner(s): Le, Vu
• Application Number:
  US08/949,303
• Time in Patent Office: 820 Days
• Field of Search: 348/699-700, 348/416, 348/402, 348/407, 348/413, 348/397-398, 348/408, 348/420, 348/384, 348/390, 386/111, 386/109, 386/112, 386/33, 386/27, 382/236, 382/238-239, 382/240, 382/244, 382/250
• US Class Current: 348/699
• CPC Class Codes: G06T 7/223 using block-matching
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/56 Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search
• CPC Class Codes: H04N 19/57 Motion estimation characterised by a search window with variable size or shape

Abstract

A novel motion estimation algorithm, AMESSAD (adaptive motion estimation based on statistical sum of absolute difference) is provided. The algorithm adaptively determines motion search step size based on statistical distribution of SAD (sum of absolute difference). That is, search step sizes to estimate motion in one portion of a frame are calculated using SAD values from neighboring portions of the frame. The efficient search procedure improves the implementation of motion compensation and transform based hybrid video coders, such as the H.26P and MPEG-X standard video compression. Compared with fixed step-size motion estimation, the adaptive algorithm improves motion estimation and hence overall video encoding speed. In addition, improved visual quality can be achieved in many cases because the algorithm differentiates regions with motion activity and allocates more motion estimation resources to local areas or local frames with higher motion content.

Claims

1. In a digital video system compression format where a video sequence is represented in series of frames, including a previous frame followed by a current frame, all separated by a predetermined time interval, the frames being divided into a plurality of blocks with predetermined positions, with each block having a size to include a predetermined matrix of luma pixels, a method for efficiently estimating the change in position of an image represented by a matrix of luma pixel data in a series of blocks in the current frame, from corresponding block-sized matrices of luma pixel data in the previous frame, the method comprising the steps of:

a) selecting a first block in the current frame;

b) selecting a block-sized matrix of luma pixels in the previous frame as an initial candidate matrix corresponding to the first block in the current frame;

c) providing a short term average comparison of luma pixel data between frames, derived from previous block position change estimates;

d) calculating a search window size, centered about the candidate matrix, in response to the short term average comparison of luma pixel data provided in Step c);

e) where a minimum spacing between block-sized matrices in the search window is provided, comparing the luma pixel data from a plurality of block-sized matrices of luma pixels uniformly distributed inside the search window, to the luma pixel data of first block in the current frame to select a new candidate matrix having luma pixel data most similar to the luma pixel data of the first block in the current frame, whereby the size of the search window varies with the history of motion between frames;

f) reducing the spacing between the plurality of block-sized matrices located inside the search window after each iteration of Step e);

g) iterating the search as follows;

1) when the spacing between the plurality of block-sized matrices is greater than, or equal to the minimum spacing, then return to step e); and

2) when the spacing between the plurality of block-sized matrices is less than the minimum spacing, then continue; and

h) comparing luma pixel data of the final candidate matrix selected in the final iteration of Step e) to the luma pixel data of the first block in the current frame, to calculate a final comparison of luma pixel data, whereby the difference in block position between the final candidate matrix and the first block provides a vector describing motion between frames.

2. A method as in claim 1 including the further step, following Step h), of:

i) updating the short term average comparison of luma pixel data, with the final comparison of luma pixel data calculated in Step h), whereby the short term average is modified for provision in Step c) of the next position change estimate.

3. A method as in claim 2 including a further step, following Step i), of:

j) updating a long term average of search window sizes with the short term average comparison of luma pixel data updated in Step i);

c₁) a step following Step c), and proceeding Step d), of providing the long term average of search window sizes; and

in which Step d) includes calculating the search window size in response to the long term average of window search size, whereby the long term average is updated in Step j) for provision in Step c₁) of the next block position change estimate.

4. A method as in claim 3 including the further step, following Step j), of:

k) updating a long term average comparison of luma pixel data with the final comparison of luma pixel data calculated in Step h), whereby the long term average is updated with the position change estimate of the first block; and

in which Step j) includes updating the long term average search window size in response to the long term average of luma pixel data.

5. A method as in claim 4 in which Step e) includes comparing luma pixel data by the calculation of the sum of absolute differences (SAD) of luma pixel data between each of the plurality of block-sized matrices in the search window and the first block in the current frame, in which the block-sized matrix with the smallest SAD is selected as the candidate matrix in the next iteration of Steps e)-f), and in which Step h) includes a calculation of the block-sized matrix with the minimum SAD (SAD_-- min) as the final comparison of luma pixel data.

6. A method as in claim 5 including a further step, following Step b), and preceding Step c), of:

b₁) calculating the SAD between the initial candidate matrix selected in Step b) and the first block in the current frame, to derive SAD_-- init; and

in which Step d) includes calculating the search window size in response to SAD_-- init calculated in Step b₁).

7. A method as in claim 6 in which Step k) includes a long term average (SAD_-- aveLT) as the long term average comparison of luma pixel data, and in which Step k) includes updating SAD_-- aveLT with SAD_-- min calculated in Step h), whereby SAD_-- aveLT is updated with SAD values after the position change of the first block is estimated.

8. A method as in claim 7 in which Step d) includes defining the search window size in terms of the number of iterations (ME_-- step) of Steps e)-f) required until the spacing between block-sized matrices is the minimum spacing, and in which Step e) includes initially distributing the plurality of block-sized matrices compared in the search window in response to the value of ME_-- step.

9. A method as in claim 8 in which Step i) includes a short term average of SAD (SAD_-- ave) as the short term average comparison of luma pixel data, and in which Step i) includes updating SAD_-- ave with the SAD_-- min calculated in Step h), whereby the SAD_-- ave is updated with SAD values after the position change for the first block is estimated.

10. A method as in claim 9 in which Step i) includes calculating SAD_-- ave in response to the number of blocks in a frame, and in which Step k) includes calculating SAD_-- aveLT in response to the total number of blocks in a plurality of frames.

11. A method as in claim 10 in which Step b) includes selecting the initial candidate matrix in response to position changes previously estimated for neighboring blocks, whereby an intra prediction is used to start the estimation process for the first block.

12. A method as in claim 11 in which Step b) includes selecting the initial candidate matrix in response to a position change previously estimated for the first block in the previous frame, whereby an inter prediction is used to start the estimation process for the first block.

13. A method as in claim 11 in which Step e) includes comparing luma pixel data from at least 8 block-sized matrices in the search window, uniformly separated by a whole number of pixel spacings.

14. A method as in claim 13 wherein the blocks of luma pixels are macroblocks each containing a 16×

16 matrix of luma pixels, in which Step d) includes using a maximum ME_-- step of 5, and in which Step g) includes a maximum of 5 iterations of Steps e)-f).

15. A method as in claim 14 including a further steps, following Step i), of:

1) calculating a variance in SAD (SAD_-- var) in response to SAD_-- min calculated in Step h), SAD_-- ave updated in Step i), and the number of macroblocks in a frame;

C₂) a step following Step c), and proceeding Step d), in which SAD_-- var is provided; and

in which Step d) includes the calculation of ME_-- step in response to the SAD_-- var, whereby SAD_-- var is updated in Step

     1) for provision in Step c₂) of the next block position change estimate.

16. A method as in claim 15 in which Step i) includes the calculation of SAD_-- ave as follows:

space="preserve" listing-type="equation">(SAD.sub.-- ave)=((numMB-1)(SAD.sub.-- ave).sub.0 +SAD.sub.-- min)/numMB

where (SAD_-- ave)₀ is the SAD_-- ave from the previous macroblock position change estimate, and numMB is the number of macroblocks in a frame.

17. A method as in claim 16 in which Step k) includes the calculation of SAD_-- aveLT as follows:

space="preserve" listing-type="equation">(SAD.sub.-- aveLT)=((numMBsLT-1)(SAD.sub.-- aveLT).sub.0 +SAD.sub.-- min)/numMBsLT

where (SAD_-- aveLT)₀ is the SAD_-- aveLT calculated from the previous macroblock position change estimate, and numMBsLT is the total number of macroblocks in a plurality of frames.

18. A method as in claim 17 in which Step d) includes the calculation of ME_-- step as follows:

a) if SAD_-- init<

SAD_-- ave-SAD_-- var, then

ME_-- step=ME_-- stepAVE-2;

b) else if SAD_-- init<

SAD_-- ave, then

ME_-- step=ME_-- stepAVE-1;

c) else if SAD_-- init<

SAD_-- ave+SAD_-- var, then

ME_-- step=ME_-- stepAVE;

d) else if SAD_-- init<

SAD_-- ave+2(SAD_-- var), then

ME_-- step=ME_-- stepAVE+1; and

e) else ME_-- step=ME_-- stepAVE+2.

19. A method as in claim 18 wherein ME_-- stepAVE is initialized with a value of 4, and in which Step j) includes updating the calculation of ME_-- stepAVE as follows:

a) if SAD_-- ave>

a₀ (SAD_-- aveLT)/a₁, then

ME_-- stepAVE=ME_-- stepAVE+1; and

b) else if SAD_-- ave<

a₂ (SAD_-- aveLT)/a₁, then

ME_-- stepAVE=ME_-- stepAVE-1

where a₀ >

a₁ >

a₂ >

0.

20. A method as in claim 19 in which Step j) includes the value of a₀ being 10, a₁, being 8, and a₂ being 7.

21. A method as in claim 19 in which Step e) includes using the value of ME_-- step calculated in Step d) to calculate s, the number of pixels initially separating the centers of adjoining macroblock-sized matrices in the search window, where s is calculated as follows:

space="preserve" listing-type="equation">s=2.sup.(ME.sbsp.--.sup.step-1) ; and

in which Step f) includes dividing the value of s by 2, to reduce the spacing between macroblocks in the search window after every iteration of Steps e)-f).

22. A method as in claim 19 in which Step l) includes the calculation of SAD_-- var as follows:

space="preserve" listing-type="equation">SAD.sub.-- var=sqrt[((numMB-1)*((SAD.sub.-- var).sub.0).sup.2 +(SAD.sub.-- min-SAD.sub.-- ave).sup.2)/numMB

where (SAD_-- var)₀ is the SAD_-- var from the previous macroblock position change estimate.

23. In a digital video system compression format where a video sequence is represented in series of frames, including a previous frame followed by a current frame, all separated by a predetermined time interval, the frames being divided into a plurality of blocks with predetermined positions, with each block having a size to include a predetermined matrix of luma pixels, a method for efficiently estimating the change in position of an image represented by a matrix of luma pixel data in a series of blocks in the current frame, from corresponding block-sized matrices of luma pixel data in the previous frame, the method comprising the steps of:

a) selecting a first block in the current frame;

b) selecting a block-sized matrix of luma pixels in the previous frame as an initial candidate matrix corresponding to the first block in the current frame;

c) providing a short term average comparison of luma pixel data between frames, derived from previous block position change estimates;

d) with the use of the short term average provided in Step c) to define the search pattern, searching in the area of luma pixels surrounding the candidate matrix to find a final candidate block-sized matrix that most closely compares with the luma pixel data of the first block, whereby a history of position changes defines the search pattern; and

e) updating the short term average comparison of luma pixel data, with the comparison of luma pixel data of the first block and the final candidate matrix calculated in Step d), whereby the short term average is modified for provision in Step c) of the next block position change estimate.

24. A method as in claim 23 including the further step, following Step d), of:

f) updating a long term average comparison of luma pixel data with the comparison of luma pixel data of the first block and the final candidate matrix calculated in Step d).

25. A method as in claim 24 including further steps of:

g) a step following Step f), updating a long term average of search pattern sizes in response to the short term average comparison of luma pixel data updated in Step e) and the long term average comparison of luma pixel data updated in Step f);

c₁) a step following Step c), and proceeding Step d), of providing the long term average of search pattern sizes; and

in which Step d) includes defining the search pattern in response to the long term average of the search pattern size.

26. A method as in claim 25 in which Step d) includes comparing luma pixel data by the calculation of the sum of absolute differences (SAD) of luma pixel data between each of the plurality of block-sized matrices in the search window and the first block in the current frame, and in which a calculation of the block-sized matrix with the minimum SAD (SAD_-- min) is the comparison of luma pixel data between the first block and the final candidate matrix.

27. A method as in claim 26 in which Step c) includes a short term average of SAD (SAD_-- ave) as the short term average comparison of luma pixel data, and in which Step e) includes updating SAD_-- ave with the SAD_-- min calculated in Step d), whereby the SAD_-- ave is updated with SAD values in Step e) for provision in Step c) of the next block position change estimate.

28. A method as in claim 27 in which Step f) includes a long term average (SAD_-- aveLT) as the long term average comparison of luma pixel data, and in which Step f) includes updating SAD_-- aveLT with SAD_-- min calculated in Step d), whereby SAD_-- aveLT is updated with SAD values in Step f) for provision in Step g.

29. A method as in claim 28 in which Step e) includes updating SAD_-- ave in response to the number of blocks in a frame, and in which Step f) includes updating SAD_-- aveLT in response to the total number of blocks in a plurality of frames.

30. A method as in claim 29 in which Step b) includes selecting the initial candidate matrix in response to position changes previously estimated for neighboring blocks, whereby an intra prediction is used to start the estimation process for the first block.

31. A method as in claim 29 in which Step b) includes selecting the initial candidate matrix in response to position changes previously estimated for the first block in the previous frame, whereby an inter prediction is used to start the estimation process for the first block.

32. A method as in claim 29 including further steps, following Step e), of:

h) calculating a variance in SAD (SAD_-- var) in response to SAD_-- min calculated in Step d), SAD_-- ave updated in Step e), and a the number of macroblocks in a frame;

c₂) a step following Step c), and proceeding Step d), in which SAD_-- var is provided; and

in which Step d) includes defining the search pattern in response to the SAD_-- var.

33. In a digital video system compression format where a video sequence is represented in series of frames, including a previous frame followed by a current frame, all separated by a predetermined time interval, the frames being divided into a plurality of macroblocks with predetermined positions, with each macroblock having a size to include a 16×

16 matrix of luma pixels, a method for efficiently estimating the change in position of an image represented by a matrix of luma pixel data in a series of macroblocks in the current frame, from corresponding macroblock-sized matrices of luma pixel data in the previous frame, the method comprising the steps of;

a) selecting the next macroblock in the series of macroblocks in the current frame;

b) selecting a macroblock-sized matrix of luma pixels in the previous frame as an initial candidate matrix corresponding to the macroblock selected in Step a), in response to position changes previously estimated for neighboring blocks, whereby an intra prediction is used to start the estimation process;

c) calculating the SAD (SAD_-- init) between the macroblock selected in Step a) and the initial candidate matrix selected in Step b);

d) providing a short term average SAD (SAD_-- ave) of luma pixel data between frames, derived from previous position change estimates;

e) providing a long term average of ME_-- step (ME_-- stepAVE), made in a plurality of macroblock position change estimates;

f) providing a variance in SAD (SAD_-- var) derived from previous position change estimates;

g) calculating the number of iterations (ME_-- step) of searching required until the spacing between block-sized matrices is the minimum spacing, the ME_-- step calculation being responsive to the values of SAD_-- init, SAD_-- ave, ME_-- step AVE, and SAD_-- var;

h) calculating the initial spacing (s) between potential candidate matrices in response to the value of ME_-- step calculated in Step g);

i) calculating the SAD between the macroblock selected in Step a) and at least 8 uniformly distributed macroblock-sized matrices, with a spacing between the centers of neighboring matrices equal to s, to locate a new candidate matrix with the minimum SAD (SAD_-- min);

j) iterating the search process as follows;

1) when s is greater than, or equal to the minimum spacing, then divide s by 2, creating a new value of s, and go to Step i); and

2) when s is less than the minimum spacing, then continue;

k) selecting the final candidate matrix in the final iteration of Step i) and comparing to the block selected in Step a) to calculate SAD_-- min;

l) with the SAD_-- min, updating SAD_-- ave, ME_-- stepAVE, and SAD_-- var for use in calculating ME_-- step in Step g) of the position change estimate of the next macroblock; and

m) going to Step a) and repeating the position change estimate process for the next macroblock in the series subsequent to the macroblock selected in Step a), whereby the number of search iterations required for a position change estimate varies in response to the history of SAD of previously estimated macroblocks.