Lifting based Image Compression using Intelligent Water Drop Algorithm

Lifting based Image Compression using Intelligent Water Drop Algorithm

Abstract Image compression is one of the most important and successful applications of the wavelet transform. Images contain large amounts of information that requires much storage space, large transmission bandwidths and more transmission time. Therefore it is advantageous to compress the image by storing only the essential information needed to reconstruct the image. This paper proposes a new technique for Lifting Scheme based Image Compression using Intelligent Water Drop Algorithm. Intelligent Water Drop (IWD) Algorithm is a nature inspired Swarm Intelligence based optimization algorithm which mimics the behavior of natural water drops in the river. Lifting based IWD scheme is applied for Image Compression and Parameters such as Compression Ratio (CR), and Peak Signal to noise ratio (PSNR) have been calculated. A compressed image having a high PSNR value is the best compressed image.

Keywords-Image compression, Lifting Scheme, Swarm Intelligence (SI), Intelligent water drop algorithm (IWD), Peak Signal to Noise Ratio (PSNR), Compression Ratio (CR).

1. INTRODUCTION

   In recent years, Digital images play an important role both in daily life applications as well as in areas of research and technology. Uncompressed graphics, audio and video data require considerably more storage capacity and high transmission bandwidth. The basic objective of image compression is to reduce the irrelevant and redundant information and maintaining the original quality or providing an acceptable fidelity. Redundancy reduction can achieved by removing repeated bits or extra bits. While in irrelevant data reduction the less important or smallest information is omitted, which will not be received by receiver. Image Compression is beneficial because it helps in reducing the usage of expensive resources like hard disk space, transmission bandwidth.

   Compression can be achieved by removing one or more of the following three types of redundancies:

   1. Coding Redundancy

   2. Inter-pixel Redundancy

   3. Psycho visual Redundancy

   Coding redundancy is exists when there is less number of optimal code words which are used while coding.

   Inter pixel redundancy occurs from correlated pixels of an image.

   Psycho visual redundancy exists because some of the data is ignored by the human visual system. Image compression is deployed to reduce the number of bits stored in an image which represent the image.

   There are various types of image formats such as BMP (Windows Bit Map), TIFF (Tagged Image File Format), PNG (Portable Network Graphics), JPEG (Joint Photographic Experts Group), etc. among all these image formats JPEG image format widely accepted in imaging industries and multimedia. JPEG stores 24 bit photographic images. JPEG image is a 24 bit color format hence it can store millions of colors and it is more superior when compared with other formats. JPEG supports 24 bit color images and 8 bit gray scale images.

   The image compression techniques are mainly classified into two categories:

   1. Lossy technique

   2. Lossless technique

   • Lossy technique provide high compression ratio when compared lossless technique, but the image after compression degrades with respect to quality. Basically lossy image compression methods use a transformation based techniques.

   • Lossless technique provides much lower compression ratios than lossy compression technique. The image after compression will have good quality. This technique will not add noise to the signal hence they are also known as noiseless scheme. To minimize the redundancy this technique uses decomposition, hence it is also called as entropy coding.

     Image compression algorithm depends on the three factors:

     • Amount of compression

     • Quality of an image

     • Speed of compression

   All the above three factors can be measured using the Performance Metrics such as PSNR, MSE, CR, Encoding and Decoding time.

   Peak Signal to Noise Ratio (PSNR) and Mean Square Error (MSE) are two performance parameters used to

   calculate the performance of an image compression technique. The Mean Square Error is a cumulative squared error between the original image and the compressed image, whereas PSNR value is the measurement of the peak signal error between the original image and the compressed image. If we find a compression scheme having a high PSNR and a lower MSE, we can recognize that it is a better one.

