TW202046727A - Lossless image compression method achieving a high throughput of 6.4G (pixel/sec) and meeting the real-time compression requirements for 4K images - Google Patents

Abstract

The present invention is a lossless image compression method, including capturing a 16x8 image block and dividing it into root pixels, multiple trunk pixels, multiple branch pixels, multiple left-leaf pixels, multiple right-leaf pixels, and calculating the residual value of the trunk pixels, calculating the residual value of the branch pixels, calculating the residual value of the left-leaf pixels, calculating the residual value of the right-leaf pixels, dividing the 16x8 image block into the original pixels, the first pixel group, the second pixel group, the third pixel group, the fourth pixel group, the fifth pixel group, the sixth pixel group, and the seventh pixel group, setting the encoding header of each pixel group, connecting the root pixels, multiple encoding headers and multiple residual values to generate a compressed data string. Therefore, the lossless image compression method of the present invention can achieve a high throughput of 6.4G (pixel/sec) and can meet the real-time compression requirements for 4K images.

Description

Lossless image compression method

The present invention relates to a lossless image compression method, in particular to lossless image compression and hardware design, which utilizes 4K resolution throughput and low complexity algorithms to meet 4K resolution throughput requirements.

With the advancement of technology, high-definition (HD) images/videos have become an important feature of modern display technology. Recently, HD has been upgraded from 1,920×1,080 (1080p) to 3,840×2,160 (2160p or 4K). This trend has pushed video compression standards to handle high-definition video content, making H.264/AVC adopted as the video compression standard for 1080p Blu-ray Discs.

However, this development trend brings two design challenges to video coding systems: large throughput and huge memory bandwidth. Although advanced CMOS technology and appropriate parallel processing or pipeline technology can solve the huge throughput problem, the above-mentioned methods cannot solve the huge memory bandwidth. The reason is that the challenge of this design lies in some memory-intensive video coding processes, such as motion estimation, intra prediction and filtering. At present, this bottleneck can be solved by embedded compression, and its embedded compression can be divided into two types: lossy embedded compression and lossless embedded compression. The error generated by lossy embedded compression will reduce the quality of visual effects. The lossless embedded compression can not only provide acceptable compression rates, but also maintain visual quality.

Furthermore, embedded compression can be used to reduce the memory bandwidth between the video encoding system and the frame memory. However, the throughput of the algorithm must be able to support the resolution provided by the display device.

More specifically, predictive coding is a commonly used technology in image compression, and it has a long history. It can be traced back to the Delta coding (Delta modulation) proposed in the 1940s, and we can still see it often today. The technology of linear predictive coding is continuously improved, innovated and strengthened. In short, predictive coding is a coding method that belongs to the time domain. His basic idea is to use the symbols that have appeared before to predict the current symbol, and then obtain the prediction error from the actual symbol and the predicted symbol, encode and send the error.

The above-mentioned coding method for the prediction error can be a lossless data compression method or a distortion data compression method. If the former is adopted, the entire system is still a distortion-free data compression method; on the contrary, if the latter is adopted, the entire system becomes a distortion-free data compression method. Therefore, predictive coding is not only a lossless data compression method, but also a distortion data compression method. The motivation for using predictive coding is that the change of the error signal is much smaller than that of the original signal, so we can use fewer bits to encode each error signal sample to achieve the purpose of data compression.

As 4K resolution images gradually become the mainstream specifications, in order to meet throughput requirements, the algorithms of conventional technologies will cause excessive hardware area and excessive power consumption, which in turn will cause the system to overheat and risk crashes.

Moreover, most of the existing image lossless compression technologies cannot meet the real-time compression requirements of 4K images. Although there are a small number of algorithm technologies that can meet the real-time compression, the compression rate is insufficient, which places a greater burden on the memory transmission bandwidth, which often occurs The problem of missing data.

Therefore, there is a great need for an innovative lossless image compression method that uses a low-complexity algorithm to achieve the specific effects of high image quality, high throughput, lossless compression, low hardware area, and low power consumption, so as to solve the above-mentioned conventional technology. All questions.

