HK1211399B - Video encoding apparatus and video decoding apparatus - Google Patents

Description

Moving picture encoding device and moving picture decoding device

This application is a divisional application of the application with application number "201080015255.5", application date of March 17, 2010, and invention name of "Motion image encoding device and motion image decoding device".

Technical Field

The present invention relates to a moving picture encoding device that encodes a moving picture to generate encoded data, and a moving picture decoding device that reproduces the moving picture based on the transmitted and stored encoded data of the moving picture.

Background Art

<Introduction and Definition of Basic Terms>

In block-based moving image coding, the input moving image to be coded is divided into predetermined processing units called macroblocks (hereinafter referred to as MBs). Coding is performed on each MB to generate coded data. When reproducing the moving image, the coded data to be decoded is processed and decoded on an MB-by-MB basis to generate a decoded image.

As a block-based motion picture coding method that is currently widely used, there is a method specified by non-patent document 1 (H.264/AVC (Advanced Video Coding)). In H.264/AVC, a predicted image is generated to estimate the input motion picture divided into MB units, and the difference between the input motion picture and the predicted image, that is, the prediction residual, is calculated. A frequency transform represented by discrete cosine transform (DCT) is applied to the obtained prediction residual to derive the transform coefficient. The derived transform coefficient is variable-length encoded using a method called CABAC (Context-based Adaptive Binary Arithmetic Coding) or CAVLC (Context-based Adaptive Variable Length Coding). In addition, the predicted image is generated by intra-frame prediction using the spatial correlation of the motion picture, or inter-frame prediction (motion compensation prediction) using the temporal correlation of the motion picture.

<Partition Concept and Effects>

In inter-frame prediction, an image that is similar to the input motion image of the encoding object MB is generated in units called partitions. In each partition, a correspondence is established with one or two motion vectors. Based on the motion vector, a predicted image is generated by referencing the area corresponding to the encoding object MB on the local decoded image recorded in the frame memory. In addition, the local decoded image referenced at this time is called a reference image. In H.264/AVC, partition sizes of 16×16, 16×8, 8×16, 8×8, 8×4, 4×8, and 4×4 can be used in pixel units. If a small partition size is used, the motion vector can be specified in a small unit to generate a predicted image, so even when the spatial correlation of the motion is small, a predicted image close to the input motion image can be generated. On the other hand, if a large partition size is used, the amount of code required for encoding the motion vector can be reduced when the spatial correlation of the motion is large.

<The concept and effect of resizing>

The prediction residual generated using a predicted image reduces spatial and temporal redundancy in the pixel values of the input moving image. Furthermore, applying DCT to the prediction residual concentrates energy in the low-frequency components of the transform coefficients. Therefore, by utilizing this energy bias to perform variable-length coding, the amount of encoded data can be reduced compared to when using neither a predicted image nor DCT.

In H.264/AVC, in order to increase the energy concentration towards low-frequency components caused by DCT, a method (block adaptive transform selection) is adopted to select a DCT suitable for the local properties of the moving image from DCTs of multiple transform sizes. For example, when generating a predicted image through inter-frame prediction, a DCT suitable for transforming the prediction residual can be selected from two DCTs, 8×8 DCT and 4×4 DCT. The 8×8 DCT can utilize the spatial correlation of pixel values in a wider range, so it is effective for flat areas with relatively few high-frequency components. On the other hand, the 4×4 DCT is effective for areas with many high-frequency components, such as the outlines of objects. In H.264/AVC, it can be said that the 8×8 DCT is a DCT with a large transform size, and the 4×4 DCT is a DCT with a small transform size.

In H.264/AVC, 8×8 DCT and 4×4 DCT can be selected when the area of a partition is 8×8 pixels or larger, and 4×4 DCT can be selected when the area of a partition is less than 8×8 pixels.

As described above, H.264/AVC can select appropriate partition sizes and transform sizes based on the spatial correlation of pixel values and motion vectors, which are local properties of a moving image, thereby reducing the amount of code required for encoding data.

<Description of Adaptive Transform Size Expansion and Partition Size Expansion>

In recent years, the use of high-definition moving images with resolutions exceeding HD (1920 x 1080 pixels) has been increasing. Compared to conventional low-resolution moving images, high-definition moving images have a wider range of spatial correlations between pixel values and motion vectors within local regions within the moving image. In particular, high-definition moving images often exhibit high spatial correlations between pixel values and motion vectors within local regions.

Non-Patent Document 2 describes a moving picture coding method that reduces the amount of coded data by expanding the partition size and transform size of H.264/AVC and utilizing the spatial correlation properties of high-definition moving pictures as described above.

Specifically, in addition to the partition sizes specified in H.264/AVC, partition sizes of 64×64, 64×32, 32×64, 32×32, 32×16, and 16×32 have been added. Furthermore, in addition to the DCT specified in H.264/AVC, three new DCT transform sizes, 16×16 DCT, 16×8 DCT, and 8×16 DCT, have been added.

When the partition size is 16×16 pixels or larger, 16×16 DCT, 8×8 DCT, and 4×4 DCT can be selected. Furthermore, when the partition size is 16×8, 16×8 DCT, 8×8 DCT, and 4×4 DCT can be selected. When the partition size is 8×16, 8×16 DCT, 8×8 DCT, and 4×4 DCT can be selected. When the partition size is 8×8, 8×8 DCT and 4×4 DCT can be selected. When the partition size is less than 8×8 pixels, 4×4 DCT can be selected.

In the method described in non-patent document 2, by switching between various partition sizes and transform sizes as described above, even for high-definition motion images with a relatively wide dynamic range of spatial correlation of pixels or motion vectors, it is possible to select partition sizes and transform sizes that are suitable for the local properties of the motion image, thereby reducing the amount of code in the encoded data.

Prior art literature

Non-patent literature

Non-Patent Document 1: ITU-T Recommendation H.264 (November 7)

Non-Patent Document 2: ITU-T T09-SG16-C-0123

Summary of the Invention

Problems to be solved by the invention

As described above, in moving picture coding methods, increasing the number of selectable partition sizes and transform sizes contributes to reducing the amount of encoded data. However, this creates a new problem: the amount of additional information required to select the partition size and transform size to be applied during decoding in each local area of the moving picture increases.

In non-patent documents 1 and 2, frequency transforms with small transform sizes (4×4 DCT) can be used even when the partition size is large. However, large partitions are more likely to be selected in areas with high spatial correlation between pixel values or motion vectors. Therefore, when applying a frequency transform with a small transform size to such partitions, it is more difficult to concentrate the energy of the prediction residual into fewer transform coefficients than when applying a frequency transform with a large transform size. Therefore, frequency transforms with small transform sizes are rarely selected, and the additional information required to select the transform size is wasted. In particular, when the maximum partition size is increased, thereby widening the size difference between the large partition size and the small transform size, it becomes even more difficult to select a small transform size.

Furthermore, in Non-Patent Document 2, frequency transforms of the same transform size can be selected for rectangular partitions. However, there is no mention of what criteria are used to determine the selectable transform sizes when the types of transform sizes are further increased.

Summary of the Invention

The present invention has been developed in view of this situation, and its object is to provide a moving picture coding apparatus that can utilize a variety of partition sizes and transform sizes, while maintaining the ability to select a partition size or transform size appropriate for local characteristics of a moving picture, while reducing the amount of code for additional information. Furthermore, a moving picture decoding apparatus is provided that can decode coded data coded by the moving picture coding apparatus.

Means for solving problems

In order to solve the above-mentioned problems, the first technical means of the present invention is to divide an input moving image into blocks of a given size and perform encoding processing on a block-by-block basis, comprising: a prediction parameter determination unit that determines the partition structure of the block; a prediction image generation unit that generates a prediction image in units of the partition specified by the partition structure; a transform coefficient generation unit that applies any one of the transforms included in a given transform preset set to the difference between the prediction image and the input moving image, that is, the prediction residual; a transform candidate derivation unit that generates a list of applicable transforms, that is, a transform candidate list, based on partition shape information; a frequency transform determination unit that determines a transform selection flag indicating the transform to be applied to each partition based on the transform candidate list; and a variable length encoding unit that performs variable length encoding on the transform selection flag based on the transform candidate list and the transform preset set.

The second technical means further includes a transformation constraint derivation unit in the first technical means, which generates a list of transformations that cannot be applied to each partition, i.e., a prohibited transformation list, based on the partition shape information. The transformation candidate list is derived based on the prohibited transformation list and the transformation preset set.

Third Technical Means In the first or second technical means, the partition shape information is a ratio of a vertical length to a horizontal length of the partition, or a size relationship between the vertical length and the horizontal length of the partition.

Fourth Technical Means In the first or second technical means, the partition shape information is the minimum value of the vertical length and the horizontal length of the partition.

A fifth technical means is that in the first or second technical means, the partition structure is expressed as a hierarchical structure, and each partition is defined to be included in a certain hierarchy according to its shape, and the partition shape information is the hierarchy to which the partition belongs.

The sixth technical means is that in the first technical means, a given transformation preset set includes at least one transformation whose transformation size is a horizontal rectangle of 1 pixel in the vertical direction, and when the horizontal length of the partition is longer than the vertical length, the transformation candidate list generation unit includes the transformation whose transformation size is a horizontal rectangle of 1 pixel in the vertical direction in the transformation candidate list.

The seventh technical means is that in the second technical means, a given transformation preset set includes at least one transformation whose transformation size is a square and at least one transformation whose transformation size is a horizontal rectangle or a vertical rectangle. When the vertical length and horizontal length of the partition are inconsistent, the transformation constraint derivation unit includes at least one square transformation in the prohibited transformation list.

The eighth technical means is that in the second technical means, a given transformation preset set includes at least one transformation with a transformation size of a horizontal rectangle and a transformation with a transformation size of a vertical rectangle. When the horizontal length of the partition is longer than the vertical length, the transformation constraint derivation unit includes the transformation with a transformation size of a vertical rectangle in the prohibited transformation list.

The ninth technical means is that in the second technical means, a given transformation preset set includes at least two transformations with transformation sizes that are in a similar relationship to each other, and when the minimum value of the longitudinal length and the lateral length of the partition is greater than a given threshold, the transformation constraint derivation unit includes the transformation with the smallest transformation size among the transformations with transformation sizes in a similar relationship in the prohibited transformation list.

The tenth technical means is that in the first technical means, a given transformation preset set includes a first transformation and a second transformation, the second transformation is in a similar relationship with the first transformation and the transformation size is smaller than the transformation size of the first transformation, the partition structure is expressed by a hierarchical structure, and it is stipulated that each partition is included in any hierarchy according to its shape, and the transformation constraint derivation unit includes the first transformation in the transformation candidate list and does not include the second transformation in the transformation candidate list when the partition belongs to a given hierarchy that is not the lowest; and includes the second transformation in the transformation candidate list when the partition belongs to a hierarchy lower than the given hierarchy that is not the lowest.

The eleventh technical means is provided in a motion picture decoding device that decodes input coded data in block units, comprising: a variable-length code decoding unit that decodes the partition structure of the block to be processed based on the input coded data; a prediction image generation unit that generates a prediction image in units of partitions specified by the partition structure; and a transform control derivation unit that derives transform constraints and/or transform candidates of applicable transforms based on partition shape information, wherein the variable-length decoding unit decodes the transform selection flag based on the input coded data and the transform constraints and/or transform candidates, and decodes the transform coefficients of the block to be processed based on the transform selection flag, and the motion picture decoding device also includes: a prediction residual reconstruction unit that applies an inverse transform corresponding to the transform specified by the transform selection flag to the transform coefficients to reconstruct the prediction residual; and a local decoded image generation unit that outputs decoded image data corresponding to the block to be processed based on the prediction image and the prediction residual.

