RU2783041C2 - Image decoding device, image decoding method, image coding device and image coding method - Google Patents

Abstract

FIELD: images encoding.

SUBSTANCE: invention relates to means for encoding an image. The image is recursively divided into rectangles of the given size to generate the target block. The block splitting step includes a quaternary splitting step in which a target block obtained by recursive splitting is divided in half in both horizontal and vertical directions to generate four blocks. The target block obtained by the recursive division is divided into two or three in the horizontal or vertical direction to generate two or three blocks. Splitting the target box in the horizontal direction is prohibited and splitting the target box in the vertical direction is allowed when splitting the target box in the horizontal direction results in the target box being beyond the right side of the image boundary, and disallowing splitting the target box in the vertical direction and allowing splitting the target box in the horizontal direction. when splitting the target box in the vertical direction results in the target box being behind the bottom side of the image boundary.

EFFECT: invention increases the efficiency of image encoding.

4 cl, 45 dwg

Description

The field of technology to which the invention belongs

The present invention relates to a technology for encoding and decoding an image in units of blocks obtained by division.

State of the art

Image encoding and decoding is performed on a block basis, wherein the image is divided into blocks, each of which contains a given number of pixels. In the present document, division into appropriate blocks of blocks can improve the efficiency of intra prediction, inter prediction, orthogonal transform, entropy coding, and the like, thereby improving coding efficiency.

Link List

Patent Literature

Patent Document 1. JP2015-526008 A

Non-Patent Literature

Non-Patent Literature 1. JVET, Universal Video Coding (Draft 2), July 2018

Disclosure of the essence of the invention

Encoding efficiency is reduced when a block is divided into blocks of an inappropriate size and shape. In particular, at the end of a frame, a block containing pixels located outside an image boundary is inappropriately sized and shaped, and the encoding efficiency decreases accordingly.

The present invention has been proposed in view of such circumstances, and therefore, an object of the present invention is to provide a technology for improving coding efficiency by dividing an image into blocks for encoding and decoding images.

According to one aspect of the present invention, an apparatus for decoding an image is provided for solving the problems described above. This apparatus is an image decoding apparatus capable of decoding images in blocks of blocks obtained by division, an image decoding apparatus including a decoder (201) adapted to decode block division information in the target block, and a delimiter (202 ) block, configured to recursively divide an image into rectangles of a predetermined size based on block division information to generate a target block. The block delimiter includes a four-delimiter configured to divide a target block obtained by recursively halving in both a horizontal direction and a vertical direction to generate four blocks, and a binary/ternary delimiter configured to divide a target block obtained recursively splitting into two or three in the horizontal or vertical direction to generate two or three blocks. The binary/ternary delimiter prohibits splitting the target box in the horizontal direction when splitting the target box in the horizontal direction causes the split target box to be beyond the right side of the image boundary, and disables splitting the target box in the vertical direction when splitting the target box in the vertical direction prompts the target block resulting from the split is beyond the bottom side of the image boundary.

According to another aspect of the present invention, an apparatus for decoding an image is provided. This apparatus is an image decoding apparatus configured to decode an image in blocks of blocks obtained by splitting, an image decoding apparatus including a decoder (201) configured to decode block split information in a target block, and a block separator, configured to recursively divide an image into rectangles of a predetermined size based on the block division information to generate a target block. The block splitter (202) includes a four-part splitter configured to split a target block obtained by recursively splitting in half in both a horizontal direction and a vertical direction to generate four blocks, and a binary/ternary splitter configured to split a target block , obtained by recursively splitting into two or three in the horizontal or vertical direction to generate two or three blocks. When splitting the target block in either direction causes the split target box to be outside the image boundary, and the splitting depth of the block reaches the specified limit depth, or the number or proportion of pixels contained in the split obtained box located outside the image boundary is greater than the specified values, the binary/ternary delimiter prevents the target block from being split by direction.

In accordance with yet another aspect of the present invention, an apparatus for decoding images is provided. This apparatus is an image decoding apparatus capable of decoding images in blocks of blocks obtained by division, an image decoding apparatus including a decoder (201) adapted to decode block division information in the target block, and a delimiter (202 ) block, configured to recursively divide an image into rectangles of a predetermined size based on block division information to generate a target block. The block delimiter includes a four-delimiter configured to divide a target block obtained by a recursive halving in both a horizontal direction and a vertical direction to generate four blocks, and a binary/ternary separator configured to divide a target block obtained by a recursive splitting into two or three in horizontal or vertical direction to generate two or three blocks. The binary/ternary delimiter determines the direction in which the target block is divided so that when the target block is divided, the target block obtained by splitting has the largest number of pixels located outside the image boundary.

In accordance with yet another aspect of the present invention, a method for decoding an image is provided. This method is an image decoding method for decoding an image in blocks of blocks obtained by splitting, the image decoding method includes a step of decoding block split information in a target block, and a step of splitting blocks of recursively dividing an image into rectangles of a predetermined size based on the block split information for target block generation. The block splitting step includes a splitting step into four of a target block obtained by recursively splitting in half in both horizontal and vertical directions to generate four blocks, and a binary/ternary splitting step for splitting the target block obtained by recursively splitting into two or three. in the horizontal or vertical direction to generate two or three blocks. The binary/triple division step prohibits division of the target block in the horizontal direction when division of the target block in the horizontal direction causes the target block obtained by division to be beyond the right side of the image boundary, and inhibits division of the target block in the vertical direction when division of the target block in the vertical direction causes the target block resulting from the split to be behind the bottom side of the image boundary.

It should be noted that any combination of the above-described components, or an entity that results from substituting expressions of the present invention in a method, apparatus, system, recording medium, computer program, or the like, may also be considered as an aspect of the present invention.

The present invention makes it possible to separate blocks suitable for encoding and decoding pictures, and thus makes it possible to improve the coding efficiency.

Brief description of the drawings

Fig. 1 is a block diagram of an image encoding apparatus according to the first embodiment.

Fig. 2 is a block diagram of an apparatus for decoding an image according to the first embodiment.

Fig. 3 is a flowchart showing the division into blocks of the tree and the division of the interior of each block of the tree.

Fig. 4 is a diagram showing the division of an input image into tree blocks.

Fig. 5 is a diagram for describing z-scan.

Fig. 6 is a diagram for describing the division of a tree block.

Fig. 7 is a flowchart showing a process to be performed for each block obtained by dividing the tree block into four.

Fig. 8 is a flowchart showing a process to be performed for each block obtained by dividing a tree block into two or three.

Fig. 9 is a diagram showing a relationship between tree blocks and an image boundary.

Fig. 10 is a diagram showing a relationship between an image border and pixels.

Fig. 11 is a flowchart showing block division according to the first embodiment.

Fig. 12 is a diagram showing block division according to the first embodiment.

Fig. 13 is a diagram showing a syntax for block division according to the first embodiment.

Fig. 14 is a flowchart showing block division according to the second embodiment.

Fig. 15 is a diagram showing block division according to the second embodiment.

Fig. 16 is a flowchart showing block divisions according to the third embodiment.

Fig. 17 is a diagram showing block division according to the third embodiment.

Fig. 18 is a flowchart showing block divisions according to the third embodiment.

Fig. 19 is a diagram showing block division according to the fourth embodiment.

Fig. 20 is a flowchart showing block divisions according to the fourth embodiment.

Fig. 21 is a diagram showing block division according to the fifth embodiment.

Fig. 22 is a diagram for describing an example of a hardware structure of an encoding and decoding device according to the first embodiment.

Implementation of the invention

According to embodiments of the present invention, a method for encoding and decoding an image in blocks of blocks obtained by division is provided.

First Embodiment

Description will be given below of the image encoding apparatus 100 and the image decoding apparatus 200 according to the first embodiment of the present invention. According to the first embodiment, division of blocks is limited in case of division of a block into two or three.

Fig. 1 is a block diagram of an image encoding apparatus 100 according to the first embodiment. In FIG. 1 shows only the data stream related to the image signal, and does not show the data stream related to additional information such as motion vector and prediction mode other than the image signal. The image encoding apparatus 100 is supplied with an image signal for at least one frame.

The block divider 101 divides the image into target encoding blocks, each of which undergoes an encoding process, and supplies the image signal in the target encoding blocks to the residual signal generator 103 . In addition, the block divider 101 supplies the image signal of the encoding target blocks to the prediction image generator 102 for judging the matching degree of the prediction image.

