Patent Abstract:
A method and apparatus to reduce the system load of motion estimation for DSP discloses circular buffers, a plurality of absolute difference calculation circuits, a multiple input adder, a full adder, a plurality of accumulators, and a control circuit. The first four bytes from the reference block buffer and the first four bytes from the search window buffer are sent to the four absolute difference calculation circuits. The control circuit determines which of the accumulators requires incrementing the value already in that accumulator by the current output of the multiple input adder. A new set of bytes from the search window buffer is then sent to the absolute difference calculation circuits, a new sum is calculated, and a second accumulator is incremented by the new sum. When all accumulators have been updated, new reference block data used. Each byte of data is loaded from memory only once.

Full Description:
BACKGROUND OF INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to power consumption during digital image processing in video compression. More specifically, a device and method that reduce power consumption by reducing the number of memory accesses when calculating absolute difference values for image correlation is disclosed.  
           [0003]    2. Description of the Prior Art  
           [0004]    Video compression standards have long been available to lower the required bandwidth and alternatively to increase the amount of video data that can be stored in any given sized storage media. In line with these goals, motion estimation is widely used for video compression standards such as MPEG-1, MPEG-2, and MPEG-4 among others.  
           [0005]    The conventional methods for motion estimation are well known to those skilled in the art. In general, each frame goes through a process where a current video frame is read into memory. A small reference block is located within a larger search window of the current frame and a motion vector is generated estimating the direction of motion of the reference block within the search window. This motion vector is used in conjunction with information from the previous frame to generate an estimated image frame in respect to the current frame. The estimated image frame is then subtracted from the current frame, which effectively removes duplicated imagery and results in much less data necessary to be saved in the output file.  
           [0006]    Because the estimated image frame is subtracted from the current frame and only the difference is saved, it is obvious that the more accurate the estimation is, the smaller the output file is. The accuracy of the estimated image frame to a large degree depends on the accuracy of the motion vector. The accuracy of the motion vector in turn depends on the accuracy of locating the reference block within the search window.  
           [0007]    It is generally accepted that the reference block can be located within the search window most accurately using a full search. A full search consists of comparing the reference block sequentially with every possible location within the search window. For each location, the comparison is done by adding the absolute values of the difference between the brightness of each pixel in the reference block and the brightness of the corresponding pixel in the current search location. The location with the lowest total of absolute values is considered the best match and is selected to be used to calculate the motion vector.  
           [0008]    Obviously, methods other than a full search that compare the reference block with a more limited number of search locations are frequently employed with satisfying results. However, nearly every method used today selects the best match based on the absolute differences in brightness between the pixels in the reference block and the pixels in the search locations. Therefore, the calculation and summing of the needed absolute differences is the common core of video image correlation.  
           [0009]    Please refer to FIG. 1 that is an absolute difference accumulator circuit (ADAC) according to a prior art. The ADAC comprises a plurality of absolute difference calculation circuits, a multiple input adder, a full adder, and an accumulator. A full description of this particular ADAC can be found in U.S. Pat. No. 5,610,850 incorporated herein by reference. Basically, pixel values from the reference block are inputted to the X 1 -Xn inputs and pixel values from the current search location are inputted into the Y 1 -Yn inputs of the absolute difference calculation circuits. The results of the absolute difference calculation circuits are added by the multiple input adder and output to the full adder. The full adder sums the output from the multiple input adder and the current value in the accumulator and places the sum back into the accumulator. When all of the pixel values for one search location have been processed, the value in the accumulator represents the match value for that particular search location. This match value is then stored elsewhere in memory, the value in the accumulator is reset to zero, and the process repeats for each search location.  
           [0010]    Nearly all image correlation methods used today select search locations that at least in part overlap one another. Because the match value for each search location is independently calculated, the pixel values in the overlapping portions of the search locations need to be loaded into memory multiple times. Each memory access uses power. Often motion estimation is used in devices, such as a PDA or cellular phone, which obtain power from a limited power source such as a battery. Power consumed by unneeded memory accesses prevents that same limited power from being used for other purposes and generates unnecessary heat within the device.  
         SUMMARY OF INVENTION  
         [0011]    It is therefore a primary objective of the claimed invention to reduce power consumption and system load for digital signal processing by reducing the number of memory accesses when calculating absolute difference values in image correlation by calculating match values for multiple search locations simultaneously.  
           [0012]    Briefly summarized, the preferred embodiment of the claimed invention discloses a circular reference block buffer, a circular search window buffer, a plurality of absolute difference calculation circuits, a multiple input adder, a full adder, a plurality of accumulators, and a control circuit. The degree of plurality of the absolute difference calculation circuits is normally equal to the degree of plurality of accumulators and equal to the number of match values being simultaneously calculated. The control circuit includes a storage unit having four pointers, or indices, to control accessing of data in the two circular buffers. The buffers are normally registers.  
           [0013]    A preferred example of the present invention has the plurality of absolute difference calculation circuits and the plurality of accumulators equal to four. At least one word-sized chunk of pixel data is loaded from the search window in memory into the circular search window buffer and a word of pixel data from the reference block is loaded into the circular reference block buffer. The first four bytes of pixel data from the circular reference block buffer are sent to a first input of the four absolute difference calculation circuits respectively. The first four bytes of pixel data from the circular search window buffer are sent to a second input of the four absolute difference calculation circuits respectively. The results of the absolute difference calculations are summed by the multiple input adder and output to the full adder.  
           [0014]    Because each accumulator represents a different search location, the control circuit determines which of the accumulators requires incrementing the value already in that accumulator by the current output of the multiple input adder. The value in the accumulator indicated by the control circuit is then sent to the full adder, added by the full adder to the output from the multiple input adder, and the result placed back into that accumulator. A new set of bytes from the circular search window buffer, offset from the previously sent set of bytes, is then sent to the second input of the absolute difference calculation circuits respectively, a new sum is calculated, and a second accumulator is incremented by the new sum. The cycle repeats using a new set of search window data and incrementing a corresponding accumulator until all accumulators have been updated. The next four bytes of data from the circular reference block buffer and the next set of bytes from the circular search window buffer are then sent to the absolute difference calculation circuits respectively. The process is repeated until the accumulators hold the total match values for their respective search locations. Data for the circular reference block buffer and the circular search window buffer are loaded from memory as needed.  
           [0015]    It is an advantage of the claimed invention that pixel value data is loaded into memory only one time when calculating the match values for a plurality of search locations, reducing system load and power consumption.  
           [0016]    These and other objectives of the claimed invention will no doubt become obvious to those of ordinary skill in the art after reading the following detailed description of the preferred embodiment, which is illustrated in the various figures and drawings. 
       
    
    
     BRIEF DESCRIPTION OF DRAWINGS  
       [0017]    [0017]FIG. 1 is a block diagram of a circuit used for calculating match values according to the prior art.  
         [0018]    [0018]FIG. 2 is a block diagram of a circuit used for calculating match values according to the present invention.  
         [0019]    [0019]FIG. 3 illustrates a circular data buffer according to the present invention.  
         [0020]    [0020]FIG. 4 is a block diagram of a control circuit according to the present invention.  
         [0021]    [0021]FIG. 5 is a flow chart of calculating match values according to the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0022]    Please refer to FIG. 2 through FIG. 4. FIG. 2 is a block diagram of an accumulation circuit  100  for calculating match values according to the present invention. FIG. 3 illustrates a circular data buffer  200  used in the present invention. FIG. 4 is a block diagram of a control circuit  300  for the present invention.  
         [0023]    The accumulation circuit  100  comprises a plurality of absolute difference calculation circuits (ADCC)  110 , a multiple input adder  150 , a full adder  160 , a multiplexer  180 , a demultiplexer  170 , and a plurality of accumulators  192 ,  194 ,  196 , and  198 . Each accumulator may be a register or in memory and of a size sufficient to insure an accurate total of the absolute differences between a reference block and a search location, which in turn depends upon the size of a reference block being used.  
         [0024]    In a preferred embodiment of the present invention shown in FIG. 2, each ADCC  110  comprises a subtractor  115 , a multiplexer  130 , and diode inverter  120 . The subtractor  115  has a first input and a second input for receiving data, a first output, a second output, and a third output for transmitting the result of the subtraction. The first output transmits a one&#39;s complement result, the second output transmits the normal output of subtractor, and the third output transmits a carry signal Cn according the result of the subtraction. The multiplexer  130  selects for output to the multiple input adder. If the Cn is equal to 0, i.e., the result of subtractor is a positive number, the normal output of subtractor is transmitted to the multiple adder. If the Cn is equal to 1, i.e., the result of subtractor is a negative number, the ones complement result is transmitted to the multiple input adder  150 . All the Cn will be decoded by decode circuit  140 . The decode circuit  140  is used to count the number of Cn is equal to one. The output of decode circuit  140  is transmitted to the multiple adder.  
         [0025]    Regardless if the ADCC disclosed by the preferred embodiment is used or an ADCC of another type is used, the control circuit  300  then causes the multiplexer  180  to sequentially select one accumulator  192 ,  194 ,  196 ,  198 . The value stored in the selected accumulator  192 ,  194 ,  196 ,  198  is added in the full adder  160  to the value output by the multiple input adder  150 . The control circuit  300  then causes the demultiplexer  170  to route the output of the full adder  160  to the same selected accumulator  192 ,  194 ,  196 ,  198  so that the value in that same accumulator  192 ,  194 ,  196 ,  198  is incremented by the amount being output by the multiple input adder  150 . The multiplexer  180  and the demultiplexer  170  are both controlled by signals from the control circuit  300 . The signals comprise the least significant bits of the number of the first byte being currently transmitted from the circular SW buffer. In this example, bytes  0 - 3  are transmitted first, followed sequentially by bytes  1 - 4 , bytes  2 - 5 , and bytes  3 - 6 . Thus a 2-bit signal can indicate which accumulator  192 ,  194 ,  196 ,  198  is to be active. The control circuit selects each accumulator  192 ,  194 ,  196 ,  198  in a round-robin fashion, with the accumulator  192 ,  194 ,  196 ,  198  selected rotating with each transfer of new data to the accumulation circuit  100 , allowing four different search locations to be calculated in one pass of a reference block.  
         [0026]    Data destined for the accumulation circuit  100  comprises pixel data included in the reference block (RB) and a search window (SW), the search window including at least one search location. The pixel data for both the reference block and the search window is usually stored in memory. Because accessing memory consumes more power than accessing a local buffer, the present invention comprises two circular buffers  200 : a circular SW buffer  200 S and a circular RB buffer  200 R. Obviously, the term “circular” refers to the method of accessing the circular buffers  200 S,  200 R rather than to a physical arrangement. Methods of providing circular access to a buffer are know in the art. The circular buffers  200 S,  200 R shown in FIG. 3 each comprise 4 words with each word 4 bytes in length, but another size for either or both of the buffers  200 S,  200 R can easily be employed in another example of the present invention. The point is that using the buffers as disclosed in the present invention minimizes the number of memory accesses, and therefore reduces power consumption.  
         [0027]    To control access to each circular buffer  200 S,  200 R, the control circuit  300  comprises a storage unit  310  for storing addresses of current locations within the circular buffers  200 S,  200 R. For this purpose, the storage unit  310  of the control circuit  300  comprises indices VWP 0   320 , VWP 1   330 , VRP 0   340 , and VRP 1   350 . The VWP 0   320  is a word index and comprises the address of where in the circular buffer  200 S a next word of SW data is to be loaded. The VWP 1   330  is also a word index and comprises the address of where in the circular buffer  200 R a next word of RB data is to be loaded. The VRP 0   340  is a byte index and indicates the next byte of data in the circular buffer  200 S to be sent to the accumulation circuit  100 . The VRP 1   350  is also a byte index and indicates the next byte of data in the circular buffer  200 R to be sent to the accumulation circuit  100 .  
         [0028]    The present invention can best be described by example. Please refer to FIG. 5. To simplify the explanation, each of the circular buffers  200 S,  200 R in this example comprises 4 words of address space with each word 4 bytes in length. The first byte in each of the circular buffers  200 S,  200 R has an address of 0, although obviously in reality a different address may be used. The indices VWP 0 , VWP 1  increment by word and the indices VRP 0 , VRP 1  increment by byte. When incremented beyond the address space of the applicable circular buffer  200 S,  200 R, all indices VWP 0 , VWP 1 , VRP 0 , and VRP 1  wrap around so that the first byte in the circular buffer  200 S,  200 R sequentially follows the last byte in the circular buffer  200 S,  200 R. The present invention comprises the following steps in this example to calculate match values for four search locations. A 16 pixel by 16 pixel reference block and a 16 pixel by 19 pixel search window are used. In this example, it is assumed that the start addresses of the reference block and the search window are in word alignment. If the start addresses of reference block and search window are not in word alignment, the following steps can be modified with a suitable VRPn and VWPn.  
         [0029]    Step  400 : Initialization. All accumulators=0. VWP 0 =0. VRP 0 =0. VWP 1 =0. VRP 1 =0.  
         [0030]    Step  405 : Load  1  word of SW pixel data into the circular SW buffer at VWP 0 . Increment VWP 0 .  
         [0031]    Step  410 : Load  1  word of SW pixel data into the circular SW buffer at VWP 0 . Increment VWP 0 .  
         [0032]    Step  415 : Load  1  word of reference data into the circular RB buffer at VWP 1 . Increment VWP 1 .  
         [0033]    Step  420 : Send bytes VRP 0  through VRP 0 +3 from the circular SW buffer and bytes VRP 1  through VRP 1 +3 from the circular RB buffer to the absolute difference calculation circuits.  
         [0034]    Step  425 : Increment the value in a first selected accumulator by the value in the full adder. Increment VRP 0 .  
         [0035]    Step  430 : Send bytes VRP 0  through VRP 0 +3 from the circular SW buffer and bytes VRP 1  through VRP 1 +3 from the circular RB buffer to the absolute difference calculation circuits.  
         [0036]    Step  435 : Increment the value in a second accumulator by the value in the full adder. Increment VRP 0 .  
         [0037]    Step  440 : Send bytes VRP 0  through VRP 0 +3 from the circular SW buffer and bytes VRP 1  through VRP 1 +3 from the circular RB buffer to the absolute difference calculation circuits.  
         [0038]    Step  445 : Increment the value in a third accumulator by the value in the full adder. Increment VRP 0 .  
         [0039]    Step  450 : Send bytes VRP 0  through VRP 0 +3 from the circular SW buffer and bytes VRP 1  through VRP 1 +3 from the circular RB buffer to the absolute difference calculation circuits.  
         [0040]    Step  455 : Increment the value in a fourth accumulator by the value in the full adder. Increment VRP 0 .  
         [0041]    Step  460 : Finished with reference block? Yes→end.  
         [0042]    Step  465 : VRP 1 =VPR 1 +4. Go to step  410 .  
         [0043]    The search locations in the above example are offset from one another by one pixel and overlap to a great degree. Another example of the present invention is extended to function using different offsets or locations by having the control circuit  300  select different accumulators  192 ,  194 ,  196 , 198 , not in a round-robin sequence, but according to a look-up table (or a programmable decoder circuit). The look-up table indicates which comparisons of bytes from the reference block and bytes from the search window belong to a specific search location and the accumulator  192 ,  194 ,  196 ,  198  representing that specific location is then selected by the control circuit  300  for updating. Additionally, the number of absolute difference calculation circuits  110  and corresponding number of accumulators  192 ,  194 ,  196 ,  198  may be altered to suit design purposes. For example, another embodiment of the present invention uses 8 absolute difference calculation circuits  110  and 8 accumulators  192 ,  194 ,  196 ,  198  and merely adjusts the indices  320 ,  330 ,  340 ,  350  accordingly. However, the embodiment disclosed in FIG. 5 comprising 4 absolute difference calculation circuits  110  and 4 accumulators  192 ,  194 ,  196 ,  198  works well with little overhead for small screened devices such as a PDA or a cellular phone.  
         [0044]    By comparing the same group of reference block bytes sequentially with the corresponding data from each search location before loading new reference data, the match values from four search locations can be calculated at the same time. Each byte of data, whether from the reference block or the search window, needs to be fetched from memory and stored in the corresponding buffer only one time for each four search locations. This present invention feature is in stark contrast with the prior art where the reference block must be reloaded into memory once for each search location and pixels in overlapping search locations may be loaded several times. Therefore, by reducing the number of memory accesses, the present invention reduces the power consumed and system load when calculating absolute difference values during image correlation.  
         [0045]    Those skilled in the art will readily observe that numerous modifications and alterations of the device and method may be made while retaining the teachings of the invention. Accordingly, the above disclosure should be construed as limited only by the metes and bounds of the appended claims.

Technology Classification (CPC): 6