RU2631992C2 - Method of encoding image and method of decoding image - Google Patents

Abstract

FIELD: physics.

SUBSTANCE: image decoding method in which the transform coefficients for the target image to be decoded and the information indicative of the internal prediction mode for the target image are decoded; scanning coefficients for generating scanned conversion coefficients; a combination of a matrix of a vertical inverse transform and a horizontal inverse transform matrix corresponding to the target image is determined based on a predetermined ratio; inversely converting the scanned transform coefficients along the vertical direction and the horizontal direction using a combination of a vertical inverse transformation matrix and a horizontal inverse transformation matrix when the internal prediction mode is the first mode or the second mode to obtain the prediction error; and a decoded image is generated based on the prediction error.

EFFECT: increasing the efficiency of video decoding.

46 dwg

Description

FIELD OF TECHNOLOGY

Embodiments of the present invention relate to orthogonal transform and inverse orthogonal transform when encoding and decoding a video.

BACKGROUND

In recent years, an image encoding method with significantly improved encoding efficiency has been jointly recommended by ITU-T and ISO / IEC as ITU-T REC. H. 264 and ISO / IEC 14496-10 (hereinafter referred to as "H. 264"). H. 264 performs discrete cosine transform (DCT) and inverse discrete cosine transform (IDCT) as the orthogonal transform and inverse orthogonal transform of prediction errors in the target pixel block regardless of the prediction scheme applied to the target pixel block.

Advanced H. 264 is intended to perform orthogonal transform and inverse orthogonal transform using individual transform bases for the respective nine types of prediction modes specified for intra-picture prediction (intra prediction), thereby increasing the coding efficiency.

LIST OF REFERENCES

NON-PATENT LITERATURE

Non-Patent Literature 1: M. Karczewicz, "Improved intra coding", ITU-T SG16 / Q. 6, VCEG Document, VCEG-AF15, April 2007.

SUMMARY OF THE INVENTION

TECHNICAL PROBLEM

However, in connection with the implementation, it is difficult to carry out orthogonal transformation and inverse orthogonal transformation using individual transformation bases for the respective numerous types of prediction modes. For example, a hardware implementation requires not only the dedicated hardware for DCT and IDCT required for H. 264, but also dedicated hardware for individual orthogonal transforms and inverse orthogonal transforms for the respective multiple types of prediction directions. Adding dedicated hardware increases the scale of relevant circuits.

The software implementation allows you to load from memory if necessary and store in the cache if necessary. In this case, the desired orthogonal transform and the inverse orthogonal transform can be realized by a general purpose multiplication device. However, it is not preferable that the costs increase as a result of increased memory bandwidth or cache size.

Thus, the aim of the embodiments is to provide an orthogonal transform and an inverse orthogonal transform that can improve coding efficiency.

SOLUTION

According to one aspect, an image encoding method includes predicting a prediction error of a target image to be encoded based on an intra prediction mode. The method includes setting a combination of a vertical transformation matrix and a horizontal transformation matrix corresponding to the target image based on a predetermined ratio. This combination includes any of a variety of transformation matrices, including a first transformation matrix and a second transformation matrix, which increases the coefficient density compared to the first transformation matrix if the one-dimensional orthogonal transformation, in the direction orthogonal to the line from the group of reference pixels on at least one the line is executed on the prediction error in the intra prediction mode, in which a group of reference pixels is referenced to generate an image from the inner him a prediction. The method includes predicting error conversion using a combination of a vertical transformation matrix and a horizontal transformation matrix to obtain transform coefficients. The method includes coding transform coefficients and information indicating an intra prediction mode for a target image.

According to another aspect, an image decoding method includes decoding transform coefficients for a target image to be decoded, and information indicating an intra prediction mode for the target image. The method includes setting a combination of a vertical inverse transform matrix and a horizontal inverse transform matrix corresponding to the target image based on a predetermined ratio. This combination includes any of a plurality of transposed matrices from a plurality of transformation matrices, including a first transformation matrix and a second transformation matrix, which increases the coefficient density compared to the first transformation matrix if the one-dimensional orthogonal transformation is in the direction orthogonal to the line from the group of reference pixels by at least one line is executed on the prediction error in the intra prediction mode, which refers to a group of reference pixels for To generate an intra-prediction image. The method includes performing an inverse transform of the prediction coefficients using a combination of a vertical inverse transform matrix and a horizontal inverse transform matrix to obtain a prediction error. The method includes generating a decoded image based on a prediction error.

BRIEF DESCRIPTION OF THE DRAWINGS

In FIG. 1 is a block diagram illustrating an image encoding apparatus according to a first embodiment.

In FIG. 2 is a block diagram illustrating an orthogonal transform unit according to the first embodiment.

In FIG. 3 is a block diagram illustrating an inverse orthogonal transform unit according to the first embodiment.

In FIG. 4A is a table illustrating a correspondence between prediction modes and a vertical transform index and a horizontal transform index according to the first embodiment.

In FIG. 4B is a table illustrating the correspondence between the vertical transformation index and the transformation matrices 1D according to the first embodiment.

In FIG. 4C is a table illustrating the correspondence between the horizontal transform index and the transform matrices 1D according to the first embodiment.

In FIG. 4D is a table illustrating a correspondence between a transform index and a vertical transform index and a horizontal transform index according to the first embodiment.

In FIG. 4E shows a table obtained by combining FIG. 4A with 4D.

In FIG. 5A is a block diagram illustrating a coefficient order control unit according to the first embodiment.

In FIG. 5B is a block diagram illustrating a coefficient order control unit according to the first embodiment.

In FIG. 6A is a graphical representation illustrating a pixel block prediction coding order.

In FIG. 6B is a graphical view illustrating an example of a block size of pixels.

In FIG. 6C is a graphical view illustrating an example of pixel block size.

In FIG. 6D is a graphical view illustrating an example of a block size of pixels.

In FIG. 7A is a graphical view illustrating an intra prediction mode.

In FIG. 7B is a graphical view illustrating an arrangement relationship between prediction target pixels and reference pixels.

In FIG. 7C is a graphical view illustrating intra prediction mode 1.

In FIG. 7D is a graphical view illustrating intra prediction mode 4.

In FIG. 8A is a graphical view illustrating a zigzag scan.

In FIG. 8B is a graphical view illustrating a zigzag scan.

In FIG. 8C is a table showing a 2D-1D transformation using a zigzag scan.

In FIG. 9 is a table showing individual 2D-1D transformations for respective prediction modes.

In FIG. 10A is a flowchart illustrating processing performed on the encoding target block by the image encoding apparatus of FIG. one.

In FIG. 10B is a flowchart illustrating processing performed on the encoding target block by the image encoding apparatus in FIG. one.

In FIG. 11 is a graphical representation illustrating a syntax structure.

In FIG. 12 is a graphical representation illustrating the syntax of a clipping header.

In FIG. 13 is a graphical representation illustrating the syntax of a coding tree unit.

In FIG. 14 is a graphical representation illustrating the syntax of a conversion unit.

In FIG. 15 is a block diagram illustrating an orthogonal transform unit that performs orthogonal transform on each of the nine types of prediction directions using a specific transform basis.

In FIG. 16 is a block diagram illustrating an orthogonal transform unit according to the second embodiment.

In FIG. 17 is a block diagram illustrating an inverse orthogonal transform unit according to the second embodiment.

In FIG. 18A is a table illustrating a correspondence between prediction modes and a vertical transform index and a horizontal transform index according to the second embodiment.

In FIG. 18B is a table illustrating a correspondence between the vertical transformation index and the transformation matrices 1D according to the second embodiment.

In FIG. 18C is a table illustrating the correspondence between the horizontal transform index and the transform matrices 1D according to the second embodiment.

In FIG. 18D is a table illustrating a correspondence between a transform index and a vertical transform index and a horizontal transform index according to the second embodiment.

In FIG. 18E shows a table obtained by combining FIG. 18A with 18D.

In FIG. 19 is a block diagram illustrating an orthogonal transform unit according to a third embodiment.

In FIG. 20 is a block diagram illustrating an inverse orthogonal transform block according to a third embodiment.

In FIG. 21A is a table illustrating a correspondence between prediction modes and a vertical transform index and a horizontal transform index according to the third embodiment.

In FIG. 21B is a table illustrating a correspondence between the vertical transformation index and the transformation matrices 1D according to the third embodiment.

In FIG. 21C is a table illustrating the correspondence between the horizontal transform index and the transform matrices 1D according to the third embodiment.

In FIG. 21D is a table illustrating a correspondence between a transform index and a vertical transform index and a horizontal transform index according to the third embodiment.

In FIG. 21E shows a table obtained by combining FIG. 21A with 21D.

In FIG. 22 is a block diagram illustrating an image decoding apparatus according to a fourth embodiment.

In FIG. 23A is a block diagram illustrating a coefficient order control unit according to a fourth embodiment.

In FIG. 23B is a block diagram illustrating a coefficient order control unit according to a fourth embodiment.

DESCRIPTION OF EMBODIMENTS

Embodiments will be described below with reference to the drawings. In the description below, the term “image” may be replaced by the term “image signal”, “image data”, or the like, if necessary.

(FIRST EMBODIMENT)

The first embodiment relates to an image encoding device. An image decoding apparatus corresponding to an image encoding apparatus according to the present embodiment will be described in the fourth embodiment. An image encoding device may be implemented by hardware such as LSI (large integrated circuit) crystals, DSP (digital signal processing processors), FPGA (user programmable gate arrays), and the like. In addition, the image encoding device may also be implemented by enabling the computer to execute the image encoding program.

As shown in FIG. 1, the image encoding apparatus according to the present embodiment includes a subtraction unit 101, an orthogonal transform unit 102, a quantization unit 103, a dequantization unit, an orthogonal transform unit 105, an addition unit 106, a reference image memory 107, an intra prediction unit 108, a block 109 prediction block, prediction selection block 110, prediction selection switch 111, block 112 of setting the matrix 1D (one-dimensional) transformation, block 113 control the order of the coefficients, block 114 of the entropy to encoding, output buffer 115, and encoding control unit 116.

The image encoding apparatus of FIG. 1 divides each of the frames or fields constituting the input image 118 into a plurality of pixel blocks, performs prediction coding of blocks of pixels resulting from division, and outputs encoded data 130. For simplicity, it is assumed that prediction coding is further performed in this document above the block of pixels from upper left to lower right, as shown in FIG. 6A. In FIG. 6A shows a coding target frame f in which the encoded blocks of p pixels are located to the left and above the coding pixel target block c.

Here, a pixel block refers to, for example, a coding tree unit, a macroblock, a subblock, or a pixel. The pixel block is hereinafter mainly used to mean a unit of a coding tree, but can be interpreted to have a different value if necessary. A coding tree unit is typically, for example, a 16 x 16 pixel block shown in FIG. 6B, but may be the 32 x 32 pixel block shown in FIG. 6C, by the 64 x 64 pixel block shown in FIG. 6D, or an 8 x 8 pixel block or a 4 x 4 pixel block shown in the drawings. The coding tree unit does not have to be square. The encoding target block or coding tree unit in the input image is hereinafter sometimes referred to as the "prediction target block". In addition, the coding unit is not limited to a block of pixels, such as a coding tree unit, but may be a frame, field, or a combination thereof.

The image encoding apparatus of FIG. 1 performs intra prediction (also referred to as intra-frame prediction, intra-frame prediction or the like) or inter prediction (also called inter-picture prediction, inter prediction or the like) to generate a predicted image 127. The image encoding apparatus orthogonally converts and quantizes the prediction error 119 between a block of pixels (input image 118) and a predicted image 127. The image encoding device then performs an entropy to dirovanie transformed and quantized prediction error to generate and output the encoded data 130.

The image encoding apparatus of FIG. 1 performs encoding by selectively applying a plurality of prediction modes involving different block sizes and different methods for generating the predicted image 127. The method for generating the predicted image 127 is roughly classified into two types: intra prediction, which performs prediction within the encoding target frame, and inter prediction, which predicts using one or more reference frames temporarily different from each other. In the present embodiment, the orthogonal transform and inverse orthogonal transform performed to generate the predicted image using intra prediction will be described in detail.

The components of the image encoding device in FIG. 1 will be described below.

Subtractor 101 subtracts the corresponding predicted image 127 from the encoding target block in the input image 118 to obtain a prediction error 119. Subtractor 101 introduces prediction error 119 into orthogonal transform unit 102.

The orthogonal transform unit 102 converts the prediction error 119 from the subtractor 101 to obtain transform coefficients 120. An orthogonal transform unit 102 will be described in detail below. An orthogonal transform unit 102 inputs transform coefficients 120 into a quantization unit 103.

The quantization unit 103 quantizes the transform coefficients from the orthogonal transform unit 102 to obtain quantized transform coefficients 121. Specifically, the quantization unit 103 quantizes in accordance with the quantization information, such as a quantization parameter and a quantization matrix, which is specified by the encoding control unit 116. The quantization parameter indicates the quantization resolution. A quantization matrix is used to assign weights to the quantization resolution for each component of the transform coefficients. The quantization unit 103 inputs transform coefficients 121 to the coefficient order control unit 113 and the dequantization unit 104.

The coefficient order control unit 113 converts the quantized transform coefficients 121, which are a two-dimensional (2D) expression, into a sequence 117 of quantized transform coefficients, which is a one-dimensional (1D) expression. The coefficient order control unit 113 then introduces a sequence 117 of quantized transform coefficients into the entropy encoding unit 114. The coefficient control unit 113 will be described in detail below.

Entropy encoding unit 114 performs entropy encoding (e.g., Huffman coding or arithmetic coding) over various encoding parameters, such as a sequence 117 of quantized transform coefficients from coefficient control unit 113, prediction information 126 from prediction selection unit 110 and quantization information that are set a coding control unit 116. Encoding parameters are required for decoding and include prediction information 126, transform coefficient information, and quantization information. Encoding parameters are held in internal memory (not shown in the drawings) in encoding control unit 116. When the prediction target block is encoded, encoding parameters for already encoded adjacent pixel blocks may be used. For example, H. 264 intra prediction allows obtaining the predicted value for the prediction mode of the prediction target block from the prediction mode information from the encoded adjacent block.

The encoded data generated by the entropy encoding unit 114, for example, is multiplexed and then temporarily accumulated in the output buffer 115. The data is then output as encoded data 130 in accordance with the proper output time interval controlled by the encoding control unit 116. Coded data 130 is output, for example, to an accumulation system (storage medium) or transmission system (communication line), which are not shown in the drawings.

The dequantization unit 104 quantizes the quantized transform coefficients 121 from the quantization unit 103 to obtain the reconstructed transform coefficients 122. Specifically, the dequantization unit 104 dequantizes in accordance with the quantization information used in the quantization unit 103. The quantization information used in the quantization unit 103 is loaded from the internal memory in the encoding control unit 116. The dequantization unit 104 introduces the reconstructed transform coefficients 122 into the inverse orthogonal transform unit 105.

The inverse orthogonal transform unit 105 performs the inverse orthogonal transform corresponding to the orthogonal transform performed by the orthogonal transform unit 102 on the reconstructed transform coefficients 122 from the dequantization unit 104 to obtain a reconstructed prediction error 123. An inverse orthogonal transform unit 105 will be described in detail below. The inverse orthogonal transform unit 105 introduces the reconstructed prediction error 123 into the addition unit 106.

