Hybrid firefly-Linde-Buzo-Gray algorithm for Channel-Optimized Vector Quantization codebook design

Abstract

This paper introduces a hybrid method that uses Firefly Algorithm (FA) and Linde-Buzo-Gray (LBG) algorithm to Channel-Optimized Vector Quantization (COVQ) codebook design. Fast nearest neighbor search (NNS) techniques are used with the purpose of execution time savings of the proposed COVQ codebook design. Simulation results concerning image transmission over a binary symmetric channel (BSC) reveal the superiority of the proposed swarm intelligence technique, referred to as FA-COVQ, over conventional COVQ codebook design method. Simulation results also reveal that the adoption of acceleration techniques in FA-COVQ codebook design can lead to execution time savings up to about 97% when compared to the FA-COVQ with brute force approach.

Keywords

Image compression Vector Quantization Channel-Optimized Vector Quantization swarm clustering algorithm Firefly Algorithm

1. Introduction

Communication systems are crucial to the society development due to their importance to a plethora of services and applications, such as medical services, bank operations and data transmission. A huge amount of information as image, voice and video are processed and transmitted every day. In this scenario, compression techniques play an important role, since their purpose is to reduce the number of bits used in signal representation, aiming to decrease memory and/or bandwidth requirements.

Vector Quantization (VQ) [22, 23] can lead to high compression rates and has been widely used in image compression, e.g. [42]. VQ is also used in other applications, such as safety monitoring systems [45], medical image processing [27, 28], information security (such as steganography and digital watermarking) [10, 33] and classification tasks [43]. However, VQ is highly sensitive to channel noise. In the case of VQ for image transmission, channel noise can generate artifacts that visually compromise the quality of the reconstructed images [37]. The Channel-Optimized Vector Quantization (COVQ) is a technique that aims to minimize the effect of the noise in the reconstructed signal. In this context, COVQ uses a codebook which is designed by a clustering algorithm to be more robust to channel errors by using information from both source and transmission channel [18].

Bio-inspired computing is a field where computational algorithms are developed based on natural processes or social behaviors [60]. Applications of bio-inspired algorithms include a wide variety of scenarios, such as image processing using machine learning [2], finite element model updatings [9, 52] and forecasting in Civil Engineering [12].

In optimization problems, such as Vector Quantization codebook design, bio-inspired techniques have been used. Examples of applications of bio-inspired algorithms to COVQ include Fuzzy logic [29], GA (Genetic Algorithm) [30] and PSO (Particle Swarm Optimization) [37]. Optimization problems often require non-biased techniques to find a proper solution. Swarm algorithms are a good choice to these cases [56] and have been used in image processing applications [4, 3, 41] and in clustering problems [13, 51, 55].

This paper introduces the application of the Firefly Algorithm (FA), a bio-inspired computing method [21, 58, 59], to design codebooks for image transmission over a noisy channel. The proposed method, called FA-COVQ codebook design, is a hybrid approach that uses FA and LBG (Linde-Buzo-Gray) [39] algorithms and aims to reduce the average distortion between the designed codebook and the training set and therefore improve the quality of reconstructed images when compared to conventional COVQ codebook design.

Previous published works regarding the combination of swarm techniques with the LBG algorithm use the methods separately, in the scenario of conventional VQ (that is, VQ codebook design assuming a noiseless channel), such as the Particle Swarm Optimization (PSO) in 2005 [11] and in 2007 [38], Artificial Bee Colony (ABC) [25], Bacterial Foraging Particle Swarm Optimization (BFPSO) [19], Honey-Bee Mating Optimization (HBMO) [24] in 2011 and Firefly Algorithm (FA) [26] in 2012. In 2013, Ping-Yi et al. [46] developed an enhancement to PSO-LBG modifying the particles initialization method and Tsai et al. [54] presented a method for speeding up Ant Colony Optimization (ACO) to solve the codebook design problem. In 2016, Karri and Jena [32] proposed the BA-LBG where a codebook designed by the LBG algorithm is used as one of the bats of the Bat Algorithm (BA). In the scenario of hybrid optimization by memetic computing [35], spatially distributed memetic algorithms can be applied to vector quantizer design [5].

In the present paper, the proposed method, FA-COVQ, is a hybrid algorithm using FA and COVQ LBG. The purpose is to take advantage of using bio-inspired computation approach to optimization problems by attempting to avoid trapping to local minima. Also, the use of LBG algorithm attempts to satisfy the nearest neighbor condition for partition and centroid condition for codevectors [22].

A variety of swarm intelligence methods should be considered for the application addressed in this work: ant colony optimization (ACO) [14], particle swarm optimization (PSO) [15, 16], bat algorithm (BA) [57], fish school search (FSS) [7] and firefly algorithm (FA) [60]. A discussion concerning the choice of one out of the four aforementioned methods follows:

•
The optimization problem under consideration (i.e., COVQ codebook design) is modeled in the present work in such manner that a swarm clustering method could be applied, jointly with the LBG algorithm. In this sense, the modeling under consideration does not involve the use of graphs – that is the reason why ACO was not chosen for the application addressed in the present work.
•
Although COVQ codebook design can be carried out by PSO, it is important to point out that PSO is a more adequate alternative when precision is an important issue in the optimization problem. This is not the case in the scenario of COVQ codebook design for image transmission – one should observe that the digital transmission under consideration involves grayscale images with 8.0 bits per pixel, a representation with 256 different intensities, which corresponds to 256 integers ranging from 0 to 255. Additionally, PSO has a high exploitation capacity and consequently it may quickly lose diversity in its canonic version.
•
The BA is as meta-heuristic algorithm introduced by Yang in 2010 [57], based on the echolocation feature of micro bats. According to [32], intensification (local search) and diversification (global search) are attained respectively with pulse rate and loudness parameters of BA. In this sense, it is possible that BA requires a high number of iterations for large codebook sizes. Additionally, according to [31], most of the application of BA is in the continuous problem domain, and the algorithm is especially suitable for complex high-dimensional problems where convergence often is a challenge. According to [57], fine adjustment of BA parameters can affect the convergence of the bat algorithm.
•
Among the two remaining candidates, it is worth mentioning the knowledge of success is not based on “marking” the search space (as occurs in ACO) nor is associated to positions of particles in the search space (as occurs in PSO). Precisely, in FA and FSS the aforementioned knowledge occurs in an indirect manner – by means of brightness in FA and by means of a mechanism of increasing/decreasing fish weights and expanding/contracting the school radius in FSS. Particularly, FSS has the capacity of generating diversity in a controlled manner, by using the aforementioned mechanisms, but it is not straightforward that it has a neighborhood attraction effect that is tuned to the problem under study.
•
The brightness attraction mechanism of FA points out this algorithm as a good candidate for COVQ codebook design. The fact that FA has a good neighborhood attraction effect points out this technique as an appropriate one for the optimization problem under consideration, which involves clustering. It is worth mentioning that, according to [31], a positive aspect of FA is its ability to be used with other algorithms (hybrid approaches) to improve outcome, and this algorithm can provide a good balance of exploration and exploitation. This issue has a good consequence in terms of computational complexity.

The inclusion of transmission channel characteristics and bio-inspired techniques increases the computational complexity of the codebook design when compared to conventional VQ codebook design. This paper introduces an alternative to enhance the performance of the FA-COVQ codebook design in terms of execution time. Due to the large amount of arithmetic and logic operations involved in the partitioning step, which is carried out mapping training vectors to their corresponding codevectors, this is the step with highest computational complexity in codebook design. An alternative is presented in the present work to speed up COVQ codebook design. It consists in the accommodation of efficient nearest neighbor search (NNS) techniques in the partitioning step of COVQ codebook design. It is important to emphasize that the original application of those NNS techniques was introduced in the literature in another scenario, more precisely, for speeding up the encoding phase of VQ. Considerations in terms of how some pre-calculus operations must be executed are introduced in the aforementioned techniques so that they work properly in the new scenario of FA-COVQ codebook design.

There is no previous work in the literature concerning the application of the firefly algorithm for Channel-Optimized Vector Quantization (COVQ) codebook design, that is, taking into account that the channel is noisy, and particularly incorporating a simple but effective strategy (i.e., the use of efficient nearest neighbor search in the partitioning step of the algorithm) to speed up the execution time. It is worth mentioning that in the work of Horng [26], the codebook is designed assuming a noiseless channel (conventional vector quantization). It is important no emphasize that COVQ codebook design is a more challenging optimization problem when compared to conventional VQ codebook design. Thus, in the present paper, the application of the firefly algorithm differs from the one addressed by Horng. Additionally, the way firefly is used differs from the approach of Horng – indeed, in the present paper, a hybrid approach is used, as an attempt to take into account the potentials of firefly and Linde-Buzo-Gray (LBG) algorithms. In the present work, the COVQ codebook design is carried out at the light of a “proactive joint work” of algorithms LBG and firefly. In the optimization task, both algorithms are used. In the work of Horng, the only role of the LBG algorithm is to generate an initial codebook for the firefly algorithm, which uses other randomly generated initial codebooks. Since the proposed approach involves the use of a population of fireflies, each one representing a COVQ codebook, nearest neighbor search (NNS) methods are used for alleviating the computational complexity of the method. In this sense, other novelty of the paper is the application of NNS in this scenario. Precisely, NNS methods are used with the purpose of arithmetic and logic operations savings in the clustering phase of the proposed method.

