CN120602681A - A fast lossless compression algorithm for star images - Google Patents

Abstract

The present invention discloses a fast lossless star image compression algorithm, aiming to address the problems of large storage requirements and low compression efficiency in existing lossless compression algorithms. The algorithm achieves efficient compression of star image data through a combination of a context modeling module, a predictive coding module, and a run-length coding module. Specifically, the algorithm divides flat and non-flat regions based on local gradient values, employing run-length coding for flat regions and predictive coding for non-flat regions; predictive coding is achieved through gradient quantization merging, prediction error calculation, and Rice coding; and run-length coding is achieved by counting the lengths of consecutive identical pixels and performing table lookup encoding. The algorithm optimizes the number of context types, reduces storage requirements, and improves compression efficiency by dynamically correcting predicted values. The algorithm is suitable for applications with high data integrity requirements, such as star sensors.

Description

Rapid star map lossless compression algorithm

Technical Field

The invention relates to the technical field of image compression algorithms, in particular to a rapid star map lossless compression algorithm.

Background

The star sensor is a posture measuring device taking a star as a reference system, and can provide accurate space orientation and reference for satellites, missiles, aviation aircrafts and the like. The working principle of the star sensor is that the image sensor collects star images in the current view field, the signal processing circuit extracts star point position and brightness information, the star image recognition algorithm is used for matching corresponding stars in the navigation star base, and finally the three-axis gesture of the star sensor is calculated through the gesture calculation algorithm according to the matching result.

The star map is an important data source of the star sensor, contains a large amount of star information, and along with the improvement of the precision requirement of the satellite control system on the star sensor, the image area array of the star sensor is larger and larger, so that huge pressure is brought to the satellite-to-ground telemetry bandwidth, and therefore, the image shot by the star sensor needs to be effectively compressed, the data quantity and the transmission time are reduced, and meanwhile, the integrity of the star information is ensured.

The image compression is classified into lossy compression and lossless compression, and the lossy compression algorithm is an algorithm that sacrifices a part of image quality to achieve a higher compression ratio when compressing an image, and the lossless compression algorithm is an algorithm that can compress image data without losing any information, and since star map information is important, the lossless compression algorithm must be used.

Common lossless compression algorithms comprise run-length coding, entropy coding, predictive coding, chained coding and the like, but the algorithms still have the defects of large storage capacity, low compression efficiency and the like. The invention provides a rapid star map lossless compression algorithm, which consists of a context modeling module, a predictive coding module and a run-length coding module, and respectively completes modeling, coding, compressing and other functions of star map data, thereby reducing the storage capacity of the compression algorithm, reducing the coded data quantity and improving the compression performance.

Disclosure of Invention

The invention aims to provide a rapid star map lossless compression algorithm, which solves the problems of large storage capacity and low compression efficiency of the existing non-calculation compression algorithm, the algorithm is composed of a context modeling module, a predictive coding module and a run-length coding module, and functions of modeling, coding, compressing and the like of star map data are respectively completed, so that the storage capacity of the compression algorithm is reduced, the coding data amount is reduced, and the compression performance is improved.

In order to achieve the above purpose, the present invention provides the following technical solutions:

A fast star map lossless compression algorithm comprising:

The context modeling is that the region types are divided according to the local gradient value Q _i of the current pixel to be coded, and a corresponding coding mode is selected, and the calculation formula of the local gradient value Q _i is as follows:

Selecting a run-length coding mode for compression when the pixel to be coded and the adjacent pixel form a flat area, and selecting a predictive coding mode for compression when the pixel to be coded and the adjacent pixel form a non-flat area;

the predictive coding mode steps are as follows:

a1, gradient quantization merging, namely dividing a local gradient value into symmetrical intervals with medium dense edges, wherein the dividing process is as follows, and the local gradient value is divided into 9 intervals in total:

After Q _i is spliced into a vector (Q ₁,Q₂,Q₃) in sequence, the Sign change is carried out on the vector, and the specific steps are that the first nonzero number appearing in Q ₁,Q₂,Q₃ is checked in sequence, if the first nonzero number is positive, the Sign variable Sign is set to be 1, (Q ₁,Q₂,Q₃) is kept unchanged, if the first nonzero number is negative, the Sign variable Sign is set to be-1, and the inverse of (Q ₁,Q₂,Q₃) is changed to (-Q ₁,-Q₂,-Q₃);

Finally, the vector (Q ₁,Q₂,Q₃) is mapped to an integer Q in the interval [0,364] according to the following mapping formula:

Q=81Q₁+9Q₂+Q₃

a2, calculating a prediction error, namely selecting a median edge detection prediction period with small calculation amount in the prediction period in the prediction coding, wherein the prediction value P _X is expressed by the following formula:

The prediction error is the difference between the gray value and the predicted value:

a3, prediction error Rice coding, wherein before Rice coding, the prediction error is mapped to be subjected to geometric distribution, and the method concretely comprises the following steps:

after mapping, rice coding is carried out, parameters k and q needed in the coding process are calculated firstly, and the calculation process is as follows:

The parameter k is used to remove the length of each field in the top-removing Rice code, the parameter Q represents the quotient in the Rice code calculation process, N [ Q ] and A [ Q ] are context parameters, N [ Q ] represents the occurrence times of the current context type, and A [ Q ] represents the sum of the absolute values of the prediction errors;

and A4, updating the context parameters, namely updating the context parameters after the coding is finished each time, wherein the updating process is as follows:

Wherein errval is the prediction error, Q is the index value, the value is [0,364] corresponding to 365 context types, A [ Q ] is the absolute sum of the prediction error, which is used for estimating the parameter k of Rice coding;

The run-length coding mode comprises the steps of firstly counting the number of pixel points with the same gray value which continuously appear, carrying out different processing according to the reason of scanning termination, if the pixels at the end of a line are not scanned, coding the run-length and then exiting the run-length coding mode, if the pixels with different gray values are scanned, then exiting the run-length coding mode and returning to the predictive coding mode to carry out predictive coding on the difference pixels.

Further, in the run-length encoding mode, in order to avoid memory overflow caused by excessive run length, a method for run-length encoding by using a table lookup is designed, wherein an encoder scans each element along index in turn, accumulates the run lengths represented by each element, and stops scanning when the accumulated value is greater than or equal to the actual run length.

Further, in step A2 in the predictive coding mode, in order to prevent the prediction error from being excessively large in the subsequent calculation, the correction is performed after the calculation of the predicted value, and the correction process is as follows:

In the formula, sign is the sign variable for judging the turnover, and CQ is the average prediction error.

The method has the advantages that the method adopts a mode of combining predictive coding and run coding, the compression algorithm comprises a context modeling module, a predictive coding module and a run coding module, star map data modeling, coding and compression are realized through the modules, redundant information can be effectively eliminated, and the storage space of the star map is reduced, so that the compression efficiency is improved. Compared with the traditional single coding mode, the method utilizes the context modeling to judge the coding mode, combines the predictive coding and the run-length coding algorithm, can effectively reduce the storage capacity of the compression algorithm, reduces the coding data quantity and improves the compression performance.

Drawings

FIG. 1 is a block diagram of a lossless compression encoder of the present invention;

FIG. 2 is a flow chart of the modeling process of the present invention;

FIG. 3 is a local gradient value calculation template;

FIG. 4 is a schematic diagram of image boundary continuation;

FIG. 5 is a flow chart of the predictive coding mode of the present invention;

FIG. 6 is a schematic diagram of interval division in the gradient quantization merging process according to the present invention;

FIG. 7 is a flow chart of a run-length encoding mode of the present invention;

FIG. 8 is a diagram illustrating a lookup table in a run-length encoding mode according to the present invention;

fig. 9 shows four different types of star maps for performance testing of the lossless compression algorithm, a) a star map with a single background, b) a star map with a complex background, c) a star map with interference in the background, and d) a pure black star map.

Detailed Description

The invention is described in further detail below with reference to the attached drawings and embodiments:

