Printer Friendly

A color image quantization algorithm based on Particle Swarm Optimization.

A color image quantization algorithm based on Particle Swarm Optimization (PSO) is developed in this paper. PSO is a population-based optimization algorithm modeled after the simulation of social behavior of bird flocks and follows similar steps as evolutionary algorithms to find near-optimal solutions. The proposed algorithm randomly initializes each particle in the swarm to contain K centroids (i.e. color triplets). The K-means clustering algorithm is then applied to each particle at a user-specified probability to refine the chosen centroids. Each pixel is then assigned to the cluster with the closest centroid. The PSO is then applied to refine the centroids obtained from the K-means algorithm, The proposed algorithm is then applied to commonly used images. It is shown from the conducted experiments that the proposed algorithm generally results in a significant improvement of image quality compared to other well-known approaches. The influence of different values of the algorithm control parameters is studied. Furthermore, the performance of different versions of PSO is also investigated.

Povzetek: Evolucijski algoritem na osnovijate pticev je uporabljen za barvno obdelavo slik.

Keywords: Color image quantization, K-means clustering algorithm, particle swarm optimization, post-clustering quantization approaches, pre-clustering quantization approaches

1 Introduction

Color image quantization is the process of reducing the number of colors presented in a digital color image [2]. Color image quantization can be formally defined as follows [27]:

Given a set of [N.sub.s'], colors where S' [subset] [R.sup.N.sub.d]] and [N.sub.d] is the dimension of the data space. The color quantization is a map [f.sub.q] : S' [right arrow] S" where S" is a set of [N.sub.s"] colors such that S" [subset] S' and [N.sub.s"] < [N.sub.s']. The objective is to minimize the quantization error resulting from replacing a color c [epsilon] S' with its quantized value [f.sub.q] (c) [epsilon] S". Color image quantization is an important problem in the fields of image processing and computer graphics [27]:

* It can be used in lossy compression techniques [27];

* It is suitable for mobile and hand-held devices where memory is usually small [18];

* It is suitable for low-cost color display and priming devices where only a small number of colors can be displayed or printed simultaneously [20].

* Most graphics hardware use color lookup tables with a limited number of colors [8].

Color image quantization consists of two major steps:

* Creating a colormap (or palette) where a small set of colors (typically 8-256 [20]) is chosen from the ([2.sup.24]) possible combinations of red, green and blue (RGB).

* Mapping each color pixel in the color image to one of the colors in the colormap.

Therefore, the main objective of color image quantization is to map the set of colors in the original color image to a much smaller set of colors in the quantized image [32]. Furthermore, this mapping, as already mentioned, should minimize the difference between the original and the quantized images [8]. The color quantization problem is known to be NP-complete [30]. This means that it is not feasible to find the global optimal solution because this will require a prohibitive amount of time. To address this problem, several approximation techniques have been used. One popular approximation method is the use of a standard local search strategy such as K-means. K-means has already been applied to the color image quantization problem [22], [3]. However, K-means is a greedy algorithm which depends on the initial conditions, which may cause the algorithm to converge to suboptimal solutions. This drawback is magnified by the fact that the distribution of local optima is expected to be broad in the color image quantization problem due to the three dimensional color space. In addition, this local optimality is expected to affect the visual image quality. The local optimality issue can be addressed by using stochastic optimization schemes.

In this paper, a new color image quantization algorithm based on Particle Swarm Optimization (PSO) is proposed. PSO is a population-based stochastic optimization algorithm modeled after the simulation of the social behavior of bird flocks and follows similar steps as evolutionary algorithms to find near-optimal solutions. PSO and other evolutionary algorithms that depend on heuristics to find 'soft' solutions are considered to be soft computing algorithms. This population-based search approach reduces the effect of the initial conditions, compared to K-means (especially if the size of the population is relatively large). The feasibility of the approach is demonstrated by applying it to commonly used images. The results show that, in general, the proposed approach performs better than state-of-the-art color image quantization approaches.

The rest of the paper is organized as follows. Section 2 surveys related work in the field of color image quantization. An overview of PSO is shown in section 3. The proposed algorithm is presented in section 4, while an experimental evaluation of the algorithm is provided in section 5. Finally, section 6 concludes the paper and provides guidelines for future research.

2 Related Work

Several heuristic techniques for color image quantization have been proposed in the literature. These techniques can be categorized into two main categories: pre-clustering and post-clustering. The next subsections discuss each of these categories.

2.1 Pre-clustering approaches

Pre-clustering approaches divide the color into disjoint regions of similar colors. A representative color is then determined from each region. These representatives form the colormap. There are many fast algorithms in this category which are commonly used.

The median cut algorithm (MCA) [10] is often used in image applications because of its simplicity [8]. MCA divides the color space repeatedly along the median into rectangular boxes until the desired number of colors is obtained.

The variance-based algorithm (VBA) [28] also divides the color space into rectangular boxes. However, in VBA the box with the largest mean squared error between the colors in the box and their mean is split.

The octree quantization algorithm [9] repeatedly subdivides a cube into eight smaller cubes in a tree structure of degree eight. Then adjacent cubes with the least number of pixels are merged. This is repeated until the required number of colors is obtained [5]. Octree produces results similar to MCA, but with higher speed and smaller memory requirements [8].

Xiang and Joy [32] proposed an agglomerative clustering method which starts with each image color as a separate cluster. Small clusters are then repeatedly clustered into larger clusters in a hierarchical way until the required number of colors is obtained. The abandoning of the fixed hierarchical division of the color space is a significant improvement over the octree approach [32].

A similar approach called Color Image Quantization by Pairwise Clustering was proposed by [27]. In this approach, a relatively large set of colors is chosen. An image histogram is then created. Two clusters that minimize the quantization error are then selected and merged together. This process is repeated until the required number of colors is obtained. According to [27], this approach performed better than MCA, VBA, octree, K-means and other popular quantization algorithms when applied to the two colored images used in their experiments.

Xiang [31] proposed a color image quantization algorithm that minimizes the maximum distance between color pixels in each cluster (i.e. the intra-cluster distance). The algorithm starts by assigning all the pixels into one cluster. A pixel is then randomly chosen as the head of the cluster. A pixel that is the most distant from its cluster head is chosen as the head of a new cluster. Then, pixels nearer to the head of the new cluster move towards the new head forming the new cluster. This procedure is repeated until the desired number of clusters is obtained. The set of cluster heads forms the colormap.

A hybrid competitive learning (HCL) approach combining competitive learning and splitting of the color space was proposed by [19]. HCL starts by randomly choosing a pixel as a cluster centroid. Competitive learning is then applied resulting in assigning all the image pixels to one cluster surrounding the centroid. A splitting process is then conducted by creating another copy of the centroid, competitive learning is then applied on both centroids. This process is repeated until the desired number of clusters is obtained. According to [19], HCL is fast, completely independent of initial conditions and can obtain near global optimal results. When applied to commonly used images, HCL outperformed MCA, VBA and K-means, and performed comparably with competitive learning [19], [20].

Braquelaire and Brun [2] compared the various preclustering heuristics and suggested some optimizations of the algorithms and data structures used. Furthermore, they proposed a new color space called [H.sub.1] [H.sub.2] [H.sub.3] and argued that it improves the quantization heuristics. Finally, they proposed a new method which divides each cluster along the axis [H.sub.1], [H.sub.2] or [H.sub.3] of greatest variance. According to [2], the proposed approach generates images with comparable quality to that obtained from better but slower methods in this category. Recently, Cheng and Yang [4] proposed a color image quantization algorithm based on color space dimensionality reduction. The algorithm repeatedly subdivides the color histogram into smaller classes. The colors of each class are projected into a line. This line is defined by the mean color vector and the most distant color from the mean color. For each class, the vector generated from projection is then used to cluster the colors into two representative palette colors. This process is repeated until the desired number of representative colors is obtained. All color vectors in each class are then represented by their class mean. Finally, all these representative colors form the colormap. According to [4], this algorithm performed better than MCA, and performed comparably to SOM when applied on commonly used images.

2.2 Post-clustering approaches

The main disadvantage of the pre-clustering approaches is that they only work with color spaces of simple geometric characteristics. On the other hand, post-clustering approaches can work with arbitrary shaped clusters. Post-clustering approaches perform clustering of the color space [4]. A post-clustering algorithm starts with an initial colormap. It then iteratively modifies the colormap to improve the approximation. The major disadvantage of post-clustering algorithms is the fact that it is time consuming [8].

The K-means algorithm is one of the most popular post-clustering algorithms. It starts with an initial set of colors (i.e. initial colormap). Then, each color pixel is assigned to the closest color in the colormap. The colors in the colormap are then recomputed as the centroids of the resulting clusters. This process is repeated until convergence. The K-means algorithm has been proven to converge to a local optimum [8]. As previously mentioned, a major disadvantage of K-means is its dependency on initial conditions.

FCM [1] and Learning Vector Quantization [16] have also been used for color image quantization. Scheunders and De Backer [21] proposed a joint approach using both competitive learning and a dithering process to overcome the problem of contouring effects when using small colormaps.

Fiume and Quellette [7] proposed an approach which uses simulated annealing for color image segmentation. Pre-clustering approaches were used to initialize the colormap.

Self-Organizing Maps (SOMs) [15] were used by [5] to quantize color images. The approach selects an initial colormap, and then modifies the colors in the colormap by moving them in the direction of the image color pixels. However, to reduce the execution time, only samples of the colors in the image are used. According to [5], the algorithm performs better than MCA and octree. Rui et al. [18] presented an initialization and training method for SOM that reduces the computational load of SOM and at the same time generates reasonably good results.

A hybrid approach combining evolutionary algorithms with K-means has been proposed by [8]. A population of individuals, each representing a colormap, are arbitrary initialized. Then, after each generation, the K-means algorithm (using a few iterations) is applied on each individual in the population. The standard error function of the Euclidean distance is chosen to be the fitness function of each individual. Based on the experiments conducted by [8], this hybrid approach outperformed both MCA and octree algorithms.

The Genetic C-means algorithm (GCMA) uses a similar idea where a hybrid approach combining a genetic algorithm with K-means was proposed by [20]. The fitness function of each individual in the population is set to be the mean square error (MSE), defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1)

