Lifting Based Image Compression using Grey Wolf Optimizer Algorithm

Lifting Based Image Compression using Grey Wolf Optimizer Algorithm

Shet Reshma Prakash

Student (M-Tech), Department of CSE Sai Vidya Institute of Technology Bangalore, India

Vrinda Shetty

Asst. Professor & HOD, Department of ISE Sai Vidya Institute of Technology Bangalore, India

Abstract Image compression is the most significant requirement due to constraints related to storage space and transmission bandwidth. This paper proposes a new technique for Lifting based image compression using Grey Wolf Optimizer Algorithm (GWO). The Lifting Scheme is a new method for faster computation of bi-orthogonal wavelets. The GWO is Swarm Intelligence based optimization algorithm which simulates the leadership hierarchy and hunting behavior of grey wolves. The performance is evaluated on the basis of Peak Signal to Noise Ratio (PSNR) and encoding and decoding is performed using Set Partitioning in Hierarchical Trees (SPIHT) technique. The best compressed image is the one which has higher PSNR value.

Keywords Image compression, Grey Wolf Optimizer Algorithm, Lifting Scheme.

1. INTRODUCTION

   Data compression is beneficial because it reduces the consumption of expensive resources like bandwidth and hard disk space. Image Compression is a technique where the size of the image is reduced by removing the redundant and irrelevant information and by encoding it using fewer bits of information. There are two types of image compression namely lossy and lossless. In lossy technique it is possible to reconstruct the approximation of the original image and compression ratio is high. In lossless technique the original image can be exactly reconstructed but the compression ratio is low. There are various techniques for image compression. JPEG is the most commonly used lossy image compression technique based on Discrete Cosine Transform (DCT). DCT represents the signal in frequency domain. DCT represents the signal as the sum of sinusoids of varying magnitude and frequencies. JPEG 2000 standard uses Discrete Wavelet Transform (DWT) which decomposes the image into four frequency sub bands i.e. LL, LH, HL and HH. This paper proposes a technique wherein image is compressed using evolutionary computation based meta-heuristic optimization algorithm i.e. Grey Wolf Optimizer (GWO). Swarm intelligence based optimization algorithm is the major part in evolutionary computation to perform continuous optimization of selected population and achieve best solution. Some of the optimization algorithms which are already used for image compression are Artificial Bee Colony (ABC), Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO).

2. LITERATURE SURVEY

   Shu Chuan et al. [1] have reviewed Swarm Intelligence based algorithms like Particle Swarm Optimization (PSO), Ant Colony System (ACS), Stochastic Diffusion Search (SDS), Bacteria Foraging (BF), the Artificial Bee Colony (ABC) for solving certain optimization problems. Harsha D Zope et al.

   [2] have done comparative study of various image compression techniques like Discrete Cosine Transform (DCT), Discrete Wavelet Transform (DWT) and Wavelet Packet Decomposition (WPD). Rajesh K Yadav et al. [3] have done comparison based on two thresholding techniques

   1. local thresholding and global thresholding. M. Mohamed Ismail and Dr. K. Baskaran [4] have worked on Adaptive Lifting Scheme based image compression using Artificial Bee Colony algorithm. The adaptive Lifting Scheme is a modification of the classical lifting where update operation is performed before the prediction according to its lifting structure. Artificial Bee Colony algorithm is optimization technique which mimics the foraging behavior of honey bees. Seyedali Mirjalili et al. [5] have proposed a new population based meta-heuristic optimization technique called Grey Wolf Optimizer (GWO) inspired by grey wolves (Canis lupus). M. Santhosh et al. [6] have decomposed the image using Lifting Scheme along with SPIHT algorithm.

3. LIFTING SCHEME

   Lifting Scheme when applied on image produces the approximation co-efficient and detail co-efficient. One major benefit of using the lifting scheme is that there is no need of temporary arrays for storing the coefficients and it is reversible. Also it does not require filters as in DWT. Lifting scheme constitutes three basic operations namely Split, Predict and Update.

   Split

   Divide the original data into two disjoint subsets. The original data set x[n] is partitioned into xe[n] (even indexed points) and xo[n] (odd indexed points).

   xe[n]=x[2n] , xo[n] = x[2n + 1]

   Predict

   Generate the wavelet coefficients d[n] as the error in predicting xo[n] from xe[n] using prediction operator P

   d[n] = xo[n]-P(xe[n] ) (1)

   Update

   Combine xe[n] and d[n] to obtain scaling coefficients c[n] that represent a coarse approximation to the original signal x[n]. This is done by applying update operator U to the wavelet coefficients and adding to xe[n].

   c[n] = xe[n]+U(d[n]) (2)

   The Forward and Inverse Lifting Scheme is shown in Figure 1 and Figure 2.

   Fig. 1. Forward Lifting scheme

   Fig. 2. Inverse Lifting Scheme

   The three steps of lifting scheme are easily invertible even if the P and U values are non-linear or space variant. It is possible to reconstruct the original signal if same values of P and U are used for Forward and Inverse Lifting Scheme.

