Programmable architecture and methods for motion estimation

• US 5,901,248 A
• Filed: 08/06/1996
• Issued: 05/04/1999
• Est. Priority Date: 02/19/1992
• Status: Expired due to Term

• Current Assignee: 8X8, Inc.
• Original Assignee: 8X8, Inc.
• Inventors: Martin, Bryan R., Rainnie, Hedley K.J., Fandrianto, Jan, Sutardja, Sehat, Wang, Chi Shin
• Primary Examiner(s): Kelley, Christopher S.
• Application Number:
  US08/692,993
• Time in Patent Office: 1,001 Days
• Field of Search: 382/238, 382/236, 348/407, 348/409, 348/413, 348/416
• US Class Current: 382/236
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/231 using full search
• CPC Class Codes: H04N 19/43 Hardware specially adapted for motion estimation or compensation
• CPC Class Codes: H04N 19/433 characterised by techniques for memory access
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/523 with sub-pixel accuracy
• CPC Class Codes: H04N 5/145 Movement estimation for video coding H04N19/51

Abstract

A programmable motion estimator includes one dual ported memory for storing an image block, the prediction error, and a temporary block used in interpolation, and a pixel-group random access dual ported memory for storing a search window. The two ports of the two memories are selectively applied to an arithmetic logic unit, or ALU, through a multiplexer. One output of the ALU provides an absolute difference, which is furnished to a tree adder. Another output of the ALU provides an average value or a difference value, as selected, which is routed to the inputs of the image memory and the search memory. Among other tasks, the programmable motion estimator performs motion vector searching, half pixel interpolation, quarter pixel interpolation and error prediction determination.

Claims

1. A method for determining a prediction error in motion estimation following the identification of a best match lock, comprising the steps of:

storing an image block in a first memory having a plurality of addressable locations N pixels in width;

selecting N pixels in parallel from any one of said addressable locations of said first memory during an address cycle;

storing said best match block in a second memory having a plurality of addressable locations M pixels in width, M being greater than N;

selecting any N contiguous pixels in parallel from any of said addressable locations of said second memory corresponding to said best match block during an address cycle;

determining differences of the N pixels from said first memory selecting step and the N pixels from said second memory selecting step; and

storing the results of said differences determining step.

2. A method as in claim 1, wherein said second memory comprises a memory array having a plurality of addressable locations N pixels in width, second memory selecting step comprises the steps of:

selecting N pixels in parallel from any one of said addressable locations of said memory array corresponding to the selected search block during an address cycle;

selecting N pixels in parallel from an adjacent addressable location of said memory array corresponding to the selected block during an address cycle, 2*N contiguous pixels thereby being selected; and

selecting N contiguous pixels of the 2*N contiguous pixels selected in said first-mentioned pixel selecting step and said second-mentioned pixel selecting step.

3. A method for selectively updating pixel information in a memory and thereafter selectively accessing surviving old pixel information and new pixel information contained therein, comprising the steps of:

arranging pixel information in a plurality of banks, each bank having a plurality of addressable locations and each addressable location containing a pixel group, adjacent pixel groups being pixel groups of adjacent banks having the same addressable location and pixel groups of adjacent banks having adjacent address locations;

overwriting at least one of said banks of pixel information with new pixel information;

selecting pixel group from one of said banks in accordance with a specified addressable location;

selecting an adjacent pixel group; and

selecting a subset of contiguous pixels from the selected pixel group and from the selected adjacent pixel group.

4. A method as in claim 3, wherein:

said arranging step comprises the step of arranging pixel information in five banks, each bank having an equal number of addressable locations and containing pixel groups of equal size;

said overwriting step comprises the step of overwriting two adjacent banks; and

said subset selecting step comprises the step of selecting a number of contiguous pixels equal to the size of said pixel groups.

5. An apparatus for performing a variety of operations relating to motion estimation, including pixel differences, sum of absolute pixel differences, and pixel averaging, comprising:

a first memory having a plurality of addressable locations, a first write port, and first and second read ports, wherein N pixels from any one of said addressable locations are accessible in parallel on each of said first and second read ports during an address cycle;

a second memory having a plurality of addressable locations greater than N pixels in width, a second write port, and third and fourth second memory read ports, wherein any N contiguous pixels from any one of said addressable locations are accessible in parallel on each of said third and fourth read ports during an address cycle, and the second memory having;

a memory array having a plurality of addressable locations N pixels in width and fifth and sixth read ports, wherein N pixels from any one of said addressable locations and N pixels from an adjacent addressable location are accessible in parallel on each of said fifth and sixth read ports during an address cycle,

a first shifter having an input coupled to said fifth read port and an out put N pixels in width, the output of said first shifter being said fifth read port, and

a second shifter having an input coupled to said sixth read port and an output N pixels in width, the output of said second shifter being said sixth read port; and

a first multiplexer having one input coupled to said first and second read ports, another input coupled to said third read port, and an output;

a second multiplexer having one input coupled to said third and fourth read ports, another input coupled to said fourth read port, and an output;

an arithmetic unit having a first operand input coupled to the output of said first multiplexer, a second operand input coupled to the output of said second multiplexer, a first output for furnishing the absolute value of a difference between said first and second operandi, and a second output for selectively furnishing one of a difference between said first and second operandi, and an average of said first and second operandi, and an average of said first and second operandi; and

an adder coupled to the first output of said arithmetic unit;

wherein the second output of said arithmetic unit is routed to said first and second inputs.

6. A method for motion estimation, comprising the steps of:

storing an image block in a first memory having a plurality of addressable locations N pixels in width;

selecting N pixels in parallel during an address cycle from any one of said addressable locations of said first memory;

storing a search window in a second memory having a plurality of addressable locations M pixels in width, M being greater than N;

selecting a search block within said search window, including skipping every I search blocks, wherein I is any positive integer;

selecting any N contiguous pixels in parallel during an address cycle from any one of best match said addressable locations of said second memory corresponding to the search block from said search block selecting step;

determining a sum of absolute differences of the N pixels from said first memory selecting step and the N pixels from said second memory selecting step;

accumulating the results of said sum of absolute differences determining step;

repeating said first memory selecting step, said second memory selecting step, said sum of absolute difference determining step, and said accumulating step for all pixels in the search block from said search block selecting step to obtain a first sum of absolute differences;

repeating said search block selecting step, said first memory selecting step, said second memory selecting step, said sum of absolute differences determining step, and said accumulating step for all pixels in the search block from said repeated search block selecting step to obtain a second sum of absolute differences;

identifying the lesser of said first sum of absolute differences and said second sum of absolute differences; and

selecting one of the search blocks from said search block relating step as a best match block based on said identifying step.