The block divider 101 recursively divides the image into rectangles of a given size to generate target encoding blocks. The block delimiter 101 includes a four-delimiter that divides a target block obtained by recursive division into four to generate four blocks, and a binary/ternary delimiter that divides a target block obtained by recursive division into two or three to generate two or three blocks. A detailed description of the operation of the block divider 101 will be given below.

The prediction image generator 102 is supplied with an image signal of an encoding target block from the block separator 101 and a decoded image signal from the decoded image memory 108 . The prediction image generator 102 uses the supplied signals to perform inter-frame prediction or inter-frame prediction based on the prediction mode, and generates a prediction image signal. In intra prediction, from the decoded picture memory 108, the prediction picture generator 102 is supplied with an image signal of an encoded block adjacent to an encoding target block in the same picture (encoding picture). Then, the prediction image generator 102 uses this image signal and the image signal of the coding target block provided by the block separator 101 to generate a prediction image signal. In inter-prediction, from the decoded picture memory 108, the prediction picture generator 102 is supplied with an encoded picture signal (reference picture) that is provided before or after the picture encoding in time sequence. Then, the prediction image generator 102 uses this image signal and the target coding block provided by the block separator 101 to estimate the degree of matching by block matching or the like. and obtaining a motion vector representing the amount of motion. The prediction image generator 102 performs motion compensation based on this motion vector and the reference image to generate a prediction image signal. The prediction image generator 102 supplies the prediction image signal thus generated to the residual signal generator 103 .

The residual signal generator 103 generates a residual signal by subtracting the encoding target image signal and the prediction signal generated by the prediction image generator 102, and supplies the residual signal to the orthogonal transform and quantization part 104 .

The orthogonal transform and quantization part 104 orthogonally transforms and quantizes the residual signal output from the residual signal generator 103 . The orthogonal transform and quantization part 104 provides the orthogonally transformed and quantized residual signal to the encoder 105 and the inverse quantization and inverse orthogonal transform part 106.

The encoder 105 generates a bit stream corresponding to the orthogonally transformed and quantized residual signal provided from the orthogonal transform and quantization part 104 . The encoder 105 further generates a bitstream corresponding to side information such as motion vector, prediction mode, and block separation information provided by each component. Then, the encoder 105 outputs the bit streams from the device 100 for encoding the image.

The inverse quantization and inverse orthogonal transform part 106 performs inverse quantization and inverse orthogonal transform of the orthogonally transformed and quantized residual signal provided from the orthogonal transform and quantization part 104 to obtain a residual signal. The inverse quantization and inverse orthogonal transform part 106 provides the residual signal to the overlay part 107 of the decoded image signal.

The decoded image signal overlay part 107 superimposes the prediction image signal generated by the prediction image generator 102 and the residual signal obtained by the inverse quantization and inverse orthogonal transform part 106 to generate a decoded image, and stores the decoded image in the decoded image memory 108. It should be noted that the decoded image signal overlay part 107, before storing the decoded image in the decoded image memory 108, may perform a decoded image filtering process to reduce block distortion or the like caused by encoding.

Fig. 2 is a block diagram of an apparatus 200 for decoding an image according to the first embodiment. In FIG. 2 only shows the data stream related to the image signal, and does not show the data stream related to additional information such as motion vector and prediction mode other than the image signal. The image decoding apparatus 200 receives a bit stream.

The decoder 201 decodes the provided bitstream and supplies the orthogonally transformed and quantized residual signal to the block separator 202 . Moreover, the decoder 201 provides side information such as a motion vector, a prediction mode, and block separation information for each component to use the side information for a process related to the side information.

The block separator 202 determines the shape of the decoding target block based on the decoded block separation information, and provides the orthogonally transformed and quantized residual signal of the determined decoding target block to the inverse quantization and inverse orthogonal transform portion 203 .

The block divider 202 recursively divides an image into rectangles of a given size based on decoded block separation information to generate a decoding target block. The block delimiter 202 includes a four-delimiter that divides a recursively split target block into four to generate four blocks, and a binary/ternary delimiter that splits a recursively split target block into two or three blocks to generate two or three blocks. three blocks. A detailed description of the operation of the block divider 202 will be given below.

The inverse quantization and inverse orthogonal transform part 203 performs inverse quantization and inverse orthogonal transformation of the provided orthogonally transformed and quantized residual signal to obtain a residual signal. The residual signal is supplied to the overlay portion 205 of the decoded image signals.

The prediction image generator 204 generates a prediction image signal from the decoded image signal provided from the decoded image memory 206, and provides the prediction image signal to the decoded image signal overlay portion 205 .

The decoded image signal overlay part 205 superimposes the prediction image signal generated by the prediction image generator 204 and the residual signal obtained by the inverse quantization and inverse orthogonal transform section 203 to generate a decoded image signal. In addition, the decoded image signal overlay part 205 stores the decoded image signal in the decoded image memory 206 . It should be noted that the decoded image signal overlay portion 205 may perform a decoded image filtering process to reduce block distortion or the like caused by encoding before storing the decoded image in the decoded image memory 206 . Then, the decoded image signal overlay portion 205 outputs the decoded image from the image decoding apparatus 200 .

Next, with reference to FIG. 3, a description will be given of the operation of the block divider 101 in the image encoding apparatus 100 . Fig. 3 shows an operation in which the block divider 101 divides an image into tree blocks and sections or each tree block into blocks.

First, the input image is divided into tree blocks of a given size (S1000). Let's say the tree block is 128×128 pixels. It should be noted that the tree block is not limited to this size and can be any size and any aspect ratio as long as the tree block is rectangular. Further, between the encoding device and the decoding device, the tree block size may be predetermined. Moreover, a configuration may be used in which the encoding device determines the tree block size and records the size in the bitstream, and the decoding device uses the tree block size recorded in the bitstream. In FIG. 4 shows how the input image is divided into tree blocks. Tree blocks are encoded in raster scan order from left to right and top to bottom.

The interior of each tree block is further divided into rectangular blocks. The interior of the tree block is encoded in the z-scan order shown in FIG. 5. The z-scan order follows the order of top left, top right, bottom left, and bottom right. The inner tree block can be divided into four, two or three.

As shown in FIG. 6A, block squaring is performed by splitting the block in half to generate four blocks in both the horizontal direction and the vertical direction.

Dividing a block into two or three is done by splitting the block in the horizontal or vertical direction. To split a block into two in the horizontal direction, the block is divided in half as shown in FIG. 6B to form two blocks. Additionally, to divide the block into three in the horizontal direction, the block is divided in a ratio of 1:2:1 as shown in FIG. 6C to form three blocks. On the other hand, in order to split a block into two in the vertical direction, the block is divided in half as shown in FIG. 6D to form two blocks. Moreover, in order to divide a block into three in the vertical direction, the block is divided in a ratio of 1:2:1 as shown in FIG. 6E to form three blocks.

With reference to FIG. 3, a description will be given of the operation of the block divider 101. First of all, it is determined whether the inside of the tree block is to be divided in half in both the horizontal direction and the vertical direction to form four blocks (S1001).

To determine the optimal case from a set of conditions, a technique called speed and distortion optimization (R-D optimization) is currently used, which includes determining whether the block should be divided into squares. In R-D optimization, the encoding cost is calculated from the encoding amount and encoding distortion. Then, the corresponding coding costs under a plurality of conditions are calculated, and the case where the coding costs become the smallest is selected. That is, it is determined whether to divide the block into squares by calculating the encoding cost when the block is divided by four, and the encoding cost when the block is not divided by four, and selecting the case with the lowest encoding cost. To determine the optimal case from a set of conditions, a method other than R-D optimization may be used.

When determining that the inside of the tree block is divided into four (S1001: YES), the inside of the tree block is divided into four (S1002). The process of further splitting the block into four will be described later (FIG. 7).

When determining that the inside of the tree block is not divided into four (S1001: NO), a determination is made whether the inside of the tree block is divided into two or three (S1003).

When determining that the inside of the tree block is divided into two or three (S1003: YES), a determination is made as to whether the division direction is the vertical direction (S1004).

When determining that the dividing direction is the vertical direction (S1004: YES), a determination is made as to whether to divide the inside of the tree block into two (S1005).

When determining that the inside of the tree block is halved (S1005: YES), the inside of the tree block is halved in the vertical direction (S1006). On the other hand, when it is determined that the inside of the tree block is divided into three (S1005: NO), the inside of the tree block is divided into three in the vertical direction (S1007). Next, a process for further dividing a block divided into two or three in the vertical direction will be described (FIG. 8).

