key: cord-0047498-0h8lzv2f
authors: Mousavirad, Seyed Jalaleddin; Schaefer, Gerald; Fang, Hui; Liu, Xiyao; Korovin, Iakov
title: Colour Quantisation by Human Mental Search
date: 2020-06-22
journal: Advances in Swarm Intelligence
DOI: 10.1007/978-3-030-53956-6_12
sha: d126e3b2ac0ed34f3dd9a38dfb028cc06e04d806
doc_id: 47498
cord_uid: 0h8lzv2f

Colour quantisation is a common image processing technique to reduce the number of distinct colours in an image which are then represented by a colour palette. The selection of appropriate entries in this palette is a challenging issue while the quality of the quantised image is directly related to the colour palette. In this paper, we propose a novel colour quantisation algorithm based on the human mental search (HMS) algorithm. HMS is a recent population-based metaheuristic algorithm with three main operators: mental search to explore the vicinity of candidate solutions based on Levy flight, grouping to determine a promising region based on a clustering algorithm, and movement towards the best strategy. The performance of our proposed algorithm is evaluated on a set of benchmark images and in comparison to four conventional algorithms and seven soft computing-based colour quantisation algorithms. The obtained experimental results convincingly show that our proposed algorithm is capable of outperforming these approaches.

Colour images usually use 24 bits per pixel, which results in 2 24 distinct colours. However, humans can recognise only up to a thousand different colours. Therefore, reducing the number of colours may not affect perception while leading to reduced complexity and resources. Colour quantisation is a process to reduce the number of distinct colours in an image and represent image colours by a colour palette comprising a small number of colours (often between 8 and 256) [1] . Colour quantisation is essential in some applications such as video conferencing and transmission through limited bandwidth channels [13, 14] , while also providing a compression method that simplifies the feature space [5] .

The primary goal of colour quantisation algorithms is to yield a good palette.

If the values of the palette are not properly selected, the resulting image will show more discrepancies compared to the original image and thus lower image quality. Therefore, choosing appropriate entries in the palette is important, it is however also known as an NP-hard problem, making colour quantisation a challenging task.

In the literature, various colour quantisation algorithms have been proposed. A relatively simple method is the popularity algorithm [4] which chooses the colours that are represented most often in the image. In median cut quantisation [4] , the colour space is divided into sub-spaces in an iterative process, while in [3] , the colour space is represented as an octree whose sub-branches combine to form the pallete. Self-organising Kohonen neural networks have also been proposed [2] , as have a number of soft computing methods [8] such as simulated annealing [10] , fuzzy c-means [11] , rough c-means [12] , and fuzzy-rough c-means [9] .

Human mental search (HMS) [7] is a recent population-based metaheuristic algorithm inspired by the exploration strategies in the bid space of online auctions. HMS has three main operators: (1) mental search, which explores the vicinity of each solution based on Levy flight, (2) grouping, which partitions the search space using a clustering algorithm, and (3) moving bids towards promising regions.

In this paper, we propose a novel method for colour quantisation based on the HMS algorithm. We formulate the colour quantisation problem as an optimisation problem and employ HMS to identify an optimal colour palette. Experimental results obtained on a benchmark image set show that our proposed approach is capable of outperforming both conventional and other soft computing-based colour quantisation methods.

The remainder of this paper is organised as follows. Section 2 introduces the HMS algorithm, while our proposed algorithm is presented in Sect. 3. Section 4 gives experimental results and discusses the performance of the proposed algorithm against other approaches. Finally, Sect. 5 concludes the paper.

Human mental search (HMS) is a recent population-based metaheuristic algorithm inspired by exploring strategies in the bid space of online auctions. Each candidate solution in HMS is called a bid, and the algorithm is based on three main operators, mental search, grouping, and movement towards a promising region. In the following, these operators are described in more detail, while Algorithm 1 lists the pseudo-code of the HMS algorithm.

Mental search explores the vicinity of a candidate solution using Levy flight. Levy flight is a type of random walk that generates random movements based Calculate the objective function values of bids 9:

x * = find the best bid in the initial population 10:

for i from 1 to Npop do 11: βi = generate random number between L and U 12: end for 13:

for iter from 1 to MaxIter do 14:

// Mental Search 15:

for i from 1 to Npop do 16: qi = generate random integer number between M l and M h 17: end for 18:

for i from 1 to Npop do 19:

for j from 1 to qi do 20:

end for 23: t = find NS with the lowest objective function value 24:

if cost(t) < cost(x i ) then 25:

x i = t 26:

end if 27: end for 28: // Clustering 29:

Cluster Npop bids into K clusters 30:

Calculate the mean objective function value of each cluster 31:

Select cluster with lowest mean objective function value as the winner cluster 32: winner = select the best bid in the winner cluster 33:

// Move bids towards best strategy 34:

for i from 1 to Npop do 35:

for n from 1 to Nvar do 36:

end for 38: end for 39:

for i from 1 to Npop do 40: βi = generate random number between L and U 41: end for 42:

x + = find best bid in current bids 43:

if cost(x + ) < cost(x * ) then 44:

x * = x + 45: end if 46: end for 47: end procedure on a Levy distribution. In Levy flight, there are some small movements and then a long jump which increases both exploration (due to the long jumps) and exploitation (due to the small movements) simultaneously. Mental search generates some new solutions according to

where x * is the best position found so far, u and v are two random numbers with normal distributions, MaxIter is the maximum number of iterations, iter shows the current iteration, and β is a random number, while ⊕ denotes element-wise multiplication. (2 − iter(2/M axIter)) is a descending factor, starting at a point near 2 and ending towards 0, and thus considers a larger vicinity of a solution at the beginning (exploration) and smaller vicinities at the end of the algorithm (exploitation).