As in [8], each chromosome represents a colormap. GCMA starts with a population of arbitrary initialized chromosomes. K-means is then applied to all the chromosomes to reduce the search space. A single-point crossover is then applied. This is followed by the application of mutation which randomly decides if a value of one is added to (or subtracted from) the gene's value (i.e. mutating the gene's value with [+ or -]1). All the chromosomes are then pairwise compared and the chromosome with the lowest MSE replaces the other chromosome. This process is repeated until a stopping criterion is satisfied. A faster version of this approach can be obtained by applying K-means to the best chromosome in each generation. For the remaining chromosomes, an approximation of K-means is used where a single iteration of K-means is applied on a randomly chosen subset of pixels. This process is repeated a user-specified number of times using different subsets. GCMA outperformed MCA, VBA, K-means, competitive learning and HCL when applied on commonly used images [19], [20]. However, GCMA is computationally expensive.

3 Particle Swarm Optimization

Particle swarm optimizers are population-based optimization algorithms modeled after the simulation of social behavior of bird flocks [12], [13]. PSO is generally considered to be an evolutionary computation (EC) paradigm. Other EC paradigms include genetic algorithms (GA), genetic programming (GP), evolutionary strategies (ES), and evolutionary programming (EP) [6]. These approaches simulate biological evolution and are population-based. In a PSO system, a swarm of individuals (called particles) fly through the search space. Each particle represents a candidate solution to the optimization problem. The position of a particle is influenced by the best position visited by itself (i.e. its own experience) and the position of the best particle in its neighborhood (i.e. the experience of neighboring particles). When the neighborhood of a particle is the entire swarm, the best position in the neighborhood is referred to as the global best particle, and the resulting algorithm is referred to as the gbest PSO. When smaller neighborhoods are used, the algorithm is generally referred to as the lbest PSO [24]. The performance of each particle (i.e. how close the particle is to the global optimum) is measured using a fitness function that varies depending on the optimization problem.

Each particle in the swarm is represented by the following characteristics:

[x.sub.i]: The current position of the particle;

[v.sub.i]: The current velocity of the particle;

[Y.sub.i]: The personal best position of the particle.

The personal best position of particle i is the best position (i.e. one resulting in the best fitness value) visited by particle i so far. Let f denote the objective function. Then the personal best of a particle at time step t is updated as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (2)

If the position of the global best particle is denoted by the vector y, then

y(t)[epsilon] {[y.sub.0],[y.sub.1], ... ,[y.sub.5]} = min {f([y.sub.0](t)), f([y.sub.s](t))} (3)

where s denotes the size of the swarm. For the lbest model, a swarm is divided into overlapping neighborhoods of particles. For each neighborhood [N.sub.j], a best particle is determined with position [y.sub.j]. This particle is referred to as the neighborhood best particle, defined as

