CN1581977A - Tree-structure-based grade tree aggregation-divided video image compression method - Google Patents

Abstract

The invention is a method for compressing video images based on hierarchical tree set partitioning (SPIHT) based on tree structure. At the encoding end, the distribution of image energy in the time-frequency domain is obtained through discrete wavelet transform; according to the correlation between wavelet coefficients, the wavelet coefficients of each level are divided according to the tree structure; and then the wavelet coefficients of each tree are respectively SPIHT encoding, the encoding results are temporarily stored in the encoding end; finally, the encoding results of each tree are synthesized into a code stream for storage or transmission. The decoding process is the reverse process of the encoding process. The present invention greatly saves the use of memory in the calculation process without consuming redundant calculations, thereby adapting to real-time and efficient compression of video streams, and is especially suitable for special systems implemented by hardware, which can be realized with less storage space Video compression with high compression ratio and low distortion.

Description

Video Image Compression Method Based on Hierarchical Tree Set Division Based on Tree Structure

technical field

The invention belongs to the technical field of video image compression, and in particular relates to a video image compression method based on hierarchical tree set division of a tree structure.

Background technique

The Hierarchical Tree Set Partitioning (SPIHT) algorithm fully considers the correlation between data, and also considers the characteristic that high-bit data is more important than low-bit data in the same data when encoding. So using the SPIHT method to compress and decompress video images can get a relatively high compression ratio without increasing the distortion of the decompressed results, so this method has received increasing attention. In the specific implementation process, the encoding system needs to establish three linked lists, namely the important pixel linked list (LSP), the unimportant pixel linked list (LIP) and the unimportant pixel set linked list (LIS). These three linked lists are used to record the tree structure. Split intermediate data. Through the use of the linked list, the coded streams can be arranged in the descending order of the threshold (importance), so as to ensure the transmission of important information and truncate non-important information, and obtain the compression effect of arbitrarily truncated code streams with high compression ratio. In order to improve the compression effect, the tree structure is required to include more data. However, as the amount of data in the tree structure increases, the length of the three linked lists becomes longer and longer, which requires a huge memory space in practical applications, which increases the cost and complexity of the system. Therefore, under the premise of not reducing the compression effect, the method of shortening the length of the linked list is becoming a research hotspot.

Contents of the invention

The purpose of this invention is to propose a kind of hierarchical tree set partitioning (SPIHT) video image compression method based on tree structure, under the premise that guarantees that compression effect does not descend, shorten the length of link list greatly, save the memory space overhead of system.

According to the hierarchical tree set partitioning (SPIHT) video image compression method based on the tree structure proposed by the present invention, the specific steps of encoding are as follows: firstly, the distribution of image energy in the time-frequency domain is obtained by discrete wavelet transform, and due to the smoothness of the image, the image The energy is concentrated in the low frequency part; according to the correlation between the wavelet coefficients, the wavelet coefficients of each level are divided according to the tree structure; then the wavelet coefficients of each tree are separately encoded by SPIHT, and the encoding results are temporarily stored in the encoding end; Finally, the encoding results of each tree are synthesized into a code stream for storage or transmission.

According to the data correlation between the wavelet coefficients, dividing the wavelet coefficients of each level according to the tree structure refers to taking each coefficient of the lowest frequency sub-band as the root of the tree, and according to the data correlation of the positions of the wavelet coefficients between different levels, we can get Data for each point in the tree structure. In the tree structure, the relationship between the upper-level wavelet coefficients and the lower-level wavelet coefficients is called the relationship between parents and children or offspring. In the wavelet coefficients, the coefficients in the same position of different sub-bands are often similar in value. According to this relationship, each coefficient of the lowest frequency sub-band is used as the root node of the tree, and the same position in the higher-level children The coefficients of are taken as the first-level children of the tree structure, and the coefficients of the higher-level children in the same position as each first-level child are the children of the first-level children, which are also the second-level children of the tree structure... ...up to the coefficients of the highest frequency subband as children of the last level.

SPIHT encoding is performed on the wavelet coefficients of each tree separately, which can reduce the wavelet coefficients processed at the same time, produce less intermediate results, and shorten the important pixel linked list (LSP), unimportant pixel linked list (LIP) and unimportant pixel set linked list ( LIS) length. The method is to obtain the encoding results of each tree in the descending order of the threshold until the threshold drops enough to meet the compression requirements. The threshold drop limit can be determined by the minimum threshold of the previous frame group or the predicted threshold obtained from the empirical threshold. The result of SPIHT encoding of the wavelet coefficients of each tree is not directly transmitted, but temporarily stored at the encoding end. When storing, the coded streams under each threshold are stored in sequence, and the length of the coded stream under each threshold is recorded.

