KR19980035968A - Quadtree Coding Method - Google Patents

Abstract

The present invention relates to a quadtree coding method. In particular, an efficient coding scheme is applied by applying an adaptive quantization technique that allocates a high bit to a level at which the most leaf is generated by examining each level of a tree during tree information encoding. The object of the present invention is to obtain a uniformity check function for each region of an image, and to divide the quadtree into a minimum tree only until the minimum region is obtained. A second step of checking the number of leaves of each level of the quadtree divided by the first step and allocating fixed bits to each level; And a third process of adaptively re-allocating and quantizing bits according to the number of leaves of each level checked by the second process, and then transmitting or storing the bits.

Description

Quadtree Encoding Method

The present invention relates to a quadtree encoding method. In particular, quadtree encoding enables high quality video encoding by increasing quadtree-level quantization bits in which a large number of leaves are generated when quadtree information is encoded. It is about a method.

In general, encoding by quadtree is a method of encoding a small amount of data in order to store or transmit a digital image having a brightness value. The average value of all brightness values, that is, a uniformity check function, is obtained for a screen of an input frame. Next, if this value is above a certain threshold, the screen is divided into predetermined regions, and the uniformity check function is obtained for each divided region, and this value is compared with the fixed threshold to divide the region only for the region above the threshold. This process is to encode each by iteratively region-dividing until reaching the minimum division (usually 2 × 2).

The tree generated during this process is encoded with tree information for each region by allocating 1 for a region to be divided, that is, a node, and 0 for a node that is not to be divided, that is, a leaf.

In addition, the brightness information of each divided region must also be encoded. The average of the brightness values of each region is quantized by a predetermined bit, so that the tree information of each region and the brightness value information thereof are encoded and transmitted to the recording medium. Will be saved.

1 is a flowchart illustrating a general quadtree encoding method, which will be described below.

First, the threshold T for dividing the region is determined by the allowable bit rate.

In other words, if the threshold value T is large, the allowable bit rate is relatively small, but since the number of bits that can express the information of the brightness value is reduced by that much, the image quality at the time of restoration is degraded, while the threshold value T is increased. When set low, the bit rate is relatively high, resulting in excellent image quality.

However, when the threshold value T is set low, the number of bits increases so that a large amount of data is transmitted during transmission, thereby increasing the transmission time, and when storing on a recording medium, the storage space should increase proportionally.

Therefore, in consideration of this point, it is preferable to set an optimal threshold value (ST100).

After the threshold value T is set by the step 100 (ST100), the uniformity check function should be set, which can be set by the following equation [1] (ST110).

[Equation 1]

Where N is the number of pixels constituting one region,

I (x, y) is the brightness value of each pixel

mean is an average value of brightness values of each pixel of an area.

In other words, the difference between the brightness value of each pixel and the average value of the brightness value of one region (initially one frame) is obtained, and its absolute value is obtained. The value divided by the total number of pixels constituting one region is used as the uniformity check function. Done.

When the uniformity test function is obtained by the step 110 (ST110), the predetermined threshold T and the uniformity test function are compared at the step 120 (ST120). If it is determined that the function is greater than the fixed threshold T, 1 is allocated to the node, and if it is not large, the function is allocated to the node, i.e., 0, to be divided into 4 nodes (ST120 to ST140).

This means that if the average brightness value of the screen of one frame is more than the fixed threshold T, it is determined that the brightness value of the screen is non-uniform, that is, it contains specific information (background, object, etc.) in any part of the screen. If it is less than the fixed threshold T, it is determined that the brightness value is uniform.

Therefore, if the uniformity check function of the initial one frame is larger than the fixed threshold T, it is divided into 4 regions, whereas if the fixed threshold T is larger than the uniformity check function, the region is divided. Instead of dividing, the uniformity check function for one frame, that is, only the average of brightness values is immediately quantized and transmitted or stored (ST140 and ST170).

