CN103618898A - Complexity image lossless compression method supporting random access - Google Patents

Abstract

The invention relates to a complexity image lossless compression method supporting random access and belongs to the technical field of video image compression. The method includes the following steps that an image is segmented into macro blocks which are divided into three regions; intra-frame detection is carried out; a mode with the minimal code bit cost is chosen to obtain a residual image of the optimal predicting mode; the residual image is segmented into different small blocks to undergo self-adaption variable-length encoding and lossless compression code streams are obtained through a compression code stream generating module. The problem of data dependency of boundary pixels among the macro blocks is solved by dividing the macro blocks into the three regions. A high data compression rate can be achieved by means of a block/pixel self-adaption predication, differential encoding and self-adaption variable-length encoding combination compression method. The lossless compression effect for the 1080p resolution ratio can be more than 50%.

Description

A Lossless Compression Method for Complex Image Supporting Random Access

technical field

The invention belongs to the technical field of video image compression, and in particular relates to a lossless compression method for complex images supporting random access.

Background technique

With the rapid development of video codec technology, integrated circuit design and manufacturing, and network communication technology, the application of digital media (such as digital TV, laser disc, video surveillance, etc.) Decoder design faces huge challenges in terms of computing resources and memory access bandwidth.

In the high-definition and ultra-high-definition video codec chip structure, the original image frame and the decoded image reference frame are stored in the external memory, and the external memory access bandwidth is the bottleneck of the structural design. At present, the industry is gradually evolving to 4K resolution. Basically, the pixels of ultra-high-definition (4Kx2K) images are four times that of 1080P resolution images, which means that compared with 1080P, ultra-high-definition (4Kx2K) will occupy four times the bandwidth. For a video with 4Kx2K (4096X2304) pixels and 30fps, data access will consume a huge amount of bandwidth. For example, only writing back each frame requires nearly 13.5Mbyte of memory bandwidth. The industry is in great need of lossless data compression technology, which can compress the image data stored in the external storage before writing to the external storage, and decompress and reconstruct the data after reading, so that the performance of the video codec is not affected at all. Reduce bus bandwidth for external memory data access.

For videos above 720p resolution, a lossless compression algorithm is designed. If it can save about 50% of the external memory access bandwidth, it can greatly alleviate the huge challenge of high-definition video codec chip structure design, and greatly reduce the system performance caused by frequent external memory access. It is very meaningful work to provide support for high-performance and low-power structure design.

In video encoders, motion estimation consumes the largest external memory access bandwidth and is the biggest challenge for system design. Generally speaking, the reference frame data is stored continuously according to the pixels in the macroblock, so it is hoped that the lossless compression algorithm can support random access to the macroblock data, so as to maximize the use of the burst mode and high-efficiency data access mode of the external SDRAM memory. Supports random access to macroblocks. When any macroblock is accessed, the hardware can reconstruct the data of the macroblock, which means that the correlation between adjacent pixels between macroblocks cannot be used, and there is no data dependence between macroblocks. This constraint is a problem that the lossless compression algorithm needs to solve. In addition, compression efficiency and regularity of data access (related to address control) are also important factors to be considered.

A variety of near-lossless compression methods appeared in the early stage. Based on the combined coding method of prediction, transformation and quantization, lossy compression is realized, and the distortion is controlled above 40dB. Some pixels of this type of method have relatively large distortion, and the distribution of distortion is uneven. This type of near-lossless compression technology is actually lossy compression, and the absolute value of some edge pixel distortion can reach 3 or even higher. This compression distortion is very unfavorable to subsequent video encoding and processing.

The lossless compression technology based on horizontal prediction + semi-fixed-length variable-length coding proposed by Dajiang Zhou of Waseda University uses macroblocks as the basic data compression processing unit, and semi-fixed-length variable-length coding is based on small blocks with a size of 2x2 to calculate the dynamics of small blocks range, each small block is mapped to one of 8 sub-districts according to the dynamic range, so that fixed-length coding is performed according to the sub-district. The self-adaptive division between cells realizes the variable length coding. The compressed data rate of this technology is 50%~70% of the uncompressed. This type of lossless compression technology does not reach an average compression efficiency of 50%, and cannot completely remove the redundancy between spatial pixels and the statistical redundancy between control characters, and there is room for further improvement in compression efficiency.

Contents of the invention

The purpose of the present invention is to overcome the above-mentioned defects and deficiencies, and provide a lossless compression method for complex images that supports random access.

The technical scheme that the present invention realizes its object adopts is as follows.

A method for lossless compression of complexity images supporting random access, comprising the following steps:

(1) Divide the image into macroblocks, divide the macroblock into three areas: the first row, the first column, and a 15x15 pixel area, and divide the 15x15 pixel area into 5x5 small blocks of 3x3;