The twelfth technical means is a motion picture decoding device that processes input coded data in block units to decode an image, comprising: a variable-length code decoding unit that decodes prediction parameters for determining a partition structure of a block to be processed, and a rule for specifying or updating transformations that can be applied to partitions and sets of partitions; and a prediction image generation unit that generates a prediction image based on a division specified by the partition structure, wherein the variable-length decoding unit decodes a transformation selection flag based on the input coded data and the rule, and decodes the transformation coefficients of the block to be processed based on the transformation selection flag, and the motion picture decoding device further comprises: a prediction residual reconstruction unit that applies an inverse transformation corresponding to the transformation specified by the transformation selection flag to the transformation coefficients to reconstruct a prediction residual; and a local decoded image generation unit that outputs decoded image data corresponding to the block to be processed based on the prediction image and the prediction residual.

Thirteenth Technical Means In the twelfth technical means, the rule includes a rule for stipulating that a specific type of transformation be included in the transformation candidate list for a partition of a specific shape.

Fourteenth Technical Means In the twelfth technical means, the rule includes a rule for prohibiting a specific type of transformation from being included in the transformation candidate list for a partition of a specific shape.

Fifteenth Technical Means In the twelfth technical means, the rule includes a rule for prescribing that, when a specific type of transformation is included in the transformation candidate list for a partition of a specific shape, the transformation is replaced with another transformation.

Sixteenth Technical Means In the twelfth technical means, the rule includes a composite rule that is a combination of basic rules that permit or prohibit a partition of a specific shape or replace a specific type of transformation.

Seventeenth Technical Means In the sixteenth technical means, the rule includes, as a composite rule, a rule for prohibiting, for a partition belonging to a higher layer than a specific layer, a small-size transformation from among transformations in a similar relationship from being included in the transformation candidate list.

Eighteenth Technical Means In the sixteenth or seventeenth technical means, the variable-length encoding unit encodes a flag indicating whether a composite rule is applied as a rule.

The nineteenth technical means is provided in a motion picture encoding device that divides an input motion picture into blocks of a given size and performs encoding processing in units of blocks, comprising: a prediction parameter determination unit that determines a partition structure of the block; a prediction image generation unit that generates a prediction image in units of partitions specified by the partition structure; a transform coefficient generation unit that applies any one of the frequency transforms included in a given transform preset set to a difference between the prediction image and the input motion picture, i.e., a prediction residual; a transform control derivation unit that derives transform constraints and/or transform candidates for transforms that can be applied to each partition based on partition shape information; a frequency transform determination unit that determines a transform selection flag indicating a transform to be applied based on the transform constraints and/or transform candidates; a transform candidate derivation rule determination unit that determines a rule for specifying or updating a derivation method of transform constraints and/or transform candidates in the transform control derivation unit; and a variable length encoding unit that variable-length encodes the transform selection flag based on the transform constraints and/or the transform candidate list and the transform preset set, and variable-length encodes the transform candidate derivation rule for each given unit larger than a block.

Effects of the Invention

In the moving picture coding apparatus of the present invention, when selecting a specific partition size, by limiting the selectable transform sizes to those with high effectiveness, the probability of selecting a transform size suitable for the local characteristics of the moving picture is maintained at a high level, while the amount of code required for the additional information can be reduced, thereby reducing the amount of encoding processing. Furthermore, the moving picture decoding apparatus of the present invention can decode coded data coded by the moving picture coding apparatus.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a diagram for explaining the definition of an extended macroblock (MB) and a processing order.

FIG2 is a block diagram showing an embodiment of a moving picture encoding apparatus according to the present invention.

FIG. 3 is a diagram for explaining the definition of a partition hierarchy and a processing order.

FIG. 4 is a flowchart for explaining an example of a process for generating a prohibited conversion list.

FIG. 5 is a flowchart for explaining another example of the process of generating the prohibited conversion list.

FIG. 6 is a diagram for explaining partition division when generating a prohibited conversion list.

FIG. 7 is another diagram for explaining partition division when generating a prohibited conversion list.

FIG8 is a flowchart for explaining still another example of the process of generating the prohibited conversion list.

FIG. 9 is a diagram for explaining a specific example of the process of generating the prohibited conversion list.

FIG10 is a flowchart for explaining an example of a coded data generation process for a conversion selection flag.

FIG11 is a block diagram showing an embodiment of a moving picture decoding apparatus according to the present invention.

FIG12 is a block diagram showing another embodiment of the moving picture encoding apparatus according to the present invention.

FIG. 13 is a flowchart for explaining an example of a process for generating a conversion candidate list.

FIG14 is a block diagram showing another embodiment of the moving picture decoding apparatus according to the present invention.

FIG15 is a block diagram showing still another embodiment of the moving picture encoding apparatus according to the present invention.

FIG16 is a block diagram showing still another embodiment of the moving picture decoding device according to the present invention.

DETAILED DESCRIPTION

(Implementation 1)

1 to 11 , a moving picture encoding device 10 and a moving picture decoding device 20 as one embodiment of the moving picture encoding device and the moving picture decoding device of the present invention are described. In the description of the drawings, the same elements are denoted by the same reference numerals and their description is omitted.

In the following description, it is assumed that the moving picture encoding device sequentially inputs an input moving picture in extended MB units consisting of 64×64 pixels and performs processing. Furthermore, the order in which the extended MBs are input is assumed to be the raster scan order shown in Figure 1. However, the present invention is also applicable to extended MB sizes other than those described above. It is particularly effective for extended MBs larger than the currently widely used processing unit of 16×16 pixels.

The processing in the video encoding and decoding devices described below is assumed to be implemented based on H.264/AVC. Unless otherwise specified, operations are assumed to comply with H.264/AVC. However, the present invention is not limited to H.264/AVC and is applicable to similar video encoding methods such as VC-1, MPEG-2, and AVS, as well as other video encoding methods that utilize block-based processing and frequency conversion.

<Configuration of Moving Image Coding Device 10>

FIG2 is a block diagram showing the configuration of the moving picture coding apparatus 10. The moving picture coding apparatus 10 includes a frame memory 101, a prediction parameter determination unit 102, a prediction image generation unit 103, a transform constraint derivation unit 104, a frequency transform determination unit 105, a prediction residual generation unit 106, a transform coefficient generation unit 107, a variable length coding unit 108, a prediction residual reconstruction unit 109, and a local decoded image generation unit 110.

<Frame Memory 101>

Locally decoded images are stored in frame memory 101. Here, a locally decoded image is an image generated by superimposing a prediction image on a prediction residual reconstructed by applying an inverse frequency transform to transform coefficients. When processing a specific extended MB in a specific frame of an input moving image, locally decoded images corresponding to frames encoded before the current frame and locally decoded images corresponding to extended MBs encoded before the current extended MB are stored in frame memory 101. Furthermore, the locally decoded images stored in frame memory 101 can be read as appropriate by various components within the apparatus.

<Prediction Parameter Determination Unit 102 (Partition Structure Definition, Mode Judgment Description)>

The prediction parameter determination unit 102 determines and outputs prediction parameters based on the local properties of the input moving image. The prediction parameters include at least the partition structure indicating the structure of the partitions applicable to each part within the extended MB, and motion information used for inter-frame prediction (motion vectors and indices of local decoded images referenced (reference image indices)). Furthermore, the intra-frame prediction mode indicating the method for generating predicted images during intra-frame prediction may also be included.

The details of the partition structure are described with reference to FIG3 . The partition structure is represented by a hierarchical structure, with the hierarchy using 64×64 pixels as the processing unit defined as hierarchy L0, the hierarchy using 32×32 pixels as the processing unit defined as hierarchy L1, the hierarchy using 16×16 pixels as the processing unit defined as hierarchy L2, and the hierarchy using 8×8 pixels as the processing unit defined as hierarchy L3. For each hierarchy, the division method can be selected from single division (no division), horizontal division (two equal divisions) using horizontal lines, vertical division (two equal divisions) using vertical lines, or four divisions (four equal divisions) using two horizontal and vertical lines. Hierarchies with larger processing units are referred to as upper hierarchies, and hierarchies with smaller processing units are referred to as lower hierarchies. In this embodiment, hierarchy L0 is the highest hierarchy, and hierarchy L3 is the lowest hierarchy. The partition structure is represented by determining the division method for each hierarchy, starting from the highest hierarchy, hierarchy L0. Specifically, the following process uniquely represents the partition structure.

(Step S10) If the division method in level L0 is one of single division, horizontal two division, or vertical two division, the area represented by the division method is used as a partition of the processing unit in level L0. If the division method is four division, the partition is determined for each divided area in step S11.

(Step S11) If the division method in layer L1 is one of single division, horizontal two division, or vertical two division, the area represented by the division method is used as a partition of the processing unit in layer L1. If the division method is four divisions, the partition is determined for each divided area in step S12.

(Step S12) If the division method in level L2 is one of single division, horizontal two division, or vertical two division, the area represented by the division method is used as a partition of the processing unit in level L2. If the division method is four division, the partition is determined for each divided area in step S13.

(Step S13) The region represented by the division method in the layer L3 is partitioned as a processing unit in the layer L3.

Here, the processing order for each partition within an extended MB is described. As shown in Figure 3, processing is performed in raster scan order at each layer, regardless of the partitioning method. However, except for the lowest layer (layer L3), when a four-partition partitioning method is selected, the partitions represented by the lower layers are processed in raster scan order for each four-partition area. In the following sections, the above processing order is applied when processing partitions within an extended MB.

The hierarchy Lx to which the partition p belongs is derived through the following process.

(Process S20) When the size of the partition p is equal to the size of the partition generated by one division, horizontal two division, or vertical two division of the specific hierarchy Ly, the value of Lx is set to Ly.

(Process S21) In cases other than the above, the value of Lx is set to L3 (Lx is set to the lowest level).

<Description of Partition Shape>

Partition shape information refers to information that characterizes each partition in the partition structure, namely, the partition size, information that characterizes the partition size, or the hierarchy within the partition structure. For example, partition shape information includes the partition size itself, such as 32×32, information indicating whether it is larger than a given partition size, the ratio of the vertical to horizontal length of a partition, the relationship between the vertical and horizontal lengths of a partition, the minimum and maximum values of the vertical and horizontal lengths of a partition, and the hierarchy to which a partition belongs.

Prediction parameters are determined through rate-distortion analysis. In this analysis, a cost, called a rate-distortion cost, is calculated for each candidate prediction parameter based on the bitrate of the coded data, the distortion of the local decoded image, and the input moving image when encoding the target extended MB using that prediction parameter. The prediction parameter that minimizes this cost is then selected. Specifically, the rate-distortion cost is calculated for all possible combinations of the partition structure and motion information used as prediction parameters, and the best combination is selected as the prediction parameter. Let R be the bitrate of the coded data of the extended MB, and D be the mean squared error between the input moving image and the local decoded image corresponding to the extended MB. Using the parameter λ, which represents the relationship between the bitrate R and the error D, the rate-distortion cost C can be calculated using the equation C = D + λR.

Through rate-distortion determination, prediction parameters suitable for encoding the extended MB to be processed, that is, a suitable partition structure and motion information corresponding to each partition are determined and output.

Furthermore, when calculating the rate-distortion cost for specific prediction parameters, the frequency transform applied to the extended MB being processed may not be uniquely determined. In this case, the rate-distortion cost obtained by applying the specific frequency transform may be used, or the minimum rate-distortion cost obtained by applying multiple frequency transforms may be used.

<Prediction Image Generator 103>

The predicted image generation unit 103 generates and outputs a predicted image of the extended MB to be processed based on the input prediction parameters. The predicted image generation is performed through the following procedure.

