Abstract:
A plurality of memory circuits and a logic circuit. The plurality of memory circuits may be configured to store a plurality of pixels. The pixels may be used in a motion estimation stage of a video encoder. The logic circuit may be configured to (i) control which of the pixels are stored in which of the plurality of memory banks and (ii) control accessing of the plurality of pixels.

Description:
FIELD OF THE INVENTION 
   The present invention relates to video processing generally and, more particularly, to a method and/or apparatus for implementing a tiled memory array for full search motion estimation. 
   BACKGROUND OF THE INVENTION 
   Certain design applications specify the need for a high performance motion estimator using an array of 16×16 sum of absolute difference value pixel processing elements, such that utilization is maximized for any search size. 
   Conventional solutions implement either a single memory or a very wide memory. With a single memory, data is stored in raster words. An array of registers is also implemented outside a PEL array to allow sequential loading of data words. The array is large enough to allow 16 words to be written when in a continuous horizontal scan. The single memory solution uses a large array of registers external to the PEL array. Such an array takes significant time to shift down to a particular row. 
   In a very wide memory implementation (either full row or full column), a barrel shifter selects the correct position. A 17 th  row register allows a shift-down in a single cycle. The very wide memory apparatus cannot handle small searches less than the width of a macroblock, since such searches do not fill the 17 th  row. 
   It would be desirable to implement a tiled memory array for full search motion estimation that operates with arbitrarily sized searches and does not need an array of registers external to the search array. 
   SUMMARY OF THE INVENTION 
   The present invention concerns a plurality of memory circuits and a logic circuit. The plurality of memory circuits may be configured to store a plurality of pixels. The pixels may be used in a motion estimation stage of a video encoder. The logic circuit may be configured to (i) control which of the pixels are stored in which of the plurality of memory banks and (ii) control accessing of the plurality of pixels. 
   The objects, features and advantages of the present invention include providing tiled memory array for implementing full search motion estimation that may (i) provide multiple memories used to store search data, (ii) provide data in memories organized so arbitrarily located directional lines segments of adjacent pixels may be accessed effectively simultaneously, and/or (iii) implement a circuit surrounding a memory to enable directional line segment access. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     These and other objects, features and advantages of the present invention will be apparent from the following detailed description and the appended claims and drawings in which: 
       FIG. 1  is a block diagram of a video system illustrating a context of the present invention; 
       FIG. 2  is a block diagram of the present invention; 
       FIG. 3  is a diagram illustrating a variety of search patterns; 
       FIG. 4  is a block diagram of the search memory and the PEL array; 
       FIG. 5  is a block diagram of an element of the PEL array; 
       FIG. 6  is a block diagram illustrating addressing of the search memory; 
       FIG. 7  is a block diagram of the search memory; 
       FIG. 8  is a block diagram of the address calculation circuit; and 
       FIG. 9  is a block diagram illustrating the coordinates of each pixel stored in each memory bank. 
   

   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
   Referring to  FIG. 1 , a block diagram of an encoder  16  is shown illustrating a context for the present invention. The encoder  16  may accept a video source signal (e.g., REFERENCE_DATA) as an input signal. The signal REFERENCE_DATA may be presented to a motion estimation block (or circuit)  100  that may be used to determine motion difference between frames. Details of the motion estimation circuit  100  will be described in more detail in connection with  FIG. 2 . An output of motion estimation circuit  100  may be passed to a motion compensation block (or circuit)  52 . A combination block (or circuit)  54  may subtract an output signal from the motion compensation module  52  from the input video source signal REFERENCE_DATA to create a signal presented to a transformation and quantization block (or circuit)  56 . An output signal from motion the compensation block (or circuit)  52  may also be provided to an adder block (or circuit)  60 . 
   The circuit  56  generally transforms and quantizes an output signal from the combination circuit  54 . An output signal from the circuit  56  may be recalculated based upon prediction error formed from a loop comprising the circuits  52 ,  54 ,  56 ,  58 ,  60  and  61 . An output of the circuit  56  may be presented as an input to the binarization unit  62 . The output signal  18  generally comprises a compressed video bitstream for transmission or storage. The output signal from the circuit  56  may become an input signal to an inverse transformation block (or circuit)  58 . The inverse transform circuit  58  generally applies an inverse transformation and an inverse quantization to the signal received from the circuit  56  and provides a resulting signal to an adder block (or circuit)  60 . The adder circuit  60  may combine the inverse quantized signal with the output signal from the motion compensation circuit  52  to create a reconstructed signal. Reconstructed pictures in the reconstructed signal may be stored in a reference memory  61 . The reconstructed pictures may then be used as reference pictures by the motion compensation module  52 . The reference memory  61  may also present a signal (e.g., SEARCH_DATA) to the motion estimation circuit  100 . The signal SEARCH_DATA may be used by the motion estimation circuit during the exceeding process. 
   An MPEG video transmission may be implemented as a series of pictures taken at closely spaced time intervals. In the MPEG/H.26x standards, a picture may be referred to as a “frame” or a “field” (hereafter, generically referred to as frames). For example, each picture in a video sequence may be encoded as one of two types, (i) an intra frame or (ii) an inter frame. Intra frames (e.g., I-frames) may be encoded in isolation from other frames, compressing data based on similarity within a region of a single frame. Inter frames (e.g., P-frames and B-frames) may be coded based on similarity a region of one frame and a region of a successive frames. Fields may be treated in a similar manner. 
   In a simplest form, an inter frame may be thought of as encoding the difference between two successive frames. Consider two frames of a video sequence showing waves washing up on a beach. The areas of the video that show the sky and the sand on the beach generally do not change, while the area of video where the waves move does change. An inter frame in the sequence may contain only the difference between two frames. As a result, only pixel information relating to the waves may be repeatedly encoded, not pixel information relating to the sky or the beach. 
   An inter frame may be encoded by generating a predicted value for each pixel in the frame based on pixels in previously encoded frames. The aggregation of the predicted values is usually called a predicted frame. The difference between the original frame and the predicted frame may be called a residual frame. The encoded inter frame generally contain information about how to generate the predicted frame utilizing both the previous frames and the residual frame. In the example of waves washing up on a beach, the predicted frame may be the first frame of the two frames and the residual frame may be the difference between the two frames. 
   In the MPEG-AVC/H.264 standard, two types of inter frames may be defined. Predictive frames (e.g., P-frames) may be encoded based on a predictive frame created from one or more frames that occur earlier in the video sequence. Bidirectional predictive frames (e.g., B-frames) are generally based on predictive frames that are generated from two frames either earlier or later in the video sequence. 
   Referring to  FIG. 2 , a block diagram of the motion estimation block (or system)  100  is shown. The system  100  generally comprises a block (or circuit)  102 , a block (or circuit)  104 , a block (or circuit)  106 , a block (or circuit)  108 . In one example, the circuit  102  may be implemented as a search memory. The search memory  102  may be implemented as a plurality of random access memories (RAMS). In one example, the circuit  104  may be implemented as a processing element (PEL) array. In one example, the circuit  106  may be implemented as a sum circuit. In one example, the circuit  108  may be implemented as a search controller circuit. The circuit  102  may have an input  110  that may receive the signal SEARCH_DATA, an output  112  that may present a signal (e.g., PIXEL_LINE) and an input  114  that may receive one or more control signals (e.g., a signal ADDRESS, a signal DIRECTION, etc.). The circuit  104  may have an input  116  that may receive a signal (e.g., PIXEL_LINE), an input  118  that may receive the signal REFERENCE_DATA, an input  120  that may receive a signal (e.g., SHIFT_DIR) and an output  122  that may present a signal (e.g.,  256 _DIFFS). The circuit  106  may have an input  124  that may receive the signal  256 _DIFFS, and an output  126  that may present a signal (e.g., SUM_DIFFS). The circuit  108  may have an input  110  that may receive the signal SUM_DIFFS, an output  128  that may present the signal SHIFT_DIR, an output  130  that may present a signal (e.g., BEST_MATCH_VECTOR) and an output  132  that may present the control signals ADDRESS and DIRECTION. 
   Referring to  FIG. 3 , a diagram illustrating a variety of search patterns (a)-(d) are shown. A search pattern (a) illustrates a sequence of vertical searches. A search pattern (b) illustrates a continuous horizontal search pattern. A search pattern (c) illustrates a gradient descent pattern. A search patter (d) illustrates a concentric type search pattern. The various search patterns and may cross over various banks of the memory  102 . 
   Referring to  FIG. 4 , a more detailed diagram of the search memory  102  and the PEL array  104  is shown. The memory  102  is shown implemented as 16 banks of random access memory. While 16 banks are shown, the particular number of banks may be varied to meet the design criteria of a particular implementation. The PEL array  104  is shown implemented as a 16×16 processing element array. The number of rows and columns of the PEL array  104  may or may not match the number of banks in the memory  102 . An element  150  is shown illustrating an example of any one of the elements in the PEL array  104 . 
   Referring to  FIG. 5 , a more detailed diagram of the element  150  is shown. The element  150  generally comprises a block (or circuit)  152 , a block (or circuit)  154 , a block (or circuit)  156 , a block (or circuit)  158 . The circuit  152  may receive data from the neighboring cell. The data may be received from a left cell, a right cell, a cell directly above the cell  150  or a cell directly below the cell  150 . The signals LEFT, RIGHT, UP and DOWN, represent data from the neighboring cells. The signal SHIFT_DIR may be used to select which of the neighboring cells the cell  10  receives data from. If the cell  150  is located on the edge of the PEL array (e.g., either the left edge, the right edge, the top edge, or the bottom edge) data may instead arrive from the signal PIXEL_LINE. The circuit  154  and the circuit  156  may be implemented as registers that hold data in response to a clock signal (not shown). The register  154  presents a signal (e.g., COMPARE_DATA). The shift register  156  presents the signal REFERENCE_DATA. The circuit  156  presents a signal (e.g., DIFF[N]). The signal COMPARE_DATA may also be presented to the neighboring cells in the PEL array  104  as the signals LEFT′, RIGHT′, UP′ AND DOWN′. Each of the elements within the PEL array  104  present a signal DIFF[N]. The combination of the outputs of the circuits  158  within each cell make up the signal  256 _DIFFS, which is generally a multi-bit signal. 
   Referring to  FIG. 6 , the diagram illustrating addressing of the search memory  102  is shown. The horizontal axis generally represents the width of a search window. In the example shown, the width is 32 pixels wide. The vertical axis shows the height of the search window. In the example shown, the search height is 24 pixels. Each of the grids is labeled to show which memory bank is being accessed. For example, a box  200  shows a pixel stored in memory bank  8 , located at column  2 , row  22 . The box  200  represents data for a particular pixel, which is typically 8 bits. A box  202  represents a line of pixels. The box  202  starts at column  6 , row  3 . The first pixel of the line is stored in memory bank, the second pixel of data is stored in memory bank  10 , the third pixel of data is stored in memory bank  11 , etc. A second box  204  represents data for another line of pixels. The box  204  starts at column  6 , row  5 . The first pixel is stored in memory bank  11 , the second pixel is stored in memory bank  12 , etc. 
   Referring to  FIG. 7 , a more detailed diagram of the search memory  102  is shown. The search memory  102  generally comprises a number of blocks (or circuits)  170   a - 170   b , a number of blocks (or circuits)  180   a - 180   n , a block (or circuit)  186 , a block (or circuit)  188 , a number of blocks (or circuits)  190   a - 190   n  and a block (or circuit)  196 . The circuits  170   a - 170   b  may be implemented as multiplexers. In the example shown, the circuits  170   a - 170   b  are implemented as 2-input multiplexers. The signal DIRECTION may be used as a select input to the circuits  170   a - 170   b . In general, the signal DIRECTION indicates whether a horizontal or a vertical access is needed. The signal ADDRESS from  FIG. 2  is shown implemented as a signal (e.g., Y 0 ) and a signal (e.g., X 0 ). 
   The circuits  180   a - 180   n  may be implemented as address calculation circuits. The circuit  188  may be implemented as a barrel shifter. In the example shown, the barrel shifter  188  may be implemented as a 16-input and 16-output shifter. The circuits  180   a - 108   n  may be used to generate address signals (e.g., ADDRa-ADDRn) that may be presented to the circuit  188 . The address signals ADDRa-ADDRn may be generated in response to signals received from the circuits  170   a - 170   n , the signal Y 0  and the signal X 0 . The circuit  186  may be implemented as a right shift circuit that may effectively divide the signal Y 0  by 2 4  (16). If so, the circuit  186  normally controls a shift input of the circuit  188  and the circuit  196 . The circuits  190   a - 190   n  may be implemented as the memory banks. 
   Referring to  FIG. 8 , a more detailed diagram of one of the address calculation circuits  180  is shown. The circuit  180  generally comprises a block (or circuit)  210 , a block (or circuit)  212 , and a block (or circuit)  214 . The circuit  210  may divide the signal X by 16 (by shifting the signal X to the right 4 binary digits). The circuit  212  may multiply the signal X by a signal (e.g., SEARCH_IMAGE_HEIGHT). The circuit  214  may add the output of the circuit  212  to the signal Y to generate the signal ADDRESS. 
   Referring to  FIG. 9 , a table is shown illustrating the coordinates of each particular pixel stored in each memory bank. The number of memory banks RAM 0 -RAM 15  are shown. A number of rows  0 - 47  are also shown. 
   The search memory  102  may simultaneously calculate the addresses ADDRa-ADDRn for each of the memory banks  190   a - 190   n . The search memory  62  may generate the addresses ADDRa-ADDRn in response to a given vector (e.g., origin, direction), and a tiling of an array of pixels, of search data. The search memory  62  may read the memory banks  190   a - 190   n  and forward data to the pel array  104 . The pel array  104  may then shift the data from an edge of the array to allow searching of a given location. A series of such accesses, coupled with a programmable shift direction of the pel array  104  may allow efficient and flexible full search motion estimation. 
   The motion estimation circuit (or engine)  100  is normally loaded with data from the signal REFERENCE_DATA. The data from the signal REFERENCE_DATA is usually a 16×16 array of pixels. The search data may be in the form of an array larger than 16×16. The present invention may be used to find the best match between the two. A sum of absolute differences may be used to rank the match, although other configurations may be implemented (e.g., a sum of squared distance, etc.) 
   The signal SEARCH_DATA is normally loaded into the search memory  102 . The search memory  102  may be implemented as the memory banks  190   a - 190   n . The data may be tiled over the memory banks  190   a - 190   n . The tiling may be implemented such that any row or column of 16 adjacent pixels is normally accessible at the same time. The circuit  180  accesses the row or column of data in response to the signals X, Y, and DIRECTION logical address. A number of circuits  180   a - 180   n  generate the address signals ADDRa-ADDRn. The logical addresses ADDRa-ADDRn are then put through the address translation of  FIG. 9  to calculate the ram addresses. The addresses are then shifted to address the appropriate ram  190   a - 190   n . The resulting data is shifted back to the correct order. 
   With a general access of 16 pixels horizontally (or vertically) arranged, the motion estimation circuit  100  may allow any type of search with full utilization during the search. The estimation portion of the search may be implemented with the array of processing units of  FIG. 6 , which calculates the absolute difference between one reference data pixel and a candidate search pixel. The signal SEARCH_DATA may then be shifted within the PEL array  104 , and externally in on one edge in multiple directions (e.g., 3 or more). The entire 16×16 array of processing units may have 3 or more edges to shift in data. These input buses are all driven by the output of the search memory unit  150 . 
   For each search location, the array of 256 differences are normally summed. In certain applications, other operations, such as a hadamard transform, may occur before the summing. The signal SUM_DIFFS may then be fed back to the search controller  108 , which may keep track of the search location with the lowest difference. The signal SUM_DIFFS may also be used to guide the search, such as with a 2 step, or gradient descent. 
   The present invention may implement a tiled memory array for full search motion estimation that may be implemented without an array of registers, external to the search array. A variety of sizes of searches may be performed without reload penalties. 
   A variety of different search metrics may be implemented. For example, instead of performing a sum of absolute differences, a sum of squared differences, a sum of absolute differences of transformed differences, or other summing may be performed. 
   The present invention may also have non-video compression applications. For example, the present invention may be implemented on a press registration for print inspection, scene analysis and object tracking, counterfeit detection, etc. 
   A variety of sizes of memory tilings may be formulated, so long as the basic property holds that a horizontal or vertical stripe are accessed in a single cycle. The same data may be used to send data into a sub pel search array  104  following the full pel best results. The scheme may be extended to support non-adjacent pixels for hierarchical searches. 
   The various signals of the present invention are generally “on” (e.g., a digital HIGH, or 1) or “off” (e.g., a digital LOW, or 0). However, the particular polarities of the on (e.g., asserted) and off (e.g., de-asserted) states of the signals may be adjusted (e.g., reversed) accordingly to meet the design criteria of a particular implementation. 
   As used herein, the term “simultaneously” is meant to describe events that share some common time period but the term is not meant to be limited to events that begin at the same point in time, end at the same point in time, or have the same duration. 
   While the invention has been particularly shown and described with reference to the preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made without departing from the scope of the invention.