HK1205611B

HK1205611B - Decoding method using a tree structure

Info

Publication number: HK1205611B
Application number: HK15106126.7A
Authority: HK
Inventors: 金守年; 林晶娟; 崔栽熏; 李圭珉; 文柱禧; 李英烈; 金海光; 全炳宇; 韩锺基; 金东元
Original assignee: Sk电信有限公司
Priority date: 2009-12-10
Filing date: 2015-06-26
Publication date: 2018-09-07

Abstract

The present invention relates to an encoding / decoding method and apparatus using a tree structure. The present invention provides a method for encoding information pertaining to an image, comprising the following steps: grouping predetermined regions having image information into a plurality of groups, determining the minimum or maximum value of the information to be encoded in the grouped regions, said information pertaining to the grouped regions, and generating node values for each of a plurality of layers to the uppermost layer; and encoding the difference between the node values for each of the layers and the node values of the upper layers, or the difference between the node values for each of the layers and the values determined in accordance with a preset reference. According to the present invention, various items of information on the image are encoded and the encoded data are decoded using a tree structure, thereby improving encoding efficiency and image compression efficiency.

Description

Decoding method using tree structure

The application is a divisional application of an invention patent application with an original application number of 201080063636.0 (international application number: PCT/KR2010/008860, application date: 2010, 12 months and 10 days, title of the invention: encoding/decoding method and apparatus using a tree structure).

Technical Field

The present disclosure relates to an encoding/decoding method and apparatus using a tree structure. More particularly, the present disclosure relates to a method and apparatus for improving encoding efficiency and thus video compression efficiency by using a tree structure in encoding of various image information and decoding of the resulting encoded data.

Background

The statements in this section merely provide background information related to the present disclosure and may not constitute prior art

Current video data compression techniques include h.261, h.263, MPEG-2, MPEG-4, etc. In encoding an image, the existing video compression technology divides each image into fixed-size macroblocks composed of a rectangular 16 × 16 pixel region having a luminance component and a rectangular 8 × 8 pixel region having a chrominance component. All these luma and chroma components are spatially or temporally predicted and the resulting prediction residual undergoes transformation, quantization and entropy coding before being finally compressed.

The encoding apparatus subdivides each macroblock into smaller-sized blocks of 16 × 16, 8 × 8, and 4 × 4 using the h.264/AVC compression standard to perform intra prediction encoding, in which a 16 × 16 pixel block is processed in one of 4 prediction modes, and an 8 × 8 pixel block and a 4 × 4 pixel block are processed in one of 9 prediction modes. For inter prediction encoding, each macroblock may first be divided into blocks of pixel sizes 16 × 16, 16 × 8, 8 × 16, 8 × 8, 8 × 4, 4 × 8, and 4 × 4. The transform is performed in units of 8 × 8 or 4 × 4 pixel blocks, and quantization of the transform coefficients uses scalar quantization. In this way, it is desirable for the video encoding apparatus in the intra-prediction encoding or inter-prediction encoding process to encode not only the target image but also various information for intra-prediction and inter-prediction.

In addition, compression of high-resolution video such as 4K × 2K video has a significant necessity, but such a technique that can efficiently compress high-resolution video of a large capacity has not been developed yet. Also, as the video size increases and the unit of division for encoding large-capacity video increases, more information is required for intra prediction encoding and inter prediction encoding, so that video compression efficiency decreases. Therefore, it is required to develop a technology capable of improving coding efficiency and video compression efficiency.

Disclosure of Invention

Technical problem

To solve the above problems and meet the needs of the developed technology, the present disclosure mainly attempts to improve encoding efficiency and thus video compression efficiency by using a tree structure in encoding of various image information and decoding of the resulting encoded data.

Summary of The Invention

One embodiment of the present disclosure provides an encoding apparatus for encoding image information to be encoded, the encoding apparatus including: a tree encoder for dividing a predetermined area having image information into a plurality of groups, generating a node value of each layer up to an uppermost layer by determining a minimum value or a maximum value of information to be encoded within the grouped area as information on the grouped area, and encoding a difference value between the node value of each layer and a node value of an upper layer or a difference value between the node value of each layer and a value determined based on a preset criterion; and an additional information encoder for encoding additional information including information on the maximum number of layers, information on the number of areas to be grouped, and information on whether a node value of each layer is determined by a minimum value or a maximum value among node values of a lower layer.

Another embodiment of the present disclosure provides a decoding apparatus for decoding a bitstream to reconstruct information, the decoding apparatus including: an additional information decoder for decoding the bitstream to reconstruct additional information, the additional information including information on the maximum number of layers, information on a size of an area of the lowermost layer, and information on whether a node value of each layer is determined by a minimum value or a maximum value among node values of a lower layer; and a tree decoder for reconstructing a difference value between a node value of each layer and a node value of an upper layer or a difference value between a node value of each layer and a value determined based on a preset criterion by decoding the bitstream using the additional information, adding the reconstructed difference value and the node value of the upper layer to reconstruct the node value of each layer, and reconstructing a node value of a lowermost layer as information to be decoded.

Yet another embodiment of the present disclosure provides an encoding apparatus for encoding image information to be encoded, the encoding apparatus including: a tree encoder for grouping areas having the same information among predetermined areas having the image information, and encoding one or more of a node value and a flag indicating whether a node of each layer is divided; and an additional information encoder for encoding additional information including information on the maximum number of layers and information on the size of an area indicated by each node of the lowest layer.

Yet another embodiment of the present disclosure provides a decoding apparatus for decoding a bitstream to reconstruct information, the decoding apparatus including: an additional information decoder for decoding a bitstream to reconstruct additional information including information on the maximum number of layers and information on sizes of areas indicated by respective nodes of the lowest layer; and a tree decoder for decoding the bitstream based on the additional information to reconstruct a flag indicating whether a node of each layer from an uppermost layer to a lowermost layer is divided, and reconstructing the information by reconstructing a node value of a node of each layer according to the reconstructed flag.

Yet another embodiment of the present disclosure provides an encoding method for encoding image information by using a tree structure, the encoding method including: forming a tree structure in which each layer includes at least one node, and the nodes are divided into or not divided into lower-layer nodes; encoding a flag indicating whether the node is divided into nodes of the lower layer; and encoding additional information including information on the maximum number of layers and information on the size of an area indicated by each node of the lowest layer.

Yet another embodiment of the present disclosure provides a decoding method for reconstructing image information by using a tree structure, the decoding method including: reconstructing additional information including information on the maximum number of layers constituting the tree structure and information on the size of an area indicated by each node of the lowest layer; and reconstructing a flag indicating whether the respective nodes included in each layer are divided, based on the additional information, and reconstructing a node value of a node of each layer according to the reconstructed flag.

Advantageous effects

According to the present disclosure as described above, by using a tree structure in encoding various image information and decoding the resulting encoded data, it is possible to improve encoding efficiency and thus video compression efficiency.

Drawings

Fig. 1 is a block diagram schematically illustrating an encoding apparatus using a tree structure according to a first embodiment of the present disclosure;

fig. 2 is an exemplary diagram illustrating information to be encoded using a tree structure according to a first embodiment of the present disclosure;

fig. 3 is an exemplary diagram illustrating a tag tree of information related to a region determined at each layer according to a first embodiment of the present disclosure;

fig. 4 is an exemplary diagram illustrating bits encoded using a tree structure according to a first embodiment of the present disclosure;

fig. 5 is a flowchart illustrating an encoding method using a tree structure according to a first embodiment of the present disclosure;

fig. 6 is a block diagram schematically illustrating a decoding method using a tree structure according to a first embodiment of the present disclosure;

fig. 7 is a flowchart illustrating a decoding method using a tree structure according to a first embodiment of the present disclosure;