(2) Intra-frame prediction: For the first row, use the horizontal direction prediction mode; for the first column, use the vertical direction prediction mode; for each small block, use the block-level prediction or pixel-level prediction that consumes the least coding bits ;

(3) Small-block intra-frame prediction mode selection: The coded bit estimation module based on the look-up table calculates the coded bit consumption for various prediction modes, selects the mode with the smallest coded bit cost, and obtains the residual image of the optimal prediction mode;

(4) Divide the residual image into different small blocks for adaptive variable length coding, estimate the dynamic range of each small block, calculate the corresponding control word mm, and obtain the corresponding control word M, which is generated by the compressed code stream generation module A lossless compressed code stream is obtained.

Preferably, in step (2), for each small block, first calculate the block-level prediction, select the horizontal or vertical mode, determine the block_pred_type (r, s), and calculate the prediction residual residue (r, s; m, n), Use semi-fixed-length VLC coding, count the number of bits_block coded in the block, and select the mode with the smallest coding cost as the block-level mode; then calculate the pixel-level prediction, calculate the horizontal and vertical prediction values of each pixel, compare the size, and select the mode with a small prediction error pixel_pred_type, and then obtain the residual of the entire block, use semi-fixed length VLC encoding, compare the number of bits_block_pixel of the statistical block encoding with the previous bits_block, and select a mode with a smaller encoding cost to determine the block-level prediction type pred_type.

Preferably, in step (3), for each 3x3 small block, estimate the dynamic range of the data in the small block, determine the partition state information mm, look up the table according to the dynamic range information mm of each small block to obtain variable length bit information, Realize the semi-fixed-length code table based on the control word mm, and then construct the Huffman variable-length code table of the coded control word M by analyzing the histogram of the M field and the huffman code off-line, and finally according to the semi-fixed-length code table based on the control word mm and The Huffman variable-length code table of the coding control word M calculates the coding bit consumption for various prediction modes.

Preferably, in step (4), the residual image is divided into different small blocks for variable-length coding: for the first row and first column residual, 4 adjacent data constitute a small block with a size of 2x2, For other 15x15 data blocks, 3x3 data blocks are used.

As a preference, for the prediction residual, adopt small-block-based semi-fixed-length VLC coding technology: for each small block, calculate the maximum coefficient and minimum coefficient in the small block, determine the dynamic range mm, divide the small block residual coefficient according to mm There are 8 intervals, which are identified by the control field M, and fixed-length coding is used for each divided interval.

Preferably, for the control word M information, the Huffman variable-length coding method is used to count the histograms of various values of M, and according to the probability distribution, a variable-length coding table is obtained when M is 0 to 7, and then the variable-length coding table is obtained based on the table look-up method. Variable length encoding.

The present invention has the following beneficial effects:

(1) Divide the macroblock into three areas, which solves the data dependence problem of the border pixels between macroblocks. Using block/pixel adaptive prediction, differential coding, and adaptive variable-length coding combined compression method can achieve a high data compression rate, and the lossless compression effect for 1080p resolution can reach more than 50%;

(2) Block/pixel-level adaptive prediction, supports adaptive coding of different small blocks in different regions, supports random access to macroblock-level data, and improves prediction efficiency, so that the prediction residual image contains smaller image information. Based on the principle of minimizing coding bit consumption, balance between prediction efficiency and prediction residual coding bit efficiency;

(3) Based on the dynamic range of the small block, adaptively divide the interval, and use semi-fixed-length variable-length coding for different intervals; for the control coefficient, use the Huffman variable-length coding method based on probability distribution; maximize the use of redundancy in symbols, so that The overall entropy coding performance is as high as possible, the coding bit consumption of residual data and control field is as small as possible, and the compression rate is improved.

Description of drawings

Fig. 1 is a flow chart of the present invention;

FIG. 2 is a schematic diagram of dividing 256 pixels of a macroblock into three regions.

Detailed ways

The present invention will be described in further detail below in conjunction with the accompanying drawings.

(1) Divide the image into macroblocks, and divide the macroblock into three areas, the first row, the first column, and a 15x15 pixel area. For a 15x15 pixel area, it is divided into 5x5 small blocks of 3x3.

(2) Intra-frame prediction is used to remove data dependence between macroblocks.

For the first row, use the horizontal direction prediction mode;

For the first column, use the vertical direction prediction mode;

For each small block, block-level prediction is adopted, or pixel-level prediction is performed on 3×3=9 pixels in the small block. Both block-level prediction and pixel-level prediction support horizontal and vertical prediction to make full use of the horizontal or vertical correlation between pixels in a macroblock to maximize prediction efficiency. In order to ensure that there is no data congestion during data processing, the pixel-level prediction mode selection in the small block needs to be performed at the small block level, that is, to ensure that the total number of coding bits of all pixels in the small block is the smallest.