An addition unit 106 adds the reconstructed prediction error 123 and the corresponding predicted image 127 together to generate a locally decoded image 124. The locally decoded image 124 is stored in the reference image memory 107. A locally decoded image 124 stored in the reference image memory 107 is referenced by the intra prediction unit 108 and the inter prediction unit 109 as the reference image 125, if necessary.

The intra prediction unit 108 performs intra prediction using the reference image 125 stored in the reference image memory 107. For example, H. 264 uses the encoded reference pixel value for a block adjacent to the prediction target block to compensate for pixels (copy or interpolate pixels) along a prediction direction, such as a vertical direction or a horizontal direction, to generate an image predicted by intra prediction. In FIG. 7A shows the prediction directions for intra prediction according to H. 264. In addition, in FIG. 7B, the arrangement relationship between the reference pixels and the encoding target pixels according to H. 264. In FIG. 7C shows a method for generating a predicted image in mode 1 (horizontal prediction). In FIG. 7D shows a method for generating a predicted image in mode 4 (downward-right diagonal prediction; Intra_NxN_Diagonal_Down_Right in FIG. 4A).

The intra prediction unit 108 may interpolate the pixel values using a predetermined interpolation method, and then copy the interpolated pixel values in a predetermined direction. The prediction directions for intra prediction according to H. 264 are illustrated, but any number of prediction modes, such as 17 or 33 types of prediction modes, are made available by defining a more detailed classification of the prediction directions. For example, H. 264 sets prediction angles at intervals of 22.5 degrees, but 17 types of prediction modes, including DC prediction, are made available by setting prediction angles at intervals of 11.25 degrees. In addition, 33 types of prediction modes, including DC prediction, are made available by setting prediction angles at intervals of 5.625 degrees. Alternatively, instead of being spaced at equal intervals, the angles of the prediction directions can be expressed by a straight line that connects the first reference point with the second reference point obtained by moving the first reference point in the horizontal direction and in the vertical direction. As described above, the number of prediction modes can be easily increased, and the present embodiment is applicable regardless of the number of prediction modes.

The inter prediction unit 109 performs inter prediction using the reference image 125 stored in the reference image memory 107. Specifically, the inter prediction unit 109 performs a block matching process between the prediction target block and the reference image 125 to obtain a motion deviation value (motion vector). The inter prediction unit 109 performs an interpolation process (motion compensation) based on the motion vector to generate an image predicted by inter prediction. H. 264 allows the interpretation process to achieve 1/4 pixel accuracy. The resulting motion vector is subjected to entropy encoding as part of the prediction information 126.

The selection switch 111 selects the output end of the intra prediction block 108 or the output end of the inter prediction block 109 in accordance with the prediction information 126 from the prediction selection block 110. The selection switch 111 then inputs the image predicted by the intra prediction or the image predicted by the inter prediction into the subtracting unit 101 and the addition unit 106 as the predicted image 127. The prediction information 126 indicates the intra prediction, the selection unit 110 obtains the image predicted by the intra the prediction, from the intra prediction block 108, as the predicted image 127. On the other hand, if the prediction information 126 indicates With the external prediction, the selection unit 110 obtains an image predicted by the inter prediction from the intra prediction unit 109 as the predicted image 127.

Prediction selection section 110 has a function for setting prediction information 126 in accordance with the prediction mode controlled by coding control section 116. As described above, intra prediction or inter prediction can be selected to generate the predicted image 127. Moreover, a plurality of modes can be further selected for each of intra prediction and inter prediction. The encoding control unit 116 determines one of a plurality of prediction modes for intra prediction and inter prediction to be an optimal prediction mode. Prediction selection unit 110 sets prediction information 126 according to the determined optimum prediction mode.

For example, in connection with intra prediction, prediction mode information from coding control unit 116 is set in intra prediction unit 108. According to the prediction mode information, the intra prediction unit 108 generates the predicted image 127. The encoding control unit 116 may specify a plurality of pieces of prediction mode information in order to increase the number of prediction mode or decrease the number of prediction mode. In addition, the encoding control unit 116 may limit the prediction mode in accordance with the characteristics of the input image. The encoding control unit 116 does not need to specify all the prediction modes, but can specify at least one piece of prediction mode information for the encoding target.

For example, coding control unit 116 determines the optimal prediction mode using the cost function shown in:

K = SAD + λ × OH (1)

In Expression (1), OH denotes a code amount for prediction information 126 (e.g., motion vector information and prediction block size information), and SAD denotes the sum of the absolute difference between the prediction target block and the predicted image 127 (i.e., the accumulated sum of absolute error values 119 predictions). In addition, λ denotes the Lagrange multiplier determined based on the value of the quantization information (quantization parameter), and K denotes the encoding cost. If Expression (1) is used, the prediction mode that minimizes the encoding cost K is determined to be optimal in terms of the amount of generated code and prediction errors. As a modification of Expression (1), the encoding cost can only be estimated based on OH or SAD, by using the value obtained by performing the Hadamard transform on the SAD or a value close to it.

In addition, the optimal prediction mode can be determined using a precoding unit (not shown in the drawings). For example, coding control unit 116 determines the optimal prediction mode using the cost function shown in:

J = D + λ × R (2)

In Expression (2), D denotes the sum of the squared differences (i.e., coding distortion) between the prediction target block and the locally decoded image, R denotes the amount of code estimated by precoding the prediction error between the prediction target block and the predicted image 127 for the prediction mode, and J stands for coding cost. In order to obtain the encoding cost in Expression (2), the precoding process and the local decoding process must be carried out in each prediction mode. This increases the scale of the relevant schemas or the amount of computation. On the other hand, the cost of coding J is obtained based on a more accurate coding distortion and a more accurate code size. As a result, the optimum prediction mode is precisely determined to enable easy maintenance of high coding efficiency. As a modification of Expression (2), the encoding cost can only be estimated based on R or D or by using a value close to R or D. Moreover, the encoding control unit 116 may, in advance, reduce the number of candidates for the prediction mode, one of which is determined using Expression (1) or Expression (2) based on information previously obtained for the prediction target block (prediction modes for surrounding pixel blocks, image analysis results and the like).

The encoding control unit 116 controls the components of the image encoding device in FIG. 1. Specifically, the encoding control unit 116 performs various control operations for the encoding process, including the operations described above.

The transformation matrix 1D definition unit 112 of the transformation matrix generates the transformation matrix 1D information 129 of the transformation matrix based on the prediction mode information included in the prediction information 126 from the prediction selection unit 110. The setting unit of the transformation matrix 1D then outputs the information 129 of the setting of the transformation matrix 1D to the orthogonal transformation unit 102 and the inverse orthogonal transformation unit 105. Information 129 setting matrix 1D conversion will be described in detail below.

An orthogonal transform unit 102 according to the present embodiment will be described in detail below with reference to FIG. 2.

The orthogonal transform unit 102 includes a select switch 201, a vertical transform unit 202, a transpose unit 203, a select switch 204, and a horizontal transform unit 205. The vertical transform unit 202 includes an orthogonal transform unit A 206 1D and an orthogonal transform unit B 207 1D. The horizontal transform block 205 includes an orthogonal transform block A 208 1D and an orthogonal transform block B 209 1D. The order of the vertical transform unit 202 and the horizontal transform unit 205 is illustrative and may be inverse.

The orthogonal transform block A 206 1D and the orthogonal transform block A 208 1D have common functions in that both blocks multiply the input matrix by the transform matrix A 1D. The orthogonal transform block B 207 1D and the orthogonal transform block B 209 1D have common functions in that both blocks multiply the input matrix by the transform matrix B 1D. Thus, the orthogonal transform unit A 206 1D and the orthogonal transform unit A 208 1D can also be implemented by using physically the same time-division hardware. This also applies to the orthogonal transform block B 207 1D and the orthogonal transform block B 209 1D.

The selection switch 201 results in a prediction error 119 to one of the orthogonal transform block A 206 1D and the orthogonal transform block B 207 1D in accordance with the vertical transform index included in the definition information 129 of the transform matrix 1D. The orthogonal transform unit A 206 1D multiplies the input prediction error 119 (matrix) by the transform matrix A 1D and outputs the product. The orthogonal transform unit B 207 1D multiplies the input prediction error 119 by the transform matrix B 1D and outputs the product. Specifically, the orthogonal transform unit A 206 1D and the orthogonal transform unit B 207 1D (i.e., vertical transform unit 202) perform the one-dimensional orthogonal transform shown in Equality (3) to eliminate the vertical correlation in the prediction error 119.

Y = VX (3)

In Expression (3), X denotes a prediction error matrix (N × N) 119, V comprehensively denotes a transformation matrix A 1D and a transformation matrix B 1D (both are N × N matrices), and Y denotes an output matrix (N × N) from of each of the orthogonal transform unit A 206 1D and the orthogonal transform unit B 207 1D. Specifically, the transform matrix V is an N × N transform matrix in which the transform basis designed to eliminate vertical correlation in the matrix X is vertical as row vectors. However, as described below, the transformation matrix A 1D and the transformation matrix B 1D are designed in different ways and have different types of nature.

The transformation matrix A 1D and the transformation matrix B 1D can use integers obtained by means of the designed transformation basis, subjected to scalar multiplication.

Here, if the prediction error 119 is a rectangular block expressed as M × N, the size of the block to be converted orthogonally can also be M × N.

The transpose unit 203 transposes the output matrix (Y) from the vertical conversion unit 202 and provides the transposed output matrix (Y) to the selection switch 204. However, the transpose unit 203 is illustrative, and the corresponding hardware need not be prepared. For example, the output matrix (Y) can be transposed without having to prepare the hardware corresponding to the transpose unit 203 by storing the results 1D of the orthogonal transform performed by the vertical transform unit 202 (each of the elements of the output matrix from the vertical transform unit 202) and load the results into in order, when the horizontal transform unit 205 performs 1D orthogonal transform.

The selection switch 204 brings the input matrix from the transpose unit 203 to one of the orthogonal transform unit A 208 1D and the orthogonal transform unit B 209 1D in accordance with the horizontal transform index included in the definition information 129 of the transform matrix 1D. The orthogonal transform unit A 208 1D multiplies the input matrix by the transform matrix A 1D and outputs the product. An orthogonal transform unit B 209 1D multiplies the input matrix by a transform matrix B 1D and outputs the product. Specifically, the orthogonal transform block A 208 1D and the orthogonal transform block B 209 1D (i.e., the horizontal transform block 205) perform the one-dimensional orthogonal transform shown in Equality (4) to eliminate horizontal correlation in the prediction error.

Z = HYT (4)

In Equality (4), H comprehensively denotes the A 1D transform matrix and the B 1D transform matrix (both are N × N matrices), and Z denotes the output matrix (N × N) from each of the orthogonal transform block A 208 1D and the B 209 block 1D orthogonal transform; the output matrix indicates transform coefficients 120. Specifically, the transform matrix H is an N × N transform matrix in which a transform basis designed to eliminate horizontal correlation in the Y matrix is vertically arranged as row vectors. As described above, the transformation matrix A 1D and the transformation matrix B 1D are designed in different ways and have different types of nature. In addition, the transformation matrix A 1D and the transformation matrix B 1D can use integers obtained by means of the designed transformation basis, subjected to scalar multiplication.

As described above, the orthogonal transform unit 102 performs orthogonal transform, in accordance with the definition information 129 of the transform matrix 1D input from the set block 112 of the transform matrix 1D, the prediction error (matrix) 119 for generating transform coefficients 120 (matrix). Using the H. 264 taken into account, the orthogonal transform unit 102 may include a DCT block (not shown in the drawings) or one of the transform matrix A 1D and the transform matrix B 1D may be replaced by a matrix for DCT. For example, the transformation matrix B 1D may be a transformation matrix for DCT. Moreover, the orthogonal transform unit 102 may implement, in addition to the DCT, various orthogonal transforms, such as the Hadamard transform, the Karunen-Loeve transform described below, and the discrete sine transform.

Now, a difference in nature between the transformation matrix A 1D and the transformation matrix B 1D will be described. Some intra prediction modes supported by H. 264 and the like generate a predicted image by copying along the prediction direction, wherein a group of reference pixels on one or both adjacent lines located to the left of or above the prediction target block, or performing similar copying after interpolation . That is, this intra prediction mode selects at least one reference pixel from the group of reference pixels in accordance with the direction of the prediction and copies the reference pixel or performs interpolation using the reference pixels to generate the predicted image. The intra prediction mode uses spatial correlation in the image and thus has prediction accuracy, which tends to decrease with increasing distance from the reference pixel. That is, the absolute value of the prediction error is likely to increase according to the distance from the reference pixel. This trend is similarly manifested regardless of the direction of prediction. More specifically, in connection with intra prediction modes (e.g., mode 1 and mode 8 in Fig. 7A), referenced (pixel values of reference pixels are copied, or interpolation is performed using reference pixels), only a group of reference pixels on a line, located to the left of or next to the prediction target block, the prediction error tends to be horizontal. Due to the prediction modes referenced (for example, mode 0, mode 3, and mode 7 in Fig. 7A) only to a group of reference pixels on a line located above or next to the prediction target block, the prediction error tends to be in the vertical direction . Moreover, in connection with prediction modes (e.g., mode 4, mode 5 and mode 6 in Fig. 7A), which refer to reference pixel groups on a line located to the left of or next to the prediction target block, and on a line placed above or next to the prediction target block, the prediction error exhibits such a tendency in the horizontal direction and the vertical direction. In general, the trend is manifested in a direction orthogonal to the line of the reference pixel group used to generate the predicted image.

The transformation matrix A 1D of the transformation is generated by preliminary designing a common transformation basis in order to increase, in comparison with the transformation matrix B 1D, the density of orthogonal transformation coefficients 1D (i.e., to reduce the proportion of non-zero coefficients in the quantized transformation coefficients 121) in the orthogonal direction (vertical direction or horizontal direction). On the other hand, the transformation matrix B 1D is generated by designing a general-purpose transformation matrix that is not of this nature. For example, a general purpose transformation is DCT. The intra prediction error conversion efficiency and thus the coding efficiency is improved by performing 1D orthogonal transformation in the orthogonal direction using the transformation matrix A 1D. For example, prediction error 119 in mode 0 (vertical prediction) tends to be in the vertical direction, but not in the horizontal direction. Hence, the orthogonal transform efficiency can be achieved by performing 1D orthogonal transform in the vertical transform block 202 using the transform matrix A 1D, and performing 1D orthogonal transform in the horizontal transform block 205 using the transform matrix B 1D.

An inverse orthogonal transform unit 105 according to the present embodiment will be described in detail below with reference to FIG. 3.

The inverse orthogonal transform unit 105 includes a select switch 301, a vertical inverse transform unit 302, a transpose unit 303, a select switch 304 and a horizontal inverse transform unit 305. The vertical inverse transform unit 302 includes an inverse orthogonal transform unit A 306 1D and an inverse orthogonal transform unit B 307 1D. The horizontal inverse transform unit 305 includes an inverse orthogonal transform block A 308 1D and an inverse orthogonal transform block B 309 1D. The order of the vertical inverse transform unit 302 and the horizontal inverse transform unit 305 is illustrative and may be inverse.