[y.sub.j](t+1) [epsilon]{[N.sub.j]|f([y.sub.j](t+1))=min {f([y.sub.i](t))}, [for all][y.sub.i] [epsilon][N.sub.j] (4)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (4)

Neighborhoods are usually determined using particle indices [25], however, topological neighborhoods can also be used [23]. It is clear that gbest is a special case of lbest with l = s; that is, the neighborhood is the entire swarm. While the lbest approach results in a larger diversity, it is still slower than the gbest approach.

For each iteration of a PSO algorithm, the velocity [v.sub.i] update step is specified for each dimension j [epsilon] 1, ... , [N.sub.d], where [N.sub.d] is the dimension of the problem. Hence, [v.sub.ij], represents the [j.sup.th] element of the velocity vector of the [i.sup.th] particle. Thus the velocity of particle i is updated using the following equation:

[v.sub.i,j](t+1)=[wv.sub.i,j](t)+[c.sub.1][r.sub.1,j](t) ([y.sub.i,j](t)=[x.sub.i,j](t))+[c.sub.r][r.sub.2,j](t)(y.sub.j](t)) (6)

where w is the inertia weight [23], [c.sub.1] and [c.sub.2] are the acceleration constants and [r.sub.1,j], [r.sub.2,j] ~ U(0,1). Eq. 6 consists of three components, namely

* The inertia weight term, w, which serves as a memory of previous velocities. The inertia weight controls the impact of the previous velocity: a large inertia weight favors exploration, while a small inertia weight favors exploitation [24].

* The cognitive component, [y.sub.i] (t)--[x.sub.i], which represents the particle's own experience as to where the best solution is.

* The social component, y(t)--[x.sub.i] (t), which represents the belief of the entire swarm as to where the best solution is. Different social structures have been investigated [11], [14], with the star topology being used most.

The position of particle i, [x.sub.i], is then updated using the following equation:

[x.sub.i] (t + 1) = [x.sub.i] (t) + [v.sub.i] (t + 1) (7)

The reader is referred to [26] and [17] for a study of the relationship between the inertia weight and acceleration constants, in order to select values which will ensure convergent behavior. Velocity updates can also be clamped through a user defined maximum velocity, [V.sub.max], which would prevent them from exploding, thereby causing premature convergence [26].

The PSO algorithm performs the update equations above, repeatedly, until a specified number of iterations have been exceeded, or velocity updates are close to zero. The quality of particles is measured using a fitness function which reflects the optimality of a particular solution.

4 The PSO-based Color Image Quantization (PSO-CIQ) Algorithm

This section defines the terminology used throughout this paper. A measure is given to quantify the quality of the resultant quantized image, after which the PSO-CIQ algorithm is introduced.

Define the following symbols:

*[N.sub.p] denotes the number of image pixels

* K denotes the number of clusters (i.e. colors in the colormap)

* [Z.sub.p] denotes the coordinates of pixel p

* [m.sub.k] denotes the centroid of cluster k (representing one color triple in the colormap)

In this paper, the terms centroid and color triplet arc used interchangeably.

4.1 Measure of Quality

The most general measure of performance is the mean square error (MSE) of the quantized image using a specific colormap. The MSE was defined in Eq. 1, and is repeated here for convenience:

[MATHEMATICAL EXPRESSION NOR REPRODUCIBLE IN ASCII.] (8)

where [C.sub.k] is the [k.sup.th] cluster.

4.2 The PSO-CIQ Algorithm

In this section, a new post-clustering color image quantization approach is described. The proposed approach is of the class of quantization techniques that performs clustering of the color space.

