40-76-1-SM.zip_40_SM-PSO_imageoptimization_psoinimage

共1个文件

pdf：1个

版权申诉

swarm

104 浏览量 2022-09-23 17:31:09 上传评论收藏 176KB ZIP 举报

资源推荐

资源详情

资源评论

收起资源包目录

40-76-1-SM.zip （1个子文件）

40-76-1-SM.pdf 191KB

Informatica 29 (2005) 261–269 261

A Color Image Quantization Algorithm Based on Particle Swarm

Optimization

Mahamed G. Omran and Andries P. Engelbrecht

Department of Computer Science

University of Pretoria

Pretoria 0002, SOUTH AFRICA

E-mail: mjomran@engineer.com, [email protected]

Ayed Salman

Department of Computer Engineering

Kuwait University

KUWAIT

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

E-mail: [email protected]

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

quantization approaches, pre-clustering quantization approaches

Received: February 6, 2005

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 osnovi jate ptičev je uporabljen za barvno obdelavo slik.

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 colors where

ℜ⊂

′

S and N

the dimension of the data space. The color quantization is

a map

S S

′′

→

′

where S

′′

is a set of

′′

N colors

such that

′

⊂

′′

and

′′′

< NN . The objective is to

minimize the quantization error resulting from replacing

a color

′

∈ with its quantized value Sc

′

∈

)(

f .

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

printing 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

) 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

differencebetween 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

262 Informatica 29 (2005) 261–269 M.G. Omran et al.

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

clustering heuristics and suggested some optimizations of

the algorithms and data structures used. Furthermore,

they proposed a new color space called H

and

argued that it improves the quantization heuristics.

Finally, they proposed a new method which divides each

A COLOR IMAGE QUANTIZATION ALGORITHM... Informatica 29 (2005) 261–269 263

cluster along the axis H

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

divides 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

MSE

∑∑

=∈∀

)(

m -z

(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 ±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

评论收藏

内容反馈

版权申诉

朱moyimi

粉丝: 64
资源: 1万+

40-76-1-SM.zip_40_SM-PSO_image optimization_pso in image_swarm

最新资源

40-76-1-SM.zip_40_SM-PSO_image optimization_pso in image_swarm

PSO.zip_PSO_pso matlab_pso swarm_swarm

PSO算法IGPSOexe.zip_PSO_PSO algorithm_pso算法_swarm-optimization_模式识

Particle-Swarm-Optimization-MPPT.zip_MPPT PSO_mppt_optimization

PSO.rar_PSO_pso code_pso swarm_swarm

pso.rar_PSO_PSO algorithm_PSO.m_swarm

PSO_proj.zip_optimization_swarm_zip

tunning-PID-by-PSO.rar_PID tunning_PSO_pid pso_swarm_tunning pid

PSO.rar_PSO_optimization_swarm

PSO.zip_optimization_swarm_zip

pso.zip_optimization_swarm_zip

ga_pso.rar_PSO_pso ga_pso-ga_swarm_遗传粒子群

DMS_PSO.zip_On Strategy_algorithm_dms_dms-pso_dynamic pso

PSO-svm.rar_ svm pso_PSO_pso svm_svm pso matlab_swarm

psopid.zip_PID-PSO simulink_PSO PID_particle swarm_pid simulin

exp_code_1.zip_PSO_pso算法_swarm_粒子群 路径_路径跟踪

mat-pso-localization-master.zip_Localization pso_SWARM WSN_pso

pso.zip_PSO粒子群_kennedy_pso swarm_pso粒子_并行PSO

PSO.rar_matlab optimization_optimization_swarm

PSO.zip_On Strategy_algorithm_article_cec2013_pso dynamic

冰河的渗透实战笔记-冰河.pdf

大灰狼远控2021最新版，解压密码222

J-LINK V10 V11固件.rar

ISO21434.pdf

Web安全漏洞扫描工具-AWVS14

stm32f103 adc采样+dma传输+fft处理 频率计_fft处理_stm32_ADCFFT_频率计_ADC采样_

CTF 竞赛入门指南（ctf-all-in-one）.pdf

Web中间件常见漏洞总结.pdf

jts-1.14.zip

CobaltStrike4.4.zip

最新资源

exp_code_1.zip_PSO_pso算法_swarm_粒子群路径_路径跟踪

stm32f103 adc采样+dma传输+fft处理频率计_fft处理_stm32_ADCFFT_频率计_ADC采样_