 Open Access
 Authors : Tanuja R. Patil , Vishwanath P. Baligar
 Paper ID : IJERTV10IS070229
 Volume & Issue : Volume 10, Issue 07 (July 2021)
 Published (First Online): 26072021
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Seed Based Approach for Near Lossless to Lossless Image Compression
Tanuja R. Patil 1
School of Electronics & Communication Engg
K. L. E. Technological University Hubballi, India
Vishwanath P. Baligar 2
School of Computer science & Engg.

L. E. Technological University Hubballi, India
Abstract Image compression is inevitable nowadays as there is a huge transaction of data in the form of images .In this paper, a novel approach to achieve near lossless compression and further lossless compression, is discussed. Here a seed based technique over gray scale images to achieve better quality, has been discussed. In this technique, 4 bytes of data is converted into three bytes with a transformation technique. Later a seed data is added to achieve near lossless results. Further by adding additional seed data, lossless compression can be achieved. A metric called correctness ratio is used to measure the quality of the reconstructed images. The quality of reconstructed images is near lossless i.e. very high when compared with JPEG approach at same PSNR values. Results of lossless compression are just comparable with JPEGLS with slight compromise in compression ratio.
KeywordsImage compression; near lossless; lossless ; comparison with JPEG ; Seed based approach.

INTRODUCTION
Image compression is a type of data compression applied to digital images, to reduce their cost for storage or transmission, as most of the data transmitted nowadays is in the form of images. These images can be either color or gray scale.
For image processing tasks, gray scale images can be preferably used, as much of today's display and image capture hardware can only support 8bit images and it is more complicated and harder to process color images.
The gray scale pixel intensity value is stored as an 8bit integer with 256 possible different shades of gray from black to white. A lot of redundancy exists in the use of 8 bit representation. This redundancy exists in 3 major forms. i.e coding redundancy, interpixel redundancy and pshycho visual redundancy.
Compression can be achieved, if these redundancy can be reduced by suitable techniques. These image compression techniques will result into two types of compression i.e. lossless and lossy image compression. Lossless image compression is usually required for applications like medical field,where each & every detail is important. This is because lossy compression methods produce compression artifacts to images and sharpedged lines become blurr when using strong compression. But lossy compression is a good choice for natural images where slight loss is acceptable to achieve smaller file size. Lossy compression is usually based on techniques that removes certain information which the human eye typically doesn't notice. Mostly used lossy
compression methods are transform coding such as discrete cosine transform (DCT, used in JPEG) or wavelet transform (used in JPEG 2000). Similarly many researchers are trying with different transformation techniques.
The most widely used methods of lossless compression in images are runlength encoding (RLE), entropy coding and dictionary coders. Recently researchers are working with prediction based coding techniques to improve the compression ratio. In this paper, we discuss about a novel approach wherein 4 bytes of data is converted into three bytes by using a transformation technique by which lossy compression is achieved. A seed data is added to improve the quality, so that near lossless results have been achieved. further by adding additional seed data lossless compression can be achieved and these results are inpar with JPEGLS methods

LITERATURE SURVEY
Many research works are going on to improve the compression ratio, improve the quality of reconstructed images, decrease the computation cost and reduce time complexity. We surveyed many papers and listed some highlights.
Subramanya, A, gives an overview of the major image compression techniques. The Joint Photographic Experts Group (JPEG) is a standard developed for compressing continuoustone still images. And it has been widely accepted for still image compression throughout the industry. JPEG can be used on both grayscale and color images. [1]
Nedhal Mohammad AlShereefi, discuss about the wavelet based lossy image compression. to achieve high compression ratio in images using 2D daubechies mWavelet Transform by applying global threshold for the wavelet coefficients.[2]

