Abstract  Palette re ordering is a class of pre processing me thod with the objective to manipulate the palette index such that the adjacent symbols are assigned close indices in the symbol space, thus enhancing the compressibilit y of the image with many lossless compressors. Finding an exact reorder ed palette would certainly be exhaustive and computationally complex. A solution to this NP hard problem is presented by us ing an Adaptive Particle Swarm Optimization (APSO) to achieve fast global convergence by maximizing the co occurrences . A new algorithm with improved inertia factor is presented here to accelerate the convergence speed of the reindexing scheme. In this algorithm, the key parameter inertia weight is formulated as a factor of gradient based rate of particle conv ergence. Experimental results assert that the propo sed modification helps in improving APSO performance in terms of solution qua lity and convergence to global optima.   Key  words : Reindexing, palette indexed image, cross entropy, r ate of particle convergence (k), improved inertia weight adaptive particle swarm optimization.    Received April 3, 2013; accepted November10, 2014; published online March 19, 2015     1. Introduction  A  colour-mapped  (pseudo-colour)  image  is  composed  of  colour  information  contained  in  a  look-up  table  and  pixel  values  that  are  indices,  which  point  to  colou r  values  in  the  look-up  table.  In  most  computer  applications,  images  are  used  to  help  stimulate  hum an  visual  perception.  A  true  color  image  is  a  matrix  o f  pixels,  each  consisting  of  red,  green  and  blue  colo r  triplets.  Each  component  ( Ri,  Gi, Bi)  triplet  has  a  range  between  0  and  255  and  is  represented  with  a  byte.  Since,  a  color-mapped  image  utilises  approximately  one  third  of  memory  space  of  its  corresponding  true- colour  representation,  colour-mapped  images  are  use d  as  user  interface  elements  of  most  windowing  operating systems .  A  color-quantized  image  is  generally  represented  with  a  color  index  map  each  element  of  which  serves   as  an  index  to  select  a  color  from  a  predefined  set   of  colors  to  represent  the  color  of  a  pixel  in  the  ima ge.  The  predefined  set  of  colors  is  called  a  palette.  T o  reduce  the  size  of  a  color-indexed  image  further,  lossless  compression  techniques  are  generally  used  because the index used to pick a particular palette  color  must be exact in decoding. A minor difference betwe en  two index values may result in a serious color shif t.  In  a  standard  image  coding  scenario,  pixel-to-pixel   correlation  nearly  always  exists  in  the  data,  espec ially  if the image is a natural scene. This correlation i s what  allows  predictive  coding  schemes  (e.g.,  DPCM)  to  perform  efficient  compression.  In  a  color  mapped  image,  the  values  stored  in  the  pixel  array  are  no  longer  directly  related  to  the  pixel  intensity.  For   each  pixel in the image, only the index of the correspon ding color  needs  to  be  stored.  Two  color  indices  which  a re  numerically  adjacent  (close)  may  point  to  two  very  different  colors.  The  correlation  still  exists,  but   only  via  the  color  map.  The  efficiency  of  a  lossless  compression algorithm for indexed images may greatl y  depend  on  the  assignment  of  indexes  in  the  relative   lookup table [2].   Palette  reordering  is  a  well-known  and  very  effective  approach  for  improving  the  compression  of   color-indexed  images.  Highly  compressed  palettized  images  are  needed  in  many  applications  such  as  game   cartridges,  computer  graphics  and  World  Wide  Web  (WWW) on-line services.  The  bottleneck  of  this  solution  is  the  intrinsic  inefficiency  to  numerically  optimize  the  palette  re- indexing. If the optimal palette configuration is s ought,  the computational  complexity  involved  would  be  high .  As  a  matter  of  fact,  a  table  of  M colors  corresponds  to  M! Configurations [26]. Clearly, this exhaustive sea rch  is  impractical  and  thus  transforms  to  an  NP  hard  problem.   In  typical  applications  where  the  search  space  is  large  and  multidimensional,  prior  information  about   the  function  is  not  available  and  traditional  mathematical  techniques  are  not  applicable.  Global  optimization  is  a  NP  complete  problem  and  heuristic  

