Abstract:
An apparatus calculates an absolute difference value, which facilitates an efficient structure of an SAD calculating unit having a tree-like structure, and a motion estimation apparatus and a motion picture encoding apparatus that use the apparatus that calculates the absolute difference value. By performing calculations after inputting carry-outs output from a plurality of pseudo absolute difference calculating units to adders in an adder tree, the number of adders necessary for each absolute difference value calculating unit may be reduced.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
       [0001]     This application claims the priority of Korean Patent Application No. 2003-86747, filed on Dec. 2, 2003, in the Korean Intellectual Property Office, the disclosure of which is incorporated herein in its entirety by reference.  
       BACKGROUND OF THE INVENTION  
       [0002]     1. Field of the Invention  
         [0003]     The present invention relates to an apparatus that calculates an absolute difference value and a motion estimation apparatus using the apparatus to calculate the absolute difference value, and more particularly, to an apparatus that calculates an absolute difference value, which facilitates an efficient structure of an absolute difference calculating unit having a tree structure, and a motion estimation apparatus using the apparatus to calculate the absolute difference value.  
         [0004]     2. Description of the Related Art  
         [0005]     Since digital video recorders (DVR) and personal video recorders (PVR) have recently come into wide use, much research and development of image compression is being conducted. Since conventional DVRs and PVRs compress input images at a fixed resolution regardless of the characteristics of the input images, e.g., temporal complexity, the efficiency of compression is low.  
         [0006]      FIG. 1  is a block diagram of a conventional motion picture encoder. Input image data is first divided into blocks of 8×8 pixels. A discrete cosine transform (DCT) unit  110  performs DCT on the input image data that is input in units of 8×8 pixel blocks to remove spatial correlation. A quantization unit  120  performs quantization on DCT coefficients generated by the DCT unit  120  to express the DCT coefficients with several representative values, thus performing high-efficiency low-loss compression. A variable length coding (VLC) unit  130  performs entropy coding on the quantized DCT coefficients and outputs an entropy-coded data stream.  
         [0007]     An inverse quantization (IQ) unit  140  performs IQ on the image data quantized by the quantization unit  120 . An inverse DCT (IDCT) unit  150  performs IDCT on the image data that is inversely quantized by the IQ unit  140 . A frame memory unit  160  stores the image data that is inversely discrete cosine transformed by the IDCT unit  150  in frame units. A motion estimation (ME) unit  170  removes temporal correlation using image data of a current input frame and image data of a previous frame stored in the frame memory unit  160 .  
         [0008]     A core module of a block-based motion picture encoding like moving picture expert group (MPEG) 2 and MPEG 4 encoding is a motion estimator, i.e., the ME unit  170  of  FIG. 1 . The ME unit  170  performs the largest amount of computation, but also has a large number of gates due to its complexity when implemented as hardware.  
         [0009]     The most frequent calculation performed by such a motion estimator is the calculation of the sum of absolute difference (SAD) of block units. In general, when relatively large images such as MPEG 2 images are handled, a plurality of SADs are simultaneously calculated and compared during one period of a clock signal. Thus, an absolute difference calculator and an adder having a tree-like structure are essential for an SAD calculation.  
         [0010]     The encoder shown in  FIG. 1  is disclosed in U.S. Pat. No. 6,122,321.  
         [0011]      FIG. 2  illustrates a general SAD calculating unit included in the motion estimation unit  170  of  FIG. 1 , and  FIG. 3  illustrates two macroblocks (MB) composed of 16×16 pixels used in an SAD calculation by the SAD calculating unit of  FIG. 2 . In  FIG. 3 , the ith pixel of a current MB is denoted by C i  and the ith pixel of a reference MB of a search area having a motion vector with a proper size is denoted by R i .  
         [0012]     Absolute difference calculating units shown in  FIG. 2 , i.e., |DIFF 0 |, |DIFF 1 |, |DIFF 2 |, |DIFF 3 |, . . . , |DIFF 255 |, calculate the differences between absolute values of pixel values C i  of pixels of the current MB, i.e., C 0 , C 1 , C 2 , C 3 , . . . , C 255 , and pixel values R i  of pixels of the reference MB, i.e., R 0 , R 1 , R 2 , R 3 , . . . , R 255 , respectively. Here, DIFF i  denotes C i −R i .  
         [0013]     Also, the SAD calculating unit of  FIG. 2  calculates an absolute difference between two blocks for each pixel using the absolute difference calculating units and calculates an SAD corresponding to a motion vector using an adder tree. Generally, as shown in  FIG. 2 , if there are 256 absolute difference values, the SAD is calculated using an adder tree.  
         [0014]      FIG. 4  illustrates the structure of each of the absolute difference calculating units of  FIG. 2 . An absolute difference calculating unit, as shown in  FIG. 4 , is used when the SAD calculating unit has a tree-like structure as shown in  FIG. 2  instead of an accumulator structure. Referring to  FIG. 4 , each of the absolute difference calculating units includes two adders. Thus, to calculate the SAD of a 16×16 MB, the absolute difference calculating units require a total of 256×2, i.e., 512, adders.  
         [0015]     As such, since the conventional SAD calculating unit requires at least two adders in each of the absolute difference calculators, a large number of adders are needed and the load of the SAD calculating unit increases.  
       SUMMARY OF THE INVENTION  
       [0016]     The present invention provides an apparatus that calculates an absolute difference value, which facilitates an efficient structure of an SAD calculating unit by reducing a number of adders in the SAD calculating unit, and a motion estimation apparatus that performs motion estimation using the apparatus to calculate the absolute difference value.  
         [0017]     According to one aspect of the present invention, an apparatus that calculates an absolute difference value comprises a plurality of pseudo absolute difference calculating units, an adder tree comprising at least one adder to add output values of the plurality of pseudo absolute difference calculating units, each of the at least one adder receiving one of the signal determining values generated by the plurality of pseudo absolute difference calculating units as a carry-in, and an additional adder adding a final value of the adder tree and a sign determining value generated by one of the plurality of pseudo absolute difference calculating units, thus calculating an absolute difference value.  
         [0018]     According to another aspect of the present invention, an apparatus calculating an absolute difference value comprises a plurality of pseudo absolute difference calculating units calculating pseudo absolute differences and a plurality of primary adders, each receiving the pseudo absolute differences calculated by two of the pseudo absolute difference calculating units, using one of the sign determining values created by the plurality of pseudo absolute difference calculating units as a carry-in, and calculating an addition value as a sum of the two pseudo absolute differences.  
         [0019]     The apparatus that calculates an absolute difference value may further comprise a secondary adder receiving the addition values calculated by two of the primary adders, using one of the sign determining values generated by the plurality of pseudo absolute difference calculating units and unused by the primary adder, as a carry-in, and calculating an addition value as the sum of the received two addition values. The apparatus may further comprise a third adder that uses the addition value calculated by the secondary adder and one of the sign determining values generated by the plurality of pseudo absolute difference calculating units and unused by the primary adder or the secondary adder, as carry-ins and that calculates an addition value as a sum of the received addition value and the received sign determining value.  
         [0020]     Additional aspects and/or advantages of the invention will be set forth in part in the description which follows and, in part, will be obvious from the description, or may be learned by practice of the invention. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0021]     These and/or other aspects and advantages of the invention will become apparent and more readily appreciated from the following description of the embodiments, taken in conjunction with the accompanying drawings of which:  
         [0022]      FIG. 1  is a block diagram of a conventional motion picture encoder;  
         [0023]      FIG. 2  is a schematic diagram of a conventional SAD calculating unit included in a motion estimation unit  170  of  FIG. 1 ;  
         [0024]      FIG. 3  illustrates two 16×16 macroblocks that may be utilized to execute a SAD calculation;  
         [0025]      FIG. 4  is a schematic diagram of an absolute difference calculating unit included in the SAD calculating unit of  FIG. 2 ;  
         [0026]      FIG. 5  is a schematic diagram of an SAD calculating unit according to a first embodiment of the present invention;  
         [0027]      FIG. 6  is a schematic diagram of an SAD calculating unit according to a second embodiment of the present invention; and  
         [0028]      FIG. 7  is a schematic diagram of an SAD calculating unit according to a third embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0029]     Reference will now be made in detail to the embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to the like elements throughout. The embodiments are described below to explain the present invention by referring to the figures.  
         [0030]      FIG. 5  is a schematic diagram of an SAD calculating unit for 2×2 blocks, according to a first embodiment of the present invention. In the first embodiment of the present invention, an SAD calculating unit for 2×2 blocks is described for convenience of explanation. However, those skilled in the art will understand how to apply the SAD calculating unit to 16×16 blocks.  
         [0031]     The SAD calculating unit shown in  FIG. 5  includes a first difference value calculating unit  510 , a second difference value calculating unit  530 , a third difference value calculating unit  550 , a fourth difference value calculating unit  570 , a first pseudo absolute value calculating unit  520 , a second pseudo absolute value calculating unit  540 , a third pseudo absolute value calculating unit  560 , a fourth pseudo absolute value calculating unit  580 , a first adding unit  590 , a second adding unit  592 , a third adding unit  594 , and a fourth adding unit  596 .  
         [0032]     The first adding unit  590  and the second adding unit  592  are classified as primary adding units, the third adding unit  594  is classified as a secondary adding unit, and the fourth adding unit  596  is classified as a tertiary adding unit.  
         [0033]     Also, the first difference value calculating unit  510  and the first pseudo absolute value calculating unit  520  form a first pseudo absolute difference calculating unit, the second difference value calculating unit  530  and the second pseudo absolute value calculating unit  540  form a second pseudo absolute difference calculating unit, the third difference value calculating unit  550  and the third pseudo absolute value calculating unit  560  form a third pseudo absolute difference calculating unit, and the fourth difference value calculating unit  570  and the fourth pseudo absolute value calculating unit  580  form a fourth pseudo absolute difference calculating unit.  
         [0034]     The first difference value calculating unit  510  includes an exclusive OR (XOR) gate  512  and an adder  514 . A case where pixel values of current and reference blocks each have a resolution of 8 bits will now be described as an example.  
         [0035]     The XOR gate  512  receives a 0th pixel value R 0  of the reference MB shown in  FIG. 3  and a carry-in ‘1’ and generates a complement of R 0 , i.e., {overscore (R 0 )}.  
         [0036]     The adder  514  receives the complement of R 0 , i.e., {overscore (R 0 )}, generated by the XOR gate  512 , a 0th pixel value C 0  of the current MB shown in  FIG. 3 , and a carry-in ‘1’ and outputs an output value Z 0 =C 0 +{overscore (R 0 )}+1 and a carry-out C out0 =[256*(C 0 +{overscore (R 0 )}+1)/256] In other words, the carry-out C out0  is a most significant bit (MSB) among 9 bits calculated by the adder  514  and serves as a sign bit, i.e., a bit that determines the sign (plus or minus).  
         [0037]     The first difference value calculating unit  510  outputs the output value Z 0  and the carry-out C out0 .  
         [0038]     The first pseudo absolute value calculating unit  520  includes an inverter  522  and an XOR gate  524 .  
         [0039]     The inverter  522  inverts the carry-out C out0  from the first difference value calculating unit  510  into {overscore (C out0 )} and outputs {overscore (C out0 )} to the XOR gate  524  and the first adding unit  590 .  
         [0040]     The XOR gate  524  receives {overscore (C out0 )} from the inverter  522  and Z 0 =C 0 +{overscore (R 0 )}+1 from the adder  514  of the first difference value calculating unit  510  and outputs an output value O 0 =Z 0 +{overscore (C out0 )}.  
         [0041]     In this way, the first pseudo absolute value calculating unit  520  outputs {overscore (C out0 )} and O 0 .  
         [0042]     The second difference value calculating unit  530  includes an XOR gate  532  and an adder  534 . The XOR gate  532  receives a 1st pixel value R 1  of the reference MB shown in  FIG. 3  and the carry-in ‘1’ and generates a complement of R 1 , i.e., {overscore (R 1 )}.  
         [0043]     The adder  534  receives the complement of R 1 , i.e., {overscore (R 1 )} created in the XOR gate  532 , a 1st pixel value C, of the current MB shown in  FIG. 3  and the carry-in ‘1’, and outputs an output value Z 1 =C 1 +{overscore (R 1 )}+1 and a carry-out C out1 =[256*(C 1 +{overscore (R 1 )}+1)/256].  
         [0044]     In this way, the second difference value calculating unit  530  outputs the output value Z 1  and the carry-out C out1 .  
         [0045]     The second pseudo absolute value calculating unit  540  includes an inverter  542  and an XOR gate  544 . The inverter  542  inverts the carry-out C out1  from the first difference value calculating unit  530  into {overscore (C out1 )} and outputs {overscore (C out1 )} to the XOR gate  544  and the third adding unit  594 .  
         [0046]     The XOR gate  544  receives {overscore (C out1 )} from the inverter  542  and Z 1 =C 1 +{overscore (R 1 )}+1 from the adder  534  of the second difference value calculating unit  530  and outputs an output value Q 1 =Z 1 +{overscore (C out1 )}.  
         [0047]     In this way, the second pseudo absolute value calculating unit  540  outputs {overscore (C out1 )} and O 1 .  
         [0048]     The third difference value calculating unit  550  and the fourth difference value calculating unit  570  perform the same functions as the first difference value calculating unit  510  and the second difference value calculating unit  530 , and will not be described in detail.  
         [0049]     Also, the third pseudo absolute value calculating unit  560  and the fourth pseudo absolute value calculating unit  580  perform the same functions as those of the first pseudo absolute value calculating unit  520  and the second pseudo absolute value calculating unit  540 , and will not be described in detail.  
         [0050]     The third absolute value calculating unit  560  outputs an output value {overscore (C out2 )} and O 2  in the same manner as the first pseudo absolute value calculating unit  560 .  
         [0051]     Also, the fourth absolute value calculating unit  580  outputs an output value {overscore (C out3 )} and O 3  in the same manner as the first pseudo absolute value calculating unit  560 . The first adding unit  590  receives the output value O 0  from the first pseudo absolute value calculating unit  520  and the output value O 1  from the second pseudo absolute value calculating unit  540 , uses the carry-out {overscore (C out0 )} of the first pseudo absolute value calculating unit  520  as a carry-in, and calculates and outputs a primary addition value ADD1.  
         [0052]     The second adding unit  592  receives the output value O 2  from the third pseudo absolute value calculating unit  560  and the output value O 3  from the fourth pseudo absolute value calculating unit  580 , uses the carry-out {overscore (C out2 )} of the third pseudo absolute value calculating unit  560  as a carry-in, and calculates and outputs a primary addition value ADD2.  
         [0053]     The third adding unit  594  receives the primary addition values ADD1 and ADD2 output from the first adding unit  590  and the second adding unit  592 , uses the carry-out {overscore (C out1 )} of the second pseudo absolute value calculating unit  540  as a carry-in, and calculates and outputs a secondary addition value ADD3.  
         [0054]     The fourth adding unit  596  receives the secondary addition value ADD3 from the third adding unit  594  and uses the carry-out {overscore (C out3 )} of the fourth pseudo absolute value calculating unit  580  as a carry-in, and calculates and outputs a tertiary addition value.  
         [0055]     The tertiary addition value calculated by the fourth adding unit  596  is an SAD of the two 2×2 blocks.  
         [0056]     In the first embodiment shown in  FIG. 5 , the carry-outs {overscore (C out0 )}, {overscore (C out1 )}, {overscore (C out2 )}, and {overscore (C out3 )} output from the pseudo absolute value calculating units  520 ,  540 ,  560 , and  580  are carried in the adding units  590 ,  594 ,  592 , and  596 , respectively. However, the carry-outs {overscore (C out0 )}, {overscore (C out1 )}, {overscore (C out2 )}, and {overscore (C out3 )} may be respectively input to a desired adding unit.  
         [0057]      FIG. 6  is a schematic diagram of an SAD calculating unit according to a second embodiment of the present invention. The SAD calculating unit according to the second embodiment of the present invention perform the same functions as the SAD calculating unit according to the first embodiment of the present invention, except that a carry-out {overscore (C out0 )} output from a first pseudo absolute value calculating unit  620  is input to a third adding unit  694  as a carry-in, and a carry-out {overscore (C out1 )} output from a second pseudo absolute value calculating unit  640  is input to a first adding unit  690  as a carry-in. Therefore, for brevity, since other functional parts of the SAD calculating unit according to the second embodiment of the present invention correspond to the similarly numbered units of the first embodiment, the other functional parts of the second embodiment will not be described.  
         [0058]      FIG. 7  is a schematic diagram of an SAD calculating unit according to a third embodiment of the present invention. The SAD calculating unit according to the third embodiment of the present invention performs the same functions as the SAD calculating unit according to the first embodiment of the present invention, except that a carry-out {overscore (C out0 )} output from a first pseudo absolute value calculating unit  720  is input to a fourth adding unit  796  as a carry-in, a carry-out {overscore (C out1 )} output from a second pseudo absolute value calculating unit  740  is input to a first adding unit  790  as a carry-in, a carry-out {overscore (C out2 )} output from a third pseudo absolute value calculating unit  760  is input to a third adding unit  794  as a carry-in, and a carry-out {overscore (C out3 )} output from a fourth pseudo absolute value calculating unit  780  is input to a second adding unit  792  as a carry-in. Therefore, for brevity, other functional parts of the SAD calculating unit according to the third embodiment of the present invention will not be described.  
         [0059]     As such, in the SAD calculating unit according to embodiments of the present invention, each of carry-outs generated by conventional absolute value calculating units are divisively input to all the adders within an adder tree as carry-ins and used to calculate an SAD. Therefore, the number of adders in absolute difference value calculating units may be reduced.  
         [0060]     For example, when an SAD between two 2×2 blocks is calculated, as shown in  FIG. 5, 4  carry-outs are output from 4 pseudo absolute value calculating units and three of the 4 carry-outs are input to three adding units  590 ,  592 , and  594  of the adder tree. A result produced by the adder tree and the remaining carry-out are added using an adder, e.g., the fourth adding unit  596 . Thus, a final SAD may be obtained. Thus, by connecting one adder to the final adder in the adder tree, the number of adders in absolute value calculating units is reduced by half.  
         [0061]     For example, when an SAD between two 2×2 blocks is calculated as shown in  FIG. 5 , the number of adders may be reduced by 4-1 adders.  
         [0062]     In the embodiments of the present invention, calculation of an SAD between two 2×2 blocks is described for convenience of explanation. However, an SAD between two 16×16 blocks may be calculated in the same way.  
         [0063]     Also, it is possible to reduce the complexity of the hardware by applying the apparatus that calculates an absolute difference value shown in  FIG. 5  to the motion estimation unit  170  of the motion picture encoder shown in  FIG. 1  or any motion picture encoder.  
         [0064]     The present invention may also be embodied as a computer readable code on a computer readable recording medium. The computer readable recording medium may be any data storage device that stores data which can be thereafter read by a computer system. Examples of the computer readable recording medium include read-only memory (ROM), random-access memory (RAM), CD-ROMs, magnetic tapes, floppy disks, optical data storage devices, and carrier waves. The computer readable recording medium may also be distributed over network coupled computer systems so that the computer readable code is stored and executed in a distributed fashion.  
         [0065]     As described above, by calculating an SAD according to an embodiment of the present invention, the number of adders used for calculation of an SAD may be reduced, and the loads of an apparatus that calculates the SAD, a motion estimation apparatus, and a motion picture encoding apparatus may also be reduced.  
         [0066]     Although a few embodiments of the present invention have been shown and described, it would be appreciated by those skilled in the art that changes may be made in these embodiments without departing from the principles and spirit of the invention, the scope of which is defined in the claims and their equivalents.