After the coding of all tree-structured wavelet coefficients is completed, in order to obtain the target code stream that meets the compression ratio requirements, it is necessary to synthesize the coding results of each tree into the target code stream. The method of synthesizing the code stream is to determine the minimum threshold, which is called the truncation threshold, so that the sum of the code streams not less than the threshold in the code stream of each tree is not greater than the target code stream length, and these code streams and code stream lengths are synthesized is the target code stream, and the remaining target code streams are evenly distributed by the remaining code streams of each tree. That is, the code streams whose threshold value is not less than the truncation threshold in the coding result of each tree and the length of these code streams are directly used as the target code stream, and the insufficient part of the target code stream is evenly distributed by the code streams whose threshold is smaller than the truncation threshold in the coding result of each tree .

The key points of the coding process are the division of the tree structure, the storage of the coding result of the tree structure wavelet coefficients and the synthesis of the target code stream.

At the decoding end, the decoding process is the inverse process of the encoding process: firstly, the code stream to be decoded is allocated to the cache of each tree, and then the code stream allocated to each tree is sequentially decoded by SPIHT to obtain the wavelet coefficients of the tree structure , and then restore the wavelet coefficients in the tree structure to wavelet coefficients arranged in sub-bands, and obtain the decoded image through inverse wavelet transform.

The hierarchical tree set partitioning (SPIHT) video image compression method based on the tree structure proposed by the present invention effectively solves the contradiction between the amount of image data and the length of the linked list. In order to improve the compression effect, multiple frames of images (frame groups) can be subjected to discrete wavelet transformation together, so that each tree can include enough wavelet coefficients; since each tree is encoded separately, it will not lead to a linked list of important pixels (LSP) , The length of the unimportant pixel linked list (LIP) and the unimportant pixel set linked list (LIS) is excessively lengthened.

Description of drawings

Figure 1 shows the search relationship between the root node and the first three generations of children.

Figure 2 shows the relationship sought by the children of the next two generations.

Detailed ways

Each composition in the invention is discussed separately below.

1. Tree structure division of discrete wavelet transform results

Discrete wavelet transform can use three-dimensional discrete wavelet transform, that is, perform discrete wavelet transform in row direction, column direction and time direction respectively. Each coefficient of the lowest frequency of the transformation result is used as the root node of a tree, and a tree structure is formed according to the following relationship. It is assumed that the size of the lowest frequency coefficient is W _min ×H _min , where W _min and H _min are respectively the width and height of the lowest frequency sub-band of the lowest frequency frame.

1) The method of finding the children of the root node The children are:

2) Two-dimensional child search method whose children are:

3) The method of finding three-dimensional children whose children are:

As shown in Figure 1 and Figure 2, Figure 1 shows the search relationship between the root node and the first three generations of children, and Figure 2 shows the search relationship between the next two generations of children, and only one of the seven branches is drawn in the figure.

2. Storage D _{M of SPIHT coding results of wavelet coefficients in each tree structure, N} represents the coded data whose threshold value is N in the Mth tree when the threshold value drops from 2 ^N+1 to 2 ^N. L _{M, N} represents the encoded data length of the Mth tree whose threshold is N when the threshold drops from 2 ^N+1 to 2 ^N. The encoding results of all trees are stored in the following format: threshold ^{2N 2N-1} ... ^2-1 1st tree D _{1, N} D _{1, N-1} ... D _{1, -1} 2nd tree D _2,N D2 _{, N-1} ... D _{2, -1} 3rd tree D _{3, N} D _{3, N-1} ... D _{3, -1} Mth tree D _{M, N} D _{M, N-1} ... D _{M, -1}

3. Synthesis of the target code stream

If there are M trees, the required length of the target stream is Q. When the threshold drops to 2 ^P , the total code stream length of all trees is

$N_1=\underset{\mathrm{no}=1}{\overset{m}{\mathrm{\&Sigma;}}}\underset{m=P}{\overset{N}{\mathrm{\&Sigma;}}}{L}_{\mathrm{no},m},$ When the threshold drops to 2 ^P-1 , the total code stream length of all trees is $N_2=\underset{\mathrm{no}=1}{\overset{m}{\mathrm{\&Sigma;}}}\underset{m=P-1}{\overset{N}{\mathrm{\&Sigma;}}}{L}_{\mathrm{no},m},$ And satisfy N ₁ <Q≤N ₂ , then 2 ^P is the truncation threshold. First, all code streams and code stream lengths when the threshold of M trees is reduced to 2 ^P are used as the target code stream. If the code stream length of each tree entering the target code stream is represented by X bits, the target code stream is about N ₁ +X, and then evenly distribute the remaining QN ₁ -X target code streams to the remaining code streams in M trees, that is, the threshold of each tree is 2 ^P-1 before (QN ₁ -X) /M code stream as the target code stream. Specifically, in the target code stream, the code stream of each tree is arranged as follows:

D_1，N——D_1，P；1st tree

D _{1, N} - D _{1, P} ;

2nd tree D2 _{, N} - _{D2, P} ;

...

D_M，N——D_M，P；Mth tree

D _{M, N} - D _{M, P} ;

D _{1, the first bit in P-1} ; D _{2, the first bit in P-1} ; ... D _{M, the first bit in P-1} ;

D _{1, the 2nd bit in P-1} ; D _{2, the 2nd bit in P-1} ; ... D _{M, the 2nd bit in P-1} ;

...

Until the target stream length reaches the requirement.

The decoding process is completely the reverse process of encoding. First, the code stream to be decoded is allocated to the cache of each tree, and then the code stream allocated to each tree is sequentially decoded by SPIHT to obtain the wavelet coefficient of the tree structure, and then the wavelet coefficient of the tree structure is restored to the The wavelet coefficients with arrangement are obtained by inverse wavelet transform to obtain the decoded image.

Simulation results

The specific simulation conditions are as follows:

The Y value data of frames 1-8 of the Miss American video image group, and the image size of each frame is 352×288. Three-level three-dimensional discrete wavelet transform is performed, and then two-level two-dimensional discrete wavelet transform is performed on low-frequency frames. The wavelet base uses Daubechies9/7 biorthogonal wavelet (row direction and column direction) and Haar wavelet (time direction). There are 99 trees in total.

The experimental results are as follows: The original image 8 frames 352×288 Y value 811008 bytes in total Wavelet transform result Each wavelet coefficient is represented by 16bits A total of 1622016 bytes each tree A frame group is divided into 99 trees 16384 bytes in total Compression factor/target stream length index before optimization After optimization ^* 200/4055 bytes LIP linked list length 6642 4433 LSP linked list length 6084 6459 LIS linked list length 3521 536 PSNR effect 39.3690 39.0733 150/5406 bytes LIP linked list length 10752 4429 LSP linked list length 7851 6419 LIS linked list length 4651 536 PSNR effect 39.9526 39.5110 100/8110 bytes LIP linked list length 14384 4443 LSP linked list length 12134 6448 LIS linked list length 5216 536 PSNR effect 40.7056 40.4405 50/16220 bytes LIP linked list length 44952 4390 LSP linked list length 22792 6462 LIS linked list length 13988 536 PSNR effect 41.4691 41.3303

^* The optimized LIP, LIP, and LIS are the largest lengths among the 99 trees, and each tree is coded until the threshold is reduced to 8. The test proves that the threshold is reduced to 8, which can generally meet the requirements of the compression ratio.

Through the above experimental results, we found that although the result of the SPIHT encoding method reduces the PSNR (reduces very little), the space for storing the linked list can be greatly reduced.

Claims (5)

1. Video image compressing method is divided in 1 one kinds of hierarchical tree set based on tree, it is characterized in that by wavelet transform obtain image energy the time distribution on the frequency domain, again wavelet coefficient at different levels is divided according to tree, wavelet coefficient to every tree carries out the SPIHT coding respectively then, coding result is temporarily deposited respectively, at last the coding result of every tree is synthesized a code stream and is used for storage or transmission.
2. Video image compressing method is divided in the 2 hierarchical tree set based on tree according to claim 1, the division that it is characterized in that tree is a tree root with each coefficient of lowest frequency subband, obtains the data of each point in the tree according to the data dependence of wavelet coefficient position between the different stage.
3. Video image compressing method is divided in the 3 hierarchical tree set based on tree according to claim 1, it is characterized in that every tree all carries out the SPIHT coding respectively, the coding result of every tree all obtains according to the order that threshold value descends, up to threshold value drop to can satisfy compression and require till.
4. 4 according to claim 1 or 3 described hierarchical tree set division video image compressing methods based on tree, the coding result that it is characterized in that every tree is temporarily stored in coding side earlier, when depositing the encoding code stream under each threshold value situation is deposited successively, and write down encoding code stream length under each threshold value situation.
5. 5 according to claim 1 or 4 described hierarchical tree set division video image compressing methods based on tree, the method that it is characterized in that synthetic code stream is to determine minimum threshold value, make the code stream sum that is not less than this threshold value in every tree-encoding code stream be not more than target code stream length, these encoding code streams and code stream length is synthetic as the target code stream, and remaining target code stream is again by all the other encoding code stream mean allocation of every tree.