References

[1] Al-Hassan W., Fayek M., and Shaheen S., PSOSA: An Optimized Particle Swarm Technique for Solving the Urban Planning Problem, in Proceedings of the International Conference on Computer Engineering and System , Cairo, Egypt, pp. 401-405, 2006.

[2] Arnavut Z. and Sahin F., Lossless Compression of Color Palette Images with One Dimensional Technique, the Journal of Electronic Imaging , vol. 15, no. 2, pp. 1-11, 2006.

[3] Battiato S., Gallo G., Impoco G., and Stanco F., An Efficient Re-Indexing Algorithm for Color- Mapped Images the IEEE Transactions Image Processing , vol. 13, no. 11, pp. 1419-1423, 2004.

[4] Battiato S., Rundo F., and Stanco F., Self Organizing Motor Maps for Color-Mapped Image Re-Indexing, the IEEE Transactions Image Processing , vol. 16, no. 12, pp. 2905- 2915, 2007.

[5] Clerc M., Think Locally, Act Locally: The Way of Life of Cheap-PSO, Technical report, available at: http://clerc.maurice.free.fr/pso/, la st visited 2001.

[6] De P., Kroese D., Mannor S., and Rubinstein R., A Tutorial on the Cross-Entropy Method, in Proceedings of Annuals of Operation Research , Germany, pp. 19-67, 2005.

[7] Eberhart R. and Shi Y., Particle Swarm Optimization: Developments, Applications and Resources, in Proceedings of IEEE Congress on Evolution Computation , Seoul, Korea, pp. 81-86, 2001.

[8] Gao Y., An X., and Liu J., A Particle Swarm Optimization Algorithm with Logarithm Decreasing Inertia Weight and Chaos Mutation, in Proceedings of International Conference on Computational Intelligence and Security , Suzhou, China, pp. 61-65, 2008.

[9] Ghali N., El-Dessouki N., Mervat N., and Bakrawi L., Exponential Particle Swarm Optimization Approach for Improving Data Clustring, the International Journal of Electrical and Electronics Engineering , vol. 3, no. 6, pp. 208-212, 2009.

[10] Hook J., Sahin F., and Arnavut Z., Application of Particle Swarm Optimization for Traveling Salesman Problem to Lossless Compression of Color Palette Images, in Proceedings of IEEE SMC System of System Engineering , Singapore pp. 1-5, 2008.

[11] Hook J., Sahin F., and Arnavut Z., Improved Lossless Compression of Color Palette Images by Re-indexing with Particle Swarm Optimization, in Proceedings of Soft Computing , Computing with words and Perception in System Analysis, Decision and Control , Famagusta, Cyprus, pp. 1- 4, 2009.

[12] Hu J., Xu J., Wang J., and Xu T., Research on Particle Swarm Optimization with Dynamic Inertia Weight, in Proceedings of the International Conference on Management and Service Science , Wuhan, China, pp. 1-4, 2009.

[13] Hu X., Eberhart R., and Shi Y., Recent Advances in Particle Swarm, in Proceedings of the Congress on Evolution Computation , Oregon, USA, pp. 90-97, 2004.

[14] Kennedy J. and Eberhart R., Particle Swarm Optimization, in Proceedings of IEEE International Conference on Neural Networks , Perth, Western Australia, pp. 1942-1948, 1995.

[15] Liu C., Ouyang C., Zhu P., and Tang W., An Adaptive Fuzzy Weight PSO Algorithm, in Speed up of Reindexing in Adaptive Particle Swarm Optimization 409 Proceedings of the 4th International Conference on Genetic and Evolution Computing , Shenzhen, China, pp. 8-10, 2010.

[16] Li H. and Gao Y., Particle Swarm Optimization Algorithm with Exponent Decreasing Inertia Weight and Stochastic Mutation, in Proceedings of the 2 nd International Conference on Information and Computing Science , Manchester, UK, vol. 1, pp. 66-69, 2009.

[17] Menon N. and Venkateswaran A., On Ordering Color Maps for Lossless Predictive Coding, the IEEE Transactions Image Processing, vol. 5, no. 11, pp. 1522-1527, 1996.