The main purpose of the present invention is to provide a lossless image compression method that utilizes prediction processing and encoding processing to realize the function of lossless image compression. Specifically, the lossless image compression method of the present invention includes capturing a 16x8 image block in the input image data as a processing block, and the processing block includes 16x8 pixels arranged in a matrix, and then all pixels of the processing block Divide into root pixels, multiple stem pixels, multiple branch pixels, multiple left leaf pixels, and multiple right leaf pixels.

Furthermore, the root pixel is the pixel (1, 1) in the 16x8 pixel, which is located in the upper left corner of the processing block, and the dry pixels are pixels (1, 2) to (1, 16). The branches Pixels are pixels on the diagonal of pixels (6, 2) to (8, 12). The left-leaf pixels are pixels located to the left of the branch pixels and between the root pixel and the stem pixels. The equal right leaf pixels are pixels located to the right of the branch pixels and between the stem pixels.

Then, the residual value of each dry pixel in the processing block is calculated to obtain the residual value of each dry pixel, and the residual value is r, and expressed as r=PC-PL, where PC is the dry pixel and PL is The pixel to the left of the dry pixel.

Similarly, calculate the residual value of each branch pixel in the processing block to obtain the residual value of each branch pixel, and the residual value is r, and expressed as r=C-PT, where PC is the branch pixel , And PT is the dry pixel above the branch pixel.

After that, the residual value of each left-leaf pixel in the processing block is calculated to obtain the residual value of each left-leaf pixel, and the residual value is r, which is expressed as r=PC-HL1, PC-HL2, PC-HL3 HL1 is (PRT+PT)/2, HL2 is (PR+PT)/2, HL3 is (PRT+PR)/2, PM is the minimum of HL1, HL2, and HL3, and if PM is HL1, then r is PC-HL1, if PM is HL2, then r is PC-HL2, if PM is HL3, then r is PC-HL3.

The residual value of each right-leaf pixel in the processing block is calculated to obtain the residual value of each right-leaf pixel, and the residual value is r, which is expressed as r=PC-HR1, PC-HR2, PC-HR3 One of them, where HR1 is (PLT+PT)/2, HR2 is (PL+PT)/2, HR3 is (PLT+PL)/2, PM is the minimum of HR1, HR2, and HR3, and if PM If it is HR1, then r is PC-HR1, if PM is HR2, then r is PC-HR2, if PM is HR3, then r is PC-HR3.

Divide the pixels of the 16x8 image block into original pixels, first pixel group, second pixel group, third pixel group, fourth pixel group, fifth pixel group, sixth pixel group, and seventh pixel group Pixel group, where the original pixel is the root pixel, the first pixel group contains all the dry pixels, the second pixel group contains all the branch pixels except the pixel (8, 12), and the third pixel group contains all All pixels in the block from pixel (2,1) to pixel (8,4) in the left-leaf pixel, the fourth pixel group includes all the left-leaf pixels except the third pixel group and pixels (8,5) to Pixels (8, 11) are arranged horizontally except for all the remaining pixels. The fifth pixel group includes all the right-leaf pixels except for the remaining pixels below the pixel (5, 10) to the pixel (5, 16) , The sixth pixel group includes all right-leaf pixels except the fifth pixel group and the pixels (8, 13) to pixels (8, 16) arranged horizontally except for the remaining pixels. The seventh pixel group includes the pixel (8, 1) All horizontally arranged pixels from pixel (8, 16).

For each pixel group, a coding header is set according to the absolute value range of the residual value corresponding to each pixel, and the coding header is represented by three bits.

Finally, according to the preset arrangement sequence, the root pixel, the code header and the residual value are concatenated to generate the compressed data string corresponding to the 16x8 image block, or called the bit string.

More specifically, the aforementioned arrangement order refers to the first pixel group including the root pixel, the encoding header of the first pixel group to the encoding header of the seventh pixel group, and the residual value of each pixel in the first pixel group. To the residual value of each pixel in the seventh pixel group.

The lossless image compression method of the present invention can reduce the memory bandwidth, and achieve a high throughput of 6.4G (pixel/sec), can meet the real-time compression requirements of 4K images, and is very suitable for applications that require fast and real-time image compression.