Figure 2 shows a schematic diagram of 256 pixels of a macroblock divided into three areas:

The first line: horizontal prediction, deltaX(1, n) = X(1, n) - X(1, n-1);

The first column: vertical prediction, deltaX(n, 1) = X(n, 1) - X( n-1, 1);

The other 15x15 pixels are divided into 5x5 pixel blocks with a size of 3x3. Each pixel block (r, s) supports two prediction modes: block-level prediction or pixel-level prediction, identified by the 1-bit control word predmode(r, s) , 1 is block-level prediction; 0 is pixel-level prediction. specifically:

a. Block-level prediction: bits_block(r, s) = bit_residue_block(r, s) + 1 + 1.

Support horizontal prediction or vertical prediction, similar to the H.264/AVC intra prediction technology, the horizontal or vertical prediction mode is identified by the control word block_pred_type(r, s), 1 is the horizontal prediction mode, and 0 is the vertical prediction mode.

b. Pixel-level prediction: bits_block_pixel(r, s) = bit_residue_block_pixel (r, s) + 1 + 9.

Support horizontal or vertical prediction mode for each pixel (r, s; m, n) in a 3x3 block, identified by the control word pixel_pred_type(r, s; m, n), 1 is the horizontal prediction mode, 0 is the vertical prediction mode; r=1~5, s=1~5, m=1~3, n=1~3.

The selection of block-level prediction and pixel-level prediction needs to be judged based on the minimization of coding bit consumption cost. For each 3x3 small block, estimate the coding bit cost of various prediction modes, select the mode with the least coding bit consumption as the optimal mode, and calculate the prediction residual. The process is as follows:

First calculate the block-level prediction: select horizontal or vertical mode, determine block_pred_type (r, s), calculate the prediction residual residue (r, s; m, n), use semi-fixed-length VLC encoding, count the number of block encoding bits bits_block, select The mode of minimum encoding cost is block-level mode block_pred_type;

Then calculate the pixel-level prediction: calculate the horizontal and vertical prediction values of each pixel, use the SAD criterion to compare the size of the prediction error, and select the mode pixel_block_type(r, s) with a small prediction error.

Then get the residual of the entire block, use semi-fixed-length VLC coding, count the number of bits_block_pixel of the block coding and compare it with the previous bits_block, select the mode with a smaller coding cost, so as to determine the block-level prediction type pred_type (r, s).

(3) Small-block intra-prediction mode selection: Judgment based on the minimum coding bit cost. The coded bit estimation module based on the look-up table calculates the coded bit consumption for various prediction modes; and this estimation process requires a semi-fixed-length code table based on the control word mm and a Huffman variable-length code table based on the coded control word M. For each 3x3 small block, the dynamic range of the data in the small block is estimated, and the partition state information mm is determined.

Among them, the semi-fixed-length code table based on the control word mm is realized, and the variable-length bit information is obtained by looking up the dynamic range information mm of each small block; and the Huffman variable-length code table of the encoded control word M is determined by M Field histogram analysis and Huffman coding offline construction.

After completing the mode selection, the residual image of the optimal prediction mode is obtained,

(4) For the residual image, it is divided into different small blocks for adaptive variable length coding. In the first row and first column of residuals, 4 adjacent data form a small block with a size of 2x2, and other 15x15 data blocks use 3x3 small data blocks. The dynamic range of each small block is estimated, the corresponding control word mm is calculated, and the corresponding control word M is obtained, and the lossless compressed code stream is obtained by the compressed code stream generation module.

Because the dynamic range (minv, maxv) has a direct impact on the coding efficiency, the 16 pixels in the first horizontal row only use the horizontal prediction mode, and the first vertical column only uses the vertical prediction mode; so for some areas with complex edges and textures, The dynamic range of the unidirectional prediction mode will be larger; the other 15x15 pixels adopt the block, pixel-level adaptive horizontal and vertical prediction mode, and the dynamic range will be relatively small. In order to avoid the mutual influence of these two situations, the present invention adopts an adaptive small block selection strategy: in order to ensure that the coding bit estimation is consistent with the block-level prediction mode adaptive selection, for the 15x15 residual block, it is divided into 5x5 blocks with a size of 3x3 For the 16 pixels in the first horizontal row, divide them into 4 small 2x2 blocks; for the 16 pixels in the first vertical column, divide them into 4 small 2x2 blocks.

