TWI432031B - Distortion-free image compression method - Google Patents

Description

Imageless compression method

The present invention relates to a distortion-free image compression method, and more particularly to a distortion-free image compression method that requires less memory space.

With advances in electronics and information technology, technological advances in processing and displaying images on computers or a wide variety of electronic devices are becoming more common. Early electronic information technology could only store or process digital pixels with lower pixels. However, there is an increasing demand for high-quality images, and how to handle and store high-quality images has become a hot topic. In order to obtain high-quality images, distortion-free compression is often used for image compression.

However, high-quality images without distortion need to store higher pixels, which poses a challenge to the computing speed of the computer and the capacity of the storage medium. For example, in the distortion-free compression algorithm, the Joint photographic experts group Lossless (JPEG-LS) uses prediction and context modeling to achieve a better compression ratio. The former mode requires a full row of pixels of the temporary image to be able to perform prediction in various modes, thus requiring a large amount of computation and storage space, and the cost required for the encoder is increased. And JPEG-LS has a higher computational complexity for applications that do not require high compression ratios, and increases the burden on the encoder.

In addition, the user's requirements for image resolution are getting higher and higher, and the burden on image compression is also increased. If the conventional distortion-free compression method is used, once the resolution of the image is increased, the encoder takes a long time and a large amount of storage space to be processed into a high-quality image. In other words, the conventional distortion-free compression method has a problem that the computational complexity is too high, resulting in low computational efficiency, and a large amount of temporary storage space.

Therefore, how to design a distortion-free compression method that is capable of balancing high visual quality, low computational complexity, and low temporary storage space is quite important in the industry.

In order to solve the above problems, the present invention provides a lossless (also known as lossless) image compression method. The distortion-free image compression method requires less memory space and can process an image with multiple pixels at a faster rate. The image has an image width of W. The distortion-free image compression method comprises the following steps: (a) selecting successive N pixels from the image, wherein N is a positive integer greater than or equal to 2, and N is smaller than the image width W; (b) performing a differential pulse wave Differential pulse code modulation (DPCM) means to obtain N non-negative difference values corresponding to the N pixels according to the values of the N pixels; (c) calculating according to the N non-negative difference values a coding parameter; and (d) encoding the N non-negative differences according to the coding parameters.

In order to compress the entire image, the distortion-free image compression method may further comprise the steps of: (e) successively selecting the next N consecutive pixels of the image; and (f) returning to step (b) until all pixels of the image are compressed. .

Wherein step (a) can directly receive the selected N pixels in the image by a temporary register.

The differential pulse code modulation means of the step (b) may include: obtaining N pixel difference values corresponding to the N pixels according to the values of the N pixels; and performing an individual for the N pixel difference values. Mapping means to obtain N non-negative difference values that individually correspond to the N pixel difference values.

According to an embodiment of the present invention, the step of: obtaining N pixel difference values corresponding to the N pixels according to the values of the N pixels may include: determining a value of the first pixel of the N pixels P _{0 is the} first pixel difference value d ₀ ; and the difference between the value P _i of the ith pixel of the N pixels and the value P _i-1 of the previous pixel is calculated as the other N-1 pixel differences Value, where i is a positive integer and 0 < i < N.

The transforming means may further include: when the ith pixel difference value d _{i of the} N pixel difference values is greater than or equal to zero, the corresponding ith non-negative number difference value n _i is the pixel difference value d _i multiplied by 2, wherein 0<=i=N; and when the i-th pixel difference d _{i of the} N pixel difference values is less than zero, the corresponding i-th non-negative difference value n _i is the pixel difference value d _i multiplied by 2 Minus 1.

The encoding parameter used to encode the N non-negative difference values may be Where n _{i is the ith} non-negative difference in the N non-negative difference values.

The above step (d) may include: encoding the N non-negative difference values by a Golomb-Rice code according to the encoding parameters.

