Programmable architecture and methods for motion estimation

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.

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.

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.