In this step, the solutions are grouped using a clustering algorithm. For this, we use the k-means algorithm to cluster the population. Then, the mean cost of each cluster is calculated and the cluster with the lowest mean cost value selected as a promising region.

In this step, candidate solutions move towards the best solution in the promising region, governed by

where x t+1 n is the n-th bid element at iteration t+1, winner t n is the n-th element of the best bid in the winner group, t is the current iteration, C is a constant, and r is in is a random number drawn from a uniform distribution between 0 and 1.

In this paper, we apply an improved HMS algorithm to the colour quantisation problem. For this, two issues need to be determined: (1) representation and (2) objective function.

In our approach, the representation is an array which encodes the colours of the colour palette. The length of the array is to N var = 3k where k is the number of colours in the palette and we store the RGB values of each colour. The objective function is chosen to minimise the mean squared error (MSE) between the original and quanitsed image

where m and n are the dimensions of the image, and R(i, j), G(i, j), and B(i, j) are the red, green, and blue pixel values at location (i, j) while the subscripts o and q denote the original and quantised image. In our approach, we improve the human mental search based on the personal experience of each candidate solution. To this end, the update equation, Eq. (3), is changed to

where pbest is the position of the best solution found so far by the n-th candidate, and C 1 and C 2 are constants.

To verify the performance of the proposed method, we have used six commonly employed benchmark images shown in Fig. 1 , namely Lenna, Peppers, Mandrill, Sailboat, Airplane, and Pool. In all experiments, the number of colours in the palette is set to 16 [8] and we set M l = 2, M h = 10, K (the number of clusters during grouping) to 5, L = 0.3, U = 1.99, and c 1 = c 2 = 1.5. HMS is run with a population size of 50 for 500 iterations. We compare our proposed algorithm to four conventional quantisation algorithms namely popularity algorithm [4] , median cut [4] , octree quantisation [3] , and Neuquant [2] , and seven soft computing-based approaches including SWASA [10] , fuzzy c-means (FCM) [11] , random sampling FCM (RSFCM) [11] , Enhanced FCM (EnFCM) [11] , anisotropic mean shift based FCM (AMS-FCM) [11] , rough c-means (RCM) [12] , and fuzzy-rough c-means (FRCM) [9] .

As evaluation measure we use the peak signal-to-noise-ratio (PSNR), which is the most commonly employed metric to evaluate colour quantisation algorithms and is defined as P SNR(I o , I q ) = 10 log 10

where MSE is the mean squared error calculated as in Eq. (4). Table 1 compares the results obtained for our proposed algorithm against the other evaluated techniques. It can be observed that the octree and Neuquant algorithms outperform the popularity and median cut approaches. Furthermore, it is clear that the soft computing-based colour quantisation algorithms outperform octree and Neuquant confirming that methods based on soft computing techniques are effective tools for colour quantisation [8] . Also apparent from Table 1 is that our proposed HMS colour quantisation algorithm yields excellent results and is convincingly shown to outperform all other algorithms giving the best image quality for all images except Pool, for which FRCM and EnFCM perform slightly better.

We also perform a ranking analysis where, as shown in Table 2 , we rank all algorithms on each image based on the PSNR results. We then average the ranks for each algorithm to identify an overall ranking. From Table 2 , it is clear not only that our proposed algorithm ranks first but also that it yields a significantly lower average rank of 1.33 compared to all other algorithms with FRCM second with an average rank of 2.92. FCM ranks third while, as expected, the conventional quantisation algorithms are the lowest ranked techniques.

In Figs. 2, 3 and 4, we show, as examples, the quantisation results from several algorithms on three of the images, namely Sailboat, Pool and Airplane. For each quantised image, we also show an error image [15] obtained by calculating the difference between the original image and its quantised counterpart 1 . The shown examples further illustrate the excellent colour quantisation results we obtain using our proposed technique and that it yields improved image quality to the other techniques. 

In this paper, we have proposed a novel quantisation algorithm based on human mental search (HMS), a population-based metaheuristic that mimics exploration strategies in the bid space of online auctions to solve optimisation problems. In our approach, HMS is employed to create a colour palette with the aim of obtaining the highest image quality for the colour quantisation problem. Experimental results on commonly employed test images verify the effectiveness of the proposed algorithm and show our approach to outperform both conventional and soft computing-based colour quantisation algorithms. In future work, we plan to integrate the proposed algorithm with k-means for further improvement, while we also investigate its use in video analysis tasks [6] .

Comparison and optimization of methods of color image quantization

Kohonen neural networks for optimal colour quantization

A simple method for color quantization: octree quantization

Color image quantization for frame buffer display

A hybrid color image quantization algorithm based on k-means and harmony search algorithms

Method of obtaining unnoise image on the basis of video sequence handling

Human mental search: a new population-based metaheuristic optimization algorithm

Soft computing based colour quantisation. EURASIP J. Image Video Process

Rough c-means and fuzzy rough c-means for colour quantisation

A hybrid colour quantisation algorithm incorporating a human visual perception model

Fuzzy clustering for colour reduction in images

Rough colour quantisation

A comparison of clustering algorithms applied to color image quantization

A genetic c-means clustering algorithm applied to color image quantization

Color image fidelity metrics evaluated using image distortion maps

Acknowledgements. This paper is published due to the financial support of the Federal Target Programme of the Ministry of Science and Higher Education of Russian Federation, project unique identifier RFMEFI60819X0281.