(Process S30) Based on the partition structure included in the prediction parameters, the extended MB is divided into partitions, and a prediction image is generated in each partition through process S31.

(Process S31) Motion information corresponding to the partition to be processed, i.e., the motion vector and reference image index, is read from the prediction parameters. A predicted image is generated by motion compensation prediction based on the pixel values of the area indicated by the motion vector on the local decoded image indicated by the reference image index.

<Prediction Residual Generator 106>

The prediction residual generation unit 106 generates and outputs a prediction residual for the extended MB based on the input moving picture and the predicted picture. The prediction residual is two-dimensional data of the same size as the extended MB, and each element is a difference value between corresponding pixels in the input moving picture and the predicted picture.

<Transform Coefficient Generation Unit 107>

The transform coefficient generator 107 generates and outputs transform coefficients by performing a frequency transform on the prediction residual based on the input prediction residual and the transform selection flag. The transform selection flag indicates the frequency transform to be applied to each partition of the extended MB. The transform coefficient generator 107 selects the frequency transform indicated by the transform selection flag for each partition within the extended MB and applies the selected frequency transform to the prediction residual. The frequency transform indicated by the transform selection flag is any one of the frequency transforms included in the set of all frequency transforms applicable by the transform coefficient generator 107 (transform preset).

In this embodiment, the transform preset set includes nine frequency transforms: 4×4 DCT, 8×8 DCT, 16×16 DCT, 16×8 DCT, 8×16 DCT, 16×1 DCT, 1×16 DCT, 8×1 DCT, and 1×8 DCT. Each frequency transform specified here corresponds to a DCT (discrete cosine transform) with a specific transform size (for example, 4×4 DCT corresponds to a discrete cosine transform with a transform size of 4×4 pixels). Furthermore, the present invention is not limited to the aforementioned set of frequency transforms and is also applicable to a subset of the aforementioned transform preset sets. Furthermore, the transform preset set may also include discrete cosine transforms with other transform sizes, such as frequency transforms including 32×32 DCT and 64×64 DCT. The transform preset set may also include frequency transforms other than discrete cosine transforms, such as Hadamard transforms, sine transforms, wavelet transforms, or frequency transforms similar to these transforms.

The process of applying a frequency transform with a transform size of W×H to an M×N pixel partition is represented by the following pseudo code. Region R(x, y, w, h) represents a region with a width of w pixels and a height of h pixels, located at a position shifted x pixels to the right and y pixels downward from the upper left corner of the partition.

for(j=0, j<N, j+=H){

for(i=0, i<M, i+=W){

Apply frequency transform to region R(i, j, W, H)

}

}

<Conversion Constraint Derivation Unit 104>

The transform constraint deriving unit 104 derives and outputs the constraints on the frequency transform selectable in each partition within the extended MB based on the input prediction parameters. In other words, the transform constraints for each partition are derived based on the partition shape information of the partition determined by the prediction parameters.

Transformation constraints are defined as a set of prohibited transformation lists associated with each partition within an extended MB. The prohibited transformation lists include frequency transformations included in the transformation preset set that cannot be selected in the associated partition (prohibited frequency transformations). In other words, the set of frequency transformations that can be selected by the associated partition (transformation candidate list) is formed by removing the elements of the prohibited transformation list from the elements of the transformation preset set.

Furthermore, the prohibited transform list and candidate transform list can be represented using transform set information that includes information indicating whether each transform is included in the set. Assuming that the number of transforms included in a transform preset set is Nt, the number of transform combinations is 2 to the power of Nt. Therefore, transform set information with a value range of 0 to (2 to the power of Nt - 1) can be used to represent the transforms included in the set. Furthermore, the transform set information does not necessarily need to represent all transform combinations; it can simply represent values corresponding to specific combinations. As an extreme example, if the transform preset set only includes 4×4 DCT and 8×8 DCT, the prohibited list can be represented using a 1-bit flag indicating whether 4×4 DCT (or 8×8 DCT) is prohibited. Alternatively, the candidate transform list can be represented using values from 0 to 2, with 0 corresponding to 4×4 DCT, 1 corresponding to the combination of 4×4 DCT and 8×8 DCT, and 2 corresponding to 8×8 DCT.

Furthermore, the meaning of transform set information can be changed based on the hierarchy, partition, or block group. For example, the same transform set information value of 0 can represent 16×16 DCT in hierarchy L0, 8×8 DCT in hierarchy L1, and 4×4 DCT in hierarchy L2. By changing the meaning of the transform set information values, the prohibited transform list and candidate transform list can be expressed using a narrower range of values.

Therefore, the transformation constraints and the transformation candidate list in the present invention are not limited to the term "list" and can be considered to be equivalent to transformation set information indicating the transformation constraints and transformation candidates.

The prohibited transformation list Lp for a specific partition p is generated using the following procedure. It is assumed that the size of the partition p is M×N pixels (M pixels horizontally and N pixels vertically). It is also assumed that the partition p belongs to the hierarchy Lx.

(Process S40) Set Lp to null.

(Process S41) A frequency transform having a transform size larger than M×N pixels is added to Lp.

(Process S42) Frequency conversion determined according to the value of Min(M, N) is added to Lp.

(Process S43) Frequency conversion determined according to the value of M÷N is added to Lp.

(Process S44) Frequency conversion determined according to the value of the layer Lx is added to Lp.

Furthermore, information indicating whether or not the pixel size is larger than M×N pixels, the value of Min(M, N), the value of M÷N, and the value of the hierarchy level Lx are partition shape information.

<Min(M, N) Transformation Size Limitations>

The above-mentioned process S42 will be described in more detail with reference to the flowchart of FIG. 4 .

(Process S50) If Min(M, N) is greater than a given threshold Th1 (for example, Th1 = 16 pixels), the process proceeds to process S51; otherwise, the process proceeds to process S52.

(Process S51) When there are two or more frequency transforms with similar transform sizes in the frequency transform list, the frequency transform with the smallest transform size (4×4 DCT, 8×1 DCT, 1×8 DCT) in the group of frequency transforms with similar transform sizes is added to Lp, and then process S52 is entered. The similar relationship here includes a similar relationship. For example, the transform sizes of 16×16, 8×8, and 4×4 in the transform preset set of this embodiment are similar. In addition, the similar relationship also includes an approximate similar relationship. For example, the transform sizes of 16×1 and 8×1, and the transform sizes of 1×16 and 1×8 in the transform preset set of this embodiment are similar. In addition, although it is not applicable in the following description, the frequency transforms can be divided into three categories according to their sizes: square, vertically rectangular, and horizontally rectangular, and the frequency transforms belonging to each category are considered to have a similar relationship.

(Process S52) If Min (M, N) is greater than a given threshold Th2 (for example, Th2 = 32 pixels), the process proceeds to process S53; otherwise, the process ends.

(Step S53) If three or more frequency transforms with similar transform sizes exist within the transform preset set, the frequency transform with the second smallest transform size (8×8 DCT) is added to Lp in each group of frequency transforms with similar transform sizes, and the process is terminated. Here, Th2>Th1.

Partitions are units of motion compensation. In order to use motion vectors to make the predicted image generated in partition units close to the input image, the partition structure is determined in a manner consistent with the inter-frame motion of the image within the partition. That is, large partitions are assigned to large objects (or parts thereof) on the input moving image, and small partitions are assigned to small objects. Generally, on the input moving image, the spatial correlation of pixel values in areas corresponding to large objects is higher than the spatial correlation of pixel values in areas corresponding to small objects. Therefore, for large partitions, frequency transforms with large transform sizes are more effective than frequency transforms with small transform sizes. Therefore, for large partitions, even when frequency transforms with a certain degree of small transform size are prohibited transforms, the amount of code in the encoded data does not increase substantially.

<Restrictions on the Conversion Size of the M÷N Value>

Next, the above-mentioned process S43 will be described in more detail with reference to the flowchart of FIG. 5 .

(Process S60) If the value of M÷N is greater than 2 (the horizontal length of partition p is greater than or equal to twice the vertical length), then proceed to process S61; otherwise, proceed to process S63.

(Process S61) All frequency transforms having square transform sizes (4×4 DCT, 8×8 DCT, 16×16 DCT) are added to Lp, and then the process proceeds to process S62.

(Process S62) A frequency transform (8×16 DCT, 1×16 DCT) whose transform size has a longer vertical length than horizontal length is added to Lp, and the process is terminated.

(Process S63) If the value of M÷N is less than 0.5 (the vertical length of partition p is more than twice the horizontal length), proceed to process S64; otherwise, proceed to process S66.

(Process S64) All frequency transforms having square transform sizes (4×4 DCT, 8×8 DCT, 16×16 DCT) are added to Lp, and then the process proceeds to process S65.

(Process S65) A frequency transform (16×8 DCT, 16×1 DCT) whose transform size has a horizontal length longer than a vertical length is added to Lp, and the process is terminated.

(Process S66) If the value of M÷N is equal to 1 (the horizontal length and vertical length of partition p are equal), then enter process S67, otherwise the processing ends.

(Process S67) Frequency transforms (16×8 DCT, 16×1 DCT, 8×16 DCT, 1×16 DCT) having different horizontal and vertical lengths of transform sizes are added to Lp.

The purpose of the above-described steps S61 and S62 will be explained with reference to FIG6 . As shown in FIG6( a ), assume that two objects (foreground object O and background B) exist within a processing unit U of a certain hierarchy, and the boundary between foreground object O and background B lies at the bottom of processing unit U. In this case, horizontal rectangular partitions, such as those shown in FIG6( b ), where the value of M÷N is 2 or greater, are selected. Conversely, vertical rectangular partitions, such as those shown in FIG6( c ), are not selected.

The following describes the relationship between the transform size and the amount of code for the encoded data in a partition that includes both the background B and the foreground object O when horizontal rectangular partitions are selected, with reference to Figures 6(d) to 6(f). Figures 6(d), 6(e), and 6(f) show the relationship between the partition and the transform size when square, horizontal rectangular, and vertical rectangular transform sizes are applied to the partition, respectively. When frequency transforming with a square transform size (Figure 6(d)) or a vertical rectangular transform size (Figure 6(f)) is used, boundaries often exist within the region where the frequency transform is applied.

On the other hand, when frequency transform with a horizontal rectangular transform size is used (Figure 6(e)), there are fewer cases where boundaries exist within the area where the frequency transform is applied. If there are boundaries within the area where the frequency transform is applied, the energy cannot be concentrated in the low-frequency components of the transform coefficients through the frequency transform, so the amount of code required to encode the transform coefficients increases. On the other hand, when there are no boundaries within the area where the frequency transform is applied, the energy can be concentrated in the low-frequency components of the transform coefficients through the frequency transform, so the amount of code required to encode the transform coefficients decreases. Therefore, for horizontal rectangular partitions, applying frequency transform with a horizontal rectangular transform size is more effective than applying frequency transform with a square or vertical rectangular transform size. Therefore, for horizontal rectangular partitions, when frequency transform with a square or vertical rectangular transform size is set to prohibit transformation, the amount of code required for encoding the data does not increase substantially.

The purpose of the above-mentioned steps S64 and S65 is the same as that described above. That is, for the vertically rectangular partition, when the frequency transformation of the square or horizontally rectangular transformation size is set to be prohibited, the code amount of the encoded data is hardly increased.

The purpose of the above-described step S66 will be explained with reference to FIG7 . As shown in FIG7( a ), assume that two objects (foreground object O and background B) exist within a processing unit U of a certain hierarchy, and the boundary between foreground object O and background B exists at the lower right portion of processing unit U. In this case, a square partition with an M÷N value of 1 is selected, as shown in FIG7( b ).