The inverse orthogonal transform block A 306 1D and the inverse orthogonal transform block A 308 1D have common functions in that both blocks multiply the input matrix by the transposed matrix of the transform matrix A 1D. The inverse orthogonal transform block B 307 1D and the inverse orthogonal transform block B 309 1D have common functions in that both blocks multiply the input matrix by the transposed matrix of the B 1D transform matrix. Thus, the inverse orthogonal transform block A 306 1D and the inverse orthogonal transform block A 308 1D can also be implemented using physically the same time-division hardware. This also applies to the inverse orthogonal transform block B 307 1D and the inverse orthogonal transform block B 309 1D.

The selection switch 301 brings the restored transform coefficients 122 to one of the inverse orthogonal transform block A 306 1D and the inverse orthogonal transform block B 307 1D in accordance with the vertical transform index included in the definition information 129 of the transform matrix 1D. An inverse orthogonal transform unit A 306 1D multiplies the input transform coefficients 122 (matrix form) by the transposed matrix of the transform matrix A 1D and outputs the product. An inverse orthogonal transform block B 307 1D multiplies the input transform coefficients 122 by the transposed matrix of the transform matrix B 1D and outputs the product. Specifically, the inverse orthogonal transform unit A 306 and the inverse orthogonal transform unit B 307 (i.e., the vertical inverse transform unit 302) perform the one-dimensional inverse orthogonal transform shown in:

Y '= VTZ' (5)

In Expression (5), Z ′ denotes a matrix (N × N) of reconstructed transform coefficients 122, VT comprehensively denotes transposed matrices for a transform matrix A 1D and a transform matrix B 1D (both are N × N matrices), and Y denotes an output matrix ( N × N) from each of the inverse orthogonal transform block A 306 1D and the inverse orthogonal transform block B 307 1D.

The transpose unit 303 transposes the output matrix (Y ') from the vertical inverse transform unit 202 and outputs the transposed output matrix to the selection switch 304. However, the transpose unit 303 is illustrative, and the corresponding hardware need not be prepared. For example, the output matrix (Y ') can be transposed without having to prepare the hardware corresponding to the transpose unit 303 by storing the results of the 1D inverse orthogonal transform performed by the inverse vertical transform unit 302 (each of the elements of the output matrix from the inverse vertical transform unit 302) and loading the results in the proper order when the horizontal inverse transform unit 305 performs a 1D inverse orthogonal transform Waning.

The selection switch 304 brings the input matrix from the transpose block 303 to one of the inverse orthogonal transform block A 308 1D and the inverse orthogonal transform block B 309 1D in accordance with the horizontal transform index included in the definition information 129 of the transform matrix 1D. An inverse orthogonal transform unit A 308 1D multiplies the input matrix by the transposed matrix of the transform matrix A 1D and outputs the product. An inverse orthogonal transform block B 309 1D multiplies the input matrix by the transposed matrix of the transform matrix B 1D and outputs the product. Specifically, the inverse orthogonal transform unit A 308 and the inverse orthogonal transform unit B 309 (i.e., the horizontal inverse transform unit 305) perform the one-dimensional inverse orthogonal transform shown in:

X '= HTY'T (6)

In Equality (6), HT comprehensively denotes the transposed matrices for the transform matrix A 1D and the transform matrix B 1D (both are N × N matrices), and X 'denotes the output matrix (N × N) from each of the inverse orthogonal transform block A 308 1D and block B 309 1D inverse orthogonal transform; the output matrix indicates the reconstructed prediction error 123.

As described above, the inverse orthogonal transform unit 105 performs orthogonal transform, in accordance with the definition information 129 of the transform matrix 1D input from the transform block 112 of the transform matrix 1D, the reconstructed transform coefficients (matrices) 122 to generate a reconstructed prediction error (matrix) 123. Using the consideration of H. 264, the inverse orthogonal transform unit 105 may include an IDCT block (not shown in the drawings) or one of the transform matrix A 1D and the transform matrix B 1D may be replaced by a matrix for DCT. For example, the transformation matrix B 1D may be a transformation matrix for DCT. Moreover, the inverse orthogonal transform unit 105 may implement, in addition to the IDCT, inverse orthogonal transforms corresponding to various orthogonal transforms, such as the Hadamard transform, the Karunen-Loeve transform described below, and the discrete sine transform for coordination with the orthogonal transform block 102.

The setting information 129 of the transformation matrix 1D according to the present embodiment, which is generated by the determining unit 112 of the transformation matrix 1D, will be described in detail below.

The mapping matrix 1D information 129 of the transform matrix 1D directly or indirectly indicates a vertical transform index for selecting a transform matrix for use in vertical orthogonal transform and vertical inverse orthogonal transform, and a horizontal transform index for selecting a transform matrix for use in horizontal orthogonal transform and horizontal inverse orthogonal transform. For example, the job information 129 of the transform matrix 1D may be expressed by the transform index (TrasformIdx) shown in FIG. 4D. The reference to the table in FIG. 4D provides the ability to obtain a vertical transform index (Idx vertical transform) and a horizontal transform index (Idx horizontal transform) from the transform index.

As shown in FIG. 4B, the vertical transformation index “0” allows selection of the transformation matrix A 1D (1D_Transform_Matrix_A) or its transposed matrix for vertical orthogonal transformation or vertical inverse orthogonal transformation. On the other hand, the vertical transformation index “1” allows the selection of the transformation matrix B 1D (1D_Transform_Matrix_B) or its transposed matrix for vertical orthogonal transformation or vertical inverse orthogonal transformation.

As shown in FIG. 4C, the horizontal transformation index “0” allows the selection of the transformation matrix A 1D (1D_Transform_Matrix_A) or its transposed matrix for horizontal orthogonal transformation or horizontal inverse orthogonal transformation. On the other hand, the horizontal transformation index “1” allows the selection of the transformation matrix B 1D (1D_Transform_Matrix_B) or its transposed matrix for horizontal orthogonal transformation or horizontal inverse orthogonal transformation.

Also in FIG. 4A illustrates an index for each (internal) prediction mode (IntraN × NPredModeIndex), its name (IntraN × NPredMode name), and the corresponding vertical transform index and horizontal transform index. In FIG. 4A, “N × N” indicates the size of the prediction target block (N = 4, 8, 16 or the like). The size of the prediction target block can be expanded to “M × N” (that is, rectangles instead of squares).

In FIG. 4E is obtained by combining FIG. 4A and FIG. 4D together and shows an index for each prediction mode, an index name, and a corresponding transform index.

Block 112 of the definition matrix 1D conversion detects the index of the prediction mode from the information of the prediction mode included in the information 126 prediction. Block 112 specify the matrix 1D conversion then generates the corresponding information 129 of the task matrix 1D conversion. The tables shown in FIG. 4A, FIG. 4B, FIG. 4C, FIG. 4D and FIG. 4E are illustrative. The conversion matrix 1D transformation unit 112 may generate the conversion matrix 1D information 129 of the transformation matrix, while avoiding the use of some or all of the tables.

For example, a TransformIdx indicating 0 means that the vertical transform index indicates 0, and that the horizontal transform index indicates 0. This means that the transform matrix A 1D is used for vertical orthogonal transforms, and that the transform matrix A 1D is used for horizontal orthogonal transforms. These values also mean that the transposed matrix of the transformation matrix A 1D is used for vertical inverse orthogonal transformation, and that the transposed matrix of the transformation matrix A 1D is used for horizontal inverse orthogonal transformation.

A TransformIdx indicating 1 means that the vertical transformation index indicates 0, and that the horizontal transformation index indicates 1. This means that the transformation matrix A 1D is used for vertical orthogonal transformation, and that the transformation matrix B 1D is used for horizontal orthogonal transformation. These values also mean that the transposed matrix of the transformation matrix A 1D is used for vertical inverse orthogonal transformation, and that the transposed matrix of the transformation matrix B 1D is used for horizontal inverse orthogonal transformation.

TransformIdx indicating 2 means that the vertical transformation index indicates 1, and that the horizontal transformation index indicates 0. This means that the transformation matrix B 1D is used for vertical orthogonal transformation, and that the transformation matrix A 1D is used for horizontal orthogonal transformation. These values also mean that the transposed matrix of the transformation matrix B 1D is used for vertical inverse orthogonal transformation, and that the transposed matrix of the transformation matrix A 1D is used for horizontal inverse orthogonal transformation.

TransformIdx indicating 3 means that the vertical transformation index indicates 1, and that the horizontal transformation index indicates 1. This means that the transformation matrix B 1D is used for vertical orthogonal transformation, and that the transformation matrix B 1D is used for horizontal orthogonal transformation. These values also mean that the transposed matrix of the transformation matrix B 1D is used for vertical inverse orthogonal transformation, and that the transposed matrix of the transformation matrix B 1D is used for horizontal inverse orthogonal transformation.

The table shown in FIG. 4A, assigns the setting information 129 of the transform matrix 1D considering the above-described trend of each intra prediction mode. That is, 0 is assigned to a vertical conversion index for prediction modes exhibiting a tendency in the vertical direction of prediction errors. 0 is assigned to the horizontal transform index for prediction modes exhibiting a trend in the horizontal direction. On the other hand, 1 is assigned to each of the directions that do not show a trend.

When the vertical and horizontal directions of the prediction are classified into two classes, depending on whether there is a trend and whether the conversion matrix A 1D or the conversion matrix B 1D is adaptively applied to each of the vertical and horizontal directions, higher conversion efficiency can be achieved than in the case where a fixed orthogonal transform, such as DCT, is applied uniformly to prediction modes.

The coefficient order control unit 113 will be described in detail below.

The coefficient order control unit 113 converts the quantized transform coefficients 121, which are a two-dimensional expression, into a sequence 117 of quantized transform coefficients, which is a one-dimensional expression, by arranging the elements of the quantized transform coefficients 121 according to a predetermined order. As an example, coefficient order control unit 113 may perform a general 2D-1D transform regardless of the prediction mode. Specifically, the coefficient order control unit 113 may use a zigzag scan as in the case of H. 264. The zigzag scan arranges the elements of the quantized transform coefficients 121 in the order shown in FIG. 8A, and converts the elements into such a sequence 117 of quantized transform coefficients as shown in FIG. 8B. In FIG. 8A and FIG. 8B, (i, j) denotes the coordinates (position information) of each element in the quantized transform coefficients 121 (matrix). Also in FIG. 2C shows a 2D-1D transformation using a zigzag scan (in the case of a 4 × 4 pixel block). Specifically, in FIG. 8C is an index (idx) indicating the order of the coefficients (scan order) in a sequence 117 of quantized transform coefficients subjected to a 2D-1D transform using a zigzag scan, and corresponding elements (cij) of the quantized transform coefficients 121. In FIG. 8C, cij denotes elements with coordinates (i, j) in the quantized transform coefficients 121 (matrix).

As another example, coefficient order control unit 113 may perform individual 2D-1D transformations for respective prediction modes. The coefficient order control unit 113 performing such an operation is illustrated in FIG. 5A. The coefficient order control unit 113 includes a select switch 501 and individual 2D-1D transform units 502, ..., and 510 for the respective nine types of prediction modes. According to the prediction mode information (for example, the prediction mode indices in FIG. 4A) included in the prediction information 126, the selection switch 501 converts the quantized transform coefficients 121 into a 2D-1D transform block corresponding to the prediction mode (one of the blocks 502, .. ., 510 2D-1D conversion). For example, the prediction mode index 0 enables the selector switch 501 to bring the quantized transform coefficients 121 into a 2D-1D transform block 502. In FIG. 5A, prediction modes and 2D-1D transform blocks are in one-to-one correspondence. The quantized transform coefficients 121 are given in one 2D-1D transform block corresponding to the prediction mode. In FIG. 9 shows a 2D-1D conversion performed by each of the blocks 502, ..., 510 of a 2D-1D conversion (in the case of a 4 × 4 pixel block). A specific design method for 2D-1D conversion for each prediction mode, as shown in FIG. 9 will be described below. In FIG. 9 is an index (idx) indicating the order of the coefficients (scan order) in the sequence 117 of quantized transform coefficients subjected to 2D-1D transform by the 2D-1D transform block, and corresponding elements (cij) of the quantized 121 transform coefficients. In FIG. 9, cij denotes elements with coordinates (i, j) in the quantized transform coefficients 121 (matrix). Also in FIG. 9, each prediction mode is expressed by its name, and the correspondence between the names and the index of the prediction mode is as shown in FIG. 4A. Thus, the use of individual 2D-1D transforms for the respective prediction modes, for example, allows the coefficients to be scanned in the order appropriate for a given trend to generate non-zero coefficients in the quantized transform coefficients 121 for each prediction mode. This increases coding efficiency.

For simplicity, an example is shown regarding a 4x4 pixel block. However, for an 8 × 8 pixel block, a 16 × 16 pixel block, and the like, individual 2D-1D transforms for respective prediction modes can be similarly set. In addition, the block of pixels is a rectangular block expressed as M × N, the size of the block to be subjected to 2D-1D conversion may also be M × N. In this case, for a rectangular block, such individual 2D-1D transformations as illustrated in FIG. 9 can be set for respective prediction modes.

In yet another example, coefficient order control unit 113 may dynamically update the scan order for 2D-1D conversion. The coefficient order control unit 113 performing such an operation is illustrated in FIG. 5B. The coefficient order control unit 113 includes a select switch 501, individual 2D-1D transform units 502, ..., and 510 for the respective nine types of prediction modes, an occurrence frequency calculation unit 511, and a coefficient order update unit 512. The selection switch 501 is as described with reference to FIG. 5A. The individual 2D-1D transform blocks 502, ..., and 510 for the respective nine types of prediction modes are different from the 2D-1D transform blocks shown in FIG. 5A is that the scan order for blocks 502, ..., and 510 2D-1D conversion is updated by block 512 updates the order of the coefficients.

The occurrence frequency calculation unit 511 creates, for each prediction mode, a histogram of the occurrence of nonzero coefficients in each element of the sequence 117 of quantized transform coefficients. The occurrence frequency calculation unit 511 introduces the generated histogram 513 into the coefficient order updating unit 512.

The coefficient order updating unit 512 updates the coefficient order with a predetermined time interval based on histogram 513. The time interval may be, for example, the time interval when the encoding process performed on a unit of the coding tree is completed, or the time interval when the encoding process completed on the one line in a coding tree unit.

Specifically, the coefficient order updating unit 512 refers to a histogram 513 for updating the coefficient order for the prediction mode using an element for which the calculated number of occurrences of non-zero coefficients is equal to or greater than the threshold value. For example, the coefficient order updating unit 512 performs an update for the prediction mode using an element for which the counted number of occurrences of non-zero coefficients is 16 or more. Setting a threshold value for the number of occurrences provides the ability to globally update the order of coefficients, thereby avoiding reduction to a local optimal solution.

Unit 512 updates the order of the coefficients sorts, for the prediction mode of the target update, the elements in order to reduce the frequency of occurrence of non-zero coefficients. Sorting can be achieved according to an existing algorithm, for example, bubble sorting or quick sorting. The coefficient order updating unit 512 inputs coefficient order updating information 514 indicating the sorted order of the elements into the 2D-1D transform unit corresponding to the prediction mode of the update target.