In summary, the distortion-free image compression method according to the present invention selects N pixels in the image and encodes the values of the N pixels by variable length coding. The processing of the N pixels does not require the use of other pixels in the image, so the encoder's scratchpad does not need to save the values of other pixels. Therefore, the image compression method without distortion has the advantages of saving a large amount of temporary storage space, and the compression method is simple and efficient.

The detailed features and advantages of the present invention are set forth in the Detailed Description of the Detailed Description of the <RTIgt; </ RTI> <RTIgt; </ RTI> </ RTI> </ RTI> <RTIgt; The objects and advantages associated with the present invention can be readily understood by those skilled in the art.

The present invention provides a lossless (also known as lossless) image compression method for processing an image having a plurality of pixels to compress an image. The distortion-free image compression method can be implemented as an encoder.

Please refer to FIG. 1 and FIG. 2, which are flowcharts of an image and a distortion-free image compression method according to an embodiment of the present invention, respectively.

Image 20 has WxL pixels, where W is an image width of image 20 and L is an image length. For example, image 20 may have 640 x 480 pixels or 128 x 128 pixels; then image width W will be 640 (pixels) or 128 (pixels). Since the pixels in the same row in the image 20 have strong correlation with each other, they can be utilized for image compression.

When the distortion-free image compression method is performed, successive N pixels are first selected from the image 20 (step S30); wherein N is a positive integer greater than or equal to 2, and N is smaller than the image width W. In order to perform the distortion-free image compression method more efficiently, the value of the image width W can be divisible as N. In other words, N can divise the image width W of the image 20. For example, when the image width W is 128 (pixels), N may be 16. The step S30 of selecting consecutive N pixels can be implemented by a processing window 22. The length of the processing window 22 is N, and the N pixels framed by the processing window 22 are N pixels compressed according to the following flow.

The encoder has a buffer to temporarily store the portion of the image 20 that needs to be processed in the scratchpad. In more detail, the image 20 may be a file stored in a memory, or may be image data transmitted by a photosensitive unit of an image capturing device. In step S30, the consecutive N pixels are selected in the image 20 received by the memory or the photosensitive unit, and the values P ₀ to P _{N-1 of the} N pixels are directly received by the register.

Therefore, when the image compression method without distortion is used to compress the image 20, only N pixels of the processing window 22 are needed, and other pixels in the image 20 are not needed. Therefore, only the N pixels need to be stored in the register of the encoder, and the entire row of W pixels in the image 20 need not be stored.

After selecting consecutive N pixels, a differential pulse code modulation (DPCM) method is performed on the N pixels; corresponding to the values P ₀ ～ P _{N-1 of the} N pixels N non-negative difference values n ₀ to n _N-1 of N pixels (step S40). The value of the pixel may be, for example, a grayscale value, an RGB value, or a hue, saturation, and lightness of the HSL color space. The distortion-free image compression method does not limit the content of the pixel values.

Please refer to FIG. 3, which is a flowchart of a differential pulse code modulation method according to an embodiment of the present invention.

The distortion-free image compression method uses the differential pulse code modulation means to obtain N non-negative difference values n ₀ to n _N-1 corresponding to the processing window 22 for distortion-free compression. The differential pulse code modulation means may first obtain N pixel difference values d ₀ to d _N-1 corresponding to the N pixels based on the values P ₀ to P _N-1 of the N pixels (step S41). Then, a mapping means is performed on the N pixel difference values to obtain N non-negative difference values n ₀ to n _N-1 corresponding to the N pixel difference values (step S46).

Please refer to "Fig. 3" and refer to "Fig. 4" and "Fig. 5", which are flowcharts of step S41 according to an embodiment of the present invention, and a flow chart of the changing means in step S46, respectively.

In step S41, the pixel difference values d ₀ to d _N-1 can be calculated according to the following "Formula 1" and "Formula 2".

d ₀ =P ₀ ............................................. ............................Formula 1