fig. 8 is a block diagram schematically illustrating an encoding apparatus using a tree structure according to a second embodiment of the present disclosure;

fig. 9 is an exemplary diagram illustrating a tree structure according to a second embodiment of the present disclosure;

fig. 10 is an exemplary diagram illustrating an information encoding result expressed as a tree structure according to a second embodiment of the present disclosure;

fig. 11 is an exemplary diagram illustrating another scheme for dividing nodes into lower layers according to a second embodiment of the present disclosure;

fig. 12 and 13 are exemplary diagrams illustrating grouping when information related to areas is distributed according to different schemes;

fig. 14 is a flowchart illustrating an encoding method using a tree structure according to a second embodiment of the present disclosure;

fig. 15 is a block diagram schematically illustrating a decoding apparatus using a tree structure according to a second embodiment of the present disclosure; and

fig. 16 is a flowchart illustrating a decoding method using a tree structure according to a second embodiment of the present disclosure.

Detailed Description

An encoding/decoding method and apparatus using a tree structure according to an embodiment of the present disclosure will be described in detail below with reference to the accompanying drawings.

According to the embodiments of the present disclosure, in encoding image information to be encoded and decoding the generated encoded data, encoding efficiency is improved by using a tree structure.

According to the embodiments of the present disclosure, information to be encoded may be information related to an image signal or various information for encoding an image signal, such as macroblock size and macroblock type information of a variable-size macroblock, partition information indicating the size and type of subblocks used for prediction and transformation, intra prediction information, a motion vector prediction direction, an optimal motion vector prediction candidate, an optimal interpolation filter of an arbitrary-size region, whether an image enhancement filter is used or not, a reference picture index, a quantization matrix index, optimal motion vector precision and transformation size information, image pixel information, encoding block information, or coefficient information indicating whether a transform coefficient other than zero exists within a predetermined block.

In addition, the predetermined region may be a macroblock of variable size, or may be blocks of various pixel sizes, such as 64 × 64 pixel blocks, 32 × 32 pixel blocks, 16 × 16 pixel blocks, 16 × 32 pixel blocks, or 4 × 16 pixel blocks. In addition, the predetermined area may be various types and sizes of areas, such as a block from which a motion vector is determined.

According to an embodiment of the present disclosure, encoding and decoding may be applied to entropy encoding and entropy decoding, but is not limited thereto, and may also be applied to various other encoding and decoding.

Fig. 1 is a block diagram schematically illustrating an encoding apparatus using a tree structure according to a first embodiment of the present disclosure.

The encoding apparatus 100 using the tree structure according to the first embodiment of the present disclosure may include a tree encoder 110 and an additional information encoder 120.

The tree encoder 110 divides a predetermined area having image information to be encoded into a plurality of groups, generates a node value of each layer up to an uppermost layer by determining a minimum value or a maximum value of the information to be encoded within the grouped area as information on the grouped area, and encodes a difference value between the node value of each layer and a node value of an upper layer or a difference value between the node value of each layer and a value determined based on a preset criterion.

The term "node value of each layer" denotes a value of information related to a grouped area of each layer. For example, the node value of the lowermost layer may be a value of information related to a predetermined area. The node value of the upper layer of the lowermost layer may be a value of information on areas grouped by a predetermined area. The value of the information related to the grouping region may be decided by a minimum value or a maximum value among values of the information related to the predetermined region included in the grouping region. Further, the value decided by the preset criterion may be a value having the highest occurrence probability in the region so far among the previous region or the adjacent region, but is not limited thereto, and may be a value decided by various criteria.

In this case, the tree encoder 110 may encode a difference value between the node value of each layer and the node value of the upper layer by using various binary encoding methods such as a unary code, a truncated unary code, and an exponential Golomb (Exp-Golomb) code. In addition, after binarizing the difference value between the node value of each layer and the node value of the upper layer by using various binary encoding methods such as unary code, truncated unary code, and exponential Golomb (Exp-Golomb) code, the tree encoder 110 may perform binary arithmetic encoding by determining a probability model for encoding the node value of a layer to be encoded based on the node value of the adjacent or upper layer, or by changing the probability model at each layer.

In addition, if the node value of each layer is determined by the minimum value among the node values of the lower layers, the tree encoder 110 skips encoding of the node values of the layers below the layer having the maximum node value. That is, in the case where the node value of each layer is decided by the minimum value among the node values of the lower layer, if a certain node value of a certain layer is the maximum value of information to be encoded, the tree encoder 110 encodes the node value of the corresponding layer and skips encoding of the node values of the lower layer, assuming that the node values of the lower layer have the same value. On the other hand, in the case where the node value of each layer is determined by the maximum value among the node values of the lower layers, the tree encoder 110 skips encoding of the node values of the layers below the layer having the smallest node value. That is, in the case where the node value of each layer is decided by the maximum value among the node values of the lower layer, if a certain node value of a certain layer is the minimum value that information to be encoded can have, the tree encoder 110 encodes the node value of the corresponding layer and skips encoding of the node values of the lower layer, assuming that all the node values of the lower layer have the same value.

In addition, in order to perform encoding according to the occurrence probability of information to be encoded, the tree encoder 110 may assign a small number or a large number according to the occurrence probability by changing the number (code number) assigned to the information to be encoded. In this case, the occurrence probability of the information to be encoded may be calculated by using various occurrence probabilities such as the occurrence probability of information on a predetermined adjacent region or the occurrence probability of information on a region that has been encoded so far within the entire or partial region including the information to be encoded.

In the case where the tree encoder 110 encodes the node value of the uppermost layer, since there is no upper layer of the uppermost layer, the tree encoder 110 may set the node value of the upper layer of the uppermost layer to a predetermined value and may encode a difference value between the node value of the uppermost layer and the set predetermined value. In this case, the predetermined value set as the node value of the upper layer of the uppermost layer may be set by various values, such as a value having the highest occurrence probability so far when encoded, among the values of information on predetermined adjacent regions, a preset value, and the entire region or a partial region including information to be encoded.

According to the first embodiment of the present disclosure, the additional information encoder 120 encodes additional information for encoding information related to a predetermined area using a tree structure. The additional information may be information on the maximum number of layers, information on the size of an area of the lowermost layer, and information on whether the node value of each layer is determined by the minimum value or the maximum value among the node values of the lower layer. The encoded additional information may be included in a header of a predetermined coding unit, such as a sequence header, a picture header, or a slice header of a bitstream.

A process of encoding information to be encoded by using the tree structure will be described in detail below with reference to fig. 2 to 4.

Fig. 2 is an exemplary diagram illustrating information to be encoded using a tree structure and numbers assigned to the respective information according to a first embodiment of the present disclosure.

In the case of inter prediction, when an image macroblock is a 64 × 64 pixel block and is divided into 8 × 16 pixel subblocks, the motion vector precision determined at each 8 × 16 pixel subblock is illustrated in fig. 2. In this case, the information to be encoded is the motion vector precision of the predetermined region, and the predetermined region is an 8 × 16 pixel sub-block.

The encoding may be implemented by using an unchanged value (unchanged value) of data to be encoded, and may also be implemented by assigning a number to the data to be encoded. The method for assigning numbers may be modified in various ways according to the occurrence probability of data. The embodiment of fig. 2 shows an example of assigning numbers 1, 2 and 3 to 1/2, 1/4 and 1/8 accuracies, respectively. The encoding apparatus 100 according to the first embodiment of the present disclosure may determine the node value of each layer by repeating a process of assigning a number to a motion vector as shown in fig. 2, grouping a predetermined number of predetermined regions for encoding using a tree structure as shown in fig. 3, and determining information related to the grouped regions based on information included within the grouped regions, at each layer.

Fig. 3 is an exemplary diagram of a tag tree showing information on an area determined at each layer according to a first embodiment of the present disclosure.

