KR100561391B1 - Zerotree coding apparatus and method - Google Patents

Abstract

The present invention relates to a zero-tree encoding apparatus, which compares a reference threshold with a wavelet coefficient and generates predetermined category information from a level of a child correspondence relationship to a level of a parent correspondence relationship using information of a previous level. Threshold comparison unit; A zero tree map storing the predetermined category information; And a zero tree generating unit generating a zero tree using a category capable of generating a zero tree among predetermined categories stored in the zero tree map.

According to the present invention, the operation is the same in all the bands, thus simplifying the construction of the control logic. Therefore, it is very easy to implement in hardware because it has high speed and simple control structure.

Description

Zerotree coding apparatus and method

1 is an exploded view of a wavelet for an image.

2A shows the "Lena" image.

2B shows the "Lena" image resolved by wavelet exploded view.

3 shows the parent-child correspondence of wavelet coefficients.

4 is a flowchart illustrating a zero tree encoding method according to the present invention.

5 shows a zero tree encoding apparatus according to the present invention.

6 illustrates an embodiment of a zero tree encoding method.

The present invention relates to a still picture compression method, and more particularly, to a method of quantizing coefficients of a wavelet domain using a zero tree coding method.

The method of using the wavelet transform as a method of compressing still images has been widely used due to the superior image quality. Mainly, the coefficients of the wavelet domain are quantized and compressed. As one of the quantization methods, a zero tree coding method proposed by Sappiro is widely used. However, Sapporo's zero tree coding method requires a lot of coding time and is inefficient because it reads the same wavelet region repeatedly. Therefore, a new method is proposed here.

Wavelet transform is also adopted in MPEG4, and many applications are expected due to its excellent image quality.

와 방향성, O(O=LL,LH,HL,HH)로 표현할 수 있다. 즉, 변환 단계 S에서 O의 방향성을 갖는 임의의 좌표 (i,j)에서의 웨이브릿 계수를 W_S,0(i,j)로 표현할 수 있다. Wavelet transform for the image can be implemented by extending the structure of the filter bank for the one-dimensional signal as shown in FIG. In FIG. 1, LL ′ represents a partial image of a low frequency band having a lower resolution than the original image because the LL ′ passes through a low pass filter in the horizontal and vertical directions. LH, HL, and HH are partial images of a high frequency band having edge components in horizontal, vertical, and diagonal directions, respectively. The resolved image can be fully synthesized with low and high pass filters for synthesis. The wavelet transformed partial image may include a conversion step indicating a resolution;

And directionality, O (O = LL, LH, HL, HH). That is, the wavelet coefficient at any coordinate (i, j) having the directionality of O in the transformation step S can be expressed as W _{S, 0} (i, j).