The remaining of this paper is organized as follows: Section 2 presents the principles of Vector Quantization and Section 3 is devoted to conventional COVQ. Section 4 describes the Firefly Algorithm, Section 5 presents the FA-COVQ codebook design and methods to accelerate the codebook design are described in Section 6. Simulation results are presented in Section 7. Conclusions are presented in Section 8.
2. Vector Quantization

Vector Quantization is a signal compression method that allows high compression rates. In image VQ, the original image is split in non-overlapping blocks of pixels. Figure 1 shows an example of a block of $4\times 4$ pixels of Lena image. This block can be seen as a vector of dimension 16.

Figure 1.

Block of 4 $\times$ 4 pixels extracted from Lena image.

Figure 2.

A concise block diagram of an image compression system based on VQ.

In the encoding phase of VQ, each input vector is compared to a list of vectors, called codevectors. The objective of this comparison is to find the nearest neighbor, that is, the codevector closest to the input vector considering some distance measure. The set of codevectors is called codebook. For each input vector, the closest codevector is determined and its index is transmitted over a channel or stored in some storage device. In this way, instead of transmitting or storing a multi-dimensional vector, an index is transmitted or stored.

In the decoding phase, the opposite process is performed. To properly reconstruct a vector, the system must have previously stored a copy of the codebook used at the encoding phase. In a table lookup procedure, each index is used to find the corresponding codevector in the codebook. So, VQ is a lossy compression method. Figure 2 shows the encoding and decoding phases in a concise block diagram.

Mathematically, VQ can be expressed as a mapping $Q$ of an input vector $\vec{X}$ belonging to $K$ -dimensional Euclidean space, $\mathbb{R}^{K}$ , into a finite subset $Y$ of $\mathbb{R}^{K}$ , that is,

$Q:\mathbb{R}^{K}\rightarrow Y,$ (1)

in which the codebook $Y={\vec{Y}_{i};i=1,2,\ldots,N}$ is the set of codevectors, $K$ is the quantizer’s dimension and $N$ is the number of codevectors, that is, the codebook size. The mapping of an input vector $\vec{X}$ in a codevector follows the minimum distance criterion, also known as nearest neighbor rule. In other words, let $\mathrm{d}(\vec{X},\vec{Y}_{i})$ be some distance measure between the input vector $\vec{X}$ and the codevector $\vec{Y}_{i}$ , so

$Q(\vec{X})=\vec{Y}_{i}\ \mathrm{if}\ \mathrm{d}(\vec{X},\vec{Y}_{i})<\mathrm{d% }(\vec{X},\vec{Y}_{j})\ \forall\ j\neq i.$ (2)

The mapping $Q$ introduces a partition of $\mathbb{R}^{K}$ in $N$ cells (called Voronoi regions) $S_{i};i=1,2,\ldots,N$ , such that

$S_{i}=\{\vec{X}|Q(\vec{X})=\vec{Y}_{i}\}.$ (3)

The codevector $\vec{Y}_{i}$ is the corresponding codevector of every input vector $\vec{X}$ belonging to region $S_{i}$ . It is important to mention that

$S_{i}\cap S_{j}=\varnothing\ \forall\ i\neq j.$ (4)

A usual distance measure is the squared Euclidean distance, given by

$\mathrm{d}(\vec{X},\vec{Y}_{i})=\sum_{i=1}^{K}(X_{j}-Y_{ij})^{2},$ (5)

where $X_{j}$ is the $j$ -th component of input vector $\vec{X}$ and $Y_{ij}$ is the $j$ -th component of codevector $\vec{Y}_{i}$ .

2.1 Codebook design problem

The quality of reconstructed images compressed by a VQ-based system is highly dependent on the quality of the codebook. Thus, an important issue of VQ is the codebook design. Given a training set of input vectors and the size $N$ of the codebook, the problem is to find the optimum set of codevectors that minimizes the average distortion between the training set and its reconstructed (quantized) version.

Among several methods, the LBG (Linde-Buzo-Gray) algorithm [39] or K-means algorithm outstands due to its vast use on literature. Given $M$ training vectors, the codebook size $N$ , the dimension $K$ and a distortion threshold $\mu$ , the LBG algorithm can be described as follows:

1.
Initialization – the codevectors in the codebook $Y$ are initialized, e.g., by choosing randomly $N$ training vectors;
2.
Partitioning – the training vectors are mapped in $N$ regions according to Eq. (3);
3.
Average distortion computation – the average distortion of the current iteration is calculated as

$\overline{D}^{t}=\frac{1}{KM}\sum_{i=1}^{M}\mathrm{d}(\vec{X}_{i},Q(\vec{X}_{i% }))$ (6)

where $t$ denotes the current iteration;
4.
Stopping criterion – the stopping criterion is defined by

$\frac{\overline{D}^{t-1}-\overline{D}^{t}}{\overline{D}^{t-1}}\leqslant\mu.$ (7)

If the stopping criterion is satisfied, the algorithm is terminated. Otherwise, it goes to Step 5;
5.
Codebook update – the codevectors (centroids) are updated according to

$\vec{Y}_{i}=\frac{\sum_{S_{i}}\vec{X}}{|S_{i}|},$ (8)

where $\sum_{S_{i}}\vec{X}$ is the sum of all training vectors in region $S_{i}$ and $|S_{i}|$ is the number of training vectors in region $S_{i}$ . Update iteration number: $t\leftarrow t+1$ . Then, the algorithm returns to Step 2.

3. Channel-Optimized Vector Quantization

When a channel error occurs, the codevector index received by the decoder differs from the one that was sent by the encoder. As a consequence, the codevector used to reconstruct the signal will be no more the closest one to the input vector. When the signal is an image, the errors that occur in the transmission channel lead to blocking artifacts that compromise the visual quality of the quantized images [17].

In general, VQ schemes aiming to increase the robustness against the effects of channel noise can be classified in two categories: Robust Vector Quantization (RVQ) [17] and Channel-Optimized Vector Quantization (COVQ) [18]. In RVQ schemes, the codebooks are designed assuming a noiseless channel and then, by means of some Index Assignment algorithm [34, 61], the codebook is organized (e.g., the codevectors are ordered) to be more robust to channel errors. On the other hand, COVQ schemes address the channel noise problem by incorporating previously known information about the channel in the codebook design. So, COVQ-based systems are developed to a specific channel, such as the Binary Symmetric Channel (BSC) or the Binary Erasure Channel (BEC). The present paper considers a COVQ scheme to a BSC, that is a discrete memoryless channel, for a variety of bit error rates.

Let $\mathrm{Pr}(j|i)$ be the probability that, due to channel errors, the index $j$ is received given that the index $i$ was transmitted [18]. In the case of a digital transmission over a BSC, the distance calculation between a training vector $\vec{X}$ and a codevector $\vec{Y}_{i}$ is defined as follows:

$\mathrm{d}_{\mathrm{covq}}(\vec{X},\vec{Y}_{i})=\sum_{j=1}^{N}\mathrm{Pr}(j|i)% \mathrm{d}(\vec{X},\vec{Y}_{j}).$ (9)

In COVQ codebook design, to measure the distance between a training vector $\vec{X}$ and a codevector $\vec{Y}_{i}$ , one takes into account the probability to transmit the index of the codevector $\vec{Y}_{i}$ and receive any of the $N$ codevectors indices. For the purpose of COVQ codebook design, the codevectors are updated, as proposed in [18], according to

$\vec{Y}_{i}=\frac{\sum_{j=1}^{N}\mathrm{Pr}(i|j)\sum_{S_{j}}\vec{X}}{\sum_{j=1% }^{N}\mathrm{Pr}(i|j)|S_{j}|}.$ (10)

The bit error rate of the channel is known before designing the codebook. The index transition-probability matrix is

$\mathrm{P}=\begin{bmatrix}\mathrm{Pr}\left(1|1\right)&\mathrm{Pr}\left(2|1% \right)&\ldots&\mathrm{Pr}\left(N|1\right)\\ \mathrm{Pr}\left(1|2\right)&\mathrm{Pr}\left(2|2\right)&\ldots&\mathrm{Pr}% \left(N|2\right)\\ \vdots&\vdots&&\vdots\\ \mathrm{Pr}\left(1|N\right)&\mathrm{Pr}\left(2|N\right)&\ldots&\mathrm{Pr}% \left(N|N\right)\\ \end{bmatrix}.$ (11)

Since the channel used is the BSC, the bit error rate ( $\varepsilon$ ) of the indices must be considered to compute $\mathrm{Pr}(j|i)$ . Figure 3 shows, briefly, the scheme of a binary symmetric channel.

Figure 3.

Scheme of a binary symmetric channel.

4. Firefly Algorithm

The Firefly Algorithm (FA) was developed by Yang in 2008 at Cambridge University [60]. It uses the concept of bioluminescence effect to find solutions in optimization problems. The FA is based on the following three rules:

•
The fireflies do not have gender, so any firefly can attract or be attracted;
•
The attractiveness is proportional to the emitted brightness, so a less bright firefly moves toward a brighter one. In the particular case of a firefly that does not have any brighter firefly to follow, it moves randomly;
•
The brightness emitted by a firefly is determined by evaluating the objective function; the better is the evaluation, the brighter is the firefly.