Ulacha1 and R. Stasiski, discuss about an efficient and simple contextbased data modeling technique for lossless image compression. Similarly as preprocessing stage of JPEGLS, it uses only 3 contexts, which makes it time efficient, and does not force the message headers to be long. Enhanced, but more computationally complex versions of the method are also analyzed. Extensive experiments show that indeed, the new technique is clearly better from data compression point of view than the preprocessing stage of
JPEGLS, while its computational complexity is approximately the same.[3]
Mamatha A.S, Vipula Singh discuss about a simple
a
b
c
d
a
b
c
d
at row x
Where, f[x][y] is the 8 bit
163
164
163
161
163
164
163
161
pixel intensity value
arithmetic calculation which uses, finding the difference between pixels , for Near Lossless Image Compression . They have used Raster, Orthogonal, Diagonal and Snake scanning methods.CR and PSNR for base value 16 is 3.628 and 35.1912 respectively.[4]
Vishwanath P. Baligar, L.M. Patnaik, G.R. Nagabhushana discuss about the design and implementation of an image coding algorithm which uses a thresholding method. Threshold is the Peak Absolute Error (PAE) allowed in the reconstructed image. It has been shown that lossless edges with nearlossless filled area give a high fidelity images. Results are compared with Set Partitioning In Hierarchical Tree (SPIHT) and proven to be better . [5]
As per Sinisa ILIC, Mile PETROVIC, Branimir JAKSIC, Petar SPALEVIC, at lower PSNR levels, there will be noise effects from the compression methodology used in JPEG. Here Contour like structures appear, which are uncomfortable for better visibility. [6]
We have discussed about some lossy compression algorithms using surrounding pixels method, pixel count method and byte shrinking method, where it is shown that at low PSNR levels, number of exact pixels in reconstructed image increases, thus reducing the contour effects that may arise in JPEG at same PSNR values.[7,12,13]
From the above survey, we got the motivation to improve the quality of images which give good correctness ratio compared to JPEG. Hence we came up with a novel seed based approach to improve the quality of the images which is described in the next section.


METHODOLOGY
In this method, the gray scale image f[x][y],is divided into blocks of four pixels .These four pixels are processed and converted into three bytes of data to produce a transformed image. For a block of 4 pixels, three byte data is generated. Later seed data is added to get near lossless and lossless result, which is explained with compression and decompression algorithms below.
A Compression algorithm with examples

Three Byte generation
Gray scale image f[x][y],is processed in blocks of four pixels in raster scan manner as shown in Fig.1
Fig.1 block of 4 pixels Fig.2 Sample block
and column y.
a= f[x][y], b=f[x][y+1], c=f[x+1][y], d=f[x+1][y+1]
For e.g. consider 4 pixel values with, a=163, b=164, c=163, d=161 shown in Fig.2
Convert all the 4 pixel values to binary form as shown below.
a=10100011 (163), b=10100100 (164),
c=10100011 (163), d=10100001 (161)

Byte1 generation:
Byte1 is generated by combining 7th & 6th bits of each of the 4 pixels as shown.
Byte1= a[7] +a[6] + b[7] +b[6]+ c[7] +c[6] + d[7] + d[6] =10101010
Thus generated Byte1 is saved in a file sayByte1.

Byte2 generation
A, 3 bit data is generated by considering 5th,4th &3rd bits of each pixel. A bit position table is created and 1 is marked in that bit position indicated by 3 bit data. In the above example, bits at bit positions 5,4,3, can be written as follows. a[5,4,3] =100, b[5,4,3] =100, c[5,4,3] =100, d [5,4,3] =100
In all these 4 pixels, bits at 5,4,3 bit positions are 100
(3 bit data) and bit position in decimal is 4, hence 1 is entered in 4th position as shown in the Table 1.
TABLE 1. BIT POSITION TABLE FOR BYTE2
Pixels
Bit positions in decimal indicated by 5th,4th,3rd bits
7
6
5
4
3
2
1
0
a
0
0
0
1
0
0
0
0
b
0
0
0
1
0
0
0
0
c
0
0
0
1
0
0
0
0
d
0
0
0
1
0
0
0
0
Byte2 is generated by logical OR of a,b,c,d [5,4,3] bits. Byte2= a[5,4,3] OR b[5,4,3] OR c[5,4,3] OR d[5,4,3] Byte2=00010000  00010000  00010000  00010000
=00010000
Thus generated Byte2 is saved in a file sayByte2.

Byte3 generation
Byte3 is generated as described. The bit positions of 2nd ,1st and 0th bits of each pixel are checked and 1 is marked in the bit position indicated by 3 bit data. In the above example, bits at bit positions 2,1,0, can be written as follows.
a [2,1,0] =011 ( 3), b[2,1,0] = 100 (4), c [2,1,0] = 011(3) d[2,1,0] =
001 (1) .At these positions 1s are entered to generate byte3 as shown in Table 2.
TABLE 2. BIT POSITION TABLE FOR BYTE3
Pixels
Bit positions in decimal indicated by 2nd,1st,0th bits
7
6
5
4
3
2
1
0
a
0
0
0
0
1
0
0
0
b
0
0
0
1
0
0
0
0
c
0
0
0
0
1
0
0
0
d
0
0
0
0
0
0
1
0
Byte3 is generated by logical OR of a,b,c,d [2,1,0] bit representation.
Byte3= a[2,1,0]OR b[2,1,0]OR c[2,1,0]OR d[2,1,0]
Byte3=00001000  00010000  00001000  0000000
=00011010,
Thus generated Byte3 is saved in a file sayByte3