2. LIFTING SCHEME

   The lifting scheme is a new method to construct wavelet basis, which was first introduced by Sweldens. The lifting scheme entirely relies on the spatial domain, has many advantages compared to filter bank structure, such as lower area, power consumption and computational complexity. The lifting scheme can be easily implemented by hardware due to its significantly reduced computations. Lifting has other advantages, such as in-place computation, integer-to-integer wavelet transforms which are useful for lossless coding. The lifting scheme has been developed as a flexible tool suitable for constructing the second generation wavelets. It is composed of three basic operation stages: split, predict and update.

   The three basic steps in Lifting based technique are:

   • Split Step: where the signal is split into even and odd points, because the maximum correlation between adjacent pixels can be utilized for the next predict step. For each pair of given input samples X[n] split into even Xe[n] and odd coefficients Xo[n]

     Where

     Xe [n] = X [2n] and Xo [n] = X [2] (1)

   • Predict Step: The even samples are multiplied by the predict factor and then the results are added to the odd samples to generate the detailed co-efficient d[n]. Detailed co-efficients results in high pass filtering.

     D [n] = Xo [n] P (Xe[n]) (2)

   • Update Step: Once the detailed coefficients are computed by the predict step, detailed coefficients are multiplied by the update factors and then the results are added to the even samples to get the coarse co-efficients c[n]. The coarser co-efficients gives low pass filtered output.

     C[n] = Xe[n] + U (d [n]) (3)

     The basic block diagram of the Lifting based technique is shown in Fig 1.

     Fig. 1: Basic block for Lifting based technique

     The Forward Lifting Scheme and Inverse Lifting Scheme is shown in the Fig 2 and 3.

     Fig. 2: Forward Lifting Scheme

     Fig. 3: Inverse Lifting Scheme

     Lifting Scheme is formed by the three steps. The Lifting steps can be easily inverted, even if P (Predict) and U (Update) are space-varying or nonlinear.

3. SWARM INTELLIGENCE

   Swarm Intelligence was introduced by Jing Wang and Gerardo Beni in the year 1989.Swarm Intelligence is based on the collective behavior of self-organized system which consists of many individuals that are coordinated and organized by the principles of indirect communication, self- organiation and decentralized control. Swarm Intelligence Systems typically consists of a population of simple boids or agents that interact locally with one another and in their environment.

   Some of the natural Swarm Intelligence System include bird flocking, animal herding, fish schooling, and bacterial growth.

   Various algorithms belonging to this domain are

   • Ant colony optimization

   • Artificial bee colony algorithm

   • Particle swarm optimization

   • The bees algorithm

   • Artificial immune systems

   • Grey wolf optimizer

   • River Formation optimization

   • Bat algorithm

   • Gravitational search algorithm

   • Glowworm swarm optimization

   • River Formation Dynamics

   • Self-propelled particles

   • Multi-swarm optimization

   • Stochastic diffusion search

   • Intelligent water drop algorithm.

     Swarm Intelligence is the collective behavior of decentralized, multi-agent, self-organized systems that shows intelligent behavior.

4. INTELLIGENT WATER DROP ALGORITHM The intelligent water drops (IWD) algorithm is a swarm-

   based optimization algorithm which was introduced in the year 2007, was resulted from observing flow of water drops in the rivers. Natural water drops in the river on its way from the source to destination often finds an optimal paths among lots of possible paths. These optimal paths are obtained by the reactions and action that takes place between the water drops and the water drops on the riverbeds. The Intelligent water drop algorithm has been used for solving the travelling salesmans problem (TSP) and multiple (or multidimensional) knapsack problem (MKP).

   Intelligent water drop algorithm is an optimization algorithm. It mimics the behavior of natural water drops in the river. The algorithm uses water drops to collectively search for optimal solutions. Each water drop constructs a solution to the problem by moving on the graph representation of the problem. Then among the obtained solution the best one in terms of quality is chosen.

   During Each iteration, an Intelligent Water drop algorithm gains some velocity and removes some soil from the path it flows on. After enough iterations of Intelligent Water drop algorithm it finds the good path that are decoded to good solution of the problem.