4. PROPOSED WORK

   The proposed work is to compress the image using new meta- heuristic called GWO using lifting Scheme. The Grey Wolf Optimizer [5] is proposed by Seyedali Mirjalili et al. [5] in 2014. The GWO algorithm mimics the hunting behavior of grey wolves and there are four types of grey wolves namely alpha, beta, delta and omega. Alpha is the most dominant wolf and is the leader for the whole pack. All other wolves

   follow the order of alpha wolf. Beta wolf is the subordinate for alpha wolf and helps him for decision making. Delta wolf also follows the order of alpha wolf and beta wolf. The Omega wolf is like scapegoat who is last person to eat in the pack.

   The block diagram for the proposed work is shown in Figure 3.The input image supplied by the user is sent for preprocessing. In preprocessing stage the image is converted to grey scale and it is resized .Then Lifting scheme is used for the decomposition of the image to the approximation coefficients (scaling coefficients) and the details coefficients (wavelet coefficients). The approximation coefficients are contained in the LL band. And detail coefficients are contained in LH, HL and HH band. The optimization is carried out in all four sub-bands using Grey Wolf Optimizer Algorithm in an iterative manner.

   Fig. 3. Block diagram for the proposed work

   The proposed system follows the procedure given below for image compression.

   1. The input image is selected by the user. The image can have any format or size.

   2. The selected image is converted to gray scale and resized.

   3. User enters the value for compression ratio.

   4. Lifting scheme decomposes the image which produces four frequency sub-bands namely LL, LH, HL and HH band. Here the proposed system uses Lazy wavelet transform to produce a set of approximation co-efficient matrix CA and detail co- efficient matrix CH, CV and CD.

   5. Grey Wolf Optimization algorithm is applied for all sub-bands which generate the set of modified approximation co-efficient matrix CA and detail co- efficient matrix CH, CV and CD.

   6. Using modified set of co-efficient and Inverse Lifing scheme the image is regenerated. This regenerated image is optimized image.

   7. The optimized image is encoded using Set Partitioning in Hierarchical Trees (SPIHT) algorithm to generate the compressed image.

   8. Finally the image is reconstructed using SPIHT decoding algorithm.

5. GREY WOLF OPTIMIZER ALGORITHM

   This algorithm mimics the social behavior and group hunting mechanism of the grey wolves. Alpha wolf is the most dominant wolf. During the optimization phase the best fittest solution is considered as alpha (). Also the second and third best solutions are considered as beta () and delta () respectively. The rest of the candidate solutions are assumed to be omega (). The hunting is carried out through knowledge among , , and wolves. The wolves follow these three wolves.

   There are three phases in hunting.

   1. Encircling the prey: During hunt the grey wolves encircle the prey and update their position according to the position of prey.

   2. Hunting: The hunt is managed under the guidance of alpha. The alpha (best search agent), beta and delta have good knowledge about the location of the prey. During optimization (hunting) the first three best solutions are saved and other search agents (including the omegas) update their position according to the position of best search agent. The following formulas are used in this context where t indicates the current iteration. Also A and C are the co-efficient vectors and X indicates the position of grey Wolf.

      D = C1.X X (3)

      D = C2.X X (4)

      D = C3.X X (5)

      X1 = X – A1. D (6)

      X2 = X – A2. D (7)

      X3 = X – A3. D (8) X(t+1) = (X1 + X2 + X3) / 3 (9)

   3. Attacking prey (exploitation): The grey wolves finish the hunt and attack the prey when it stops moving.

   4. Searching for prey (exploration): The grey wolves search for the prey according to the position of alpha, beta and delta. They diverge from each other to search for prey and converge to attack the prey

   Thus in each iteration the position of the prey is estimated according to the position of alpha, beta and delta wolves.

   Each candidate solution i.e. omega updates its distance from the prey. The three operators required to perform the optimization are coefficient vectors A, C and a. The C vector represents the effect of obstacles while approaching the prey. The A has a random value in between the range of -2a to + 2a. Also the value of a is decreased from 2 to 0 over the range of iterations and r1, r2 are random vectors in range of 0 to 1. The vectors A and C are calculated by using following formulas

   A= 2a.r1 a (10)

   C= 2.r2 (11)

   Thus when the value of |A|<1 the grey wolves attack the prey by converging towards each other and when |A|>1 they diverge from each other. As the value of A goes on decreasing half of the iterations are dedicated for exploration(|A| > 1) and the other half are dedicated for exploitation(|A| < 1).The GWO has only two main parameters to be adjusted (a and C).The pseudo-code for Grey Wolf Optimizer Algorithm is given below.

   Grey wolf population Xi (i = 1,2.n) initialization Initialize the values for a, A and C

   Calculation of fitness value for all search agents X = the best search agent

   X = the second best search agent X = the third best search agent

   While (t< Max Number of iterations) For each search agent

   Update the position of the current search agent by (9) End for

   Update a,A and C

   Calculate the fitness of all search agents Update X , X , X

   t= t+ 1 end while return X