[18] Niraimathi P., Sudhakar M., and Bhoopathy K., Efficient Reordering Algorithm for Color Palette Image using Adaptive Particle Swarm Technique, the Applied Soft Computing , vol. 12, no. 8, pp. 2199-2207, 2012.

[19] Semary N., Hadhoud M., Abdul-Kader H., and Abbas A., Novel Compression System for Hue- Saturation and Intensity Color Space, the International Arab Journal of Information Technology , vol. 10, no. 6, pp. 546-552, 2013.

[20] Pei S., Chuang Y., and Chuang W., Effective Palette Indexing for Image Compression using Self-organization of Kohonen Feature Map, the IEEE Transactions Image Processing , vol. 15, no. 9, pp. 2493-2498, 2006.

[21] Peram T., Veeramachaneni K., and Mohan C., Fitness-Distance-Ratio Based Particle Swarm Optimization, in Proceedings of IEEE Swarm Intelligence Symposium , Indiana, USA, pp. 174- 181, 2003.

[22] Pinho A. and Neves A., A Note on Zeng s Technique for Color Reindexing of Palette-Based Images, the IEEE Signal Processing letters , vol. 11, no. 2, pp. 232-234, 2004.

[23] Pinho A. and Neves A., Survey on Palette Reordering Methods, the IEEE Transactions Image Processing , vol. 13, no. 11, pp. 1411- 1418, 2004.

[24] Pinho A. and Neves A., On the Relation between Memon s and the Modified Zeng s Palette Reordering Methods, the Image Vision Computing , vol. 24, no. 5, pp. 534-540, 2006.

[25] Sahin F. and Devasia A., Distributed Particle Swarm Optimization for Structural Bayesian Network Learning, Swarm Intelligence: Focus on Ant and Particle Swarm Optimization: I Tech Education and Publishing , Vienna, pp. 505-532, 2007.

[26] Sayood K., Lossless Compression Handbook , Academic New York, USA, 2002.

[27] Shi X., Liang Y., Lee H., Lu C., and Wang Q., Particle Swarm Optimization-based Algorithms for TSP and Generalized TSP, the Information Processing Letters , vol. 103, no. 5, pp. 169-176, 2007.

[28] Shi Y. and Eberhart R., A Modified Swarm Optimizer in Proceedings of IEEE International Conference of Evolution Computation , Anchorage, Alaska, 1998.

[29] Shi Y. and Eberhart R., Fuzzy Adaptive Particle Swarm Optimization in Proceedings of IEEE Congress on Evolutionary Computation , Seoul, Korea, pp. 101-106, 2001.

[30] Suganthan P., Particle Swarm Optimiser with Neighborhood Operator, in Proceedings of IEEE Congress on Evolutionary Computation , Washington, USA, pp. 1958-1962, 1999.

[31] Trelea I., The Particle Swarm Optimization Algorithm: Convergence Analysis and Parameter Selection, the Information Processing Letters , vol. 85, no. 6, pp. 317-325, 2003.

[32] Yang C., Cheng Y., and Chuang L., A Novel Chaotic Inertia Weight Particle Swarm Optimization for PCR Primer Design, in Proceedings of the International Conference on Technology and Applications of Artificial Intelligence , Hsinchu, Taiwan, pp. 373-378, 2010.

[33] Zhou Z. and Shi Y., Inertia Weight Adaption in Particle Swarm Optimization Algorithm Advances in Swarm Intelligence, in Proceedings of the 2 nd International Conference , ICSI , Chongqing, China, pp. 71-79, 2011. Niraimathi Ponnusamy graduated from Bharath University, India and received her MTech in VLSI design. She is a faculty member in the Department of electronics and eommunication engineering, MIT Campus Anna University. Her research areas include image processing, soft computing, VLSI and signal processing algorithms. Bhoopathy Krishnaswamy completed his doctoral degree from IIT Madras. He is presently working as Professor, ECE Department, in MIT campus, Anna University, India. His areas of interest include signal processing, image processing and network security.