In the context of color image quantization, a single particle represents a colormap (i.e. a particle consists of K cluster centroids representing RGB color triplets). The RGB coordinates in each color triple are floating-point numbers. Each particle [x.sup.i] is constructed as [x.sup.i] = ([m.sub.i,1 ... , [m.sub.i,k], ... ,[m.sub.i,K]) where [m.sub.i,k] refers to the [k.sup.th] cluster centroid vector of the [i.sup.th] particle. Therefore, a swarm represents a number of candidate colormaps. The quality of each particle is measured using the MSE (defined in Eq. 8) as follows:

f ([x.sub.i]) = MSE([x.sub.i]) (9)

The algorithm initializes each particle randomly from the color image to contain K centroids (i.e. color triplets). The set of K color triplets represents the colormap. The K-means clustering algorithm is then applied to each particle at a user-specified probability, [P.sub.kmeans]. The K-means algorithm is used in order to refine the chosen colors and to reduce the search space. Each pixel is then assigned to the cluster with the closest centroid. The fitness function of each particle is calculated using Eq. 9. The PSO velocity and update Eq.'s 6 and 7 are then applied. The procedure is repeated until a stopping criterion is satisfied. The colormap of the global best particle after [t.sub.max] iterations is chosen as the optimal result.

The PSO-CIQ algorithm is summarized below:

1. Initialize each particle by randomly choosing K color triplets from the image.

2. For t = 1 to [t.sub.max]

(a) For each particle i

i. Apply K-means for a few iterations with a probability [P.sub.kmeans].

ii. For each pixel [Z.sub.p]

Calculate [d.sup.2] ([Z.sub.p--[m.sub.i,k]) for all clusters [C.sub.i,k].

Assign [z.sub.p] to [C.sub.i,kk] where

[d.sup.2]([Z.sub.p]-[m.sub.i,kk]): min {[d.sup.]2 ([Z.sub.p]--[m.sub.i,k])} [for all] k = 1, ... ,K

iii. Calculate the fitness, f([x.sub.i])

(b) Find the global best solution y(t)

(c) Update the centroids using Eq.'s 6 and 7

In general, the complexity of the PSO-CIQ algorithm is O(sK[t.sub.max][N.sub.p]). The parameters s, K and [t.sub.max] can be fixed in advance. Typically s, K and [t.sub.max] << [N.sub.p]. Therefore, the time complexity of PSO-CIQ is O([N.sub.p]). Hence, in general the algorithm has linear time complexity in the size of a data set.

5 Experimental Results

The PSO-CIQ algorithm was applied to a set of four commonly used color images namely: Lenna (shown in Figure 1 (a)), peppers, jet and mandrill. The size of each image is 512 x 512 pixels. All images are quantized to 16, 32 and 64 colors.

[FIGURE 1 OMITTED]

The rest of this section is organized as follows: Section 5.1 illustrates that the PSO-CIQ can be used successfully as a color image quantization algorithm by comparing it to other well-known color image quantization approaches. Section 5.2 investigates the influence of the different PSO-CIQ control parameters. Finally, the use of different PSO models (namely, gbest, lbest and lbest-to-gbest) are investigated in section 5.3.

The results reported in this section are averages and standard deviations over 10 simulations. An lbest PSO is used (unless otherwise specified) with an initial neighborhood of zero (considering the particle on its own) which linearly increased to a gbest implementation. This approach is referred to as lbest-to-gbest-PSO. This hybrid approach is used in order to initially avoid being trapped in local optima, by focusing on exploration [25]. The algorithm then attempts to converge to the best solution found by the initial phase by using a gbest approach. The PSO-CIQ parameters were initially set as follows: pkmeans = 0.1, s = 20, tmax = 50, number of Kmeans iterations is 10 (the effect of these values are then investigated), w =0.72, [c.sub.1] = [c.sub.2] = 1.49 and [V.sub.max] = 255 for all the test images. These parameters were used in this section unless otherwise specified. For the SOM, a Kohonen network of 4x4 nodes was used when quantizing an image to 16 colors, a Kohonen network of 8x8 nodes was used when quantizing an image to 32 colors, and a Kohonen network of 8x8 nodes was used when quantizing an image to 64 colors. All SOM parameters were set as in Pandya and Macy [17]: the

learning rate [eta](t) was initially set to 0.9 then decreased by 0.005 until it reached 0.005, the neighborhood function [[DELTA].sub.w] w(t) was initially set to (4+4)/4 for 16 colors, (8+4)/4 for 32 colors, and (8+8)/4 for 64 colors. The neighborhood function is then decreased by 1 until it reached zero.

5.1 PSO-CIQ vs. Well-Known Color Image Quantization Algorithms

This section presents results to compare the performance of the PSO-CIQ algorithm with that of SOM and GCMA for each of the test images.

Table 1 summarizes the results for the four images. The results of the GCMA represent the best case over several runs and are copied from [20]. The results are compared based on the MSE measure (defined in Eq. 8). The results showed that, in general, PSO-CIQ outperformed GCMA in all the test images except for the mandrill image and the case of quantizing the Jet image to 64 colors. Furthermore, PSO-CIQ generally performed better than SOM for both Lenna and peppers images. SOM and PSO-CIQ performed comparably when applied to the mandrill image. SOM generally performed better than PSO-CIQ when applied to the Jet image. Figure 1 show the visual quality of the quantized image generated by PSO-CIQ when applied to Lenna.

5.2 Influence of PSO-CIQ Parameters

The PSO-CIQ algorithm has a number of parameters that have an influence on the performance of the algorithm. These parameters include [V.sub.max], the swarm size, the number of PSO iterations, [p.sub.kmeans] and the number of Kmeans iterations. This section investigates the influence of different values of these parameters using the Lenna image when quantized to 16 colors.

5.2.1 Velocity Clamping

Table 2 shows that using [V.sub.max] : 5 or [V.sub.max] = 255 generally produces comparable results.

5.2.2 Swarm Size

Increasing the swarm size from 20 to 50 particles slightly improves the performance of the PSO-CIQ algorithm as shown in Table 3. Similarly, increasing the swarm size from 50 to 100 particles slightly improves the performance of the PSO-CIQ algorithm. On the other hand, reducing the swarm size from 20 to 10 particles significantly reduces the efficiency of the PSO-CIQ algorithm. The rationale behind these results is that increasing the number of particles increases diversity, thereby limiting the effects of initial conditions and reducing the possibility of being trapped in local minima.

5.2.3 Number of PSO iterations

Increasing the number of PSO iterations, [t.sub.max], from 50 to 100 slightly improves the performance of the PSO-CIQ algorithm as shown in Table 4. Similarly, increasing [t.sub.max] from 100 to 150 slightly improves the performance of the PSO-CIQ algorithm. Therefore, it can be concluded that increasing [t.sub.max] generally improves the performance of the PSO-CIQ algorithm.

5.2.4 [P.sub.kmeans]

Applying the K-means clustering algorithm to a larger set of particles is expected to improve the performance of the PSO-CIQ algorithm. The rationale behind this expectation is the fact that the K-means algorithm generally reduces the search space and refines the chosen colors. This expectation is verified by the results shown in Table 5 which shows that increasing the value of [P.sub.kmeans] generally improves the performance of the PSO-CIQ algorithm. However, as a trade-off, increasing the value of [p.sub.kmeans] will increase the computational requirements of the PSO-CIQ algorithm.

5.3 Number of K-means iterations

Reducing number of K-means iterations from 10 to 5 degrades the performance of the PSO-CIQ as shown in Table 6. On the other hand, increasing the number of K-means iterations from l0 to 50 significantly improves the performance of the PSO-CIQ as shown in Table 6. These results suggest that increasing the number of K-means iterations improves the performance of the PSO-CIQ. However, when the number of K-means iterations was reduced to 5 iterations but at the same time [P.sub.kmeans] was increased from 0.1 to 0.5 the generated MSE was equal to 210.315 [+ or -] 1.563 which is significantly better than the corresponding result in Table 6. This result suggests that the number of K-means iterations can be reduced without affecting the performance of PSO-CIQ given that the [P.sub.kmeasn] is increased.

5.4 Comparison of gbest-, lbest- and lbest-to-gbest-PSO

In this section, the effect of different models of PSO is investigated using the Lenna image when quantized to 16 colors. A comparison is made between gbest-, lbest- and lbest-to-gbest-PSO (which has been used in the above experiments) using a swarm size of 20 particles. For lbest-PSO, a neighborhood size of l = 2 was used. Table 7 shows the result of the comparison. The results show no significant difference in performance.

6 Conclusion

This paper presented a PSO-based color image quantization algorithm (PSO-CIQ). The PSO-CIQ algorithm was compared against other well-known color image quantization techniques. In general, the PSO-CIQ performed better than the other techniques when applied to a set of commonly used images. The effects of different PSO-CIQ control parameters were studied. The performance of different versions of PSO was then investigated.

The PSO-CIQ uses the K-means clustering algorithm to refine the color triplets. Future research can investigate the use of other more efficient clustering algorithms such as FCM and KHM [33]. Finally, the PSO-CIQ uses the RGB color space. Although the RGB model is the most widely used model, it has some weaknesses. One of these weaknesses is that equal distances in the RGB color space may not correspond to equal distance in color perception. Hence, future research may try to apply the PSO-CIQ to other color spaces (e.g. the L*u*v* color space [29]).

References

[1] Balasubramanian R, Allebach J (1990) A new approach to platte selection for color images, Image Technology 17: 284-290.

[2] Braquelaire J, Brun L (1997) Comparison and optimization of methods of color image quantization, IEEE Transactions on Image Processing 6(7): 1048-1052.

[3] Celenk M (1990) A color clustering technique for image segmentation, computer vision, Graphics and Image Processing 52:145-170.

[4] Cheng S, Yang C (2001) A fast and novel technique for color quantization using reduction of color space dimensionality, Pattern Recognition Letters 22: 845-856.

[5] Dekker A (1994) Kohonen neural networks for optimal colour quantization, Network: Computation in Neural Systems 5:351-367.

[6] Engelbrecht A (2002) Computational Intelligence: An Introduction, John Wiley and Sons.

[7] Fiume E, Quellette M (1989) On distributed, probabilistic algorithms for computer graphics, Graphics Interface '89, 211-218.

[8] Freisleben B, Schrader A (1997) An evolutionary approach to color image quantization, Proceedings of IEEE International Conference on Evolutionary Computation, 459-464.

[9] Gervautz M, Purgathofer W (1990) A Simple Method for Color Quantization: Octree Quantization, Graphics Gems, Academic Press, New York.

[10] Heckbert P (1982) Color image quantization for frame buffer display, ACM Computer Graphics 16(3): 297-307.

[11] Kennedy J (1999) Small worlds and mega-minds: effects of neighborhood topology on particle swarm performance, Proceedings of the Congress on Evolutionary Computation, 1931-1938.

[12] Kennedy J, Eberhart R (1995) Particle swarm optimization, Proceedings of IEEE International Conference on Neural Networks, Perth, Australia 4:1942-1948.

[13] Kennedy J, Eberhart R (2001) Swarm Intelligence, Morgan Kaufmann.

[14] Kennedy J, Mendes R (2002) Population structure and particle performance, Proceedings of the IEEE Congress on Evolutionary Computation, Honolulu, Hawaii.

[15] Kohonen T (1989) Self-Organization and Associative Memory, 3rd edn. Springer-Verlag, Berlin.

[16] Kotropoulos C, Auge E, Pitas I (1992) Two-layer learning vector quantizer for color image quantization, In: Vandewalle J, Boite R, Moonen M, Oosterlinck A (eds) Signal Processing IV: Theories and Applications, 1177-1180.

[17] Pandya A, Macy R (1996) Pattern Recognition with Neural Networks in C++, CRC Press.

[18] Rui X, Chang C, Srikanthan T (2002) On the initialization and training methods for Kohonen self-organizing feature maps in color image quantization, Proceedings of the First IEEE International Workshop on Electronic Design, Test and Applications.

[19] Scheunders P (1997) A comparison of clustering algorithms applied to color image quantization, Pattern Recognition Letters 18(11-13): 1379-1384.

[20] Scheunders P (1997) A genetic C-means clustering algorithm applied to color image quantization, Pattern Recognition 30(6): 859-866.

[21] Scheunders P, De Backer S (1997) Joint quantization and error diffusion of color images using competitive learning, International Conference on Image Processing 1:811.

[22] Sharer S, Kanade T (1987) Color Vision, Encyclopedia of Artificial Intelligence, Wiley.

[23] Shi Y, Eberhart R (1998) A modified particle swarm optimizer, Proceedings of the IEEE International Conference on Evolutionary Computation, Piscataway, NJ, 69-73.

[24] Shi Y, Eberhart R (1998) Parameter selection in particle swarm optimization, Proceedings of Evolutionary Programming 98, 591-600.

[25] Suganthan P (1999) Particle swarm optimizer with neighborhood optimizer, Proceedings of the Congress on Evolutionary Computation, 19581962.

[26] Van den Bergh F (2002) An analysis of particle swarm optimizers, Ph.D. dissertation, Department of Computer Science, University of Pretoria.

[27] Velho L, Gomes J, Sobreiro M (1997) Color image quantization by pairwise clustering, Proceedings of the 10th Brazilian Symposium on Computer Graphics and Image Processing, 203-207.

[28] Wan S, Prusinkiewicz P, Wong S (1990) Variance-based color image quantization for frame buffer display, Color Research and Application 15(1): 5258.

[29] Watt A (1989) Three-Dimensional Computer Graphics, Addison-Wesley.

[30] Wu X, Zhang K (1991) A better tree-structured vector quantizer, Proceedings IEEE Data Compression Conference, 392-401.

[31] Xiang Z (1997) Color image quantization by minimizing the maximum inter-cluster distance, ACM Transactions on Graphics 16(3): 260-276.

[32] Xiang Z, Joy G (1994) Color image quantization by agglomerative clustering, IEEE Computer Graphics and Applications 14(3): 44-48.

[33] Zhang B (2000) Generalized K-Harmonic means-boosting in unsupervised learning, Technical Report HPL-2000-137, Hewlett-Packard Labs.

Mahamed G. Omran and Andries P. Engelbrecht

Department of Computer Science

University of Pretoria

Pretoria 0002, SOUTH AFRICA

E-mail: mjomran@engineer.com, engel@cs.up.ac.za

Ayed Salman

Department of Computer Engineering

Kuwait University

KUWAIT

Phone: +965-4811188-5833 Fax: +965-4817451

E-mail: ayed@eng.kuniv.edu.kw

Received: February 6, 2005
Table 1. Comparison between SOM, GCMA and PSO-CIQ

Image K SOM GCMA PSO-CIQ

Lenna 16 235.6 [+ or -] 332 210.203 [+ or -]
 0.49 1.487
 32 126.400 [+ or -] 179 119.167 [+ or -]
 1.200 0.449
 64 74.700 [+ or -] 113 77.846 [+ or -]
 0.458 16.132

Peppers 16 425.600 [+ or -] 471 399.63 [+ or -]
 13.162 2.636
 32 244.500 [+ or -] 263 232.046 [+ or -]
 3.854 2.295
 64 141.600 [+ or -] 148 137.322 [+ or -]
 0.917 3.376

Jet 16 121.700 [+ or -] 199 122.867 [+ or -]
 0.458 2.0837
 32 65.000 [+ or -] 96 71.564 [+ or -]
 0.000 6.089
 64 38.100 [+ or -] 54 56.339 [+ or -]
 0.539 11.15

Mandril 16 629.000 [+ or -] 606 630.975 [+ or -]
 1 0.775 2.059
 32 373.600 [+ or -] 348 375.933 [+ or -]
 0.490 3.42
 64 234.000 [+ or -] 213 237.331 [+ or -]
 0.000 2.015

Table 2. Effect of [V.sub.max] on the performance of PSO-CIQ
using Lenna image (16 colors)

 MSE

[V.sub.max]=5 209.338 [+ or -] 0.402
[V.sub.max]=255 210.203 [+ or -] 1.487

Table 3. Effect of the swarm size on the performance of
PSO-CIQ using Lenna image (16 colors)

 MSE

s = 10 212.196 [+ or -] 2.458
s = 20 210.203 [+ or -] 1.487
s = 50 210.06 [+ or -] 1.11
s = 100 209.468 [+ or -] 0.703

Table 4. Effect of the number of PSO iterations on the
performance of PSO-CIQ using, Lenna imatie (16 colors)

 MSE

[t.sub.max] = 50 210.203 [+ or -] 1.487
[t.sub.max] = 100 209.412 [+ or -] 0.531
[t.sub.max] = 150 208.866 [+ or -] 0.22

Table 5. Effect of [p.sub.kmeans] on the performance of PSO-CIQ
using Lenna image (16 colors)

 MSE

[p.sub.kmeans] = 0.1 210.203 [+ or -] 1.487
[p.sub.kmeans] = 0.25 209.238 [+ or -] 0.74
[p.sub.kmeans] = 0.5 209.045 [+ or -] 0.594
[p.sub.kmeans] = 0.9 208.886 [+ or -] 0.207

Table 6. Effect of the number of K-means iterations on the
performance of PSO-CIQ using Lenna image (16 colors)

No. of K-means iterations MSE

5 212.627 [+ or -] 3.7
10 210.203 [+ or -] 1.487
50 208.791 [+ or -] 0.111

Table 7. Comparison of gbest-, lbest- and lbest-to-gbest-PSO
versions of PSO-CIQ using Lenna imagre (16 colors)

 MSE

gbest PSO 209.841 [+ or -] 0.951
lbest PSO 210.366 [+ or -] 1.846
lbest-to-best PSO 210.203 [+ or -] 1.487
COPYRIGHT 2005 Slovenian Society Informatika
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2005 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Omran, Mahamed G.; Engelbrecht, Adries P.; Salman, Ayed
Publication:Informatica
Geographic Code:7KUWA
Date:Oct 1, 2005
Words:6130
Previous Article:Perception-oriented prominent region detection in video sequences.
Next Article:A hybird image retrieval system with user's relevance feedback using neurocomputing.
Topics:


Related Articles
ALGORITHM DEVELOPED FOR MINIMIZING CUMULATIVE TIME-BASE QUANTIZATION ERRORS.
Editorial: special issue on soft computing in multimedia processing.
A very low bit rate image compressor using transformed classified vector quantization.
Systems engineering using swarm particle optimisation.
Stopping criteria for a constrained single-objective particle swarm optimization algorithm.
Features selection of SVM and ANN using particle swarm optimization for power transformers incipient fault symptom diagnosis.
Solving engineering optimization problems with the simple constrained particle swarm optimizer.

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |