1. Partial Pixel Compression

A pixel of an image consists of R, G, and B, and the image data is stored as 8-bit, representing 256 levels. Most of images consist of low frequencies, and the ratio of the high-frequency element such as the edge is relatively low. Therefore, there are many identical upper bits since the difference between neighboring pixels is not much.

If the number of consecutive pixels to be compared is defined as Pixel Comparison Range (PCR), and Partial Pixel is defined as the partial bit of a pixel to be compared, Fig. 2 represents the probability of pixels being identical according to PCR and the size of the partial pixel of sample images with the size of the partial pixel of Fig. 1.

Fig. 1. Sample images: (a) Baboon; (b) Camera; (c) Citrus; (d) Coin; (e) F 16; (f) Fishing boat; (g) Lena; (h) Word.

Fig. 2. The probability of an adjacent pixel being identical according to the size of the partial pixel and PCR.

Although the probability of a pixel being identical with the neighboring pixel is no more than 16.5%, 66.9% of the pixels are identical when only the upper 4 bits are compared. Since there are many cases where the upper bits of neighboring pixels are identical while only the sub-bits are different, compression can be realized by storing only the sub-bits, excluding overlapping upper bits. During decompression, they can be recovered through the upper bit of the previous pixel and sub-bits that are stored as compressed data.

In the compression process, if the nth pixel of the original image consists of the upper-bit partial pixel ``B'' and sub-bit partial pixel ``b,'' the upper bit of the nth pixel is different from the (n-1)th pixel, so the nth pixel is saved as the mth compressed data, and this is marked on flag to 0 as uncompressed data.

However, the upper-bit of the (n + 1)th and (n + 2)th pixels are identical ``B'' with that of the nth pixel, the previous pixel, so the sub-bit ``c'' and ``d'' can be saved excluding the identical upper-bit, and this is marked with the flag to 1 as compressed data and saved as the (m + 1)th compressed data. For decompression, first, the compression/ uncompression of the corresponding data is distinguished through the flag. Since the mth compressed data is uncompressed, the remaining except the flag is generated as the nth pixel. Since the (m + 1)th data is compressed, the (n + 1)th pixel can be generated through ``B,'' the upper bit of the previous pixel, and ``c,'' the upper bit of the compressed data. And the (n + 2)th pixel can be generated through ``B'' and ``d.'' According to Fig. 2, the probability of pixels being identical increases as the size of the upper bit increases and PCR to be compared gets smaller. However, to have a high compression rate, the upper bit and PCR have to be large. Therefore, the size of the partial pixel to be compared with PCR for achieving the maximum compression rate is represented by (1).

(1)

In Table 1, the higher the values of PCR and the upper bit width, the higher the expected compression rate, and even though distribution may vary according to the characteristics of the image, normally, the compression rate is the highest when the partial pixels of the upper 4 bits are compared given PCR of 2. ``-'' sign represents the case when the size increased after the compression, and the case where PCR is 1 and the case of full pixels compared are not included since compression is not done due to the absence of upper-bit to be reduced.

As in Fig. 3, the compression method which compares the partial pixel and excludes the overlapping upper-bit shall be called Partial Pixel Compression (PPC), and the compression rate is sufficient as described in Table 1.

Fig. 3. Concepts of compression/decompression.

2. Truncated Partial Pixel Compression

However, due to the flag overhead in PPC, compressed pixels need 1 additional bit compared to original pixels.

This increases the amount of data when there are many adjacent pixels in an image with different upper bits, which cannot be compressed by PPC. The amount of data is determined by the worst compression rates. Another compression algorithm is proposed to share the same computational method as PPC while achieving high image quality with a compression rate guard to maintain the worst compression rate.

When 2 bits are truncated as shown in Fig. 4(c), in areas where adjacent pixels have similar values like the sky area, image quality degradation such as the pseudo edges can be observed. However, in areas where adjacent pixels have significant differences, such as in textured surfaces, the quality degradation is less noticeable. However, when 1 bit is truncated as shown in Fig. 4(b), it may be difficult to perceive quality degradation not only in textured surfaces but also in the sky.

Fig. 4. Lower bit truncated images: (a) Original; (b) LSB 1 bit truncated; (c) LSB 2-bit truncated; (d) 1 or 2-bit mixed (proposed).

Applying these characteristics to PPC, in cases there is a significant difference between adjacent pixels, such as on the ground, 2 bits are truncated as uncompressed type, and in cases there is less difference between adjacent pixels, such as in the sky, 1 bit is truncated from each pixel as a partial type. Uncompressed type is to store data without compression, partial type is to compress only important parts of the data, leaving the rest uncompressed. Further discussion on these concepts will be described later in Table 2.

The proposed compression approach, named Truncated Partial Pixel Compression (TPPC), truncates 1 or 2 bits as shown in Fig. 4(d). By eye test, there is no perceptual image quality degradation, and even mathematically, it also shows a very high image quality with a PSNR of 45.2~dB. TPPC fundamentally shares the same compression and decompression process as PPC, with the key difference in the truncation of lower bits, as described in Fig. 3. In case the nth original pixel in Fig. 5 has different upper bits compared to the previous pixel, 2 bits from the lower portion are truncated, and like in PPC, the flag is set to 0, indicating uncompressed type.

Fig. 5. Concepts of TPPC.

In case the (n + 1) and (n + 2) pixels have the same upper bit group as the previous pixel as shown Fig. 5, the least significant bit (LSB) of both bit groups c and d are truncated by 1 bit each, and like in normal PPC, the flag is set to 1, indicating it is a partial type. The decompression process is the same as PPC, with the only difference being that during decompression, as shown in Fig. 5, the truncated bits are padded using the most significant bits (MSB)

TPPC is applied in cases where PPC yields low compression rates. Because the extent of TPPC determines the trade-off between overall image quality and compression rates, the modes can be set based on the requirements of a certain application or target system with the flexibility in choosing a frame or a block level. Two algorithms (PPC or TPPC) can be chosen considering the compression results or predicting the algorithm according to the image characteristic. For the first approach, when the algorithm is selected after the compression, PPC packets can be converted to TPPC packets if the compression rate exceeds the compression rate guard. As they use the same compression processes, as explained in Fig. 5 and only the difference is whether LSBs (Least Significant Bits) of the lower bit groups are truncated or not. The alternative approach is predicting the algorithm according to the image characteristics before the compression. Because the compression rate of PPC varies depending on the similarity in adjacent pixels, a metric, image slope is used in this work for the criterion to use TPPC. If the number of pixels in the image is denoted as ‘n’ and the value of the x-th pixel is denoted as 'Px,' the image slope is defined by Eq. (2).

The image slope is the average difference between adjacent pixels, as shown in Eq. (2). A higher image slope value indicates a lower probability of similarity between adjacent pixels in the upper bit group, resulting in lower compression rates. Therefore, as image slope and compression rate are highly correlated, it makes image slope a suitable criterion for the application of TPPC.

The compression rates of PPC and TPPC for 152 selected images with various features are sorted according to the image slope as in Fig. 6. Both PPC and TPPC show a decreasing trend in compression rate as the image slope increases. PPC shows a compression rate from 41.7% to -9.1%, with an average of 23.4%, while TPPC shows a compression rate ranging from 54.7% to 15.2%, with an average of 40.4%. In terms of image quality, TPPC maintains a very high image quality, as PSNR ranges from 42.3 dB to 54.4 dB with an average of 46.0 dB, and visually perceived emotional loss is minimal as in Fig. 4(d). As the image slope exhibits a high correlation with compression rates as shown in Fig. 6, the algorithm selection can be made based on the image slope. The image slope for the criterion for algorithm selection is defined as the image slope corner. When the image slope is less than the image slope corner, PPC is used, and when it is greater, TPPC is used. Fig. 6 illustrates the cases where the image slope corner is set to 9. When the image slope is 9 or lower, PPC is used, resulting in lossless compression. When the image slope is 9 or higher, TPPC is used, providing a high image quality of PSNR 45 dB approximately while achieving high compression rates.

Fig. 6. Image slope and compression rate.

3. Full Pixel Compression

In the method such as RLE which compares the full pixel of the entire image, since the probability of the pixels being identical decreases significantly as PCR increases as shown in Fig. 2, the compression rate is low except in some particular cases. However, if the method used in comparing and compressing full pixels is used along with the method which compares and compresses partial pixels, limited to the part where there are many continuous identical pixels, the compression rate can be improved so that it would be more suitable for more various images.

The process of comparing and compressing full pixels will be called full pixel compression. 1-bit code has been extended to use partial pixel compression and full pixel compression in combination. In the same way, the case of partial pixel compression when the flag is 1, the case of full pixel compression through the code when the flag is 0, and the case where compression is not done are distinguished. In case three pixels are consecutive in full pixel compression, they are stored with code of 1 and flag of 0 as in Fig. 7. Here, the probability of two pixels being consecutively identical is 52.9% according to the result of Fig. 2, where the previous pixel and the upper bit are identical, allowing partial pixel compression. In addition, as PCR increases, the probability of the pixels being identical reduces, which allows for full pixel compression when three pixels are identical, to get a high compression rate. Since the pixels from the nth and (n + 2) are identical to "A'' in Fig. 7, they are compressed and stored with "A" as code = 1 and flag = 0. Since the (n + 3)th pixel is not identical with the consecutive pixel, it is stored with code and flag = 0. During the decompression procedure, the compression of data is identified through code and flag; code = 1 and flag = 0, as the mth data, indicates completion of compression, outputting "A" three times for decompression.

Fig. 7. Concepts of FPC.