In order to encode information to be encoded using a tree structure as shown in fig. 2, the video encoding apparatus 100 determines the tree structure shown in fig. 3 by repeating a process of grouping 4 8 × 16 pixel subblocks in each layer up to the highest layer and determining information about each grouping region using the minimum value of information included in the grouping region.

Thereafter, the video encoding apparatus 100 encodes additional information for encoding information based on the tree structure. The additional information may be information on the maximum number of layers in the tree structure, information on the size of an area of the lowest layer, and information on whether the information on the area grouped with each layer is determined by the minimum value or the maximum value among the information on the areas of the lower layers. Instead of the information on the size of the area of the lowest layer, the information on the number of areas to be grouped may be included in the additional information and then encoded. In fig. 3, as additional information, the maximum number of layers in the tree structure is 4, the size of the area of the lowest layer is 8 × 16 pixels, and the information on the grouping area of each layer is the minimum value of the information on the area of the lower layer. In this case, instead of encoding the size of the area of the lowest layer as additional information, the number of areas to be grouped "4" may be encoded as encoding information.

Referring to fig. 3, since the minimum value of the numbers assigned to the first 4 regions of the layer 3 is the number 1 indicating 1/2 precision, the value of the information on the first region of the layer 2 is the number 1 indicating 1/2 precision. In this way, the tree structure as shown in fig. 3 is determined by the following steps: regions of each layer from layer 3 to layer 0 are grouped, and a minimum value of information on regions included in the grouped regions is determined as a value of the information on the grouped regions.

If the tree structure as shown in fig. 3 is determined, the encoding apparatus 100 generates code bits (code bits) from an upper layer to a lower layer and encodes the generated code bits. In addition, since the encoding apparatus 100 knows the maximum value of information to be encoded, the encoding apparatus 100 can generate a binary bit (binary bit) by using a truncated unary code.

In this case, the method for encoding the node of each layer encodes a difference value from the upper layer node value, and the method for encoding the difference value encodes as many binary bits "0" as the difference value, and encodes a binary bit "1" at the end. If there is no difference between the value of the current node to be encoded and the value of the upper node, a binary bit "1" is encoded.

More specifically, the method for encoding each node value encodes a difference value between a value of a current node to be encoded and a value of an upper node by using binary bits "0" and "1", except for the following cases (1) to (3). Only as many binary bits "0" as the difference are encoded, and at the end binary bits "1" are encoded. If there is no difference between the value of the current node to be encoded and the value of the upper node, a binary bit "1" is encoded. In contrast, as many binary bits "1" as the difference value may be encoded, and if there is no difference between the value of the current node to be encoded and the value of the upper node, a binary bit "0" may be encoded.

(1) In encoding each node value, in the case where the value of the upper node is the maximum value that the data to be encoded can have, the lower node is not encoded because the lower node cannot have a larger value than the upper node. That is, all lower nodes have the same value as the number of the upper node.

(2) In encoding the difference value, in the case where the value of the current node is the value of the data to be encoded or the maximum value that the number may have, the binary bit "0" is encoded in the same number as the difference value of the upper node, and the binary bit "1" indicating the termination of encoding of the current node is not encoded at the end thereof. For example, if the maximum value that the data to be encoded can have is 3 and the value of the upper node is 1, the binary bit "00" is encoded and the value of the current node to be encoded is 3.

(3) When the value of the last node among the nodes having the same upper node is encoded, in the case where the values of the nodes other than the last node are greater than the value of the upper node, the value of the last node is not encoded.

In encoding the value of the highest-level node, a difference value from the maximum value that the value or number of data to be encoded can have is encoded by using the above-described binary bit 0 or 1. In addition, another method for encoding the value of the highest level node may encode a difference value from the number or data having the highest occurrence probability.

Fig. 4 is an exemplary diagram illustrating bits of the motion vector precision of fig. 2 encoded by using a tree structure according to a first embodiment of the present disclosure.

Fig. 4 illustrates bits generated by encoding information about the regions of fig. 2 using a tree structure and corresponding regions. A process of encoding information related to the region of fig. 2 by using the tree structure of fig. 3 will be described below with reference to fig. 4. In the following encoding process, the node value means a number.

In the case of the region (0,0), the 0 th layer as the highest layer does not have an upper layer. Assuming that 1/2 precision has the highest occurrence probability, the node value of the upper layer is set to 1(1/2 precision). Therefore, the difference value between the node value of the uppermost layer and the node value of the layer above it is 0. If expressed as a binary bit string, 0 becomes 1. Since the node value of the region (0,0) in the 1 st layer is 1(1/2 precision) and the node value of the upper layer is 1(1/2 precision), the difference value therebetween is 0. If expressed as a binary bit string, 0 becomes 1. Since the node value of the region (0,0) in the 2 nd layer is 1(1/2 precision) and the node value of the upper layer is 1(1/2 precision), the difference value therebetween is 0. If expressed as a binary bit string, 0 becomes 1. Since the node value of the region (0,0) in the 3 rd layer is 1(1/2 precision) and the node value of the upper layer is 1(1/2 precision), the difference value therebetween is 0. If expressed as a binary bit string, 0 becomes 1. Therefore, a binary bit string obtained by encoding information on the region (0,0) among the regions shown in fig. 1 is 1111.

In the case of the area (0,1), since the node values of the 0 th layer, the 1 st layer, and the 2 nd layer have been encoded in the process of encoding the node values of the area (0,0), the node values of the 0 th layer, the 1 st layer, and the 2 nd layer are not encoded, and only the node value of the 3 rd layer is encoded. Since the node value of the area (0,1) in the 3 rd layer is 2(1/4 precision) and the node value of the upper layer thereof is 1(1/2 precision), the difference value between the numbers is 1. If represented as a binary bit string, a 1 becomes 01. Therefore, a binary bit string obtained by encoding information on the region (0,1) among the regions shown in fig. 2 is 01.

In the case of the area (0,4), since the node value of the 0 th layer has been encoded in the process of encoding the area (0,0), the node value of the 0 th layer is not encoded, and only the node values of the 1 st, 2 nd and 3 rd layers are encoded. Since the node value of the area (0,1) in the 1 st layer is 1(1/2 precision) and the node value of the upper layer thereof is 1(1/2 precision), the difference value between the numbers is 1. If represented as a binary bit string, a 1 becomes 01. Since the node value of the area (0,2) in the 2 nd layer is 2(1/4 precision) and the node value of the upper layer thereof is 2(1/4 precision), the difference value between the numbers is 0. If represented as a binary bit string, a 0 becomes a 1. Since the node value of the region (0,4) in the 3 rd layer is 2(1/4 precision) and the node value of the upper layer thereof is 2(1/4 precision), the difference value between the numbers is 0. If represented as a binary bit string, a 0 becomes a 1. Therefore, a binary bit string obtained by encoding information on the region (0,4) among the regions shown in fig. 1 is 0111.

In the case of the region (2,0), since the node values of the 0 th and 1 st layers have already been encoded, the encoded values of the 0 th and 1 st layers are not encoded, and only the node values of the 2 nd and 3 rd layers are encoded. Since the node value of the region (1,0) in the 2 nd layer is 3(1/8 precision) and the node value of the upper layer is 1(1/2 precision), the difference value between the numbers is a maximum value of 2 and the corresponding node value is 3(1/8 precision). Thus, the binary bit string generated by the truncated unary code is 00. Since the maximum value occurs, the node value of the lower layer of the corresponding node is not encoded.

Also, in the case of the region (2,6), since the node values of the 0 th and 2 nd layers have already been encoded, the node values of the 0 th and 1 st layers are not encoded, and only the node values of the 2 nd and 3 rd layers are encoded. Since the node value of the region (0,1) in the 2 nd layer is 3(1/8 precision) and the node value of the upper layer is 2(1/4 precision), the difference value between them is 1 and the corresponding node value is 3(1/8 precision). Therefore, the binary bit string generated by truncating the unary code is 0. In this case, the node value of the lower layer is not encoded because the maximum value occurs.