Once the coefficient order updating information 514 is input to the 2D-1D conversion unit, the 2D-1D conversion unit performs 2D-1D conversion in accordance with the updated scan order. If the scan order is dynamically updated, the initial scan orders for the 2D-1D transform blocks must be specified. For example, the zigzag scan or scan order illustrated in FIG. 9 can be used as the initial scan order.

Dynamic updating of the scan order is assumed to achieve consistently high coding efficiency, even if the tendency to generate non-zero coefficients in the quantized transform coefficients 121 varies depending on the nature of the predicted image, quantization information (quantization parameter), and the like. Specifically, the amount of code generated by encoding the length of the series in the entropy encoding unit 114 may be reduced.

For simplicity, H. 264 was illustrated and a case of nine types of prediction modes was described. However, even if the number of prediction mode types is increased to 17, 33 or the like, individual 2D-1D transforms for respective prediction modes can be achieved by adding 2D-1D transform blocks corresponding to the prediction modes resulting from this increase.

The processing performed on the encoding target block (coding tree unit) by the image encoding device in FIG. 1 will be described below with reference to FIG. 10A and FIG. 10B. In the example shown in FIG. 10A and FIG. 10B, it is assumed that orthogonal transformation and inverse orthogonal transformation are allowed according to the present embodiment (that is, adaptive orthogonal transformation and inverse orthogonal transformation based on the information 129 of the determination matrix 1D transformation). However, as described below, syntax may be defined to prohibit orthogonal transformation and inverse orthogonal transformation according to the present embodiment.

Once the input image 118 is input to the image encoding apparatus of FIG. 1 in units of the encoding target block, the encoding process of the encoding target block begins (step S601). The intra prediction unit 108 and the inter prediction unit 109 use the reference image 125 stored in the reference image memory 107 to generate an image predicted by intra prediction and an image predicted by intra prediction (step S602). The encoding control unit 116 determines the optimum prediction mode with respect to the above-described encoding cost to generate prediction information 126 (step S603). Prediction information 126 is input to each element by the prediction selector 110, as described above. If the prediction information 126 generated in step S603 indicates an intra prediction, the processing proceeds to step S605. If the prediction information 126 generated in step S603 indicates an inter prediction, the processing proceeds to step S605 '.

In step S605, the subtracting unit 101 subtracts the image 127 predicted by the (intra) prediction from the encoding target to generate the prediction error 119. Processing then proceeds to step S606. On the other hand, also in step S605 ′, the subtracting unit 101 subtracts the image 127 predicted by the (external) prediction from the encoding target block to generate the prediction error 119. Processing then proceeds to step S614 '.

In step S606, the determining unit 112 of the transformation matrix 1D extracts prediction mode information included in the prediction information 126 generated in step S603. Based on the extracted prediction mode information (for example, referring to the table in FIG. 4A), the transform matrix 1D setting unit 112 generates the transform matrix 1D setting information 129 (step S607). The conversion matrix 1D definition unit 112 converts the conversion matrix information 1D 129 to the orthogonal transform unit 102 and the inverse orthogonal transform unit 105.

The selection switch 201 in the orthogonal transform block 102 selects the orthogonal transform block A 206 1D or the orthogonal transform block B 207 1D based on the setting information 129 of the transform matrix 1D (step S608, step S609 and step S610). On the other hand, the selection switch 204 in the orthogonal transform block 102 selects the orthogonal transform block A 208 1D or the orthogonal transform block B 209 based on the setting information 129 of the transform matrix 1D (step S611, step S612 and step S613). Processing then proceeds to step S614.

For example, if the transformation index (TransformIdx), example information 129 of setting the transformation matrix 1D, 0, the selection switch 201 selects the orthogonal transformation unit A 206 1D in the vertical transformation unit 202 (step S609). If TransformIdx 0, the selection switch 204 selects the orthogonal transform block A 208 1D in the horizontal transform block 205 (step S612). If TransformIdx 1, the select switch 201 selects the orthogonal transform unit A 206 1D in the vertical transform unit 202 (step S609). If TransformIdx 1, the selection switch 204 selects the orthogonal transform block B 209 1D in the horizontal transform block 205 (step S613). If TransformIdx 2, the selection switch 201 selects the orthogonal transform block B 207 1D in the vertical transform block 202 (step S610). If TransformIdx 2, the selection switch 204 selects the orthogonal transform block A 208 1D in the horizontal transform block 205 (step S612). If TransformIdx 3, the selection switch 201 selects the orthogonal transform block B 207 1D in the vertical transform block 202 (step S610). If TransformIdx 3, the selection switch 204 selects the orthogonal transform block B 209 1D in the horizontal transform block 205 (step S613).

In step S614, the orthogonal transform unit 102 performs vertical transform and horizontal transform, which correspond to the tasks made in step S608, ... and step S613 of prediction error 119 for generating transform coefficients 120. Subsequently, the quantization unit 103 quantizes the transform coefficients 120 generated in step S614 (step S615). Processing then proceeds to step S616.

On the other hand, in step S614 ', the orthogonal transform unit 102 performs a fixed orthogonal transform, for example, DCT, prediction errors 119 to generate transform coefficients 120. Subsequently, the quantization unit 103 quantizes the transform coefficients 120 generated in step S614 ′ to generate the quantized transform coefficients 121 (step S615 ′). Processing proceeds to step S617 '. The orthogonal transformation performed in step S614 ′ may be implemented by a DCT block (not shown in the drawings) or an orthogonal transform block B 207 1D and an orthogonal transform block B 209 1D.

In step s616, the coefficient order control unit 113 sets the scanning order (i.e., in the example shown in Fig. 5A and Fig. 5B, the unit to which the select switch 501 is connected) based on the prediction mode information included in the prediction information 126 generated on step S603. Processing proceeds to step S617. If the coefficient order control unit 113 performs a general 2D-1D transform regardless of the prediction mode, step S616 may be omitted.

In step S617, the coefficient order control unit 113 performs a 2D-1D conversion corresponding to the job done in step S616 of the quantized transform coefficients 121 to generate a sequence 117 of quantized transform coefficients. Subsequently, the entropy encoding unit 114 performs entropy encoding of the encoding parameters including a sequence 117 of quantized transform coefficients (step S618). The encoded data is output at an appropriate time interval controlled by the encoding control unit 116. On the other hand, the dequantization unit 104 quantizes the quantized transform coefficients 121 to generate the reconstructed quantized transform coefficients 122 (step S619). Processing proceeds to step S620.

In step S617 ′, the coefficient order control unit 113 performs, for example, a fixed 2D-1D transformation, such as a zigzag scan, or a 2D-1D transformation corresponding to the Intra_NxN_DC in FIG. 9, quantized transform coefficients 121 to generate a sequence of 117 quantized transform coefficients. Subsequently, the entropy encoding unit 114 performs entropy encoding of the encoding parameters including a sequence 117 of quantized transform coefficients (step S618 ′). The encoded data is output at an appropriate time interval controlled by the encoding control unit 116. On the other hand, the dequantization unit 104 quantizes the quantized transform coefficients 121 to generate the reconstructed quantized transform coefficients 122 (step S619 ′). Processing then proceeds to step S626 '.

The selection switch 301 in the inverse orthogonal transform block 105 selects the inverse orthogonal transform block A 306 1D or the inverse orthogonal transform block B 307 1D based on the setting information 129 of the transform matrix 1D (step S620, step S621 and step S622). On the other hand, the selection switch 304 in the inverse orthogonal transform block 105 selects the inverse orthogonal transform block A 308 1D or the inverse orthogonal transform block B 309 1D based on the determination information 129 of the transform matrix 1D (step S623, step S624 and step S625). Processing then proceeds to step S626.

For example, if the transform index (TransformIdx), example information 129 of setting the transformation matrix 1D, 0, the select switch 301 selects the inverse orthogonal transform block A 306 1D in the vertical inverse transform block 302 (step S621). If TransformIdx 0, the selection switch 304 selects the inverse orthogonal transform block A 308 1D in the horizontal inverse transform block 305 (step S624). If TransformIdx 1, the select switch 301 selects the inverse orthogonal transform block A 306 1D in the vertical inverse transform block 302 (step S621). If TransformIdx 1, the selection switch 304 selects the inverse orthogonal transform block B 309 1D in the horizontal inverse transform block 305 (step S625).

If TransformIdx 2, the select switch 301 selects the inverse orthogonal transform block B 307 1D in the vertical inverse transform block 302 (step S622). If TransformIdx 2, the selection switch 304 selects the inverse orthogonal transform block A 308 1D in the horizontal inverse transform block 305 (step S624). If TransformIdx 3, the selection switch 301 selects the inverse orthogonal transform block B 307 1D in the vertical inverse transform block 302 (step S622). If TransformIdx 3, the selection switch 304 selects the inverse orthogonal transform block B 309 1D in the horizontal inverse transform block 305 (step S625).

In step S626, the inverse orthogonal transform unit 105 performs vertical transform and horizontal transform, which correspond to the tasks made in step S620, ... and step S625 of the reconstructed transform coefficients 122 to generate a reconstructed prediction error 123. Processing proceeds to step S627. In step S626 ', the inverse orthogonal transform unit 105 performs inverse orthogonal transform, for example, IDCT, of the reconstructed transform coefficients 122 to generate a reconstructed prediction error 123. Processing then proceeds to step S627. The fixed inverse orthogonal transformation performed in step S626 ′ may be implemented by an IDCT block (not shown in the drawings) or an inverse orthogonal transform block B 307 1D and an inverse orthogonal transform block B 309 1D.

In step S627, the addition unit 106 adds the reconstructed prediction error 123 generated in step S626 or S626 'to the corresponding predicted image 127 to generate a locally decoded image 124. The locally decoded image 124 is stored in the reference image memory 107 as a reference image. Thus, the encoding process of the encoding target block ends (step S628).

A method for designing the transformation matrix A 1D and the transformation matrix B 1D will be described below. According to H. 264, nine types of prediction modes are set for a 4 × 4 pixel block and an 8 × 8 pixel block. Four types of prediction modes are set for a block of 16 × 16 pixels.

First, prediction error 119 is generated for each prediction mode. Those of the prediction errors 119 for the respective prediction modes that exhibit, in the vertical direction or horizontal direction, the above tendency to have an absolute value increasing with distance from the reference pixel are collected. Then, a singular matrix decomposition is performed in which the direction with the tendency manifested in it is set as the column direction, and in which the prediction errors 119 are located in the row direction. Thus, a 1D orthogonal basis is designed that eliminates vertical correlation in the matrix. The 1D orthogonal basis is arranged in the column direction as row vectors to generate the transformation matrix A 1D.

On the other hand, a singular matrix decomposition is performed in which the direction with no tendency shown in it is set as the column direction, and in which the prediction errors 119 are located in the row direction. Thus, a 1D orthogonal basis is generated that eliminates vertical correlation in the matrix. The 1D orthogonal basis is located in the column direction as row vectors to generate the B 1D transform matrix. The B 1D transform matrix can simply be replaced by a matrix for DCT. For simplicity, design was illustrated for a block of 4 × 4 pixels. However, transformation matrices 1D for 8 × 8 pixel blocks and 16 × 16 pixel blocks can be similarly designed. In addition, the above-described design method is illustrative, and design can be carried out if necessary due to the above-described nature of the recorded prediction error.

A specific design method for 2D-1D conversion for each prediction mode (scan order), as illustrated in FIG. 9 will be described below. The scan order for each prediction mode can be designed based on the quantized transform coefficients 121 generated by the quantization unit 103. For example, designing for a 4 × 4 pixel block prepares a plurality of training images to generate prediction error 119 for each of the nine types of prediction modes. The orthogonal transforms shown in Expression (3) and Expression (4) are performed on each prediction error 119 to generate transform coefficients 120. Then, transform coefficients 120 are quantized. In connection with the quantized transform coefficients 121, the number of occurrences of nonzero coefficients is cumulatively added for each of the elements of a 4 × 4 pixel block. Cumulative addition is carried out on all training images to create a histogram indicating the frequency of occurrence of non-zero coefficients for each of the 16 elements of a 4 × 4 pixel block. Based on the histogram, indices from 0 to 15 are assigned to elements in decreasing order of occurrence frequency. Such assignment of indices is individually carried out in all prediction modes. The order of the assigned indices is used as the scan order corresponding to each prediction mode.

For simplicity, a 4 × 4 pixel block design was illustrated. However, scan orders for 8 × 8 pixel blocks and 16 × 16 pixel blocks can be similarly designed. In addition, even if the number of prediction modes is increased to 17, 33, or any other value, this design can be achieved using a similar method. A method for dynamically updating the scan order is described with reference to FIG. 5B.

The syntax used by the image encoding apparatus of FIG. 1 will be described.

The syntax indicates the structure of the encoded data (example, encoded data 130 in FIG. 1) obtained by an image encoding apparatus encoding video data. When the encoded data is decoded, the image decoding apparatus refers to the same data structure for interpreting the syntax. In FIG. 11 illustrates the syntax 700 used by the image encoding apparatus of FIG. one.

Syntax 700 includes three parts, that is, high-level syntax 701, cut-level syntax 702, and coding tree level syntax 703. The high-level syntax 701 includes syntax information at a level higher than clipping. A cut refers to a rectangular region or a continuous region included in a frame or field. The cut-level syntax 702 includes information required to decode each cut. The encoding tree layer syntax 703 includes information required to decode each encoding tree (i.e., each unit of the encoding tree). Each of these parts includes additionally detailed syntax.

The high level syntax 701 includes sequence level syntax and picture level syntax, such as sequence parameter setting syntax 704 and picture parameter setting syntax 705. The cut-level syntax 702 includes the cut header syntax 706 and the cut data syntax 707. The coding tree level syntax 703 includes the coding tree unit syntax 708 and the prediction unit syntax 709.

The syntax 708 units of the coding tree may have the structure of a tetra tree. Specifically, as an element of the syntax syntax 708 of the coding tree unit, the syntax 708 of the coding tree unit may be further recursively involved. That is, one unit of the coding tree can be divided into pieces using tetra trees. In addition, the syntax 708 units of the encoding tree contains the syntax 710 conversion unit. The transform unit syntax 710 is invoked with each syntax 708 of the coding tree unit located at the end of the tetra tree. The transform unit syntax 710 has information on the inverse orthogonal transform, quantization, and the like described therein.

In FIG. 12, the clipping header syntax 706 according to the present embodiment is illustrated. slice_directional_unified_transform_flag shown in FIG. 12 is, for example, a syntax element that indicates whether the orthogonal transform and the inverse orthogonal transform according to the present embodiment are allowed or prohibited for a particular cut.

slice_directional_unified_transform_flag 0 means that the orthogonal transform and inverse orthogonal transform according to the present embodiment are allowed in this clipping. Hence, the orthogonal transform unit 102 and the inverse orthogonal transform unit 105 perform fixed orthogonal and inverse orthogonal transforms, such as DCT and IDCT. The fixed orthogonal transform and inverse orthogonal transform can be performed by the orthogonal transform block B 207 1D, the orthogonal transform block B 209 1D, the inverse orthogonal transform block B 307 1D, and the inverse orthogonal transform block B 209 1D (i.e., by the transform matrix B 1D) or block DCT and IDCT (none of the blocks are shown in the drawings). In addition, the coefficient order control unit 113 performs a fixed 2D-1D transformation (e.g., zigzag scanning). A fixed 2D-1D conversion may be performed by a 2D-1D conversion unit 504 (mode 2) or a 2D-1D conversion unit not shown in the drawings.