Fig. 1 is a frame diagram of a lossless compression encoder according to the present invention, which is mainly divided into two parts, namely modeling and encoding. In the figure, the encoder reads pixel data of a source image row by row from left to right according to a raster scanning sequence, and the modeling process is completed by calculating gradient values according to adjacent scanned pixels after the pixel data enter the encoder. After modeling is completed, the encoder selects different encoding modes according to the magnitude of the gradient value, wherein the encoding modes comprise prediction encoding and run-length encoding, the prediction encoding utilizes a predictor to predict the current pixel, the prediction error obtained after the prediction is completed is subjected to Rice encoding, and the run-length encoding counts continuous identical pixel values and encodes the statistical result. And outputting the obtained compressed code stream by the encoder after the encoding process is finished.

1. Context modeling process

In order to adapt to the compression requirements of different areas, the area types need to be divided according to the local gradient value of the current pixel, and the corresponding coding mode is selected, and the process is called a context modeling process.

As shown in fig. 3, the calculation template of the local gradient value is calculated according to the pixel values of the current pixel X to be encoded and four adjacent pixels A, B, C, D around the current pixel X, and the calculation formula of the local gradient value is as follows:

For the edge pixels of the image, since the adjacent pixels around the edge pixels are not all present, boundary extension is needed to ensure the correctness and the integrity of the image operation, namely, if the current pixel X to be encoded is positioned in the first row of the image, the pixel value at the A, B, C position is 0, namely, I _A＝I_B＝I_C =0, if the current pixel X to be encoded is positioned in the first column of the image, the pixel value at the D position is equal to the pixel value at the B position, namely, I _D＝I_B, and if the current pixel X to be encoded is positioned in the last column of the image, the pixel value at the C position is equal to the pixel value at the B position, namely, I _C＝I_B. As shown in fig. 4, where the solid line portion is an image area and the broken line portion is a continuation area.

The local gradient value reflects the flatness around the current pixel to be encoded, and when the three gradient values D ₁、D₂、D₃ are all 0, the current pixel to be encoded and the adjacent pixels form a flat area, and the current pixel to be encoded and the adjacent pixels form a non-flat area, and when the three gradient values D ₁、D₂、D₃ are not 0, the current pixel to be encoded and the adjacent pixels form a non-flat area, and the current pixel to be encoded and the adjacent pixels form a prediction encoding mode.

2. Predictive coding mode

As shown in fig. 5, which is a flowchart of a predictive coding mode, the predictive coding mode compresses by using predictive coding, and mainly includes two processes of prediction and coding, which uses correlation between adjacent pixels of an image to implement lossless compression by predicting each pixel of a non-flat area and Rice coding a prediction error.

2.1 Gradient quantization combining

Different local gradient values (D ₁,D₂,D₃) divide the pixels into different context types during the context modeling process, and the prediction errors corresponding to the pixels contained in each context type are considered to obey the same statistical distribution. When the image to be compressed is an 8bit gray scale image, together divide the image into 511× 511 x 511 context types. Although the partitioning of more context types can make the prediction more accurate, there are disadvantages that, on one hand, a large number of partitions results in a small number of pixels belonging to each type and even zero, thereby causing parameter redundancy, and on the other hand, a larger storage space is required to store different types in the implementation process of the algorithm, increasing the resource occupation of the algorithm, and therefore, proper quantization and merging of gradient values are required.

Firstly, dividing a local gradient value into symmetrical sections with dense middle and sparse two sides, wherein a dividing schematic diagram is shown in fig. 6, and the dividing schematic diagram is divided into 9 sections, and the dividing process is shown in the following formula:

Next, to further reduce the context types, Q _i is concatenated in order to a vector (Q ₁,Q₂,Q₃) and Sign-changed by checking the first non-zero number appearing in Q ₁,Q₂,Q₃ in order, setting the Sign variable Sign to 1 if it is positive, (Q ₁,Q₂,Q₃) remaining unchanged, setting the Sign variable Sign to-1 if it is negative, and reversing (Q ₁,Q₂,Q₃) to (-Q ₁,-Q₂,-Q₃). The number of types after transformation is reduced from 729 to 365 compared to before transformation.

Finally, in order to facilitate the following steps such as updating the context parameters, the vector (Q ₁,Q₂,Q₃) is mapped to an integer Q within the interval [0,364], and the mapping formula is as follows:

Q=81Q₁+9Q₂+Q₃

2.2 prediction error calculation

In order to facilitate hardware implementation, a predictor in predictive coding selects a median edge detection predictor with a small calculation amount, and the predictor completes prediction by detecting edge information around a current pixel point. If I _A≥max(I_B,I_D), I _B≥I_D indicates that there is a horizontal edge near the current pixel, and the predicted value takes the gray value of the left side of the current pixel, i.e., P _X＝I_D, and if I _B<I_D indicates that there is a vertical edge near the current pixel, and the predicted value takes the gray value of the top of the current pixel, i.e., P _X＝I_B. The same applies when I _A≤min(I_B,I_D). If there is no edge near the current pixel, P _X＝I_B+I_D-I_A. The predicted value P _X is expressed by the following formula:

in order to prevent the overlarge prediction error in the subsequent calculation, the correction is carried out after the calculation of the predicted value, and the correction process is as follows:

In the formula, sign is a symbol variable for judging the overturn, CQ is an average prediction error, and the average prediction error is taken as a prediction correction value and belongs to one of the context parameters.

When the correction of the predicted value is completed, the predicted error is the difference between the gray value and the predicted value:

2.3 prediction error Rice coding

The Rice coding is suitable for lossless compression of non-negative integer sequences conforming to geometric distribution, and the prediction error is subjected to bilateral geometric distribution, so before the Rice coding is performed, the prediction error needs to be mapped to be subjected to geometric distribution, and the method specifically comprises the following steps:

after mapping, rice coding is carried out, parameters k and q needed in the coding process are calculated firstly, and the calculation process is as follows:

The parameter k is used to remove the length of each field in the top-removing Rice coding, the parameter Q represents the quotient in the Rice coding calculation process, N [ Q ] and A [ Q ] are context parameters, N [ Q ] represents the occurrence times of the current context type, and A [ Q ] represents the sum of absolute values of prediction errors.

2.4 Context parameter update

Each context type has a corresponding set of context parameters that are used to correct prediction errors, select an appropriate coding scheme, etc. The context parameters mainly include the following:

(1) AQ is the absolute value sum of prediction error, which is used to estimate the parameter k of Rice coding.

(2) And B < Q > is a prediction error sum used to assist in calculating an average prediction error CQ.

(3) And CQ is average prediction error for correcting the predicted value of pixel point.

(4) N [ Q ]: number of occurrences of current context type.

The context parameters need to be updated after each encoding is finished, and the updating process is as follows:

Wherein errval is a prediction error, Q is an index value, and the value is [0,364] corresponding to 365 context types.

3. Run-length coding mode

As shown in fig. 7, which is a flowchart of a run-length encoding mode, when a pixel is located in a flat region of an image, the encoder will select a run-length encoding to compress. The method comprises the steps of firstly scanning the pixel points to be coded in a run length mode, namely counting the number of the pixel points with the same gray value continuously appearing, and secondly carrying out different treatments according to the reason of scanning termination. If the pixels with different gray values are scanned, the run length is coded, then the run coding mode is exited, and if the pixels with different gray values are scanned, the run coding mode is exited, and the prediction mode is returned to for performing the prediction coding on the difference pixels.

When coding the run length, in order to avoid the overflow of the memory caused by the overlarge run length, the invention designs a method for coding the run length by using a table lookup:

As shown in FIG. 8, each element in the table represents a run length, denoted as 2 ^rk. The encoder sweeps each element in turn along index and accumulates the run lengths represented by each element. And stopping scanning when the accumulated value is greater than or equal to the actual run length.

The experimental process comprises the following steps:

in order to cover different star map types, four typical star maps with different backgrounds are selected for performing performance test of a lossless compression algorithm, wherein the star maps are respectively a star map with a single background, a star map with a complex background, a star map with interference in the background and a pure black star map, as shown in fig. 9.

