Programmable architecture and methods for motion estimation

• US 5,594,813 A
• Filed: 02/19/1992
• Issued: 01/14/1997
• Est. Priority Date: 02/19/1992
• Status: Expired due to Term

• Current Assignee: 8X8, Inc.
• Original Assignee: Medi-Tech
• Inventors: Wang, Chi S., Fandrianto, Jan, Sutardja, Sehat, Martin, Bryan R., Rainnie, Hedley K. J.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): KELLEY, CHRISTOPHER S
• Application Number:
  US07/838,380
• Time in Patent Office: 1,791 Days
• Field of Search: 382/30, 382/34, 382/41, 382/236, 382/238, 382/303, 382/307, 358/105, 348/415, 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. In motion vector searching, the ALU performs pixel absolute difference arithmetic using the pixel groups from the image memory and from the search memory, and determines a sum of absolute differences in the tree adder. In half pixel interpolation, the ALU performs pixel averaging arithmetic using pixel groups from the search memory, and writes back to the search memory. In quarter pixel interpolation, the ACU performs pixel averaging arithmetic using pixel groups from the image and search memories, and writes back to the search memory. In some quarter pixel interpolations, temporary interpolated blocks from the image memory are used to interpolated quarter pixel blocks. These temporary blocks are obtained by pixel averaging in the ALU using pixel groups from the search memory. In error prediction determination, the ALU performs pixel subtraction using the pixel groups from the image memory and from the search memory, and writes back to the image memory.

Claims

1. 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 N pixels in width, 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 N pixels in width, a second write port, and third and fourth 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 third and fourth read ports during an address cycle;

a first shifter having an input port coupled to said third read port and an output port N pixels in width;

a second shifter having an input port coupled to said fourth read port and an output port N pixels in width;

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

a second multiplexer having one input port coupled to the output ports of said first and second shifters, another input port coupled to the output port of said second shifter, and an output port;

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

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

wherein the second output port of said arithmetic unit is routed to said first and second write ports.

2. 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 N pixels in width;

selecting a search block within said search window;

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

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

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

selecting N contiguous pixels in parallel from

the 2*N contiguous pixels;

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 differences 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 selecting step and said repeated search block selecting step as a best match block based on said identifying step.

3. 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, further comprising the steps of;

identifying a temporary best match search block while skipping every B/C blocks, wherein B is a search block dimension in pixels and C is any positive binary number less than a number of pixels in a search block;

identifying a smaller search window; and

identifying said best match search block while skipping every B/D blocks, wherein B is a search block dimension in pixels and D is any positive binary number greater than C;

selecting any N contiguous pixels in parallel during an address cycle from any one of 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 differences 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 selecting step and said repeated search block selecting step as a best match block based on said identifying step.