When determining that the division direction is the horizontal direction (S1004: NO), a determination is made as to whether to divide the inside of the tree block into two (S1008).

When determining that the inside of the tree block is halved (S1008: YES), the inside of the tree block is halved in the horizontal direction (S1009). On the other hand, when it is determined that the inside of the tree block is divided into three (S1008: NO), the inside of the tree block is divided into three in the horizontal direction (S1010). Below will be a description of the process of additional division of the block, divided into two or three horizontally (Fig. 8).

When determining that the inside of the tree block is not divided into two or three (S1003: NO), the block splitting process ends without dividing the inside of the tree block (S1011).

Next, with reference to the flowchart of the algorithm in FIG. 7, a description will be given of a process to be performed for each of the four blocks obtained by dividing the tree block in half in both the horizontal direction and the vertical direction.

First of all, it is determined whether to further divide the inside of the block in half in both the horizontal direction and the vertical direction to obtain four blocks (S1101).

When determining that the inside of the block is further divided into four (S1101: YES), the inside of the block is further divided into four (S1102).

When determining that the inside of the block is not further divided into four (S1101: NO), a determination is made whether to divide the inside of the block into two or three (S1103).

When determining that the inside of the block is divided into two or three (S1103: YES), a determination is made as to whether the dividing direction is the vertical direction (S1104).

When determining that the dividing direction is the vertical direction (S1104: YES), a determination is made as to whether to divide the inside of the block into two (S1105).

When determining that the inside of the block is halved (S1105: YES), the inside of the block is halved in the vertical direction (S1106). On the other hand, when it is determined that the inside of the block is divided into three (S1105: NO), the inside of the block is divided into three in the vertical direction (S1107).

When determining that the dividing direction is the horizontal direction (S1104: NO), a determination is made as to whether to divide the inside of the block into two (S1108).

When determining that the inside of the block is halved (S1108: YES), the inside of the block is halved in the horizontal direction (S1109). On the other hand, when it is determined that the inside of the block is divided into three (S1108: NO), the inside of the block is divided into three in the horizontal direction (S1110).

When determining that the inside of the block is not divided into two or three (S1103: NO), the block dividing process is completed without further dividing the inside of the block (S1111).

The process shown in the flowchart of FIG. 7 is recursively executed for each of the four blocks obtained by splitting. The interior of a block divided by four is encoded in z-scan order.

Next, with reference to the flowchart of the algorithm in FIG. 8, a description will be given of a process to be performed for each of the blocks obtained by dividing a tree block into two or three in the vertical direction.

When the tree block is divided into two or three in the vertical direction, it is determined whether to further divide the inside of each of the blocks obtained by dividing into two or three (S1201).

When determining that the inside of the block is divided into two or three (S1201: YES), a determination is made as to whether the dividing direction is the vertical direction (S1202).

When determining that the dividing direction is the vertical direction (S1202: YES), a determination is made as to whether to divide the inside of the block into two (S1203).

When determining that the inside of the block is halved (S1203: YES), the inside of the block is halved in the vertical direction (S1204). On the other hand, when it is determined that the inside of the block is divided into three (S1203: NO), the inside of the block is divided into three in the vertical direction (S1205).

When determining that the dividing direction is the horizontal direction (S1202: NO), a determination is made as to whether to divide the inside of the block into two (S1206).

When determining that the inside of the block is halved (S1206: YES), the inside of the block is halved in the horizontal direction (S1207). On the other hand, when it is determined that the inside of the block is divided into three (S1206: NO), the inside of the block is divided into three in the horizontal direction (S1208).

When determining that the inside of the block is not divided into two or three (S1201: NO), the block division process is completed without further dividing the inside of the block (S1209).

The process shown in the flowchart of FIG. 8 is recursively executed for each of the blocks obtained by splitting into two or three in the vertical direction. The interior of a block divided into two or three is encoded in order from left to right.

Similarly, the process shown in the flowchart of FIG. 8 is recursively executed for each of the blocks obtained by splitting into two or three in the horizontal direction. The interior of a block divided into two or three is encoded in order from top to bottom.

It should be noted that a process for further splitting blocks obtained by splitting a tree block has been described, but the parent block need not be a tree block. For example, when a tree block (128 × 128 pixels) is divided into four and the resulting four blocks (64 × 64 pixels) are further divided, the above process is also applied to the division of blocks obtained by further division.

For recursive block splitting, the number of split times can be defined so that it is limited. In addition, the number of split times may be predetermined between the encoding device and the decoding device. In addition, a configuration may be used in which the encoder determines and records the number of split times in the bitstream, and the decoder uses the split times recorded in the bitstream.

Description will be given below of block division at the end of a frame. Fig. 9 shows the relationship with the border of the image when the image is divided into blocks of the tree. As shown in FIG. 9, the image size is not necessarily equal to an integer multiple of the tree block size, so that a tree block located at the end of a frame may contain an intra-frame and an extra-frame portion of the frame relative to the image boundary. Tree blocks 1001, 1002, 1003 are shown as tree blocks located at the end of a frame. In this case, as shown in FIG. 10, the out-of-frame part located outside the image boundary is treated as the outermost pixels in the frame. Pixels 1011, 1012, 1013 are shown as the outermost pixels in the frame.

Pixel 1011 is located in tree block 1001 and in the upper right corner of the frame. A pixel located on the right side of pixel 1011, that is, an out-of-frame pixel located outside the image boundary, is treated as pixel 1011.

Pixel 1012 is located in tree block 1002 and in the lower left corner of the frame. A pixel located on the underside of pixel 1012, that is, an out-of-frame pixel located outside the image boundary, is treated as pixel 1012.

Pixel 1013 is located in tree block 1003 and in the lower right corner of the frame. Pixels located on the right side, bottom side, and bottom right side of pixel 1013, i.e., out-of-frame pixels located outside the image boundary, are treated in the same way as pixel 1013.

Then, when a block is divided into two or three, the division of the blocks is limited. This allows the block located at the end of the frame to be divided into blocks of a suitable shape, and thus improve the coding efficiency.

Block splitting restrictions apply to splitting a block located at the end of a frame into two or three. That is, the halving or tri-diving process (S1004 to S1010) shown in FIG. 3 is replaced by the process described below. Moreover, the halving or tri-diving process (S1104 to S1110) shown in FIG. 7 is replaced by the process described below. Further, the halving or tri-diving process (S1202 to S1208) shown in FIG. 8 is replaced by the process described below.

With reference to FIG. 11, a description will be given of block division limitations. First, for all block division patterns, a determination is made as to whether to limit block division (S1301). All block splitting patterns include four patterns: a pattern in which a block is divided into two in a horizontal direction; a pattern in which a block is split in two in the vertical direction; a pattern in which the block is divided into three horizontally; and a pattern in which the block is divided into three in the vertical direction. In addition, it is determined whether or not to limit the division of blocks based on whether pixels located outside the image boundary are divided. For example, when a block is divided into two in the horizontal direction, and pixels located outside the image boundary are divided accordingly, the division of the block into two in the horizontal direction is limited.

Here, limiting block splitting in the horizontal direction corresponds to prohibiting block splitting in the horizontal direction. In addition, limiting block division in the vertical direction corresponds to prohibiting block division in the vertical direction. In the same way, the restriction of splitting a block into two corresponds to the prohibition of splitting a block into two. Additionally, the restriction of splitting a block by three corresponds to prohibiting splitting a block by three.

It is then determined whether or not to limit the block division for all block division patterns (S1302). When block division is restricted for all patterns (S1302: YES), the block is not divided (S1314). On the other hand, when the block separation is not limited for all patterns (S1302: NO), a determination is made as to whether to limit the block separation in the horizontal direction (S1303).

When the division of blocks in the horizontal direction is limited (S1303: YES), proceed to the next process (S1306). On the other hand, when the block division in the horizontal direction is not limited (S1303: NO), a determination is made whether to restrict the block division in the vertical direction (S1304).

When the separation of blocks in the vertical direction is limited (S1304: YES), proceed to the next process (S1310). On the other hand, when the division of the block in the vertical direction is not limited (S1304: NO), a determination is made whether to divide the block in the vertical direction (S1305).

When it is determined that the block division direction is the vertical direction (S1305: YES), a determination is made as to whether the block division should be limited to three (S1306). On the other hand, when it is determined that the block dividing direction is the horizontal direction (S1305: NO), proceed to the next process (S1310).

