вход по аккаунту


978-3-319-68195-5 18

код для вставкиСкачать
Effective Colour Reduction Using Grey
Wolf Optimisation
Gerald Schaefer1(B) , Punjal Agarwal2 , and M. Emre Celebi3
Department of Computer Science, Loughborough University, Loughborough, UK
The LNM Institute of Information Technology, Jaipur, India
Department of Computer Science, University of Central Arkansas, Conway, USA
Abstract. Colour reduction algorithms allow displaying or processing
true colour images using a limited palette of distinct colours. Clearly, the
colours that make up the palette are important as they determine the
quality of the resulting image. Colour quantisation can also be seen as an
optimisation problem where the task is to identify those colours that will
lead to the best possible resulting image quality. In this paper, we utilise
a recent meta-heuristic optimisation algorithm, Grey Wolf Optimisation,
for colour reduction of images. Experimental results on a benchmark set
of images confirm that our approach performs significantly better than
other, purpose built colour quantisation algorithms.
Colour reduction (or colour quantisation) is a common image processing technique that allows the representation of true colour images using only a small
number of colours. True colour images typically use 24 bits per pixel resulting
overall in 224 , i.e. more than 16 million different colours. Colour reduction uses
a colour palette that contains only a small number of distinct colours (usually
between 8 and 256) and pixel data are then stored as indices to this palette.
Clearly, the choice of the colours that make up the palette is of crucial importance for the quality of the quantised image. However, the selection of the optimal
colour palette is known to be an np-hard problem [1]. In the image processing
literature many different algorithms have been introduced that aim to find a
palette that allows for good image quality of the quantised image [1–3].
Colour reduction can also be seen as an optimisation problem where the task
is to identify those colours that best represent the image and lead to the best
possible resulting image quality. Soft computing techniques such as algorithms
based on evolutionary or optimisation principles have also been employed in this
context to extract a suitable palette [4–6]. In this paper, we utilise a recent metaheuristic optimisation algorithm, Grey Wolf Optimisation [7], which is based on
leadership and hunting behaviour of grey wolf packs, for colour reduction of
images. Our experimental results on a benchmark set of images show that this
c Springer International Publishing AG 2018
J.M.R.S. Tavares and R.M. Natal Jorge (eds.), VipIMAGE 2017,
Lecture Notes in Computational Vision and Biomechanics 27,
DOI 10.1007/978-3-319-68195-5 18
Effective Colour Reduction Using Grey Wolf Optimisation
results in a very competitive colour reduction algorithm that performs significantly better than other, purpose built colour quantisation techniques.
Grey Wolf Optimisation (GWO)
Grey Wolf Optimisation (GWO) is an optimisation techniques developed by Mirjalili in [7]. Here, grey wolves are considered as apex predators who have a strict
social dominant hierarchy. Four types of grey wolves – alpha, beta, delta, and
omega – are employed to simulate this leadership hierarchy. Alphas are leaders,
and are mostly responsible for making decisions about hunting, identifying the
sleeping place, time to wake, etc. Betas represent the second level in the hierarchy. They are subordinate wolves that help the alpha in decision-making or
other pack activities. A beta wolf is probably the best candidate to make an
alpha in case one of the alphas dies or becomes very old. Omegas are the lowest
ranking wolves, and thus have to submit to all other dominant wolves. Deltas
comprise the fourth group.
Let α be the best solution, β the second best solution, δ the third solution
and ω the remainder of all candidate solutions. In GWO, hunting is guided by
α, β and δ, while ω solutions follow these three wolves.
During the hunt, grey wolves encircle the prey. This encircling behaviour is
modelled as
X(t + 1) = Xp (t) − A · D, with
D = |C · Xp (t) − A · X(t)|,
where t is the iteration number, Xp is the prey position and X indicates the
position of the grey wolf. A and C are coefficient vectors and calculated as
A = 2a · r1 − a, and C = 2 · r2 ,
where the components of a are linearly decreased from 2 to 0 over time, and r1 ,
r2 are random vectors in [0, 1].
α is usually guiding the hunt, while β and δ might participate in hunting
occasionally. In order to simulate the hunting behaviour of grey wolves, α (the
best candidate solution), β and δ are assumed to have better knowledge about
the potential location of prey. The first three best solutions obtained so far and
ω (the other search agents) update their positions according to the position of
the best search agents according to
Dα = |C1 .Xα − X|,
Dβ = |C2 .Xβ − X|,
X1 = Xα − A1 · (Dα ), X2 = Xβ − A2 · (Dβ ),
Dδ = |C3 .Xδ − X|
X3 = Xδ − A3 · (Dδ ), (4)
G. Schaefer et al.
X(t + 1) =
X1 + X2 + X3
A grey wolf ends a hunt by attacking the prey. When |A| < 1, the wolves attack
towards the prey, which represents an exploitation process. In contrast, in an
exploration process, α, β and δ diverge from each other to search for prey and
converge to attack it. This is modelled by using A with random values greater
than 1 or less than -1, since with |A| > 1 the wolves move from the current prey
to look for a fitter solution.
Colour Reduction Using GWO
The colour reduction problem can be regarded as an optimisation problem whose
goal it is to identify the optimal colours of the palette so that the resulting image
quality is the best achievable. Image quality is commonly judged based on the
mean squared error between the original image Io and the quantised image Iq
MSE(Io , Iq ) =
1 [(Ro (i, j) − Rq (i, j))2
3nm i=1 j=1
+(Go (i, j) − Gq (i, j))2 + (Bo (i, j) − Bq (i, j))2 ]
where R(i, j), G(i, j), and B(i, j) are the red, green, and blue pixel values at
location (i, j), and n and m are the dimensions of the images. In order to avoid
the creation of unused palette entries, the objective function that we are trying to
minimise using Grey Wolf Optimisation is expanded by a penalty term p(P, Iq )
1 if li = 0
p(P, I) =
δai , ai =
0 otherwise
where Ii is the number of pixels Ij represented by colour Pi of the palette.
Experimental Results
In our experiments, we used six benchmark images that are commonly used in
the colour quantisation literature (Lenna, Peppers, Mandrill, Sailboat, Airplane,
and Pool - see Fig. 1) and applied our proposed GWO-based colour reduction
algorithm with a palette of 16 colours.
To put the results obtained into context, we have also implemented four popular colour quantisation algorithms to generate corresponding quantised images
with a palette size of 16, namely
Effective Colour Reduction Using Grey Wolf Optimisation
Fig. 1. The six test images used in the experiments: (Lenna, Peppers, Mandrill, Sailboat, Pool, and Airplane. (from left to right, top to bottom).
• Popularity algorithm [1]: First a uniform quantisation step is applied where
each colour channel is reduced to a bit depth of 5 bits. Then, simply those n
colours that are represented most often form the colour palette.
• Median cut quantisation [1]: This algorithm starts by computing the box
that encompasses all colours present in the image. The box is then split
(orthogonal to the colour axis) at the median value into two sub-cubes. The
larger remaining sub-cube is then again divided at its median point and this
process is repeated until n colour boxes have been found.
• Octree quantisation [2]: The colour space is represented as an octree where
the root node corresponds to the whole colour space, the nodes at the next
level the eight sub-cubes that are obtained by dividing each colour axis into
two equal halves, and so on. In a first pass the sub-tree that represents the
colours present in the image is built and in a second pass, starting at the
bottom of the tree, nodes are successively merged until a tree of n colours is
• Neuquant [3]: A one-dimensional self-organising Kohonen neural network is
trained to generate the colour map. The Kohonen network defines a mapping
from the colour values in the image to an index representing the palette
entries. The weights of the network are updated based on the image data to
ensure an optimal palette with good image quality.
G. Schaefer et al.
In addition, we compare our proposed algorithm to another work that is
also based on optimisation, namely [5] where an improved variant of simulated
annealing, step width adapting simulated annealing (SWASA) [8], is employed
to derive a colour palette. For all algorithms, pixels in the quantised images
were assigned to their nearest neighbours in the colour palette to provide the
best possible image quality.
The obtained results are listed in Table 1, expressed in terms of peak signal
to noise ratio (PSNR) defined as
PSNR(Io , Iq ) = 10 log10
M SE(Io , Iq )
with MSE (the mean-squared error) calculated as in Eq. (6).
Table 1. Quantisation results, given in terms of PSNR [dB].
Lenna Peppers Mandrill Sailboat Pool
Airplane average
Popularity algorithm [1] 22.24
19.87 15.91
Median cut [1]
24.57 24.32
Octree [2]
29.39 28.77
Neuquant [3]
27.08 28.24
29.84 29.43
proposed GWO
30.11 30.69
From Table 1 we can see that of the dedicated colour quantisation algorithms
Octree and Neuquant clearly outperform the Popularity and Median Cut methods. In turn, the simulated annealing based approach outperforms both Octree
and Neuquant and shows that optimisation based approaches to colour reduction
are effective. Nevertheless, it is obvious that our GWO-based approach achieves
significantly better image quality than any of the other algorithms, including
Octree, Neuquant and also SWASA. In fact, on average, our colour quantisation
approach provides an increase in PSNR of about 1.5 dB compared to conventional
approach and more than 1 dB compared to SWASA, which is quite remarkable.
Examples of this performance are given in Figs. 2, 3 and 4 which show the
original image together with the images colour reduced by all algorithms. Error
images (or image distortion maps) are commonly employed for judging the difference between images or the performance of competing algorithms [9]. For
each quantised image, we therefore also provide an error image that represents
the difference between the original and the palettised image (the squared error
at each pixel location is calculated, the resulting image then inverted and a
gamma function applied to increase the contrast). It can be seen that popularity
Effective Colour Reduction Using Grey Wolf Optimisation
Fig. 2. Lenna image (top-left) and colour reduced images using (from left to right, top
to bottom): Popularity, Median cut, Octree, Neuquant, SWASA and GWO algorithms.
Also shown are error images of the quantised images.
G. Schaefer et al.
Fig. 3. Pool image (top-left) and colour reduced images, laid out in the same fashion
as Fig. 2
based colour quantisation does not work very well. Median cut performs better
but not as well as Octree and Neuquant which provide much improved image
quality. While SWASA provides a further improvement, our proposed GWO
colour reduction algorithm outperforms all other approaches and clearly produces the images with the highest image fidelity.
Effective Colour Reduction Using Grey Wolf Optimisation
Fig. 4. Airplane image (top-left) and colour reduced images, laid out in the same
fashion as Fig. 2
G. Schaefer et al.
In this paper, we have proposed a novel approach to colour reduction. In particular, we have presented a colour quantisation algorithm based on Grey Wolf
Optimisation (GWO) where GWO is employed to derive a colour palette that
will lead to the lowest distortions and thus the highest image quality. Experimental results obtained on a set of common test images have demonstrated
that this approach can not only be effectively employed but clearly outperforms
dedicated colour quantisation algorithms.
1. Heckbert, P.S.: Color image quantization for frame buffer display. ACM Comput.
Graph. (ACM SIGGRAPH 1982 Proc.) 16(3), 297–307 (1982)
2. Gervautz, M., Purgathofer, W.: A simple method for color quantization: octree
quantization. In: Glassner, A.S. (ed.) Graphics Gems, pp. 287–293. Academic Press,
San Diego (1990)
3. Dekker, A.H.: Kohonen neural networks for optimal colour quantization. Netw.
Comput. Neural Syst. 5, 351–367 (1994)
4. Scheunders, P.: A genetic c-means clustering algorithm applied to color image quantization. Pattern Recogn. 30(6), 859–866 (1997)
5. Nolle, L., Schaefer, G.: Color map design through optimization. Eng. Optim. 39(3),
327–343 (2007)
6. Schaefer, G., Nolle, L.: Optimal image colour extraction by differential evolution.
Int. J. BioInspired Comput. 2(3/4), 251–257 (2010)
7. Mirjalili, S., Mirjalili, S.M., Lewis, A.: Grey wolf optimizer. Adv. Eng. Softw. 69,
46–61 (2014)
8. Nolle, L.: On the effect of step width selection schemes on the performance of stochastic local search strategies. In: 18th European Simulation Multi-Conference, pp.
149–153 (2004)
9. Zhang, X.M., Wandell, B.A.: Color image fidelity metrics evaluated using image
distortion maps. Signal Process. 70(3), 201–214 (1998)
Без категории
Размер файла
6 511 Кб
978, 68195, 319
Пожаловаться на содержимое документа