Frei-Chen bases based lossy digital image compression technique

In recent decades, many algorithms have been proposed in the field of digital data compression [1,2], all of which have focused on reducing the redundancy of digital data to increase the efficiency of storing, processing, and transmitting data [3]. Image compression is an image processing application used to reduce the size of a digital images [4,5]. The main goals are to allow more images to be stored in the same storage device and more images to be shared/transferred over the same link/network [6].

In image compression there are two main algorithms: compression algorithm and the decompression algorithm. The result of the compression algorithm is the compressed image which is smaller in size compared to the original image. On the other hand, the decompression algorithm tries to reconstruct the original image from the compressed image [7,8]. All image compression algorithms aim at having small size for compressed image (high compression factor) and a high-quality reconstructed image (high-quality compression). The block diagram for image compression is shown in Figure 1. In order to reduce the pixel redundancy, the input image is transformed to another format by applying a compression algorithm/compressor. Moreover, the decompression algorithm is applied as an inverse process of the compressor.

The efficiency of the compression algorithms can be measured, depending on the application, by using different criterions. The most important criteria is the compression factor. The compression factor measures the size of the image before and after compression. Thus, the larger the compression factor, the more effective the compression algorithm [7]. The compression factor (R) is given by Eq. (1),

where, $S(o)$ and $S(c)$ are the sizes of the original and compressed images, respectively.

Even though, high compression factor is desirable, the quality of the reconstructed images should still be high in order to have applicable compression algorithm. Therefore, there is a tradeoff between the compression factor and compression quality. In other words, achieving high compression factor should also produce a decompressed image with minimal distortions [9].

Compression algorithms are divided into two techniques based on the decompressed, reconstructed, image. If the reconstructed image is similar to the original one, the compression is lossless, otherwise it is considered lossy. The lossless techniques and [10–12] are used when the quality of the decompressed image is the most important. In lossless techniques, which are also called reversible techniques, [9], the correlation between the original and decompressed images is1. Therefore, the decompressed image will keep all data details about the original image [13]. On the other hand, in lossy compression technique, some details are lost during compression/decompression and thus it is impossible to reconstruct the exact original image from the compressed one. Lossy compression algorithms usually have higher compression factors compared to lossless algorithms. Lossy compression techniques are commonly used in loss-tolerant applications such as multimedia images [14,15], where a loss in some of the image data does not cause problems especially when it is not noticeable by the human eye.

Recently, many algorithms for data and image compression have been proposed. For example, mixed Discrete Cosine Transform (DCT) and Huffman Coding techniques are used in Joint Photographic Experts Group (JPEG) and Moving Picture Experts Group (MPEG) compression algorithms [16].

Furthermore, Temporal-Length is used in Three-dimensional discrete cosine transform (3-D DCT) coding technique [17], mixed Wavelet Transform and RLE techniques [18], Wavelet Transform [19], lossy JPEG [20,21], Lossless JPEG [22], mixed block optimization and RLE [23], Geometric wavelet (GW) [24] and Compression for Join-Based Graph Mining Algorithms [25]. In addition to image compression [26,27], Run Length Encoding (RLE) algorithm is used for other applications such as fingerprint analysis [28], motion detection [29], data compression [30,31], video compression [32,33], edge detection in real-time image processing [34,35], and scanning and pattern recognition [36].

In this paper, we integrate Frei-Chen bases and Run Length Encoding techniques to achieve high compression factors and high quality decompressed images. The proposed method is applied to gray scale images, however, it can be extended to RGB images. Thus, Frei-Chen bases technique and the Modified Run Length Encoding (RLE) are applied to compress images. The Frei-Chen bases technique is applied at the first stage of compression in which the nine pixels, in most 3X3 blocks of image, are replaced by a single value that represents the average value of these pixels. Even though Frei-Chen bases technique provides lossy compression, it maintains the main characteristics of the image. Additionally, the Frei-Chen bases technique enhances the compression factor, making it advantageous to use. In the second stage, RLE is applied to further increase the compression factor. The goal of using RLE is to enhance the compression factor without adding any distortion to the resultant decompressed image. Integrating RLE with Frei-Chen bases technique, as described in the proposed algorithm, ensures high quality decompressed images and high compression rate.

Frei-Chen bases [37] are used for boundary detection technique. They were suggested by Werner Frei and Chung-Ching Chen to recognize edges and lines features in digital images [38].