By way of example, slice_directional_unified_transform_flag 1 means that the orthogonal transform and inverse orthogonal transform according to the present embodiment are allowed throughout this clipping. That is, the encoding process is carried out in accordance with the above-described encoding flowchart in FIG. 10A and FIG. 10B. That is, the select switch 201 selects the orthogonal transform unit A 206 1D or the orthogonal transform unit B 207 1D based on the information 129 of the definition of the transform matrix 1D. The selection switch 204 selects the orthogonal transform block A 208 1D or the orthogonal transform block B 209 1D based on the information 129 of the definition of the transform matrix 1D. In addition, the select switch 301 selects the inverse orthogonal transform block A 306 1D or the inverse orthogonal transform block B 307 1D based on the information 129 of the definition of the transform matrix 1D. The selection switch 304 selects the inverse orthogonal transform block A 308 1D or the inverse orthogonal transform block B 309 1D based on the information 129 of the set matrix 1D transform. Moreover, the selection switch 501 selects one of the 2D-1D transform units 502, ... and 510 in accordance with the prediction mode information included in the prediction information 126.

In addition, in another example, if slice_directional_unified_transform_flag 1, the syntax in the bottom layer (such as a coding tree unit or transform unit) can be specified to indicate whether orthogonal transform and inverse orthogonal transform according to the present embodiment are allowed or denied for each local region within the clipping .

In FIG. illustrated syntax 708 units of the coding tree according to the present embodiment.

ctb_directional_unified_transform_flag shown in FIG. 13 is a syntax element indicating whether the orthogonal transform and the inverse orthogonal transform according to the present embodiment are allowed or prohibited for a particular coding unit. In addition, pred_mode shown in FIG. 13 is a syntax element included in the prediction unit syntax 709, and indicates a coding type in a coding tree unit or macroblock. MODE_INTRA indicates that the encoding type is intra prediction.

ctb_directional_unified_transform_flag is encoded only when slice_directional_unified_transform_flag 1 is described above, and when the encoding type of the encoding tree unit is an intra prediction.

ctb_directional_unified_transform_flag 0 means that the orthogonal transform and inverse orthogonal transform according to the present embodiment are prohibited in the coding tree unit. Hence, the orthogonal transform unit 102 and the inverse orthogonal transform unit 105 perform fixed orthogonal and inverse orthogonal transforms, such as DCT and IDCT. The fixed orthogonal transform and inverse orthogonal transform can be performed by the orthogonal transform block B 207 1D, the orthogonal transform block B 209 1D, the inverse orthogonal transform block B 307 1D, and the inverse orthogonal transform block B 209 1D (i.e., by the transform matrix B 1D) or block DCT and IDCT (none of the blocks are shown in the drawings). In addition, the coefficient order control unit 113 performs a fixed 2D-1D transformation (e.g., zigzag scanning). A fixed 2D-1D conversion may be performed by a 2D-1D conversion unit 504 (mode 2) or a 2D-1D conversion unit not shown in the drawings.

On the other hand, ctb_directional_unified_transform_flag 1 allows the orthogonal transform and the inverse orthogonal transform according to the present embodiment in a coding unit. Then, the encoding process is carried out in accordance with the above-described encoding flowchart in FIG. 10A and FIG. 10B. That is, the select switch 201 selects the orthogonal transform unit A 206 1D or the orthogonal transform unit B 207 1D based on the information 129 of the definition of the transform matrix 1D. The selection switch 204 selects the orthogonal transform block A 208 1D or the orthogonal transform block B 209 1D based on the information 129 of the definition of the transform matrix 1D. In addition, the select switch 301 selects the inverse orthogonal transform block A 306 1D or the inverse orthogonal transform block B 307 1D based on the information 129 of the definition of the transform matrix 1D. The selection switch 304 selects the inverse orthogonal transform block A 308 1D or the inverse orthogonal transform block B 309 1D based on the information 129 of the set matrix 1D transform. Moreover, the selection switch 501 selects one of the 2D-1D transform units 502, ... and 510 in accordance with the prediction mode information included in the prediction information 126.

When a flag specifying whether orthogonal transformation and inverse orthogonal transformation according to the present embodiment is enabled or disabled is encoded in the syntax 708 of a coding tree unit, as in the example of FIG. 13, the amount of information (code amount) is increased compared to when the flag is not encoded. However, flag coding allows optimal orthogonal transformations to be performed for each local area (i.e., for each unit of the coding tree).

In FIG. 14 illustrates a transform unit syntax 710 according to the present embodiment.

tu_directional_unified_transform_flag shown in FIG. 14 is a syntax element indicating whether the orthogonal transformation and the inverse orthogonal transformation according to the present embodiment are allowed or prohibited for a particular transformation unit. In addition, pred_mode shown in FIG. 14 is a syntax element included in the prediction unit syntax 709 and indicates a coding type in a particular coding tree unit or macroblock. MODE_INTRA indicates that the encoding type is intra prediction.

tu_directional_unified_transform_flag is encoded only when slice_directional_unified_transform_flag 1 is described above, and when the encoding type of the encoding tree unit is an intra prediction.

tu_directional_unified_transform_flag 0 prohibits orthogonal transformation and inverse orthogonal transformation according to the present embodiment in the transformation unit. Hence, the orthogonal transform unit 102 and the inverse orthogonal transform unit 105 perform fixed orthogonal and inverse orthogonal transforms, such as DCT and IDCT. The fixed orthogonal transform and inverse orthogonal transform can be performed by the orthogonal transform block B 207 1D, the orthogonal transform block B 209 1D, the inverse orthogonal transform block B 307 1D, and the inverse orthogonal transform block B 209 1D (i.e., by the transform matrix B 1D) or block DCT and IDCT (none of the blocks are shown in the drawings). In addition, the coefficient order control unit 113 performs a fixed 2D-1D transformation (e.g., zigzag scanning). A fixed 2D-1D conversion may be performed by a 2D-1D conversion unit 504 (mode 2) or a 2D-1D conversion unit not shown in the drawings.

On the other hand, tu_directional_unified_transform_flag 1 allows the orthogonal transform and inverse orthogonal transform according to the present embodiment in a transform unit. Then, the encoding process is carried out in accordance with the above-described encoding flowchart in FIG. 10A and FIG. 10B. That is, the select switch 201 selects the orthogonal transform unit A 206 1D or the orthogonal transform unit B 207 1D based on the information 129 of the definition of the transform matrix 1D. The selection switch 204 selects the orthogonal transform block A 208 1D or the orthogonal transform block B 209 1D based on the information 129 of the definition of the transform matrix 1D. In addition, the select switch 301 selects the inverse orthogonal transform block A 306 1D or the inverse orthogonal transform block B 307 1D based on the information 129 of the definition of the transform matrix 1D. The selection switch 304 selects the inverse orthogonal transform block A 308 1D or the inverse orthogonal transform block B 309 1D based on the information 129 of the set matrix 1D transform. Moreover, the selection switch 501 selects one of the 2D-1D transform units 502, ... and 510 in accordance with the prediction mode information included in the prediction information 126.

When a flag specifying whether orthogonal transform and inverse orthogonal transform according to the present embodiment is enabled or disabled is encoded in transform unit syntax 710 as in the example of FIG. 14, the amount of information (code amount) is increased compared to when the flag is not encoded. However, flag coding allows optimal orthogonal transformations to be performed for each local area (i.e., for each transform unit).

Syntax elements not defined according to the present embodiment or descriptions of other conditional branches may be inserted between rows in the syntax tables illustrated in FIG. 12, FIG. 13 and FIG. 14. In addition, the syntax table may be divided into a plurality of tables, or the plurality of syntax tables may be unified. Additionally, illustrated terms for syntax elements may be optionally changed.

As described above, the image encoding apparatus according to the present embodiment uses the intra prediction trend to have prediction accuracy decreasing with increasing distance from the reference pixel. The image encoding device classifies the vertical and horizontal directions of the prediction modes into two classes, depending on whether or not this trend is present. The image encoding apparatus further adaptively applies the transform matrix A 1D or the transform matrix matrix B 1D to each of the vertical and horizontal directions. The transformation matrix A 1D of the transformation is generated by preliminary designing a common transformation basis in order to increase the coefficient density after 1D orthogonal transformation (that is, to reduce the proportion of non-zero coefficients in the quantized transformation coefficients 121) in the direction orthogonal to the line of the reference pixel group (vertical direction and horizontal direction ) On the other hand, the transformation matrix B 1D is generated by designing a general-purpose transformation matrix that is not of this nature. For example, a general purpose transformation is DCT. Hence, the image encoding apparatus according to the present embodiment achieves a high conversion efficiency compared to the case where a fixed orthogonal transformation, such as DCT, is applied uniformly to the prediction modes.

In addition, the orthogonal transform unit 102 and the inverse orthogonal transform unit 105 according to the present embodiment are suitable for both a hardware implementation and a software implementation.

Expressions (3) by Expression (6) express the multiplications of fixed matrices. Thus, when the orthogonal transform block and the inverse orthogonal transform block are implemented by hardware, it is assumed that the implementation is configured using circuit-implemented logic instead of multiplying devices.

If a dedicated transform basis is used for each of the nine types of intra-prediction modes to perform orthogonal transform and inverse orthogonal transform, you need to prepare nine 2D orthogonal transform blocks or prepare 18 (= 9 × 2) orthogonal transform blocks 1D as shown in FIG. 15. Nine 2D orthogonal transform blocks or 18 orthogonal transform blocks 1D multiply different transform matrices. As a result, in addition to the dedicated DCT hardware required for H. 264, nine orthogonal transform 2D blocks or 18 orthogonal transform blocks 1D are additionally provided. This increases the scale of the relevant schemas.

On the other hand, as shown in FIG. 2 and FIG. 3, the orthogonal transform unit and the inverse orthogonal transform unit according to the present embodiment uses a combination of two (if the vertical (inverse) transform unit and the horizontal (inverse) transform unit are shared with time division) orthogonal transform units 1D with a circuit for transposing a matrix, to implement four types of two-dimensional orthogonal transforms. Hence, the orthogonal transform block and the inverse orthogonal transform block according to the present embodiment provide the possibility of significantly suppressing the magnification in the scale of the circuits in hardware implementation.

In addition, if a dedicated transform basis is used for each of the nine types of intra prediction modes to perform orthogonal transform and inverse orthogonal transform, the software implementation is assumed to be as follows. Nine 2D orthogonal transform matrices or 18 (= 9 × 2) 1D orthogonal transform matrices are stored in memory. Each of the transformation matrices is used for the corresponding one of the prediction modes, orthogonal transformation is implemented using a general purpose multiplication device. This can increase the size of the memory into which the transformation matrices are stored, and thus the expense, and also increase the throughput of the memory as a result of loading the transformation matrix into the memory for each transformation.

On the other hand, the orthogonal transform unit and the inverse orthogonal transform unit according to the present embodiment combines the vertical transform and the horizontal transform using transform matrices 1D to carry out four types of orthogonal transforms. Thus, the orthogonal transform unit and the inverse orthogonal transform unit according to the present embodiment make it possible to significantly suppress the increase in memory size in a software implementation.

In addition, the preparation of individual scan orders for the respective prediction modes, as described in the present embodiment, improves coding efficiency. The quantized transform coefficients 121 show that the tendency to generate nonzero coefficients shifts depending on the element. The trend for generating nonzero coefficients varies depending on the direction of prediction of the intra prediction. Moreover, with the same prediction direction, even encoding blocks of pixels from different input images 118 leads to similar trends for generating nonzero coefficients. Hence, when the coefficient order control unit 113 converts the elements into corresponding sequences of 122 one-dimensional quantized transform coefficients in order of decreasing the probability of occurrence of non-zero coefficients in the quantized 121 transform coefficients, non-zero coefficients very likely densely appear in the sequence 122 of quantized transform coefficients. This allows a reduction in the amount of code generated as a result of encoding the length of the series in the entropy encoding unit 114. As described with reference to FIG. 5A and FIG. 5B, the coefficient order control unit 113 may invariably use the scan orders studied for the respective prediction modes, or use the scan order dynamically updated during the encoding process. Using scan orders optimized for the respective prediction modes, entropy encoding unit 114 can reduce, compared to H. 264, the amount of generated code based on a sequence of 122 quantized transform coefficients without significantly increasing the amount of computation.

(SECOND EMBODIMENT)

The image encoding apparatus according to the second embodiment is different from the image encoding apparatus according to the first embodiment in the details of the orthogonal transform and inverse orthogonal transform. The same components of the present embodiment, as the corresponding components of the first embodiment, are hereinafter denoted by the same reference numbers, and basically the different components will be described below. An image decoding apparatus corresponding to an image encoding apparatus according to the present embodiment will be described in the fifth embodiment.

Instead of the orthogonal transform block 102 illustrated in FIG. 2, the image encoding apparatus according to the present embodiment includes the orthogonal transform unit 102 illustrated in FIG. 16. The orthogonal transform unit 102 of FIG. 16 includes a select switch 801, a vertical transform unit 802, a transpose unit 203, a select switch 804, and a horizontal transform unit 805. The vertical transform unit 802 includes an orthogonal transform block C 806 1D, an orthogonal transform block D 807 1D, and an orthogonal transform block E 808 1D. The horizontal transform block 805 includes an orthogonal transform block C 809 1D, an orthogonal transform block D 810 1D, and an orthogonal transform block E 811 1D. The order of the vertical transform unit 802 and the horizontal transform unit 805 is illustrative and may be inverse.

The orthogonal transform block C 806 1D and the orthogonal transform block C 809 1D have common functions in that both blocks multiply the input matrix by the transform matrix C 1D. The orthogonal transform block D 807 1D and the orthogonal transform block D 810 1D have common functions in that both blocks multiply the input matrix by the transform matrix D 1D. The orthogonal transform block E 808 1D and the orthogonal transform block E 811 1D have common functions in that both blocks multiply the input matrix by the transform matrix E 1D.

The conversion matrix C 1D, the conversion matrix D 1D, and the conversion matrix E 1D according to the present embodiment will be described below.

As described above, prediction error 119 tends to have an absolute value increasing with distance from the reference pixel. This trend is similarly manifested regardless of the direction of prediction. However, the prediction error in the DC prediction mode does not tend in the vertical direction or in the horizontal direction. The present invention uses the transformation matrix E 1D described below for the DC prediction mode. For prediction modes other than the DC prediction mode, the present embodiment adaptively uses a transformation matrix C 1D and a transformation matrix D 1D depending on whether a trend is present, as is the case with the first embodiment.

Specifically, the C 1D transform matrix can be generated using the same design method as the design method for the above described A 1D transform matrix. Moreover, the transformation matrix D 1D can be generated using a design method similar to the design method for the above-described transformation matrix B 1D. That is, the transform matrix D 1D can be generated by implementing a design method for the transform matrix B 1D with the DC prediction mode included.