The following is a more detailed description of the implementation of the present invention in conjunction with the drawings and component symbols, so that those who are familiar with the art can implement it after studying this manual.

Please refer to the first figure, which is an operation flowchart of a lossless image compression method according to an embodiment of the present invention. As shown in the first figure, the lossless image compression method of the present invention includes steps S10, S20, S30, S40, S50, S60, S70, S80, which are used to perform prediction processing and encoding processing on the input image data to achieve lossless image compression The function can greatly reduce the required memory bandwidth and maintain high-quality images.

First of all, the lossless image compression method of the present invention starts from step S10, which mainly captures 16x8 image blocks in the input image data as processing blocks, that is, the processing blocks include 16x8 pixels arranged in a matrix, and These pixels are divided into different groups. As shown in the second figure, the pixel (1, 1) is located in the upper left corner of the processing block, called the root pixel RT, and the pixels (1, 2) to (1, 16) start from the pixels adjacent to the root pixel The pixel on the right to the right edge is called the dry pixel T. The pixel on the diagonal of pixels (6, 2) to (8, 12) is the branch pixel B, which is located on the left side of the branch pixel and the root pixel and the dry pixel The pixel in between is the left leaf pixel LL, and the pixel located to the right of the branch pixel and between the stem pixels is the right leaf pixel RL.

For the convenience of the following description, as shown in the third figure, the pixel PC is regarded as the target pixel, and the pixels above, left, right, upper left, and upper right of the pixel PC are respectively regarded as the upper pixel PT, the left pixel PL, and the right pixel. PR, upper left pixel PLT, upper right pixel PRT.

Then, go to step S20, perform residual value calculation on each dry pixel T in the processing block to obtain the residual value r of the dry pixel T, and the residual value r is PC-PL, where PC is the dry pixel and PL is The pixel to the left of the dry pixel.

In step S30, the residual value calculation is performed on each branch pixel B in the processing block to obtain the residual value r of the branch pixel B, and the residual value r is PC-PT, where PC is the branch pixel, and PT is the dry pixel above the branch pixel.

In step S40, the residual value of each left-leaf pixel LL in the processing block is calculated to obtain the residual value r of the left-leaf pixel LL, and the residual value r is the value of PC-HL1, PC-HL2, PC-HL3 One of them, where HL1 is (PRT+PT)/2, HL2 is (PR+PT)/2, HL3 is (PRT+PR)/2, and PM is the minimum of HL1, HL2, and HL3, and If PM is HL1, then the residual value r is PC-HL1, if PM is HL2, then the residual value r is PC-HL2, if PM is HL3, then the residual value r is PC-HL3.

In step S50, the residual value of each right-leaf pixel RL in the processing block is calculated to obtain the residual value r of the right-leaf pixel RL, and the residual value r is the value of PC-HR1, PC-HR2, PC-HR3 One of them, where HR1 is (PLT+PT)/2, HR2 is (PL+PT)/2, HR3 is (PLT+PL)/2, and PM is the minimum of HR1, HR2, and HR3, and If PM is HR1, then the residual value r is PC-HR1, if PM is HR2, then the residual value r is PC-HR2, if PM is HR3, then the residual value r is PC-HR3.

Specifically, the aforementioned steps S20, S30, S40, and S50 belong to the prediction process, and the residual value r of each pixel can be obtained.

After that, the process of encoding processing includes steps S60, S70, and S80.

First, go to step S60. According to the fourth figure, divide the 16x8 image block into the original pixel R, the first pixel group G1, the second pixel group G2, the third pixel group G3, the fourth pixel group G4, and the fourth pixel group G2. The five pixel group G5, the sixth pixel group G6, and the seventh pixel group G7. Specifically, the original pixel R is the above-mentioned root pixel, the first pixel group G1 includes all dry pixels, the second pixel group G2 includes all branch pixels except the pixel (8, 12), and the third pixel Group G3 includes all the pixels in the block from pixel (2,1) to pixel (8,4) in all the left-leaf pixels, totaling 6x4, a total of 24 pixels, the fourth pixel group G4 includes all the left-leaf pixels except the third Pixel group G3 and pixels (8, 5) to pixels (8, 11) are arranged horizontally except for the remaining pixels. The fifth pixel group G5 includes all the pixels located in the right leaf except for pixels (5, 10) to pixels ( 5, 16) The remaining pixels of the pixels below, the sixth pixel group G6 includes all right-leaf pixels except for the fifth pixel group G5 and the pixels (8, 13) to (8, 16) horizontally arranged. Pixels, the seventh pixel group G7 includes all the pixels arranged horizontally from the pixel (8, 1) to the pixel (8, 16).