In general, Frei-Chen technique consists of nine orthonormal bases $(wi)$⁠, where $i=1,2,…,9$⁠. Each basis represents some features of the image. Any $3X3$ sub-image can be written as a weighted sum from these nine orthonormal¹ Frei-Chen bases (also known as masks). The Frei-Chen bases can be classified into three subspaces: edge, line and average subspaces.

There are four bases for the edge subspace, $w1$⁠, $w2$⁠, $w3$ and $w4$⁠. The first pair represents isotropic average gradient while the second pair represents the ripple gradient. As shown in Figures 2a and 2b. These bases are used to detect vertical or horizontal edge in the image.

The next four bases $w5$⁠, $w6$⁠, $w7$ and $w8$ represent line subspace where $w5$ and $w6$ represent directional line and $w7$ and $w8$ represent unidirectional line or discrete Laplacian. Figures 3a and 3b show line subspace bases.

Finally, $w9$ which is shown in Figure 4 is used to compute the average area. When applied to images, this subspace gives equal weights to all image pixels.

Therefore, each Frei-Chen basis reveals different details about the image and hence can be used, as we will see, in image compressions. Table 1 summarizes Frei-Chen basis characteristics [37].

As mentioned earlier, Frei-Chen bases are masks that can be applied to an image after dividing it into subimages, blocks, of size 3X3. The projection of different Frei-Chen bases will represent specific characteristic for each subimage. The basis that results in the highest projection value represents the characteristic that best describes that block of the image [38]. This means that we can replace the nine pixel values with one value that corresponds to basis with the highest projection.

In order to explain the advantages of using Frei-Chen bases, suppose we have an image I of size NXN. The total energy (T) that image I has is represented by:

where $∗$ represents the convolution operator. The energy (E) for the projection of each Frei-Chen basis is represented by:

where $B$ is a block, subimage, of the image $i$⁠. The bases that produces the highest energy suggests which subspace the block belongs to. Using the fact that Frei-Chen bases are orthonormal, we can reconstruct the block, $B$ from the projections, $E−i=w_i∗B$⁠, by:

Equation (4) suggests that a block B can be fully reconstructed from its projections into the Frei-Chen bases. In addition, those bases with high projections would be sufficient to recover B with little distortions.

In this paper; Frei-Chen bases are used for image compression as a first stage. We use that fact that in natural images, neighboring pixels are very close in value to each other. This means that the projection of the average space, $w9$⁠, is the highest and thus it will be sufficient to estimate block $B$ by using $w9$⁠. In this case, Eq. (4) can be written as,

This means that the nine pixels which represent block $B$ can be replaced by a single value that corresponds to the projection of $w9$⁠. The first stage of compression can be summarized as follows:

• 1.

  The original grayscale image $I$ of size $NXN$ is divided into blocks, $B$⁠, of size $3×3$⁠.

• 2.

  Each block is projected into all Frei-Chen bases.

• 3.

  For each block, if the energy of $w9$ projection is the largest, we calculate the average grayscale level mean (X) of the pixels of that block. Otherwise, the block pixels will remain the same.

• 4

  Steps 1–3 are repeated for all blocks.

The algorithm of the Frei-Chen compression technique is shown below.

After using Frei-Chen bases in the first stage, the resultant image will be an image that looks close to the original image. The only difference is that for those blocks at which the projection of $w9$ is the highest, the pixels values are replaced by a single value (X) which represents the average value of the nine pixels. Therefore, the image resulted from the first stage will contain many adjacent repeated pixels.

In order to make use of this repetition and redundancy, we propose to use the well-known Run-Length Encoding (RLE) algorithm to further compress the image. RLE is a lossless data compression technique and is used to reduce the number of redundant bits. The main advantage for using the lossless RLE algorithm is to increase the compression factor without introducing new distortion to the decompressed image.

The RLE algorithm for image compression is similar to that of data compression. The image resulted from applying Frei-Chen algorithm will be scanned to find the run of similar pixels. This scan can be horizontally, vertically or Zig-Zag as shown in Figure 6.

To enhance the RLE algorithm, the Block-Block scanning technique will be used, this technique is expected to produce higher efficiency since we have blocks (the result of the first stage) in which all pixels have the same value X. The Block-Block scanning is shown in Figure 7. The image is divided into blocks; where the pixels inside each block are either scanned vertically or horizontally and all blocks together are also scanned vertically or horizontally. In this paper, blocks are scanned vertically and pixels inside the block are scanned horizontally. The results of this scan are stored in a vector which contains the pixel values and its run. In the resultant vector, the run of the same pixel’s value will be merged to reduce the size of the vector as shown in Figure 6.