d _i =P _i -P _i-1 , 0<i<N, and i is a positive integer.

Where P ₀ is the value of the first of the N pixels in the processing window 22, and P _i is the value of the ith pixel of the N pixels in the processing window 22. And d ₀ is the pixel difference corresponding to P ₀ , and d _i is the pixel difference corresponding to P _i .

"Formula 1" takes the value P ₀ of the first pixel among the N pixels as the first pixel difference value d ₀ (step S42). "Formula 2" This value of the N pixels P _i of the i-th pixel and its preceding pixel P _i-1 values were calculated difference, as other N-1 pixel difference value d ₁ ~ d _N-1, Where 0 < i < N (step S43). In other words, the pixel difference values d ₁ to d _N-1 are obtained by subtracting the values P ₀ to P _N-1 of the adjacent pixels.

According to another embodiment of the present invention, the value P _-1 of the previous pixel of the first pixel of the processing window 22 in the image 20 can be saved. The value of the first pixel difference value d ₀ corresponding to the processing window 22 is the difference between P ₀ and P _-1 .

After obtaining the pixel difference values d ₀ to d _N-1 corresponding to the processing window 22 in step S41, the conversion means may first determine whether the pixel difference values d _i are greater than or equal to 0 (step S47), and then according to the following formula 3 And "Formula 4" calculate the non-negative difference n ₀ ~ n _N-1 .

n _i = 2 × d _i , if d _i ≧0..................................... ...............3

n _i = 2 × d _i -1, if d _i <0................................... ..............Form 4

Where n _i is the value of the i-th pixel of the N non-negative difference values n ₀ to n _N-1 , and 0 ≦ i < N.

For a pixel difference value d _i greater than or equal to 0, "Formula 3" multiplies the pixel difference value d _i by 2 as a non-negative difference value n _i . That is, the non-negative difference value n _i is the pixel difference value d _i multiplied by 2 (step S48). For a pixel difference value d _i smaller than 0, "Expression 4" is a value obtained by multiplying the pixel difference value d _i by 2 and subtracting 1 as a non-negative difference value n _i . That is, the non-negative difference value n _i is the pixel difference value d _i multiplied by 2 and then decreased by 1 (step S49).

In this way, N non-negative difference values n ₀ to n _N-1 corresponding to the N pixels can be obtained according to the values P ₀ to P _{N-1 of the} N pixels in step S40.

Please return to "Figure 2." Then, according to the N non-negative difference values n ₀ ～ n _N-1 , a coding parameter k is calculated (step S50); and according to the coding parameter k, the N non-negative difference values n ₀ ～ n _N-1 is encoded (step S60).

The step S60 may include: encoding the N non-negative difference values n ₀ ～ n _N-1 according to the coding parameter k by a Golomb-Rice code.

The encoding parameter used to process the N non-negative difference values may be .

The Columbus-Rice code is a variable-length code (VLC) that encodes a higher probability value for a shorter one. According to the Columbus-Les code, a divisor m is first set according to the coding parameter k. By dividing the N non-negative difference values n ₀ to n _N-1 by the divisor m, the corresponding N quotients Q and the remainder R are obtained. Where the divisor m is the kth power (2 ^k ) of 2.

The Columbus-Rice code then encodes the resulting quotient Q into a unary code and encodes the number R into a binary code of length k bits.

For example, assume that the non-negative difference n ₀ is 163 and the encoding parameter k is 5. Therefore, the quotient Q of the non-negative difference n ₀ can be calculated as 5, and the remainder R is 3. Then, the quotient Q of the non-negative difference value n ₀ can be encoded as "111110" by the unary code, and the remainder R is encoded as "00011" by the binary code.

In this way, the values P ₀ to P _N-1 of the N pixels in the processing window 22 can be compressed into distortion-free variable length coding. The entire image 20 can be compressed by a distortion-free image compression method. Please refer to FIG. 6 , which is a flowchart of a distortion-free image compression method according to another embodiment of the present invention.