When the block division into three is limited (S1306: YES), the block is divided into two in the vertical direction (S1308). On the other hand, when dividing a block into three is not limited (S1306: NO), a determination is made whether to divide a block into two (S1307).

When it is determined that the block is divided into two (S1307: YES), the block is divided into two in the vertical direction (S1308). On the other hand, when it is determined that the block is divided into three (S1307: NO), the block is divided into three in the vertical direction (S1309).

When the division in the vertical direction is limited (S1304: YES) and when it is determined that the division direction of the block is the horizontal direction (S1305: NO), a determination is made as to whether the division of blocks should be limited to three (S1310).

When the division of the block into three is limited (S1310: YES), the block is divided into two in the horizontal direction (S1312). On the other hand, when dividing a block into three is not limited (S1310: NO), a determination is made whether to divide a block into two (S1311).

When it is determined that the block is halved (S1311: YES), the block is halved in the horizontal direction (S1312). On the other hand, when it is determined that the block is divided into three (S1311: NO), the block is divided into three in the horizontal direction (S1313).

That is, when pixels located outside the image boundary are separated as a result of block separation, block separation in the corresponding direction is restricted.

A specific example will be described below. The tree block located at the bottom of the frame is not divided into four (S1001: NO), but the inside of the tree block is divided into two or three (S1003: YES). In FIG. 12A shows how the tree block contains in-frame and out-of-frame portions across an image boundary. Here, it is determined whether or not to restrict the block division for all tree block division patterns (S1301).

Fig. 12A-12D show how the tree block is divided according to all templates. When a block is split in two in the vertical direction, as shown in FIG. 12A, pixels located outside the image boundary are separated so that this block separation is limited. Similarly, as shown in FIG. 12B, when a block is divided into three in the vertical direction, pixels located outside the image boundary are separated so that this separation of the blocks is limited. On the other hand, when a block is halved in the horizontal direction as shown in FIG. 12C, pixels outside the image boundary are not separated, so this block division is not limited. Similarly, when a block is divided into three in the horizontal direction, as shown in FIG. 12D, pixels outside the image boundary are not separated, so this block division is not limited.

Therefore, block division is not limited for all block division patterns (S1302: NO). In addition, block separation in the horizontal direction is not limited (S1303: NO), and block separation in the vertical direction is limited (S1304: YES). Then division of the block into three is not limited (S1310: NO). Therefore, a determination is made whether to divide the block into two (S1311). When it is determined that the block is divided into two (S1311: YES), the block is divided into two in the horizontal direction (S1312).

Such block separation restrictions allow the block to have a suitable shape. This is because in a block containing out-of-frame pixels, the pixel values of the out-of-frame portion are uniform. Therefore, changes in pixel values of the intra-frame portion in the block are small compared to a block containing no pixels outside the frame. This reduces the need to encode small pixel changes. Therefore, it is possible to reduce the amount of coding and improve the efficiency of coding by combining as many out-of-frame pixels as possible into a block.

These block separation restrictions also apply to the right end of the frame. Fig. 12E-12H show how the tree block is divided according to all patterns. Here, when a block is halved in the horizontal direction as shown in FIG. 12E, pixels located outside the image boundary are separated. In addition, when the block is divided into three in the horizontal direction, as shown in FIG. 12F, pixels outside the image boundary are separated. Therefore, this division of blocks is limited. Such blocking restrictions improve coding efficiency.

Below, a description will be given of the operation of the block divider 202 of the device 200 for decoding images. The block divider 202 divides the block using the same processing procedure as the block divider 101 of the image encoding apparatus 100 described above. The block divider 101 selects a block separation pattern and outputs the thus selected block separation information. On the other hand, the block separator 202 divides the block based on the block separation information obtained by decoding the bitstream. The block division restrictions are the same as those of the image encoding apparatus 100 described above.

In FIG. 13 shows a syntax (bitstream syntax rule) for block separation according to the first embodiment. In FIG. 13 QT () represents the syntax for the process of dividing a block into four, MTT () represents the syntax for the process of dividing a block into two or three. The image encoding apparatus 100 performs encoding according to this syntax, and the image decoding apparatus 200 performs decoding according to this syntax.

First, whether the block should be divided into four is represented by QTflag. QTflag is set to 1 to enable split by four, and QTflag is set to 0 to disable split by four. If split by four is initiated (QTflag = 1), when each of the four blocks resulting from the split can be further split by four (QTvalid = 1), the split by four process is performed recursively. If split by four is disabled (QTflag = 0), split by two or three is displayed using the MTTflag. If split-by-two or split-by-two is initiated (MTTflag = 1), then whether split in the vertical direction should be performed is displayed by vertical_flag, and split by two is represented by BTflag. vertical_flag is set to 1 to enable splitting in the vertical direction, and vertical_flag is set to 0 to enable splitting in the horizontal direction. In addition, BTflag is set to 1 to enable split-by-two, and BTflag is set to 0 to enable split-by-three. When each of the two or three blocks resulting from the split can be further split into two or three (MTTvalid = 1), the split into two or three process is performed recursively.

Below, a description will be given of the QTvalid variable representing whether each of the four blocks obtained by splitting can be further split into four. QTvalid is defined for each of the four blocks resulting from the split. When the four split blocks do not contain intra-frame pixels, QTvalid is set to 0. Otherwise, QTvalid is set to 1.

Next, a description will be given of the MTTvalid variable representing whether each of the two or three blocks obtained by splitting can be further split into two or three. MTTvalid is determined for each of the two or three blocks resulting from the split. When two or three split blocks do not contain intra-frame pixels, MTTvalid is set to 0. Otherwise, MTTvalid is set to 1.

According to the present embodiment, the block separation direction is limited, which eliminates the need for a vertical_flag. Therefore, the vertical_flag in FIG. 13 may be omitted.

Such block separation restrictions make it possible to divide a block located at the end of a frame into blocks of a suitable shape and thus improve coding efficiency. This further allows separation of blocks suitable for image encoding and decoding.

Second Embodiment

According to the second embodiment of the present invention, a description will now be made of an image encoding apparatus and an image decoding apparatus. According to the second embodiment, the block separation is limited when the block separation depth reaches the limit depth. Other configurations are the configurations according to the first embodiment; therefore, description of other configurations is not given.

Below, a description will be given of the block separation depth. According to the first embodiment, a process of dividing a block into two or three and then recursively dividing each of the two or three blocks obtained by dividing into two or three has been described. For this process, the first splitting process into two or three is defined as depth 0. In addition, the second splitting process of each of the two or three blocks obtained by the first splitting into two or three blocks is defined as depth 1, the third splitting process of each of the two or three blocks obtained by the second splitting process into two or three is defined as depth 2, and the depth of each subsequent process is defined in the same way. Moreover, the depth to be used in limiting block separation is predetermined as the limit depth.

Block splitting restrictions apply to splitting a block into two or three located at the end of a frame. That is, the halving or tri-diving process (S1004 to S1010) shown in FIG. 3 is replaced by the process described below. Moreover, the halving or tri-diving process (S1104 to S1110) shown in FIG. 7 is replaced by the process described below. Further, the halving or tri-diving process (S1202 to S1208) shown in FIG. 8 is replaced by the process described below.

With reference to FIG. 14, a description will be given of the limitations of block division. First, when a block is divided into two or three, a determination is made whether the separation depth of the blocks has reached the limit depth. (S1401).

When the depth has not reached the limit depth (S1401: NO), it is determined not to limit the block separation (S1402). On the other hand, when the depth reaches the limit depth (S1401: YES), it is determined whether or not to limit the block division for all block division patterns (S1301). S1301 is the same as according to the first embodiment; therefore, S1301 will not be described.

It is then determined whether or not to limit the block division for all block division patterns (S1302). S1302 and subsequent processes are the same as in the first embodiment; therefore, the description of S1302 and subsequent processes is omitted.

That is, when pixels located outside the image boundary are separated as a result of block separation and the block separation depth has reached the limit depth, the block separation is limited.

