 Open Access
 Total Downloads : 22
 Authors : Shet Reshma Prakash, Vrinda Shetty
 Paper ID : IJERTCONV3IS14016
 Volume & Issue : NCACCT – 2015 (Volume 3 – Issue 14)
 Published (First Online): 24042018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Lifting Based Image Compression using Grey Wolf Optimizer Algorithm
Shet Reshma Prakash
Student (MTech), 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 biorthogonal 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.

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 metaheuristic 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).

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
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 metaheuristic 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.


LIFTING SCHEME
Lifting Scheme when applied on image produces the approximation coefficient and detail coefficient. 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 nonlinear 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.

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 subbands 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.

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

The selected image is converted to gray scale and resized.

User enters the value for compression ratio.

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

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

Using modified set of coefficient and Inverse Lifing scheme the image is regenerated. This regenerated image is optimized image.

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

Finally the image is reconstructed using SPIHT decoding algorithm.


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.

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

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 coefficient 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)

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

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 pseudocode 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


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.

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

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.


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.

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.

REFERENCES

ShuChuan Chu, HsiangCheh 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. Â© SpringerVerlagBerlin Heidelberg 2011.

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 22502459, Volume 2, Issue 1, January 2012),Website: www.ijetae.com .

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. 17.

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.

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..

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