Firstly, a lossless compression algorithm is realized through software, lossless compression and decompression experiments are carried out on each star map, secondly, the numerical values of various indexes are analyzed, and finally, the differences of experimental results of different star maps are compared, and corresponding conclusions are obtained.

1. Single background star map experimental results

Experimental data obtained after compressing and decompressing a star map with a single background by using the lossless compression algorithm of the invention are shown in table 1.

Table 1 evaluation index of lossless compression algorithm (background single star chart)

As can be seen from the experimental data in Table 1, the star map has low complexity, can achieve a compression ratio of 2.7355:1 after using a lossless compression algorithm, which indicates that the original map has more information redundancy, and has a coding efficiency of 0.8158, which indicates that the compressed data is close to the theoretical shortest compression code length. The results show that the lossless compression algorithm effectively removes information redundancy in the original image.

2. Star map experimental result with complex background

The experimental data obtained after compressing and decompressing the star map with complex background by using the lossless compression algorithm of the invention are shown in table 2.

Table 2 evaluation index of lossless compression algorithm (background complex star chart)

The experimental data in table 2 show that the compression ratio and the relative redundancy of the star map with complex background are lower than those of the star map with single background, which indicates that the internal information redundancy of the image with complex background is less and the potential of lossless compression is also less.

The coding efficiency is very close to 1, which indicates that the average code length of the compressed data is almost equal to the theoretical shortest compressed code length, which also reflects that it is difficult to achieve a high lossless compression ratio for images with complex backgrounds.

3. Star map experimental result with interference on background

Experimental data obtained after compressing and decompressing star images with interference on the background by using the lossless compression algorithm of the invention are shown in table 3.

Table 3 evaluation index of lossless compression algorithm (background with interference star chart)

From the experimental data in table 3, it is shown that the image complexity of the star map with interference on the background is higher than that of the star map with single background, but lower than that of the star map with complex background, which indicates that the overall image is smoother in spite of some interference information in the star map background. The star map with interference can obtain a higher compression ratio of 2.5654:1 by using a lossless compression algorithm, which indicates that the star map with interference on the background has more internal information redundancy and a larger lossless compression space. But the compression ratio is lower than that of the image with single background, which means that the compression effect is not as good as that of the image with single background.

4. Experimental results of pure Black Star

Experimental data obtained after compressing and decompressing pure black star images using the lossless compression algorithm of the present invention are shown in table 4.

Table 4 evaluation index of lossless compression algorithm (pure black star chart)

Experimental data shows that the background complexity of the pure black image is 0, which indicates that the inside of the pure black image is very smooth and the pixel value is single. The extremely high compression ratio of 18927.3616:1 can be obtained after the lossless compression algorithm is used, which shows that the pure black image has a lot of internal information redundancy and the lossless compression space is huge. The compression effect is more pronounced compared to any star map.

However, for a pure black image, the ideal compression code length is 0 and the coding efficiency is 0. This is because from the viewpoint of information theory, an information source that outputs only one element has no information amount because the probability of each occurrence of its output element is 100%, and there is no uncertainty, i.e., the amount of uncertainty is not eliminated. It is therefore meaningless to use the coding efficiency index for solid-color images.

Analysis of experimental results

The compression ratio and the relative redundancy of the image are reduced along with the increase of the complexity of the image, the information redundancy of the image with higher complexity is less, and the potential of lossless compression is also less. Therefore, the lossless compression algorithm has better compression effect for images with smooth and clean background.

The coding efficiency is improved along with the increase of the image complexity, the lossless compression algorithm can better utilize the compression space of the image with higher complexity to enable the image to be closer to the theoretical optimal compression state, but the lossless compression algorithm also shows that the theoretical compression space of the star map with complex background is smaller, and higher compression ratio is difficult to realize. For a single star map with a background, the theoretical compression space is larger, and the lossless compression algorithm needs to process more information redundancy, and can obtain a higher compression ratio although the coding efficiency is lower.