A specific example will be described below. The tree block located at the bottom of the frame is not divided into four parts (S1001: NO), but the inside of the tree block is divided into two or three (S1003: YES). In addition, the limit depth is set to 1. In FIG. 12A shows how the tree block contains in-frame and out-of-frame portions across an image boundary. When this tree block is divided into two or three, the pixels located outside the image boundary are separated as a result of splitting in the vertical direction. Note that the depth is 0 and has not reached the limit depth 1 (S1401: NO). Therefore, it is determined not to restrict block division (S1402). Specifically, block separation is limited for all patterns (S1302: NO), block separation in the horizontal direction is not limited (S1303: NO), and block separation in the vertical direction is not limited (S1304: NO). Then, it is determined whether or not to divide the block in the vertical direction (S1305). When the block division in the vertical direction is determined (S1305: YES), the division of the block into three is not limited (S1306: NO), so it is determined whether to divide the block into two (S1307). When a block halving is determined (S1307: YES), the block is halved in the vertical direction (S1308). The above is shown in Fig. 12A.

Subsequently, from the blocks obtained by division in the vertical direction, the left block is divided into two or three. Here, the depth is 1 and has reached the limit depth 1 (S1401: YES). Therefore, for all block division patterns, a determination is made as to whether the block division should be limited (S1301).

Fig. 15A-15D show how the block is divided according to all patterns. When a block is split in two in the vertical direction, as shown in FIG. 15A, pixels located outside the image boundary are separated, so that this block division is limited. Similarly, as shown in FIG. 15B, when a block is divided into three in the vertical direction, pixels located outside the image boundary are divided, so that this division of the block is limited. On the other hand, when a block is halved in the horizontal direction as shown in FIG. 15C, pixels located outside the image boundary are not separated, so this block division is not limited. Similarly, when a block is divided into three in the horizontal direction, as shown in FIG. 15D, pixels outside the image boundary are not separated, so this block division is not limited.

Therefore, block division is not limited for all block division patterns (S1302: NO). Further, block separation in the horizontal direction is not limited (S1303: NO) and block separation in the vertical direction is limited (S1304: YES). Then division of the block into three is not limited (S1310: NO). Therefore, a determination is made whether to divide the block into two (S1311). When it is determined that the block is divided into two (S1311: YES), the block is divided into two in the horizontal direction (S1312).

Such block separation restrictions allow the block to have an appropriate size and shape. This is because in a block containing out-of-frame pixels, the pixel values of the out-of-frame portion are uniform. Therefore, changes in pixel values of the intra-frame portion in the block are small compared to a block containing no pixels outside the frame. This reduces the need to encode small pixel changes. Therefore, it is possible to reduce the amount of coding and improve the efficiency of coding by combining as many out-of-frame pixels as possible into a block.

Block separation restrictions also apply to the right end of the frame. The depth when a tree block is split into two or three is 0 and has not reached the depth limit of 1, so the block split is not limited and the block is split into two or three. When a block obtained by division is further divided, the depth is 1 and reaches the limit depth of 1, so that a determination is made whether to limit the division of the block. Then, when the block is divided into two in the horizontal direction or when the block is divided into three in the horizontal direction, the pixels outside the image boundary are divided accordingly. Therefore, this division of blocks is limited. Such block division restrictions improve coding efficiency.

According to the present embodiment, the division depth of the blocks is determined to be divided into two or three. Depth can also be specified to be divided by four. In addition, according to the present embodiment, the block separation is limited based on the block separation depth. Alternatively, the division of the block is limited based on the number or proportion of pixels contained in the block and located outside the image boundary. That is, when these values are greater than the predetermined values, block separation is limited. Additionally, these values may be different for each block separation depth. This allows a block with a small number or fraction of out-of-frame pixels to be split, and prevents a block with a large number or fraction of out-of-frame pixels from being split. The bitstream encoding device may use a configuration in which values relating to block division restrictions such as a limiting block division depth and the number or proportion of pixels contained in the block located outside the picture boundary are recorded, and the decoding device uses the values recorded in the bitstream.

According to the first embodiment, block separation is limited regardless of the block separation depth. On the other hand, according to the present embodiment, the block separation is limited based on the block separation depth. This allows a block with a small pixel ratio outside the frame to be split and prevents a block with a large pixel ratio out of the frame from being split. This allows a block located at the end of a frame to be divided into blocks of suitable size and shape, and thus improves coding efficiency. This further allows separation of blocks suitable for image encoding and decoding.

Third Embodiment

A description will be given of an image encoding apparatus and an image decoding apparatus according to a third embodiment of the present invention. According to the third embodiment, block separation is controlled based on the number of pixels located outside the image boundary. Other configurations are the same as those of the first embodiment; therefore, description of other configurations is not given.

The block division control is applied to the division of a block located at the end of a frame into two or three. That is, the halving or tri-diving process (S1004 to S1010) shown in FIG. 3 is replaced by the process described below. Moreover, the halving or tri-diving process (S1104 to S1110) shown in FIG. 7 is replaced by the process described below. Further, the halving or tri-diving process (S1202 to S1208) shown in FIG. 8 is replaced by the process described below.

With reference to FIG. 16, a description will be given of block division control. First, for all block separation patterns, the number of pixels outside the image boundary is counted (S1601). All block splitting patterns include four patterns: a pattern in which a block is divided into two in a horizontal direction; a pattern in which a block is split in two in the vertical direction; a pattern in which the block is divided into three horizontally; and a pattern in which the block is divided into three in the vertical direction.

Then, for both the pattern in which the block is divided into two and the pattern in which the block is divided into three, the division direction in which the number of pixels outside the image boundary becomes the largest is determined (S1602).

Then, determination of the division of the block into two is performed (S1603).

When it is determined to perform split-by-two (S1603: YES), split-by-two is performed in the split-by-two direction determined in S1602 (S1604). On the other hand, when it is determined to perform the division by three (S1603: NO), the division by three is performed in the division direction determined in S1602 (S1605).

That is, the division direction of the block is controlled to cause the block to contain the largest number of pixels located outside the image boundary.

A specific example will be described below. Suppose the image is 1920×1080 pixels and the tree block is 128×128 pixels. In addition, the tree block is not divided into four (S1101: NO) and the inside of the block is divided into two or three (S1103: YES). Then, as shown in FIG. 17A, at the lower end of the frame, 72 pixels are located outside the image boundary in the vertical direction. Here, when a tree block is divided according to all patterns, the number of pixels outside the image boundary in each block is counted (S1601).

Fig. 17A-17D show how the tree block is divided according to all patterns. When a block is divided into two in the vertical direction, as shown in FIG. 17A, the left side (500) and right side (501) of the divided block each have 4608 pixels. On the other hand, when the block is divided into two in the horizontal direction, as shown in FIG. 17B, the top side (510) and bottom side (511) of the divided block have 1024 pixels and 8192 pixels, respectively. That is, the largest number of pixels located outside the image border is 8192 pixels in the lower part obtained by dividing the block in the horizontal direction. Therefore, the separation direction at which the number of pixels becomes the largest is the horizontal direction (S1602).

Similarly, when a block is divided into three in the vertical direction, as shown in FIG. 17C, the left side (520) and right side (522) of the divided block each have 2304 pixels, and the center (521) has 4608 pixels. On the other hand, when the block is divided into three in the horizontal direction, as shown in FIG. 17D, the top side of the divided block has 0 pixels, the center (531) has 5120 pixels, and the bottom side (532) has 4096 pixels. That is, the largest number of pixels located outside the image border is 5120 pixels in the center, obtained by dividing the block horizontally. Therefore, the separation direction at which the number of pixels becomes the largest is the horizontal direction (S1602).

Finally, a determination is made as to whether the block is to be divided into two (S1603). When it is determined to divide the block into two (S1603: YES), the block is divided into two in the horizontal direction, which is the determined division direction (S1604). On the other hand, when it is determined to divide the block into three (S1603: NO), the block is divided into three in the horizontal direction, which is the determined division direction (S1605).

According to the present embodiment, when a block is divided into two or three, the division direction of the block is controlled to cause the block to contain the largest number of pixels outside the image boundary. This is because in a block containing out-of-frame pixels, the pixel values of the out-of-frame portion are uniform, and there is virtually no need to encode minor pixel changes. Therefore, it is possible to reduce the amount of encoding and improve the efficiency of encoding by bringing as many of such pixels in a block as possible.

Additionally, not only the block division direction but also the number of block divisions can be determined. As described above, the largest number of pixels outside the image boundary is 8192 pixels in the case of division by two and 5120 pixels in the case of division by three. That is, since the block located outside the image boundary has more pixels when divided by two, the block is divided by two.

This is because splitting by three encourages splitting the block at a position close to the end of the block compared to splitting by two. A split by three tends to have fewer pixels outside the image boundary than a split by two. Therefore, at the end of the frame, the block is not divided into three, and the direction in which the block is divided into two can be determined. This reduces the process required to split a block into three and thus speeds up the block splitting process.