There are two important elements in the FA that simulate natural phenomena: the light intensity variation and the attractiveness formulation. For the sake of simplicity, the attractiveness of a firefly is a function of its brightness. The attractiveness varies with the distance between the fireflies. It occurs because the light intensity decreases when the distance between them increases and the light may be absorbed by the environment.

Let $\vec{Y}_{i}$ and $\vec{Y}_{j}$ be the position vectors of fireflies $i$ and $j$ . The attractiveness $\beta$ between the fireflies should be a monotonically decreasing function with respect to the distance $\mathrm{d}(\vec{Y}_{i},\vec{Y}_{j})$ between them [58, 59, 60],

$\beta=\beta_{0}e^{-\gamma\mathrm{d}(\vec{Y}_{i},\vec{Y}_{j})},\gamma>0,$ (12)

in which $\beta_{0}$ is the attractiveness when $\mathrm{d}(\vec{Y}_{i},\vec{Y}_{j})=0$ and $\gamma$ is the light absorption coefficient. The movement of the firefly $i$ attracted by firefly $j$ is given by

$\vec{Y}_{i}^{t+1}=\left(1-\beta\right)\vec{Y}_{i}^{t}+\beta\vec{Y}_{j}^{t}+% \alpha\left(\mathrm{rand}-\frac{1}{2}\right),$ (13)

where $t$ represents the current iteration, $\alpha$ is a parameter used to control randomness and $\mathrm{rand}$ is a random number between 0 and 1. Figure 4 shows the flowchart of the Firefly Algorithm.

Figure 4.
Flowchart of Firefly Algorithm.

The stopping criterion strongly depends on the problem to be solved. In classic maximum/minimum optimization problems, usual criteria are the number of iterations and the amount of times that the objective function is calculated.
5. Firefly algorithm applied to COVQ codebook design

The FA-COVQ uses the Firefly Algorithm embedded to the codebook design phase. The target is to take advantage of the multiple possible solutions of the FA to generate a better codebook in terms of the achievement of a minimum distortion. In this work, conventional COVQ codebook design is the name in literature used to the COVQ codebook design considered in [17].

The implementation of the FA-COVQ considers that each firefly represents one codebook. So, assuming the use of $F$ fireflies, that is, $F$ different codebooks, it follows that at the end of FA-COVQ codebook design there will be $F$ solutions and the one which presents the smallest average distortion is chosen as the overall solution. In terms of the Firefly Algorithm, this solution is represented by the brightest firefly at the last iteration. Also, each firefly has its own partition and average distortion, which is the FA optimization function. The FA-COVQ codebook design steps are described as follows:

1.
Initialization – initially $F$ codebooks $Y_{f};f=1,2,\ldots,F$ , of size $N$ and $K$ -dimensional codevectors are, for example, randomly generated. Each codebook is considered as a firefly position;
2.
Partitioning 1 – for each firefly, $M$ training vectors are mapped into the regions $S_{i}$ according to

$\displaystyle S_{i}=\{\vec{X}|\mathrm{d}_{\mathrm{covq}}(\vec{X},\vec{Y}_{i})$ $\displaystyle\quad∼{}\leqslant\mathrm{d}_{\mathrm{covq}}(\vec{X},\vec{Y}_{j})% \ \forall\ j\neq\ i\};$ (14)
3.
Average distortion computation – the average distortion $\overline{D}_{f}^{t}$ is calculated for each firefly, as

$\overline{D}_{f}^{t}=\frac{1}{KM}\sum_{i=1}^{M}\sum_{j=1}^{N}\mathrm{d}_{% \mathrm{covq}}(\vec{X}_{i},\vec{Y}_{j}),$ (15)

where $f$ is the firefly index (that is, $f$ stands for the $f$ -th firefly) and $t$ is the number of the current iteration;
4.
Brightest firefly selection – the brightness of each firefly is calculated with respect to its average distortion computed in Step 3. The brightest firefly is the current candidate to be the FA-COVQ solution. The brightness intensity of a firefly is given by the inverse of the corresponding average distortion, that is, the smaller is the average distortion, the brighter is the firefly.

$\mathrm{brightness}\left(Y_{f}\right)^{t}=\frac{1}{\overline{D}_{f}^{t}};$ (16)
5.
Stopping criterion – the stopping criterion depends on the average distortion of the brightest firefly’s corresponding codebook, that is, of the best one, given by

$\frac{\overline{D}_{\mathrm{best}}^{t-1}-\overline{D}_{\mathrm{best}}^{t}}{% \overline{D}_{\mathrm{best}}^{t-1}}\leqslant\mu.$ (17)

If it is satisfied, the algorithm is terminated and the brightest firefly found in Step 4 is returned as the solution. Otherwise, the algorithm goes to Step 6;
6.
Firefly algorithm update 1 – each firefly (with the exception of the brightest one) is attracted by a brighter one according to Eqs (12) and (13);
7.
Firefly algorithm update 2 – the brightest firefly moves randomly according to

$\vec{Y}_{j}^{t+1}=\vec{Y}_{j}^{t}+\alpha\left(\mathrm{rand}-\frac{1}{2}\right);$ (18)
8.
Partitioning 2 – the $M$ training vectors of all $F$ codebooks are mapped into the $N$ partitioning regions of each codebook according to Eq. (14);
9.
Codebook update – for each firefly, the codevectors are updated according to Eq. (10) and return to Step 2.

Notice that the partitioning step is performed twice (Steps 2 and 8) for each iteration in FA-COVQ while the conventional COVQ algorithm performs it just once for each iteration (Step 2). This is necessary to update the partitions with the influence of the firefly steps. Otherwise, the codebook update Step 9 would override the modifications incorporated by the firefly algorithm. Figure 5 shows the flowchart of FA-COVQ algorithm.

Figure 5.
Flowchart of FA-COVQ algorithm.

The swarm COVQ codebook design algorithm itself has a higher computational complexity when compared to the non-swarm version of the algorithm due to the multiple particles used. The fact that the partitioning step is executed twice for every particle also leads to a higher complexity when compared to conventional COVQ. This motivates the search for techniques to accelerate the codebook design algorithm, as proposed in Section 6.
6. Speeding up COVQ codebook design

Channel-Optimized Vector Quantization codebook design has a high computational cost due to the amount of logic and arithmetic operations performed at each iteration. The partitioning is the most complex step of COVQ codebook design. In this step, the conventional COVQ codebook design scheme performs $N^{2}$ Euclidean distance calculations at each iteration for each training vector, as presented in Eq. (15). When there is a swarm algorithm accommodated, that amount is multiplied by the number of particles used. Hence, a challenging and relevant problem is the computational complexity of the algorithm.

In this work, alternatives are presented for the purpose of execution time savings of the swarm based COVQ codebook design. Precisely, in the present work efficient nearest neighbor search techniques (originally proposed in the literature to speed up the encoding phase of VQ) are accommodated in the partitioning steps of FA-COVQ codebook design.

6.1 Efficient nearest neighbor search techniques

Alternatives to reduce the computational cost, in general, involve eliminating codevectors from the search for the nearest neighbor. Thus, elimination criteria are included to prevent the partial or complete calculation of the squared Euclidean distance. The application of those criteria involves an additional set of operations carried out to determine, for instance, the average and norm of vectors. For some techniques, extra memory storage is also needed during algorithm execution. In this section the following techniques are addressed: Partial Distance Search (PDS) [8], Equal-average Nearest Neighbor Search (ENNS) [50], Improved Equal-average Neighbor Search (IENNS) [44], Equal-average Equal-variance Nearest Neighbor Search (EENNS) [36], Improved Equal-average Equal-variance Nearest Neighbor Search (IEENNS) [6], Equal-average Equal-variance Equal-norm Nearest Neighbor Search (EEENNS) [40].

Bei and Gray introduced the algorithm PDS as a modification to the encoding stage of Vector Quantization. This method avoids to perform the squared difference between every component of two vectors by checking if the partial distance is greater than the smallest distance found so far. Initially, the first distance calculation is performed completely according to Eq. (5). Then, for the next codevectors, for each component, it is checked whether the partial distance is greater than the smallest distance found. If that is true, there is no need to continue the calculation and the algorithm can proceed to the next codevector. Thus, it is possible to reduce the number of multiplications, additions and subtractions at the price of increasing the number of comparisons [8].

The rest of the algorithms in this paper uses average, standard deviation, norm or a combination of them to reduce the number of squared Euclidean distance calculations. The ENNS algorithm takes into account the fact that close vectors have close component averages, that is, the average of the components. Thus, the average of the closest codevector is usually close to the corresponding training vector average. Based on this premise, an elimination criterion is established. Let $m_{\vec{Y}_{i}}$ be the codevector $\vec{Y}_{i}$ average, $m_{\vec{X}}$ the training vector $\vec{X}$ average and $d_{\mathrm{min}}$ the distance between the training vector $\vec{X}$ and the codevector that presents the smallest absolute difference in terms of its average and $m_{\vec{X}}$ . If a codevector $\vec{Y}_{i}$ satisfies

$\displaystyle m_{\vec{Y}_{i}}\geqslant m_{\vec{X}}+\sqrt{\frac{d_{\mathrm{min}% }}{K}}\ \ \ \ \ \ \mathrm{or}$ $\displaystyle m_{\vec{Y}_{i}}\leqslant m_{\vec{X}}-\sqrt{\frac{d_{\mathrm{min}% }}{K}},$ (19)

