Video encoding method and device and decoding method and device

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
0
Assignments
First Claim
1. A video decoding apparatus comprising a processor configured to:
 receive a quantized transform block which has a predetermined size,determine a scaling constant for scaling of transform coefficients included in the quantized transform block based on a quantization parameter,scale the transform coefficients by using the scaling constant, andinversetransform the transform block that includes the scaled transform coefficients,wherein, where i denotes a remainder after the quantization parameter is divided by 6, the scaling constant for i=0 is 40, the scaling constant for i=1 is 45, the scaling constant for i=2 is 51, the scaling constant for i=3 is 57, the scaling constant for i=4 is 64, and the scaling constant for i=5 is 72, andthe transform block is inversetransformed by using discrete cosine inversetransform.
0 Assignments
0 Petitions
Accused Products
Abstract
A video encoding method, a video encoding apparatus, a video decoding method, and a video decoding apparatus are provided. The video encoding method includes producing a fast transform matrix based on a transform matrix which is used for frequency transformation on a block which has a predetermined size; producing a transformed block by transforming the block having the predetermined size by using the fast transform matrix; and performing scaling with respect to the transformed block in order to correct a difference between the transform matrix used for the frequency transformation and the fast transform matrix.
31 Citations
No References
Block transform and quantization for image and video coding  
Patent #
US 7,881,371 B2
Filed 02/25/2005

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Corporation

Method and apparatus for resizing images using discrete cosine transform  
Patent #
US 7,876,976 B2
Filed 02/23/2007

Current Assignee
Seoul National University Industry Foundation, Samsung Electronics Co. Ltd.

Sponsoring Entity
Seoul National University Industry Foundation, Samsung Electronics Co. Ltd.

Apparatus for and method of transcoding data  
Patent #
US 8,059,716 B2
Filed 09/11/2006

Current Assignee
Seoul National University Industry Foundation, Samsung Electronics Co. Ltd.

Sponsoring Entity
Seoul National University Industry Foundation, Samsung Electronics Co. Ltd.

Multimedia signal processing using fixedpoint approximations of linear transforms  
Patent #
US 7,689,052 B2
Filed 06/09/2006

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Corporation

Low power, high performance transform coprocessor for video compression  
Patent #
US 7,756,351 B2
Filed 10/28/2004

Current Assignee
STMicroelectronics Incorporated

Sponsoring Entity
STMicroelectronics Incorporated

Block transform and quantization for image and video coding  
Patent #
US 7,839,928 B2
Filed 04/12/2005

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Corporation

Fast video codec transform implementations  
Patent #
US 7,487,193 B2
Filed 05/14/2004

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Corporation

Processing of performance sensitive transforms  
Patent #
US 7,558,815 B2
Filed 01/24/2005

Current Assignee
Ricoh Company Limited

Sponsoring Entity
Infoprint Solutions Company LLC

CMOS image sensor and method of fabricating the same  
Patent #
US 20070023764A1
Filed 07/24/2006

Current Assignee
Magnachip Semiconductor Limited

Sponsoring Entity
Magnachip Semiconductor Limited

Apparatus for and method of transcoding data  
Patent #
US 20070058720A1
Filed 09/11/2006

Current Assignee
Seoul National University Industry Foundation, Samsung Electronics Co. Ltd.

Sponsoring Entity
Seoul National University Industry Foundation, Samsung Electronics Co. Ltd.

2D transforms for image and video coding  
Patent #
US 7,242,713 B2
Filed 02/28/2003

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Corporation

Fast multiplierless integer invertible transforms  
Patent #
US 20070196025A1
Filed 01/04/2007

Current Assignee
FastVDO LLC

Sponsoring Entity
FastVDO LLC

Method and apparatus for resizing images using discrete cosine transform  
Patent #
US 20070237414A1
Filed 02/23/2007

Current Assignee
Seoul National University Industry Foundation, Samsung Electronics Co. Ltd.

Sponsoring Entity
Seoul National University Industry Foundation, Samsung Electronics Co. Ltd.

METHOD AND CIRCUIT FOR PERFORMING CORDIC BASED LOEFFLER DISCRETE COSINE TRANSFORMATION (DCT) FOR SIGNAL PROCESSING  
Patent #
US 20070250557A1
Filed 04/24/2007

Current Assignee
National Taiwan University of Science and Technology, UniversitT Dortmund

Sponsoring Entity
National Taiwan University of Science and Technology, UniversitT Dortmund

Estimating sampledomain distortion in the transform domain with rounding compensation  
Patent #
US 20070237236A1
Filed 04/07/2006

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Corporation

REDUCTION OF ERRORS DURING COMPUTATION OF INVERSE DISCRETE COSINE TRANSFORM  
Patent #
US 20070297504A1
Filed 06/22/2007

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Method for image compression implementing fast twodimensional discrete cosine transform  
Patent #
US 5,642,438 A
Filed 03/17/1995

Current Assignee
XVD Technology Holdings Ltd.

Sponsoring Entity
ALARIS INC., GT Technologies

Scaled forward and inverse discrete cosine transform and video compression/decompression systems employing the same  
Patent #
US 6,694,342 B1
Filed 10/16/2000

Current Assignee
Sun Microsystems Incorporated