The block split control is used to divide a block located at the end of a frame into two or three. That is, the halving or trifling process (S1004 to S1010) shown in FIG. 3 is replaced in the process described below. In addition, the halving or triple splitting process (S1104 to S1110) shown in FIG. 7 is replaced in the process described below. In addition, the process of splitting into two or three (S1202 to S1208) shown in FIG. 8 is replaced by the process described below.

With reference to FIG. 18, a description will be given of the block division control. First, for all block division patterns, the number of pixels outside the image boundary (S1651). All block separation patterns include two patterns: a pattern in which a block is divided into two in the horizontal direction and a pattern in which the block is divided into two in the vertical direction.

Next, a division direction is determined (S1652) in which a block is divided into two and with which the number of pixels outside the image boundary becomes the largest. Then, the block is divided into two in the dividing direction, whereby (S1654) is determined.

The syntax for splitting blocks according to the present embodiment is the same as shown in FIG. 13 but without the vertical_flag. This is because the block division direction is controlled according to the present embodiment, which eliminates the need for a vertical_flag. In addition, according to the present embodiment, the number of block divisions can be determined, and block division into three can be prevented. This eliminates the need for a BTflag so that a configuration without a BTflag can be used. The syntax for splitting blocks according to the present embodiment may be the same as shown in FIG. 13.

In the case of 1920 × 1080 pixels, there is no pixel outside the image boundary at the right end of the frame. However, when the image width is not equal to an integer multiple of the tree block size, there are pixels located outside the image boundary, so the block division is controlled in the same manner as described above.

According to the present embodiment, the block division direction is controlled based on the number of pixels outside the image boundary. The block division direction may be controlled based on the proportion of pixels located outside the image boundary.

This block division control allows a block located at the end of a frame to be divided into blocks of a suitable size and shape, and thus improves coding efficiency. This further allows separation of blocks suitable for image encoding and decoding.

Fourth Embodiment

A description will be given of an image encoding apparatus and an image decoding apparatus according to a fourth embodiment of the present invention. According to the fourth embodiment, a case that differs in an image boundary from the above-described embodiments will be described. Other configurations are similar to the first embodiment; therefore, description of other configurations is not given.

Here, consider a pattern that differs in image border from FIG. 12. It should be noted that even when the image boundary is different, no pattern is considered for which the determination result is the block separation limit determination is the same as in FIG. 12. For example, suppose the image border is slightly higher, as shown in FIG. 12A. Even in this case, block separation is limited because pixels outside the image boundary are separated. That is, for FIG. 12A, the result of determining whether or not to limit the block separation does not change even when the image boundary changes in position in the vertical direction. This is true for FIG. 12b. Similarly, for FIG. 12E and FIG. 12F, the result of determining whether or not to limit the block separation does not change even when the image boundary changes in position in the left-right direction.

As a result, patterns differing in image boundaries from FIG. 12 are the patterns shown in FIG. 19A-19D. The border of the image shown in Fig. 19A is higher than shown in FIG. 12C. Similarly, the border of the image shown in FIG. 19B is located higher than shown in FIG. 12D. Similarly, the image borders shown in FIG. 19C and FIG. 19D are closer to the left edge than shown in FIG. 12G and FIG. 12H.

Fig. 19A and FIG. 19B both show separation in the horizontal direction. However, dividing by two prevents the separation of pixels located outside the image boundary, while dividing by three encourages the separation of pixels located outside the image border. That is, only the division of the block into three is limited.

Fig. 19C and FIG. 19D show separation in the vertical direction. However, dividing by two prevents the separation of pixels located outside the image boundary, while dividing by three encourages the separation of pixels located outside the image border. That is, only the division of the block into three is limited.

Specifically, the determination of whether to limit the division of a block is different between division by two and division by three. This is because splitting by three results in splitting the block at a position close to the end of the block, compared to splitting by two. Splitting by three tends to separate pixels located outside the image boundary compared to splitting by two. Therefore, at the end of the frame, the block is not divided into three, and it can be decided whether to limit the direction in which the block is divided into two. This makes it possible to shorten the process required to split a block into three, and thus speed up the process of splitting a block.

Block splitting restrictions apply to splitting a block located at the end of a frame into two or three. That is, the halving or tri-diving process (S1004 to S1010) shown in FIG. 3 is replaced by the process described below. Moreover, the process of dividing into two or three (S1104 to S1110) shown in FIG. 7 is replaced by the process described below. Further, the halving or tri-diving process (S1202 to S1208) shown in FIG. 8 is replaced by the process described below.

With reference to FIG. 20, a description will be given of the limitations of block division. Fig. 20 is a diagram similar to FIG. 11, but without some processes. Therefore, the same step number as in FIG. 11 and description may be omitted.

First, for all block division patterns, a determination is made as to whether to limit block division (S1901). All block separation patterns include two patterns: a pattern in which a block is divided into two in a horizontal direction, and a pattern in which a block is divided into two in a vertical direction. Further, it is determined whether or not to limit the division of blocks based on whether pixels located outside the image boundary are separated. For example, when a block is divided into two in the horizontal direction, and pixels located outside the image boundary are divided accordingly, the division of the block into two in the horizontal direction is limited. S1302 and subsequent processes are the same as shown in FIG. 11, but without the processes associated with the division into three; therefore, the description of S1302 and subsequent processes is omitted.

With reference to FIG. 19A describes a specific example. In the case of FIG. 19A, for all block division patterns, a determination is made whether to restrict block division (S1901). When a block is halved in the horizontal direction, pixels outside the image boundary are not separated, so the division in the horizontal direction is not limited. Further, when a block is split into two in the vertical direction, pixels outside the image boundary are split, so that splitting in the vertical direction is limited. Therefore, block division is not limited for all block division patterns (S1302: NO). Block separation in the horizontal direction is not limited (S1303: NO) and block separation in the vertical direction is limited (S1304: YES). That is, the block is halved in the horizontal direction (S1312).

Consider a pattern in which the image border is closer to the top or to the left than the image borders shown in FIG. 19. This results in the fact that in any pattern, pixels located outside the border of the image must be separated. Therefore, at the end of the frame, the blocks are divided into two, and the division of the block into three is always limited.

The described block division control process divides a block located at the end of a frame into blocks of a suitable size and shape, and thus increases coding efficiency. This process further allows the block to be partitioned appropriately for encoding and decoding the image.

Fifth Embodiment

According to the fifth embodiment of the present invention, a description will be given of an image encoding apparatus and an image decoding apparatus. According to the fifth embodiment, block division restrictions at the lower right end of a frame will be described. Other configurations are similar to those of the first embodiment; hence, descriptions of other configurations are omitted.

As shown in FIG. 9, tree blocks located at the end of a frame may be in the frame and outside the frame relative to the image boundary. In particular, the out-of-frame part contained in tree block 1003 located at the lower right end of the frame tends to be larger than the out-of-frame part contained in tree block 1001 located at the right end of the frame or the out-of-frame part contained in block 1002 tree located at the lower end of the frame. Therefore, high probability block separation restrictions can improve coding efficiency. When splitting a tree block, the splitting of the blocks contained in the tree block obtained by splitting is limited.

With reference to FIG. 20 describes a block split constraint at the lower right end of a frame. The block located at the lower right end of the frame corresponds to the block 1003 of the tree shown in FIG. 9.

First, for all block division patterns, a determination is made as to whether to restrict block division (S1901). All block splitting patterns include two patterns: a pattern in which a block is split in two in the horizontal direction and a pattern in which a block is split in two in the vertical direction. Further, it is determined whether or not to limit the separation of blocks based on whether or not pixels are separated outside of the image boundary. For example, when a block is halved in the horizontal direction and pixels outside the image boundary are appropriately divided, the halving of the block in the horizontal direction is limited.

Because the block is located at the lower right end of the frame, pixels outside the image boundary are split for all block split patterns. When block division is restricted for all patterns (S1302: YES), the block is not divided (S1314).

With reference to FIG. 21 describes a specific example. Fig. 21A and FIG. 21B show all block division patterns for the tree block located at the lower right end of the frame. As shown in both Figs. 21A and FIG. 21B, pixels outside the image boundary are separated. When block division is restricted for all patterns (S1302: YES), the block is not divided (S1314).

Fig. 21C shows an example in which the image border is the same as shown in FIG. 21A and the wood block is divided into four. Let us assume that the four blocks obtained by division are indicated by blocks 601, 602, 603, 604 in z-scan order. Description of each block division step will be given with reference to FIG. 21c.