then $\vec{Y}_{i}$ can be eliminated in the search for the nearest neighbor. If the codevector is not eliminated, then the PDS technique is used. In ENNS it is necessary to compute and store $N$ average values previously. In order to apply ENNS, the codevectors should be sorted in ascending order according to the mean values prior to starting the search.

The IENNS algorithm can be seen as an improvement of the ENNS algorithm. In the IENNS technique, the vectors are split into two equal-sized sub-vectors. Let $S_{\vec{X}_{l}}$ and $S_{\vec{Y}_{jl}}$ be the sum in all dimensions of the sub-vectors formed by the components of the first half of the training vector $\vec{X}$ and codevector $\vec{Y}_{j}$ respectively. Let $S_{\vec{X}_{r}}$ and $S_{\vec{Y}_{jr}}$ be the sum of all components of the sub-vectors formed by the remaining components of the training vector $\vec{X}$ and codevector $\vec{Y}_{j}$ respectively. If the condition

$\displaystyle(S_{\vec{X}_{l}}-S_{\vec{Y}_{jl}})^{2}\geqslant\frac{Kd_{\mathrm{% min}}}{2}\ \ \ \ \ \ \mathrm{or}$ $\displaystyle(S_{\vec{X}_{r}}-S_{\vec{Y}_{jr}})^{2}\geqslant\frac{Kd_{\mathrm{% min}}}{2}$ (20)

is satisfied, then the codevector $\vec{Y}_{j}$ can be safely eliminated in the search for the nearest neighbor. The IENNS algorithm performs all the steps of ENNS with the difference that the new test in Eq. (20), is run immediately after the elimination criteria based on averages on Eq. (19). The mean values of $N$ codevectors and the sum of $2\times N$ sub-vectors must be previously calculated and stored.

Figure 6.

Set of images of 256 $\times$ 256 pixels coded at 8.0 bpp used in simulations.

The remaining algorithms, EENNS, IEENNS and EEENNS, follow the same ENNS structure and include new criteria to eliminate more codevectors. Besides the relation between the vectors averages, the EENNS creates a new criterion based on the relation between the standard deviation of the vectors. The standard deviation of a $K$ -dimensional vector $\vec{w}=\left(w_{1},w_{2},\ldots,w_{K}\right)$ is given by

$v_{\vec{w}}=\sqrt{\mathrm{d}(\vec{w},\vec{m}_{\vec{w}})},$ (21)

where $\vec{m}_{\vec{w}}$ is a vector in which every component is equal to the vector $\vec{w}$ average. So, let $v_{\vec{X}}$ and $v_{\vec{Y}_{j}}$ be the standard deviation values of the training vector $\vec{X}$ and codevector $\vec{Y}_{j}$ respectively. The new criterion is defined as follows:

$\displaystyle v_{\vec{Y}_{j}}\geqslant v_{\vec{X}}+\sqrt{d_{\mathrm{min}}}\ \ % \ \ \ \ \mathrm{or}$ $\displaystyle v_{\vec{Y}_{j}}\leqslant v_{\vec{X}}-\sqrt{d_{\mathrm{min}}}.$ (22)

Thus, $N$ values of average and standard deviation must be previously calculated and stored.

Such as EENNS technique, the IEENNS also uses the average and standard deviation based inequalities to eliminate codevectors. The difference is that the latter one uses both simultaneously. So, the inequality introduced by IEENNS is given by

$K(m_{\vec{X}}-m_{\vec{Y}_{j}})^{2}+(v_{\vec{X}}-v_{\vec{Y}_{j}})^{2}\geqslant d% _{\mathrm{min}}.$ (23)

The IEENNS is performed in two steps. The first one is the criterion based on the vectors average defined in Eq. (19). Then the criterion based on Eq. (23) is applied and only after, if necessary, the PDS algorithm is used. For the IEENNS it is enough to calculate and store previously the same number of values that EENNS, since IEENNS uses no additional information.

The EEENNS algorithm also takes advantage of the closeness relation with respect to the average and standard deviation of the vectors, but includes a new one based on the vectors norm, defined by

$\|\vec{w}\|=\sqrt{\sum_{i=1}^{K}w_{i}^{2}}.$ (24)

Let $\|\vec{X}\|$ and $\|\vec{Y}_{j}\|$ be the norm values of the training vector $\vec{X}$ and codevector $\vec{Y}_{j}$ respectively. The new elimination criterion is given by

$\displaystyle\|\vec{Y}_{j}\|\geqslant\|\vec{X}\|+\sqrt{d_{\mathrm{min}}}\ \ \ % \ \ \ \mathrm{or}$ $\displaystyle\|\vec{Y}_{j}\|\leqslant\|\vec{X}\|-\sqrt{d_{\mathrm{min}}}.$ (25)

This criterion is applied after the second criterion of the EENNS algorithm, based on standard deviation. It is important to mention that $N$ average, $N$ standard deviation and $N$ norm values of the codevectors must be calculated prior to the EEENNS method execution.

In the encoding phase, the pre-calculated data of the codevectors are used only for querying and need to be computed and stored only once for future reference. However, it is also necessary at each encoding process to perform the pre-calculation with respect to the $M$ input vectors. In the codebook design phase, those data also need to be stored, the pre-calculations related to the input vectors must be performed once and, for each iteration, one needs to sort and compute the average, standard deviation and norm of the $N$ codevectors according to the technique used. Furthermore, considering a bio-inspired swarm technique, such as the Firefly Algorithm, the amount of pre-calculations and sorting mentioned for codebook design related to the codevectors is, in a single iteration, equal to twice the number of particles used. This occurs because, as mentioned before, the partitioning step is performed twice for each particle.

In FA-COVQ, the pre-calculations concerning the training vectors should be performed before Step 1 (Initialization). Concerning the codevectors, at each iteration they must be sorted in ascending order and the pre-calculus should be performed before Step 2 (Partitioning 1) and Step 8 (Partitioning 2).

Table 1

Mean values and standard deviations of final average distortion ( $\overline{D}$ ) achieved by conventional COVQ and FA-COVQ for $N=$ 256

Image	Measure	$\varepsilon=$ 0.005		$\varepsilon=$ 0.010		$\varepsilon=$ 0.050		$\varepsilon=0.100$
		COVQ	FA-COVQ	COVQ	FA-COVQ	COVQ	FA-COVQ	COVQ	FA-COVQ
Lena	Mean	110.63	96.44	130.89	114.87	241.08	225.37	376.09	371.88
	Standard deviation	1.80	1.27	2.05	1.88	5.02	2.47	15.35	3.99
Boat	Mean	164.12	141.25	189.40	166.48	308.34	293.51	449.45	445.54
	Standard deviation	2.52	1.94	3.89	2.41	4.16	1.51	4.75	2.80
Clock	Mean	102.30	83.19	128.17	104.44	252.66	238.41	420.19	415.85
	Standard deviation	1.59	5.10	3.52	1.90	4.06	4.76	10.99	3.14

7. Simulation results

Simulation results are presented for images Lena, Boat and Clock, 256 $\times$ 256 pixels with 256 gray levels, shown in Fig. 6. These images were used as training sets for codebook design and as images transmitted through the noisy channel. All simulations were carried out using a computer with Windows 7, Intel Core i7-4500U, 8 GB of memory and the algorithms were implemented using C/C $++$ .

Table 2
$\mathrm{\overline{PSNR}_{final}}$ results achieved by different codebook design methods after transmission over a BSC for $\varepsilon=$ 0.005 and $\varepsilon=$ 0.010. The highest values for each combination of $\varepsilon$ , $N$ and image are in bold

Image	Method	$\varepsilon=$ 0.005				$\varepsilon=$ 0.010
		$N=$ 32	$N=$ 64	$N=$ 128	$N=$ 256	$N=$ 32	$N=$ 64	$N=$ 128	$N=$ 256
Lena	COVQ	24.99	25.79	26.14	26.49	24.54	24.56	24.72	24.88
	FA-COVQ	25.32	26.21	26.63	27.08	24.85	24.95	25.28	25.46
	FSS-COVQ	25.42	26.27	26.81	27.12	24.78	24.97	25.25	25.38
	PSO-COVQ	25.34	26.24	26.61	27.00	24.75	25.03	25.03	25.41
Boat	COVQ	23.77	24.54	25.00	25.19	23.26	23.53	23.65	23.71
	FA-COVQ	23.99	24.81	25.33	25.81	23.47	23.71	24.29	24.36
	FSS-COVQ	24.03	24.86	25.45	25.84	23.54	23.97	24.22	24.36
	PSO-COVQ	23.93	24.81	25.44	25.75	23.53	23.95	24.00	24.14
Clock	COVQ	24.79	25.17	25.65	25.44	23.75	23.56	24.14	24.06
	FA-COVQ	25.07	25.84	26.54	26.79	24.07	24.37	24.93	25.29
	FSS-COVQ	25.20	25.78	26.22	26.68	24.06	24.24	24.88	25.57
	PSO-COVQ	25.10	25.70	26.07	26.53	23.92	24.48	24.97	25.66

Table 3

$\mathrm{\overline{PSNR}_{final}}$ results achieved by different codebook design methods after transmission over a BSC for $\varepsilon=$ 0.050 and $\varepsilon=0.100$ . The highest values for each combination of $\varepsilon$ , $N$ and image are in bold