FIG. 2A illustrates the "Lena" image, and FIG. 2B illustrates the conversion of the "Lena" image in three steps (S = 3`).

As shown in FIG. 2B, the image of the low frequency band has a shape similar to that of the original image of FIG. 2A. An image of a high frequency band appears as an edge having a direction, and has a similar shape for each frequency band. By using this property, the coefficients in the wavelet transform region can be set to correspondence as shown in FIG.

3 shows the parent-child correspondence of wavelet coefficients.

In FIG. 3, it can be seen that each region has a parent-child relationship. One coefficient of the low frequency region S = 3, O = LL has a son-child relationship with the coefficient of the high frequency band S = 3, O = LH, HL, HH of the same resolution step. In addition, all three coefficients have son-child relationships with four coefficients in two stages. The coefficients W _{3, LL in the} low frequency region have a parent-child relationship with three coefficients of the high frequency band having different directionalities in the same step. The coefficient of the high frequency band has a parent-child relationship with four coefficients having the same directionality as the high frequency coefficient one step below. This parent-child correspondence is useful for various fields including image compression.

The coefficients of the wavelet domain have parent-child relationships between the high level coefficients and the low level coefficients.

The zero tree searcher requires a wavelet converter as a preprocess. Since the zero tree search targets the wavelet coefficients, the coefficient of the wavelet domain is obtained from the still image using the wavelet converter, and then the zero tree searcher is used.

The zerotree searcher uses the parent-child correspondence of wavelet coefficients. In FIG. 3, when the coefficients of level 3 are smaller than the predetermined threshold, there is a high probability that the coefficients of level 2 and level 1 are smaller than the threshold. In this case, compression is performed by compressing and transmitting all coefficients constituting the zero tree into a symbol called zero tree.

As shown in FIG. 3, the sizes of the coefficients having the child correspondence have sizes of x4, x16, ... as compared to the coefficients having the parent correspondence. In order to determine whether one coefficient constitutes a zero tree, it is necessary to search whether all coefficients having child correspondences are smaller than a predetermined threshold. The coefficients with the child correspondence are read repeatedly until the zero tree search is completed. Therefore, as the low level zero tree is searched, the bandwidth and coding time increase exponentially. Since the low level wavelet coefficients store detailed information of the image, the low level wavelet coefficients must be repeatedly read in order to send detailed image information.

The technical problem to be achieved by the present invention is to zero the detailed information and coding time of the image proportionately, reduce the bandwidth requirements, and reduce the external memory usage by using the internal memory using a zero tree map to facilitate low power An apparatus and method for tree encoding are provided.

The zero-tree encoding apparatus according to the present invention for solving the above technical problem compares a reference threshold and a wavelet coefficient and uses the information of the previous level to obtain predetermined category information from the level of the child correspondence relation to the level of the parent correspondence relation. A threshold comparison unit to generate; A zero tree map storing the predetermined category information; And a zero tree generating unit generating a zero tree using a category capable of generating a zero tree among predetermined categories stored in the zero tree map.

In addition, the threshold comparison unit preferably compares the first reference threshold value with the wavelet coefficient by setting a value not smaller than 1/2 of the maximum value of the wavelet coefficient.

In addition, the first reference threshold is preferably determined to be a multiplier of two.

The zero tree map may be divided into a first category when the wavelet coefficient is smaller than the reference threshold and a coefficient of a previous level is larger than the reference threshold, and the second category when the wavelet coefficient is larger than the reference threshold. Preferably, the predetermined category information is divided into a third category, wherein the wavelet coefficient is smaller than the reference threshold and the coefficient of the previous level is smaller than the reference threshold.

In addition, it is preferable that the zero tree map has two bits of information of the zero tree map.

According to another aspect of the present invention, there is provided a method for generating a zero tree by using a parent-child correspondence of wavelet coefficients generated by wavelet transforming an input image. Comparing a reference threshold and a wavelet coefficient, and also comparing the reference threshold and coefficients of a previous level; (b) From step (a), if the wavelet coefficient is smaller than the reference threshold and the coefficient of the previous level is larger than the reference threshold, the wavelet coefficient is divided into a first category, and if the wavelet coefficient is larger than the reference threshold, Separating into two categories, wherein the wavelet coefficient is smaller than the reference threshold and the coefficient of the previous level is also smaller than the third threshold; And (c) constructing a zero tree only in the case of the third category, without forming a zero tree in the case of the first category and the second category in the step (b). It features.

In addition, the reference threshold is preferably set to a value no smaller than 1/2 of the maximum value of the wavelet coefficient.

In addition, in the zero tree generation method, when the generation of the zero tree for all coefficients is completed, the reference tree is reduced to 1/2 to repeat the zero tree generation process until the predetermined bit rate is satisfied.

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

In the zero-tree coding method according to the present invention, if a wavelet coefficient of a certain frequency band is not important for an arbitrary threshold value, it is very unlikely that the coefficient of a higher frequency band having a corresponding relationship in this band is also very important. depart.

That is, since the coefficient lower than the threshold value from the low frequency band to the high frequency band can be configured as a single sample value called zero tree, the number of position information to be transmitted can be effectively reduced. In addition, the zero-tree coding method can satisfy a desired bit amount, and is a very advantageous method for gradual transmission because information is transmitted sequentially from high energy information.

The zero tree coding method is as follows.

1) Wavelet transform the input image. As shown in FIG. 3, the wavelet transformed image has a parent-child relationship for each band.

2) The initial threshold, T ₀ , is determined so that the following conditions are met. In other words,

That is, a value not smaller than 1/2 'of the maximum value of the wavelet coefficient is determined as the first threshold. In general, the initial threshold is determined to be a multiplier of two.

3) A sample is generated by comparing each coefficient with a threshold as shown in FIG. After generating the sample for the total coefficients, lower the threshold by half as follows and continue with the same method.

T _i = T _i-1 / 2 (i = 1, 2,…)

This method is called successive-approximation quantization (SAQ). This process continues until the specified bit rate is met.

Four samples are produced in the process of 3). Positive siginificant (POS), negative significant (NEG), isolated zero (IZ), and zerotree root (ZTR). POS is assigned when the count is greater than the threshold and positive, and NEG is a sample assigned when the count is negative. ZTR is a sample value that is assigned when the coefficient is smaller than the threshold and all coefficients that have a child relationship to the coefficient are also smaller than the threshold. Due to this ZTR, a lot of compression effects can be obtained. If the coefficient is smaller than the threshold but any coefficient having a child relationship is larger than the threshold, the IZ is allocated.

The whole process of zero-tree coding is divided into two phases: dominant pass and subordinate pass.

The main process produces the four samples mentioned above, and the sub-process increases the precision of the value once more for POS and NEG samples. All symbols thus produced are arithmetic encoded and the encoding process is repeated until a predetermined bit rate is satisfied.

Since the zero tree coding method uses one threshold for all wavelet coefficients, it does not reflect the frequency and local characteristics of the image. Therefore, it is desirable to use an adaptive threshold value for each region of the image to reflect the characteristics of each image.

5 relates to a zero tree generating apparatus according to the present invention, and includes a threshold comparison unit 510, a zero tree map 520, and a zero tree generation unit 530.

The threshold comparison unit 510 compares a given threshold with a wavelet coefficient and divides the information into three categories using information of a previous level.

The first is greater than the threshold (Th).

The second is smaller than the threshold Th, and the coefficient of the previous level corresponds to the first category.

The third is smaller than the threshold Th, and the coefficient of the previous level also belongs to the third category.

The first piece of information is unlikely to construct a zero tree, since the wavelet coefficient is larger than the threshold (POS, NEG).

The second information indicates that the wavelet coefficient is smaller than the threshold and the coefficient of the previous level is larger than the threshold. In the parent-child relationship, the parental response coefficient is smaller than the threshold, but the child response coefficient is larger than the threshold (IZ). Therefore, there is no possibility of constructing a zero tree.

In the third information, since the wavelet coefficient is smaller than the threshold and the coefficient of the previous level also corresponds to the third category, the zero tree is configured in the parent-child correspondence (ZTR). Therefore, the zero tree is constructed at the current level.

Accordingly, the threshold comparison unit 510 stores the above three category information in the direction of the parent correspondence from the level of the child correspondence and stores the information in the zero tree map 520.

The zero tree map 520 stores category information generated from the threshold comparator 510 and is referred to to generate information at the same time.

The zero tree generator 530 generates a zero tree with reference to the zero tree map 520. The coefficients in the third category at the top level constitute a zero tree. Therefore, the zero tree is generated and transmitted, and the zero tree is indicated on the low level zero tree map 520. Information in the first and second categories is transmitted without compression because it does not form a zero tree.

When zero tree generation of the first level is completed, it proceeds to the second level. At this time, information about coefficients which are found to belong to zero tree at the first level is recorded in the zero tree map. Therefore, there are a total of four category information.

The first is larger than the threshold.

The second is smaller than the threshold, and the coefficient of the previous level corresponds to the first category.

The third is smaller than the threshold, and coefficients from the previous level also fall in the third category.

Fourth belongs to zero tree. (The coefficients of the child correspondence of the coefficients in the third category at the previous level.)

The coefficients in the first, second, and third categories can be treated the same as the first level, and the fourth coefficients do not need to be transmitted because they belong to the zero tree, and only zero in the coefficient zero tree map 520 of the child correspondence relationship. This indicates that the tree does not need to be transmitted at lower levels.

Referring to FIG. 6, zero tree coding will be described.

When performing the zero-tree coding, if the coefficient in the low band is read and is smaller than the predetermined threshold, it is necessary to sequentially read the coefficients having the same position to determine whether the coefficient is smaller than the threshold.

In FIG. 6, if the coefficient of HL0 is smaller than the threshold, both coefficients of HL1 and HL2 should be checked to see if it is a zero tree. Implementing this in hardware results in DRAM read operations. After the encoding of the HL0 band is finished, the LH0 band is encoded, and the HH0 band is encoded. When the encoding of the 0 bands is completed, the HL1 band is encoded. In the HL1 band, a read operation of the DRAM is performed to encode the HL0 band. It is read back in order to perform encoding of the HL1 band. The HL2 band will be read again as well. The higher the band, the greater the number of duplicate reads and the larger the range, so there is more DRAM access. Since zero-tree coding is only for simple comparison, the limitation of operating speed is DRAM access. Therefore, reducing DRAM access is a way to increase speed. Therefore, we propose a method to reduce memory access.

In the zero-tree method according to the present invention, encoding is started in an upper band. In the upper band, a symbol is generated by comparing a threshold with a coefficient. When encoding in the lower band, the symbol is generated by referring to the symbol of the upper band. If the symbol in the HL2 band was ZTR, then if the coefficient of HL1 is less than the threshold, it is naturally ZTR. Even if the tree is zero tree in the HL2 band, if the coefficient of HL1 is larger than the threshold, it becomes a significant symbol. If it is not the zero tree R in the HL2 band, even if the coefficient is smaller than the threshold value in the HL1 band, it is not ZTR and becomes IZ (Isolate Zero).

When encoding HL0, the coefficient refers to the symbol of HL1. If the symbol of HL1 was ZTR when the coefficient of HL0 was smaller than the threshold, then the symbol of HL2 is naturally ZTR, so it is not necessary to search until HL2. You only need to refer to the symbol in HL1. Therefore, when creating a symbol of HL0, only the symbol of HL1 needs to be referred. If HL1 is IZ when the coefficient of HL0 is smaller than the threshold, it means that there is a coefficient larger than the threshold in the upper band of HL1, so HL0 is also IZ. In this way, you do not have to search all the upper bands to create a ZTR, just the upper band, so you do not have to read the DRAMs redundantly. Therefore, the number of memory accesses can be significantly reduced. In addition, Shapiro's method searches coefficients to generate a zero tree, but the proposed method requires only two bits because only symbols are searched. The bus width of the processor is 16 bits, so eight symbols can be read at a time. Thus, once accessed, there is no need to access the memory while creating six zerotrees. Therefore, the memory access bus band is reduced back to 1/8 from the above.

The following is the difference in memory access bandwidth obtained experimentally. In Table 1, it can be seen that the method according to the present invention can significantly improve the speed of zero tree coding.

Drawing Sapiro way Method according to the invention Boats 13269636 4151044 Bridge 12214294 4139116 cablecar 13550007 4153375 Cjs 13342057 4153116 Couple 13393812 4148770 F16 13415046 4150956

The proposed method for the H / W implementation consists of a threshold comparator 510, a zero tree map 520, and a zero tree generator 530. Each of these methods can be implemented simply by performing a simple repetitive task. In addition, since the design time is shortened and the information of the zero tree map 520 is composed of 2 bits, the zero tree map 520 can be implemented in the zero tree searcher, thereby reducing external memory usage, which is very advantageous for low power.

Another advantage of the present invention is that the configuration of the control logic is simple. To generate a symbol, the control logic reads the coefficients, compares them to the threshold, and creates a new symbol by referring to the symbol of the upper band. The behavior is the same for all bands.

However, Shapiro's method is not simple. In order to generate the symbol of the lower band, the coefficient of the upper band should be read and compared with the threshold. At this time, the upper band should read four times the size of the current pixel and make a comparison, and the upper band should read 16 times the size. In this way, the coefficients should be read up to the top band. If 6 bands are divided by the wavelet transform, 6 bands must be read to the top band to perform zero tree coding in the lowest band, and 6 bands must be read to perform zero tree coding in the upper band.

According to the present invention, the operation is the same in all the bands, thus simplifying the construction of the control logic. Therefore, it is very easy to implement in hardware because it has high speed and simple control structure.

Claims (8)

A threshold comparison unit for comparing the reference threshold and the wavelet coefficient and generating predetermined category information from the level of the child correspondence relationship to the level of the parent correspondence relationship using information of a previous level; A zero tree map storing the predetermined category information; And And a zero tree generation unit generating a zero tree using a category capable of generating a zero tree among predetermined categories stored in the zero tree map. The method of claim 1, wherein the threshold comparison unit And an initial reference threshold is set to a value not smaller than 1/2 of the maximum value of the wavelet coefficient and compared with the wavelet coefficient. The method of claim 2, wherein the first reference threshold is And a zero-tree generator for determining a multiplier of two. The method of claim 1, wherein the zero tree map If the wavelet coefficient is larger than the reference threshold, the wavelet coefficient is separated into a first category, and if the wavelet coefficient is smaller than the reference threshold, and the coefficient of the previous level is larger than the reference threshold, the wavelet coefficient is separated into a second category. And predetermined category information divided into third categories having coefficients smaller than the reference threshold and coefficients of previous levels smaller than the reference threshold are stored. The method of claim 1, wherein the zero tree map The zero tree generating apparatus, characterized in that the information of the zero tree map is composed of 2 bits. A method of generating a zero tree by using a parent-child correspondence of wavelet coefficients generated by wavelet transforming an input image, (a) comparing the reference threshold and the wavelet coefficients, and also comparing the coefficients of the previous threshold and the previous level; (b) if the wavelet coefficient is larger than the reference threshold from step (a), the wavelet coefficient is divided into a first category, and if the wavelet coefficient is smaller than the reference threshold and the coefficient of the previous level is larger than the reference threshold, Separating into two categories, wherein the wavelet coefficient is smaller than the reference threshold and the coefficient of the previous level is also smaller than the third threshold; (c) in the step (b), in the case of the first category and the second category, the zero tree is not configured, and the zero tree is included only in the third category. Zero tree generation method. The method of claim 6, wherein the reference threshold is A method for generating a zero tree, characterized in that the value is set not to be smaller than 1/2 of the maximum value of the wavelet coefficient. The method of claim 6, When the generation of the zero tree for all coefficients is completed, the zero tree generation method is repeated until the predetermined bit rate is satisfied by reducing the reference threshold value to 1/2.

Images