In step S70, for each pixel group, according to the absolute value range of the residual value corresponding to each pixel, a coding header is set and represented by three bits. Specifically, when the residual value of all pixels is 0, the coding header is 000; when the absolute value of the residual value is in the range of 0 to 1, the coding header is 001; when the absolute value of the residual value is in the range 0~3, the coding header is 010; when the absolute value of the residual value is in the range of 0-7, the coding header is 011; when the absolute value of the residual value is in the range of 0-15, the coding header is 100 ; When the absolute value of the residual value ranges from 0 to 31, the coding header is 101; when the absolute value of the residual value ranges from 0 to 63, the coding header is 110; when the absolute value of the residual value exceeds the range 0~63, the code header is 111.

In step S80, the root pixel, multiple encoding headers, and multiple residual values are concatenated according to a preset arrangement order to generate a compressed data string corresponding to a 16x8 image block, or called a bit string (bitstearm) , Wherein the preset arrangement order refers to the first pixel group including the root pixel, the encoding header of the first pixel group to the encoding header of the seventh pixel group, and the residual value of each pixel in the first pixel group to the first pixel group. The residual value of each pixel in the seven-pixel group.

In the above-mentioned compressed data string, since the encoding header of each pixel group has 3 bits, the total encoding headers of the first to seventh pixel groups are 21 bits (7x3), and the encoding header The value of is the number of bits used to represent the residual value of each pixel in the pixel group. In short, when the value of the encoding header is small, it means that the number of bits occupied by the residual value of each pixel in the pixel group is also small.

In summary, the feature of the present invention lies in the use of image area fast segmentation, prediction processing, and encoding processing to specifically realize lossless (lossless) embedded compression (EC) image compression algorithm, compression ratio (Compression Ratio) , CR) can be as high as 2.24, which not only saves about 55.4% of the memory bandwidth, but also maintains high-quality images. For example, if the method of the present invention is made into a chip using CMOS 0.18 um semiconductor technology, then The maximum throughput can reach 6.4G (pixel/sec) and 3,840x2,160@60fps, which can meet the real-time compression requirements of 4K images.

The above descriptions are only used to explain the preferred embodiments of the present invention, and are not intended to limit the present invention in any form. Therefore, any modifications or changes related to the present invention made under the same spirit of the invention , Should still be included in the scope of the invention's intention to protect.

S10, S20, S30, S40: steps S50, S60, S70, S80: steps R: raw pixels G1: The first pixel group G2: The second pixel group G3: The third pixel group G4: The fourth pixel group G5: The fifth pixel group G6: The sixth pixel group G7: seventh pixel group PC: target pixel, PT: upper pixel PL: left pixel PR: Right pixel PLT: upper left pixel PRT: upper right pixel RT: Root pixel T: dry pixel B: branch pixel LL: left leaf pixel RL: Right leaf pixel

The first figure shows the operation flowchart of the lossless image compression method according to the embodiment of the invention. The second figure shows a schematic diagram of a 16x8 image block in a lossless image compression method according to an embodiment of the invention. The third figure shows a schematic diagram of adjacent pixels of the target pixel in the lossless image compression method according to the embodiment of the present invention. The fourth figure shows a schematic diagram of dividing a 16x8 image block into first to seventh pixel groups in a lossless image compression method according to an embodiment of the present invention.

S10, S20, S30, S40: steps

S50, S60, S70, S80: steps

Claims (2)

