Abstract:
Provided are a method and an apparatus for video encoding/decoding based on an orthogonal transform and vector quantization. A video encoding method includes determining whether an input image is a residual image, if the input image is a residual image, performing first encoding on the input image through transform/quantization and performing second encoding on the input image through vector quantization, comparing data obtained through the first encoding and data obtained through the second encoding, and selecting an encoding type based on the result of the comparison, generating mode information indicating the selected encoding type, and outputting data obtained according to the selected encoding type

Description:
CROSS-REFERENCE TO RELATED PATENT APPLICATION 
       [0001]    This application claims priority from Korean Patent Application No. 10-2006-0006805, filed on Jan. 23, 2006, 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]    Methods and apparatuses consistent with the present invention relate to video encoding and decoding, and more particularly, to video encoding/decoding based on an orthogonal transformation and vector quantization. 
         [0004]    2. Description of the Related Art 
         [0005]    Conventional video codec standards such as moving picture experts group (MPEG)-2, MPEG-4, H.264, and VC1 use a discrete cosine transform (DCT) for video encoding and use wavelet transforms for the encoding of still images. 
         [0006]      FIG. 1  is a block diagram of a related art video encoder such as an MPEG-2 encoder, an MPEG-4 encoder, or an H.264 encoder. 
         [0007]    Input video data is divided into a plurality of 16×16 macroblocks. 
         [0008]    An encoder control unit  110  serves as a bitrate controller to determine a quantization coefficient for each block so that a desired bitrate for the entire sequence and a target bit for each picture can be achieved. 
         [0009]    A transform/quantization unit  120  transforms the input video data to remove the spatial redundancy of the input video data. The transform/quantization unit  120  quantizes transform coefficients obtained by transform encoding using a predetermined quantization step, thereby obtaining two-dimensional N×M data composed of the quantized transform coefficients. A DCT may be used as the transform. The quantization is performed using a predetermined quantization step. 
         [0010]    An inverse quantization/inverse transform unit  130  inversely quantizes the video data that is quantized by the transform/quantization unit  120  and inversely transforms the inversely quantized video data using, for example, an inverse DCT (IDCT). 
         [0011]    A deblocking filter  140  performs filtering to remove a blocking effect occurring in a motion-compensated image due to quantization and outputs the result of the filtering to a frame memory  150 . 
         [0012]    The frame memory  150  stores the video data that is inversely quantized/inversely transformed by the inverse quantization/inverse transform unit  130  in frame units. 
         [0013]    An intraframe prediction unit  160  obtains a predictor for each block or macroblock in a spatial domain of an intra macroblock, obtains a difference between the obtained predictor and the intra macroblock, and transmits the difference to the transform/quantization unit  120 . 
         [0014]    A motion estimation/motion compensation (ME/MC) unit  170  estimates a motion vector (MV) and a sum of absolute differences (SAD) for each macroblock using input video data of a current frame and video data of a previous frame stored in the frame memory  150 . The ME/MC unit  170  also generates a motion-compensated prediction area P, e.g., a 16×16 region selected by ME, based on the estimated MV. 
         [0015]    An entropy-encoding unit  180  receives the quantized transform coefficients from the transform/quantization unit  120 , motion vector information from the ME/MC unit  170 , and information required for decoding such as coding type information and quantization step information from the encoder control unit  110 , performs entropy-encoding, and outputs a final bitstream. 
         [0016]    In other words, in the video encoder of  FIG. 1 , an addition unit  190  subtracts the motion-compensated prediction area P generated by the ME/MC unit  170  from an input current macroblock, thereby generating a residual image. The generated residual image undergoes an orthogonal transform, e.g., a DCT, and quantization through the transform/quantization unit  120 . The entropy-encoding unit  180  entropy-encodes header information such as a coefficient for each macroblock, motion information, and control data output from the transform/quantization unit  120 , thereby generating a compressed bitstream. 
         [0017]    As such, the related art video encoder uses an orthogonal transform, e.g., a DCT, to transform the video. Such a transform improves compression efficiency for an intra block, but degrades compression efficiency for a residual block in an inter block. In particular, as the H.264 encoder encodes the intra block in the same manner as it encodes the residual block through intraprediction, the efficiency of a DCT may deteriorate in some cases. 
       SUMMARY OF THE INVENTION 
       [0018]    The present invention provides a method and an apparatus for video encoding/decoding. 
         [0019]    According to one aspect of the present invention, there is provided a video encoding method. The video encoding method includes determining whether an input image is a residual image, if the input image is a residual image, performing first encoding on the input image through transform/quantization and performing second encoding on the input image through vector quantization, comparing data obtained through the first encoding and data obtained through the second encoding, and selecting an encoding type based on the result of the comparison, generating mode information indicating the selected encoding type, and outputting data obtained according to the selected encoding type. 
         [0020]    The comparison of the data may include comparing the bitrate of the data obtained through the first encoding and the bitrate of the data obtained through the second encoding. 
         [0021]    The bitrate of the data obtained through the first encoding or the second encoding may be calculated after entropy-encoding of the data. 
         [0022]    The comparison of the data may include comparing the rate of distortion of the data obtained through the first encoding and the rate of distortion of the data obtained through the second encoding. 
         [0023]    If the input image is not the residual image, only the first encoding may be performed on the input image. 
         [0024]    The video encoding method may further include performing entropy-encoding on the output data and the generated mode information. 
         [0025]    The transform may be an orthogonal transform. 
         [0026]    According to another aspect of the present invention, there is provided a video encoder including a determination unit, a first encoding unit, a second encoding unit, a comparison unit, and a mode selection unit. The determination unit determines whether an input image is a residual image. The first encoding unit performs transform/quantization on the input image. The second encoding unit performs vector quantization on the input image if the input image is a residual image. The comparison unit compares data obtained by the first encoding unit and data obtained by the second encoding unit. The mode selection unit selects an encoding type based on the result of the comparison, generates mode information indicating the selected encoding type, and outputs data obtained according to the selected encoding type. 
         [0027]    According to still another aspect of the present invention, there is provided a video decoding method. The video decoding method includes performing entropy-decoding on an input bitstream to extract video data, motion information, and mode information indicating an encoding type of an input image from the entropy-decoded bitstream, performing first decoding on the extracted video data through inverse quantization/inverse transform or second decoding on the extracted video data through inverse vector quantization based on the extracted mode information, and adding video data that is motion-compensated or intraprediction-decoded using the extracted motion information to the decoded video data, thereby generating reconstructed video data. 
         [0028]    According to yet another aspect of the present invention, there is provided a video decoder including an entropy-decoding unit, a first decoding unit, a second decoding unit, and a video reconstruction unit. The entropy-decoding unit performs entropy-decoding on an input bitstream to extract video data, motion information, and mode information indicating an encoding type of an input image from the entropy-decoded bitstream. The first decoding unit performs first decoding on the extracted video data through inverse quantization/inverse transform based on the extracted mode information. The second decoding unit performs second decoding on the extracted video data through inverse vector quantization based on the extracted mode information. The video reconstruction unit adds video data that is motion-compensated or intraprediction-decoded using the extracted motion information to the decoded video data, thereby generating reconstructed video data. 
         [0029]    According to yet another aspect of the present invention, there is provided a computer-readable recording medium having recorded thereon a program for performing a video encoding method. The video encoding method includes determining whether an input image is a residual image, if the input image is a residual image, performing first encoding on the input image through transform/quantization and performing second encoding on the input image through vector quantization, comparing data obtained through the first encoding and data obtained through the second encoding, and selecting an encoding type based on the result of the comparison, generating mode information indicating the selected encoding type, and outputting data obtained according to the selected encoding type. 
         [0030]    According to yet another aspect of the present invention, there is provided a computer-readable recording medium having recorded thereon a program for performing a video decoding method. The video decoding method includes performing entropy-decoding on an input bitstream to extract video data, motion information, and mode information indicating an encoding type of an input image from the entropy-decoded bitstream, performing first decoding on the extracted video data through inverse quantization/inverse transform or second decoding on the extracted video data through inverse vector quantization based on the extracted mode information, and adding video data that is motion-compensated or intraprediction-decoded using the extracted motion information to the decoded video data, thereby generating reconstructed video data. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0031]    The above and other aspects of the present invention will become more apparent by describing in detail exemplary embodiments thereof with reference to the attached drawings, in which: 
           [0032]      FIG. 1  is a block diagram of a related art video encoder; 
           [0033]      FIG. 2  is a block diagram of a video encoder according to an exemplary embodiment of the present invention; 
           [0034]      FIGS. 3A and 3B  are views for explaining a vector quantization mode according to an exemplary embodiment of the present invention; 
           [0035]      FIG. 4  is a flowchart illustrating a video encoding method used in the video encoder of  FIG. 2  according to an exemplary embodiment of the present invention; 
           [0036]      FIG. 5  is a block diagram of a video decoder according to an exemplary embodiment of the present invention; and 
           [0037]      FIG. 6  is a flowchart illustrating a video decoding method used in the video decoder of  FIG. 5  according to an exemplary embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS 
       [0038]    Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings. 
         [0039]      FIG. 2  is a block diagram of a video encoder according to an exemplary embodiment of the present invention. 
         [0040]    A deblocking unit  250 , a frame memory  260 , an intraprediction unit  270 , and a motion prediction unit  280  of the video encoder of  FIG. 2  function in the same way as corresponding functional units of the related art video encoder of  FIG. 1  and a description thereof will not be provided for simplicity of explanation. 
         [0041]    A residual image detection unit  210  determines whether an input image is a residual image encoded according to an interprediction mode or an intraprediction mode. The residual image according to the interprediction mode refers to a difference between a current image and a motion-compensated prediction area. 
         [0042]    If the input image is a residual image, the residual image detection unit  210  outputs the input image to a transform/quantization unit  220  and a vector quantization unit  222 . The transform/quantization unit  220  performs an orthogonal transform such as a discrete cosine transform (DCT). 
         [0043]    If the input image is not a residual image, for example, if it is the original image, the residual image detection unit  210  outputs the input image to the transform/quantization unit  220 . 
         [0044]    If there is an output from the vector quantization unit  222 , a mode selection unit  230  calculates the number of bits of the residual image that has been vector-quantized by the vector quantization unit  222  and the number of bits of the residual image that has been transformed/quantized by the transform/quantization unit  220 . The mode selection unit  230  selects one of a vector quantization mode, i.e., the vector-quantized residual image, and a transform/quantization mode, i.e., the transformed/quantized residual image, based on the calculated numbers of bits, and outputs the selected residual image and corresponding mode information to an entropy-encoding unit  290 . The mode selection unit  230  also outputs the selected residual image to one of an inverse quantization/inverse transform unit  240  and an inverse vector quantization unit  242 . The mode selection unit  230  may also entropy-encode the transformed/quantized residual image and the vector quantized residual image, compare the numbers of bits of the entropy-encoded residual images, and select a mode having the smaller number of bits. 
         [0045]    The mode selection unit  230  may also calculate the rate-distortion cost of the transformed/quantized residual image and the rate-distortion cost of the vector quantized residual image and select a mode having the smaller rate-distortion cost. The rate-distortion cost may be obtained by comparing the result of inverse quantization/inverse transform of the transformed/quantized residual image or the result of inverse vector quantization of the vector quantized residual image with the original residual image. 
         [0046]    For example, when the transform/quantization mode is selected, the mode selection unit  230  outputs quantized coefficients and the output quantized coefficients undergo zigzag scanning and then entropy-encoding through the entropy-encoding unit  290 . The mode information indicating the transform/quantization mode is also output to the entropy-encoding unit  290  and undergoes entropy-encoding. 
         [0047]    When the vector quantization mode is selected, the mode selection unit  230  outputs index information of a codebook having an image pattern that is most similar to the pattern of the input image and the output index information is entropy-encoded. 
         [0048]      FIGS. 3A and 3B  are views for explaining the vector quantization mode according to an exemplary embodiment of the present invention.  FIG. 3A  illustrates a pixel block of the input image and  FIG. 3B  illustrates a group of codebooks having representative image patterns. 
         [0049]    During vector quantization, the original pixel block, i.e., the pixel block of  FIG. 3A , is mapped to a codebook having the most similar image pattern. In  FIGS. 3A and 3B , a codebook # 2  having the most similar image pattern to the input pixel block is selected and an index ‘2’ indicating the codebook # 2  is transmitted. 
         [0050]    Although the residual image detection unit  210  determines the type of input image and determines whether to perform vector quantization according to the result of determination in the current exemplary embodiment of the present invention, vector quantization may also be performed on all input images. 
         [0051]    Moreover, only when the residual image detection unit  210  determines that the input image is a residual image, the mode selection unit  230  can compare the outputs of the transform/quantization unit  220  and the vector quantization unit  222  for selection. 
         [0052]    The mode selection unit  230  outputs video data to the inverse quantization/inverse transform unit  240  or the inverse vector quantization unit  242  according to the selected mode. 
         [0053]    Data reconstructed by the inverse quantization/inverse transform unit  240  and the inverse vector quantization unit  242  is stored in the frame memory  260 . 
         [0054]    As such, in the current exemplary embodiment of the present invention, during video encoding for removing spatial redundancy, if the input image is a residual image, transform/quantization and vector quantization are adaptively used, thereby improving encoding efficiency. 
         [0055]    Although the transform/quantization unit  220  uses an orthogonal transform such as a DCT for video transform in the current exemplary embodiment of the present invention, it may also use another orthogonal transform such as integer transform. Tree-based vector quantization, classified vector quantization, or predictive vector quantization may be used for vector quantization. 
         [0056]      FIG. 4  is a flowchart illustrating a video encoding method used in the video encoder of  FIG. 2  according to an exemplary embodiment of the present invention. 
         [0057]    In operation  410 , it is determined whether an input image is a residual image according to an interprediction mode or an intraprediction mode. 
         [0058]    In operation  420 , if the input image is a residual image, transform/quantization and vector quantization are performed on the input image. 
         [0059]    In operation  430 , if the input image is not a residual image, for example, is the original image, transform/quantization is performed on the input image. 
         [0060]    In operation  440 , the number of bits of the transformed/quantized residual image obtained in operation  420  and the number of bits of the vector quantized residual image obtained in operation  420  are calculated and the calculated numbers of bits are compared to select one of a vector quantization mode and a transform/quantization mode. 
         [0061]    In operation  450 , mode information indicating the selected mode obtained in operation  440  is generated. 
         [0062]    In operation  460 , entropy-encoding is performed on the generated mode information obtained in operation  450  and on the transformed/quantized video data or the vector quantized video data corresponding thereto, or entropy-encoding is performed on the transformed/quantized video data obtained in operation  430 . 
         [0063]      FIG. 5  is a block diagram of a video decoder according to an exemplary embodiment of the present invention. 
         [0064]    Referring to  FIG. 5 , the video decoder includes an entropy decoding unit  510 , a mode selection unit  520 , an inverse quantization/inverse transform unit  530 , an inverse vector quantization unit  540 , a frame memory  550 , and an MC unit  560 . 
         [0065]    The entropy decoding unit  510  entropy-decodes an input encoded bitstream to extract video data, motion vector information, and mode information indicating whether the video data is transformed/quantized data or vector quantized data. The extracted video data and mode information are input to the mode selection unit  520  and the extracted motion vector information is input to the MC unit  560 . 
         [0066]    The mode selection unit  520  outputs the input video data to the inverse quantization/inverse transform unit  530  or the inverse vector quantization unit  540  according to the input mode information. 
         [0067]    For example, if the input mode information indicates that the input video data is vector quantized data, the input video data undergoes inverse vector quantization through the inverse vector quantization unit  540 . A predictor, e.g., a motion-compensated prediction area obtained by the MC unit  560 , is added to the inverse vector quantized video data, thereby generating reconstructed video data. The reconstructed video data is output to a display unit (not shown). 
         [0068]    If the input mode information indicates that the input video data is transformed/quantized data, the input video data undergoes inverse quantization/inverse transform through the inverse quantization/inverse transform unit  530 . A predictor, e.g., a motion-compensated prediction area obtained by the MC unit  560 , is added to the inversely quantized/inversely transformed video data, thereby generating reconstructed video data. The reconstructed video data is output to a display unit (not shown). 
         [0069]      FIG. 6  is a flowchart illustrating a video decoding method used in the video decoder of  FIG. 5  according to an exemplary embodiment of the present invention. 
         [0070]    In operation  620 , an input encoded bitstream is entropy decoded to extract video data, motion vector information, and mode information indicating whether the video data is transformed/quantized data or vector quantized data. 
         [0071]    In operation  640 , inverse quantization/inverse transform or inverse vector quantization is performed on the extracted video data according to the extracted mode information. 
         [0072]    In operation  660 , a predictor e.g., a motion-compensated prediction area obtained by the MC unit  560 , is added to the inversely quantized/inversely transformed video data or the inverse vector quantized video data, thereby generating reconstructed video data. 
         [0073]    As described above, according to exemplary embodiments of the present invention, during video encoding for removing spatial redundancy, if an input image is a residual image, encoding efficiency can be improved. 
         [0074]    Meanwhile, the present invention can also be embodied as computer-readable code on a computer-readable recording medium. The computer-readable recording medium is any data storage device that can store 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 (e.g., transmission over the Internet). The computer-readable recording medium can also be distributed over network coupled computer systems so that the computer-readable code is stored and executed in a distributed fashion. 
         [0075]    While the present invention has been particularly shown and described with reference to the exemplary embodiments thereof, it will be understood by those of ordinary skill in the art that various changes in form and details may be made therein without departing from the spirit and scope of the present invention as defined by the following claims.