Sponsoring Entity
Sun Microsystems Incorporated

Scaled forward and inverse discrete cosine transform and video compression/decompression systems employing the same  
Patent #
US 6,134,270 A
Filed 06/13/1997

Current Assignee
Oracle America Inc.

Sponsoring Entity
Sun Microsystems Incorporated

Compensating for errors in performance sensitive transformations  
Patent #
US 20060080373A1
Filed 10/07/2004

Current Assignee
Ricoh Company Limited

Sponsoring Entity
Infoprint Solutions Company LLC

Implementation of a transform and of a subsequent quantization  
Patent #
US 20060294173A1
Filed 01/27/2006

Current Assignee
Antti Hallapuro, Kim Simelius

Sponsoring Entity
Antti Hallapuro, Kim Simelius

Efficient scaling in transform domain  
Patent #
US 20050069224A1
Filed 09/30/2003

Current Assignee
International Business Machines Corporation

Sponsoring Entity
International Business Machines Corporation

Fast DCT method and apparatus for digital video compression  
Patent #
US 20050074062A1
Filed 10/06/2003

Current Assignee
Taiwan Imaging Tek Corporation

Sponsoring Entity
Taiwan Imaging Tek Corporation

Fast video codec transform implementations  
Patent #
US 20050256916A1
Filed 05/14/2004

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Corporation

Implementation of a transform and of a subsequent quantization  
Patent #
US 20030078953A1
Filed 08/30/2001

Current Assignee
Nokia Technologies Oy

Sponsoring Entity
Nokia Corporation

Video block transform  
Patent #
US 20030093452A1
Filed 08/22/2002

Current Assignee
Texas Instruments Inc.

Sponsoring Entity
Texas Instruments Inc.

2D transforms for image and video coding  
Patent #
US 20030206582A1
Filed 02/28/2003

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Corporation

VIDEO DECODER WITH REDUCED DYNAMIC RANGE TRANSFORM WITH QUANTIZATION MATRICIES  
Patent #
US 20120230395A1
Filed 03/11/2011

Current Assignee
Sharp Electronics Corporation

Sponsoring Entity
Sharp Electronics Corporation

Mechanism for processing order16 discrete cosine transforms  
Patent #
US 8,417,045 B2
Filed 07/29/2010

Current Assignee
Ricoh Company Limited

Sponsoring Entity
Infoprint Solutions Company LLC

Fast multiplierless integer invertible transforms  
Patent #
US 8,548,265 B2
Filed 01/04/2007

Current Assignee
FastVDO LLC

Sponsoring Entity
FastVDO LLC

Transform design with scaled and nonscaled interfaces  
Patent #
US 8,849,884 B2
Filed 03/26/2007

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

9 Claims
 1. A video decoding apparatus comprising a processor configured to:
receive a quantized transform block which has a predetermined size, determine a scaling constant for scaling of transform coefficients included in the quantized transform block based on a quantization parameter, scale the transform coefficients by using the scaling constant, and inversetransform the transform block that includes the scaled transform coefficients, wherein, where i denotes a remainder after the quantization parameter is divided by 6, the scaling constant for i=0 is 40, the scaling constant for i=1 is 45, the scaling constant for i=2 is 51, the scaling constant for i=3 is 57, the scaling constant for i=4 is 64, and the scaling constant for i=5 is 72, and the transform block is inversetransformed by using discrete cosine inversetransform.
 2. A video encoding apparatus comprising a processor configured to:
obtain a transform block by transforming a residual block indicating differences between a current block and a predicted block of the current block, determine a scaling constant for quantization of transform coefficients included in the transform block based on a quantization parameter, quantize the transform coefficients in the transform block based on the scaling constant, entropycode the quantized transform block, and output a bitstream including quantized transform block information indicating the quantized transform block, wherein, where i denotes a remainder after the quantization parameter is divided by 6, the scaling constant for i=0 is 40, the scaling constant for i=1 is 45, the scaling constant for i=2 is 51, the scaling constant for i=3 is 57, the scaling constant for i=4 is 64, and the scaling constant for i=5 is 72.
 3. A video encoding method comprising:
obtaining a transform block by transforming a residual block indicating differences between a current block and a predicted block of the current block; determining a scaling constant for quantization of transform coefficients included in the transform block based on a quantization parameter; quantizing the transform coefficients in the transform block based on the scaling constant; entropycoding the quantized transform block; and output a bitstream including quantized transform block information indicating the quantized transform block, wherein, where i denotes a remainder after the quantization parameter is divided by 6, the scaling constant for i=0 is 40, the scaling constant for i=1 is 45, the scaling constant for i=2 is 51, the scaling constant for i=3 is 57, the scaling constant for i=4 is 64, and the scaling constant for i=5 is 72, and the transform block is transformed by using discrete cosine transform.
 4. A video encoding apparatus comprising a processor configured to:
obtain a transform block by transforming a residual block indicating differences between a current block and a predicted block of the current block, determine a scaling constant for quantization of transform coefficients included in the transform block based on a quantization parameter, quantize the transform coefficients in the transform block based on the scaling constant, entropycode the quantized transform block, and output a bitstream including quantized transform block information indicating the quantized transform block, wherein, where i denotes a remainder after the quantization parameter is divided by 6, the scaling constant for i=0 is 40, the scaling constant for i=1 is 45, the scaling constant for i=2 is 51, the scaling constant for i=3 is 57, the scaling constant for i=4 is 64, and the scaling constant for i=5 is 72, and the transform block is transformed by using discrete cosine transform.
 5. A video encoding method comprising:
obtaining a transform block by transforming a residual block indicating differences between a current block and a predicted block of the current block; determining a scaling constant for quantization of transform coefficients included in the transform block based on a quantization parameter; quantizing the transform coefficients in the transform block based on the scaling constant; entropycoding the quantized transform block; and output a bitstream including quantized transform block information indicating the quantized transform block, wherein, where i denotes a remainder after the quantization parameter is divided by 6, the scaling constant for i=0 is 40, the scaling constant for i=1 is 45, the scaling constant for i=2 is 51, the scaling constant for i=3 is 57, the scaling constant for i=4 is 64, and the scaling constant for i=5 is 72, and a transform matrix includes elements that are integers.
 6. A nontransitory computerreadable recording medium comprising a bitstream, the bitstream comprising:
quantized transform block information indicating a quantized transform block of a current block; quantization parameter information indicating a quantization parameter; and prediction mode information indicating a prediction mode of the current block, wherein, the quantized transform block is derived by entropydecoding the quantized transform block information, transform coefficients in the quantized transform block are scaled by using a scaling constant that is determined based on the quantization parameter, a transform block that includes the scaled transform coefficients is inversetransformed to obtain a residual block indicating differences between the current block and a predicted block of the current block, the predicted block of the current block is determined based on the prediction mode of the current block, wherein, where i denotes a remainder after the quantization parameter is divided by 6, the scaling constant for i=0 is 40, the scaling constant for i=1 is 45, the scaling constant for i=2 is 51, the scaling constant for i=3 is 57, the scaling constant for i=4 is 64, and the scaling constant for i=5 is 72, and the transform block is transformed by using discrete cosine transform.
 7. A nontransitory computerreadable recording medium comprising a bitstream, the bitstream comprising:
quantized transform block information indicating a quantized transform block of a current block; quantization parameter information indicating a quantization parameter; and prediction mode information indicating a prediction mode of the current block, wherein, the quantized transform block is derived by entropydecoding the quantized transform block information, transform coefficients in the quantized transform block are scaled by using a scaling constant that is determined based on the quantization parameter, a transform block that includes the scaled transform coefficients is inversetransformed to obtain a residual block indicating differences between the current block and a predicted block of the current block, the predicted block of the current block is determined based on the prediction mode of the current block, wherein, where i denotes a remainder after the quantization parameter is divided by 6, the scaling constant for i=0 is 40, the scaling constant for i=1 is 45, the scaling constant for i=2 is 51, the scaling constant for i=3 is 57, the scaling constant for i=4 is 64, and the scaling constant for i=5 is 72, and the transform matrix includes elements that are integers.
 8. A nontransitory computerreadable recording medium comprising a bitstream, the bitstream comprising:
quantized transform block information indicating a quantized transform block of a current block; quantization parameter information indicating a quantization parameter; and prediction mode information indicating a prediction mode of the current block, wherein, the quantized transform block is derived by entropydecoding the quantized transform block information, transform coefficients in the quantized transform block are scaled by using a scaling constant that is determined based on the quantization parameter, a transform block that includes the scaled transform coefficients is inversetransformed to obtain a residual block indicating differences between the current block and a predicted block of the current block, the predicted block of the current block is determined based on the prediction mode of the current block, wherein, where i denotes a remainder after the quantization parameter is divided by 6, the scaling constant for i=0 is 40, the scaling constant for i=1 is 45, the scaling constant for i=2 is 51, the scaling constant for i=3 is 57, the scaling constant for i=4 is 64, and the scaling constant for i=5 is 72, the transform block is transformed by using discrete cosine transform and includes elements that are integers.
 9. A nontransitory computerreadable recording medium comprising a bitstream, the bitstream comprising:
