A New Efficient Reordering Algorithm for Color Palette Image

Full Text (PDF, 516KB), PP.53-60

Views: 0 Downloads: 0


Somaye Akbari Moghadam 1,* Mahnaz Rajabzade 1 Mohammad Sadeq Garshasbi 2 Javad Sadri 3

1. Department of Computer Engineering, Ferdows branch, Islamic Azad University, Ferdows, Iran

2. Department of Computer Engineering, Germi branch, Islamic Azad University, Germi, Iran

3. School of Computer Science, McGill University, 3630 University, Montreal, QC, Canada H3A 2B2

* Corresponding author.

DOI: https://doi.org/10.5815/ijigsp.2014.01.08

Received: 19 Jul. 2013 / Revised: 23 Aug. 2013 / Accepted: 26 Sep. 2013 / Published: 8 Nov. 2013

Index Terms

Reindexing, NP-Complete, Lossless, Compression, Genetic Algorithms


Palette re-ordering is a class of pre-processing methods aiming at finding a permutation of color palette such that the resulting image of indexes is more amenable for compression. The efficiency of lossless compression algorithms for fixed-palette images (indexed images) may change if a different indexing scheme is adopted. Obtaining an optimal re-indexing scheme is suspected to be a hard problem and only approximate solutions have been provided in literature. In this paper, we explore a heuristic method to improve the performances on compression ratio. The results indicate that the proposed approach is very effective, acceptable and proved.

Cite This Paper

Somaye Akbari Moghadam,Mahnaz Rajabzade,Mohammad Sadeq Garshasbi,Javad Sadri, "A New Efficient Reordering Algorithm for Color Palette Image", IJIGSP, vol.6, no.1, pp. 53-60, 2014. DOI: 10.5815/ijigsp.2014.01.08


[1]Ming-ni wu, Chia-chen lin and Chin-chen chang, " A Color Re-Indexing Scheme Using Genetic Algorithm", Proceedings of the 6th WSEAS International Conference on Multimedia Systems & Signal Processing, Hangzhou, China, April 16-18, 2006 (pp125-131).

[2]Sebastiano Battiato, Giovanni Gallo, Gaetano Impoco, and Filippo Stanco, " An Efficient Re- Indexing Algorithm for Color-Mapped Images ", IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 13, NO. 11, NOVEMBER 2004.

[3]Chin-Chen Changa, Chih-Yang Linb and Yi-Hsuan Fanb, " Lossless data hiding for color images based on block truncation coding ", Elsevier, Pattern Recognition 41 (2008) 2347 – 2357.

[4]P. Niraimathia, M.S. Sudhakara and K. Bhoopathy Baganb, " Efficient reordering algorithm for color palette image using adaptive particle swarm technique ", Elsevier, Applied Soft Computing 12 (2012) 2199–2207.

[5]A.J. Pinho, A.J.R. Neves, A note on Zeng’s technique for color reindexing of palette-based images, IEEE Signal Process. Lett. 11 (2) (2004) 232–234.

[6]Z. Arnavut, F. Sahin, Lossless compression of color palette images with one dimensional technique, J. Electron. Imaging 15 (2) (2006).

[7]A.J. Pinho, A.J.R. Neves, Survey on palette reordering methods, IEEE Trans. Image Process. 13 (11) (2004) 1411–1418.

[8]J.V. Hook, F. Sahin, Z. Arnavut, Application of particle swarm optimization for traveling salesman problem to lossless compression of color palette images, in: Proceedings of IEEE SMC System of Systems Engineering, 2008, pp. 1–5.

[9]P.T. de Boer, D.P. Kroese, S. Mannor, R.Y. Rubinstein, A tutorial on the crossentropy method, Ann. Oper. Res. (2005) 19–67.

[10]Cengiz Kahramana, Orhan Enginb, Ihsan Kayaa, and R. Elif, Multiprocessor task scheduling in multistage hybrid flow-shops: A parallel greedy algorithm approach, Elsevier, Applied Soft Computing 10 (2010) 1293–1300.