Next, referring to Figures 7(d) to (f), the relationship between the transform size and the amount of code for the encoded data in the partition (lower right partition) that includes both the background B and the foreground object O when a square partition is selected is explained. Figures 7(d), (e), and (f) respectively show the relationship between the partition and the transform size when a square, a horizontal rectangle, and a vertical rectangle are applied to the lower right partition. In this case, when any of the transform sizes of square, vertical rectangle, and horizontal rectangle are adopted, the proportion of the boundary in the area where the frequency transform is applied does not change much. Therefore, for the lower right partition, the difference in the amount of code for the encoded data is small when the frequency transform using any of the transform sizes of square, vertical rectangle, and horizontal rectangle is used.

On the other hand, partitions other than the lower right partition within processing unit U contain only background B and have no boundaries. Therefore, regardless of the transform size, no boundaries exist within the region where the frequency transform is applied. Therefore, compared to frequency transforms using vertically or horizontally rectangular transform sizes, frequency transforms using square transform sizes, which effectively utilize the spatial correlation of the pixel values of the prediction residual in a well-balanced manner in both the horizontal (horizontal) and vertical (vertical) directions, are more able to concentrate energy in the transform coefficients. Therefore, for square partitions, frequency transforms using square transform sizes are more effective than frequency transforms using horizontally or vertically rectangular transform sizes. Therefore, for square partitions, even when frequency transforms using horizontally or vertically rectangular transform sizes are set as prohibited, the amount of code in the encoded data does not increase substantially.

<Restrictions on the Transform Size of the Partition's Hierarchy>

Next, the above-mentioned process S44 will be described in more detail with reference to the flowchart of FIG. 8 .

(Process S70) If the layer Lx is the highest layer, the process proceeds to process S71; otherwise, the process proceeds to process S72.

(Process S71) A frequency transform other than the frequency transform having the largest transform size (8×8 DCT, 4×4 DCT) among a plurality of frequency transform candidates (16×16 DCT, 8×8 DCT, 4×4 DCT) having similar transform sizes is added to Lp, and the process is terminated.

(Process S72) If the layer Lx is the lowest layer, the process proceeds to process S73; otherwise, the process ends.

(Process S73) A frequency transform other than the frequency transform with the smallest transform size (16×16 DCT, 8×8 DCT) among a plurality of frequency transform candidates (16×16 DCT, 8×8 DCT, 4×4 DCT) having similar transform sizes is added to Lp, and the process is terminated.

When partitions are represented using a hierarchical structure, even if the partitions belonging to the top hierarchy are used to restrict a portion of frequency transforms with relatively small transform sizes, the amount of code in the coded data will not increase substantially. This is because even if a specific transform (e.g., 8×8 DCT or 4×4 DCT) cannot be selected in the top hierarchy, it can be selected in the lower hierarchies. In other words, in areas where frequency transforms with small transform sizes are valid, by not selecting the partitions belonging to the top hierarchy and selecting partitions in the lower hierarchies where frequency transforms with small transform sizes are available, the increase in the amount of code in the coded data can be suppressed. In particular, for large partitions, based on the fact that frequency transforms with large transform sizes are valid, when there are multiple frequency transforms with similar transform sizes among the frequency transform candidates, it is preferable to restrict the frequency transforms with small transform sizes in the top hierarchy.

Similarly, when partitions are represented using a hierarchical structure, even if frequency transforms with relatively large transform sizes are limited using the partitions belonging to the lowest hierarchy, the amount of code for the encoded data does not increase substantially. In particular, for small partitions, based on the fact that frequency transforms with small transform sizes are effective, when there are multiple frequency transforms with similar transform sizes among the frequency transform candidates, it is preferable to limit the frequency transforms with larger transform sizes in the lowest hierarchy.

<Specific Example of Prohibited Conversion List Generation Processing>

A specific example of the process of generating transformation constraints, i.e., a prohibited transformation list for each partition, for a specific partition structure in the transformation constraint derivation unit 104, as described above, will be described with reference to FIG9 . As shown in FIG9 , after the extended MB is divided into four at level L0, the upper left portion is divided into one at level L1 (partition a), the upper right portion is divided into two horizontally at level L1 (partitions b and c), the lower left portion is divided into two vertically at level L1 (partitions d and e), and the lower right portion is divided into four at level L1.

For the area divided into four parts at level L1, the upper left portion is divided into one part at level L2 (partition f), the upper right portion is divided into two parts horizontally at level L2 (partitions g and h), the lower left portion is divided into two parts vertically at level L2 (partitions i and j), and the lower right portion is divided into four parts at level L2. Each part divided into four parts at level L2 is divided into one part at level L3 (partitions k, l, m, and n). As described above, the nine selectable transform sizes for frequency transform are 4×4, 8×8, 16×16, 16×1, 1×16, 8×1, 1×8, 16×8, and 8×16.

Partition a is 32×32 pixels in size and belongs to level L1. After applying the aforementioned prohibited transform list generation process, frequency transforms for transform sizes of 4×4, 8×1, and 1×8 are added to the prohibited transform list in step S51, 8×8 in step S52, and 1×16, 16×1, 16×8, and 8×16 in step S67.

Partitions b and c are 32×16 pixels in size and belong to level L1. After applying the aforementioned prohibited transform list generation process, frequency transforms for transform sizes of 4×4, 8×1, and 1×8 are added to the prohibited transform list in step S51; 4×4, 8×8, and 16×16 are added in step S61; and 1×16 and 8×16 are added in step S62.

Partitions d and e are 16×32 pixels in size and belong to level L1. After applying the aforementioned prohibited transform list generation process, frequency transforms for transform sizes of 4×4, 8×1, and 1×8 are added to the prohibited transform list in step S51; 4×4, 8×8, and 16×16 are added in step S64; and 16×1 and 16×8 are added in step S65.

Partition f is 16×16 pixels in size and belongs to level L2. After applying the aforementioned prohibited transformation list generation process, frequency transforms for transform sizes of 4×4, 8×1, and 1×8 are added to the prohibited transformation list in step S51, and 16×1, 1×16, 16×8, and 8×16 are added to the prohibited transformation list in step S67.

Partitions g and h are 16×8 pixels in size and belong to level L2. After applying the aforementioned prohibited transform list generation process, frequency transforms for transform sizes of 16×16, 1×16, and 8×16 are added to the prohibited transform list in step S41; 4×4, 8×8, and 16×16 are added in step S61; and 1×16 and 8×16 are added in step S62.

Partitions i and j are 8×16 pixels in size and belong to level L2. After applying the aforementioned prohibited transform list generation process, frequency transforms for transform sizes of 16×16, 16×1, and 16×8 are added to the prohibited transform list in step S41; 4×4, 8×8, and 16×16 are added in step S64; and 16×1 and 16×8 are added in step S65.

Partitions k, l, m, and n are 8×8 pixels in size and belong to level L3. After applying the aforementioned prohibited transform list generation process, frequency transforms for transform sizes of 16×16, 16×1, 16×8, 1×16, and 8×16 are added to the prohibited transform list in step S41; 16×1, 16×8, 1×16, and 8×16 are added in step S67; and 8×8 and 16×16 are added in step 5b.

As in the above example, for other extended MBs having a partition structure, a prohibited conversion list may be generated for each partition within the extended MB and output as a conversion constraint.

In the above description, all of processes S42, S43, and S44 are executed during the prohibited transformation list generation process. However, only a portion of these processes may be used. Furthermore, in the detailed process of process S42, only one of the determinations in process S50 and process S51 may be executed. Furthermore, in the detailed process of process S43, only a portion of each of processes S60, S63, and S66 may be executed, and post-determination processing may only be executed for either process S61 or S62, or either process S64 or S65. Furthermore, in the detailed process of process S44, only one of the determinations in process S70 or process S72 may be executed. By omitting such processes, the computational processing required for prohibited transformation list generation can be reduced.

<Frequency Conversion Determination Unit 105>

The frequency transformation determination unit 105 determines the frequency transformation to be applied to each partition within the extended MB using the input transformation constraints, and outputs this information as a transformation selection flag. The process of determining the frequency transformation to be applied to a specific partition p is as follows.

(Process S120) Extract the prohibited transformation list Lp corresponding to the partition p from the transformation constraints.

(Process S121) A difference set between the preset conversion set and the prohibited conversion list Lp is obtained as a candidate conversion list Cp.

(Process S122) If the candidate transform list Cp is empty, the frequency transform with the smallest transform size among the frequency transforms for square transform sizes included in the transform preset set is added to the candidate transform list Cp. This process is necessary to avoid situations where there is no frequency transform to be applied when the prohibited transform list is consistent with the transform preset set. This process can be omitted if a prohibited transform list inconsistent with the transform preset set is always generated.

(Process S123) The rate-distortion cost when each frequency transform included in the transform candidate list Cp is applied is calculated, and the frequency transform that minimizes the rate-distortion cost is set as the frequency transform to be applied to the partition p.

<Variable Length Coding Unit 108>

The variable-length coding unit 108 generates and outputs coded data corresponding to the transform coefficients, prediction parameters, transform constraints, and transform selection flag in the extended MB based on the input transform coefficients, prediction parameters, transform constraints, and transform selection flag.

The transform coefficients and prediction parameters are variable-length coded using existing methods and then output. The transform selection flag is variable-length coded using transform constraints and then output. The variable-length coding process of the transform selection flag is described below with reference to the flowchart in FIG10 .

(Process S80) If the division method of the layer L0 in the extended MB is other than four divisions, the process of process S81 is executed; otherwise, the processes of process S82 to process S92 are executed.

(Process S81) Variable-length coding is performed on information indicating the frequency transformation applied to each partition within the processing unit (64×64 pixels) of the hierarchy L0, and the process is terminated.

(Process S82) The following processes of process S83 to process S92 are executed for each processing unit (32×32 pixels) of the layer L1 obtained by dividing the processing unit of the layer L0 into four.

(Step S83) If the division method of the layer L1 in the current processing unit (32×32 pixels) is other than four-division, the process proceeds to Step S84; otherwise, the process proceeds to Step S85.

(Step S84) Variable-length coding is performed on information indicating the frequency transformation applied to each partition within the current processing unit (32×32 pixels), and then the process proceeds to Step S92.

(Process S85) The following processes of process S86 to process S91 are applied to each of the processing units (16×16 pixels) of the layer L2 obtained by dividing the processing unit (32×32 pixels) of the layer L1 into four.

(Step S86) If the division method of the layer L2 in the current processing unit (16×16 pixels) is other than four-division, the process proceeds to step S87; otherwise, the process proceeds to step S88.

(Step S87) Variable-length coding is performed on information indicating the frequency transformation applied to each partition within the current processing unit (16×16 pixels), and then the process proceeds to Step S91.

(Process S88) The following processes of process S89 to process S90 are executed for each processing unit (8×8 pixels) of the layer L3 obtained by dividing the processing unit of the layer L2 into four.

(Step S89) Variable-length coding is performed on information indicating the frequency transformation applied to each partition within the current processing unit (8×8 pixels), and then the process proceeds to Step S90.

(Step S90) If the processing of all processing units (8×8 pixels) is completed, the process proceeds to Step S91. Otherwise, the next processing unit (8×8 pixels) is set and the process proceeds to Step S89.

(Step S91) If the processing of all processing units (16×16 pixels) is completed, the process proceeds to step S92. Otherwise, the next processing unit (16×16 pixels) is set and the process proceeds to step S86.

(Step S92) If the processing of all processing units (32×32 pixels) is completed, the processing is terminated. Otherwise, the next processing unit (32×32 pixels) is set and the process proceeds to Step S83.

The variable-length coding of the transform selection flag corresponding to a specific partition p is performed using the following procedure.

(Process S130) Extract the prohibited transformation list Lp corresponding to the partition p from the transformation constraints.