In the case of performing arithmetic coding, the encoding apparatus 100 generates a probability model by using a binary bit string or information on adjacent regions, and performs arithmetic coding on the generated binary bit string. The encoding apparatus 100 inserts the generated binary bit string into the bit stream without performing arithmetic encoding.

In this way, by encoding the information exemplarily shown in fig. 2 using a tree structure, a bit stream is generated.

Although fig. 2 to 4 show an example in which numbers 1, 2, and 3 are assigned to 1/2 precision, 1/4 precision, and 1/8 precision, and then encoded, different numbers may be assigned to different precisions by using information on neighboring areas or the occurrence probability of encoded information.

Fig. 5 is a flowchart illustrating an encoding method using a tree structure according to a first embodiment of the present disclosure.

With the encoding method using a tree structure according to the first embodiment of the present disclosure, the encoding apparatus 100 divides a predetermined area having image information to be encoded into a plurality of groups, and generates a node value of each layer up to an uppermost layer by determining a minimum value or a maximum value of the information to be encoded within the grouped area as information on the grouped area (step S510). The encoding device 100 encodes a difference value between the node value of each layer and the node value of the upper layer (step S520). The encoding apparatus 100 encodes additional information including information on the maximum number of layers, information on the size of an area of the lowermost layer, and information on whether the node value of each layer is determined by the minimum value or the maximum value among the node values of the lower layer (step S530).

The encoding apparatus 100 does not necessarily have to perform the step S530, and the step S530 may be optionally performed according to an implementation scheme or necessity. For example, in the case where the encoding apparatus 100 and the decoding apparatus (described below) mutually know one or more of information on the maximum number of layers, information on the size of an area of the lowermost layer, and information on whether the node value of each layer is determined by the minimum value or the maximum value among the node values of the lower layers, the encoding apparatus 100 may encode not the mutually known information but only the mutually unknown information. The encoding apparatus 100 may not encode the additional information if all information has been mutually known in the negotiation and setup process.

In step S530, the encoding apparatus 100 may insert information about the number of regions to be grouped into encoding information instead of information about the size of the region of the lowest layer, and encode the encoding information. This is because if the maximum number of layers is determined, the size of the area of the lowest layer for determining the number of areas to be grouped can also be determined.

In step S520, the encoding apparatus 100 may encode the difference value by using binary encoding, or perform binary arithmetic encoding by encoding the difference value using binary encoding and then changing the probability model. In this case, the probability model may be determined based on node values of adjacent or upper layers, or may be changed differently at each layer.

In step S520, in the case where the node value of each layer is determined by the minimum value among the node values of the lower layers, the encoding apparatus 100 may skip encoding of the node values of the lower layers of the node having the maximum node value. In the case where the node value of each layer is determined by the maximum value among the node values of the lower layers, the encoding apparatus 100 may skip encoding of the node values of the layers below the layer having the smallest node value.

In step S520, the encoding apparatus 100 may change the number assigned to the information to be encoded so as to perform encoding according to the occurrence probability of the information to be encoded.

In step S520, in the case where the encoding apparatus encodes the node value of the uppermost layer, the encoding apparatus 100 may set the node value of the upper layer of the uppermost layer to a predetermined value and encode a difference value between the node value of the uppermost layer and the set predetermined value.

Fig. 6 is a block diagram schematically illustrating a decoding apparatus using a tree structure according to a first embodiment of the present disclosure.

The decoding apparatus 600 using the tree structure according to the first embodiment of the present disclosure may include an additional information decoder 610 and a tree decoder 620.

The additional information decoder 610 decodes the bitstream to reconstruct additional information including information on the maximum number of layers, information on the size of an area of the lowermost layer, and information on whether a node value of each layer is determined by a minimum value or a maximum value among node values of the lower layer. The tree decoder 620 reconstructs a tree structure using the decoded additional information, and reconstructs a difference value between a node value of each layer and a node value of an upper layer thereof or a difference value between a node value of each layer and a value determined by a preset standard. In this case, the additional information decoder 610 reconstructs the additional information by extracting data having the encoded additional information from the header of the bitstream and then decoding the extracted data. The header of the bitstream may be a macroblock header, a slice header, a picture header, or a sequence header. The value determined by the preset criterion may be a value having the highest occurrence probability among the regions decoded so far among the previous regions or the adjacent regions, but is not limited thereto, and may be a value determined by various criteria.

The additional information decoder 610 is not necessarily included in the decoding apparatus 600 and may be optionally included therein according to an implementation scheme or necessity. For example, in the case where the encoding apparatus 100 and the decoding apparatus 600 mutually know information on the maximum number of layers, information on the size of an area of the lowermost layer, and information on whether the node value of each layer is determined by the minimum value or the maximum value among the node values of the lower layer, the encoding apparatus 100 may not encode the additional information, and accordingly, the decoding apparatus 600 may reconstruct the tree structure by using the preset additional information without reconstructing the additional information by decoding the bitstream.

The tree decoder 620 decodes a bitstream by using additional information to reconstruct a difference value between a node value of each layer and a node value of an upper layer or a difference value between a node value of each layer and a value determined by a preset criterion. The tree decoder 620 reconstructs a node value of each layer by adding the reconstructed difference value to a node value of an upper layer. The tree decoder 620 reconstructs a node value of the lowermost layer as information to be decoded. That is, the tree decoder 620 reconstructs the enhanced tree structure by using additional information preset or reconstructed by the additional information decoder 610. The tree decoder 620 decodes the bitstream based on the enhanced tree structure to reconstruct a difference value between a node value of each layer and a node value of an upper layer. The tree decoder 620 reconstructs a node value of each layer by adding the reconstructed difference value to a node value of an upper layer.

In this case, the tree decoder 620 may decode the bitstream by using a plurality of binary decoding methods, such as unary code, truncated unary code, and exponential golomb code, to reconstruct a difference value between the node value of each layer and the node value of the upper layer. In addition, after decoding the bitstream by using various binary decoding methods, such as unary code, truncated unary code, and exponential golomb code, the tree decoder 620 may perform binary arithmetic decoding by determining a probability model of a layer to be decoded based on a node value of an adjacent layer or an upper layer. In addition, the tree decoder 620 may perform arithmetic decoding of the bitstream by differentially changing the probability model of each layer.

In the case where it is identified that the encoding apparatus 100 determines that the minimum value among the node values of the lower layer is the node value of each layer based on the additional information, the tree decoder 620 skips decoding of the node values of the layers below the layer having the maximum node value, assuming that all the node values of the lower layer have the same value. On the other hand, in the case where it is identified based on the additional information that the encoding apparatus 100 determines that the maximum value among the node values of the lower layer is the node value of each layer, the tree decoder 620 skips decoding of the node values of the layers below the layer having the smallest node value, assuming that all the node values of the lower layer have the same value.

The tree decoder 620 may differentially change the number according to the occurrence probability of information to be decoded. That is, the tree decoder 620 may be assigned a small number or a large number according to the occurrence probability of information to be decoded. The occurrence probability of information to be decoded can be calculated by using various methods, such as the occurrence probability of information related to a predetermined adjacent region, or the occurrence probability of information that has been decoded and reconstructed before a region having information to be decoded.

In the case where the tree decoder 620 reconstructs a difference value between the node value of the uppermost layer and the node value of the upper layer thereof, it is assumed that the tree decoder 620 reconstructs only the difference value, having a predetermined value since the upper layer of the uppermost layer does not exist. In this case, the predetermined value may be any one of the following values: a value having the highest occurrence probability among the values of the information on the predetermined adjacent regions, the preset value, the value having the highest occurrence probability, etc., decoded so far.