Image	Method	$\varepsilon=$ 0.050				$\varepsilon=0.100$
		$N=$ 32	$N=$ 64	$N=$ 128	$N=$ 256	$N=$ 32	$N=$ 64	$N=$ 128	$N=$ 256
Lena	COVQ	20.64	20.88	21.06	20.76	19.02	19.07	18.87	18.88
	FA-COVQ	20.76	21.20	21.11	21.18	19.29	18.91	18.93	18.94
	FSS-COVQ	20.64	21.19	21.18	21.08	19.23	18.95	18.93	18.99
	PSO-COVQ	20.81	21.19	21.08	20.98	19.25	18.95	18.98	18.97
Boat	COVQ	20.18	20.38	20.57	20.33	18.74	18.69	18.33	18.42
	FA-COVQ	20.09	20.69	20.82	20.46	18.94	18.71	18.25	18.52
	FSS-COVQ	20.16	20.67	20.88	20.39	18.96	18.73	18.30	18.51
	PSO-COVQ	20.21	20.68	20.83	20.12	18.96	18.61	18.30	18.54
Clock	COVQ	20.10	20.32	19.60	19.79	18.12	17.96	18.26	17.96
	FA-COVQ	20.40	20.38	20.19	20.02	18.15	18.27	18.24	18.06
	FSS-COVQ	20.43	20.25	19.87	20.12	18.14	18.21	18.29	18.13
	PSO-COVQ	20.35	20.19	20.17	20.07	18.14	18.29	18.26	17.99

The codebooks were designed with sizes ( $N$ ) 32, 64, 128 and 256, dimension $K=$ 16 (blocks of 4 $\times$ 4 pixels) and for transmission over a binary symmetric channel (BSC) with bit error rates ( $\varepsilon$ ) 0.005, 0.010, 0.050 and 0.100. The stopping criterion adopted was the distortion threshold $\mu=$ 0.001. The codebooks were initialized with random vectors selected from the training set. Regarding the hybrid methods for codebook design, the simulation results are presented for a swarm of 10 particles. Thus, considering FA-COVQ, for each codebook size $N$ , 10 codebooks (each firefly represents a codebook) were generated for each image used in the study.

The FA-COVQ algorithm is compared with the conventional COVQ and two other hybrid methods: an algorithm based on Fish School Search (FSS), called FSS-COVQ [20], and an algorithm based on Particle Swarm Optimization, called PSO-COVQ [37]. The parameter values $\beta_{0}$ , $\alpha$ and $\gamma$ applied to the FA-COVQ in the codebook design stage are 0.4, 0.7 and 0.00001, respectively. The values of $\beta_{0}$ and $\alpha$ were obtained from a preliminary analysis. Sets of values were investigated in the range between 0 and 2, and the set which generated codebooks more robust to channel errors was chosen. Precisely, from a preliminary analysis for a bit error rate $\varepsilon=$ 0.005, the values investigated for $\beta_{0}$ were the ones in the set {0.2, 0.4, 0.6, 0.8, 1.0, 1.2, 1.4, 1.6, 1.8, 2.0}, the values investigated for $\alpha$ were the ones in the set {0.1, 0.3, 0.5, 0.7, 0.9, 1.1, 1.3, 1.5, 1.7, 1.9}, and the values investigated for $\gamma$ were the ones in the set {0.001, 0.0001, 0.00001, 0.000001}. Hence, 10 $\times$ 10 $\times$ 4 $=$ 400 combinations of parameters were tested, and the best combination was selected and used in all simulations. Concerning the PSO-COVQ, the simulations were carried out considering the cognitive constant $c_{1}=0.1$ , the social constant $c_{2}=0.2$ and the inertia factor $w=0.7$ . Regarding FSS-COVQ simulations, the parameters used were individual step 0.0001 and volitive step 0.01, according to [20].

The robustness of the codebooks is measured by using the Peak Signal-to-Noise Ratio (PSNR) of the corresponding reconstructed images after transmission over the noisy channel. In other words, more robust codebooks lead to reconstructed images with better quality, that is, with higher values of PSNR.

7.1 Quality of reconstruction

The mean values and standard deviations of the final average distortions $(\overline{D})$ obtained by a set of codebooks of size $N=$ 256 are shown in Table 1. In general, the FA-COVQ achieved better results in terms of final average distortion when compared to the conventional COVQ. The highest decreasings in terms of the final average distortion obtained by FA-COVQ with respect to conventional COVQ were presented for bit error rates 0.005 and 0.010. For Lena, the average distortions were 96.44 (12.83% of decrease) and 114.87 (12.24% of decrease) respectively. For Boat, the average distortions were 141.25 (13.93% of decrease) and 166.48 (12.10% of decrease) respectively. For Clock, the average distortions were 83.19 (18.68% of decrease) and 104.44 (18.51% of decrease) respectively. An advantage of FA-COVQ codebook design when compared to the conventional COVQ codebook design is the fact that the former is less sensitive to the initial codebook. Indeed, in almost all the cases in Table 1, FA-COVQ led to a smaller standard deviation.

In this work, $\mathrm{\overline{PSNR}}$ is the average of the Peak Signal-to-Noise Ratio (PSNR) values of reconstructed images after 20 transmissions through a noisy channel, and $\mathrm{\overline{PSNR}_{final}}$ is the average $\mathrm{\overline{PSNR}}$ of 10 different codebooks designed for a given size $N$ and bit error rate $\varepsilon$ . Tables 2 and 3 show the $\mathrm{\overline{PSNR}_{final}}$ values achieved by FA-COVQ, FSS-COVQ, PSO-COVQ and conventional COVQ for the three images considered in this paper. Considering Lena image, it is observed that the algorithms FA-COVQ and FSS-COVQ led, each one, to highest values of $\mathrm{\overline{PSNR}_{final}}$ in 37% of the simulations. In average, PSNR gains up to 0.59 dB ( $N=$ 256 and $\varepsilon=$ 0.005) were achieved by substituting COVQ conventional codebooks for FA-COVQ codebooks. When reconstructing the image with FSS-COVQ and PSO-COVQ codebooks in substitution to COVQ conventional ones, gains up to 0.67 dB ( $N=$ 128 and $\varepsilon=$ 0.005) and 0.53 dB ( $N=$ 256 and $\varepsilon=$ 0.010) were obtained respectively. Regarding Boat image, the FSS-COVQ obtained the highest PSNR gains in 10 out of 16 of the combinations of $N$ and $\varepsilon$ . Average gains up to 0.65 dB ( $N=$ 256 and $\varepsilon=$ 0.010) were achieved with FSS-COVQ codebooks in substitution to conventional COVQ codebooks. When substituting conventional COVQ codebooks by FA-COVQ codebooks, PSNR gains up to 0.65 dB were achieved for $N=$ 256 and $\varepsilon=$ 0.010. When reconstructing the image Boat with PSO-COVQ codebooks, PSNR gains up to 0.56 dB ( $N=$ 256 and $\varepsilon=$ 0.005) were obtained. Finally, considering the results for Clock, the images reconstructed with FA-COVQ codebooks presented the highest values of $\mathrm{\overline{PSNR}_{final}}$ in 43.75% of simulations, that is, in 7 out of 16 combinations of $N$ and $\varepsilon$ considered in this paper. When substituting COVQ conventional codebooks, FA-COVQ, FSS-COVQ and PSO-COVQ achieved, in average, PSNR gains up to 1.35 dB ( $N=$ 256 and $\varepsilon=$ 0.005), 1.51 dB ( $N=$ 256 and $\varepsilon=$ 0.010) and 1.60 dB ( $N=$ 256 and $\varepsilon=$ 0.010) for Clock image. It is important to mention that the substitution of COVQ conventional codebooks for FA-COVQ codebooks leads, in general, to significant PSNR gains (more than 0.5 dB) in images reconstructed with codebook size 256, and bit error rates 0.005 and 0.010.

Considering the hybrid techniques (FA-COVQ, FSS-COVQ and PSO-COVQ), in general, FSS-COVQ codebooks led to reconstructed images with more quality in terms of PSNR, as presented in Fig. 7. In 41.66% of simulations, the $\mathrm{\overline{PSNR}_{final}}$ of images reconstructed with FSS-COVQ codebooks achieved the highest values of PSNR. The FA-COVQ led to reconstructed images with the best quality, in terms of PSNR, in 35.42% of simulations.

Figure 7.

Percentage of times that each codebook design method outperforms the others in terms of $\mathrm{\overline{PSNR}_{final}}$ .

Figure 8 shows the images Lena and Clock reconstructed after transmission over a BSC with bit error rate 0.005 and a slice zoomed. Codebooks were designed by conventional COVQ and FA-COVQ for size $N=$ 256. It is noticed that the blocking artifacts are less annoying when the images are quantized by FA-COVQ codebooks as compared to the ones quantized by conventional COVQ codebooks, that is, the increase of the PSNR value by using FA-COVQ in substitution to conventional COVQ reflects the quality of the corresponding reconstructed images. As an example, a reconstructed Clock image with PSNR 26.53 dB was obtained by using FA-COVQ codebook, while a reconstructed one with PSNR 25.63 dB was obtained by using conventional COVQ codebook.

Figure 8.