(Process S131) A difference set between the preset conversion set and the prohibited conversion list Lp is obtained as a candidate conversion list Cp.

(Process S132) If the transform candidate list Cp is empty, the frequency transform with the smallest transform size among the frequency transforms of the square transform size included in the transform preset set is added to the transform candidate list Cp. The frequency transform added in this process is not limited to the frequency transforms described above; it may also be a frequency transform with a transform size smaller than that of other partitions p included in the transform preset set. However, it must be the same frequency transform used in process S122 of the frequency transform determination unit.

(Process S133) If the number of frequency transforms included in the transform candidate list Cp is only one, the variable-length coding process is terminated. In this case, even if information indicating the frequency transform applied to partition p is not included in the encoded data, it is possible to uniquely determine which frequency transform to apply when decoding the data, so no problem occurs.

(Process S134) The frequency transforms included in the transform candidate list Cp are rearranged in a given order and associated with indexes that increase by 1 starting from 0.

(Step S135) Variable-length encoding is performed on the index associated with the frequency transform applied to partition p. As a variable-length encoding method for the index, for example, the following method can be applied: assuming the number of elements in the frequency transform candidate list is s, the index value is binarized with t bits using the smallest t such that 2 raised to the power of t is greater than s, and the resulting bit string is used as the encoded data.

If the number of elements in the frequency transform candidate list is small, the amount of code required for index encoding is reduced. Specifically, by setting prohibited transforms for each partition, the amount of code required for encoding the transform selection flag can be reduced. Furthermore, if the number of elements in the frequency transform candidate list is small, the amount of computation required for encoding the frequency transform to be applied can be reduced.

Furthermore, the order specified in step S134 can be, for example, as follows: a frequency transform with a large transform size is assigned a smaller index than a frequency transform with a small transform size; a square transform is assigned a smaller index than a horizontally rectangular transform; and a horizontally rectangular transform is assigned a smaller index than a vertically rectangular transform. In this case, it is easy to associate smaller indices in the order of 16×16 DCT, 16×8 DCT, 8×16 DCT, 8×8 DCT, 4×4 DCT, 16×1 DCT, 1×16 DCT, 8×1 DCT, and 1×8 DCT.

As another example, the given order in the above-mentioned process S134 can also be the order of the highest selection frequency of each frequency transform. Specifically, after the encoding process of the input motion image is started, the number of times each transform in the transform preset set is selected as the transform of the partition is counted, and the following order is created: smaller indices are assigned to frequency transforms with higher selection frequencies. In this case, since a bias is also generated in the frequency of occurrence of the index, the amount of code when the index is variable-length encoded in process S135 is reduced. In addition, at appropriate timing such as when the encoding of a new frame starts or when the encoding of a set of a given number of extended MBs, i.e., a slice, starts, the coefficient value of the above-mentioned number of selections can be initialized to a specified value such as zero. In addition, the number of conditional frequency transform selections, for example, the number of selections of each frequency transform for each partition size, can also be counted and utilized.

Furthermore, other methods may be used for variable-length coding of the index in the above-mentioned step S135, such as various VLCs and CABAC specified in H.264/AVC.

In addition, instead of directly performing variable-length coding on the index, a flag indicating whether it is consistent with the index prediction value may be encoded, and the index may be variable-length coded only when the flag indicates inconsistency. The frequency transform used by the processing object partition is estimated using the information of the extended MB that has been coded (local decoded image, partition structure, motion vector, etc.), and the index corresponding to the frequency transform can be used as the index prediction value. In particular, it is preferred to derive the index prediction value based on the frequency transform applied to the partition near the processing object partition, taking into account the spatial correlation of the frequency transform. Specifically, the following method is preferred: the index of the frequency transform applied to each partition located to the left, above, and above the right of the processing object partition is derived separately; and if two or more of these indices are consistent, the value is used as the index prediction value, otherwise the minimum value among these indices is used as the index prediction value.

Furthermore, the variable-length encoding process for the transform selection flags described above describes the case where the transform selection flags for all partitions are variable-length encoded. However, if the frequency transform applied to each partition belonging to the same processing unit of a specific layer Lx is the same, variable-length encoding can be performed on the transform selection flags common to the partitions within the processing unit for each layer Lx. While this reduces the degree of freedom in selecting a frequency transform, encoding the transform selection flag for each layer Lx processing unit eliminates the need to encode the transform selection flag for each partition, thus reducing the amount of code required to encode the transform selection flag. Alternatively, partitions can be further divided into units of frequency transforms whose size is not less than the maximum transform size included in the transform candidate list, and the transform selection flag can be encoded for each unit.

<Prediction Residual Reconstruction Unit 109>

The prediction residual reconstruction unit 109 performs inverse frequency transformation on the transform coefficients based on the input transform coefficients and the transform selection flag, thereby reconstructing the prediction residual and outputting it. If the transform coefficients are quantized, inverse quantization is applied before frequency transformation.

<Local Decoded Image Generator 110>

The local decoded image generation unit 110 generates and outputs a local decoded image based on the input predicted image and prediction residual. Each pixel value in the local decoded image is the sum of the pixel values corresponding to the predicted image and the prediction residual. Furthermore, a filter may be applied to the local decoded image to reduce block distortion and quantization error at block boundaries.

<Operation of Moving Image Coding Device 10>

Next, the operation of the moving picture encoding device 10 will be described.

(Process S100) An input moving picture input from the outside to the moving picture encoding device 10 is sequentially input to the prediction parameter determination unit 102 and the prediction residual generation unit 106 in units of extended MBs, and the subsequent processes of S101 to S109 are sequentially performed on each extended MB.

(Process S101 ) The prediction parameter determination unit 102 determines prediction parameters for the extended MB to be processed based on the input moving picture, and outputs the prediction parameters to the prediction picture generation unit 103 and the variable-length coding unit 108 .

(Process S102) In the prediction image generation unit 103, a prediction image that is approximate to the area of the processing object extended MB in the input motion image is generated based on the input prediction parameters and the local decoded image recorded in the frame memory 101, and is output to the prediction residual generation unit 106 and the local decoded image generation unit 110.

(Process S103 ) The prediction residual generation unit 106 generates a prediction residual corresponding to the extended MB to be processed based on the input moving picture and the predicted picture, and outputs it to the frequency transformation determination unit 105 and the transform coefficient generation unit 107 .

(Process S104) The transform constraint derivation unit 104 derives constraints on frequency transform in each partition of the extended MB to be processed as transform constraints based on the input prediction parameters, and outputs them to the frequency transform determination unit 105 and the variable length coding unit 108.

(Process S105) In the frequency transform determination unit 105, the frequency transform applied to each partition of the processing target extended MB is determined based on the input transform constraint and prediction residual, and is output as a transform selection flag to the transform coefficient generation unit 107, the variable length coding unit 108, and the prediction residual reconstruction unit 109.

(Process S106) In the transform coefficient generation unit 107, the frequency transform specified by the input transform selection flag is applied to the input prediction residual to generate the transform coefficient corresponding to the processing target extended MB, and output it to the variable length coding unit 108 and the prediction residual reconstruction unit 109.

(Process S107) In the prediction residual reconstruction unit 109, the inverse frequency transform corresponding to the frequency transform specified by the input transform selection flag is applied to the input transform coefficient, and the prediction residual corresponding to the processing target extended MB is reconstructed and output to the local decoded image generation unit 110.

(Process S108) The local decoded image generation unit 110 generates a local decoded image based on the input prediction residual and the predicted image, and outputs the local decoded image to the frame memory 101 for storage.

(Process S109) In the variable-length coding unit 108, variable-length coding is performed on the input transform coefficients, prediction parameters, and transform selection flag using the input transform constraints, and the result is output to the outside as coded data.

Through the above-described process, the moving picture encoding device 10 can encode the input moving picture to generate encoded data and output it to the outside.

<Configuration of Moving Image Decoding Device 20>

Next, a description will be given of a moving picture decoding device 20 that decodes the coded data coded by the moving picture coding device 10 to generate a decoded moving picture.

11 is a block diagram showing the configuration of the image decoding device 20 . The moving picture decoding device 20 includes a frame memory 101 , a prediction image generation unit 103 , a transform constraint derivation unit 104 , a prediction residual reconstruction unit 109 , a local decoded image generation unit 110 , and a variable length code decoding unit 201 .

The variable-length code decoding unit 201 decodes and outputs prediction parameters, a transform selection flag, and transform coefficients based on the input coded data and transform constraints. Specifically, the prediction parameters are first decoded from the coded data and output. Next, the transform selection flag is decoded from the coded data using the transform constraints and output. Finally, the transform coefficients are decoded from the coded data using the transform selection flag and output.

<Operation of Video Decoding Device 20>

Next, the operation of the moving picture decoding device 20 will be described.

(Process S110) The coded data input from the outside to the moving picture decoding device 20 is sequentially input to the variable length code decoding unit 201 in units of extended MBs, and the subsequent processes S111 to S117 are sequentially performed on the coded data corresponding to each extended MB.

(Process S111 ) The variable-length code decoding unit 201 decodes the prediction parameters corresponding to the processing target extended MB from the input coded data, and outputs the decoded prediction parameters to the predicted image generating unit 103 and the transform constraint deriving unit 104 .

(Process S112 ) The transform constraint derivation unit 104 derives constraints on frequency transform in each partition of the processing target extended MB based on the input prediction parameters as transform constraints, and outputs them to the variable length code decoding unit 201 .

(Process S113) The variable length code decoding unit 201 decodes the transform selection flag corresponding to the processing target MB based on the input coded data and transform constraints, and outputs it to the prediction residual reconstruction unit 109.

(Process S114) In the variable-length code decoding unit 201, based on the input coded data and the transform selection flag derived in (Process S113), the transform coefficients corresponding to the processing target extended MB are decoded and output to the prediction residual reconstruction unit 109.

(Process S115 ) The predicted image generator 103 generates a predicted image corresponding to the extended MB to be processed based on the input prediction parameters and the local decoded image stored in the frame memory 101 , and outputs the predicted image to the local decoded image generator 110 .

(Process S116) In the prediction residual reconstruction unit 109, the inverse frequency transform corresponding to the frequency transform specified by the input transform selection flag is applied to the input transform coefficient, and the prediction residual corresponding to the processing target extended MB is reconstructed and output to the local decoded image generation unit 110.

(Process S117) In the local decoded image generation unit 110, a local decoded image is generated based on the input prediction residual and the prediction image, and is output to the frame memory 101 for storage, and is output to the outside as a region on the decoded moving image corresponding to the processing target block.

As described above, the moving picture decoding device 20 can generate a decoded moving picture from the encoded data generated by the moving picture encoding device 10 .

<Supplementary Note 1: Use of Information Other Than Partition Size and Hierarchy>

Furthermore, in the description of the moving picture encoding device 10 and the moving picture decoding device 20, a method has been described in which a prohibited transform list is generated for each partition within an extended MB based solely on the partition size and the hierarchy to which the partition belongs. However, other information that can be reproduced during decoding based on information included in the encoded data may also be used. For example, a motion vector or reference picture index included in the prediction parameters may be used to derive the prohibited transform list.

The following describes the process of adding a frequency transform to the prohibited transform list using a motion vector and a reference image index in a specific partition p. Furthermore, the motion vector of partition p is set to mvp, and the reference image index is set to refp. Furthermore, among the partitions adjacent to the upper edge of partition p, the motion vector of the partition located to the left (partition u) is set to mvu, and the reference image index is set to refu. Furthermore, among the partitions adjacent to the left edge of partition p, the motion vector of the partition located above (partition 1) is defined as mvl, and the reference image index is defined as refl.

(Process S140) If mvp, mvu, and mvl are all consistent, and refp, refu, and refl are all consistent, the process proceeds to process S141. Otherwise, the process ends.