Seed Generation
Now, seed generation is done by counting the number of 1s in byte2 & byte3.The count of number of 1s in byte2 and byte3, will be either 1,2,3, or 4. If the number of 1s is one, reconstruction will be perfect and seed data is not required, but if the number of 1s is 2,3, or 4,we need to add extra bits called as seeds so that perfect or lossless reconstruction is possible. If the seeds for count 2 &3 are added, it will result in near lossless image i.e. very high quality image with good compression ratio and if seeds for count=4 are added, it will result in lossless image compression.

Seed generation for count of number of 1s in byte2 or byte3 =2
Consider another block of 4 pixels, where a count of 2is expected in byte2 or byte3.for e.g. a=163, b=157,c=163, d=157. Their binary representation can be given as a=10 100 011,b=10 011 101,c=10 100 011,d=10 011 101.Here,
bits at bit positions 5,4,3, can be written as follows a[5,4,3] =100, b[5,4,3] =011, c[5,4,3] =100, d [5,4,3] =011
Byte2 is generated by logical OR of a,b,c,d [5,4,3] bits as described in Table 2.
Byte2= a[5,4,3] OR b[5,4,3] OR c[5,4,3] OR d[5,4,3] Byte2=00010000  00001000  00010000  00001000
=00 011 000
Now ,to generate the seeds, the bit positions are encoded as follows i.e lower bit position(which is 3) is given the code0, and higher bit position (which is 4) is given the code as 1.
For pixel a, bit position is 4 , code is1.For pixel b, bit position is 3, code is 0 .For c, bit position is 4,code is 1 and for d, bit position is 3, code is 0. Hence a 4 bit seed named seed1 is generated by combining the code for each of them as,
Seed1=1 0 1 0
This is how a 4 bit seed is generated for one block and stored in a separate file say seed1 file.

Seed generation for a count of number of 1s in byte2 / byte3 =3
Consider another example of 4 pixels, where a count =3 is expected for e.g. a=163, b=157,c=143, d=157
their binary representation can be given as
a=10 100 011,b=10 011 101,c=10 001 111,d=10 011 101
In the above example, bits at bit positions 5,4,3, can be written as follows
a[5,4,3]=100, b[5,4,3] =011, c[5,4,3] =001, d[5,4,3] =011,and1 is
marked in bit position table
Byte2 is generated by logical OR of a, b, c, d [5,4,3] bit representation.
Byte2=a[5,4,3] OR b[5,4,3] OR c[5,4,3] OR d[5,4,3]
Byte2= 00011010 ( Thus here, number of 1s are three) Now , the bit positions are encoded as follows i.e lower bit position(here,1) is given the code00, middle bit position(here,3) is given the code01higher bit position(here.4) is given the code10
Now, the bit positions for a,b,c,d are checked and assigned the code as shown.
For pixels a,b,c,d, bit positions are 4,3,1,3 resply. Hence a 8 bit seed is generated by combining the code for each of them as,
seed2=10 01 00 01
This is how the seed is generated for number of 1s =3, and stored in a separate file say seed2 file.

Seed generation for number of 1s =4
Consider another example for e.g. a=163, b=157,c=178, d=143.Their binary representation can be given as
a=10 100 011, b=10 011 101,c=10 110 010,d=10 001 111
In above example, bit positions for the bits 5,4,3,can be written as follows
a[5,4,3] =100, b[5,4,3 =]011, c[5,4,3] =110, d[5,4,3] =001
Byte2 is generated by logical OR of a,b,c,d [5,4,3] bit representation.
Byte2=a[5,4,3] OR b[5,4,3] OR c[5,4,3] OR d[5,4,3] byte2= 01 011 010
The bit positions are arranged in ascending order and later the codes are assigned. Bit position1(i.e.1)=00, bit poition2(i.e.3) = 01 bit position3(i.e.4)=10, bit position4(i.e.6) =11.
Now, the bit positions for a, b, c, d are checked and assigned the code as shown.
Bit positions of pixels a,b,c,d are 4,3,6,1 resply. Hence 8 bit seed is generated by combining the code for each of them as, seed3=10 01 11 01
This is how the seed is generated for number of 1s =4, and stored in a separate file say seed3 file.