Reconstructed images after transmission over a BSC, bit error rate 0.005, codebooks designed with size $N=$ 256. (a) Lena by COVQ (PSNR $=$ 26.38 dB), (b) Lena by FA-COVQ (PSNR $=$ 27.07 dB), (c) Clock by COVQ (PSNR $=$ 25.63 dB) and (d) Clock by FA-COVQ (PSNR $=$ 26.53 dB).

In Fig. 9, reconstructed Lena and Clock images are presented after transmission over a binary symmetric channel with bit error rate 0.010. Codebooks were designed by conventional COVQ and FA-COVQ for size $N=$ 256. The bit stream transmitted for each pair of images, quantized by conventional COVQ and FA-COVQ in Fig. 9, were impacted by noise in the same bit stream positions, for example, if the seventh bit of Fig. 9(a) was received with error, the seventh bit of Fig. 9(b) was also received with error. Therefore, it is possible to visually inspect the robustness of the codebooks designed observing the effects caused by the channel noise in blocks of pixels on the same position in a pair of images (using conventional COVQ and FA-COVQ). One can observe the reduction of the visual impairment caused by the spurious blocking artifacts due to transmission errors in the images quantized by FA-COVQ codebook as compared to the respective ones quantized by conventional COVQ codebook. Regarding the results achieved by FA-COVQ, it is also possible to observe that many of the blocks incorrectly reconstructed are similar to their neighbors. The Lena image reconstructed with conventional COVQ codebook obtained PSNR $=$ 25.18 dB and the Lena image reconstructed with FA-COVQ codebook obtained PSNR $=$ 25.95 dB.

Figure 9.

Reconstructed images after transmission over a BSC, bit error rate 0.010, codebooks designed with size $N=$ 256. (a) Lena by COVQ (PSNR $=$ 25.18 dB), (b) Lena by FA-COVQ (PSNR $=$ 25.95 dB), (c) Clock by COVQ (PSNR $=$ 24.44 dB) and (d) Clock by FA-COVQ (PSNR $=$ 25.86 dB).

Results of the non-parametric Wilcoxon test are presented in Table 4 considering the PSNR of reconstructed images using the conventional COVQ and FA-COVQ. The confidence level was set to 95%. It is worth to note that the data set of PSNR values obtained by the reconstructed images using codebooks designed by FA-COVQ method presents a statistically significant superiority in most cases. It is worth to note that, considering bit error rates 0.005 and 0.010, FA-COVQ outperforms conventional COVQ in all cases. For higher bit error rates (e.g., $\varepsilon=$ 0.050 and $\varepsilon=$ 0.100), the results are similar in many cases. In few cases, FA-COVQ leads to images with lower quality of reconstruction when compared to conventional COVQ.

Table 4

Non-parametric Wilcoxon test for two data sets of PSNR values of reconstructed images by conventional COVQ and FA-COVQ with a confidence level of 95%. A black triangle ( $\blacktriangle$ ) means that FA-COVQ data set presents a statistically significant superiority when compared to conventional COVQ one. A white triangle ( $\triangledown$ ) means that conventional COVQ data set is superior and a slash (–) means both data sets are similar

Image	$N$	$\varepsilon=$ 0.005	$\varepsilon=$ 0.010	$\varepsilon=$ 0.050	$\varepsilon=0.100$
Lena	32	$\blacktriangle$	$\blacktriangle$	–	$\blacktriangle$
	64	$\blacktriangle$	$\blacktriangle$	$\blacktriangle$	$\triangledown$
	128	$\blacktriangle$	$\blacktriangle$	–	–
	256	$\blacktriangle$	$\blacktriangle$	$\blacktriangle$	–
Boat	32	$\blacktriangle$	$\blacktriangle$	–	$\blacktriangle$
	64	$\blacktriangle$	$\blacktriangle$	$\blacktriangle$	–
	128	$\blacktriangle$	$\blacktriangle$	–	$\triangledown$
	256	$\blacktriangle$	$\blacktriangle$	–	–
Clock	32	$\blacktriangle$	$\blacktriangle$	$\blacktriangle$	–
	64	$\blacktriangle$	$\blacktriangle$	–	$\blacktriangle$
	128	$\blacktriangle$	$\blacktriangle$	$\blacktriangle$	–
	256	$\blacktriangle$	$\blacktriangle$	$\blacktriangle$	–

Table 5

FA-COVQ codebook design execution time (in minutes) considering 7 NNS techniques. For each combination of $N$ and $\varepsilon$ , the lowest results for each combination of $\varepsilon$ , $N$ and image are in bold

Image	$\varepsilon$	$N$	Method
			FS	PDS	ENNS	IENNS	EENNS	IEENNS	EEENNS
Lena	0.005	32	3.32	2.21	0.53	0.44	0.48	0.36	0.51
		64	15.93	9.41	1.75	1.47	1.50	1.15	1.60
		128	65.10	37.66	5.32	4.71	5.02	3.57	4.80
		256	293.65	154.45	20.58	17.37	18.36	12.06	17.11
	0.050	32	2.33	1.24	0.42	0.38	0.40	0.34	0.40
		64	10.57	5.37	1.53	1.39	1.41	1.01	1.45
		128	51.42	23.56	5.42	5.72	6.24	3.95	5.30
		256	207.41	95.48	21.19	18.48	20.62	15.42	20.17
Boat	0.005	32	3.16	2.13	0.61	0.47	0.53	0.44	0.59
		64	15.40	8.88	2.13	1.81	1.97	1.46	1.94
		128	63.27	36.17	7.90	6.07	6.60	4.76	6.67
		256	281.14	153.16	30.02	21.75	24.19	16.67	25.18
	0.050	32	2.23	1.30	0.48	0.44	0.44	0.40	0.46
		64	10.23	5.22	1.82	1.59	1.74	1.47	1.87
		128	48.76	25.54	6.77	6.20	7.55	5.21	6.72
		256	218.98	105.33	29.77	24.63	27.56	19.99	26.52
Clock	0.005	32	3.59	1.92	0.38	0.36	0.41	0.35	0.39
		64	17.14	8.83	1.41	1.36	1.14	1.07	1.20
		128	71.21	36.74	4.78	3.87	3.91	3.49	4.22
		256	321.03	138.82	15.51	11.23	13.45	10.83	12.30
	0.050	32	2.13	1.01	0.33	0.35	0.33	0.32	0.36
		64	9.04	5.34	1.24	1.23	1.18	1.10	1.28
		128	46.27	19.23	4.41	4.14	4.43	3.92	4.42
		256	187.73	70.90	17.35	15.11	15.01	13.02	16.26

Figure 10 shows the average distortion achieved by a set of 10 codebooks designed with size $N=$ 128 and for a binary symmetric channel with bit error rate 0.010. The training set used was Lena. The figure presents the average distortion for each iteration ( $\overline{D}^{t}$ ) of the conventional COVQ and FA-COVQ codebook design. For each iteration of FA-COVQ algorithm, the number of the current brightest firefly is registered in the curve. As an example, the FA-COVQ codebook design ran 26 iterations and it achieved a final average distortion equals to 141.01; for 13 out of 26 iterations, the brightest firefly has changed during the process. There were 8 (out of 10) different fireflies on the whole execution, which means that the solutions do not get stagnated over a few ones, and this can be seen as the attempt of the algorithm to escape from local minima. The conventional COVQ algorithm for codebook design stage executed 17 iterations and by the end of this process a final average distortion of 154.71 was achieved.

Figure 10.

Average distortion for each iteration of FA-COVQ and conventional COVQ codebook design algorithm with $N=$ 128 and $\varepsilon=$ 0.010.

Table 6

Codebook design execution time for FA-COVQ, FSS-COVQ and PSO-COVQ with IEENNS considering $\varepsilon=$ 0.005 and $\varepsilon=$ 0.010. The lowest results for each combination of $\varepsilon$ , $N$ and image are in bold

Image	Method	$\varepsilon=$ 0.005				$\varepsilon=$ 0.010
		$N=$ 32	$N=$ 64	$N=$ 128	$N=$ 256	$N=$ 32	$N=$ 64	$N=$ 128	$N=$ 256
Lena	FA-COVQ	0.36	1.15	3.57	12.06	0.39	1.33	3.99	12.55
	FSS-COVQ	0.54	1.56	4.19	13.50	0.49	1.51	4.38	15.16
	PSO-COVQ	0.53	1.55	4.41	14.95	0.50	1.53	4.30	16.43
Boat	FA-COVQ	0.44	1.46	4.76	16.67	0.48	1.54	5.17	17.39
	FSS-COVQ	0.61	1.95	6.02	17.61	0.59	1.88	5.81	17.23
	PSO-COVQ	0.49	1.71	5.85	18.67	0.55	1.87	5.91	20.90
Clock	FA-COVQ	0.35	1.07	3.49	10.83	0.39	1.13	3.67	11.24
	FSS-COVQ	0.48	1.36	3.61	10.26	0.47	1.37	3.76	11.00
	PSO-COVQ	0.48	1.21	3.59	11.01	0.42	1.24	4.19	12.50

Table 7

Codebook design execution time for FA-COVQ, FSS-COVQ and PS-COVQ with IEENNS considering $\varepsilon=$ 0.050 and $\varepsilon=0.100$ . The lowest results for each combination of $\varepsilon$ , $N$ and image are in bold

Image	Method	$\varepsilon=$ 0.050				$\varepsilon=0.100$
		$N=$ 32	$N=$ 64	$N=$ 128	$N=$ 256	$N=$ 32	$N=$ 64	$N=$ 128	$N=$ 256
Lena	FA-COVQ	0.34	1.01	3.95	15.42	0.29	0.97	3.62	15.35
	FSS-COVQ	0.38	1.22	4.59	15.48	0.29	1.07	3.90	15.01
	PSO-COVQ	0.38	1.33	4.95	16.98	0.29	1.24	4.90	16.64
Boat	FA-COVQ	0.40	1.47	5.21	19.99	0.32	1.12	5.11	17.03
	FSS-COVQ	0.45	1.49	5.27	20.57	0.33	1.22	5.19	17.16
	PSO-COVQ	0.48	1.72	6.25	23.08	0.36	1.29	5.35	20.10
Clock	FA-COVQ	0.32	1.10	3.92	13.02	0.24	0.88	3.34	11.77
	FSS-COVQ	0.39	1.23	4.06	13.11	0.29	0.96	3.71	13.97
	PSO-COVQ	0.38	1.15	4.70	14.79	0.29	1.01	3.74	13.82

7.2 Execution time

Table 5 shows the results for all NNS techniques presented in this paper applied to FA-COVQ codebook design: full search (FS), PDS, ENNS, IENNS, EENNS, IEENNS and EEENNS. In general, IEENNS showed better results in terms of execution time savings when used in the partitioning steps of FA-COVQ codebook design. For Lena, time savings up to 95.89% was achieved with respect to FS, decreasing the codebook design from 293.65 minutes to 12.06 minutes, for $N=$ 256 and $\varepsilon=$ 0.005. For $N=$ 128 and $\varepsilon=$ 0.010, time savings up to 97.11% with respect to FS was achieved, decreasing the execution time from 67.8 minutes to 3.99 minutes. For Boat and Clock, the IEENNS technique also presented the best results regarding execution time savings. For example, considering Boat, $N=$ 256 and $\varepsilon=$ 0.005, time savings up to 94.07% with respect to FS was achieved, decreasing the execution time from 281.14 minutes (using FS) to 16.67 minutes (using IEENNS). For Clock, $N=$ 256 and $\varepsilon=$ 0.005, time savings up to 96.63% with respect to FS was achieved, decreasing FA-COVQ codebook design execution time from 321.03 minutes to 10.83 minutes.

Regarding the efficient nearest neighbor search (NNS) techniques presented previously, the one who led to more time savings was IEENNS. As presented in Fig. 11, considering all hybrid methods presented in this paper (FA-COVQ, FSS-COVQ and PSO-COVQ), IEENNS led the highest time savings in 95% of simulations. It was possible to achieve codebook design execution time savings up to 96.63%. It was achieved for Clock, using FA-COVQ codebook design with $N=$ 256 and $\varepsilon=$ 0.005. In this case, codebook design execution time was decreased from 321.03 minutes (using FS) to 10.83 minutes (using IEENNS). The remaining techniques led to the best results in just a few simulations. ENNS, for example, was the best one in 2.1% of simulations, where execution time savings up to 95.17% with respect to FS was obtained.

Figure 11.

Percentage of times that each NNS technique outperforms the others in terms of execution time savings.

Figure 12.

Percentage of times that each hybrid codebook design method, using IEENNS, showed better results in terms of execution time.

In Tables 6 and 7, the execution time in minutes are presented for FA-COVQ, FSS-COVQ and PSO-COVQ using IEENNS as NNS technique. In most of simulations, the FA-COVQ method allows faster codebook design. For example, considering Lena image, $N=$ 32 and $\varepsilon=$ 0.005, FA-COVQ codebook design execution time was 0.36 minutes, while the execution times for FSS-COVQ and PSO-COVQ were 0.54 and 0.53 minutes, respectively. For Lena image, the only case where FA-COVQ did not achieve the fastest codebook design was for $N=$ 256 and $\varepsilon=$ 0.100. In this case, FSS-COVQ codebook design execution time was 15.01 minutes, while the FA-COVQ execution time was 15.35 minutes. Regarding Boat image, for $N=$ 64 and $\varepsilon=$ 0.010, FA-COVQ codebook design execution time was 1.54 minutes, while FSS-COVQ and PSO-COVQ execution times were 1.88 and 1.87 minutes, respectively. Concerning simulations results for image Clock, for example, for $N=$ 128 and $\varepsilon=$ 0.005, FA-COVQ codebook design execution time was 3.49 minutes, while FSS-COVQ and PSO-COVQ execution times were 3.61 and 3.59 minutes, respectively. In general, FA-COVQ codebook design is faster than FSS-COVQ and PSO-COVQ codebook design. As observed in Fig. 12, FA-COVQ is the fastest swarm technique in 88.6% of the simulations.

8. Conclusion

This work presents an alternative to conventional Channel-Optimized Vector Quantization (COVQ) codebook design based on bio-inspired swarm intelligence computation. A hybrid method based on the Firefly Algorithm (FA) is proposed to COVQ codebook design, called FA-COVQ. This approach aims to reduce the final average distortion of the codebooks designed as an attempt to minimize the effects of channel noise in the quality of reconstructed images. Additionally, alternatives to accelerate FA-COVQ codebook design are presented, which consist on including efficient nearest neighbor search (NNS) techniques in the partitioning steps of FA-COVQ codebook design. It is worth to mention that the original application of these acceleration techniques in the literature is in the encoding phase of Vector Quantization.

The proposed method differs from other FA-based codebook design techniques in terms of how the swarm algorithm is used with the LBG algorithm. Previously published works use the LBG algorithm to generate a codebook that is used as one of the particles (or fireflies in the case of the Firefly Algorithm). In this paper, the Firefly Algorithm is embedded to the LBG iterations taking advantage of using bio-inspired computation approach to optimization problem by attempting to avoid trapping to local minima and LBG algorithm in attempting to satisfy the nearest neighbor conditions for partition and centroid condition for codevectors.

Future works may consider other swarm algorithms like the Honey-Bee Mating Algorithm [1] applied to COVQ codebook design. Future works also include the use of other fast NNS techniques to be incorporated to COVQ codebook design as well as the use of swarm algorithms for COVQ codebook design with the purpose of image transmission over different channels, such as Rayleigh, Rician and Nakagami fading channels [47, 48, 49, 53].

Footnotes

Acknowledgments

The authors would like to thank CNPq and FACEPE for the financial support. The authors also would like to thank the anonymous reviewers for their valuable comments and suggestions to improve the quality of the paper. The authors would like to express their gratitude to Prof. Carmelo J.A. Bastos Filho, for his relevant comments and proficient discussions about swarm intelligence algorithms.

References

Abbass

. MBO: Marriage in honey bees optimization – A haplometrosis polygynous swarming approach. In IEEE Congress on Evolutionary Computation. 2001; 207-214.

Adeli

Hung

. Machine Learning – Neural Networks, Genetic Algorithms, and Fuzzy Systems. New York: John Wiley and Sons; 1995.

Akay

Karaboga

. A survey on the applications of artificial bee colony in signal, image, and video processing. Signal, Image and Video Processing. 2015; 9(4): 967-90.

Alkhalaf

Alfarraj

Hemeida

. Fuzzy-VQ image compression based hybrid PSOGSA optimization algorithm. In IEEE International Conference on Fuzzy Systems (FUZZ-IEEE). 2015; 1-6.

Azevedo

CRB

Azevedo

FEAG

Lopes

WTA

Madeiro

. Terrain-based memetic algorithms for vector quantizer design. In Krasnogor

Melián-Batista

Moreno-Pérez

Moreno-Vega

Pelta

. (Org.). Nature Inspired Cooperative Strategies for Optimization (NICSO 2008). Berlin/Heidelberg: Springer. 2009; 236: 197-211.

Baek

Jeon

Sung

. A fast encoding algorithm for vector quantization. IEEE Signal Processing Letters. 1997; 4(12): 325-327.

Bastos-Filho

CJA

Lima-Neto

Lins

AJCC

Nascimento

AIS

Lima

. A novel search algorithm based on fish school behavior. In IEEE International Conference on Systems, Man and Cybernetics (SMC). 2008; 2646-2651.

Bei

Gray

. An improvement of the minimum distortion enconding algorithm for vector quantization. IEEE Transactions on Communications. 1985; 33(10): 1132-1133.

Boulkabeit

Mthembu

De Lima Neto

Marwala

. Finite element model updating using fish school search and volitive particle swarm optimization. Integrated Computer-Aided Engineering. 2015; 22(4): 361-376.

10.

Chang

Nguyen

Lin

. A reversible compression code hiding using SOC and SMVQ indices. Information Sciences. 2015; 300: 85-99.

11.

Chen

Yang

Gou

. Image compression method using improved PSO vector quantization. Advances in Natural Computation. 2005; 3612: 490-495.

12.

Chou

J-S

Pham

A-D

. Smart artificial firefly colony algorithm-based support vector regression for enhanced forecasting in civil engineering. Computer-Aided Civil and Infrastructure Engineering. 2015; 30(9): 715-732.

13.

Cruz

Maia

Szabo

de Castro

. A bee-inspired algorithm for optimal data clustering. In IEEE Congress on Evolutionary Computation. 2013; 3140-3147.