The foregoing is merely exemplary embodiments of the present application, and detailed technical solutions or features that are well known in the art will not be described in detail herein. It will be apparent to those skilled in the art that various modifications and improvements can be made without departing from the technical scope of the application, and these should also be regarded as the scope of the application, which does not affect the effect of the application and the practical applicability of the patent. The protection scope of the present application is subject to the content of the claims, and the description of the specific embodiments and the like in the specification can be used for explaining the content of the claims.

Claims (3)

1. A fast star map lossless compression algorithm, comprising:

The context modeling is that the region types are divided according to the local gradient value Q _i of the current pixel to be coded, and a corresponding coding mode is selected, and the calculation formula of the local gradient value Q _i is as follows:

Selecting a run-length coding mode for compression when the pixel to be coded and the adjacent pixel form a flat area, and selecting a predictive coding mode for compression when the pixel to be coded and the adjacent pixel form a non-flat area;

the predictive coding mode steps are as follows:

a1, gradient quantization merging, namely dividing a local gradient value into symmetrical intervals with medium dense edges, wherein the dividing process is as follows, and the local gradient value is divided into 9 intervals in total:

After Q _i is spliced into a vector (Q ₁,Q₂,Q₃) in sequence, the Sign change is carried out on the vector, and the specific steps are that the first nonzero number appearing in Q ₁,Q₂,Q₃ is checked in sequence, if the first nonzero number is positive, the Sign variable Sign is set to be 1, (Q ₁,Q₂,Q₃) is kept unchanged, if the first nonzero number is negative, the Sign variable Sign is set to be-1, and the inverse of (Q ₁,Q₂,Q₃) is changed to (-Q ₁,-Q₂,-Q₃);

Finally, the vector (Q ₁,Q₂,Q₃) is mapped to an integer Q in the interval [0,364] according to the following mapping formula:

Q=81Q₁+9Q₂+Q₃

A2, calculating a prediction error, namely selecting a median edge detection prediction period with small calculation amount in the prediction period in the prediction coding, wherein the prediction value Px is expressed by the following formula:

The prediction error is the difference between the gray value and the predicted value:

a3, prediction error Rice coding, wherein before Rice coding, the prediction error is mapped to be subjected to geometric distribution, and the method concretely comprises the following steps:

after mapping, rice coding is carried out, parameters k and q needed in the coding process are calculated firstly, and the calculation process is as follows:

The parameter k is used to remove the length of each field in the top-removing Rice code, the parameter Q represents the quotient in the Rice code calculation process, N [ Q ] and A [ Q ] are context parameters, N [ Q ] represents the occurrence times of the current context type, and A [ Q ] represents the sum of the absolute values of the prediction errors;

and A4, updating the context parameters, namely updating the context parameters after the coding is finished each time, wherein the updating process is as follows:

Wherein errval is the prediction error, Q is the index value, the value is [0,364] corresponding to 365 context types, A [ Q ] is the absolute sum of the prediction error, which is used for estimating the parameter k of Rice coding;

The run-length coding mode comprises the steps of firstly counting the number of pixel points with the same gray value which continuously appear, carrying out different processing according to the reason of scanning termination, if the pixels at the end of a line are not scanned, coding the run-length and then exiting the run-length coding mode, if the pixels with different gray values are scanned, then exiting the run-length coding mode and returning to the predictive coding mode to carry out predictive coding on the difference pixels.

2. A fast star map lossless compression algorithm according to claim 1, wherein in the run-length encoding mode, to avoid memory overflow caused by excessive run-length, a method of run-length encoding using a look-up table is designed, in which an encoder scans each element in turn along index, accumulates the run-lengths represented by each element, and stops scanning when the accumulated value is equal to or greater than the actual run-length.

3. The fast star map lossless compression algorithm according to claim 1, wherein in step A2 in the predictive coding mode, in order to prevent the prediction error from being excessively large in the subsequent calculation, the correction is performed after the calculation of the predicted value, and the correction process is as follows:

In the formula, sign is the sign variable for judging the turnover, and CQ is the average prediction error.