Thus, the method that compares and compresses the partial and full pixels shall be called Partial Pixel and Fixed Run Length Compression (PFC). In addition, RLE is the method that compresses after storing the pixel value and the number of consecutions when there are continuous identical pixels, and the compression rate cannot be expected from ordinary images. Still, the compression rate for the images with continuous identical pixels is very high compared to other algorithms. In conclusion, if the proposed algorithms, PFC and PPC are compared since the method by which compression is done after eliminating overlapping elements is quite similar to RLE, much hardware can be shared for three algorithms, which makes hardware complexity low.

If the algorithm with a high compression rate among PFC, PPC, and RLE is designed to be programmable as per image characteristics, on average, a high compression rate can be achieved. Furthermore, by selectively applying TPPC to images with low compression rates, it is possible to maintain the compression rate above a certain level.

A method is selected for the best compression algorithm according to the image characteristic analysis results. But, in this case, high hardware complexity is required due to the demand for very large buffer memory for the characteristic analysis with delay. However, the moment of scene change of images is a very short time among the entire time of displaying image, and the characteristics of the image, while one scene is maintained, tend to be identical or like the previous frame. Therefore, a method is proposed that applies the algorithm with the highest compression rate in the previous frame to the compression of the current frame. Specifically, the method is used which selects compression algorithm adaptively with prediction based on frame characteristic history. The way the algorithm is selected in such a way will be called compression mode.

Table 2 shows the format of compression data according to each compression mode. Compression mode can be divided largely into PPC, TPPC, PFC, and RLE. PPC can be divided again into partial and uncompressed types, and these are distinguished by flag. Partial type is the case where compression is done without the repetitive upper bit, as shown in Fig. 3, and Table 1, PCR is 2 when the compression rate is the highest, and compression is done when the upper 4 bits of the pixel are compared. Uncompressed type is the case where compression is not done because one pixel is saved when the previously compressed pixel is not identical to the upper bit. TPPC has the same data format as PPC, with the only difference being the truncation of the LSB as shown in Fig. 5. Next, the storage format of PFC is divided into partial type, fixed run length, and uncompressed type, and these are distinguished by flag and code.

Although the partial type is like that of PPC, they are not identical since the adjacent first pixel is compared with the upper 4 bits since PFC has one more bit compared to PPC, and the second, the upper 3 bits are compared and compressed considering the large pixel distance. Fixed run length is the case where a pixel and the number of the consecution of the pixels are saved with code and flag when the input pixels are consecutively identical, and they can be stored only when three pixels are consecutive. Compressed data is saved as a fixed run length when three pixels are consecutive to be stored as one pixel and code = 1 and flag = 0. Likewise, an uncompressed type of PFC can save only one pixel in case compression is not available with a partial type or fixed run length. RLE has the ordinary format which stores one pixel data and run length.

4. HVS-based Compression Algorithms

In the previously described cases of PPC, TPPC, and PFC, compression is carried out based on the actual pixel values of the image. Commonly, compression rates increase when adjacent pixels share the same value.

In the human processes of image evaluation, humans exhibit a non-linear characteristic in perceiving brightness, as illustrated in Fig. 8 ^[10]. Humans are particularly insensitive to significant changes in high brightness.

Fig. 8. Brightness sensitivity curve.

As shown in Fig. 9, Look Up Table(LUT) is presented to have a lower slope considering the non-linear insensitivity of human perception for the high-brightness regions of the brightness sensitivity curve as shown in Fig. 8. It increases the occurrences of the same adjacent pixels to increase the compression rate. The encoding LUT is presented in the encoder before performing the compressions. It transforms the pixel values to have the same value as perceived by humans.

Fig. 9. Block diagram of providing encoding LUT and decoding LUT.

Considering the brightness sensitivity as depicted in Fig. 8, the LUT curve becomes almost flat in the high pixel region, resulting in a decrease in image quality as the flatness increases, which is a trade-off between the compression rate and the image quality. Therefore, to improve both compression rate and image quality, as shown in Fig. 10, after the decompression, the original image quality is restored, using the decoding LUT.

Fig. 10. Data compression/decompression with HVS-based LUT.

As shown in Fig. 10, compared to the case the LUT shown in Fig. 8 is not used, more MSBs of the same value are generated by the LUT, and thus the compression rate can be improved. Additionally, the curve used for the decoding LUT, as shown in Fig. 11, results in an overall decrease in brightness due to the brightness sensitivity curve. According to brightness sensitivity, humans are more sensitive to changes in low brightness ranges. Therefore, in this region, a higher slope is used to compensate for the decreasing portion as shown in Fig. 8. On the contrary, the high pixel region is used with a lower slope, as depicted on the right side of Fig. 11. However, as mentioned in Fig. 8, due to the brightness perception theory, humans do not perceive distortion in the high brightness range sensitively, so it does not affect the image quality perceived by humans.

Fig. 11. Relationship between encoding LUT curve and decoding LUT curve.