Programmable architecture and methods for motion estimation

Claim 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.

Claim 2

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.

Claim 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 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.

Claim 4

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.

Claim 5

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.

Claim 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, 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.