(Process S141) When there are two or more frequency transforms with similar transform sizes in the frequency transform list, the frequency transform with the smallest transform size in the group of frequency transforms with similar transform sizes is added to Lp, and then the process ends.

The consistency of motion vectors between adjacent blocks indicates that the spatial correlation of motion vectors is high in the local area near the extended MB to be coded. High spatial correlation of motion vectors tends to also increase the spatial correlation of pixel values. Therefore, even if frequency transforms with similar transform sizes are prohibited from being applied to frequency transforms with small transform sizes, the increase in the amount of coded data is minimal.

In addition, in the above description, the motion vector and reference image index used for deriving the prohibited transformation list are used as the motion vector and reference image index of the adjacent partition of partition p, but other motion vectors can also be used. For example, the motion vector within the extended MB adjacent to the extended MB (processing target extended MB) to which partition p belongs can be used. Specifically, the motion vector of the partition located in the upper right of the extended MB adjacent to the left side of the processing target extended MB is used as mvl, and the motion vector of the partition located in the lower left of the extended MB adjacent to the upper side of the processing target extended MB is used as mvu. In this case, all partitions within the extended MB use the same mvl and mvu, so the processing of processes S140 and S141 can be performed in parallel on a partition basis.

<Supplementary Note 2: Regarding the Timing of Generating the Prohibited Conversion List>

Furthermore, in the description of the moving image encoding device 10 and the moving image decoding device 20, the transform constraint derivation unit 104 has been described as executing the prohibited transform list generation process for each partition of the extended MB on a continuous basis. However, if frequency transforms are added to the prohibited transform list based solely on the partition size and the hierarchy to which the partition belongs, the prohibited frequency transform list can be generated in advance at a predetermined timing. In this case, the prohibited transform list generated in advance for each partition type must be associated with each partition within the extended MB in the transform constraint derivation unit 104. The predetermined timing can be immediately after the start of encoding of the input moving image or the start of decoding of the encoded data, or immediately after the start of encoding or decoding of a predetermined coding unit such as a sequence, frame, or slice. By reducing the number of times the prohibited transform list generation process is executed, the encoding and decoding processing load can be reduced.

In contrast, when adding a frequency transform to the prohibited transform list using a motion vector or reference picture index, it is necessary to perform the prohibited transform list generation process on a continuous basis for each extended MB, as described above with respect to the moving picture encoding apparatus 10 and the moving picture decoding apparatus 20. In this case, while the increased number of prohibited transform list generation processes increases the encoding and decoding processing load, compared to a case where generation is not performed for each MB, more information that can be derived from the coded data can be used, enabling generation of a prohibited transform list that is more appropriate to the local characteristics of the moving picture.

(Implementation Method 2)

12 to 14 , a moving picture encoding device 11 and a moving picture decoding device 21 as another embodiment of the moving picture encoding device and the moving picture decoding device of the present invention will be described. In the description of the drawings, the same elements are denoted by the same reference numerals and their description will be omitted.

The motion image encoding device 11 and the motion image decoding device 21 of this embodiment are characterized in that the transformation constraint derivation unit 104 in the motion image encoding device 10 and the motion image decoding device 20 is replaced by the transformation candidate derivation unit 111, so that the prohibited transformation list is not generated and the transformation candidate list is directly derived.

The conversion constraint derivation unit 104 and the conversion candidate derivation unit 111 are collectively referred to as a conversion control derivation unit.

FIG12 is a block diagram showing the configuration of the moving picture coding apparatus 11. The moving picture coding apparatus 11 includes a frame memory 101, a prediction parameter determination unit 102, a prediction image generation unit 103, a prediction residual generation unit 106, a transform coefficient generation unit 107, a prediction residual reconstruction unit 109, a local decoded image generation unit 110, a transform candidate derivation unit 111, a frequency transform determination unit 112, and a variable length coding unit 113.

The transform candidate derivation unit 111 outputs information on frequency transforms selectable in each partition within the extended MB as a transform candidate list based on the input prediction parameters. In other words, the transform candidate list for each partition is generated based on the partition shape information of the partition determined by the prediction parameters.

The transform candidate list is associated with each partition in the extended MB, and defines a set of frequency transforms that can be selected by each partition among the frequency transforms included in the transform preset set.

The conversion candidate list Cp for a specific partition p is generated by the following process: Assume that the size of the partition p is M×N pixels (M pixels horizontally and N pixels vertically). Assume that the partition p belongs to the hierarchy Lx.

(Process S150) A frequency conversion determined according to the magnitude relationship between M and N is added to Cp.

(Process S151) If Cp is empty, a frequency transform having a transform size smaller than all partition sizes and having the largest transform size among frequency transforms is added to Cp.

The above-mentioned process S150 will be described in more detail with reference to the flowchart of FIG. 13 .

(Step S160) Using a given value Th3 (e.g., Th3 = 16 below), the values of Min(M, Th3) are set for M1, and Min(N, Th3) are set for N1. Th3 is preferably set to the length of one side of the transform size of the largest square frequency transform included in the transform preset set. If a frequency transform with a transform size of M1 × N1 exists in the transform preset set, that frequency transform is added to the candidate transform list Cp, and the process proceeds to Step S161.

(Process S161) When M is larger than N (when the partition p is a horizontal rectangle), proceed to process S162; otherwise, proceed to process S163.

(Process S162) If there is a frequency transform having a transform size of M1×1 in the transform preset set, the frequency transform is added to the transform candidate list Cp, and the process ends.

(Process S163) When M is smaller than N (when the partition p is a vertically long rectangle), the process proceeds to process S164; otherwise, the process proceeds to process S165.

(Process S164) If there is a frequency transform having a transform size of 1×N1 in the transform preset set, the frequency transform is added to the transform candidate list Cp, and the process ends.

(Step S165) M2 is set to the value of M1÷2, and N2 is set to the value of N1÷2. If a frequency transform with a transform size of M2×N2 exists in the transform preset set, the frequency transform is added to the transform candidate list Cp, and the process ends. This step is executed when M and N are equal (when partition p is a square).

The above-mentioned size relationship between M and N and the partition size M×N are partition shape information.

In the above process, if a horizontally rectangular (vertically rectangular) partition exists in the transform preset set, a frequency transform of a transform size in which the partition's vertical (horizontal) length is shorter than its height (width) is added to the transform candidate list Cp. As mentioned with reference to FIG6 in the description of the prohibited transform list derivation process in the transform constraint derivation unit 104 of the motion picture coding device 10, a frequency transform of a horizontally rectangular (vertically rectangular) transform size is effective for a horizontally rectangular (vertically rectangular) partition. In particular, by using a frequency transform of a transform size in which the short side is significantly shorter than the long side, the presence of object boundaries within the transform size can be reduced, thereby enhancing the frequency transform's effect of concentrating energy on the low-frequency components of the transform coefficients.

The frequency transform determination unit 112 uses the input candidate transform list to determine the frequency transform to be applied to each partition within the extended MB and outputs this information as a transform selection flag. Specifically, the frequency transform determination unit 112 calculates the rate-distortion cost when applying each frequency transform included in the candidate transform list Cp and selects the frequency transform that minimizes the rate-distortion cost as the frequency transform to be applied to partition p.

The variable length coding unit 113 generates and outputs coded data corresponding to the transform coefficient, prediction parameter, variable length code, transform candidate list, and transform selection flag in the extended MB based on the input transform coefficient, prediction parameter, variable length code, and transform selection flag.

The variable-length coding process for the transform selection flag in each partition within the extended MB is the same as processes S80 to S92 ( FIG. 10 ) in the variable-length coding unit 108 of the moving picture coding apparatus 10. As the detailed variable-length coding process for the transform selection flag in a specific partition p, processes S133 to S135 in the variable-length coding unit 108 are applied.

Next, the operation of the moving picture encoding device 11 will be described.

(Process S170) The input moving picture input from the outside to the moving picture encoding device 11 is sequentially input to the prediction parameter determination unit 102 and the prediction residual generation unit 106 in units of extended MBs, and the subsequent processes of S171 to S179 are sequentially performed on each extended MB.

(Process S171) The prediction parameter determination unit 102 determines prediction parameters for the extended MB to be processed based on the input moving picture, and outputs the parameters to the predicted picture generation unit 103 and the variable-length coding unit 113.

(Process S172) In the prediction image generation unit 103, a prediction image that is approximate to the area of the processing object extended MB in the input motion image is generated based on the input prediction parameters and the local decoded image recorded in the frame memory 101, and is output to the prediction residual generation unit 106 and the local decoded image generation unit 110.

(Process S173 ) The prediction residual generation unit 106 generates a prediction residual corresponding to the extended MB to be processed based on the input moving picture and the predicted picture, and outputs it to the frequency transformation determination unit 112 and the transform coefficient generation unit 107 .

(Process S174) The transform candidate derivation unit 111 derives constraints on frequency transform in each partition of the processing target extended MB based on the input prediction parameters, and outputs the constraints to the frequency transform determination unit 112 and the variable length coding unit 113.

(Process S175) In the frequency transformation determination unit 112, the frequency transformation applied to each partition of the processing object extended MB is determined based on the input transformation constraints and prediction residuals, and is output as a transformation selection flag to the transformation coefficient generation unit 107, the variable length coding unit 113, and the prediction residual reconstruction unit 109.

(Process S176) In the transform coefficient generation unit 107, the frequency transform specified by the input transform selection flag is applied to the input prediction residual, thereby generating a transform coefficient corresponding to the processing target extended MB, and outputting it to the variable length coding unit 108 and the prediction residual reconstruction unit 109.

(Process S177) In the prediction residual reconstruction unit 109, the inverse frequency transform corresponding to the frequency transform specified by the input transform selection flag is applied to the input transform coefficient, thereby reconstructing the prediction residual corresponding to the processing object extended MB and outputting it to the local decoded image generation unit 110.

(Process S178) The local decoded image generation unit 110 generates a local decoded image based on the input prediction residual and the predicted image, and outputs the local decoded image to the frame memory 101 for storage.

(Process S179) In the variable-length coding unit 113, the input transform coefficients, prediction parameters, and transform selection flag are variable-length coded using the input transform constraints, and are output to the outside as coded data.

Through the above-described process, the moving picture encoding device 11 can encode the input moving picture to generate encoded data and output it to the outside.

<Other Examples of Conversion Candidate List Generation Method>

While the description of the transform candidate derivation unit 111 above illustrates an example of a transform candidate list generation method, other methods may also be used to generate a transform candidate list. For example, when the transform preset set includes two similar frequency transforms, DCTa and DCTb (where DCTa's transform size is larger than DCTb's), a transform candidate list generation method is also effective in which DCTa is added to the transform candidate list for partitions included in the upper hierarchy, but DCTb is not added, and DCTb is added to the transform candidate list for partitions included in the lower hierarchy. More specifically, when the transform preset set includes both the 16×16 DCT and the 8×8 DCT, at least the 16×16 DCT is added to the transform candidate list for partitions included in hierarchy L0, which processes 64×64 pixels, but not the 8×8 DCT, and at least the 8×8 DCT is added to the transform candidate list for partitions included in hierarchy L1, which processes 32×32 pixels.

Even if a specific frequency transform DCTb (e.g., 8×8 DCT) cannot be selected for a partition belonging to a specific layer Lx, if DCTb can be selected for partitions belonging to the layer Ly below layer Lx, then in areas where DCTb is available, the increase in the amount of coded data can be suppressed by selecting partitions belonging to the lower layer Ly where DCTb can be selected, rather than selecting partitions belonging to the upper layer Lx. This is particularly effective for large partitions, as frequency transforms with large transform sizes are available. Instead of prohibiting DCTb selection for partitions belonging to the upper layer Lx, a DCTb with a larger transform size (e.g., 16×16 DCT) can be selected, while allowing DCTb to be selected for partitions belonging to the lower layer Ly.