However, when the area is divided by step 130 (ST130), it is determined in step 150 (ST150) whether the divided area reaches a minimum area, that is, an area of 2x2, This is to prevent deterioration of image quality during restoration.

Therefore, if the minimum area has not yet been reached, the uniformity test function of each of the four initially divided areas is obtained and set by Equation [1], and then the process is performed again from the step 120 (ST120).

In step 120 (ST120), the uniformity check function of each region divided by 4 by step 160 (ST160) is compared with a predetermined threshold T, and the node having a higher uniformity check function (node allocated to 1). The region for the leaf is divided again, and the region for the leaf whose fixed threshold T is larger (node assigned to 0) is not divided.

Subsequently, it is determined again in step 150 (ST150) whether the divided area reaches the minimum area again, and if the minimum area is not reached again, the process from step 120 (ST120) to step 170 (ST170) is repeated repeatedly. The area division is performed until the uniformity test function reaches the minimum area for the area larger than the fixed threshold T.

If the region division reaches the minimum region, in step 170 (ST170), the uniformity check function (that is, the average of the brightness values of each region) for each segmented or undivided region is quantized and encoded into a predetermined bit to transmit the data through the communication line. It will be transmitted or recorded on the recording medium.

However, in such a quadtree splitting method, since the average value of each leaf is obtained and quantized by a fixed number of bits, the number of quantization bits is fixed even when a large number of leaves appear during tree information encoding. There is this.

Therefore, in view of such a problem, the present invention performs efficient encoding by applying an adaptive quantization technique that examines each level of a tree and assigns a high bit to the level at which the most leaf occurs when tree information is encoded. The purpose is.

1 is a flowchart illustrating a general quadtree encoding method.

2 is a block diagram showing a quadtree encoding apparatus of the present invention.

3 is a flowchart illustrating a quadtree encoding method of the present invention.

4A illustrates a quadtree partitioning process according to the present invention.

4B is a diagram illustrating a region division state by a divided quadtree.

Explanation of symbols for the main parts of the drawings

100: uniformity test function setting unit 110: determination unit

120: region division unit 130: bit allocation unit

140: encoder 150: transmitter

A quadtree encoding method of the present invention for achieving the above object comprises: a first method of obtaining a uniformity check function for each region of an image and dividing the quadtree until only a node having a non-uniform brightness value reaches a minimum region; process; A second step of checking the number of leaves of each level of the quadtree divided by the first step and allocating fixed bits to each level; And a third process of adaptively re-allocating and quantizing bits according to the number of leaves of each level checked by the second process and then transmitting or storing the bits.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings.

First, the initial uniformity check function for a frame is set in the same manner as the conventional one by the uniformity check function setting unit 100 (ST200, 210), and the uniformity check function thus set is determined by the determination unit 110. This is compared with the set threshold T (ST220).

If it is determined that the uniformity test function is greater than or equal to the threshold T initially set by the determination unit 110, the region dividing unit 120 assigns 1 to the corresponding node as shown in FIG. 4A and is not large. If it is determined that 0 is allocated to the corresponding node, an area of an initial frame is divided into 4 areas as illustrated in FIG. 4B (ST220 to ST230).

Thereafter, the area dividing unit 120 determines whether the divided area reaches a predetermined minimum size (usually 2 × 2) (ST250). If the area is not reached, the uniformity checking function setting unit 100 is again performed. ) And the determination unit 110 repeats the above process to form a quadtree.

If the division result of such an area is represented in a bitstream, it can be expressed as an example as follows.

1 1010 0000 1000 0010 (0000)

In this case, the bit 0000 in the last parenthesis may be omitted at the lowest level.

This is because the lowest level bit is 0000 unconditionally.

As a result of quadtree dividing the bitstream, as shown in FIG. 4A, the bitstream is composed of four levels.

In addition, 4b is a diagram showing the image of one frame is divided according to the brightness value by the quadtree configured as described above.