The transformation matrix E 1D may be a matrix for DCT. Alternatively, the transformation matrix E 1D can be generated by preliminary designing a common transformation basis in order to increase, in comparison with the transformation matrix D 1D, the coefficient density after 1D orthogonal transformation (i.e., to reduce the proportion of non-zero coefficients in the quantized transformation coefficients 121) in the vertical direction and horizontal direction.

Instead of the inverse orthogonal transform unit 105 illustrated in FIG. 3, the image encoding apparatus according to the present embodiment includes an inverse orthogonal transform unit 105 illustrated in FIG. 17. The inverse orthogonal transform unit 105 of FIG. 17 includes a select switch 901, a vertical inverse transform unit 902, a transpose unit 303, a select switch 904 and a horizontal inverse transform unit 905. The vertical inverse transform unit 902 includes an inverse orthogonal transform block C 906 1D, an inverse orthogonal transform block D 907 1D, and an inverse orthogonal transform block E 908 1D. The horizontal inverse transform unit 905 includes an inverse orthogonal transform block C 909 1D, an inverse orthogonal transform block D 910 1D, and an inverse orthogonal transform block E 911 1D. The order of the vertical inverse transform unit 902 and the horizontal inverse transform unit 905 is illustrative and may be inverse.

The inverse orthogonal transform block C 906 1D and the inverse orthogonal transform block C 909 1D have common functions in that both blocks multiply the input matrix by the transposed matrix of the C 1D transform matrix. The inverse orthogonal transform block D 907 1D and the inverse orthogonal transform block D 910 1D have common functions in that both blocks multiply the input matrix by the transposed matrix of the transform matrix D 1D. The inverse orthogonal transform block E 908 1D and the inverse orthogonal transform block E 911 1D have common functions in that both blocks multiply the input matrix by the transposed matrix of the transform matrix E 1D.

The setting information 129 of the transformation matrix 1D according to the present embodiment, generated by the setting unit 112 of the transformation matrix 1D, will be described in detail below.

The mapping matrix 1D information 129 of the transform matrix 1D directly or indirectly indicates a vertical transform index for selecting a transform matrix for use in vertical orthogonal transform and vertical inverse orthogonal transform, and a horizontal transform index for selecting a transform matrix for use in horizontal orthogonal transform and horizontal inverse orthogonal transform. For example, the job information 129 of the transform matrix 1D may be expressed by the transform index (TrasformIdx) shown in FIG. 18D. The reference to the table in FIG. 18D provides the ability to obtain a vertical transform index (Idx vertical transform) and a horizontal transform index (Idx horizontal transform) from the transform index.

As shown in FIG. 18B, the vertical transformation index “0” allows selection of the above-described transformation matrix C 1D transformation (1D_Transform_Matrix_C) or its transposed matrix for vertical orthogonal transformation or vertical inverse orthogonal transformation. On the other hand, the vertical transformation index “1” allows the selection of the above-described transformation matrix D 1D (1D_Transform_Matrix_D) or its transposed matrix for vertical orthogonal transformation or vertical inverse orthogonal transformation. Moreover, the vertical transformation index “2” allows the selection of the above-described transformation matrix E 1D (1D_Transform_Matrix_E) or its transposed matrix for vertical orthogonal transformation or vertical inverse orthogonal transformation.

As shown in FIG. 18C, the horizontal transform index “0” allows the selection of the C 1D transform matrix (1D_Transform_Matrix_C) or its transposed matrix for horizontal orthogonal transform or horizontal inverse orthogonal transform. On the other hand, the horizontal transformation index “1” allows the selection of the transformation matrix D 1D (1D_Transform_Matrix_D) or its transposed matrix for horizontal orthogonal transformation or horizontal inverse orthogonal transformation. Moreover, the horizontal transformation index “2” allows the selection of the transformation matrix E 1D (1D_Transform_Matrix_E) or its transposed matrix for horizontal orthogonal transformation or horizontal inverse orthogonal transformation.

Also in FIG. 18A, an index for each (intra) prediction mode (IntraN × NPredModeIndex), its name (IntraN × NPredMode name), and the corresponding vertical transform index and horizontal transform index are illustrated. In FIG. 18A "N × N" indicates the size of the prediction target block (N = 4, 8, 16 or the like). The size of the prediction target block can be expanded to “M × N” (that is, rectangles instead of squares).

In FIG. 18E is obtained by combining FIG. 18A and FIG. 18D together and shows an index for each prediction mode, a prediction mode name, and a corresponding transform index.

The block 112 setting matrix 1D conversion detects the index of the prediction mode in the information of the prediction mode included in the information 126 prediction. Block 112 specify the matrix 1D conversion then generates the corresponding information 129 of the task matrix 1D conversion. The tables shown in FIG. 18A, FIG. 18B, FIG. 18C, FIG. 18D and FIG. 18E are illustrative. The conversion matrix 1D transformation unit 112 may generate the conversion matrix 1D information 129 of the transformation matrix, while avoiding the use of some or all of the tables.

For example, a TransformIdx indicating 0 means that the vertical transform index indicates 0, and that the horizontal transform index indicates 0. This means that the transform matrix C 1D is used for vertical orthogonal transforms, and that the transform matrix C 1D is used for horizontal orthogonal transforms. These values also mean that the transposed matrix of the transformation matrix C 1D is used for vertical inverse orthogonal transformation, and that the transposed matrix of the transformation matrix C 1D is used for horizontal inverse orthogonal transformation.

A TransformIdx indicating 1 means that the vertical transformation index indicates 0, and that the horizontal transformation index indicates 1. This means that the transformation matrix C 1D is used for vertical orthogonal transformation, and that the transformation matrix D 1D is used for horizontal orthogonal transformation. These values also mean that the transposed matrix of the transformation matrix C 1D is used for vertical inverse orthogonal transformation, and that the transposed matrix of the transformation matrix D 1D is used for horizontal inverse orthogonal transformation.

TransformIdx indicating 2 means that the vertical transformation index indicates 1, and that the horizontal transformation index indicates 0. This means that the transformation matrix D 1D is used for vertical orthogonal transformation, and that the transformation matrix C 1D is used for horizontal orthogonal transformation. These values also mean that the transposed matrix of the transformation matrix D 1D is used for vertical inverse orthogonal transformation, and that the transposed matrix of the transformation matrix C 1D is used for horizontal inverse orthogonal transformation.

TransformIdx indicating 3 means that the vertical transformation index indicates 2, and that the horizontal transformation index indicates 2. This means that the transformation matrix E 1D is used for vertical orthogonal transformation, and that the transformation matrix E 1D is used for horizontal orthogonal transformation. These values also mean that the transposed matrix of the transformation matrix E 1D is used for vertical inverse orthogonal transformation, and that the transposed matrix of the transformation matrix E 1D is used for horizontal inverse orthogonal transformation.

Here, if the prediction target block is a rectangular block expressed as M × N, the size of the block to be converted orthogonally can also be M × N.

The table shown in FIG. 18A, assigns setting information 129 of the transform matrix 1D, given the above trend of each intra prediction mode. That is, for DC prediction mode 2, both a vertical transform index and a horizontal transform index are assigned. Hence, for the DC prediction mode, the orthogonal transform and the inverse orthogonal transform are performed in the vertical direction and the horizontal direction using the transform matrix E 1D and its transposed matrix. As a result, high conversion efficiency is achieved.

For prediction modes other than the DC prediction mode, 0 is assigned to the vertical transform index if the trend appears in the vertical direction of the prediction error. 0 is assigned to the horizontal transformation index if the trend appears in the horizontal direction of the prediction error. On the other hand, 1 is assigned to each of the directions that do not show a trend. High conversion efficiency is achieved by classifying the vertical and horizontal directions of the prediction modes other than the DC prediction mode into two classes depending on whether there is a trend, and adaptively applying the transformation matrix C 1D or the transformation matrix D 1D to the vertical and horizontal directions.

As described above, the image encoding apparatus according to the present embodiment uses the tendency of intra prediction to have decreasing prediction accuracy with increasing distance from the reference pixel, as in the case of the first embodiment, while applying orthogonal transform and inverse orthogonal transform to DC prediction in a specific way, different from the course of action for other prediction modes. The image encoding device classifies the vertical and horizontal directions of the prediction modes into two classes depending on whether there is a trend, and adaptively applies the transformation matrix C 1D or the transformation matrix D 1D to the vertical and horizontal directions. The image encoding apparatus applies the transform matrix E 1D to the DC prediction mode. The C 1D transform matrix is generated by preliminary designing a common transform basis in order to increase the coefficient density after 1D orthogonal transform (i.e., to reduce the fraction of non-zero coefficients in the quantized transform coefficients 121) in the direction orthogonal to the line of the reference pixel group (vertical and horizontal direction). The transformation matrix D 1D is generated by designing a general-purpose transformation matrix that is not of this nature with the DC prediction mode included. The transformation matrix E 1D may be a matrix for DCT. Alternatively, the transform matrix E 1D is generated by preliminary designing a common transform basis in order to increase, for prediction error 119 in DC prediction mode, the coefficient density after 1D orthogonal transform (i.e., to reduce the proportion of non-zero coefficients in quantized transform coefficients 121) in the vertical direction and horizontal direction. Hence, the image encoding apparatus according to the present embodiment achieves higher conversion efficiency than in the case where a fixed orthogonal transformation, such as DCT, is applied uniformly to the prediction modes.

(THIRD EMBODIMENT)

The image encoding device according to the third embodiment differs from the image encoding devices according to the first embodiment and the second embodiment in the details of the orthogonal transform and the inverse orthogonal transform. The same components of the present embodiment, as the corresponding components of the first embodiment and the second embodiment, are hereinafter denoted by the same reference numbers, and basically the different components will be described below. An image decoding apparatus corresponding to an image encoding apparatus according to the present embodiment will be described in the sixth embodiment.

Instead of the orthogonal transform block 102 illustrated in FIG. 2, the image encoding apparatus according to the present embodiment includes the orthogonal transform unit 102 illustrated in FIG. 19. The orthogonal transform unit 102 of FIG. 19 includes a select switch 1201, a vertical transform unit 1202, a transpose unit 203, a select switch 1204, and a horizontal transform unit 1205. The vertical transform unit 1202 includes an orthogonal transform unit F 1206 1D, the orthogonal transform unit G 1207 1D, and the orthogonal transform unit H 1208 1D. The horizontal transform block 1205 includes an orthogonal transform block F 1209 1D, an orthogonal transform block G 1210 1D, and an orthogonal transform block H 1211 1D. The order of the vertical transform unit 1202 and the horizontal transform unit 1205 is illustrative and may be inverse.

The orthogonal transform block F 1206 1D and the orthogonal transform block F 1209 1D have common functions in that both blocks multiply the input matrix by the transform matrix F 1D. The orthogonal transform block G 1207 1D and the orthogonal transform block G 1210 1D have common functions in that both blocks multiply the input matrix by the transform matrix G 1D. The orthogonal transform block H 1208 1D and the orthogonal transform block H 1211 1D have common functions in that both blocks multiply the input matrix by the transform matrix H 1D.

The conversion matrix F 1D, the conversion matrix G 1D, and the conversion matrix H 1D according to the present embodiment will be described below.

As described above, prediction error 119 tends to have an absolute value increasing with distance from the reference pixel. This trend is similarly manifested regardless of the direction of prediction. However, intra prediction modes include prediction modes in which they refer (reference pixel values are copied, or interpreted using reference pixel values) only to a group of reference pixels on a line to the left of and next to the prediction target block, or on a line placed above and next to the prediction target block, and prediction modes that refer to reference pixel groups on a line located to the left of and next to the prediction target block, and on a line placed yshe and adjacent to the prediction target block. The way in which this tendency manifests itself varies between a prediction mode for which only a group of reference pixels on one line are referenced and a prediction mode for which only a group of reference pixels on two lines are referenced. Thus, the present embodiment performs orthogonal conversion and inverse orthogonal conversion differently between prediction modes that refer only to a group of reference pixels on one line and prediction modes that refer only to groups of reference pixels on two lines.

Specifically, the H 1D transform matrix described below is used for prediction modes in which reference pixel groups on two lines are referenced. On the other hand, the transformation matrix F 1D and the transformation matrix G 1D are adaptively used for prediction modes in which only a group of reference pixels on one line are referenced, depending on whether a trend is present, as is the case with the first embodiment.

Specifically, the transformation matrix F 1D can be generated using a design method similar to the design method for the above-described transformation matrix A 1D. In addition, the transformation matrix F 1D can be generated by implementing the design method for the above transformation matrix A 1D, while at the same time excluding prediction modes that refer to groups of pixels on two lines (for example, mode 4, mode 5 and mode 6 on Fig. 7A). In addition, the transformation matrix G 1D can be generated using the same design method as the design method for the above described transformation matrix B 1D. Alternatively, the transformation matrix G 1D may be a matrix for DCT.

The H 1D transform matrix can be generated by pre-designing a common transform basis in order to increase, for prediction error 119 in prediction modes that refer to pixel groups on two lines, the coefficient density after 1D orthogonal transform (i.e., to reduce the fraction nonzero coefficients in quantized transform coefficients 121) in the vertical direction and horizontal direction.

Instead of the inverse orthogonal transform unit 105 illustrated in FIG. 3, the image encoding apparatus according to the present embodiment includes an inverse orthogonal transform unit 105 illustrated in FIG. 20. The inverse orthogonal transform unit 105 of FIG. 20 includes a select switch 1301, a vertical inverse transform unit 1302, a transpose unit 303, a select switch 1304, and a horizontal inverse transform unit 1305. The vertical inverse transform unit 1302 includes an inverse orthogonal transform block F 1306 1D, an inverse orthogonal transform block G 1307 1D, and an inverse orthogonal transform block H 1308 1D. The horizontal inverse transform unit 1305 includes an inverse orthogonal transform block F 1309 1D, an inverse orthogonal transform block G 1310 1D, and an inverse orthogonal transform block H 1311 1D. The order of the vertical inverse transform unit 1302 and the horizontal inverse transform unit 1305 is illustrative and may be inverse.

The inverse orthogonal transform block F 1306 1D and the inverse orthogonal transform block F 1309 1D have common functions in that both blocks multiply the input matrix by the transposed matrix of the transform matrix F 1D. The inverse orthogonal transform block G 1307 1D and the inverse orthogonal transform block G 1310 1D have common functions in that both blocks multiply the input matrix by the transposed matrix of the G 1D transform matrix. The inverse orthogonal transform block H 1308 1D and the inverse orthogonal transform block H 1311 1D have common functions in that both blocks multiply the input matrix by the transposed matrix of the H 1D transform matrix.

The setting information 129 of the transformation matrix 1D according to the present embodiment, generated by the setting unit 112 of the transformation matrix 1D, will be described in detail below.

The mapping matrix 1D information 129 of the transform matrix 1D directly or indirectly indicates a vertical transform index for selecting a transform matrix for use in vertical orthogonal transform and vertical inverse orthogonal transform, and a horizontal transform index for selecting a transform matrix for use in horizontal orthogonal transform and horizontal inverse orthogonal transform. For example, the job information 129 of the transform matrix 1D may be expressed by the transform index (TrasformIdx) shown in FIG. 21D. The reference to the table in FIG. 21D provides the ability to obtain a vertical conversion index (Idx vertical conversion) and a horizontal conversion index (Idx horizontal conversion) from the conversion index.