For the prediction residual residue, a small-block-based semi-fixed-length VLC coding technique is used. For each small block, calculate the maximum coefficient maxv and minimum coefficient minv in the small block, determine the dynamic range according to minv and maxv (use mm to distinguish), and adaptively divide the residual coefficient of the small block into 8 codes with variable length according to mm area, and is identified by the control field M. For each division interval, a fixed-length code is used, as shown in Table 1.

               Table 1 Residual coefficient semi-fixed-length code table

For the control word M information, in order to reduce the encoding bits of the M field, the Huffman variable-length coding method is used, and the histograms of various values of M are counted. According to the probability distribution, the variable-length coding table when M is 0-7 is obtained. Determine the variable-length coding code table, and then perform variable-length coding based on the table look-up method.

mm = max (abs(maxv), abs(minv))

if (maxv == -minv && max!=1) mm = mm+1

Note that there are 5x5 small 3x3 blocks in the 15x15 area, and 4+4 2x2 blocks in the first horizontal row and the first vertical row. Because the dynamic range is different, the probability distribution of the M field is also different. For 3x3 and 2x2 small blocks, independent huffman code tables are used, as shown in columns 2 and 3 in Table 2

Table 2 Huffma variable-length code table of control field M

The present invention has been described according to the embodiments. On the premise of not departing from the principle, the device can also be modified and improved. It should be pointed out that all technical solutions obtained by means of equivalent replacement or equivalent transformation fall within the protection scope of the present invention.

Claims (6)

1. support the complexity map of random access as a lossless compression method, it is characterized in that, comprise the following steps:

(1), image is divided into macro block, by macroblock partitions, be three regions: the first row, first row and 15x15 pixel region, and 15x15 pixel region is divided into the fritter of 5x5 3x3;

(2), infra-frame prediction: for the first row, adopt horizontal direction predictive mode; For first row, adopt vertical direction predictive mode; For each fritter, adopt and select coded-bit to consume minimum piece level prediction or Pixel-level prediction;

(3), fritter Intra prediction mode selection: the coded-bit estimation module based on tabling look-up is that various predictive modes calculate coded-bit consumption, selects the pattern of coded-bit Least-cost, obtains the residual image of optimal prediction modes;

(4), residual image be divided into different fritters carry out self-adapting changeable long codes, estimate the dynamic range of each fritter, calculate corresponding control word mm, obtain corresponding control word M, by compressed bit stream generation module, obtain Lossless Compression code stream.

2. as claimed in claim 1ly a kind ofly support the complexity map of random access as lossless compression method, it is characterized in that, in step (2), for each fritter, first computing block level prediction, selection level or vertical mode, determine block_pred_type (r, s), calculate prediction residual residue (r, s; M, n), adopt half fixed length VLC coding, statistics block number of coded bits bits_block, selecting the pattern of minimum code cost is piece level pattern; Then calculating pixel level prediction, calculate the horizontal vertical predicted value of each pixel, big or small, select the little pattern pixel_pred_type of predicated error, then obtain the residual error of whole, adopt half fixed length VLC coding, statistics block number of coded bits bits_block_pixel and and bits_block comparison above, selection is compared with the pattern of lower Item cost, thus definite piece level type of prediction pred_type.

3. as claimed in claim 1ly a kind ofly support the complexity map of random access as lossless compression method, it is characterized in that, in step (3), for each 3x3 fritter, estimate data ground dynamic range in fritter, determine subregion state information mm, according to the dynamic range information mm of each fritter, table look-up and obtain elongated bit information, the half fixed length code table of realization based on control word mm, then by M field histogram analysis and huffman coding off-line, build the Huffman variable length code table that obtains coding-control word M, last according to the half fixed length code table based on control word mm and the Huffman variable length code table of coding-control word M, for various predictive modes calculate coded-bit consumption.

4. as claimed in claim 1ly a kind ofly support the complexity map of random access as lossless compression method, it is characterized in that, in step (4), for residual image, be divided into different fritters and carry out Variable Length Code: for the first row, first row residual error, adjacent 4 data form a fritter that size is 2x2, for other 15x15 data blocks, adopt 3x3 data fritter.

5. as claimed in claim 4ly a kind ofly support the complexity map of random access as lossless compression method, it is characterized in that, for prediction residual, the half fixed length VLC coding techniques of employing based on fritter: for each fritter, calculate greatest coefficient, minimum coefficient in fritter, determine dynamic range mm, according to mm, fritter residual error coefficient is divided into 8 intervals, and by control field M sign, for each demarcation interval, adopt block code.

6. as claimed in claim 5ly a kind ofly support the complexity map of random access as lossless compression method, it is characterized in that, for control word M information, adopt Huffman variable length encoding method, the block diagram of the various values of statistics M, according to probability distribution, obtain M and get 0 ~ 7 o'clock Variable Length Code table, then based on look-up method, carry out Variable Length Code.

Images