Fig. 21C shows the block division performed by the following steps. First, in the process shown in FIG. 3, the image is divided into tree blocks (S1000), it is determined that the inside of each tree block is divided into four (S1001: YES), and the tree block is divided into four (S1002). The process shown in Fig. 7 is performed for each of the blocks 601, 602, 603, 604 obtained by dividing by four.

As shown in FIG. 7, it is determined that the inside of the block obtained by dividing is not further divided into four (S1101: NO), and then it is determined that the inside of the block is divided into two or three (S1103: YES). The splitting process into two or three (S1104 to S1110) shown in FIG. 7 is replaced by the process shown in FIG. twenty.

As shown in FIG. 20, for all block division patterns, a determination is made as to whether the block division should be limited (S1901). Since the block is located at the lower right end of the frame, pixels located outside the image boundary are divided for all block separation patterns. When block division is restricted for all patterns (S1302: YES), the block is not divided (S1314). Then, the block division shown in FIG. 21c.

Fig. 21D shows an example in which the image border is different from the image border shown in FIG. 21C and the tree block is divided into four. This example shows a complex division of blocks according to a combination of the above embodiments. Of the four blocks obtained by division, blocks 602, 603 are further divided into blocks. A description will be given of each block splitting step to be performed after the tree block is divided into four (S1002) at each of the four blocks 601, 602, 603, 604.

The process shown in Fig. 7 is executed at block 601. In FIG. 7, it is determined that the inside of the block obtained by dividing is not further divided into four (S1101: NO), and then it is determined that the inside of the block is not divided into two or three (S1103: NO). The block division process is completed without further division of the inside of the block 601 (S1111).

The process shown in Fig. 7 is executed at block 602. In FIG. 7, it is determined that the inside of the block obtained by dividing is not further divided into four (S1101: NO), and then it is determined that the inside of the block is divided into two or three parts (S1103: YES). The splitting process into two or three (S1104 to S1110) shown in FIG. 7 is replaced by the process shown in FIG. twenty.

As shown in FIG. 20, for all block division patterns, a determination is made as to whether the block division should be limited (S1901). When a block is halved in the horizontal direction, pixels located outside the image boundary are separated, so that the separation in the horizontal direction is limited. Moreover, when a block is split into two in the vertical direction, pixels outside the image boundary are not split, so that splitting in the vertical direction is not limited. Therefore, block division is not limited for all block division patterns (S1302: NO). Then, the division of blocks in the horizontal direction is limited (S1303: YES). That is, the block is halved in the vertical direction (S1308). Block 602 then splits in the vertical direction along section 612.

At block 603, the process shown in FIG. 7. In FIG. 7, it is determined that the inside of the block obtained by dividing is not further divided into four (S1101: NO), and then it is determined that the inside of the block is divided into two or three parts (S1103: YES). The splitting process into two or three (S1104 to S1110) shown in FIG. 7 is replaced by the process shown in FIG. eighteen.

As shown in FIG. 18, for all block separation patterns, the number of pixels outside the image boundary is counted (S1651). All block separation patterns include two patterns: a pattern in which a block is divided into two in a horizontal direction, and a pattern in which a block is divided into two in a vertical direction. As shown in FIG. 17A and FIG. 17B, the number of pixels located outside the image boundary becomes the largest when the block 603 is divided in the horizontal direction. Therefore, the dividing direction in which a block is divided into two and in which the number of pixels outside the image boundary becomes the largest is determined as the horizontal direction (S1652). Then, the block is divided into two in the division direction thus determined (S1654). As a result, the block 603 splits in the horizontal direction along the section 623.

At block 604, the process shown in FIG. 7. As shown in FIG. 7, it is determined that the inside of the block obtained by splitting is not further divided into four (S1101: NO), and then it is determined that the inside of the block is divided into two or three parts (S1103: YES). The splitting process into two or three (S1104 to S1110) shown in FIG. 7 is replaced by the process shown in FIG. twenty.

As shown in FIG. 20, for all block division patterns, a determination is made as to whether the block division should be limited (S1901). When a block is split in two in the horizontal direction along section 624, pixels located outside the image boundary are split so that the split in the horizontal direction is limited. Further, when a block is split in two in the vertical direction along section 614, pixels outside the image boundary are split so that splitting in the vertical direction is limited. That is, for all block separation patterns, pixels located outside the image boundary are separated. When block division is restricted for all patterns (S1302: YES), the block is not divided (S1314).

This block division control allows a block located at the end of a frame to be divided into blocks of a suitable size and shape, and thus improves coding efficiency. This further allows separation of blocks suitable for image encoding and decoding.

According to all the embodiments described above, the block separation process at a position outside the image boundary can be controlled. Accordingly, with any given desired border, the block separation process at a position outside the image border can be controlled. Additionally, the definition of more significant pixels than neighboring pixels can be considered as any desired border, allowing control over the separation of blocks located outside the border. Additionally, the position beyond any desired boundary is not limited to the bottom end or right end of the frame, but may be the top end or left end of the frame, or may be different from such ends. This makes it possible to divide even a block that is not located at the end of a frame into blocks of a suitable size and shape, and thus can improve coding efficiency.

All or some of the embodiments described above may be combined.

According to all the above-described embodiments, the bitstream output by the image encoding apparatus has a specific data format for decoding according to the encoding method used in the embodiments. The bitstream may be delivered via a recording medium that is readable by a computer or the like and on which the bitstream is recorded, such as an HDD, SSD, flash memory or optical disc, or alternatively may be delivered from a server via a wired or wireless network. Therefore, an image decoding apparatus compatible with this image encoding apparatus is capable of decoding a bitstream having this particular data format regardless of delivery methods.

In the case of using a wired or wireless network to exchange the bit stream between the image encoding device and the image decoding device, the bit stream can be converted into a data format suitable for the transmission form of the communication path and then transmitted. In this case, a transmission device that converts the bitstream output from the image encoding device into coded data having a data format suitable for the transmission form of the communication path and transmits the coded data to the network, and a reception device that receives the coded data via the network, decodes the encoded data into a bitstream, and provides the bitstream to an image decoding device.

The transmission apparatus includes a memory that serves as a buffer for storing a bitstream output from the image encoding apparatus, a packet processor that packetizes the bitstream, and a transmitter that transmits the packetized encoded data over a network. The receiving device includes a receiver that receives the packetized encoded data over a network, a memory that serves as a buffer for storing the encoded data thus obtained, and a packet processor that packetizes the encoded data to generate a bitstream and delivers the bitstream to the device for image decoding.

When a wired or wireless network is used to exchange the bit stream between the image encoding device and the image decoding device, a relay device is used in addition to the transmission device and the reception device, which receives the encoded data transmitted by the transmission device and provides the encoded data to the reception device. The relay device includes a receiver that receives the packetized coded data transmitted by the transmission device, a memory that serves as a buffer for storing the coded data thus obtained, and a transmitter that transmits the packetized coded data to the network. The relay apparatus may further include a receive packet processor that performs packet processing on the packetized encoded data to generate a bitstream, a recording medium that stores the bitstream, and a transmit packet processor that packetizes the bitstream.

Additionally, may be added as a component serving as a display device such as a display that displays an image decoded by the image decoding device. In this case, the display reads the decoded image signal generated by the decoded image signal overlay part 205 and stored in the decoded image memory 206, and displays the decoded image signal on the screen.

Additionally, a component serving as an imaging device, such as an imaging part that inputs a captured image to an image encoding device, may be added. In this case, the imaging part inputs the captured image signal into the block divider 101 .

Fig. 22 shows an example of the hardware structure of the device for encoding and decoding according to the present invention. The encoding and decoding apparatus includes an image encoding apparatus structure and an image decoding apparatus structure according to embodiments of the present invention. The encoding and decoding apparatus 9000 includes a CPU 9001, a codec IC 9002, an input/output interface 9003, a memory 9004, an optical disc drive 9005, a network interface 9006, and a video interface 9009, and all components are connected via a bus 9010.

Image encoder 9007 and image decoder 9008 are typically implemented as codec IC 9002. The image encoding process in the image encoding apparatus according to the embodiments of the present invention is performed by the image encoder 9007, and the image decoding process in the image decoding apparatus according to the embodiments of the present invention is performed by the image encoder 9007. The I/O interface 9003 is implemented, for example, via a USB interface and is connected to an external keyboard 9104, mouse 9105 or the like. The CPU 9001 controls the device 9000 for encoding and decoding to perform an operation required by the user, in accordance with the input of the user operation through the I/O interface 9003. The user operation performed by the keyboard 9104, mouse 9105, or the like includes selection of encoding and decoding functions to be performed, encoding quality settings, bitstream input and output destinations, image input and output destinations, and the like. .