As shown in FIG. 21B, the vertical transformation index “0” allows selection of the above-described transformation matrix F 1D transformation (1D_Transform_Matrix_F) or its transposed matrix for vertical orthogonal transformation or vertical inverse orthogonal transformation. On the other hand, the vertical transformation index “1” allows the selection of the above-described transformation matrix G 1D (1D_Transform_Matrix_G) or its transposed matrix for vertical orthogonal transformation or vertical inverse orthogonal transformation. Moreover, the vertical transformation index "2" allows you to select the above matrix H 1D transformation (1D_Transform_Matrix_H) or its transposed matrix for vertical orthogonal transformation or vertical inverse orthogonal transformation.

As shown in FIG. 21C, the horizontal transformation index “0” allows the selection of the transformation matrix F 1D (1D_Transform_Matrix_F) or its transposed matrix for horizontal orthogonal transformation or horizontal inverse orthogonal transformation. On the other hand, the horizontal transformation index “1” allows the selection of the transformation matrix G 1D (1D_Transform_Matrix_G) or its transposed matrix for horizontal orthogonal transformation or horizontal inverse orthogonal transformation. Moreover, the horizontal transformation index “2” allows the selection of the transformation matrix H 1D (1D_Transform_Matrix_H) or its transposed matrix for horizontal orthogonal transformation or horizontal inverse orthogonal transformation.

Also in FIG. 21A, an index for each (intra) prediction mode (IntraN × NPredModeIndex), its name (IntraN × NPredMode name), and the corresponding vertical transform index and horizontal transform index are illustrated. In FIG. 21A, “N × N” indicates the size of the prediction target block (N = 4, 8, 16 or the like). The size of the prediction target block can be expanded to “M × N” (that is, rectangles instead of squares).

In FIG. 21E is obtained by combining FIG. 21A and FIG. 21D together and shows an index for each prediction mode, an index name, and a corresponding transform index.

The block 112 setting matrix 1D conversion detects the index of the prediction mode in the information of the prediction mode included in the information 126 prediction. Block 112 specify the matrix 1D conversion then generates the corresponding information 129 of the task matrix 1D conversion. The tables shown in FIG. 21A, FIG. 21B, FIG. 21C, FIG. 21D and FIG. 21E are illustrative. The conversion matrix 1D transformation unit 112 may generate the conversion matrix 1D information 129 of the transformation matrix, while avoiding the use of some or all of the tables.

For example, a TransformIdx indicating 0 means that the vertical transform index indicates 2, and that the horizontal transform index indicates 2. This means that the transform matrix H 1D is used for vertical orthogonal transforms, and that the transform matrix H 1D is used for horizontal orthogonal transforms. These values also mean that the transposed matrix of the transformation matrix H 1D is used for vertical inverse orthogonal transformation, and that the transposed matrix of the transformation matrix H 1D is used for horizontal inverse orthogonal transformation.

A TransformIdx indicating 1 means that the vertical transformation index indicates 0, and that the horizontal transformation index indicates 1. This means that the transformation matrix F 1D is used for vertical orthogonal transformation, and that the transformation matrix G 1D is used for horizontal orthogonal transformation. These values also mean that the transposed matrix of the transformation matrix F 1D is used for vertical inverse orthogonal transformation, and that the transposed matrix of the transformation matrix G 1D is used for horizontal inverse orthogonal transformation.

TransformIdx indicating 2 means that the vertical transformation index indicates 1, and that the horizontal transformation index indicates 0. This means that the transformation matrix G 1D is used for vertical orthogonal transformation, and that the transformation matrix F 1D is used for horizontal orthogonal transformation. These values also mean that the transposed matrix of the transformation matrix G 1D is used for vertical inverse orthogonal transformation, and that the transposed matrix of the transformation matrix F 1D is used for horizontal inverse orthogonal transformation.

A TransformIdx indicating 3 means that the vertical transformation index indicates 1, and that the horizontal transformation index indicates 1. This means that the transformation matrix G 1D is used for vertical orthogonal transformation, and that the transformation matrix G 1D is used for horizontal orthogonal transformation. These values also mean that the transposed matrix of the transformation matrix G 1D is used for vertical inverse orthogonal transformation, and that the transposed matrix of the transformation matrix G 1D is used for horizontal inverse orthogonal transformation.

Here, if the prediction target block is a rectangular block expressed as M × N, the size of the block to be converted orthogonally can also be M × N.

The table shown in FIG. 21A, assigns setting information 129 of the transform matrix 1D, given the above trend of each intra prediction mode. That is, for prediction modes in which reference pixel groups on two lines are referenced, 2 is assigned both a vertical transformation index and a horizontal transformation index. Hence, for prediction modes in which reference pixel groups on two lines are referenced, orthogonal transformation and inverse orthogonal transformation are performed in the vertical direction and the horizontal direction using the transform matrix H 1D and its transposed matrix. As a result, high conversion efficiency is achieved.

For prediction modes other than prediction modes in which reference pixel groups on two lines are referenced, 0 is assigned a vertical transformation index if the trend appears in the vertical direction of the prediction error. 0 is assigned to the horizontal transformation index if the trend appears in the horizontal direction of the prediction error. On the other hand, 1 is assigned to each of the directions that do not show a trend. High conversion efficiency is achieved by classifying the vertical and horizontal directions of the prediction modes other than the prediction modes in which reference pixel groups on two lines are referenced, into two classes depending on whether a trend is present, and adaptively applying the transformation matrix F 1D or the matrix G 1D conversion to vertical and horizontal directions.

As described above, the image encoding apparatus according to the present embodiment uses the tendency of intra prediction to have decreasing prediction accuracy with increasing distance from the reference pixel, as in the case of the first embodiment, while applying orthogonal transform and inverse orthogonal transform to prediction modes in a certain way varying depending on the number of lines corresponding to groups of reference pixels. The image encoding device classifies the vertical and horizontal directions of the prediction modes other than the prediction modes, which refer to reference pixel groups on two lines, into two classes depending on whether a trend is present, and adaptively applies the transformation matrix F 1D or the matrix G 1D conversions to vertical and horizontal directions. On the other hand, the image encoding device uses the matrix H 1D conversion in prediction modes, which refer to groups of reference pixels on two lines. For prediction modes that refer only to a group of reference pixels on one line, the transformation matrix F 1D is generated by preliminary designing a common transformation basis in order to increase the coefficient density after 1D orthogonal transformation (that is, to reduce the fraction of non-zero coefficients in the quantized coefficients 121 transformations) in a direction orthogonal to a line of a group of reference pixels (vertical direction and horizontal direction). On the other hand, the transformation matrix G 1D is generated by designing a general-purpose transformation matrix that is not of this nature. Moreover, the H 1D transform matrix is generated by preliminary designing a common transform basis in order to increase, for prediction error 119 in each prediction mode, for which pixel groups on two lines are referenced, the coefficient density after 1D orthogonal transform (i.e., so that reduce the proportion of nonzero coefficients in the quantized transform coefficients 121) in the vertical direction and horizontal direction. Hence, the image encoding apparatus according to the present embodiment achieves higher conversion efficiency than in the case where a fixed orthogonal transformation, such as DCT, is applied uniformly to the prediction modes.

The first and third embodiments prepare two or three types of transform matrices 1D and select one of the transform matrices 1D for vertical transform (or vertical inverse transform) and horizontal transform (or horizontal inverse transform) according to the prediction mode. However, the above two or three types of 1D transformation matrices are illustrative. Coding efficiency can be increased by preparing more transformation matrices. For example, a second embodiment and a third embodiment can be combined together to prepare four types of 1D transformation matrices. However, the increased number of types of prepared transformation matrices requires additional hardware or the like. Thus, it is desirable to consider the balance between coding efficiency and disadvantages resulting from the increased number of types of transformation matrices.

(FOURTH EMBODIMENT)

A fourth embodiment relates to an image decoding apparatus. An image encoding apparatus corresponding to an image decoding apparatus according to the present embodiment is described in the first embodiment. That is, the image decoding apparatus according to the present embodiment decodes the encoded data generated, for example, by the image encoding apparatus according to the first embodiment.

As shown in FIG. 22, the image decoding apparatus according to the present embodiment includes an input buffer 401, an entropy decoding unit 402, a coefficient order control unit 403, a dequantization unit 404, an inverse orthogonal transform unit 405, an addition unit 406, a reference image memory 407, an intra prediction unit 408, an inter prediction unit 409, a select switch 410, a transform matrix 1D block 411, and an output buffer 412.

The image decoding apparatus of FIG. 22 decodes the encoded data in the input buffer 401, accumulates the decoded image 419 in the output buffer 412, and outputs the decoded image 419 as the output image 425. The encoded data 414 is output, for example, by the image encoding device in FIG. 1, and temporarily accumulates in the input buffer 401 by means of an accumulation system or transmission system (not shown in the drawings).

In order to decode the encoded data 414, the entropy decoding unit 402 decodes each frame or field based on syntax. Entropy decoding unit 402 subjects each code sequence for entropy decoding to reproduce encoding parameters for encoding the encoding target block, such as prediction information 424 including prediction mode information 421 and a quantized transform coefficient sequence 415. Encoding parameters are required for decoding and include prediction information 424, transform coefficient information, and quantization information. A sequence 415 of quantized transform coefficients is input to a coefficient order control unit 403. Moreover, the prediction mode information 421 included in the prediction information 424 is likewise input to the coefficient order control unit 403. Prediction information 424 is inputted to a block 411 for setting a transform matrix 1D and a selection switch 410.

The coefficient order control unit 403 converts a sequence 415 of quantized transform coefficients, which is a one-dimensional expression, into quantized transform coefficients 416, which are a two-dimensional expression. The coefficient order control unit 403 then introduces the quantized transform coefficients 416 to the dequantization unit 404. A coefficient order control unit 403 will be described in detail below.

The dequantization unit 404 dequantizes the quantized transform coefficients 416 from the coefficient order control unit 403 to obtain the reconstructed transform coefficients 417. Specifically, the dequantization unit 404 dequantizes in accordance with the quantization information decoded by the entropy decoding unit 402. The dequantization unit 404 introduces the reconstructed transform coefficients 417 into the inverse orthogonal transform unit 405.

The inverse orthogonal transform unit 405 performs the inverse orthogonal transform corresponding to the orthogonal transform performed on the encoding side on the reconstructed transform coefficients 417 from the dequantization unit 404 to obtain a reconstructed prediction error 418. The inverse orthogonal transform unit 405 introduces the reconstructed prediction error 418 into the addition unit 406.

Specifically, the inverse orthogonal transform unit 405 according to the present embodiment is a component that is substantially the same as or similar to the inverse orthogonal transform unit 105 in FIG. 3 and thus will not be described in detail below. In particular, the inverse orthogonal transform block 405 according to the present embodiment uses the transform matrix A 1D and the transform matrix B 1D that are common to the inverse orthogonal transform block in FIG. 3. The reconstructed transform coefficients 122, the definition information 129 of the transform matrix 1D, and the reconstructed prediction error 129 of FIG. 3 correspond to the reconstructed transform coefficients 417, the job information 422 of the transform matrix 1D of the transform, and the reconstructed prediction error 418 according to the present embodiment, respectively.

The addition unit 406 adds the reconstructed prediction error 418 and the corresponding prediction image 423 together to generate a locally decoded image 419. The decoded image 419 is temporarily accumulated in the output buffer 412 for the output image 425 and is also stored in the reference image memory 407 for the reference image 420. On the decoded image stored in the reference image memory 407 is referenced in blocks of a frame or field, if necessary, an intra prediction block 408 and an outside block 409 it as a prediction reference image 420. The decoded image 419 is temporarily accumulated in the output buffer 412 is output from the output time interval controlled by the decoding control unit 413.

The intra prediction block 408, the inter prediction block 409, and the selection switch 410, which are substantially the same as or similar to the intra prediction block 108, the inter prediction block 109, and the selection switch 110 in FIG. 1 and thus will not be described in detail below. The decoding control unit 413 controls the components of the image decoding apparatus in FIG. 22. Specifically, the decoding control unit 413 performs various control operations for the decoding process, including the operations described above.

The transformation matrix 1D definition unit 411 generates the transformation matrix 1D information 422 based on the prediction mode information included in the prediction information 424 from the entropy decoding unit 402. The transformation matrix 1D definition unit 411 outputs the transformation matrix 1D information 422 of the transformation matrix 1D, the inverse orthogonal transformation unit 405.

Specifically, the transform matrix 1D setting unit 411 is a component that is substantially the same as or similar to the transform matrix 1D setting unit 112 according to the first embodiment, and thus will not be described in detail below. That is, the block 411 for setting the transform matrix 1D according to the present embodiment uses, for example, the tables in FIG. 4A, FIG. 4B, FIG. 4C, FIG. 4D and FIG. 4E for generating information 422 of specifying a transformation matrix 1D. The prediction information 126 and the setting information 129 of the transform matrix 1D according to the first embodiment correspond to the prediction information 424 and the setting information 422 of the transform matrix 1D according to the present embodiment, respectively.

In addition, the image decoding apparatus of FIG. 22 uses a syntax that is the same as or similar to the syntax described with reference to FIG. 11, FIG. 12, FIG. 13 and FIG. 14. Thus, a detailed description of the syntax is omitted.

A coefficient order control unit 403 will be described in detail below.

The coefficient order control unit 403 converts a sequence 415 of quantized transform coefficients, which is a one-dimensional expression, into quantized transform coefficients 416, which are a two-dimensional expression, by arranging the elements of a sequence 415 of quantized transform coefficients in a predetermined order (i.e., the order corresponding to the order used on coding side). As an example, if the coding side performs 2D-1D conversion regardless of the prediction mode, coefficient order control unit 403 can perform a general 1D-2D conversion regardless of the prediction mode. Specifically, the coefficient order control unit 403 may use an inverse zigzag scan as in the case of H. 264. An inverse zigzag scan is a 1D-2D transformation corresponding to the above zigzag scan.

In another example, if the coding side performs individual 2D-1D transforms for the respective prediction modes, the coefficient order control unit 403 can also perform individual 1D-2D transforms for the respective prediction modes. A coefficient order control unit 403 performing such an operation is illustrated in FIG. 23A. The coefficient order control unit 403 includes a selection switch 1001 and individual 1D-2D transform units 1002, ..., and 1010 for respective prediction modes. According to the prediction mode information (for example, the prediction mode indices in FIG. 4A) included in the prediction information 424, the selection switch 1001 brings the sequence 415 of the quantized transform coefficients into a 1D-2D transform unit (one of 1002, ... and 1010) corresponding to the prediction mode. For example, the prediction mode index 0 enables the selection switch 1001 to cast a sequence 415 of quantized transform coefficients into a 1D-2D transform unit 1002. In FIG. 23A, prediction modes and 1D-2D transform blocks are in one-to-one correspondence. The sequence 415 of quantized transform coefficients is given in one block 1D-2D conversion corresponding to the prediction mode. The sequence 415 of quantized transform coefficients is then converted to quantized transform coefficients 416.