The bit allocator 130 checks the number of nodes allocated to 0 of the quadtree, that is, the number of leaves and allocates fixed bits (ST270,280). In this case, the total number of leaves is 16, and the tree information is 5 bits. If we quantize, we need a total of 80 bits (16 × 5).

However, bit allocation in the present invention assigns different bits to each level by the following procedure.

If you count the leaves at each level in the quadtree,

Level 1: 2,

Level 2: 7,

Level 3: 3,

Level 4: There are four.

It can be seen that level 2 is the level with the most leaves.

Therefore, the highest bit number is allocated for level 2, and if the number of bits to be allocated to the level having the most leaf is 5, the bits allocated to each level are as follows.

Level 1: 2/7 × 5 = 1 bit to 2 bits

Level 2: 7/7 × 5 = 5 bits

Level 3: 3/7 × 5 = 2 bits to 3 bits

Level 4: 4/7 × 5 = 2 bits to 3 bits

In Level 1, since it has 7/2 leaf counts (2) as compared to Level 2, which has the largest number of leaves, 5 bits are allocated and 1 or 2 bits are allocated.

Level 2 allocates 5 bits as it is because it has the largest number of leaves. Level 3 allocates 2 to 3 bits because it has 3/7 leaves (3) as compared to level 2.

Finally, at level 4, the number of leaves is 4/7 (4), so this also allocates 2 to 3 bits as in level 3.

In this way, a general rule can be established as shown in Equation [1] regarding how to allocate bits.

[Equation 1]

(Number of zeros in the level / Number of zeros in the level with the highest number of zeros)

× (number of bits assigned to the level with the most leaves)

This is the number of bits allocated for one level.

Thereby, bits for quantizing the brightness value for each level can be allocated, and the number of bits available for quantizing the brightness value for the entire quadtree level can be defined by the following equation [3].

[Equation 3]

Therefore, according to an example of the present invention, the total number of bits required to quantize the brightness value for the level of the entire quadtree has only 10 bits or a maximum of 13 bits.

This reduces the number of bits that can be quantized significantly compared to the conventional 80 bits.

The encoder 140 quantizes and encodes the allocated bits by this method, adds tree information thereto, and the transmitter 150 receives the output of the quantizer 140 and transmits the output to the receiver through a communication line. Or stored in various recording media.

In addition, at the receiving end or in the reconstruction process, the encoded data transmitted or recorded is received to reconstruct by displaying the brightness value of each area at a corresponding position on the screen with reference to the tree information.

As described in detail above, the quadtree coding method according to the present invention quantizes a brightness value by applying an adaptive quantization technique that examines each level of a tree and assigns a high bit to the level at which the most leaf occurs when tree information is encoded. By significantly reducing the number of bits to be transmitted, the amount of data that can be transmitted is reduced, and the storage space can be efficiently saved even when the data is stored through the recording medium. By allocating more bits to enable high quality image reconstruction at the time of reconstruction, consequently, an efficient encoding can be performed.

Claims (4)

Obtaining a uniformity check function of each region of the image and dividing the quadtree until only nodes of regions having non-uniform brightness values reach a minimum region; A second step of checking the number of leaves of each level of the quadtree divided by the first step and allocating fixed bits to each level; And a third process of adaptively re-allocating and quantizing bits according to the number of leaves of each level checked by the second process, and then transmitting or storing the bits. The bit number allocated to each level of the quadtree of the third process is determined by dividing the number of leafs of the level having the largest number of leaves by the number of leafs of the corresponding level, and then setting this value to the level having the most leaf. Quadtree encoding method characterized in that the value multiplied by the number of bits to be allocated. The quadtree encoding method according to claim 2, wherein the number of bits to be allocated to the level having the largest leaf is a preset value. The number of leaves according to claim 1, wherein the total number of bits available for quantizing the brightness value for the entire quadtree level is multiplied by the number of leaves at that level times the number of bits to assign to the level with the most leaves. Quadtree coding method characterized in that the sum of the number of leaves of the highest level, divided by all.