quantized transform block information indicating a quantized transform block of a current block; quantization parameter information indicating a quantization parameter; and prediction mode information indicating a prediction mode of the current block, wherein, the quantized transform block is derived by entropydecoding the quantized transform block information, transform coefficients in the quantized transform block are scaled by using a scaling constant that is determined based on the quantization parameter, a transform block that includes the scaled transform coefficients is inversetransformed to obtain a residual block indicating differences between the current block and a predicted block of the current block, the predicted block of the current block is determined based on the prediction mode of the current block, wherein, where i denotes a remainder after the quantization parameter is divided by 6, the scaling constant for i=0 is 40, the scaling constant for i=1 is 45, the scaling constant for i=2 is 51, the scaling constant for i=3 is 57, the scaling constant for i=4 is 64, and the scaling constant for i=5 is 72, the transform block is transformed by using discrete cosine transform and includes elements that are integers, the prediction information indicates an intra mode or an inter mode.
1 Specification
This is a continuation of U.S. application Ser. No. 15/700,668, filed Sep. 11, 2017, which is a continuation of U.S. application Ser. No. 15/149,931, filed May 9, 2016, now U.S. Pat. No. 9,788,013 issued Oct. 10, 2017, which is a continuation of application Ser. No. 13/876,778, filed Mar. 28, 2013, now U.S. Pat. No. 9,350,997 issued May 24, 2016, which is a national stage entry of International Patent Application No. PCT/KR2011/007165, filed on Sep. 28, 2011, and claims the benefit of U.S. Provisional Patent Application No. 61/387,128, filed on Sep. 28, 2010 in the U.S. Patent and Trademark Office, the disclosures of which are incorporated herein by reference in their entireties.
Exemplary embodiments relate to a video encoding method, a video encoding apparatus, a video decoding method, and a video decoding apparatus, and more particularly, to a method and apparatus for transforming a largesized block, and a method and apparatus for inversely transforming a largesized transformed block.
According to a current international video coding standard, such as H.264 or MPEG4, a video signal is hierarchically divided into a sequence, a frame, a slice, a macroblock, and a block, wherein the block is a minimum processing unit. With respect to encoding, a prediction remaining error of the block is determined via intraframe or interframe prediction, block transformation is performed such that energy is focused on a coefficient of a decimal, and image data is compressed and recorded as a coded bitstream via quantization, scanning, runlength coding, and entropy coding. With respect to decoding, processes are performed in the opposite order. First, a block transformation coefficient of entropy coding is extracted from a bitstream. Then, a prediction remaining error of a block is reconstructed via inversequantization and inversetransformation, and prediction information is used to reconstruct video data of the block. In an encodingdecoding process, a transformation module is a base of video compression, and transformation performance of the transformation module directly affects the general performance of a codec.
Discrete cosine transform (DCT) has been employed in conjunction with an initial video coding standard, such as MPEG1 or H.261. After DCT was introduced in 1974, DCT has been widely used in image and video coding fields. Transformation performance of DCT is excellent compared to all suboptimal transforms, because DCT removes a correlation of image elements in a transformation domain and prepares a base for highlyefficient image compression. However, because a DCT matrix is expressed using floating point numbers, many system resources are used due to massive floating point operations. Accordingly, a new DCT algorithm is required so as to improve transformation efficiency while performing transformation on a largesize block.
One or more exemplary embodiments provide a video encoding method, a video encoding apparatus, a video decoding method, and a video decoding apparatus that enable fast frequency transformation with respect to a largesized block. One or more exemplary embodiments also provide a video encoding method, a video encoding apparatus, a video decoding method, and a video decoding apparatus, in which transform errors that may be generated when using fast frequency transformation may be compensated for via scaling or descaling performed in a quantization or dequantization process.
According to an exemplary embodiment, an error in a result of inverse DCT (IDCT) which is obtained using a fast transformation matrix is reduced by performing scaling with respect to a transformed block.
In image transformation and image inversetransformation according to one or more exemplary embodiments, an operation based on an integer instead of a floating point operation is performed when a large block is transformed and inversely transformed, so that calculation complexity is reduced and an operation speed is increased.
In addition, an error value as between performance of a transformation based on a floating point operation and performance of a fast transformation may be compensated for by performing scaling and descaling during the quantization or the dequantization.
The above and other features and advantages of the present inventive concept will become more apparent by describing in detail exemplary embodiments thereof with reference to the attached drawings in which:
According to an aspect of one or more exemplary embodiments, there is provided a video encoding method comprising: producing a fast transform matrix based on a first transform matrix which is used for performing a frequency transformation on a block which has a predetermined size; producing a transformed block by transforming the block which has the predetermined size by using the fast transform matrix; and performing scaling with respect to the transformed block in order to correct a difference between the first transform matrix and the fast transform matrix.
According to an aspect of one or more exemplary embodiments, there is provided a video encoding apparatus, including: a transformer which produces a fast transform matrix based on a first transform matrix which is used for performing a frequency transformation on a block which has a predetermined size and produces a transformed block by transforming the block which has the predetermined size by using the fast transform matrix; and a quantizer which performs scaling with respect to the transformed block in order to correct a difference between the first transform matrix and the fast transform matrix.
According to an aspect of one or more exemplary embodiments, there is provided a video decoding method comprising: receiving a quantized transformed block which has a predetermined size; performing descaling with respect to the quantized transformed block in order to correct a difference between a first inversetransform matrix which is used for performing a frequency inversetransformation on the quantized transformed block and a fast inversetransform matrix which is produced based on the first inversetransform matrix; and producing an inverselytransformed block by inversely transforming a descaled transformed block which is obtained by the descaling by using the fast inversetransform matrix.
According to an aspect of one or more exemplary embodiments, there is provided a video decoding apparatus, including: a dequantizer which performs descaling with respect to a quantized transformed block in order to correct a difference between a first inversetransform matrix which is used for performing a frequency inversetransformation on the quantized transformed block and a fast inversetransform matrix which is produced based on the first inversetransform matrix; and an inversetransformer which produces an inverselytransformed block by inversely transforming a descaled transformed block which is obtained by the descaling by using the fast inversetransform matrix.
Hereinafter, exemplary embodiments will be described more fully with reference to the accompanying drawings.
Referring to
The predictor 110 divides an input image into blocks, each of which has a respective predetermined size, and generates a prediction block by performing inter prediction or intra prediction on each block. In detail, the predictor 110 performs inter prediction for generating a prediction block by using at least one of a motion prediction process and a compensation process, which processes generate a motion vector which indicates a region which is similar to a current block within a predetermined search range of a reference picture that has previously been encoded and then restored, and intra prediction for generating a prediction block by using data of an adjacent block that is adjacent to a current block.
The subtracter 115 generates a residual by subtracting the prediction block of the current block from original image data.
The transformer 120 transforms the residual to a frequency domain. Specifically, in exemplary embodiments, a discrete cosine transform (DCT) matrix which is defined with respect to an existing block having a relatively small size, such as a 4×4 block or an 8×8 block, may be enlarged and may be applied to a block having a size of at least 16×16. As is described below, the transformer 120 performs a DCT according to additions and subtractions based on an integer and a shift operation, instead of using a floating point operation, by substituting elements of a transformation matrix which is used for an existing DCT with rational numbers, thereby reducing a calculation complexity while increasing an operation speed. According to another exemplary embodiment, the transformer 120 may perform a DCT by using a fast transformation matrix which includes elements that are obtained by multiplying the elements of a transformation matrix used for performing DCT by a power of 2 and then rounding up each of the multiplied elements to a respective nearest integer, thereby reducing overall calculation complexity.
The quantizer 130 quantizes the transformed residual. In particular, the quantizer 130 performs predetermined scaling so as to reduce an error value as between a result of the transformation performed using the fast transform matrix by the transformer 120 and a result of a transformation performed using a DCT matrix based on an actual floating point operation. Scaling and quantization will be described in detail below.
The entropy encoder 140 generates a bitstream by performing variable length encoding on quantized image data.
The transformation performed in the transformer 120 of
The transformer 120 performs a columnwise transform and a rowwise transform with respect to an N×N (where N denotes an integer) input block in order to produce an N×N transformed block. When the N×N input block is referred to as Input, a rowwise DCT matrix is referred to as Transform_hor, a columnwise DCT matrix is referred to as Transform_ver, and a transform result value is referred to as Output, the transformer 120 performs a matrix operation as expressed in the following Equation: Output=Transform_hor×Input×Transform_ver, and then the transformer 120 outputs the transform result value Output. In the matrix operation, a first matrix multiplication Transform_hor×Input corresponds to an execution of a onedimensional (1D) horizontal DCT with respect to each row of the N×N input block Input, and a multiplication of Transform_hor×Input by Transform_ver corresponds to an execution of a 1D vertical DCT with respect to each column of the N×N input block Input. The rowwise DCT matrix Transform_hor is the transpose of the columnwise DCT matrix Transform_ver. Although the below description is focused on an N×N transform matrix and an N×N inversetransform matrix that respectively perform frequency transformation and frequency inversetransformation with respect to the N×N input block, one or more exemplary embodiments may also be applied to the cases of using an a×b (where a and b denote integers) frequency transform matrix and an a×b frequency inversetransform matrix.
When an element located at a (i,k) (where i and k are integers) position of a vertical transform matrix is referred to as Aik, the (i,k)th element Aik of the vertical transform matrix for transformation with respect to an N×N input block may be defined as in Equation 1:
Because a horizontal transform matrix is the transpose of the corresponding vertical transform matrix, an (i,k)th element Bik of the corresponding horizontal transform matrix is expressible as a value which may be obtained by using a cosine function, similarly as with the vertical transform matrix. The transformer 120 may perform a DCT based on additions, subtractions, and a shift operation by using a fast transform matrix which is produced by substituting elements of a transformation matrix which is used for DCT with rational numbers. According to another exemplary embodiment, the transformer 120 may perform a DCT by using a fast transformation matrix which is formed of elements that are obtained by multiplying the elements of the transformation matrix used for DCT by a power of 2 and then rounding up each of the multiplied elements to a respective nearest integer.
Referring to
As shown in the flow graph 200, cθ and sθ may become irrational numbers based on a corresponding value of θ in the DCT, and thus calculation complexity may increase. Such a process of the DCT may increase complexity when realized using hardware. Accordingly, according to an exemplary embodiment, the transformer 120 produces a fast transform matrix which is similar to the original DCT matrix by substituting trigonometrical function values of each of the elements used for performing the DCT with rational numbers. According to another exemplary embodiment, the transformer 120 produces a fast transform matrix by multiplying each of the elements used for performing DCT by a predetermined constant, for example, 2^{n}, and rounding up each of the multiplied elements to a respective nearest integer.
In detail, referring to
As described above, because cos θ and sin θ may be irrational numbers based on a value of θ, the transformer 120 substitutes cos θ and sin θ which are included in the elements of the transform matrix Original_A with rational numbers. For example, when N=16, the transformer 120 substitutes cos 0 with a0, cos(π×(1/2)/16) with a1, cos(π×(2/2)/16) with a2, cos(π×(3/2)/16) with a3, cos(π×(4/2)/16) with a4, cos(π×(5/2)/16) with a5, cos(π×(6/2)/16) with a6, cos(π×(7/2)/16) with a7, cos(π×(8/2)/16) with a8, cos(π×(9/2)/16) with a9, cos(π×(10/2)/16) with a10, cos(π×(11/2)/16) with a1, cos(π×(12/2)/16) with a12, cos(π×(13/2)/16) with a13, cos(π×(14/2)/16) with a14, and cos(π×(15/2)/16) with a15. Similarly, sin θ may be substituted with variables ai by using a relationship such as sin θ=cos(90−θ). The variables ai may be rational numbers, and a denominator of each variable ai may have a value which is equal to a power of 2 and which is capable of a shift operation. The variable ai is limited to a dyadic rational, because if the denominator is equal to a power of 2, a division operation or the like which is necessary for transformation may be substituted with a right shift operation (»).
For example, when N is equal to 16, 16 variables ai may have the following values: a1=63/64, a2=62/64, a3=61/64, a4=59/64, a5=56/64, a6=53/64, a7=49/64, a8=45/64, a9=40/64, a10=35/64, a11=30/64, a12=24/64, a13=18/64, a14=12/64, and a15=6/64.
If N is equal to 16, a 1D DCT which is performed with respect to the 16×16 input block by using a substituted 16×16 transform matrix A may be expressed as the following operation, wherein Xi (where i denotes an integer within the range of 0 to 15) denotes an input value to be transformed, Bi, Ci, Di, Ei, and Fi denote intermediate values, and Yi denotes a transform result value:
As another example, if N is equal to 32, similarly as when N is equal to 16, a fast transform matrix A may be produced by substituting the elements constituting a 32×32 transform matrix Original_A for use in 1D DCT with respect to a 32×32 block with values based on 32 variables ai (where i denotes an integer within the range of 0 to 31). Referring back to
When N is equal to 32, 32 variables ai may have the following values; a1=255/256, a2=254/256, a3=253/256, a4=251/256, a5=248/256, a6=244/256, a7=241/256, a8=236/256, a9=231/256, a10=225/256, a11=219/256, a12=212/256, a13=205/256, a14=197/256, a15=189/256, a16=181/256, a17=171/256, a18=162/256, a19=152/256, a20=142/256, a21=131/256, a22=120/256, a23=109/256, a24=97/256, a25=86/256, a26=74/256, a27=62/256, a28=49/256, a29=37/256, a30=25/256, and a31=12/256.
When N is equal to 32, a 1D DCT which is performed on a 32×32 input block by using the fast transform matrix A may be expressed as the following operation, wherein Xi (where i denotes an integer in the range of 0 to 31) denotes an input value to be transformed, Ai, Bi, Ci, Di, Ei, and Fi denote intermediate values, and Yi denotes a transform result value:
As described above, according to another exemplary embodiment, the transformer 120 produces a fast transform matrix by multiplying each of elements used for performing a DCT by 2^{n }and rounding up each of the multiplied elements to a respective nearest integer. In detail, the fast transform matrix A is produced by transforming the values of the elements of the DCT matrix Original_A based on the following equation: A=round(Original_A*2^{n}), representing an operation of multiplying the transform matrix Original_A for use in a 1D DCT by 2^{n }(where n is an integer) and then rounding up each element of the multiplied transform matrix Original_A to a respective nearest integer.
According to exemplary embodiments, because the transformer 120 performs a transformation by using the fast transform matrix A instead of the original N×N transform matrix Original_A, an error occurs as between a result value based on the original N×N transform matrix Original_A and a result value based on the substituted transform matrix A. Accordingly, according to an exemplary embodiment, this error may be reduced or minimized by performing scaling with respect to a transformed block in a quantization operation.
Referring to
For example, a 16×16 intermediate matrix S is defined as follows:
In operation 320, Si values that enable a sum of squares of elements excluding a diagonal component of the transformation error matrix Original_AS□A to be a minimum are obtained. The Si values may be determined using any optimization algorithm. For example, the Si values may be determined by setting an initial value of S1 to be equal to (¼*2^{(1/2)}) and then applying an optimization algorithm, such as, for example, a NelderMead simplex method.
In operation 330, a scaling matrix is produced based on a matrix S□S^{T }which is obtained by multiplying each of the elements of the N×N intermediate matrix S, to which the acquired Si values have been applied, by corresponding elements of a transposed matrix S^{T }of the N×N intermediate matrix S, respectively.
When PF denotes the matrix S□S^{T}, a scaling matrix MF may be calculated according to the following equation: MF=PF*2^{m}/Qstep. Here, Qstep denotes a quantization step, and m is a positive integer.
The scaling matrices MF, as shown in
Such a scaling matrix MF may be obtained for a 32×32 block in a similar manner as that described above for obtaining the scaling matrix MF for the 16×16 block.
As described above, the quantizer 130 performs scaling with respect to a transformed block by using a scaling matrix MF or a predetermined scaling constant in order to reduce an error value as between a result of the transformation which is performed by using the fast transform matrix A by the transformer 120 and a result of the transformation which is performed by using the DCT matrix Original_A based on an actual floating point operation. In detail, the quantizer 130 may perform scaling and quantization simultaneously with respect to a transformed block which corresponds to a result of the transformation on the N×N block by using the scaling matrix MF and a shift operation. The quantization is performed by performing a bit shift operation on a value which is obtained by multiplying the scaling matrix MF and the transformed block and then adding a predetermined offset to the value, by a q bit as expressed in the following equation: q=floor(QP/6)+m. When Zij denotes a quantized coefficient value, Wij denotes a transformation coefficient, and f denotes an offset, Zij=(Wij.MF+f)»qbits and sign(Zin)=sign(Wij). Here, “.MF” denotes a vector product operation for multiplying the elements at corresponding locations in matrices. As described above, the vector product operation may be indicated as □.
Further, in a dequantization operation, dequantization may be performed by applying a descaling matrix and a shift operation in order to compensate for a difference between an original N×N inverse transform matrix Original_A−1 which is used for performing an IDCT, and an N×N fast inversetransform matrix A−1.
According to an exemplary embodiment, a descaling matrix V may be generated based on a matrix PF which corresponds to the matrix S□S^{T }which is obtained by multiplying each of the elements of the intermediate matrix S with the corresponding elements of the transposed matrix S^{T}, which are also used to generate the scaling matrix MF. In detail, when Qstep denotes a quantization step, PF denotes the matrix S□S^{T}, and n is a positive integer, the descaling matrix V may be obtained by using the following equation: V=Qstep*PF*2^{n}.
When the descaling matrix V is obtained as described above, descaling and dequantization may be performed by performing a bit shift operation on a value which is obtained by multiplying the descaling matrix V and a quantized transformation coefficient, by a floor(QP/6) bit, wherein floor[x] is a maximum integer which is smaller than or equal to x and QP denotes a quantization parameter. In particular, when Zij denotes a quantized coefficient value and Wij denotes a transformation coefficient, Wij may be obtained by dequantizing the quantized coefficient Zij via the following equation: Wij=(Zij)«floor(QP/6). Here, “.V” denotes a vector product operation for multiplying each of the elements at corresponding locations in matrices. As described above, the vector product operation may be indicated as □.
Similarly, descaling matrices V based on a quantization parameter QP which is applied to the 32×32 block may be obtained in a process similar to that described above with respect to the descaling matrices V as applied to the 16×16 block.
Referring to
Referring to
with respect to an input value [X1,X2].
When a DCT is performed based on the flow graph 800 of
For example, a 1D DCT which is performed on a 32×32 input block by using the fast transform matrix A may be expressed as the following operation, wherein Xi (where i is an integer in the range of 0 to 31) denotes an input value to be transformed, Ai, Bi, Ci, Di, and Ei denote intermediate values, and Yi denotes a transform result value:
According to another exemplary embodiment, the quantizer 130 may perform scaling by multiplying each element of the transformed block by a predetermined scaling constant. In detail, the quantizer 130 may perform scaling and quantization simultaneously with respect to an N×N transformed block by using a scaling constant QMat and a shift operation. The quantization and the scaling are performed by performing a bit shift operation on a value which is obtained by multiplying the scaling constant QMat and the N×N transformed block and then adding a predetermined offset to the value, by a q bit of the following equation: q=floor(QP/6)+m. When Zij denotes a quantized coefficient value, Wij denotes a transformation coefficient, and f denotes an offset, Zij=(Wij·QMat+f)»qbits and sign(Zij)=sign(Wij).
The scaling constant QMat may be selected based on the quantization parameter QP, and is defined with respect to Qstep values of 0.625, 0.6875, 0.8125, 0.875, 1, and 1.25 of only an initial six quantization steps, without having to be defined with respect to all quantization steps. As described above, when the quantization parameter QP increases by 6, the quantization step Qstep is doubled, and thus the scaling constant QMat may be defined with respect to the Qstep values of the initial six quantization steps, and the scaling constant QMat based on the other quantization parameters QP may be selected based on a (QP mod 6) value.
For example, if i=(QP mod 6), a scaling constant QMati for scaling with respect to a 16×16 transformed block which is obtained by performing a DCT based on the flow graph 200 or 800 of
QMat0=81, QMat1=89, QMat2=105, QMat3=113, QMat4=129; QMat5=146
The scaling constant QMati is not limited thereto, and may be adjusted within a range of ±1 or ±2. In particular, the scaling constant QMati may be adjusted within a range of QMati±1 or QMati±2.
A scaling constant QMati for scaling with respect to a 32×32 transformed block which is obtained by performing a DCT based on the flow graph 200 or 800 of
QMat0=40, QMat1=44, QMat2=52, QMat3=56, QMat4=64; QMat5=72
The scaling constant QMati is not limited thereto, and may be adjusted within a range of ±1 or ±2. In particular, the scaling constant QMati may be adjusted within a range of QMati±1 or QMati±2. For example, QMat0=40, QMat1=45, QMat2=51, QMat3=57, QMat4=64, and QMat5=72 may be used as the scaling constant QMati.
Further, in a dequantization operation, dequantization may be performed by applying a descaling constant and a shift operation in order to compensate for a difference between the original N×N inverse transform matrix Original_A−1 which is used for performing an IDCT, and the N×N fast inversetransform matrix A−1, which is an inverse matrix of the N×N fast transform matrix A.
According to another exemplary embodiment, a descaling constant DQMat may be determined based on the quantization parameter QP. When the descaling constant DQMat is obtained as described above, descaling and dequantization may be performed by performing a bit shift operation on a value which is obtained by multiplying the descaling constant DQMat and a quantized transformation coefficient, by a floor(QP/6) bit, wherein floor[x] is a maximum integer smaller than or equal to x and QP denotes a quantization parameter. In particular, when Zij denotes a quantized coefficient value and Wij denotes a transformation coefficient, Wij may be obtained by descaling and dequantizing the quantized coefficient Zij via the following equation: Wij=(Zij)*DQMat«floor(QP/6).
The descaling constant DQMat is defined with respect to Qstep values of 0.625, 0.6875, 0.8125, 0.875, 1, and 1.25 of only an initial six quantization steps, without having to be defined with respect to all quantization steps, because when the quantization parameter QP increases by 6, the quantization step Qstep is doubled, and thus the descaling constant DQMat may be defined with respect to the Qstep values of the initial six quantization steps, and the descaling constant DQMat based on the other quantization parameters QP may be selected based on a (QP mod 6) value.
For example, if i=(QP mod 6), a descaling constant MQMati which is used for descaling with respect to a 16×16 transformed block which is obtained by performing a DCT based on the flow graph 200 or 800 of
DQMat0=81, DQMat1=89, DQMat2=105, DQMat3=113, DQMat4=129; DQMat5=146
The descaling constant DQMati is not limited thereto, and may be adjusted within a range of ±1 or ±2. In particular, the descaling constant DQMati may be adjusted within a range of QMati±1 or QMati±2.
A descaling constant DQMati which is used for descaling with respect to a 32×32 transformed block which is obtained by performing a DCT based on the flow graph 200 or 800 of
DQMat0=40, DQMat1=44, DQMat2=52, DQMat3=56, DQMat4=64; DQMat5=72
The descaling constant DQMati is not limited thereto, and may be adjusted within a range of ±1 or ±2. In particular, the descaling constant DQMati may be adjusted within a range of QMati±1 or QMati±2. For example, DQMat0=40, DQMat1=45, DQMat2=51, DQMat3=57, DQMat4=64, and QMat5=72 may be used as the descaling constant DQMati.
Referring to
In operation 1020, the transformer 120 produces an N×N transformed block by transforming the N×N block using the fast transform matrix.
In operation 1030, the quantizer 130 performs scaling on the N×N transformed block in order to correct a difference between the N×N transform matrix which is used for performing the 1D DCT and the fast transform matrix. As described above, the quantizer 130 performs scaling with respect to a transformed block by using the scaling matrix MF or the scaling constant QMat in order to reduce an error value as between a result of the transformation performed using the fast transform matrix A by the transformer 120 and a result of the transformation performed using the DCT matrix Original_A based on an actual floating point operation.
Referring to
The entropy decoder 1110 extracts prediction mode information, reference picture information, and residual information of a current block to be decoded, from an input bitstream.
The dequantizer 1120 dequantizes quantized transformation coefficients, which are entropydecoded by the entropy decoder 1110. In particular, according to an exemplary embodiment, the dequantizer 1120 performs descaling on an N×N transformed block in order to correct a difference between an N×N inversetransform matrix for use in performing a 1D IDCT with respect to a quantized N×N transformed block and a fast inversetransform matrix which is produced based on the N×N inversetransform matrix.
The inversetransformer 1130 inversetransforms the dequantized transformation coefficients. Accordingly, residual values for each block are restored. The inverse transformation may be performed by performing an Npoint IDCT by using an inverse matrix A−1 of an N×N fast transform matrix A which may be acquired according to any one of various exemplary embodiments. The inversetransformer 1130 performs an IDCT by using a fast transformation matrix which is formed of elements that are obtained by substituting the elements of an inversetransform matrix used for performing the IDCT with rational numbers, or by multiplying each of the elements of the inversetransform matrix by a power of 2 and then rounding up each of the multiplied elements to a respective nearest integer.
An IDCT which is performed on a 16×16 transformed block by using the flow graph 200 of
An IDCT which is performed on a 32×32 transformed block by using the flow graph 200 of
An IDCT which is performed on a 16×16 transformed block by using the flow graph 800 of
An IDCT which is performed on a 32×32 transformed block by using the flow graph 800 of
Referring to
In operation 1230, the inversetransformer 1130 produces an N×N inversetransformed block by inversely transforming a descaled N×N transformed block using the fast inversetransform matrix. As described above, the fast inversetransform matrix is the inverse matrix A^{−1 }of the N×N fast transform matrix A which may be acquired according to any one of various exemplary embodiments, and an IDCT is performed by using a fast transformation matrix which is formed of elements that are obtained by substituting the elements of an inversetransform matrix which is used for performing the IDCT with rational numbers, or by multiplying each of the elements of the inversetransform matrix by a power of 2 and then rounding up each of the multiplied elements to a respective nearest integer.
One or more exemplary embodiments can also be embodied as computer readable codes on a transitory or nontransitory computer readable recording medium. The computer readable recording medium may include any data storage device that can store data which can be thereafter read by a computer system. Examples of the nontransitory computer readable recording medium include readonly memory (ROM), randomaccess memory (RAM), compact diskROM (CDROMs), magnetic tapes, floppy disks, optical data storage devices, and/or any other suitable medium. The computer readable recording medium can also be distributed over networkcoupled computer systems so that the computer readable code is stored and executed in a distributed fashion.
While the present inventive concept has been particularly shown and described with reference to 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 disclosure as defined by the following claims.