14.

Dorigo

Birattari

Stutzle

. Ant colony optimization. IEEE Computational Intelligence Magazine. 2006; 1(4): 28-39.

15.

Eberhart

Kennedy

. A new optimizer using particle swarm theory. In International Symposium on Micro Machine and Human Science. 1995; 39-43.

16.

Eberhart

Kennedy

. Particle swarm optimization. In IEEE International Conference on Neural Networks. 1995; 4: 1942-1948.

17.

Farvardin

. A study of vector quantization for noisy channels. IEEE Transactions on Information Theory. 1990; 36(4): 799-809.

18.

Favardin

Vaishampayan

. On the performance and complexity of channel-optimized vector quantizers. IEEE Transactions on Information Theory. 1991; 37(1): 155-160.

19.

Feng

Horng

. VQ-Based fuzzy compression systems designs through bacterial foraging particle swarm optimization algorithm. In 5th IEEE International Conference on Genetic and Evolutionary Computing (ICGEC). 2011: 256-259.

20.

Ferreira

FABS

Madeiro

. A fish school search based algorithm for image channel-optimized vector quantization. In IEEE International Conference on Systems, Man, and Cybernetics (SMC). 2016; 1680-1685.

21.

Fister

Yang

Brest

. A comprehensive review of firefly algorithms. Swarm and Evolutionary Computation. 2013; 13: 34-46.

22.

Gersho

Gray

. Vector quantization and signal compression. Massachusetts: Springer Science & Business Media; 1992.

23.

Gray

. Vector quantization. IEEE ASSP Magazine. 1984; 1(2): 4-29.

24.

Horng

Jiang

. Image vector quantization algorithm via honey bee mating optimization. Expert Systems with Applications. 2011; 38(3): 1382-1392.

25.

Horng

Jiang

. The artificial bee colony algorithm for vector quantization in image compression. In 4th IEEE International Conference on Broadband Network and Multimedia Technology (IC-BNMT). 2011: 319-323.

26.

Horng

. Vector quantization using the firefly algorithm for image compression. Expert Systems with Applications. 2012; 39(1): 1078-1091.

27.

Hosseini

Naghsh-Nilchi

. Medical ultrasound image compression using contextual vector quantization. Computers in Biology and Medicine. 2012; 42(7): 743-750.

28.

Hsu

. Segmentation-based compression: new frontiers of telemedicine in telecommunication. Telematics and Informatics. 2015; 32(3): 475-485.

29.

Hwang

Lin

. Fuzzy channel-optimized vector quantization. IEEE Communication Letters. 2000; 4(12): 408-410.

30.

Hwang

Yeh

. Genetic channel-optimized vector quantizer design for burst error channels. Neurocomputing. 2005; 63: 345-357.

31.

Kar

. Bio inspired computing – A review of algorithms and scope of applications. Expert Systems with Applications. 2016; 29: 20-32.

32.

Karri

Jena

. Fast vector quantization using a bat algorithm for image compression. Engineering Science and Technology, an International Journal. 2016; 19(2): 769-781.

33.

Kieu

Ramroach

. A reversible steganographic scheme for VQ indices based on joint neighboring coding. Expert Systems with Applications. 2015; 42(2): 713-722.

34.

Knagenhjelm

Agrell

. The Hadamard transform – A tool for index assignment. IEEE Transactions on Information Theory. 1996; 42(4): 1139-1151.

35.

Krasnogor

Smith

. A tutorial for competent memetic algorithms: Model, taxonomy, and design issues. IEEE Transactions on Evolutionary Computation. 2005; 9(5): 474-488.

36.

Lee

Chen

. Fast closest codeword search algorithms for vector quantisation. IEE Proceedings – Vision, Image and Signal Processing. 1994; 141(3): 143-148.

37.

Leitão

HAS

Lopes

WTA

Madeiro

. PSO algorithm applied to codebook design for channel-optimized vector quantization. IEEE Latin America Transactions. 2015; 13(4): 961-967.

38.

Liao

Wang

Zhou

. A novel optimizer based on particle swarm optimizer and LBG for vector quantization in image coding. In 3rd IEEE International Conference on Natural Computation (ICNC). 2007; 3: 416-420.

39.

Linde

Buzo

Gray

. An algorithm for vector quantizer design. IEEE Transactions on Communications. 1980; 28(1): 84-95.

40.

Sun

. Equal-average equal-variance equal-norm nearest neighbor search algorithm for vector quantization. IEICE Transactions on Information and Systems. 2003; 86(3): 660-663.

41.

Mishra

Agarwal

Sharma

Bedi

. Optimized gray-scale image watermarking using DWT-SVD and firefly algorithm. Expert Systems with Applications. 2014; 41(17): 7858-7867.

42.

Mohammed

Minhas

QMJ

Sid-Ahmed

. An efficient fingerprint image compression technique based on wave atoms decomposition and multistage vector quantization. Integrated Computer-Aided Engineering. 2010; 17(1): 29-40.

43.

Neto

ARR

Barreto

. Opposite maps: Vector quantization algorithms for building reduced-set SVM and LSSVM classifiers. Neural Processing Letters. 2013; 37(1): 3-19.

44.

Pan

Huang

. A new vector quantization image coding algorithm based on the extension of the bound for Minkowski metric. Pattern Recognition. 1998; 31(11): 1757-1760.

45.

Perng

Lin

Hsu

. Multi-sensor fusion in safety monitoring systems at intersections. In IEEE International Conference on Systems, Man and Cybernetics (SMC). 2014; 2131-2137.

46.

Ping-Yi

Tsai

Chou

Shi

Chen

. Improved PSO-LBG to design VQ codebook. In Proceedings of Society of Instrument and Control Engineers (SICE) Annual Conference. 2013; 876-879.

47.

Queiroz

WJL

Lopes

WTA

Madeiro

Alencar

. An alternative method to compute the bit error probability of modulation schemes subject to Nakagami-m fading. EURASIP Journal on Advances in Signal Processing (Print). 2010; 1-12.

48.

Queiroz

WJL

Madeiro

Lopes

WTA

Alencar

. Error probability of multichannel reception with theta-QAM scheme under correlated Nakagami-m fading. Journal of Communication and Information Systems (Online). 2014; 29: 37-45.

49.

Queiroz

WJL

Madeiro

Lopes

WTA

Alencar

. Performance analysis of generalized QAM modulation under eta-mu and kappa-mu fading. EURASIP Journal on Advances in Signal Processing (Online). 2013; 2013(1): 1-10.

50.

Kim

. A fast mean-distance-ordered partial codebook search algorithm for image vector quantization. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing. 1993; 40(9): 576-579.

51.

Serapião

Corrêa

Gonçalves

Carvalho

. Combining K-Means and K-Harmonic with fish school search algorithm for data clustering task on graphics processing units. Applied Soft Computing. 2016; 41: 290-304.

52.

Shabbir

Omenzetter

. Particle swarm optimization with sequential niche technique for dynamic finite element model updating. Computer-Aided Civil and Infrastructure Engineering. 2015; 30(5): 359-375.

53.

Shahidi

Alajaji

Linder

. Exploiting memory and soft-decision information in channel optimized quantization for correlated fading channels. In 12th Canadian Workshop on Information Theory (CWIT). 2011: 66-69.

54.

Tsai

Tseng

Yang

Chiang

. PREACO: A fast ant colony optimization for codebook generation. Applied Soft Computing. 2013; 13(6): 3008-3020.

55.

Veroneze

, de França

, Zuben

. Assessing the performance of a swarm-based biclustering technique for data imputation. In IEEE Congress of Evolutionary Computation (CEC). 2011; 386-393.

56.

Yang

X-S

Deb

Fong

Zhao

. From swarm intelligence to metaheuristics: nature-inspired optimization algorithms. Computer. 2016; 49(9): 52-59.

57.

Yang

X-S

. A new metaheuristic bat-inspired algorithm. In Nature Inspired Cooperative Strategies for Optimization (NICSO 2010). Studies in Computational Intelligence. Berlin: Springer. 2010; 284: 65-74.

58.

Yang

X-S

. Firefly algorithm, stochastic test functions and design optimization. International Journal of Bio-Inspired Computation. 2010; 2(2): 78-84.

59.

Yang

X-S

. Firefly algorithms for multimodal optimization. Stochastic Algorithms: Foundations and Applications. 2009; 5792: 169-178.

60.

Yang

X-S

. Nature-Inspired Metaheuristic Algorithms. United Kingdom: Luniver Press; 2008.

61.

Zeger

Gersho

. Pseudo-gray coding. IEEE Transactions on Communications. 1990; 38(12): 2147-2157.

Hybrid firefly-Linde-Buzo-Gray algorithm for Channel-Optimized Vector Quantization codebook design

Abstract

Keywords

1. Introduction

6.1 Efficient nearest neighbor search techniques

Table 2 PSNR ¯ final results achieved by different codebook design methods after transmission over a BSC for ε = 0.005 and ε = 0.010. The highest values for each combination of ε , N and image are in bold

Footnotes

Acknowledgments

References

Table 2
$\mathrm{\overline{PSNR}_{final}}$ results achieved by different codebook design methods after transmission over a BSC for $\varepsilon=$ 0.005 and $\varepsilon=$ 0.010. The highest values for each combination of $\varepsilon$ , $N$ and image are in bold