A process of reconstructing information by decoding a bitstream using a tree structure according to a first embodiment of the present disclosure will be described in detail below with reference to fig. 2 to 4.

The decoding apparatus 600 extracts data having encoded additional information from a picture header, a slice header, or a macroblock header of a bitstream, and reconstructs the additional information by decoding the extracted data. In addition, the decoding apparatus 600 may use preset additional information. The additional information may include information on the maximum number of layers, information on the size of an area of the lowermost layer, and information on whether the node value of each layer is determined by the minimum value or the maximum value among the node values of the lower layer. The decoding apparatus 600 may reconstruct the tree structure as shown in fig. 3 by using information on the maximum layer number and information on the size of the area of the lowest layer among the additional information. In this case, the decoding apparatus 600 may reconstruct the tree structure by using information on the number of areas to be grouped, instead of information on the size of the area of the lowest layer. In addition, the decoding apparatus 600 may reconstruct the tree structure by using both information on the size of the area of the lowest layer and information on the number of areas to be grouped.

If the tree structure as shown in fig. 3 is reconstructed, the decoding apparatus 600 decodes a bitstream in which a difference value between a node value of each layer and a node value of an upper layer is encoded using the reconstructed tree structure, as described above with reference to fig. 4.

Since the decoding apparatus 600 already knows the maximum value of the information to be decoded, the decoding apparatus 600 decodes the binary bit string by using the truncated unary code. In this case, it can be assumed that the numbers of 1/2 precision, 1/4 precision, and 1/8 precision are 1, 2, and 3, respectively. The number of each precision can be changed differently according to the occurrence probability of each precision. If the decoding apparatus 600 performs arithmetic decoding of the binary bit string, the decoding apparatus 600 generates a probability model by using information about adjacent regions or the binary bit string, and generates a binary bit stream by arithmetic decoding of the lower bit stream. The decoding apparatus 600 generates the binary bit string by decoding the bit stream if the decoding apparatus does not perform arithmetic decoding of the binary bit string.

Referring to fig. 4, in the case of the region (0,0), the 0 th layer of the highest layer has no upper layer. Assuming that the node value of the upper layer has 1/2 precision (highest occurrence probability), if the binary bit string 1 is decoded, the difference value between the node value of the uppermost layer and the node value of the upper layer thereof is 0. In the layer 1, if the binary bit string 1 is decoded, a difference value from a node value of an upper layer thereof is 0. In the layer 2, if the binary bit string 1 is decoded, a difference value from a node value of an upper layer thereof is 0. In the layer 3, if the binary bit string 1 is decoded, a difference value from a node value of an upper layer thereof is 0. If the node value of each layer is added to the difference value between the node value of each layer and the node value of the upper layer thereof, the node value of each layer is 1, i.e., 1/2 precision. Therefore, the reconstructed information of the region (0,0) is 1/2 precision.

In the case of the region (0,1), since the layer 0, the layer 1 and the layer 2 have already been decoded in the process of reconstructing information about the region (0,0), additional decoding is not performed on them. In the layer 3, if the binary bit string 01 is decoded, a difference value from a node value of an upper layer thereof is 1. Therefore, the reconstructed information of the region (0,1) is 2, which means 1/4 accuracy.

In the case of the region (2,0), since the layer 0 and the layer 1 have already been decoded in the process of reconstructing information on the region (0,0), additional decoding is not performed on them. In the layer 2, since the node value of the upper layer is 1(1/2 accuracy), it can be known that the difference value from the node value of the upper layer is the maximum value, i.e., 2. Therefore, if the binary bit string 00 is decoded by truncating the unary code, the reconstructed information of the region (2,0) is 1/8 precision.

Likewise, in the case of the region (2,6), since the upper layer of the 2 nd layer is 1/4 th precision, it can be known that the maximum value of the difference is 1. If the binary bitstream 0 is decoded by the truncated unary code, the difference from the upper layer is 1, and the reconstructed information of the region (2,6) is 1/8 precision. In this case, since the maximum value occurs, the node value of the lower layer is not decoded and is determined to 1/8 precision.

In the above example, decoding is performed assuming that numbers 1, 2, and 3 are assigned to 1/2 precision, 1/4 precision, and 1/8 precision, respectively. However, the numbers of the respective precisions can be changed differently by using the information about the adjacent regions or the occurrence probability of the decoded and reconstructed information.

Fig. 7 is a flowchart illustrating a decoding method using a tree structure according to a first embodiment of the present disclosure.

With the decoding method using the tree structure according to the first embodiment of the present disclosure, the decoding apparatus 600 decodes a bitstream to reconstruct additional information (step S710). That is, the decoding apparatus 600 extracts data having encoded additional information from a header of a predetermined coding unit (such as a picture header, a slice header, or a macroblock header) of a bitstream, and reconstructs the additional information by decoding the extracted data. The additional information may include information on the maximum number of layers, information on the size of an area of the lowermost layer, and information on whether the node value of each layer is determined by the minimum value or the maximum value among the node values of the lower layer.

The decoding apparatus 600 does not necessarily perform the step S710, but may optionally perform the step S710 according to an implementation scheme or necessity. For example, in the case where the encoding apparatus 100 and the decoding apparatus 600 mutually negotiate to preset all pieces of information included in the additional information, the encoding apparatus 100 may not encode the additional information, and accordingly, the decoding apparatus 600 may decode the bitstream by using the preset additional information. In the case where only a part of information included in the additional information is set by the prearrangement between the encoding apparatus 100 and the decoding apparatus 600, the encoding apparatus 100 may encode only information that is not known to each other, and the decoding apparatus 600 may decode the bitstream to reconstruct only the information that is not known to each other. The reconstructed information and preset other information may be used for decoding.

The decoding apparatus 600 may decode the bitstream to reconstruct a difference value between the node value of each layer and the node value of the upper layer (step S720). That is, the decoding apparatus 600 reconstructs an enhanced tree structure by using the additional information reconstructed at step S710 or preset additional information, and reconstructs a difference value between a node value of each layer and a node value of an upper layer by decoding a bitstream using the reconstructed enhanced tree structure.

The decoding apparatus 600 reconstructs a node value of each layer by adding the reconstructed difference value to a node value of an upper layer (step S730), and reconstructs a node value of a lowermost layer as information to be decoded (step S740).

In step S720, the decoding apparatus 600 may reconstruct the node value of each layer by decoding the bitstream using the binary decoding method, or may reconstruct the node value of each layer by performing binary arithmetic decoding by decoding the bitstream using the binary decoding method and then changing the probability model. The probability model may be determined based on node values of adjacent or upper layers, or may be changed differently at each layer.

In step S720, the decoding apparatus 600 may change the number assigned to the information to be decoded so as to decode according to the occurrence probability of the information to be decoded.

In step S730, in the case of recognizing that the node value of each layer is determined by the minimum value among the node values of the lower layers, the decoding apparatus 600 may reconstruct all the node values of the layers below the layer having the maximum node value using the maximum value.

In step S730, in the case of recognizing that the node value of each layer is determined by the maximum value among the node values of the lower layer, the decoding apparatus 600 may reconstruct all node values of layers below the layer having the smallest node value using the minimum value.

In step S730, in decoding the node value of the uppermost layer, the decoding apparatus 600 may reconstruct the node value of the uppermost layer by setting the node value of the upper layer of the uppermost layer to a predetermined value.

As described above, according to the first embodiment of the present disclosure, by efficiently encoding image information to be encoded using a tree structure, compression efficiency can be improved.

Fig. 8 is a block diagram schematically illustrating an encoding apparatus using a tree structure according to a second embodiment of the present disclosure.