A lossless image compression method, including: Capture a 16x8 image block in the input image data as a processing block. The processing block contains 16x8 pixels arranged in a matrix, and divides all the pixels in the processing block into one pixel, multiple dry pixels, Multiple branch pixels, multiple left-leaf pixels, and multiple right-leaf pixels, the root pixel is the pixel (1, 1) in the 16x8 pixel, which is located at the upper left corner of the processing block, and the dry pixels are pixels (1, 2) to (1, 16), the branch pixels are pixels on the diagonal of pixels (6, 2) to (8, 12), and the left leaf pixels are located in the branch pixels And the pixels between the root pixel and the stem pixels, and the right leaf pixels are the pixels located on the right side of the branch pixels and between the stem pixels; The residual value of each dry pixel in the processing block is calculated to obtain the residual value of each dry pixel, and the residual value is r, which is expressed as r=PC-PL, where PC is the dry pixel, and PL is the pixel to the left of the dry pixel; Calculate the residual value of each branch pixel in the processing block to obtain the residual value of each branch pixel, and the residual value is r, expressed as r=C-PT, where PC is the branch Pixel, and PT is the dry pixel above the branch pixel; Calculate the residual value of each left-leaf pixel in the processing block to obtain the residual value of each left-leaf pixel, and the residual value is r, which is expressed as r=PC-HL1, PC-HL2, PC -One of HL3, where HL1 is (PRT+PT)/2, HL2 is (PR+PT)/2, HL3 is (PRT+PR)/2, PM is the minimum of HL1, HL2, and HL3, If PM is HL1, then r is PC-HL1, if PM is HL2, then r is PC-HL2, if PM is HL3, then r is PC-HL3; Perform residual value calculation on each right-leaf pixel in the processing block to obtain the residual value of each right-leaf pixel, and the residual value is r, which is expressed as r=PC-HR1, PC-HR2 One of PC-HR3, where HR1 is (PLT+PT)/2, HR2 is (PL+PT)/2, HR3 is (PLT+PL)/2, PM is the minimum of HR1, HR2, and HR3 , And if PM is HR1, then r is PC-HR1, if PM is HR2, then r is PC-HR2, if PM is HR3, then r is PC-HR3; The pixels of the 16x8 image block are divided into an original pixel, a first pixel group, a second pixel group, a third pixel group, a fourth pixel group, and a fifth pixel group, A sixth pixel group and a seventh pixel group, the original pixel is the root pixel, the first pixel group includes all the dry pixels, and the second pixel group includes the sub-pixels (8, 12) All the branch pixels other than the other, the third pixel group includes all the pixels in the block from pixel (2, 1) to pixel (8, 4) in all the left-leaf pixels, the fourth pixel group The group includes all the left-leaf pixels except for the third pixel group and all pixels in the horizontal arrangement of pixels (8, 5) to (8, 11). The fifth pixel group includes all the pixels The remaining pixels of the right-leaf pixels except all the pixels below the pixels (5, 10) to (5, 16), the sixth pixel group includes all the right-leaf pixels, except the fifth pixel group and pixels (8, 13) to pixel (8, 16) other than pixels arranged in the horizontal direction, the seventh pixel group includes all pixels arranged in the horizontal direction from pixel (8, 1) to pixel (8, 16); For each pixel group, according to an absolute value range of the residual value corresponding to each pixel, a coding header is set, and the coding header is represented by three bits; and According to a preset arrangement sequence, the root pixel, the encoding headers, and the residual values are concatenated to generate a compressed data string corresponding to the 16x8 image block, or called a bit string (bitstearm ), The arrangement sequence refers to the order from the root pixel, the encoding header of the first pixel group to the encoding header of the seventh pixel group, the residual value of each pixel in the first pixel group to The residual value of each pixel in the seventh pixel group. According to the lossless image compression method described in item 1 of the scope of patent application, when the encoding header of each pixel group is set, if the residual value of all the pixels is 0, the encoding header is 000; When the absolute value of the residual value ranges from 0 to 1, the code header is 001; when the absolute value of the residual value ranges from 0 to 3, the code header is 010; in the absolute value of the residual value When the value range is 0~7, the coding header is 011; when the absolute value of the residual value is in the range of 0-15, the coding header is 100; when the absolute value of the residual value is in the range of 0~ At 31 o'clock, the code header is 101; when the absolute value of the residual value is in the range of 0 to 63, the code header is 110; when the absolute value of the residual value exceeds the range of 0 to 63, the code header is Is 111.

Images