Byte and seed generation for bits at 2,1,0 positions
Similarly for the bits[2,1,0] , above steps as mentioned in

& III.A.2 are repeated to generate the seeds & saved in seed4,seed5,seed6 files.
All the above transformed files are further Huffman compressed to achieve better compression.

Decompression algorithm
If the image is reconstructed with the transformed three bytes without the seeds, it will result into lossy image with very low PSNR. But near lossless image with high PSNR can be achieved by reading seeds file generated for count=2 and 3.It will result into high quality image.

Decompression algorithm to achieve Near Losssless compression
Read and Huffman decode the following files, byte1,byte2,byte3,seed1,seed2, seed4,seed5 to reconstruct all 8 bits of 4 pixels.

Reconstruction of 7th & 6th bits
Bits at bit position 7 & 6 for all 4 pixels is obtained from byte1 file.

Reconstruction of bits 5,4,3
Bits at bit position 5,4,3 have to be reconstructed from the byte, read from byte2 ,seed1 & seed2 files.
Read the byte from byte2 file, Get the count of number of 1s. Arrange the bit positions in ascending order. i.e. lower bit position (L) & higher bit position(H).
If the count is 2, read the seed1 file to get the seed value. From the seed value, get the code to assign the bit positions. for e.g.if seed value is (1 01 0),then higher bit (H)is assigned to pixel a[5,4,3] & c[5,4,3], (L) is assigned to b[5,4,3] & d[5,4,3]. Thus we can reconstruct bits 5,4,3 of all 4 pixels.
If the count is 3, read the seed2 file to get the seed value. From the seed value, get the code to assign the bit positions. for e.g. if seed value is (01 10 01 00),then middle bit (M)is assigned to pixel a[5,4,3] ,(H) is assigned to b[5,4,3],(M) is assigned to c[5,4,3] and (L) is assigned to d[5,4,3].Thus we can reconstruct bits 5,4,3 of all pixels.

Reconstruction of bits 2,1,0.
Similarly bits [2,1,0] can be reconstructed by the same procedure as described above in III.B.1 section, by reading byte3,seed4 and seed5 files.
For a count of number of 1s =4, the bit positions are assigned randomly to each of the four pixels. By this, we may get slight loss in the reconstruction , but, energy of four pixels is retained and it results in near lossless compression which is described in section IV.
But by adding seeds for count=4 we get lossless compression which is explained in section IV.


Decompression algorithm to achieve lossless image compression



Repeat Steps explained in section III.B.1

If the count of number of 1s in byte2 or byte3=4, then read the fileseed3 to reconstruct 5th,4th,3rd
bits of all 4 pixels. and by reading seed6 file ,reconstruct 2nd.1st.0th bits of all 4 pixels. By this reconstruction procedure all the bits of 4 pixels can be reconstructed and lossless compression can be achieved. And results are discussed in section IV.


DISCUSSION OF RESULTS
A Results for near lossless compression
Above algorithm is implemented on standard test images and reconstructed images are shown in figures Fig3Fig.8.Left side are the original images and right side are the reconstructed images. We can see the quality of reconstructed images, which is very high .They almost resemble the original image . The quality of reconstructed image is measured by another metric called as correctness ratio to measure how many pixels are same as original in the reconstructed image and are tabulated in Table 3 & 4. The Compression ratio achieved by our approach is in the range of 1.31.5. Results show that , using this approach reconstructed image is near lossless with high PSNR. The correctness ratio is also higher i.e .the number of correct pixels as that of original using our approach are far higher than JPEG approach measured at same PSNR values.
Table 3 Comparison of correct pixels with JPEG
Images
PSNR
Correct pixels obtained by JPEG
approach
Correct pixels by our approach
Lena
41.14
50,484
179631
Barbara
38.58
40486
166163
Baboon
36.66
30182
148482
Boat
39.68
49586
171708
Ayamatsura
39.67
52478
180864
pepper
38.7
39,867
1,75,324
Table 4 Comparison of correctness ratio with JPEG
Images
PSNR
Correctness ratio by JPEG approach
Correctness ratio by our approach
Lena
41.14
0.19
0.68
Barbara
38.58
0.15
0.63
Baboon
36.66
0.11
0.56
Boat
39.68
0.18
0.65
Aya matsura
39.67
0.2
0.68
pepper
38.7
0.15
0.67

Results on Images
Fig 3 Lena Fig.4 Barbara
Fig. 5 Baboon Fig, 6 Boat
Fig. 7 Aya Matsura Fig. 8 Pepper

Results for lossless compression
We have implemented lossless algorithm for the above listed images and obtained fully perfect images without any loss. Table 5 shows the bits per pixel (bpp) required for our algorithm as compared to JPEGLS and these results show that bpp is slightly higher , but this approach gives a simple and innovative approach for lossless compression.
Table 5 Compression ratio and bpp for lossless compression
Images
C.R.
Bpp with Jpeg LS
Bpp with our algorithm
Lena
1.35
4.24
5.54
Barbara
1.28
5.0
5.9
Baboon
1.27
5.2
6.0
Boat
1.34
4.25
5.6
Ayamatsuura
1.36
4.1
5.41
pepper
1.30
4.71
5.57


CONCLUSION AND FUTURE SCOPE

Using seed based approach, reconstructed image is near lossless with high PSNR. The correctness ratio is also higher i.e .the number of correct pixels as that of original using our approach are far higher than JPEG approach measured at same PSNR values. Lossless image also can be obtained with a slight compromise with compression ratio. This approach is less computation intensive, with time complexity O(n2). It is simpler approach for compression as well as decompression. Further compression ratio can be improved by optimizing the encoding method of seeds.
ACKNOWLEDGMENTI wholeheartedly thank our guide Dr. Vishwanath P. Baligar for his constant guidance and motivation throughout the work. I Thank our Vice Chancellor Dr.Ashok Shettar and Principal, Dr.P.G.Tewari for providing all the support and facilities required to carry out the work. I thank our H.O.D. Dr. Nalini C.Iyer for her constant support and encouragement. I thank all those who has directly or indirectly supported to carry out the research work.
REFERENCES

Subramanya, A. (2001). Image compression technique. IEEE Potentials, 20(1), 1923. doi:10.1109/45.913206

Nedhal Mohammad AlShereefiImage Compression Using Wavelet Transform Journal of Babylon University/Pure and Applied Sciences/ No.(4)/ Vol.(21): 2013

G. Ulacha1 and R. Stasiski2 new simple contextbased technique for lossless image compression.

Mamatha A.S, Vipula Singh, Near Lossless Image SystemAsia Pacific Conference on Postgraduate Researchin Microelectronics & Electronics (PRIMEASIA),Dec 2012

Vishwanath P. Baligar, L.M. Patnaik, G.R. Nagabhushana ,Low complexity, and high fidelity image compression using fixed threshold methodwww.Elsevier.com ,Information Sciences 176 (2006) 664675

Sinisa ILIC, Mile PETROVIC, Branimir JAKSIC, Petar SPALEVIC, Ljubomir LAZIC, Mirko MILOSEVIC, Experimental analysis of picture quality after compression by different methods, PRZEGLD ELEKTROTECHNICZNY, ISSN 00332097, R. 89 NR 11/2013 9.

T. R. Patil, V. P. Baligar and R. P. Huilgol, "Low PSNR High Fidelity Image Compression Using Surrounding Pixels," 2018 International Conference on Circuits and Systems in Digital Enterprise Technology (ICCSDET), Kottayam, India, 2018, pp. 1 6, doi: 10.1109/ICCSDET.2018.8821082.

Fabian Mentzer, Eirikur Agustsson Michael Tschannen Radu Timofte Luc Van Goo Conditional Probability Models for Deep Image Compression
https://openaccess.thecvf.com/content_cvpr_2018/papers/Mentzer.

V.P.Baligar L.M.Patnaik, G.R.Nagabhushan, High compression and low order linear predictor for lossless coding of grayscale images www.elsevier.com,Image& vision computing21(2003) 543550 5.

M. J. Weinberger, G. Seroussi, and G. Sapiro, LOCOI: A low complexity, contextbased, lossless image compression algorithm, in Proc. 1996 Data Compression Conference, Snowbird, UT, Mar. 1996, pp. 140149 6.

A. M. Raid, W. M. Khedr, M. A. Eldosuky and Wesam Ahmed, Jpeg image compression using discrete cosine transform – A survey, International Journal of Computer Science & Engineering Survey (IJCSES) Vol.5, No.2, April 2014 7.

Tanuja R.Patil ,Vishwanath P.Baligar, A pixel count approach for lossy image compression In book: ICT Analysis and Applications (pp.369377) DOI:10.1007/9789811583544_37.

Tanuja R.Patil ,Vishwanath P.Baligar, Byte shrinking approach for lossy image compression ICTCS 2020,First online 67 21,DOI: 10.1007/9789811608827_13