The encoding apparatus 800 using the tree structure according to the second embodiment of the present disclosure may include a tree encoder 810 and an additional information encoder 820, both for variable-sized blocks.

The tree encoder 810 for variable-sized blocks groups areas having the same information among predetermined areas having image information to be encoded, and encodes one or more of a node value and a flag indicating whether a node of each layer is divided.

The additional information encoder 820 for a variable-size block encodes additional information including information on the maximum number of layers in the tree structure according to the second embodiment and information on the size of an area indicated by each node of the lowest layer. The encoded additional information is included in a header of the bitstream. The header of the bitstream may be a sequence header, a picture header, a slice header, a macroblock header, and the like.

A process of encoding information to be encoded by using the tree structure will be described in detail below with reference to fig. 9 and 10.

Fig. 9 is an exemplary diagram illustrating a tree structure according to a second embodiment of the present disclosure.

Fig. 9A shows an area within a single picture having information to be encoded. In fig. 9A, each region may be a 16 × 16 pixel macroblock. A, B and C indicated within each region represent the information to be encoded in the respective region. Such information may be motion vector accuracy, but is not limited thereto, and may be various information such as partition type information, intra prediction mode, or coefficient information. In the second embodiment, although it is assumed that each region is a 16 × 16 pixel macroblock, the region may be various blocks such as a 64 × 64 pixel block, a 32 × 32 pixel block, a 16 × 16 pixel block, a 16 × 8 pixel block, an 8 × 4 pixel block, a 4 × 8 pixel block, or a 4 × 4 pixel block. In addition, the respective regions may have different sizes.

Fig. 9B illustrates a plurality of sets of regions having the same information among the regions illustrated in fig. 9A. Fig. 9C shows a tree structure of information on the grouped areas shown in fig. 9B. In fig. 9C, the area indicated by the lowest node is a 16 × 16 macroblock, and the maximum number of layers in the tree structure is 4. Accordingly, such additional information is encoded and included in the header of the relevant area.

Fig. 10 is an exemplary diagram illustrating an information encoding result expressed as a tree structure according to a second embodiment of the present disclosure.

If the information of the tree structure shown in fig. 9C is encoded, a final bit stream as shown in fig. 10 can be obtained. Whether a node is divided into lower-layer nodes is encoded by a single bit. For example, a bit value of '1' represents a node into which the current node is divided into lower layers, and a bit value of '0' represents a node into which the current node is not divided into lower layers. In case of the node of the lowermost layer, whether the node is divided into the nodes of the lower layer is not encoded, but the node value of the node of the lowermost layer is encoded.

In fig. 9C, since the node of the 0 th layer is divided into the nodes of the lower layers, the node of the 0 th layer is encoded using the bit value '1'. Since the node value of the first node of the divided layer 1 is a and the first node is not divided into nodes of the lower layer any more, the first node is encoded using a bit value of '0' and the node value a is encoded. Since the second node of the 1 st layer is divided into nodes of lower layers, the second node is encoded with a bit value of '1'. Since the third node of the layer 1 is not divided into nodes of lower layers, the third node is encoded with a bit value of '0' and encodes a node value B. Since the last fourth node of the 1 st layer is divided into nodes of lower layers, the last fourth node is encoded with a bit value of '1'. In the same manner, each node of layer 2 is encoded. In layer 3, the maximum number of layers is designated 4 in the header. Therefore, since it can be known that there is no more node of the lower layer, only each node value is encoded.

Although A, B and C are used for convenience to indicate each node value, each node value may also be represented as a binary bit. In addition, the example of fig. 9 shows only two cases: in the first case, the nodes are divided into lower level nodes; and a second case where the nodes are not divided into lower level nodes. In this embodiment, in the case where the node is divided into the nodes of the lower layer, the node is divided into 4 nodes. Referring to fig. 9, the division of the nodes into 4 nodes of the lower layer means that the area corresponding to the node of the current layer is divided into 4 equal sub-areas. Alternatively, as shown in fig. 11, the nodes may be divided into lower-level nodes in various forms. For example, the nodes may not be divided into the nodes of the lower layer. The nodes may be divided into lower-level nodes in the form of two horizontally divided regions. The nodes may be divided into lower level nodes in the form of two vertically divided regions. The nodes may be divided into lower-level nodes in the form of four regions. In this case, information indicating the four partition types may be transmitted to the decoding apparatus.

If the area of the packet is not large, the encoding apparatus 800 may reduce the number of bits for indicating the existence of the node of the lower layer by encoding a flag indicating that the node of the upper layer is divided into the nodes of the specific layer. For example, in the case where the maximum number of layers is specified to be 4 in the header of the bitstream and information to be encoded is distributed as shown in fig. 12, the regions shown in fig. 12 can be represented by grouping regions having the same information as shown in fig. 13. In this case, the encoding apparatus 800 may encode a flag indicating that the node of the highest layer is divided into nodes of layer 2 or layer 3. Accordingly, the number of flags indicating that the node of the upper layer is divided into the nodes of the lower layer can be reduced, thereby reducing the number of bits.

Fig. 14 is a flowchart illustrating an encoding method using a tree structure according to a second embodiment of the present disclosure.

With the encoding method using the tree structure according to the second embodiment of the present disclosure, the encoding apparatus 800 groups regions having the same information among predetermined regions to be encoded, and encodes one or more of a node value and a flag indicating whether each node of each layer is divided (step S1410), and encodes additional information including information on the maximum number of layers and information on the size of the region indicated by each node of the lowermost layer (step S1420).

At step S1410, if the node is divided, the encoding apparatus 800 may encode a flag indicating the division of the node. That is, the encoding apparatus 800 may determine whether the nodes of each layer are divided. If the nodes are divided, the encoding apparatus 800 may encode only a flag indicating that the corresponding node is divided into nodes of a lower layer, without encoding the corresponding node value.

In step S1410, if the node is not divided, the encoding apparatus 800 may encode a node value of the node and a flag indicating that the node is not divided. That is, the encoding apparatus 800 may determine whether the nodes of each layer are divided. If the node is not divided, the encoding apparatus 800 may encode a node value of the corresponding node and a flag indicating that the corresponding node is not divided into nodes of a lower layer. The term "node value of a node" refers to information possessed by the node. If regions having the same information are grouped into a single node, the same information is a node value.

In step S1410, if the node is the node of the lowermost layer, the encoding apparatus 800 may encode only the node value of the corresponding node. That is, the encoding apparatus 800 may determine whether a node to be encoded is the lowest layer before determining whether the node of each layer is divided. The encoding apparatus 800 may encode only a node value of the corresponding node without encoding a flag indicating whether the corresponding node is divided, if the corresponding node is the lowermost layer.

In step S1420, the encoding apparatus 800 may insert data having the encoded additional information into a header of the bitstream. The header of the bitstream may be a header of various coding units such as a sequence header, a picture header, a slice header, or a macroblock header.

At step S1410, after encoding the flag indicating that the node is divided, the encoding apparatus 800 may encode the flag indicating that the node is directly divided into one or more lower-layer nodes. That is, after encoding the flag indicating whether the node is divided, if the corresponding node is divided into nodes of lower layers, the encoding apparatus may encode the flag indicating that the corresponding node is subdivided into nodes of lower layers, and may also encode the flag indicating that the corresponding node is divided into nodes of lower two or more layers.

Fig. 15 is a block diagram schematically illustrating a decoding apparatus using a tree structure according to a second embodiment of the present disclosure.

The decoding apparatus 1500 using a tree structure according to the second embodiment of the present disclosure may include an additional information decoder 1510 and a tree decoder 1520, both for variable-sized blocks.

