A Novel Low Space Image Storing and Reconstruction Method by K-Means Clustering Algorithm
Santanu Halder1, Abul Hasnat2, Debotosh Bhattacharjee3, Mita Nasipuri3
1Department of Computer Science and Engineering, Government College of Engineering and Leather Technology, Kolkata, West Bengal
2Department of Computer Science and Engineering, Government College of Engineering and Textile Technology, Berhampore, West Bengal
3Department of Computer Science and Engineering, Jadavpur University, Kolkata-700032, West Bengal
*Corresponding Author E-mail: sant.halder@gmail.com
ABSTRACT:
This paper presents a lossy image compression technique that proposes a novel approach for storing RGB color images which save 33% memory space compared to memory space requirement of conventional method of storing RGB images. The proposed method, first finds the most and least dominating color components among three Red, Green and Blue color channels for each RGB image and then for each pixel of the image, it finds the absolute difference between the most and least dominating color values and expresses the difference as a fraction of the most dominating color value of the pixel. All the fraction values are clustered into sixteen groups using K-Means Clustering algorithm and all centroids are stored as Header. The less significant two bits of each the other two color channels are modified according to the cluster information. These two modified color channels along with one Header are stored for each image. Thus 33% of the memory space requirement to store the original image could be saved using the proposed method. At the time of reconstruction of the image, according to the cluster information third color component is retrieved with the help of the header. The experimental result shows that the reconstructed images retain around 98.5±0.5% of the original image information. The method has been implemented using Matlab 7 and tested on one standard FRAV2D database and hundred natural images and this method could be applied to compress any RGB image.
KEYWORDS: Psycho-visual redundancy, Lossy image compression, Clustering, K-means, dominating color.
I. INTRODUCTION
An image is essentially a 2-D signal processed by the human visual system. The signals, representing images, are usually in analog form. However, for processing, storage and transmission by computer applications, they are converted from analog to digital form. A digital image is basically a 2-Dimensional array of pixel intensities [1-3]. There are a lot of works available in literature on both lossless and lossy image compression techniques [3-9]. Image compression addresses the problem of reducing the amount of data required to represent a digital image while keeping the resolution and the visual quality of the reconstructed image as close to the original image as possible. It is a process intended to yield a compact representation of an image, thereby reducing the image storage/transmission requirements. Image compression techniques reduce the number of bits required to represent an image by taking advantage of the three basic data redundancies:
1. Coding Redundancy
2. Interpixel Redundancy
3. Psychovisual Redundancy.
Coding redundancy is present when less than optimal code words are used. Interpixel redundancy results from correlations between the pixels of an image. Psychovisual redundancy is due to data that is ignored by the human visual system (i.e. visually non essential information). The proposed work concentrates on the Psychovisual redundancy to reduce the required storage space for an image. An inverse process called decompression (decoding) is applied to the compressed data to get the reconstructed image. The benefits of compression can be summarized as follows:
1. It reduces the data transmission cost as less number of data is to be transferred over network.
2. It not only reduces storage requirements but also overall execution time.
3. It also reduces the probability of transmission errors since fewer bits are transferred.
4. It also provides a level of security against illicit monitoring.
The image compression techniques are broadly classified into two categories depending on whether or not an exact replica of the original image could be reconstructed using the compressed image. These are:
1. Lossless technique
2. Lossy technique
The proposed work focuses on a lossy compression technique based on storing the RGB image database in a new approach where for each image only most and one of the other two color component of the RGB image are stored. For this purpose whole symmetric image database is clustered into several groups of more similar images, some extra information are embedded in the least significant two bits of binary representation of each of the stored two color components of each pixel of an image. After that one image from each of these groups of images are stored in conventional method and for the remaining images of each group, only the most dominating color components, one of the other two color components and a header of four elements for each of the images are stored. This proposed method of storing color images requires nearly 33% less memory space compared to memory requirement of storing the RGB images in conventional method. During the reconstruction phase of original image, the least dominating color component is retrieved using the Header containing sixteen centroids. Thereafter, for each image only two color components are stored along with Header. The third color component is retrieved in accordance with the Header information and the RGB image is reconstructed. The whole work is divided into two sections.
A. Storing the color images using the two color components.
B. Retrieval of the third color component using the header and reconstruction of color image.
A. Storing the color images using the two color components.
In
the proposed method, first the sequence of most dominating color component is selected
for an image. Then for each pixel, the variation of color intensity of least
significant color component with respect to most dominating color channel are
clustered into sixteen clusters using K-Means clustering algorithm [10-13]. The
centroids of these sixteen groups are stored in a Header. In next step, for
each pixel modification is done in the less significant two bits of dominating two
color components
and
. The
modified C1 and C2 along with header are stored instead
of the whole image. The whole process is shown step by step in Fig. 1.
Figure 1. Process of storing the images using two color components.
B. Retrieval of the third color component and reconstruction of color image
The RGB color image needs all the three color components whereas the proposed method, each image is stored using only two color components and one Header. So to reconstruct the image, the retrieval of the third color component is required. The retrieval of the third color component for each pixel of the image is done with the hidden information in the least significant two bits of the stored two color components and the cluster information contained in the Header. After the third color component is retrieved and all the three color components are available for reconstruction of the RGB color image. The compression technique exploits psycho-visual redundancy of image and information loss in this lossy compression method is indiscernible in human visual system. The whole process of third color component retrieval of the RGB image is shown in Fig. 2.
Figure 2. Image reconstruction flowchart
The proposed method has been tested on one standard RGB face image database a) FRAV2D [14] and hundreds of natural RGB images captured using standard camera.
This paper is organized as follows: Section II discusses the selection of two dominating color component. Section III describes K-Means algorithm and application of it in the proposed method, Section IV. Construction of Header for each image, Section V describes the process of embedding extra information in the two color component bits stored. Section VI Restoration of the RGB image, Section VII Shows the experimental results and finally Section VIII concludes about some of the aspects analyzed in this paper.
TABLE I. CENTROIDS AND RANGE OF MAPPING FOR AN IMAGE FROM FRAV2D DATABASE
|
Cluster No. |
Header of the image in Fig 3(a) |
Header of the image in Fig 3(b) |
Header of the image in Fig 3(c) |
Header of the image in Fig 3(d) |
|
1 |
-2.3595 |
-80.000 |
-0.3644 |
-0.3644 |
|
2 |
-1.6358 |
-18.4162 |
-0.2243 |
-0.2243 |
|
3 |
-1.1751 |
-6.9359 |
-0.1640 |
-0.1640 |
|
4 |
-0.8928 |
-3.7423 |
-0.1209 |
-0.1209 |
|
5 |
-0.6823 |
-2.2521 |
-0.0891 |
-0.0891 |
|
6 |
-0.5178 |
-1.5378 |
-0.0620 |
-0.0620 |
|
7 |
-0.3857 |
-1.1255 |
-0.0372 |
-0.0372 |
|
8 |
-0.2787 |
-0.8568 |
-0.0138 |
-0.0138 |
|
9 |
-0.1888 |
-0.6655 |
0.0064 |
0.0064 |
|
10 |
-0.1079 |
-0.5133 |
0.0318 |
0.0318 |
|
11 |
-0.0516 |
-0.3822 |
0.0601 |
0.0601 |
|
12 |
-0.0129 |
-0.2588 |
0.0932 |
0.0932 |
|
13 |
0.0169 |
-0.1328 |
0.1334 |
0.1334 |
|
14 |
0.0429 |
0.0020 |
0.1913 |
0.1913 |
|
15 |
0.0718 |
0.1823 |
0.2754 |
0.2754 |
|
16 |
0.1128 |
0.4762 |
0.4014 |
0.4014 |
II. CONCLUSION:
This paper presents lossy image compression technique that proposes a novel approach for storing RGB color images which saves 33% memory space compared to memory space requirement of conventional method of storing RGB images. The experimental result shows that the reconstructed image retains around 98% data of the original image. The compression technique exploits psycho-visual redundancy of image and information loss in this lossy compression method is indiscernible in human visual system. This work may be extended in future to further application of compression techniques in the compressed file obtained using proposed method. The method has been tested on the images of one standard database FRAV2D and hundred natural images. The proposed algorithm is very simple and has been implemented using Matlab 7.
III. ACKNOWLEDGMENT:
Authors are thankful to the "Center for Microprocessor Application for Training Education and Research", "Project on Storage Retrieval and Understanding of Video for Multimedia" at Computer Science & Engineering Department, Jadavpur University, for providing infrastructural facilities during progress of the work. One of the authors, Mr. Abul Hasnat is thankful to Government College of Engineering and Textile Technology, Berhampore, West Bengal for kindly permitting them to carry on the research work.
IV. REFERENCES:
[1] R. C. Gonzalez, R. E. Woods, S. L. Eddins, “Digital Image processing using MATLB”, Mc-Graw Hill, 2011.
[2] R. C. Gonzalez, R. E. Woods, “Digital Image Processing”, Addison Wesley, 2002.
[3] Ming Yang & Nikolaos Bourbakis ,“An Overview of Lossless Digital Image Compression Techniques,” Circuits & Systems, 2005 48th Midwest Symposium, vol. 2 IEEE ,pp 1099-1102,7 – 10 Aug, 2005.
[4] Milos Klima, Karel Fliegel, “Image Compression Techniques in the field of security Technology: Examples and Discussion”, Security Technology, 2004, 38th Annual 2004 International Carnahan Conference, pp 278-284,11-14 Oct., 2004.
[5] Ismail Avcibas, Nasir Memon, Bulent Sankur, Khalid Sayood, “A Progressive Lossless / Near Lossless Image Compression Algorithm”, IEEE Signal Processing Letters, vol. 9, No. 10, pp 312-314, October 2002.
[6] C.K. Li and H.Yuen, “A High Performance Image Compression Technique For Multimedia Applications”, IEEE Transactions on Consumer Electronics, Vol. 42, no. 2, pp 239-243, 2 May 1996.
[7] Wen Shiung Chen, en- HuiYang & Zhen Zhang, “ A New Efficient Image Compression Technique with Index- Matching Vector Quantization,” Consumer Electronics, IEEE Transactions, Vol. 43, Issue 2, pp 173- 182, May 1997.
[8] David H. Kil and Fances Bongjoo Shin, “Reduced Dimension Image Compression And its Applications”, Image Processing, 1995, Proceedings of International Conference, Vol. 3, pp 500-503, 23-26 Oct., 1995.
[9] Santanu Halder, Debotosh Bhattacharjee, Mita Nasipuri, Dipak Kumar Basu, “A low space bit plane slicing based image storage method using extended JPEG format”, IJETAE, ISSN 2250-2459, Vol 2, Issue 4, 2012.
[10] Anil K. Jain,Richard C. Dubes, “Algorithms for Clustering Data”, 2004.
[11] Guojun Gan,Chaoqun Ma,Jianhong Wu, “Data Clustering Theory, Algorithms and Applications”, 2007.
[12] John A. Hartigan, “Clustering Algorithms”, 1975.
[13] Tapas Kanungo,David M. Mount,Nathan S. Netanyahu,Christine D. Piatko, Ruth Silverman,Angela Y. Wu, “An Efficient k-Means Clustering Algorithm: Analysis and Implementation”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 24, no. 7,July 2002.
[14] FRAV2D Database (2004), Freely available from: http://www.frav.es/databases/frav2d/.
|
Received on 04.01.2014 Accepted on 29.01.2014 © EnggResearch.net All Right Reserved Int. J. Tech. 4(1): Jan.-June. 2014; Page 186-196 |