Programmable architecture and methods for motion estimation

• US 6,965,644 B2
• Filed: 03/01/2001
• Issued: 11/15/2005
• Est. Priority Date: 02/19/1992
• Status: Expired due to Fees

• Current Assignee: 8X8, Inc.
• Original Assignee: 8X8, Inc.
• Inventors: Fandrianto, Jan, Sutardja, Sehat, Martin, Bryan R., Wang, Chi Shin, Rainnie, Hedley K. J.
• Primary Examiner(s): Le, Vu
• Application Number:
  US09/797,035
• Publication Number:
  US 20010046264A1
• Time in Patent Office: 1,720 Days
• Field of Search: 375/240.16, 375/240.17, 348699-700, 382/234, 382/236, 382/238, 382/247, 386/109, 386/111, 708/402, 708/407, 711/149
• US Class Current: 375/240.16
• CPC Class Codes: G06T 9/007 Transform coding, e.g. discrete cosine transform
• CPC Class Codes: G06V 10/75 Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries
• CPC Class Codes: H04N 19/433 characterised by techniques for memory access
• CPC Class Codes: H04N 5/14 Picture signal circuitry for video frequency region cameras or camera modules comprising electronic image sensors, or control thereof H04N23/00
• CPC Class Codes: H04N 7/141 between two video terminals, e.g. videophone telephonic communication systems combined with television receiver for reception of entertainment or information matter H04M11/085
• CPC Class Codes: H04N 7/147 Communication arrangements, e.g. identifying the communication as a video-communication, intermediate storage of the signals selecting H04Q
• CPC Class Codes: H04N 7/148 Interfacing a video terminal to a particular transmission medium, e.g. ISDN
• CPC Class Codes: H04N 7/15 Conference systems

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 an arithmetic operation on groups of pixels under program control, comprising:

a first memory having a first read port and a plurality of addressable locations N pixels in width and M rows in height, wherein X pixels from any one of said addressable locations are accessible in parallel on said first read port during an address cycle, X being at least N;

a second memory having a second read port and a plurality of addressable locations greater than N pixels in width and at least M rows in height, wherein any X contiguous pixels, arranged N pixels in width and M rows in height, from any one of said addressable locations are accessible in parallel on said second read port during an address cycle; and

an arithmetic unit having a first operand input port coupled to said first read port, a second operand input port coupled to said second read port, and an output.

2. An apparatus as in claim 1, wherein said second memory comprises:

a memory array having a plurality of addressable locations N pixels in width and a third read port, wherein X pixels from any one of said addressable locations and X pixels from an adjacent addressable location are accessible in parallel on said third read port during an address cycle; and

a shifter having an input port coupled to said third read port and an output port N pixels in width, said shifter output port being said second read port.

3. An apparatus as in claim 2, wherein said shifter is adapted to perform from zero to N-1 shifts on a pixel boundary.

4. An apparatus as in claim 1, further comprising a controller coupled to said first memory by a first address bus, and coupled to said second memory by a second address bus, said controller being under microcode control.

5. An apparatus as in claim 1, further comprising a controller coupled to said first memory by a first address bus, and coupled to said second memory by a second address bus, said controller being under software control.

6. An apparatus as in claim 1, further comprising a state machine coupled to said first memory by a first address bus, and coupled to said second memory by a second address bus.

7. An apparatus as in claim 1, wherein said arithmetic unit comprises a subtractor circuit receiving a first and second operandi so that pixel differences are determinable in parallel.

8. An apparatus as in claim 1, wherein said arithmetic unit comprises an absolute difference circuit receiving a first and second operandi, further comprising an adder coupled to the output port of said arithmetic unit so that a sum of absolute pixel differences is determinable in parallel.

9. An apparatus as in claim 8, wherein said adder is a tree adder.

10. An apparatus as in claim 1, wherein said arithmetic unit comprises an averager circuit receiving a first and second operandi so that pixel averages are determinable in parallel.

11. An apparatus as in claim 1, wherein the arithmetic unit comprises an absolute difference circuit receiving the first and second operandi.

12. An apparatus as in claim 1, wherein the first memory stores a plurality of pixels defining a time t digital video image block having a frame location, and the second memory stores a plurality of pixels defining a time t-1 digital video search window having a frame location approximately centered on the frame location of the digital image block.

13. An apparatus for performing an arithmetic operation on groups of pixels under program control, comprising:

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

an arithmetic unit having a first operand input port coupled to said first read port, a second operand input port coupled to said second read port, and an output.

14. An apparatus as in claim 13, wherein said memory comprises:

a memory array having a plurality of addressable locations N pixels in width, a third read port, and a fourth read port, 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; and

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

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

15. An apparatus as in claim 14, wherein said first and second shifters are adapted to perform from zero to N-1 shifts on a pixel boundary.

16. An apparatus as in claim 13, further comprising a controller coupled to said memory by an address bus, said controller being under microcode control.

17. An apparatus as in claim 13, further comprising a controller coupled to said memory by an address bus, said controller being under software control.

18. An apparatus as in claim 13, further comprising a state machine coupled to said memory by an address bus.

19. An apparatus as in claim 13, wherein said arithmetic unit comprises a subtractor circuit receiving a first and second operandi so that pixel absolute differences are determinable in parallel.

20. An apparatus as in claim 13, wherein said arithmetic unit comprises an absolute difference circuit receiving a first and second operandi, further comprising an adder coupled to the output port of said arithmetic unit so that a sum of pixel differences is determinable in parallel.

21. An apparatus as in claim 20, wherein said adder is a tree adder.

22. An apparatus as in claim 13, wherein said arithmetic unit comprises an averager circuit receiving a first and second operandi so that pixel averages are determinable in parallel.

23. A method for performing an arithmetic operation on pixel operandi of width N, comprising the steps of:

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

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

selecting a second group of any N contiguous pixels in parallel from any one of said addressable locations of said memory during said address cycle;

performing an arithmetic operation wherein a first operand is from said first group of pixels and a second operand is from said second group of pixels.

24. An apparatus for performing an arithmetic operation including two blocks of pixels, comprising:

a first memory having a first read port and a plurality of addressable locations for storing a plurality of pixels arranged in a first pixel block, wherein the first pixel block has a width of N pixels, and the plurality of pixels are accessible in parallel on the first read port during an address cycle;

a second memory having a second read port and a plurality of addressable locations for storing a plurality of pixels arranged in a second pixel block, wherein the second pixel block has a width of greater than N pixels, and any block of contiguous pixels having a width of N pixels from the second pixel block are accessible in parallel on the second read port during an address cycle; and

an arithmetic unit having a first operand input port coupled to the first read port, a second operand input port coupled to the second read port, and an output.

25. An apparatus as in claim 24, wherein the first memory stores a plurality of pixels defining a time t digital video image block having a frame location, and the second memory stores a plurality of pixels defining a time t-1 digital video search window having a frame location approximately centered on the frame location of the digital image block.

26. An apparatus as in claim 24, wherein the first pixel block has a height of M pixels and any block of contiguous pixels from the second pixel block has a height of M pixels.

27. An apparatus as in claim 24, wherein the arithmetic unit comprises a comparator circuit receiving a first operand on the first operand import port and a second operand on the second operand input port such that differences between the first and second operandi are determinable in parallel for each pixel.

28. An apparatus as in claim 24, wherein the arithmetic unit comprises a subtractor circuit receiving the first and second operandi so that pixel differences are determinable in parallel.

29. An apparatus as in claim 24, wherein the arithmetic unit comprises a subtractor circuit receiving the first and second operandi so that pixel differences are determinable in parallel.