<Configuration of Moving Image Decoding Device 21>

Next, a description will be given of the moving picture decoding device 21 that decodes the coded data coded by the moving picture coding device 11 to generate a decoded moving picture.

14 is a block diagram showing the configuration of the image decoding device 21 . The moving picture decoding device 20 includes a frame memory 101 , a predicted image generator 103 , a prediction residual reconstruction unit 109 , a local decoded image generator 110 , a transform candidate derivation unit 111 , and a variable length code decoder 202 .

The variable-length code decoding unit 202 decodes and outputs prediction parameters, a transform selection flag, and transform coefficients based on the input coded data and the transform candidate list. Specifically, the prediction parameters are first decoded from the coded data and output. Next, the transform selection flag is decoded from the coded data using the transform candidate list and output. Finally, the transform coefficients are decoded from the coded data using the transform selection flag and output. While decoding the transform selection flag requires knowing how many bits were used to encode the transform selection flag, this does not necessarily require information about the elements included in the transform candidate list; simply knowing the number of elements in the transform candidate list is sufficient. In this case, the signal input to the variable-length code decoding unit 202 and the signal used to decode the transform selection flag may simply be information about the number of elements in the transform candidate list.

<Operation of Moving Image Decoding Device 21>

Next, the operation of the moving picture decoding device 21 will be described.

(Process S180) The coded data input from the outside to the moving picture decoding device 20 is sequentially input to the variable length code decoding unit 201 in units of extended MBs, and the subsequent processes S181 to S187 are sequentially performed on the coded data corresponding to each extended MB.

(Process S181) The variable-length code decoding unit 202 decodes the prediction parameters corresponding to the processing target extended MB from the input coded data and outputs the decoded prediction parameters to the predicted image generating unit 103 and the transform candidate deriving unit 111.

(Process S182) The transform candidate derivation unit 111 derives a transform candidate list for each partition of the processing target extended MB based on the input prediction parameters, and outputs the list to the variable-length code decoding unit 202.

(Process S183) In the variable-length code decoding unit 202, the transform selection flag corresponding to the processing target MB is decoded based on the input coded data and transform constraints, and output to the prediction residual reconstruction unit 109.

(Process S184) In the variable length code decoding unit 202, based on the input coded data and the transform selection flag derived in (Process S183), the transform coefficient corresponding to the processing target extended MB is decoded and output to the prediction residual reconstruction unit 109.

(Process S185) The predicted image generator 103 generates a predicted image corresponding to the processing target extended MB based on the input prediction parameters and the local decoded image stored in the frame memory 101, and outputs the predicted image to the local decoded image generator 110.

(Process S186) In the prediction residual reconstruction unit 109, the inverse frequency transform corresponding to the frequency transform specified by the input transform selection flag is applied to the input transform coefficient, and the prediction residual corresponding to the processing target extended MB is reconstructed and output to the local decoded image generation unit 110.

(Process S187) In the local decoded image generation unit 110, a local decoded image is generated based on the input prediction residual and the prediction image, and is output to the frame memory 101 for storage, and is output to the outside as an area on the decoded moving image corresponding to the processing target block.

<Decoder Summary>

As described above, the moving picture decoding device 21 can generate a decoded moving picture from the encoded data generated by the moving picture encoding device 11 .

(Implementation 3)

Next, referring to Figures 15 and 16 , a moving picture encoding device 30 and a moving picture decoding device 40, which are other embodiments of the moving picture encoding device and moving picture decoding device according to the present invention, will be described. In the description of the figures, identical elements are denoted by identical reference numerals, and their description will be omitted. Furthermore, the partition structures and transform presets usable in the moving picture encoding device 30 and the moving picture decoding device 40 are the same as those used in the moving picture encoding device 11 and the moving picture decoding device 21.

The motion image encoding device 30 and the motion image decoding device 40 in this embodiment are different from the motion image encoding device 11 and the motion image decoding device 21 in that they have the following function: using given units larger than MB, such as scenes, frames, and slices of motion images, to adaptively change the derivation method of the transformation candidate list of the transformation candidate derivation unit to match the nature of the motion images.

FIG15 is a block diagram showing the configuration of the moving picture coding apparatus 30. The moving picture coding apparatus 30 includes a frame memory 101, a prediction parameter determination unit 102, a prediction image generation unit 103, a prediction residual generation unit 106, a transform coefficient generation unit 107, a prediction residual reconstruction unit 109, a local decoded image generation unit 110, a frequency transform determination unit 112, a transform candidate list derivation rule determination unit 301, a transform candidate derivation unit 302, and a variable length coding unit 303.

The conversion candidate list derivation rule determination unit 301 generates conversion candidate list derivation rules for defining or updating the conversion candidate list derivation method used by the conversion candidate derivation unit based on an input moving image input in predetermined units larger than MB, such as scenes, frames, or slices. For simplicity of explanation, the conversion candidate list derivation rules are generated for each frame.

(Definition of the conversion candidate list derivation rule)

The conversion candidate list derivation rules are defined as a combination of the following basic rules.

Basic Rule 1: Specifies that for a given partition A, a given frequency transform B in the preset transform set be added to the transform candidate list. Hereinafter, Basic Rule 1 is described using the format [permit, partition A, frequency transform B]. For example, [permit, 64×64, T16×16] indicates that a T16×16 frequency transform is added to the transform candidate list for a 64×64 partition.

Basic Rule 2: For a given partition A, a given frequency transform B within the transform preset set is prohibited from being included in the transform candidate list. Below, Basic Rule 2 is described using the format [prohibit, partition A, frequency transform B]. For example, [prohibit, 64×64, T4×4] prohibits T4×4 from being included in the transform candidate list for a 64×64 partition.

Basic Rule 3: When a given frequency transform B in the transform preset set is included in the transform candidate list for a given partition A, frequency transform B in the transform candidate list is replaced with another frequency transform C. Furthermore, Basic Rule 3 is described below using the format [replace, partition A, frequency transform B, frequency transform C]. For example, [replace, 64×32, T4×4, T16×1] indicates that when T4×4 is included in the transform candidate list for a 64×32 partition, T4×4 is removed from the transform candidate list and T16×1 is added to the transform candidate list.

That is, the conversion candidate list derivation rule includes a plurality of basic rules, and each basic rule is classified into any one of the basic rules 1 to 3 described above.

Furthermore, in addition to basic rules, the conversion candidate list derivation rules may also include compound rules represented by a combination of basic rules, or may be used in place of basic rules. Several examples of compound rules are listed below.

Compound Rule 1: Prohibit specific transformations in partitions belonging to a specific hierarchy. For example, prohibiting transformations of sizes smaller than T8×8 in the L0 hierarchy corresponds to Compound Rule 1. The compound rule (R1) can be expressed as a set of the following basic rules.

R1 = {[Prohibit, P, T]: (P is a partition belonging to the L0 layer) ∧ (T is a frequency conversion of T8×8 or less)}

In addition, the rule that prohibits small-sized frequency transformations among frequency transformations that are in a similar relationship at the upper level of a given layer is also equivalent to the compound rule 1. More specifically, the rule that prohibits T8×8 and T4×4 among the transformations of T16×16, T8×8, and T4×4 that are in a similar relationship at the upper level of layer L1 is also equivalent to the compound rule 1.

Compound Rule 2: In a partition of a specific shape, a specific transformation A is replaced with a specific transformation B. For example, in a square partition, a rule that replaces a rectangular frequency transformation with a given square frequency transformation (e.g., T4×4) corresponds to Compound Rule 2. The compound rule (R2) can be expressed as a set of the following basic rules.

R2 = {[permutation, P, T, T4×4]: (P∈square partition)∧(T∈rectangular frequency transformation)}

Furthermore, a rule that replaces square frequency transformation with horizontally rectangular frequency transformation in horizontally rectangular partitions also corresponds to the composite rule 2.

(Determination process of conversion candidate list derivation rule)

First, before the start of encoding, rule candidates consisting of basic rules and composite rules are predefined, and the candidate transformation list derivation rules are set to empty. Next, for each input frame, the rate-distortion cost is calculated when encoding is performed using each basic rule or composite rule included in the candidate rules. Furthermore, the rate-distortion cost C1 is calculated when none of the candidate rules are applied. Next, the rate-distortion cost C2 when each basic rule or composite rule is applied is compared with cost C1. If cost C2 is less than cost C1, the basic rule or composite rule is applied and included in the candidate transformation list derivation rules.

Through the above-described process, only basic rules or composite rules that can reduce the rate-distortion cost by being applied during frame encoding among given rule candidates are added to the transformation candidate list derivation rules.

Based on the input prediction parameters and the transform candidate list derivation rule, the transform candidate derivation unit 302 outputs information regarding the frequency transforms selectable in each partition within the extended MB as a transform candidate list. The transform candidate list is associated with each partition within the extended MB and specifies the set of frequency transforms selectable in each partition from among the frequency transforms included in the transform preset set. The input transform candidate list derivation rule is also used in the transform candidate list derivation process.

The process of generating the conversion candidate list Cp for a specific partition p based on the input conversion candidate list derivation rule is as follows: It is assumed that the size of the partition p is M×N pixels (M pixels horizontally and N pixels vertically).

(Process S200) When the conversion candidate list derivation rules include compound rules, each compound rule is decomposed into basic rules and then added to the conversion candidate list derivation rules.

(Process S201) The process of process S202 is executed for all basic rules belonging to basic rule 1 included in the conversion candidate list.

(Step S202) The basic rule 1 to be processed is expressed as [permission, P1, T1]. If the shape of the partition p matches P1, the frequency transformation T1 is added to the transformation candidate list.

(Step S203) The process of step S204 is executed for all the basic rules belonging to basic rule 2 included in the conversion candidate list.

(Step S204) The basic rule 2 to be processed is expressed as [prohibit, P2, T2]. If the shape of the partition p matches P2 and the frequency transformation T2 is present in the transformation candidate list, the frequency transformation T2 is removed from the transformation candidate list.

(Step S205) The process of step S206 is executed for all the basic rules belonging to the basic rule 3 included in the conversion candidate list.

(Step S206) The basic rule 2 to be processed is expressed as [Permutation, P3, T3, T4]. If the shape of the partition p matches P3 and the frequency transformation T3 exists in the transformation candidate list, the frequency transformation T3 is replaced by the frequency transformation T4.

Through the above process, the conversion candidate derivation unit 302 can derive a conversion candidate list based on the input conversion candidate list derivation rule.

The variable-length coding unit 303 generates and outputs coded data corresponding to the input transform coefficients, prediction parameters, transform candidate lists, transform selection flags, and transform candidate list derivation rules.

The following describes the details of the process for generating coded data corresponding to the transformation candidate list derivation rules. The coded data is generated by variable-length encoding each base rule or composite rule included in the transformation candidate list derivation rules. In variable-length encoding of the base rules, information indicating whether the underlying base rule is classified as one of basic rules 1 to 3 is first encoded. Next, information indicating the partitions for which the underlying base rule applies is encoded. Finally, for basic rule 1, information indicating the types of frequency transformations to be permitted is encoded; for basic rule 2, information indicating the types of frequency transformations to be prohibited is encoded; and for basic rule 3, information indicating the types of frequency transformations before and after substitution is encoded. Furthermore, if the types of basic rules that can be included in the transformation candidate list derivation list are predetermined, the amount of code can be reduced by using information indicating whether the basic rule applies as coded data, rather than using the aforementioned method for variable-length encoding of the basic rules. Furthermore, if a specific basic rule is predetermined to always apply, variable-length encoding of that basic rule is unnecessary.