After performing the steps S30 to S60 to compress the N pixels of the processing window 22, it is further determined whether or not all the pixels of the image 20 are compressed (step S70). If the image 20 has not been completely compressed, the next N consecutive pixels of the image 20 are successively selected (step S80), and the selected N pixels in step S80 are processed in steps S40, S50, and S60. If the image 20 has been compressed to a compressed image file, it can end.

That is to say, the distortion-free image compression method is that the N pixels selected in step S30 are successively selected to select another N pixels, and the additionally selected N pixels are processed as the new processing window 22.

In summary, the distortion-free image compression method according to the present invention selects N pixels in the image and encodes the values of the selected pixels with variable length coding. Since the other pixels in the image are not needed during compression, the register of the encoder only needs to save the values of the N pixels, and can save a lot of temporary storage space. The distortion-free image compression method only processes N pixel values in each image window one by one to compress a complete image, and has the advantages of simple and efficient compression mode.

20. . . image

twenty two. . . Processing window

1 is a schematic diagram of an image according to an embodiment of the present invention;

2 is a flow chart of a distortion-free image compression method according to an embodiment of the present invention;

Figure 3 is a flow chart of a differential pulse code modulation means according to an embodiment of the present invention;

Figure 4 is a flow chart of step S41 according to an embodiment of the present invention;

Figure 5 is a flow chart of a transformation means according to an embodiment of the present invention;

Figure 6 is a flow chart of a distortion-free image compression method according to another embodiment of the present invention.

Claims (8)

A distortion-free image compression method for processing an image having a plurality of pixels, wherein an image width of the image is W, and the distortion-free image compression method comprises: (a) selecting consecutive N from the image The pixels, wherein N is a positive integer greater than or equal to 2, and N is less than the image width W; (b) performing a differential pulse code modulation means to obtain corresponding N according to the values of the N pixels N non-negative difference values of the pixels; (c) calculating an encoding parameter according to the N non-negative difference values; and (d) encoding the N non-negative difference values according to the encoding parameters. The distortion-free image compression method of claim 1, further comprising: (e) successively selecting the next N consecutive pixels of the image; and (f) returning to step (b) until the compression is completed. All of these pixels of the image. The distortion-free image compression method of claim 1, wherein the differential pulse code modulation means comprises: obtaining N pixel difference values corresponding to the N pixels according to the values of the N pixels. And performing a transforming means for the N pixel difference values to obtain the N non-negative difference values individually corresponding to the N pixel difference values. The distortion-free image compression method of claim 3, wherein the step of obtaining N pixel difference values corresponding to the N pixels according to the values of the N pixels comprises: N pixels the first one of the pixel value P ₀ as the first one of the pixel difference value d _0; and calculates a value of the pixel prior to its i-th value of the pixel of the N pixels P _i P _i- The difference of ₁ is taken as the other N-1 pixel difference values, where i is a positive integer and 0 < i < N. The distortion-free image compression method of claim 3, wherein the transforming means comprises: when the i-th pixel difference d _{i of} the N pixel difference values is greater than or equal to zero, the corresponding i-th the difference is a non-negative n _i D _i for the pixel difference value is multiplied by 2, where 0 <= i <N; and when the difference in the N pixels of the i-th pixel difference D _i is less than zero, the corresponding The i-th non-negative difference n _{i is} the pixel difference d _i multiplied by 2 and then decremented by one. The distortion-free image compression method according to claim 1, wherein the coding parameter is Where n _{i is the ith of} the N non-negative difference values of the non-negative difference. The distortion-free image compression method of claim 1, wherein the step (d) comprises: encoding the N non-negative difference values by a Columbus-Rice code according to the encoding parameter. The distortion-free image compression method according to claim 1, wherein the step (a) directly receives the selected N pixels in the image by a temporary register.