To reconstruct the image, a reverse two stage decompression algorithms will be applied. In the first stage, the vector resulted from the RLE algorithm will be used to reconstruct all blocks of the image.

Frei-Chen bases will then be applied to get the final decompressed image as shown in Figure 8.

In this section, we will present the experimental results obtained by applying the proposed compression algorithm. The proposed algorithm has been implemented and test using MATLAB software. Several images have been tested. The average compression ratio of all images is 8.965 with standard deviation of 0.01. In addition, the correlation factor and the Mean Square Error MSE were 0.952 and 0.123, respectively. In this paper, however, we will show the results of Barbara, Boat, Cameraman, Lena and Mandrill images shown in Figure 9.

The results of applying the first stage of the proposed compression algorithm using Frei-Chen bases is shown in Table 2. The compression ratio on all images was around 9. This is expected since in the first stage, we are replacing the nine pixels of the blocks in which the average subspace $w9$ is the highest with one value which is the average of all pixels. This means that if the projection of $w9$ into all the blocks is the highest, the compression ratio would be 9. In addition, in natural images, the adjacent pixels have very close values, which means that the projection of $w9$ basis will be the highest in most blocks. This also explains the reason of having compression ratio close to 9.

Since the first stage replaces nine pixels values by one value, it would introduce some distortions when reconstructing the image. In order to study this distortion, we use two measure: the correlation and the mean square error (MSE) between the original and reconstructed images. The correlation measure shows how close both images are to each other. A correlation value of 1 means that both images are the same and a value close to 0 means both images are very different. MSE measure how much error does using Frei-Chen bases introduce. The MSE is given by,

where $Pi$ is the pixel value form the decompressed image, $Qi$ is the pixel value form the original image, and $(N,M)$ are the number of rows and columns, respectively. The results for the correlation and MSE for all test images are shown in Table 3. The results show that the first stage of the proposed algorithm produce highly correlated decompressed image with small MSE.

In the second stage of the proposed algorithm, we applied RLE. RLE is a lossless algorithm and thus the results of the correlation and the MSE between the decompressed and the original images will be similar to the results of the first stage as shown in Table 3.

RLE is applied to the resultant image from the first stage using different block sizes. Table 4 shows the correlation values between the decompressed image from the second stage and the decompressed image of the first stage.

Table 5 shows the compression factor of the first stage (Frei-Chen) and the second stage (RLE with block size 7X7). It is clear that most compression come from the first stage. In order to find the overall compression ratio $(RT)$⁠, we use Eq. (7),

where $RFC$ and $RRLE$ are the compression ratios from Frei-Chen and RLE stages, respectively. The overall compression ratio $RT$⁠, MSE, and PSNR are listed in Table 6. As mentioned earlier, the MSE values does not change by applying RLE because it’s a lossless algorithm.

Peak signal-to-noise ratio (PSNR) [39,40] is calculated using Eq. (8),

In order to show the effectiveness of the proposed algorithm, we compared it with several algorithms. Tables 7 and 8 show the compression factor $R$ for different compression algorithms applied on the Lena and Cameraman images.

As shown in the results, the proposed algorithm outperforms other algorithms by big margin.

In this paper, a new algorithm for digital image compression is proposed. The proposed algorithm consists of two stages; Frei-Chen bases stage and Run-Length Encoding stage. The main focus of this algorithm was to obtain a higher compression factor while decreasing the distortion of the decompressed image.

The experimental results showed the efficiency of the proposed algorithm in terms of compression factor and MSE. The Frei-Chen stage provides high compression factor and yet preserve high correlation values. To improve the compression factor, Frei-Chen bases are combined with well-known RLE. The results of the proposed algorithm outperfroms other algorithms in the area of image compression. In the future, the proposed compression algorithm can be extended and applied for the RGB medical images.

Declaration of Competing Interest: The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.Publishers note: The publisher wishes to inform readers that the article “Frei-Chen bases based lossy digital image compression technique” was originally published by the previous publisher of Applied Computing and Informatics and the pagination of this article has been subsequently changed. There has been no change to the content of the article. This change was necessary for the journal to transition from the previous publisher to the new one. The publisher sincerely apologises for any inconvenience caused. To access and cite this article, please use Al-khassaweneh, M., AlShorman, O. (2020), “Frei-Chen bases based lossy digital image compression technique”, Applied Computing and Informatics. Vol. ahead-of-print No. ahead-of-print. https://10.1016/j.aci.2019.12.004. The original publication date for this paper was 02/01/2020.