CN1564604A - Gradation tree set partitioning image compression method based on tree shaped structure - 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 firstly 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; 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, and can achieve high Compression ratio and low distortion video compression.

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 is 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.

Detailed ways

1. The specific implementation method of the encoding end

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:

{(2x, 2y, z), (2x+1, 2y, z), (2x, 2y+1, z), (2x+1, 2y+1, z)} (2)

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

2. The storage of the SPIHT encoding result of each tree structure wavelet coefficient

D _{M, 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 expressed 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:

1st tree $\underset{m=P}{\overset{N}{\mathrm{\&Sigma;}}}{L}_{1,m},$ D _{1, N} - D _{1, P} ;

2nd tree $\underset{m=P}{\overset{N}{\mathrm{\&Sigma;}}}{L}_{2,m},$ D _{2, N} - _{D 2, P} ;

...

Mth tree $\underset{m=P}{\overset{N}{\mathrm{\&Sigma;}}}{L}_{m,m},$ 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.

2. The specific implementation method of the decoder

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.

3. 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×288Y 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 7739 316 LSP linked list length 4565 115 LIS linked list length 5423 97 PSNR effect 38.2365 38.1827 150/5406 bytes LIP linked list length 8761 316 LSP linked list length 6663 115 LIS linked list length 7051 97 PSNR effect 39.0111 38.6621 100/8110 bytes LIP linked list length 17075 316 LSP linked list length 8853 115 LIS linked list length 9985 97 PSNR effect 39.9610 39.2729 50/16220 bytes LIP linked list length 38470 316 LSP linked list length 18784 115 LIS linked list length 19531 97 PSNR effect 41.2432 40.8792

^* 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 can find 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, a kind of hierarchical tree set division video image compression method based on tree-like structure, it is characterized in that the concrete steps of encoding are as follows: first obtain the distribution of image energy in the time-frequency domain by discrete wavelet transform, according to the correlation between 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 for storage or transmission. 2. The video image compression method according to claim 1, characterized in that the division of the tree structure is based on each coefficient of the lowest frequency sub-band as the tree root, according to different levels The data correlation between the positions of the wavelet coefficients yields the data for each point in the tree structure. 3. A method for compressing video images based on a hierarchical tree set division of a tree structure according to claim 1, wherein each tree is subjected to SPIHT encoding respectively, and the encoding results of each tree are obtained in the descending order of the threshold , until the threshold drops enough to meet the compression requirements. 4, according to claim 1 or 3, a kind of hierarchical tree set division video image compression method based on tree-like structure, it is characterized in that the encoding result of each tree is temporarily stored in the encoding end first, and the values under each threshold are stored when storing. The coded streams are stored sequentially, and the length of the coded streams under each threshold is recorded. 5. According to claim 1 or 4, a hierarchical tree set-based video image compression method based on a tree structure is characterized in that the method of synthesizing code streams is to determine the minimum threshold, so that there is no The sum of code streams smaller than the threshold is not greater than the target code stream length, and these code streams and code stream lengths are combined as the target code stream, and the remaining target code streams are evenly distributed by the remaining code streams of each tree.