Increasing Compression Rate of Images Through Data Representation using Spiral Path and Biplanes

Increasing Compression Rate of Images Through Data Representation using Spiral Path and Biplanes

Elda CINA1,

1Information Technology Faculty,Aleksander Moisiu, University of Durres,

Durrës,Albania

Esmerald ALIAJ12 1Information Technology Faculty,Aleksander Moisiu, University of Durres, Durrës,Albania

Habib HAMAM2,3

Faculty of Engineering, University of Moncton, Canada

3School of Engineering, Canadian Institute of Technology, Albania

Abstract Images are important pieces of information in our lives. Peoples requirement for quality is rising every day following the even faster grow of technology. Due to memory limits or medium bandwidth capacity, compression is indispensable. The most delicate type of images to compress are those where precision is very important and error margin must be almost zero. Compression through data representation with combinations is a very interesting method because of the huge number of opportunities it presents. With this paper we are going to introduce an evolution of Spiral technique which is based on data representation through combinations. This new technique gives bigger compression rate with a very small, nearly irrelevant loss, without sacrificing a lot of CPU time. Using Spiral path we also touch fields of information security, such as Cryptography, Steganography and Watermarking.

Key wordsInformation security, Combinations, Compression, Compression rate, Spiral path.

1. INTRODUCTION

   A digital signal is generally represented by a matrix of samples (1D-speech, 2D-images, and 3D-objects in space). Each sample is expressed in binary way by a sequence of bits. If we take in consideration images we can say that an image with width W and height H is represented by W*H pixels. Each of the pixels (samples) could take values from 0 to 255 (if we limit our discussion to gray levels).

   So to memorize an image we need W*H* 8 bits. For the sake of brevity we will not consider information in the header (format type, size of the image, compression ratio, etc).

   Compression could be lossless or lossy. Lossless techniques are very important in applications where precision is very important, such as in medical imaginary or space research. Some of the most known techniques for lossless compression are:

   • Run length encoding (RLE) [1]

   • Huffman encoding [2,5]

   • Lempel-Ziv-Welch coding (LZW) [3,5]

   • Arithmetic coding [4]

   • Delta encoding [5]

   • Transform-based compression [5]

   • Data representation through combinations [6]

   According to references [6] [9], there exist a method called Spiral which gives us a very satisfying compression rate around 4:1 compared to classical method which usually offer a compression rate of factor 2. With this paper we show how this method can be used in lossy compression. By removing only two bit planes for each pixel, a change of the gray value up to 3 levels darker occurs. This type of change is almost imperceptible for the human eye.

   This paper is organized within 6 sections. It starts with a general introduction, the second section is a description of data Representation through Combinations method, the third one is a description of Compression through Spiral Path technique. The fourth section is our approach of image compression. The fifth section follows with results and method performance. Concluding remarks are then given in section 6.

2. DATA REPRESENTATION THROUGH

   COMBINATIONS

   According to the data representation through combination technique the signals are defined in a new way from the general. Instead of explicating the pixels and writing them in the file, a unique number is assigned to each combination of pixels. This number is referred to as index in what follows. Thus an image is nothing but a combination of pixels and this combination is numbered. This enables not only flexible intrinsic compression but also encryption methods.

   For example if we take in consideration a simple image of 4 pixels and 3 gray levels ( L= 0, 1, 2) with all possible combinations we could built the table below:

   TABLE I. ALL COMBINATION WITH 4 PIXELS AND 3 GRAY LEVELS

   For more details on this method or how to get better compression rate rearranging indexes you can refer to [6-9].

3. COMPRESSION THROUGH SPIRAL PATH

   The first step of transporting images is transforming them to 1D signal and then converting them to a binary form. The conventional way is to put the image rows one after the other. The spiral path method uses another approach. It builds the 1D signal arranging the pixels through a spiral path as pointed out in Figure 1. By adopting this idea we can take advantages from the histogram and the variability methods mentioned in the above section [6-9]. After the spiral path we built the table of combinations starting from the middle variable image. The middle variable image is the image starting from the most frequent gray level. The pixels differ from the first pixels accordingly:

   combination	s[1]	s[2]	s[3]	s[4]
   0	0	0	0	0
   1	0	0	0	1
   2	0	0	0	2
   3	0	0	1	0
   4	0	0	1	1
   5	0	0	1	2
   …	…	…	…	…
   9	0	1	0	0
   10	0	1	0	1
   11	0	1	0	2
   ….	….	….	….	….
   18	0	2	0	0
   …	….	….	….	….
   27	1	0	0	0
   …	….	….	….	….
   54	2	0	0	0
   ….	….	….	….	…..
   72	2	2	0	0
   73	2	2	0	1
   74	2	2	0	2
   75	2	2	1	0
   76	2	2	1	1
   77	2	2	1	2
   78	2	2	2	0
   79	2	2	2	1
   80	2	2	2	2

   pixel i pixel i 1

   pixel 0 n

   pixel 0 n

   mod ulo

   mod ulo

   256

   256

   (1)

   Where n 1, 2, 127

   123	123	123	123
   154	154	154	136
   154	180	154	123
   180	180	166	123
   167	166	149	136

   Figure 1. Gray image with size (5*4)

   Figure 2. Converting a 2D array into 1D

   As we can see from the table if our image is represented from index 5 we need only three bits to represent it instead of 8 bits ( 4 pixel x 2 bits per value) of the conventional case. This leads to a compression ratio of 8/5 or 1,6 : 1.

   Lets take another index, the biggest number 80. We need 7 bits to represent that number which is also lower than the general case of 8 bits.

   In general the compression ratio varies from:

   Using this technique, it has been proved that the image would be, maybe not in the beginning of the table of combinations but obviously near it.

   To optimize the technique the start point pixel is chosen that pixel (over many which satisfy the histogram approach) which has the lowest variability.

   to (combinations 0 and 1):

   N

   f (x)

   i1

   a(i) a(i 1)

   N

   min

   (2)

   The images tend to be big. In such a case we cannot process the image as a whole because of computers architecture limits so we need to divide it into blocks. Thus, after compression we have a group of indexes which leads into relative slow compression and decompression process.

   For more details on this method or how to get better compression rate rearranging indexes you can refer to [9].

4. PROPOSED APPROACH

   Image lossless compression is very important in medical imaging, technical drawings, space studies etc. The compression method through spiral path gives us a satisfying compression rate compared to already known algorithm. It gives us the opportunity to obtain a compression rate of 4:1 independently from the image.

   But we can go further for a better performance if we loss slightly some information. As it is known a digital image is represented by pixels and each pixel is compound of bits.

   We have taken into consideration images with 8bit/pixel (bpp) precision. Each pixel has a gray value between 0 and 255 (gray levels). We consider the 8bpp data in the form of 8 bit planes, each bit plane associated with a position in the binary representation of the pixels.8 bit data is a set of 8 bit planes. Each bit plane may have a value of 0 or 1 at each pixel, but together all the bit planes makeup a byte with value from 0 to 255.

   Figure 3. Image sample into its bit planes

   If we scarify some of them we can obtain a better compression ratio from the one mentioned before. According to several experiments it has been proved that removing the two lowest bit planes brings us to a compression ratio of 5.3333..:1.

   This loss is very small because 2 lowest bit planes give a difference on the pixel intensity up to 3 levels of gray. More specific:

   Bit plane 8 = 1*20=1 Bit plane 7 = 1*21=2

   This difference from the original almost impossible to be noticed. Based on this we can say that this type of compression is almost lossless.

5. RESULTS

   A number of experiments have been carried out in order to evaluate the performance of the proposed Algorithm. Different sizes and contents have tested. According to this theory, we obtain a compression rate of 5.333:1 in any case. At the end of the paper are shown some of the tests followed by the real and intensified error.

   As you can see the error is almost imperceptible. This type of compression like the method through spiral is also image independent compressing technique.

   Removing bit planes, except the higher compression rate gives also better performance in time of processing. Using pixels represented with six bits, gives the opportunity to work with base 64 numbers instead of base 256, which leads into smaller combination table, bigger blocks and less indexes. According to this, time of processing is reduced with a factor of 2.

6. CONCLUSIONS

With this paper we introduce a new technique of image compression through combinations representation method. We propose a lossy version of Spiral technique through removable of 2 bit planes. It gives a better compression rate compared with the lossless one form 44 to 5.33. While this method which is lossy can still be used in delicate image processing. Another significant advantage is the lower time of processing( almost half of it). This technique is independent of image size or gray levels distribution on pixels. Using spiral path bring also big opportunities into information security issues such as cryptography, steganography and watermarking. These aspects and other are going to be taken in consideration by us into future perspective.

REFERENCES

1. Comparison of JPEG image coders. Grgic, S. Mrak, M., & Grgic, M. (2001) Retrieved October 23, 2003, from http://www.vcl.fer.hr/dtv/sgrgic_vip2001.pdf

2. A Hybrid Image Compression Technique, Acoustics Speech & Signal Processing, Dr. Charles F. Hall, , IEEE International Conference on ICASSP 85, Vol.10, pp 149- 152, Apr, 1985

3. "Optimized RTL design and implementation of LZW algorithm for high bandwidth applications". Electrical Review 2011 (4): 279285.

4. Generalized Kraft Inequality and Arithmetic Coding. IBM Journal of Research and Development 20: 198203. doi:10.1147/rd.203.0198 J. Rissanen (1976).

5. S. Smith, The Scientist and Engineer's Guide to Digital Signal Processing, Elsevier Science, ISBN-13: 9780750674447 (2002)

6. A new representation of data through combinations, H. Hamam, ICCAT 2013,

7. A New Representation of Image Through Numbering Pixel CombinationsJ. Said, R. Souissi, H. Hamam pg. 46 Journal of Information Security Research Volume 4 Number 1 March 2013

8. Increasing Compression Rate Of Images Through The Method Of Numbering Combinations E.Cina, H.Hamam ISTI 2013

9. Compressing 2D Images through data representation using spiral path,

E. Cina, E. Aliaj, H. Hamam, ISTI 2014

Figure 4. Test images ( Lena, Asja, Peppers, Baboon, Ajla, Children)

Below you can find numerical details of test images we took in consideration:

TABLE II. NUMERICAL RESULTS ON SPIRAL WITH LOSS TECHNIQUE