Frei-Chen bases based lossy digital image compression technique

Abstract

In the big data era, image compression is of significant importance in today’s world. Importantly, compression of large sized images is required for everyday tasks; including electronic data communications and internet transactions. However, two important measures should be considered for any compression algorithm: the compression factor and the quality of the decompressed image. In this paper, we use Frei-Chen bases technique and the Modified Run Length Encoding (RLE) to compress images. The Frei-Chen bases technique is applied at the first stage in which the average subspace is applied to each 3 × 3 block. Those blocks with the highest energy are replaced by a single value that represents the average value of the pixels in the corresponding block. 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. The results of the proposed algorithms are shown to be comparable in quality and performance with other existing methods.

Citation

Al-khassaweneh, M. and AlShorman, O. (2024), "Frei-Chen bases based lossy digital image compression technique", Applied Computing and Informatics, Vol. 20 No. 1/2, pp. 105-118. https://doi.org/10.1016/j.aci.2019.12.004

1. Introduction

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),

(1)R=S(o)S(c)

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.

2. Methodology

2.1 Frei-Chen basis technique

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.

2.1.1 Edge subspace

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.

2.1.2 Line subspace

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.

2.1.3 Average subspace

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].

2.2 Frei-Chen expansion

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:

(2)T=I∗I

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

(3)Ei=wi∗B

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:

(4)B=∑i=19(Ei∗wi)=∑i=19(wi∗B)∗wi

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.

2.3 Frei-Chen compression technique

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,

(5)B=E9∗w9=(w9∗B)∗w9

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.

2.4 Run length encoding (RLE) technique

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.

3. Results and discussion

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,

(6)MSE=(∑ (Pi−Qi)2/(N∗M))

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.

3.1 RLE compression results

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),

(7)RT=RFC×RRLE

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),

(8)PSNR=10 log10(25521N∗M∑i(Pi−Qi)2)

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.

4. Conclusion

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.

Figures

Figure 1

Block Diagram for Image Compression/Decompression.

Figure 2a

Edge Subspace (w1 and w2): Isotropic average gradient basis.

Figure 2b

Edge Subspace (w3 and w4): The ripple basis.

Figure 3a

Line Subspace (w5 and w6): Directional line.

Figure 3b

Line Subspace (w7 and w8): Discrete Laplacian.

Figure 4

Average Subspace (w9): Average mask.

Figure 5

Horizontal, Vertical and Zig-Zag scans.

Figure 6

Block-Block scanning technique.

Figure 7

Compression/Decompression outlines.

Figure 8

Test images; a) Barbara, b) Boat, c) Cameraman, d) Lena and e) Mandrill.

Table 1

Frei-Chen basis characteristics.

W	Block feature
W1	Vertical Gradient
W2	Horizontal Gradient
W3	Vertical Ripple
W4	Horizontal Ripple
W5	Vertical Line
W6	Horizontal Line
W7	Vertical Discrete Laplacian
W8	Horizontal Discrete Laplacian
W9	Constant Area

Table 2

Frei-Chen compression results.

The image	Original size	Compressed size	R
Barbara	512 × 512	171 × 171	8.9649
Boat	512 × 512	171 × 171	8.9649
Cameraman	512 × 512	171 × 171	8.9649
Mandril	225 × 225	75 × 75	9.0000
Lena	512 × 512	171 × 171	8.9649

Table 3

Frei-Chen compression correlation and MSE.

The image	R	Correlation factor	MSE
Barbara	8.9649	0.9512	0.1435
Boat	8.9649	0.9620	0.0983
Cameraman	8.9649	0.9712	0.1261
Mandril	9.0000	0.8644	0.0960
Lena	8.9649	0.9799	0.0616

Table 4

RLE Results for all block sizes.

The image	R (3*3)	R (5*5)	R (7*7)
Barbara	1.2019	1.1943	1.2328
Boat	1.4475	1.4760	1.4760
Cameraman	2.0429	2.0977	2.321
Mandril	1.2873	1.2288	1.2779
Lena	1.5344	1.4905	1.5710

Table 5

R for Frei-Chen and RLE.

The image	R (Frei-Chen)	R (RLE)
Barbara	8.9649	1.2328
Boat	8.9649	1.4760
Cameraman	8.96492	2.321
Mandril	9.0000	1.2779
Lena	8.9649	1.5710

Table 6

Final results.

The image	R (Tot)	MSE	Correlation Factor	PSNR
Barbara	11.0519	0.1435	0.9512	56.5622
Boat	13.2321	0.0983	0.9620	58.2052
Cameraman	20.8075	0.1261	0.9712	57.1236
Mandril	11.5074	0.0960	0.8644	58.3080
Lena	14.0838	0.0616	0.9799	60.2350

Table 7

Comparison with other compression techniques for Lena.

The technique	R
Proposed method	14.083
Fractal based [41]	13.33
Chinese remainder theorem [42]	6
Artificial bee colony and genetic algorithms [43]	10
Fuzzy C-Means-Based JPEG Algorithm [44]	12.77
Searchless fractal image coding [45]	12.8

Table 8

Comparison with other compression techniques for cameraman.

The technique	R
Proposed method	20.80
Neural Networks-multilayer	7
perceptrons [46]	0.75
Curvelet, ridgelet and wavelet [47]	8.19
Global Structure Transformation [48]	7
JPEG standard Jesse’s scheme [49]	5.45

	Algorithm 1 Frei-Chen compression technique
	1: Input: Image I, Frei Chen basis (w1,…,w9)
	2: For every 3×3 block in image I do
	3: project every block with w1,…,w9
	4: If w9 project is the largest then
	5: replace the block by the average value
	6: else
	7: keep the block unchanged
	8: end if
	9: end for

Notes

1. All Frei-Chen subspaces are multiplied by the orthonormality constants. These constants are: 18 for w1, w2, w3 and w4, 12 for w5 and w6, 16 for w7 and w8 and 13 for w9.