Lifting based Image Compression using Intelligent Water Drop Algorithm

Download Full-Text PDF Cite this Publication

Text Only Version

Lifting based Image Compression using Intelligent Water Drop Algorithm

Vivek G

Mrs. Vrinda Shivashetty

Dr. G. G Rajput

Student (M-Tech), Department of CSE

Asst. Prof. Department of ISE

Associate Professor, Dept. of CS

Sai Vidya Institute of Technology

Sai Vidya Institute of Technology

Rani Channamma University

Bangalore, India

Bangalore, India

Belagavi, India

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.

Leave a Reply

Your email address will not be published. Required fields are marked *