Composite rules are decomposed into basic rules and then encoded. Furthermore, if the types of composite rules that can be included in the transformation candidate list derivation list are predetermined, encoding information indicating whether the composite rule applies can reduce the amount of code. For example, in partitions larger than 32×32, the prohibition of applying composite rules such as T4×4 and T8×8 can be encoded as a 1-bit flag.

Furthermore, specific basic rules or composite rules can be grouped together to define a rule group, and information indicating whether each basic rule included in the rule group is applicable can be encoded, or a flag indicating whether the applicable application of all basic rules included in the rule group is estimated using a predetermined method can be encoded. Specifically, if the composite rules indicating the applicable application of T16×16, T8×8, and T4×4 in layer L3 are set to enable_t16×16_L3, enable_t16×16_L3, and enable_t16×16_L3, respectively, these three decoding rules are combined to create the rule group enable_L3. During encoding, the applicable application of enable_L3 is first encoded with one bit. When enable_L3 is applied, the applicable application of each composite rule included in the rule group is encoded with one bit. When enable_L3 is not applied, the applicable application of each composite rule is estimated using a predetermined method.

Furthermore, the basic rules and composite rules can be encoded together rather than as separate variable-length codes. For example, a flag indicating that all basic rules are not applied or that at least one basic rule is applied can be encoded, and only when the flag indicates that at least one basic rule is applied, information indicating whether each basic rule is applied is encoded. Furthermore, a flag indicating whether to inherit the candidate transformation list derivation rule applied in the previous frame can be encoded, and only when this flag indicates that the candidate transformation list derivation rule is not inherited is the candidate transformation list derivation rule encoded.

Next, the operation of the moving picture encoding device 30 will be described.

(Process S210) An input moving picture input from the outside to the moving picture coding device 30 is input to the transform candidate list derivation rule determination unit 301 on a frame-by-frame basis, and is then sequentially input to the prediction parameter determination unit 102 and the prediction residual generation unit 106 on an extended MB basis. Processes S211 and S212 are executed for each frame, and processes S213 to S221 are executed for each extended MB.

(Process S211) The transform candidate list derivation rule determination unit 301 generates a transform candidate list derivation rule based on the input frame and outputs the rule to the transform candidate derivation unit 302 and the variable length coding unit 303.

(Process S212) In the variable-length coding unit 303, corresponding coded data is generated based on the input transformation candidate list derivation rule and output to the outside.

(Process S213) The prediction parameter determination unit 102 determines prediction parameters for the processing target extended MB based on the input moving picture, and outputs the prediction parameters to the prediction image generation unit 103, the transform candidate derivation unit 302, and the variable length coding unit 303.

(Process S214) In the prediction image generation unit 103, based on the input prediction parameters and the local decoded image recorded in the frame memory 101, a prediction image that is approximate to the area of the processing object extended MB in the input motion image is generated and output to the prediction residual generation unit 106 and the local decoded image generation unit 110.

(Process S215 ) The prediction residual generation unit 106 generates a prediction residual corresponding to the extended MB to be processed based on the input moving picture and the predicted picture, and outputs it to the frequency transformation determination unit 112 and the transform coefficient generation unit 107 .

(Process S216) The transform candidate derivation unit 302 derives constraints on frequency transform in each partition of the processing target extended MB based on the input prediction parameters and transform candidate list derivation rule, and outputs the constraints to the frequency transform determination unit 112 and the variable length coding unit 303.

(Process S217) In the frequency transformation determination unit 112, the frequency transformation applied to each partition of the processing object extended MB is determined based on the input transformation constraints and prediction residuals, and is output as a transformation selection flag to the transformation coefficient generation unit 107, the variable length coding unit 303, and the prediction residual reconstruction unit 109.

(Process S218) In the transform coefficient generation unit 107, the frequency transform specified by the input transform selection flag is applied to the input prediction residual, and the transform coefficient corresponding to the processing target extended MB is generated and output to the variable length coding unit 108 and the prediction residual reconstruction unit 109.

(Process S219) In the prediction residual reconstruction unit 109, the inverse frequency transform corresponding to the frequency transform specified by the input transform selection flag is applied to the input transform coefficient, thereby reconstructing the prediction residual corresponding to the processing object extended MB and outputting it to the local decoded image generation unit 110.

(Process S220) In the local decoded image generation unit 110, a local decoded image is generated based on the input prediction residual and the predicted image, and is output to the frame memory 101 for storage.

(Process S221) In the variable-length coding unit 303, the input transform coefficients, prediction parameters, and transform selection flag are variable-length coded using the input transform constraints, and are output to the outside as coded data.

Through the above-described process, the moving picture encoding device 30 can encode the input moving picture to generate encoded data and output it to the outside.

<Configuration of Moving Image Decoding Device 40>

Next, a description will be given of a moving picture decoding device 40 that decodes the coded data coded by the moving picture coding device 30 to generate a decoded moving picture.

16 is a block diagram showing the configuration of the image decoding device 40 . The moving picture decoding device 40 includes a frame memory 101 , a predicted image generator 103 , a prediction residual reconstruction unit 109 , a local decoded image generator 110 , a transform candidate derivation unit 302 , and a variable length code decoder 401 .

The variable-length code decoding unit 401 decodes and outputs prediction parameters, a transform selection flag, transform coefficients, and a transform candidate list derivation rule based on the input coded data and transform candidate list. Specifically, the transform candidate list derivation rule is first decoded and output. Next, the prediction parameters are decoded from the coded data and output. Next, the transform selection flag is decoded from the coded data using the transform candidate list and output. Finally, the transform coefficients are decoded from the coded data using the transform selection flag and output.

<Operation of Video Decoding Device 40>

Next, the operation of the moving picture decoding device 40 will be described.

(Process S230) The coded data input from the outside to the motion picture decoding device 40 is sequentially input to the variable length code decoding unit 401 in units of frames, and the subsequent processes S231 to S239 are sequentially performed on the coded data corresponding to each frame.

(Process S231) The variable-length code decoding unit 401 decodes the conversion candidate list derivation rule corresponding to the processing target frame from the input coded data, and outputs it to the conversion candidate derivation unit 302.

(Process S232) In the variable-length code decoding unit 401, the input frame-based coded data is divided into extended MB-based coded data, and the subsequent processes of S233 to S239 are sequentially performed on the coded data corresponding to each extended MB.

(Process S233) The variable-length code decoding unit 401 decodes prediction parameters from the coded data in the extended MB unit to be processed, and outputs the decoded prediction parameters to the transform candidate derivation unit 302.

(Process S234) The transform candidate derivation unit 302 derives a transform candidate list for each partition of the processing target extended MB based on the input transform candidate list derivation rule and prediction parameters, and outputs the list to the variable-length code decoding unit 401.

(Process S235) In the variable-length code decoding unit 401, the transform selection flag corresponding to the processing target MB is decoded based on the input coded data and transform constraints, and output to the prediction residual reconstruction unit 109.

(Process S236) In the variable length code decoding unit 202, based on the input coded data and the transform selection flag derived in (Process S235), the transform coefficient corresponding to the processing target extended MB is decoded and output to the prediction residual reconstruction unit 109.

(Process S237 ) The predicted image generator 103 generates a predicted image corresponding to the processing target extended MB based on the input prediction parameters and the local decoded image stored in the frame memory 101 , and outputs the predicted image to the local decoded image generator 110 .

(Process S238) In the prediction residual reconstruction unit 109, the inverse frequency transform corresponding to the frequency transform specified by the input transform selection flag is applied to the input transform coefficient, thereby reconstructing the prediction residual corresponding to the processing object extended MB and outputting it to the local decoded image generation unit 110.

(Process S239) The local decoded image generator 110 generates a local decoded image based on the input prediction residual and the prediction image, outputs it to the frame memory 101 for storage, and outputs it to the outside as a region on the decoded moving image corresponding to the processing target block.

As described above, the moving picture decoding device 40 can generate a decoded moving picture from the encoded data generated by the moving picture encoding device 11 .

Furthermore, typically, part or all of the moving picture encoding device and moving picture decoding device in the above-described embodiments can be implemented as an integrated circuit, i.e., an LSI (Large Scale Integration). Each functional block of the moving picture encoding device and moving picture decoding device can be individually integrated into a chip, or some or all of the functional blocks can be integrated into a chip. Furthermore, integrated circuit implementation is not limited to LSI; dedicated circuits or general-purpose processors can also be used. Furthermore, as semiconductor technology advances, if an integrated circuit technology that replaces LSI becomes available, integrated circuits based on that technology can be employed.

Explanation of symbols

10…Moving image encoding device, 11…Moving image encoding device, 20…Moving image decoding device, 21…Moving image decoding device, 30…Moving image encoding device, 40…Moving image decoding device, 101…Frame memory, 102…Prediction parameter determination unit, 103…Prediction image generation unit, 104…Transform constraint derivation unit, 105…Frequency transform determination unit, 106…Prediction residual generation unit, 107…Transform coefficient generation unit, 108…Variable length coding unit, 109…Prediction residual reconstruction unit, 110…Local decoded image generation unit, 111…Transform candidate derivation unit, 112…Frequency transform determination unit, 113…Variable length coding unit, 201…Variable length code decoding unit, 202…Variable length code decoding unit, 301…Candidate list derivation rule determination unit, 302…Transform candidate derivation unit, 302…Variable length coding unit, 401…Variable length code decoding unit.

Claims (2)

1. A motion picture decoding device, which decodes input encoded data in block units, characterized in that it comprises: A variable-length decoding unit decodes the partition structure of the block of the object being processed based on the input encoded data; A prediction image generation unit generates prediction images in units of partitions defined by the partitioning structure; and The transformation candidate derivation unit determines a list of applicable transformations, i.e., a transformation candidate list, based on the partition shape information. The partition shape information includes: the partition size of each partition, the characteristics of the partition size, and at least one of the hierarchical structure of the partition. The variable-length decoding unit decodes the transform selection flag based on the input encoded data and the transform candidate list, and decodes the transform coefficients of the block to be processed based on the transform selection flag, wherein the transform selection flag specifies the transform from the transform candidate list. The motion image decoding device also includes: The prediction residual reconstruction unit applies an inverse transform corresponding to the transform specified by the transform selection flag to the transform coefficients to reconstruct the prediction residuals; and The local decoded image generation unit outputs decoded image data corresponding to the block of the processing object based on the predicted image and the prediction residual; The partitioning structure is represented by a hierarchical structure, and each partition is defined as being contained in any hierarchical level according to its shape. 2. A motion picture encoding apparatus, which divides an input motion picture into blocks of a given size and encodes them in blocks, characterized in that it comprises: The predictor parameter determination unit, and the partitioning structure of its determination block; The prediction image generation unit generates prediction images in units of partitions defined by the partitioning structure; The transform coefficient generation unit applies the difference between the predicted image and the input motion image, i.e., the prediction residual, to any one of the transforms included in a given transform preset set. The transformation candidate derivation unit derives a list of applicable transformations, i.e., a transformation candidate list, based on the partition shape information. The partition shape information includes: the partition size of each partition, the characteristics of the partition size, and at least one of the hierarchical structure in the partition structure. A frequency transformation determination unit determines a transformation selection flag for each of the blocks, the transformation selection flag indicating the transformation to be applied to the prediction residual in the block from among the transformations included in the transformation candidate list; and A variable-length encoding unit performs variable-length encoding on the transform selection flag according to the transform candidate list; The partitioning structure is represented by a hierarchical structure, and it is stipulated that each partition is contained in any hierarchical level according to its shape. The transformation preset set includes frequency transformations, which are 4×4DCT, 8×8DCT, 16×16DCT, and 32×32DCT.