5. PROPOSED WORK

   Image compression is the process of minimizing the size of an image without degrading its quality. As the multimedia images are growing in huge numbers one of the major factor for this is the use of smart phones, hence the image compression has become a necessity as it saves network traffic, bandwidth, and disk space. There are many different ways in which images can be compressed, The Lifting scheme is one among them.

   Lifting Scheme is a method to generate the wavelets in an efficient way. When compared to classical filter banks method the Lifting Scheme has some advantages , such as the simple and fast hardware implementation, the ease of inverse implementation, the fewer and simpler arithmetic computations required, occupying less memory storage, in addition, the Lifting Scheme is more appropriate for low power and high speed applications such as the video or image/ processing applications. In addition to this Intelligent Water Drop algorithm based image Compression is a new technique using which the results of compression are far better in comparison to the effective Compression.

   Fig. 4: Proposed block diagram

   In the proposed work first the user would Input some standard images once the image is selected the goes through some preprocessing step where the image would be converted into grayscale and finally the image would be resized into 512*512. Once the image is preprocessed the Lifting scheme is applied for the preprocessed image wherein we are going to obtain four Sub Bands LL, LH, HL, and HH. Among this four sub bands the original image will only be present in the LL Sub band and in all the other three sub bands we would have the distortion so we are finally going to take the LL Sub band and we would perform the Optimization on this band. For performing the optimization we are going to choose Intelligent Water drop Algorithm. After some iterations of Intelligent Water drop Algorithm we are going to obtain some optimized result and that result would be displayed to the user.

   Algorithm Design

   Step 1: Image Acquisition.

   Step 2: Bi-part the whole image using Lifting Scheme to obtain four sub bands.

   Step 3: Intelligent Water Drop (IWD) Parameter initialization (Coefficients of image)

   • Static Parameter initialization: The number of water drops NIWD as to be a positive integer value, which is set to the number of values Nc of the graph.

     And again velocity updating, the parameters such as av= 1, bv= .01 and cv= 1 are specified.

   • Dynamic Parameter initialization: Soil & velocity of IWDs

     Every IWD has a visited node list Vc (IWD), which is initially empty: Vc (IWD) = { }. Each IWDs velocity is set to InitVel. All IWDs amount of soil has been set to zero.

     Step 4: Calculate weight values of sub band images which is equal to soil content of the sub band image.

     W = ()(), = 0

     =1

     W = ()(), = 0

     =1

     Step 5: On the basis of water drop, Depart matrices by adding

     water drops one by one.

     Step 6: For each IWD moving from pixel i to pixel j, update its velocity velIWD (t) by

     ( + 1) = () +

     + . 2(, )

     Where velIWD (t +1) is the updated velocity of the IWD.

     Step 7: Solution construction by IWDs along with water drop velocity updating.

   • Neglect the content with higher soil values.

   • Continue with lower soil values.

   Step 8: Generate a new matrix & compare new matrix with sub band images.

   Step 9: Reconstruct the whole image by applying Inverse Lifting Scheme.

   The purpose of this work is to enhance the results for the lossy image and to compare the values of the results. The problem taken for this research work is divided into following objectives: To reduce the size of compressed image. To reduce the elapsed time of compression by using intelligent water drop algorithm. Completion of above two objectives with minimum distortion in reconstructed image. Comparing on the basis of PSNR.

6. EXPERIMENTAL RESULTS

   The whole design of the Lifting based image compression using Intelligent water drop algorithm is simulated in MATLAB R2010a. The compression is done based on the compression ratio given by the user. Finally for the given compression ratio the image gets compressed and PSNR gets generated. PSNR is used for measuring the quality of an image. Higher the PSNR values better the quality of an image.

   a) Lena Image b) Reconstructed Lena Image

   a)Mandrill image b)Reconstructed Mandrill image

   a)Airplane image b)Reconstructed Airplane image

   The original images and the compressed image are shown in the below fig 5(a) and (b) where the first image is the original image second one is compressed image.

   a) Pepper image b) Reconstructed Pepper image

   a)House image b) Reconstructed House image

   Fig. 5: a) Original Image b) Reconstructed Image

   The performance is evaluated for Pepper image, House image, Lena image, Mandrill image, and Airplane image on the basis of parameter like PSNR (Peak Signal to Noise Ratio) and Compression ratio the results are obtained and are tabulated as shown in Table I. On basis of results obtained this technique is giving best compression results for pepper image.

   TABLEI

   PSNR VALUES FOR SOME STANDARD IMAGES WITH RESPECT TO THEIR COMPRESSION RATIO

   Compressi on Ratio (CR)	Table shows the PSNR Values for different images against the ompression ratio
   	Pepper Image	House Image	Lena Image	Mandrill Image	Airplane Image
   30	40.1144	39.5578	40.8102	39.8314	39.983
   40	36.8718	34.539	37.0098	35.8622	35.7795
   50	36.6189	34.4273	36.3096	35.8589	35.6749
   60	32.6094	33.5004	31.1514	31.5280	34.4979
   70	32.6094	3.5004	31.1514	31.5280	34.4979

   Chart for the standard images

   50

   40

   30

   20

   10

   0

   CR30 CR40 CR50 CR60 CR70

   Pepper image House image Lena image

   Mandrill image Airplane image

   Pepper image House image Lena image

   Mandrill image Airplane image

   Fig. 6: Graph showing PSNR values for different images.

7. CONCLUSION

   The idea of designing and implementation of image compression project is born with the observation in our visualization in the web. We have presented an integrated framework for the image compression using intelligent water drop algorithm. The implementation of the Intelligent Water Drop based compression obtains the high Peak signal to noise ratio. The results obtained are promising when compared with other optimization technique, the pepper image has higher PSNR when compared with other standard database images. The higher the Peak signal to noise ratio better the quality of an image

8. FUTURE ENHANCEMENT

   In future work, Intelligent Water Drop Algorithm can be implemented by using the threshold value so that it can reduce the number of coefficients which represents the image by optimally selecting the threshold value to get better quality and compression. Adaptive Lifting Scheme can be implemented where it can reconstruct the wavelets without any overhead cost.

9. REFERENCES

1. Shu-Chuan Chu, Hsiang Cheh Huang, John F. Roddick, and JengShyang Pan, Overview of Algorithms for Swarm Intelligence, Springer-Verlag Berlin Heidelberg, Vol 1, pp. 2841, 2011.

2. Nazneen Tarannum S, H. Rizvi, and Prof .R .R .Keole, Preliminary Review of swarm Intelligence: A Clever Algorithm and Data Clustering, International Journal of Computer Science and Information Technologies, Vol .5(2), pp.1892-1899, 2014.

3. Simranjeet Kaur, Prateek Agarwal, and Rajbir Singh Rana, Ant Colony Optimization: A Technique used for Image Processing, International Journal of Computer Science and technology, Vol. 2(2), June 2011.

4. Nada M. A. Al Salami, Ant Colony Optimization Algorithm, UbiCC Journal, Vol. 4, Num. 3, August 2009.

5. M. Mohamed Ismail and Dr. K. Baskaran, Adaptive Lifting Based Image Compression Scheme Using Artificial Bee Colony Algorithm, International Journal of Electronics Communication and Computer Engineering Vol. 4(1), 2013.

6. Vrinda Shivashetty and G.G Rajput, Adaptive Lifting Based Image Compression using – Interactive Artificial Bee Colony Algorithm, International Journal of Science and Research (IJSR), Vol. 3(7), July 2014.

7. R.Ramanathan, K.Kalaiarasi, and D.Prabha, Improved wavelet based compression with adaptive lifting scheme using Artificial Bee Colony algorithm, International journal of advanced research in computer engineering & technology, Vol. 2(4), April 2013.

8. Nishat kanvel, Dr.S.Letitia, and Dr.Elwin Chandra Monie, Adaptive lifting based image compression scheme with PSO (particle swarm optimization) technique, International Journal of Engineering Science and Technology, Vol. 2(9), pp.4886-4895, 2010.

9. M.Mohamed Ismail and Dr.K.Baskaran, Clustering Based Adaptive Image Compression Scheme Using Particle Swarm Optimization Technique, International Journal of Engineering Science and Technology, Vol. 2(10), pp.5114-5119, 2010.

10. Hamed Shah Hosseini, The IWD (intelligent water drops) algorithm a nature inspired swarm based optimization algorithm, International Journal Bio-Inspired Computation, Vol. 1, pp. 1-2, 2009.

11. Jaspreet Kaur Sidhu, Harish Kundra, IWD Based Image Compression, International Journal of Advances in Computer Science and Communication Engineering (IJACSCE), Vol. 1(1), November 2013.

12. H.S. Hosseini, Problem solving by IWD (intelligent water drops), Proceedings of IEEE Congress on Evolutionary Computation, pp.32263231, September 2007.

13. Shah-Hosseini, Intelligent water drops (IWD) algorithm: a new optimization method for solving the multiple knapsack problem, International Journal of Intelligent Computing and Cybernetics, Vol. 1, No. 2, pp.193212, 2008.

14. D.K.Sonal, A Study of Various Image Compression Technique, National Conference on Challenges & Opportunities in Information Technology, 2007.

BIOGRAPHY

Vivek G received B.E from Sri Revana Siddeshwara Institute of Technology and presently pursuing Mtech in Computer Science from Sai Vidya Institute of Technology.

Vrinda ShivaShetty received B.E from Gulbarga University and M.Tech degree from VTU in Computer Science and Engineering and presently pursuing Ph.D. in Image Compression from the University of Gulbarga, Karnataka. Field of Interest includes Evolutionary Computaion, Image Processing.

Dr. G. G. Rajput currently working as Associate Professor in the Department of Computer Science at Rani Channamma University Belagavi, Karnataka State, India. The Area of interest includes Image processing, Pattern recognition, Operations Research and Software Engineering.