The additional information decoder 1510 for the variable-size block decodes a bitstream to reconstruct additional information including information on the maximum number of layers and information on the size of an area indicated by each node of the lowest layer. The tree decoder 1520 for the variable-sized blocks reconstructs a tree structure using the reconstructed additional information. In this case, the additional information decoder 1510 for the variable-size block extracts data having the encoded additional information from the header of the bitstream and decodes the extracted data to reconstruct the additional information. The header of the bitstream may be a macroblock header, a slice header, a picture header, a sequence header, and the like.

However, the additional information decoder 1510 for the variable-sized block is not necessarily included in the decoding apparatus 1500, but may be optionally included according to an implementation scheme or necessity. For example, in a case where the encoding apparatus 800 and the decoding apparatus 1500 mutually negotiate the maximum number of layers and the size of the area indicated by each node of the lowest layer in advance, the encoding apparatus 800 may not encode the additional information. Therefore, the decoding apparatus 1500 may reconstruct the tree structure by using the preset additional information instead of reconstructing the additional information by decoding the bit stream.

The tree decoder 1520 for the variable-size blocks decodes the bitstream based on the additional information to reconstruct the flag indicating whether the node of each layer from the uppermost layer to the lowermost layer is divided, and reconstructs the information by reconstructing the node value of the node of each layer according to the reconstructed flag. That is, the tree decoder 1520 for the variable-size block decodes the bitstream based on the additional information reconstructed by the additional information decoder 1510 for the variable-size block or the preset additional information. The tree decoder 1520 for the variable-sized blocks determines whether nodes of each layer from the highest layer to the lowest layer are divided. If not divided, the tree decoder 1520 for the variable-size blocks reconstructs a tree structure by reconstructing node values of the nodes, and reconstructs information to be decoded based on the reconstructed tree structure.

A description will be provided with reference to fig. 9 and 10 regarding a process of reconstructing information by decoding a bitstream using a tree structure by a decoding apparatus 1500 according to a second embodiment of the present disclosure.

The decoding apparatus 1500 extracts encoded additional information from a macroblock header, a slice header, a picture header, or a sequence header of a bitstream, and decodes the extracted additional information to reconstruct the additional information. The additional information includes information on the maximum number of layers in the tree structure and information on the size of an area indicated by each node of the lowest layer.

The decoding apparatus 1500 extracts a bit string, such as the final bit of fig. 10, from the bitstream. Next, as described above, the decoding apparatus 1500 reconstructs a tree structure based on the reconstructed additional information and the extracted bit string, as schematically shown in fig. 10.

For example, the decoding apparatus 1500 sequentially reads bit values of a bit string of final bits extracted from a bitstream, and reconstructs a flag indicating whether or not a node of each layer from the highest layer to the lowest layer is divided into nodes of lower layers. If the reconstructed flag indicates that the node is not divided into nodes of the lower layer, the decoding apparatus 1500 reads the next bit string and reconstructs the node value of the corresponding node. The reconstructed node value is information to be decoded. In addition, if the reconstructed flag indicates that the node is divided into the nodes of the lower layer, the decoding apparatus 1500 reads the next bit value and reconstructs the flag indicating whether the next node or a next node after the next layer is divided into the nodes of the lower layer. In this way, the decoding apparatus 1500 sequentially reads the bit string and reconstructs information up to the lowest layer. Meanwhile, for the lowest-layer node, the decoding apparatus 1500 does not reconstruct the flag indicating whether the node is divided, and reconstructs only the node value of each node.

In the case where the node is divided into the nodes of the lower layer, the node is divided into 4 nodes as schematically shown in fig. 9. Referring to fig. 9, the division of the nodes into 4 nodes of the lower layer means that the area corresponding to the node of the current layer is divided into 4 equal sub-areas. Alternatively, as shown in fig. 11, the nodes may be divided into lower-level nodes in various forms. For example, the nodes may not be divided into the nodes of the lower layer. The nodes may be divided into lower nodes in the form of two horizontally divided regions, and the nodes may be divided into lower nodes in the form of two vertically divided regions. The nodes may be divided into lower-level nodes in the form of four regions. In this case, information indicating the four partition types is transmitted from the encoding apparatus to the decoding apparatus 1500.

In this way, the decoding apparatus 1500 reconstructs a tree structure as shown in fig. 9C by reconstructing information from the highest layer to the lowest layer, and reconstructs information on the respective areas shown in fig. 9B and 9A based on the reconstructed tree structure.

If the flag reconstructed by extracting data from the bit string of the bitstream and decoding the extracted data indicates that the node of a specific layer is directly divided into nodes of the lower two or more layers, the decoding apparatus 1500 skips decoding of layers between the indicated layers and decodes one or more of a node value of the corresponding node and a flag indicating whether the indicated node of the lower layer is divided.

With regard to the decoding method using the tree structure according to the second embodiment of the present disclosure, the decoding apparatus 1500 decodes a bitstream to reconstruct additional information including information on the maximum number of layers and information on the size of an area indicated by each node of the lowest layer (step S1610). The decoding apparatus 1500 decodes the bit string extracted from the bit stream based on the additional information to reconstruct a flag indicating whether the node of each layer from the uppermost layer to the lowermost layer is divided, and reconstructs information by reconstructing the node value of the node of each layer according to the reconstructed flag (step S1620).

In step S1620, if the flag indicates that the node is not divided into nodes of the lower layer, the decoding apparatus 150 may reconstruct a node value of the node. That is, the decoding apparatus 1500 reconstructs a flag indicating whether the node of each layer is divided, decodes a next node if the reconstructed flag indicates that the node of the corresponding node is divided into the nodes of the lower layer, and reconstructs only the node value of the corresponding node when the reconstructed flag indicates that the node of the corresponding node is not divided into the nodes of the lower layer.

In the case where the node is divided into the nodes of the lower layer, the node is divided into 4 nodes as exemplarily shown in fig. 9. Alternatively, as shown in fig. 11, the nodes may be divided into lower-level nodes in various forms. For example, the nodes may not be divided into the nodes of the lower layer. The nodes may be divided into lower-level nodes in the form of two horizontally divided regions. The nodes may be divided into lower level nodes in the form of two vertically divided regions. The nodes may be divided into lower-level nodes in the form of four regions. In this case, information indicating four partition types is transmitted to the decoding apparatus 1500.

In step S1620, the decoding apparatus 1500 may reconstruct only the node values of the respective nodes of the lowermost layer. That is, in reconstructing a flag indicating whether a node of each layer is divided and/or a node value of the node, the decoding apparatus 1500 determines in advance whether a node to be decoded is included in the lowermost layer. If the node to be decoded is included in the lowermost layer, the decoding apparatus 1500 reconstructs only the node value of the corresponding node, without reconstructing the flag indicating whether the corresponding node is divided.

In the encoding/decoding method using a tree structure according to an embodiment of the present disclosure, information to be encoded and decoded is not limited to data set forth in the embodiment, but may be applied to encoding and decoding of various information set forth below.

The information to be encoded may include information related to an image signal or various information used to encode the image signal, such as macroblock size and macroblock type information, macroblock partition information indicating the size and type of subblocks used for prediction and transformation, intra prediction information, a motion vector prediction direction, an optimal motion vector prediction candidate, an optimal interpolation filter for an area of an arbitrary size, whether an image enhancement filter is used, a reference picture index, a quantization matrix index, optimal motion vector precision and transformation size information, image pixel information, encoding block information, or coefficient information indicating whether a transform coefficient other than zero exists within a predetermined block.

In an embodiment of the present disclosure, a macroblock has a variable size as a default unit for video encoding and decoding. According to an embodiment of the present disclosure, the macroblock size information may be encoded by using a tree structure. To this end, the encoding apparatus according to an embodiment of the present disclosure generates information on the maximum size and the minimum size of a macroblock, information on the maximum number of layers constituting a tree, and a macroblock division partition flag, and transmits the generated information to the decoding apparatus. Information on the maximum size and the minimum size of a macroblock and information on the maximum number of layers constituting a tree may be included in a bitstream as header information of a sequence, a group of pictures (GOP), a picture, a slice, and the like.