In another example, if the coding side dynamically updates the scan order during 2D-1D conversion, the coefficient order control unit 403 can also dynamically update the scan order in 1D-2D conversion in a specific manner corresponding to the procedure used on the coding side. A coefficient order control unit 403 performing such an operation is illustrated in FIG. 23B. The coefficient order control unit 403 includes a selection switch 1001, individual 1D-2D transform blocks 1002, ..., and 1010 for the respective nine types of prediction modes, an occurrence frequency calculation unit 1011, and a coefficient order update unit 1012. The selection switch 1001 is as described with reference to FIG. 23A. The individual 1D-2D transform blocks 1002, ..., and 1010 for the respective nine types of prediction modes are different from the 1D-2D transform blocks shown in FIG. 23A is that the scan order for blocks 1002, ..., and 1D-2D conversion blocks 1010 is updated by coefficient order updating block 1012.

The occurrence frequency calculation unit 1011 creates a histogram from the occurrence of nonzero coefficients in each element of the sequence 416 of quantized transform coefficients. The occurrence frequency calculation unit 1011 introduces the generated histogram 1013 into the coefficient order updating unit 1012.

The coefficient order updating unit 1012 updates the coefficient order with a predetermined time interval based on histogram 1013. The time interval may be, for example, the time interval when the decoding process performed on a unit of the coding tree is completed, or the time interval when the decoding process completed on the one line in a coding tree unit.

Specifically, the coefficient order control unit 1012 refers to a histogram 1013 for updating the coefficient order for the prediction mode with an element for which the counted number of occurrences of non-zero coefficients is equal to or greater than the threshold value. For example, coefficient order control block 1012 performs an update for prediction mode using an element for which the counted number of occurrences of nonzero coefficients is 16 or more. Setting a threshold value for the number of occurrences provides the ability to globally update the order of coefficients, thereby avoiding reduction to a local optimal solution.

Unit 1012 controls the order of the coefficients sorts, for the prediction mode of the update target, elements in order to reduce the frequency of occurrence of non-zero coefficients. Sorting can be achieved according to an existing algorithm, for example, bubble sorting or quick sorting. The coefficient order control unit 1012 inputs coefficient order update information 1014 indicating the sorted element order into the 1D-2D transform unit corresponding to the prediction mode of the update target.

Once the coefficient order updating information 1014 is input to the 1D-2D conversion unit, the 1D-2D conversion unit performs 1D-2D conversion in accordance with the updated scan order. If the scan order is dynamically updated, the initial scan orders for the 1D-2D conversion units that correspond to the scan order on the encoding side must be specified.

For simplicity, H. 264 was illustrated and a case of nine types of prediction modes was described. However, even if the number of prediction mode types is increased to 17, 33 or the like, individual 1D-2D transforms for respective prediction modes can be achieved by adding 1D-2D transform blocks corresponding to the prediction modes resulting from this increase.

As described above, the image decoding apparatus according to the present embodiment includes an inverse orthogonal transform unit that is the same or similar to the inverse orthogonal transform unit of the image encoding apparatus according to the first embodiment. Hence, the image decoding apparatus according to the present embodiment has effects that are the same or similar to the effects of the image encoding apparatus according to the first embodiment.

(FIFTH EMBODIMENT)

The image decoding apparatus according to the fifth embodiment is different from the image decoding apparatus according to the fourth embodiment in the details of the inverse orthogonal transform. The same components of this embodiment as corresponding components of the fourth embodiment are hereinafter denoted by the same reference numbers, and basically the different components will be described below. An image encoding apparatus corresponding to an image decoding apparatus according to the present embodiment is described in the second embodiment.

The inverse orthogonal transform unit 405 according to the present embodiment is a component that is substantially the same as or similar to the inverse orthogonal transform unit 105 in FIG. 17 and thus will not be described in detail below. In particular, the inverse orthogonal transform block 405 according to the present embodiment uses the transform matrix C 1D, the transform matrix D 1D and the transform matrix E 1D, which are common to the inverse orthogonal transform block 105 in FIG. 17. The reconstructed transform coefficients 122, the definition information 129 of the transform matrix 1D of the transform, and the reconstructed prediction error 129 of FIG. 17 correspond to the reconstructed transform coefficients 417, the job information 422 of the transform matrix 1D of the transform, and the reconstructed prediction error signal 418 according to the present embodiment, respectively.

The conversion matrix 1D definition unit 411 according to the present embodiment is a component that is substantially the same as or similar to the transformation matrix 1D determination unit 112 according to the second embodiment and thus will not be described in detail below. That is, the block 411 for setting the transform matrix 1D according to the present embodiment uses, for example, the tables in FIG. 18A, FIG. 18B, FIG. 18C, FIG. 18D and FIG. 18E for generating information 422 of specifying a transformation matrix 1D. The prediction information 126 and the setting information 129 of the transformation matrix 1D according to the second embodiment correspond to the prediction information 424 and the setting information 422 of the transformation matrix 1D according to the present embodiment, respectively.

As described above, the image decoding apparatus according to the present embodiment includes an inverse orthogonal transform unit that is the same or similar to the inverse orthogonal transform unit of the image encoding apparatus according to the second embodiment. Hence, the image decoding apparatus according to the present embodiment has effects that are the same or similar to the effects of the image encoding apparatus according to the second embodiment.

(SIXTH EMBODIMENT)

The image decoding apparatus according to the sixth embodiment is different from the image decoding apparatuses according to the fourth embodiment and the fifth embodiment in the details of the inverse orthogonal transform. The same components of the present embodiment, as the corresponding components of the fourth embodiment and the fifth embodiment, are hereinafter denoted by the same reference numbers, and basically the different components will be described below. An image encoding apparatus corresponding to an image decoding apparatus according to the present embodiment is described in the third embodiment.

The inverse orthogonal transform unit 405 according to the present embodiment is a component that is substantially the same as or similar to the inverse orthogonal transform unit 105 in FIG. 20 and thus will not be described in detail below. In particular, the inverse orthogonal transform unit 405 according to the present embodiment uses the transform matrix F 1D, the transform matrix G 1D, and the transform matrix H 1D, which are common to the inverse orthogonal transform block 105 in FIG. 20. The reconstructed transform coefficients 122, the definition information 129 of the transform matrix 1D of the transform, and the reconstructed prediction error 129 of FIG. 20 correspond to the reconstructed transform coefficients 417, the job information 422 of the transform matrix 1D of the transform, and the reconstructed prediction error signal 418 according to the present embodiment, respectively.

The transform matrix 1D setting unit 411 according to the present embodiment is a component that is substantially the same as or similar to the transform matrix 1D setting unit 112 according to the third embodiment, and thus will not be described in detail below. That is, the block 411 for setting the transform matrix 1D according to the present embodiment uses, for example, the tables in FIG. 21A, FIG. 21B, FIG. 21C, FIG. 21D and FIG. 21E for generating information 422 of specifying a transformation matrix 1D. The prediction information 126 and the setting information 129 of the transformation matrix 1D according to the third embodiment correspond to the prediction information 424 and the setting information 422 of the transformation matrix 1D according to the present embodiment, respectively.

As described above, the image decoding apparatus according to the present embodiment includes an inverse orthogonal transform unit that is the same or similar to the inverse orthogonal transform unit of the image encoding apparatus according to the third embodiment. Hence, the image decoding apparatus according to the present embodiment has effects that are the same or similar to the effects of the image encoding apparatus according to the third embodiment.

Fourth to sixth embodiments prepare two or three types of transform matrices 1D and select one of the transform matrices 1D for vertical inverse transform and horizontal inverse transform according to the prediction mode. However, the above two or three types of 1D transformation matrices are illustrative. Coding efficiency can be increased by preparing more transformation matrices. For example, the fifth embodiment and the sixth embodiment can be combined together to prepare four types of 1D transformation matrices. However, the increased number of types of prepared transformation matrices requires additional hardware or the like. Thus, it is desirable to consider the balance between coding efficiency and disadvantages resulting from the increased number of types of transformation matrices.

Modifications of the embodiments will be given and presented below.

The first to sixth embodiments describe an example in which a frame is divided into rectangular blocks with a size of 16 × 16 pixels or the like, and in which encoding or decoding is performed on each block in the order from upper left to lower right in the picture (see FIG. 6A). However, the encoding order and decoding order are not limited to this example. For example, encoding and decoding can be done in order from lower right to upper left or in a spiral from the center to the edge of the picture. Moreover, encoding and decoding can be carried out in order from the upper right to the lower left or in a spiral from the edge to the center of the picture.

The first to sixth embodiments illustrate the sizes of the prediction target block, such as a 4 × 4 pixel block, an 8 × 8 pixel block, and a 16 × 16 pixel block for description. However, the prediction target block need not have a uniform block shape. For example, examples of the size of the prediction target block may include a 16 × 8 pixel block, an 8 × 16 pixel block, an 8 × 4 pixel block, or a 4 × 8 pixel block. In addition, not all blocks within the same coding tree unit must have the same block size, and many different block sizes can be taken together within the coding tree unit. If many different block sizes can be taken together within a coding tree unit, the increased number of blocks into which the coding tree unit is divided increases the amount of code required to encode or decode division information. Thus, the block size is desirably selected, given the balance between the amount of code for the division information and the quality of the locally decoded image or decoded image.

To simplify the first to sixth embodiments, the components comprehensively describe the components of a color signal without distinguishing luminance signals from color difference signals. However, if the prediction process varies between a luminance signal and a color difference signal, the same prediction scheme or other prediction schemes can be used. If different prediction schemes are used for the luminance signal or for the color difference signal, the prediction scheme selected for the color difference signal can be encoded or decoded in a certain way, similar to the procedure for the luminance signal.

To simplify the first to sixth embodiments, the components comprehensively describe the components of a color signal without distinguishing a luminance signal from a color difference signal. However, if the orthogonal transform process varies between a luminance signal and a color difference signal, the same orthogonal transform scheme or other orthogonal transform schemes can be used. If different orthogonal transform schemes are used for the luminance signal or for the color difference signal, the orthogonal transform circuit selected for the color difference signal can be encoded or decoded in a certain way, similar to the procedure for the luminance signal.

As described, each of the embodiments achieves an effective orthogonal transform and an inverse orthogonal transform, while at the same time alleviating difficulties in hardware implementation and software implementation. Hence, each embodiment improves coding efficiency and thus subjective image quality.

While certain embodiments have been described, these embodiments have been provided by way of example only and are not intended to limit the scope of these inventions. In fact, the new methods and systems described herein can be implemented in a variety of other forms; in addition, various omissions, replacements, and changes in the forms of the methods and systems described herein can be made without departing from the essence of these inventions. The accompanying claims and their equivalents are intended to cover such forms or modifications as might fall within the scope and essence of these inventions.

For example, a program may be provided that is stored in a computer readable storage medium and configured to implement processing according to each of the embodiments. The storage medium may be in any storage format providing that the program can be stored in the storage medium and read from the storage medium by a computer; the storage medium may be a magnetic disk, an optical disk (CD-ROM, CD-R, DVD or the like), a magneto-optical disk (MO or the like), a semiconductor memory, or the like.

In addition, a program configured to implement processing according to each of the embodiments may be stored on a computer (server) connected to a network, such as the Internet. Thus, the program can be downloaded to a computer (client) through the network.

LIST OF REFERENCE POSITIONS

101: subtraction block

102: orthogonal transform unit

103: quantization unit

104: dequantization unit

105: inverse orthogonal transform block

106: addition block

107: reference image memory

108: intra prediction block

109: inter prediction block

110: prediction selection unit

111: prediction selection switch

112: block definition matrix 1D conversion

113: coefficient order control unit

114: entropy coding unit

115: output buffer

116: coding control unit

117: a sequence of quantized transform coefficients

118: input image

119: prediction error

120: conversion rate

121: quantized transform coefficient

122: restored conversion coefficient

123: recovered prediction error

124: locally decoded image

125: reference image

126: prediction information

127: predicted image

129: 1D transformation matrix setting information

130: encoded data

201, 204, 801, 804, 1101, 1104, 1201, 1204: select switch

202, 802, 1102, 1202: vertical conversion unit

206, ..., 209, 806, ..., 811, 1206, ..., 1211: orthogonal transform unit 1D

203, 1103: transpose block

205, 805, 1105, 1205: horizontal conversion unit

301, 304, 901, 904, 1301, 1304: select switch

302, 902, 1302: vertical inverse transform unit

303: transpose block

305, 905, 1305: horizontal inverse transform unit

306, ..., 309, 906, ..., 911, 1306, ..., 1311: inverse orthogonal transform unit 1D

401: input buffer

402: entropy decoding unit

403: coefficient order control unit

404: dequantization unit

405: inverse orthogonal transform block

406: addition block

407: reference image memory

408: intra prediction block

409: inter prediction block

410: select switch

411: 1D transformation matrix setting unit

412: output buffer

413: decoding control unit

414: encoded data

415: a sequence of quantized transform coefficients

416: quantized transform coefficient

417: restored conversion coefficient

418: recovered prediction error

419: decoded image

420: reference image

421: prediction mode information

422: job information matrix 1D conversion

423: predictive image

424: prediction information

425: output image

501: select switch

502, ..., 510: 2D-1D conversion block

511: occurrence rate counter

512: coefficient order updating unit

513: bar chart

514: coefficient order update information

700: syntax

701: high level syntax

702: clipping level syntax

703: coding tree level syntax

704: syntax for setting sequence parameters

705: picture parameter syntax

706: clipping header syntax

707: clipping data syntax

708: coding tree unit syntax

709: Prediction Unit Syntax

710: conversion unit syntax

1001: select switch

1002, ..., 1010: 1D-2D transform block

1011: occurrence rate counter

1012: coefficient order update block

1013: histogram

1014: coefficient order update information

Claims (7)

A method of decoding an image, characterized in that it comprises the steps in which: decoding transform coefficients for the target image to be decoded, and information indicating an intra prediction mode for the target image; scanning conversion coefficients to generate scanned conversion coefficients; setting a combination of a vertical inverse transform matrix and a horizontal inverse transform matrix corresponding to the target image based on a predetermined ratio; performing the inverse transform of the scanned transform coefficients along the vertical direction and the horizontal direction using a combination of a vertical inverse transform matrix and a horizontal inverse transform matrix when the intra prediction mode is the first mode or the second mode to obtain a prediction error, both from the first mode and the second mode are other than (1) the third mode corresponding to the vertical direction, or (2) the fourth mode, co sponds to the horizontal direction, wherein the first mode comprises at least a fifth mode corresponding to the first diagonal direction, the sixth mode corresponding to a second diagonal direction, the seventh mode corresponding to a third diagonal direction; and generating a decoded image based on the prediction error, and wherein said combination corresponds to any one of a plurality of candidate combinations including a first candidate combination and a second candidate combination, both of the vertical inverse transformation matrix and the horizontal inverse transformation matrix are the first transformation matrix in the first candidate combination when the intra prediction mode is the first mode, and both from the matrix of the vertical inverse transform and the matrix of the horizontal inverse transform are the second matrix of pre rofessional second combination candidates when the intra prediction mode is the second mode, the first matrix transformation differs from the second transform matrix.

Images