6. EXPERIMENT RESULTS

   The proposed work is implemented using Matlab R2010. The experiment was conducted for various standard images having different sizes and format. Figure. 4. shows the original image and the reconstructed image obtained after decompression.

   1. Lena Image b) Reconstructed Lena Image

      TABLE I Comparative results for various images

      Comp- ression Ratio	Table shows the PSNR Values for different images against the compression ratio
      	Lena Image	Pepper Image	Balls Image	House Image	Mandrill Image
      30	41.89	41.06	41.52	41.07	39.21
      40	38.32	37.34	34.91	34.88	35.64
      50	36.66	37.22	34.91	34.84	35.49
      60	31.31	33.00	36.60	34.02	31.52
      70	31.31	33.00	36.60	34.02	31.52

      Comp- ression Ratio	Table shows the PSNR Values for different images against the compression ratio
      	Lena Image	Pepper Image	Balls Image	House Image	Mandrill Image
      30	41.89	41.06	41.52	41.07	39.21
      40	38.32	37.34	34.91	34.88	35.64
      50	36.66	37.22	34.91	34.84	35.49
      60	31.31	33.00	36.60	34.02	31.52
      70	31.31	33.00	36.60	34.02	31.52

   2. Pepper image b) Reconstructed Pepper image

   LENA IMAGE

   LENA IMAGE

   50

   40

   30

   20

   10

   0

   50

   40

   30

   20

   10

   0

   PEPPER IMAGE

   BALLS IMAGE

   CR CR CR CR CR 30 40 50 60 70

   COMPRESSION RATIO

   PEPPER IMAGE

   BALLS IMAGE

   CR CR CR CR CR 30 40 50 60 70

   COMPRESSION RATIO

   HOUSE IMAGE

   HOUSE IMAGE

   PSNR

   PSNR

   a)Balls image b)Reconstructed Balls image

   MANDRILL

   IMAGE

   MANDRILL

   IMAGE

   a)House image b) Reconstructed House image

   a)Mandrill image b)Reconstructed Mandrill image

   Fig. 4. a) Original Image b) Reconstructed Image

   The performance is evaluated for Lena image, Pepper image, Balls image, House image and Mandrill image on the basis of the metric PSNR (Peak Signal to Noise Ratio). The results obtained are tabulated as shown in Table I.

   Fig. 5. Graph showing PSNR values for different images.

7. CONCLUSION

   The Meta heuristic Grey Wolf Optimizer is able to produce better results compared to various optimization algorithms. Based on the results obtained it is concluded that the proposed system gives high value of PSNR for Lena Image compared to other images listed in Table I. The proposed system gives best compressed image without sacrificing its original quality and produces high value for PSNR.

8. FUTURE ENHANCEMENT

   The proposed system can be enhanced by replacing the Lifting Scheme with Adaptive Lifting Scheme. Adaptive LS is the modification of original Lifting Structure where the update operation is performed before predict operation.

9. REFERENCES

1. Shu-Chuan Chu, Hsiang-Cheh Huang, John F. Roddick, and Jeng- Shyang Pan – Overview of Algorithms for Swarm Intelligence, International Conference on Computer and Computational Intelligence(ICCCI 2011) , Part I, LNCS 6922, pp. 28 41, 2011. © Springer-VerlagBerlin Heidelberg 2011.

2. Mrs. Harsha D. Zope, Prof. Mrs. Pallavi Y. Patil – Comparative Study of Different Approaches of Image Compression, International Journal of Emerging Technology and Advanced Engineering (ISSN 2250-2459, Volume 2, Issue 1, January 2012),Website: www.ijetae.com .

3. Rajesh K. Yadav, S.P. Gangwar and Harsh V. Singh – Study and analysis of wavelet based image compression techniques, International Journal of Engineering, Science and Technology, Vol. 4, No. 1, 2012, pp. 1-7.

4. M. Mohamed Ismail, Dr. K. Baskaran – Adaptive Lifting Based Image Compression Scheme Using Artificial Bee Colony Algorithm, International Journal of Electronics Communication and Computer Engineering, Volume 4, Issue 1, ISSN (Online): 2249071X, ISSN (Print): 22784209.

5. Seyedali Mirjalili, Seyed Mohammad Mirjalili, Andrew Lewis Grey Wolf Optimizer, Advances in Engineering Software,Vol. 69,2014,pp.4661,Website:www.elsevier.com/locate/advengsoft..

6. M. Santhosh, B. Stephen Charles and Dr. M N Giriprasad- Image Decomposition and Compression by using Lifting Scheme, International Journal of Engineering and Innovative Technology (IJEIT), Volume 3, Issue 2, August 2013