As shown in fig. 9 or 11, the macroblock division flag may be encoded by using a tree structure and may be included in a header of a coding unit. In other words, the information encoded and decoded using the tree structure according to the embodiment of the present disclosure is the above-described macroblock division flag.

The maximum size and the minimum size of the macroblock may be set with the horizontal size and the vertical size separately determined to allow the use of macroblocks of arbitrary sizes. In addition, the maximum size and the minimum size of the macroblock to be encoded may be allocated with an actual size, or a magnification rate may be transmitted to instruct to enlarge or reduce a predetermined size by a certain factor. To encode the magnification ratio for generating the maximum macroblock size by multiplying a predetermined size by a certain multiple (selected as 16), log is encoded₂(selected MB size/16). For example, if the macroblock size is 16 × 16, 0 is encoded. If the macroblock size is 32 × 32, 1 is encoded. In addition, the ratio of the horizontal size and the vertical size may be separately encoded.

Alternatively, after the maximum macroblock size value is encoded by the above-described method, the maximum macroblock size is encoded by using a log indicating a ratio of the maximum macroblock size to the minimum macroblock size₂(maximum macroblock size/minimum macroblock size) value, the minimum size value of the macroblock may be encoded. In contrast, after encoding the minimum block size by the above-described method, by using the log₂(maximum macroblock size/minimum macroblock size) value, the maximum macroblock size value may be encoded.

In addition, according to an embodiment of the present disclosure, macroblock partition information may be encoded and decoded using a tree structure according to the present disclosure. The macroblock partition information may include information on the maximum size and minimum size of subblocks for prediction and/or transformation, information on the maximum number of layers constituting a tree, and a macroblock partition division flag, as information on the size and/or type of subblocks (that is, macroblock partitions) for prediction and/or transformation. An encoding apparatus according to an embodiment of the present disclosure transmits macroblock partition information to a decoding apparatus.

The maximum size and the minimum size of subblocks for prediction and/or transformation may be determined in units of an entire picture sequence, GOP, picture or slice. Information on the maximum and minimum sizes of subblocks used for prediction and/or transformation and information on the maximum number of layers constituting a tree may be included in a bitstream as header information of a sequence, GOP, picture or slice.

On the other hand, by using the tree structure according to the embodiment of the present disclosure, the macroblock partition division flag among the macroblock partition information may be encoded. The macroblock partition division flag may be included in a header of a macroblock corresponding to a coding unit or a header of a macroblock partition.

In addition, for the subblock size for prediction and/or transform, that is, prediction and/or transform size information, the horizontal size and the vertical size and/or the transform size of the maximum size and the minimum prediction may be separately set. Thus, predictions and/or transforms of arbitrary size may be used. In addition, the maximum size and the minimum size of the available prediction and/or transformation may be allocated with actual sizes, or a magnification rate may be transmitted for instructing to enlarge or reduce a predetermined size by a certain factor. To encode the magnification ratio for generating the maximum prediction and/or transform size by multiplying a predetermined size by a certain multiple (which is selected as 4), the log is encoded₂(selected prediction and/or transform/4). For example, if the prediction and/or transform size is 4 × 4, 0 is encoded. If the prediction and/or transform sizes are 8 x 8, then coding1. In addition, the ratio of the horizontal size and the vertical size may be separately encoded.

Alternatively, after encoding the value of the maximum prediction and/or transform size by the above-described method, by using a log indicating a ratio of the maximum prediction and/or transform size to the minimum prediction and/or transform size₂(maximum prediction and/or transform size/minimum prediction and/or transform size) values, the minimum prediction and/or transform size values may be encoded. Instead, after encoding the value of the minimum prediction and/or transform size by the above method, by using log₂(maximum prediction and/or transform size/minimum prediction and/or transform size) values, which may be encoded.

The coding block information indicating whether or not there is a non-zero transform coefficient within a predetermined block may be a 1-bit flag indicating whether or not there is a non-zero transform coefficient within a sub-block divided for prediction or transform. In this case, different flags may be encoded for the luminance component (Y) block and the chrominance component (U, V) block. For three blocks of luminance and chrominance components (Y, U, V), the presence or absence of non-zero transform coefficients may be indicated by a single flag.

Alternatively, after encoding a flag indicating whether or not non-zero transform coefficients exist within all blocks of the three components (Y, U, V), only a transform type may be encoded when non-zero transform coefficients exist, and then flags indicating whether or not non-zero transform coefficients exist within sub-blocks of respective chrominance components may be encoded, respectively.

According to the above-described embodiments of the present disclosure, the tree encoder generates the tree structure of the image information to be encoded by grouping the regions having the same information among the regions having the image information to be encoded. However, this is only one example of generating a tree structure, and it is obvious to those skilled in the art that a tree structure may be generated in various ways. For example, by repeatedly dividing a reference block (e.g., a maximum-sized macroblock) into smaller-sized subblocks, the size of the macroblock that is being a coding/decoding unit or the size of a subblock used for prediction or transformation may be determined. In other words, macroblocks or subblocks of various sizes for prediction or transform may be included in a single picture by dividing a reference block into a plurality of first subblocks, subdividing the first subblocks into smaller sized second subblocks, or not subdividing the first subblocks. In this case, whether to divide the block into subblocks may be indicated by a division flag. In this way, the macroblock size information (i.e., macroblock division flag) or the subblock size information for prediction or transform (i.e., macroblock partition division flag) has a tree structure as shown in fig. 9B or 9C.

Although exemplary embodiments of the present disclosure have been described for illustrative purposes, those skilled in the art will appreciate that various modifications, additions and substitutions are possible, without departing from the essential characteristics of the disclosure. Accordingly, the exemplary aspects of the disclosure are not described for limiting purposes. Accordingly, the scope of the present disclosure is not defined by the above aspects but by the claims and the equivalents thereof.

Industrial applicability

As described above, the present disclosure is very useful for application in video compression processing for encoding and decoding images, and can improve encoding efficiency by using a tree structure in encoding of various kinds of image information and decoding of resulting encoded data, and thus improve video compression efficiency.

Cross Reference to Related Applications

Where appropriate, the present application claims priority in accordance with the 35U.S. C § 119(a) to patent application No.10-2009-0122500, filed in Korea at 12, 10, 2009, and patent application No.10-2010-0126315, filed in Korea at 12, 10, 2010, the entire contents of which are incorporated herein by reference. In addition, the non-provisional application claims priority in countries other than the united states for the same reason based on korean patent application, the entire contents of which are incorporated herein by reference.

Claims

1. A decoding method for reconstructing image information divided in a tree structure from a bitstream, the decoding method comprising:

decoding the bitstream to reconstruct additional information, the additional information including information on a maximum number of layers of the tree structure and information on a block size of a lowest layer of the tree structure; and

reconstructing a flag indicating whether a node of each layer is divided or not based on the additional information including information on the maximum number of layers and information on a block size of the lowest layer, and reconstructing the image information of a block corresponding to a node that is not further divided according to the reconstructed flag,

wherein the flag indicating whether the node of the lowest layer is divided or not is not included in the bitstream,

wherein the additional information is included in a sequence header.

2. The decoding method of claim 1, wherein if the node is divided into nodes of a lower layer, the block corresponding to the node is divided into four sub-blocks having equal sizes.

3. The decoding method of claim 1, wherein the image information comprises transform coefficient information of the block or information indicating whether a non-zero transform coefficient is present within the block.

4. The decoding method of claim 1, wherein the block size is a size of a transform.

5. The decoding method of claim 1, wherein the image information comprises prediction information of the block.