When the user wishes to reproduce an image recorded on the disc recording medium 9100, the optical disc drive 9005 reads the bitstream from the inserted disc recording medium 9100 and transmits the bitstream thus read to the image decoder 9008 of the IC codec 9002 over the bus 9010. The image decoder 9008 performs an image decoding process in the image decoding apparatus according to the embodiments of the present invention on the bitstream thus input, and transmits the decoded image to the external monitor 9103 via the video interface 9009. Further, the encoding and decoding apparatus 9000 includes a network interface 9006 for connecting to the external distribution server 9106 or mobile terminal 9107 over the network 9101. When the user wishes to play back an image recorded on the distribution server 9106 or mobile terminal 9107 instead of an image recorded on the disk media recording body 9100, the network interface 9006 retrieves the bitstream via the network 9101 instead of reading the bitstream from the inserted disk recording medium 9100. Further, when the user wishes to reproduce an image recorded in the memory 9004, an image decoding process is performed in the image decoding apparatus according to embodiments of the present invention on the bitstream recorded in the memory 9004.

When the user requires an operation to encode an image captured by the external camera 9102 and write the image thus encoded to the memory 9004, the video interface 9009 receives the image from the camera 9102 and transmits the image to the image encoder 9007. codec 9002 over bus 9010. An image encoder 9007 performs an image encoding process in an image encoding device according to embodiments of the present invention on an image input via a video interface 9009 to generate a bitstream. The bitstream is then transferred to the memory 9004 over the bus 9010. When the user wishes to record the bitstream onto the disk recording medium 9100 instead of the memory 9004, the optical disc drive 9005 writes the bitstream onto the inserted disk recording medium 9100.

A hardware structure having an image encoding device and no image decoding device, or a hardware structure having an image decoding device and no image encoding device can be implemented. Such a hardware structure is implemented, for example, by replacing the IC codec 9002 with an image encoder 9007 or an image decoder 9008.

Obviously, the processes described above for encoding and decoding can be implemented as a transmission device, a storage device, and a reception device using hardware, or alternatively, can be implemented via firmware stored in read only memory (ROM), flash memory. or the like, or software installed on a computer, or the like. The firmware program and the software may be delivered via a recording medium that is readable by a computer or the like. and on which the firmware program and the software program are recorded may be delivered from a server via a wired or wireless network, or may be delivered via a data broadcast such as digital terrestrial broadcast or satellite digital broadcast.

The present invention has been described based on embodiments. Those skilled in the art will appreciate that these embodiments are illustrative and that various modifications to the combination of components or processes are possible, and that such modifications are also within the scope of the present invention.

Industrial Applicability

The present invention is applicable to image encoding and decoding methods.

List of reference positions

100 image encoding device, 101 block separator, 102 prediction image generator, 103 residual signal generator, 104 orthogonal transform and quantization part, 105 encoder, 106 inverse quantization and inverse orthogonal transform part, 107 overlay part decoded image signals, 108 decoded image memory, 200 image decoding apparatus, 201 decoder, 202 block separator, 203 inverse quantization and inverse orthogonal transform part, 204 prediction image generator, 205 decoded image signal overlay part, 206 - decoded picture memory.

Claims (28)

1. An image decoding device, characterized in that it is configured to decode an image in units of blocks obtained by division, the image decoding device comprising: a decoder configured to decode block separation information that includes a flag indicating whether the block is divided by a separation line in a horizontal direction or a separation line in a vertical direction; and a block delimiter configured to recursively divide an image into rectangles of a predetermined size based on the block delimiter information to generate a target block, the block delimiter including a quaternary splitter configured to split the target block obtained by the recursive split in half in both the horizontal and vertical directions to generate four blocks, and a binary/ternary delimiter configured to divide the target block obtained by the recursive division into two or three in the horizontal direction or in the vertical direction to generate two or three blocks, wherein the binary/ternary delimiter is configured to prohibit division of the target block by the division line in the horizontal direction and allow division of the target block by the division line in the vertical direction, when division of the target block by the division line in the horizontal direction causes the target block obtained by division to be beyond the right side of the image boundary , and prohibit splitting the target block with a split line in the vertical direction, and allow splitting the target block with a split line in the horizontal direction, when dividing the target block with the split line in the vertical direction causes the target block obtained by splitting to be beyond the bottom side of the image boundary, while the decoder is configured not to decode the flag under a condition that prohibits splitting the target block with a split line in the horizontal direction or a split line in the vertical direction. 2. An image decoding method for decoding an image in units of blocks obtained by division, the image decoding method comprising: a decoding step of decoding block separation information that includes a flag indicating whether to divide the target block with a separation line in the horizontal direction or a separation line in the vertical direction; and a block splitting step of recursively dividing an image into rectangles of a predetermined size based on the block splitting information to generate a target block, the block splitting step including a quaternary splitting step of splitting the target block obtained by the recursive splitting in half in both the horizontal and vertical directions to generate four blocks, and a binary/ternary splitting step in which the target block obtained by the recursive splitting is divided into two or three in the horizontal or vertical direction to generate two or three blocks, wherein at the stage of binary/ternary division, the division of the target block by the division line in the horizontal direction is prohibited and the division of the target block by the division line in the vertical direction is allowed, when the division of the target block by the division line in the horizontal direction leads to the location of the target block obtained by division beyond the right side of the image border, and forbidding the target block to be divided by the vertical dividing line, and allowing the target block to be divided by the vertical dividing line when dividing the target block by the vertical dividing line causes the target block obtained by dividing to be beyond the lower side of the image boundary, wherein in the decoding step, a flag is not decoded under a condition that prohibits division of the target block by a division line in the horizontal direction or a division line in the vertical direction. 3. A device for encoding an image, characterized in that it is configured to encode an image in units of blocks obtained by division, and the device for encoding an image contains: a block divider configured to recursively divide the image into rectangles of a given size to generate a target block; and an encoder configured to encode partitioning information that includes a flag indicating whether to partition the target block with a partition line in a horizontal direction or a partition line in a vertical direction; while the block separator includes: a quaternary splitter configured to split the target block obtained by the recursive split in half in both the horizontal and vertical directions to generate four blocks, and a binary/ternary delimiter configured to divide the target block obtained by the recursive division into two or three in the horizontal direction or in the vertical direction to generate two or three blocks, wherein the binary/ternary delimiter is configured to prohibit division of the target block by the division line in the horizontal direction and allow division of the target block by the division line in the vertical direction, when division of the target block by the division line in the horizontal direction causes the target block obtained by division to be beyond the right side of the image boundary , and prohibit splitting the target block with a split line in the vertical direction, and allow splitting the target block with a split line in the horizontal direction, when dividing the target block with the split line in the vertical direction causes the target block obtained by splitting to be beyond the bottom side of the image boundary, while the encoder is configured not to encode the flag under a condition that prohibits splitting the target block with a split line in the horizontal direction or a split line in the vertical direction. 4. An image encoding method for encoding an image in units of blocks obtained by division, the image encoding method comprising: a block splitting step of recursively dividing an image into rectangles of a predetermined size to generate a target block; and an encoding step of encoding block separation information that includes a flag indicating whether to divide the target block with a separation line in the horizontal direction or a separation line in the vertical direction; wherein the block splitting step includes a quaternary splitting step of splitting the target block obtained by the recursive splitting in half in both the horizontal and vertical directions to generate four blocks, and a binary/ternary splitting step in which the target block obtained by the recursive splitting is divided into two or three in the horizontal or vertical direction to generate two or three blocks, wherein at the stage of binary/triple division, the division of the target block by the division line in the horizontal direction is prohibited and the division of the target block by the division line in the vertical direction is allowed, when the division of the target block by the division line in the horizontal direction leads to the location of the target block obtained by division beyond the right side of the image border, and prohibiting the division of the target block by the division line in the vertical direction, and allowing the division of the target block by the division line in the horizontal direction, when the division of the target block by the division line in the vertical direction causes the target block obtained by division to be beyond the lower side of the image boundary, while in the encoding step, do not encode a flag under a condition that prohibits division of the target block by a division line in the horizontal direction or a division line in the vertical direction.

Images