RP BASED OPTIMIZED IMAGE COMPRESSING TECHNIQUE

RP BASED OPTIMIZED IMAGE COMPRESSING TECHNIQUE

• 1.
  International Journal ofElectronics and Communication Engineering Research and Development (IJECERD), ISSN 2248-9525(Print), ISSN- 2248-9533 (Online) Volume 4, Number 2, April-June (2014) 56 RP BASED OPTIMIZED IMAGE COMPRESSING TECHNIQUE Sharanabasappa Chattaraki IV sem M.Tech (DE&CS) student E&C Dept, MCE, Hassan, Karnataka, India Dr. B. R. Sujatha Associate Professor, E&C Dept, MCE, Hassan, Karnataka, India ABSTRACT Colorization is a method that adds color components to a gray scale image using only a few representative pixels (RP) by the user. A novel approach to image compression called colorization-based coding is being done. It automatically extracts representative pixels from an original color image at an encoder and restores a full color image by using colorization at the decoder. However past studies on colorization based coding obtain redundant representative pixels and do not remove the pixels required for suppressing coding errors. The main issue in colorization based coding is how to extract representative pixels (RP) so that compression rate is high and the reconstructed images have good visual quality. In this work we formulate the colorization based coding into an optimization problem i.e., an Lଵ minimization problem. We use the colorization matrix that colorizes the image in a multi scale manner and this is combined with RP extraction method allows us to choose a very small set of RP. Simulation results revealed that implemented method compress the color image with higher compression rate and has good quality and is comparable to conventional JPEG standard. Keywords: Chrominance value, Compression Rate Colorization, Image compression, Luminance value, reconstruction 1. INTRODUCTION Colorization based coding refers to the color compression technique based on the use of colorization methods [2]-[5]. In colorization approach, the color values of an image are obtained from a few pixels having color information [6]. The color information of these pixels is propagated to neighbouring pixels by colorization methods making the whole image colorized. Colorization based coding utilizes the fact that the required number of pixels having color information is small. The encoder chooses the pixels required for the IJECERD © PRJ PUBLICATION International Journal of Electronics and Communication Engineering Research and Development (IJECERD) ISSN 2248– 9525 (Print) ISSN 2248 –9533 (Online) Volume 4, Number 2, April- June (2014), pp. 56-63 © PRJ Publication, http://www.prjpublication.com/IJECERD.asp
• 2.
  International Journal ofElectronics and Communication Engineering Research and Development (IJECERD), ISSN 2248-9525(Print), ISSN- 2248-9533 (Online) Volume 4, Number 2, April-June (2014) 57 colorization process, which are called RP (representative pixels) in [5], and maintains the color information only for the RP. The position information and the color values are sent to the decoder only for the RP. Then, the decoder restores the color information for the remaining pixels using colorization methods. The main issue in colorization based coding is how to extract the RP such that the compression rate and the quality of the restored image becomes good. Several methods have been proposed to this end [2]-[5]. All these strategies take an iterative methodology in which a random set of RP is chosen. At that point, a tentative color image is reconstructed using RP set, and the nature of the reconstructed color image is evaluated by comparing it with original color image. Additional RP are obtained from areas where the quality does not fulfil a certain criteria utilizing RP extraction methods, while redundant RP are diminished by utilizing RP reduction methods. However the set of RP may hold repetitive pixels or some needed pixels may be missed. In this work we have formulated the RP selection problem into an optimization problem. The selection of RP is optimal with respect to given colorization matrix in the sense that difference error between the original color image and reconstructed color image becomes minimum with respect to Lଶ norm error. The optimal set of RP obtained by single minimization steps does not require any additional RP extraction/reduction methods. Therefore there is no need for iteration. In this work we used a construction method of colorization matrix [1], which combined with the RP extraction method produces a high quality reconstructed image. 2. RELATED WORKS Levin et al's propose a colorization algorithm, which reproduces the colors in the decoder utilizing the color informaton for just a couple of representative pixels (RP) and the gray image which holds the luminance information. For instance, utilizing the YCbCr color space, Y is the luminance component corresponding to u and the Cb and Cr color components corresponding to u for a couple of RP. Emulating the documentation in [4], we signified y as the luminance vector, u as the result vector, i.e., the vector holding the color components to be remade in the decoder, and x as the vector which holds the color qualities just at the positions of the RP, and zeros at other positions. The vectors y, u, and x are all in raster-scan order. The cost function defined by Levin et al. is J (u) = x-Au2 (1) Which has to be minimized with respect to u. Here, A ൌ I െ W where I is an n ൈ n identity matrix, n is the number of pixels inu, W is an n ൈ n matrix that contains w୰ୱ ′ weighting components, which is defined as w୰ୱ ′ ൌ ൜ 0 if r ‫א‬ w୰ୱ otherwise Where w୰ୱ α eሺ୷ሺ୰ሻି୷ሺୱሻ/ଶσ౨ మ (2) Here, denotes the set of the positions of the RP, ߪ௥ ଶ is a small positive value, and w୰ୱ is the weighting component between the pixels at the r’s and the s’s positions, wheres ‫א‬ Nሺr), and Nሺrሻ is the 8-neighborhood of the r’s pixel. Furthermore, y(r) and y(s) are the luminance values at the r’s and thes’s positions in the luminance vector y, respectively. The minimiser of (1) can be explicitly computed as u ൌ ሾAିଵ ሿሾxሿ (3)
• 3.
  International Journal ofElectronics and Communication Engineering Research and Development (IJECERD), ISSN 2248-9525(Print), ISSN- 2248-9533 (Online) Volume 4, Number 2, April-June (2014) 58 3. METHODOLOGY A. System Diagram Figure 1 shows the overall system diagram of this work. In the encoder, the original color image is first decomposed into its luminance channel and its chrominance channels. The luminance channel is compressed using conventional one-channel compression techniques, e.g., JPEG standard and its discrete Fourier or Wavelet coefficients are transmitted to the decoder. Also, in the encoder, the colorization matrix C is constructed by performing a multiscale meanshift clustering on decompressed luminance channel. Using the matrix C and the original chrominance values obtained from the original color image, the RP set is extracted by solving an optimization problem, i.e., an Lଵ minimization problem. Decoder decompresses the luminance channel by using discrete Fourier or Wavelet coefficients. This RP set is sent to the decoder, where the colorization matrix C is also reconstructed from the decompressed luminance channel. Then, by performing colorization using the matrix C and the RP set, the color image is reconstructed. B. Formulating the RP Extraction Problem into an ‫ۺ‬૚ Minimization Problem The colorization process can be expressed in matrix form as follows: ሾuሿ ൌ ሾCሿሾx ሿ (4) where C is a square matrix of size n ൈ m. C has the size n ൈ m, where m is the size of x, and normally m ൏ ݊. In the colorization process, C and x are given and u is the solution to be sought. In contrast, in colorization based coding, the problem in the encoder is to determine x when C and u are given. For the aim of compression, to obtain a sparse vector x. Therefore formulate problem of selecting RP as Lଵ minimization problem argmin|x|ଵ୶ , subject to Rୋ ሾu଴ሿ ൌ RୋሾCሿሾxሿ ሺ5ሻ Where Rୋ is a random Gaussian matrix. Equation ሺ5ሻ is an optimization problem and can be solved by linear programming such as the Basis Pursuit (BP) or Orthogonal Matching Pursuit (OMP) [6] [7]. Fig 1: Implemented System Original Color Image Luminance Channel(Y) Conventional Image Compression Decompressed (Y) channel Conventional Image Decompression Encoder Decoder Multiscale Meanshift Clustering Colorization matrix [C] RP Set Extraction Reconstructed Color Image Colorization Colorization matrix [C] Multiscale Meanshift Clustering Decompressed (Y) channel
• 4.
  International Journal ofElectronics and Communication Engineering Research and Development (IJECERD), ISSN 2248-9525(Print), ISSN- 2248-9533 (Online) Volume 4, Number 2, April-June (2014) 59 Since ሺ5ሻ is an optimization problem, the various results from variational methods can be incorporated into the colorization based coding problem. For example, ሺ5ሻ can also be reformulated as an unconstrained problem. argmin ୶ |x|ଵ ൅ λԡRୋሾu଴ሿ െ RୋሾCሿሾxሿԡ૛ ሺ6ሻ For the unconstrained problem the solution varies as the λ parameter varies. In fact, we can alternatively solve the following equation, such that we can control the number of nonzero components as we are minimizing the error between the reconstructed and the original color images argmin ୶ ԡሾu଴ሿ െ ሾCሿሾxሿԡଶ subject to |x|଴ ൑ L ሺ7ሻ Where L is a positive integer that controls the number of nonzero components in x. The number L can be determined by the desired compression rate i.e for large compression rate L is set to a small number. The above equation can be solved either by the Basis Pursuit (BP) or the Orthogonal Matching Pursuit [OMP] solver. C. Construction of the Colorization Matrix For the equation (5)-(7) to be solved, the matrix C has to be determined. In [5], the observation has been made that the column vectors of the colorization matrix can be regarded as the colorization basis vectors. This is considered for constructing the matrixC. The chrominance image u is the linear combination of these column vectors treating the nonzero values (RP) in x as coefficients. For x to become sparse, i.e., to have only a few RP, the column vectors corresponding to the RP should have a large effect on the chrominance imageu. Generally, if a column vector in C has many large nonzero entries, this means that the corresponding RP has a large effect on the chrominance image u. In other words, this means that in the decoder, a large region can be colorized by this RP. Therefore, the vector x obtained by using equation (5)–(7) should contain the RP (or coefficients) which correspond to the column vectors that have large effects on the colorized image. Furthermore, RP corresponding to column vectors with a similar effect on the image should not be redundantly chosen. 1)Multiscale Meanshift Clustering: It plays an important role in the construction of the colorization matrix. In this work, we used the mean-shift clustering [8] due to its several desirable properties. The mean shift clustering uses two parameters where one decides the photometric distances between the pixels inside the clustered regions, and the other decides the spatial distances. Therefore, using the mean shift clustering, we can easily generated segmented regions of different photometric and spatial characteristics. Here we perform a multiscale meanshift clustering to construct the colorization basis. The reason that we use a multiscale meanshift clustering is that there is the possibility that some regions in the colorized image may lack either the Cb or Cr components when using single scale segmentation. This is due to the fact that even though the RP for both the Cb and Cr components have to be selected for every segmented region, some may not be selected due to the Lଵ minimizing constraint. A multi scale mean shift clustering is performed at different scales by using kernels with different bandwidths. A kernel with large bandwidth segments the image into large segments, while a kernel with smaller bandwidth segments the image into smaller segments. This will result in segmented regions of different scales. Now, at each scale, the domain of the whole image ( ) is the union of the segmented regions
• 5.
  International Journal ofElectronics and Communication Engineering Research and Development (IJECERD), ISSN 2248-9525(Print), ISSN- 2248-9533 (Online) Volume 4, Number 2, April-June (2014) 60 = ଵ ୩ ‫׫‬ ଶ ୩ ‫׫‬ … … … ୬ౡ ୩ ‫׊‬k ሺ8ሻ Where, k denotes the scale level, n୩ is the total number of segmented regions at the kth scale, and ୨ ୩ denotes the jth segmented region at the kth scale level. The arrangement of basis vectors according to scale level in matrix C as shown in fig (2). C = Fig 2: Colorization matrix C constructed with multi scale meanshift clustering. The colorization basis vectors are arranged according to the scale. 4. Algorithm A. Encoder 1) Input: Reading Original color image I 2) Decomposition: Decompose I into its luminance channel (y) and original chrominance images u0 cb and u0 cr 3) Perform multiscale meanshift clustering on y to obtain segmented regions k j, j = 1 . . . nk , ‫׊‬k. 4) Construct column vectors Cj, k using k j, j = 1, . . . nk , ‫׊‬k. 5) Concatenate the column vectors construct Cj, k to onstruct the colorization matrix C. 6) Using the Orthogonal Matching Pursuit (OMP) obtain the RP set x by solving the following equation argmin୶ԡሾu଴ሿ െ ሾCሿሾxሿԡଶ subject to |x|଴ ൑ L for u଴ ൌ uୡୠ ଴ and u଴ ൌ uୡ୰ ଴ . 7) Output: Final RP set x ൌ ሼxୡୠ ୩ , xୡ୰ ୩ ሽ (optimal with respect to the matrixC). B. Decoder: 1) Input: Luminance channel (y), RP set x ൌ xୡୠ ୩ , xୡ୰ ୩ 2) Reconstruction 2.1) reconstruct the matrix C by performing multiscale mean shift clustering on y. 2.2) reconstruct the color components by UCb = CxCb and UCr = CxCr 2.3) reconstruct color image I by combining the luminance channel y and the color Components UCb and UCr. 3) Output: Reconstructed Color Image I C1,1 C2,1..Cn,1 C2,1 .....Cn,2......C1,k.....Cn,k...... scale 1 scale 2 scale K
• 6.
  International Journal ofElectronics and Communication Engineering Research and Development (IJECERD), ISSN 2248-9525(Print), ISSN- 2248-9533 (Online) Volume 4, Number 2, April-June (2014) 61 5. RESULTS AND DISCUSSION We compared the implemented method with the JPEG standards. The file sizes of images compressed with JPEG standards are the sum of the compressed luminance channel and chrominance values together. In the implemented method, we used equation (7) with L= 200 i.e., total of 200RP. The compressed file size is the sum of the compressed luminance channel and RP set. In the implemented method we used less than 6 bits to determine the positions of the RP by using delta and Huffman encoding and 2 bytes are used to encode the chrominance values, we take two different color images to compare with JPEG standard. The reconstructed image using implemented method is comparable to JPEG standard as observed in Fig.3 and Fig.4. We used one 256 × 256 sized image and one 294 × 220 sized image. The implemented method comparable to JPEG standard noticeably in every aspect: in file size, PSNR value as mentioned in table I and visual quality shown in Fig.3 and Fig.4 Table I: Comparison of the file sizes in (kb) and PSNR values with the JPEG standard Image Method File Size PSNR Bird JPEG Implemented method 4.43(kb) 4.42(kb) 30.1425 27.3089 pepper JPEG Implemented method 5.70(kb) 5.42(kb) 26.5420 23.7969 (a) (b) (c) Fig 3 (a) Original Image , (b) JPEG Standard (c) Implemented method
• 7.
  International Journal ofElectronics and Communication Engineering Research and Development (IJECERD), ISSN 2248-9525(Print), ISSN- 2248-9533 (Online) Volume 4, Number 2, April-June (2014) 62 (a) (b) (c) Fig 4.(a) Original Image , (b) JPEG Standard, (c) Implemented method 6. CONCLUSION In this paper colorization based coding has been formulated into an optimization problem, we found the solution for the colorization based coding problem using L1 minimization technique. We used a method to compute the colorization matrix which can colorize the image with a very small set of RP. Performance parameter such as PSNR is discussed and implemented method is comparable to JPEG standard is providing good quality compressed image. However the problem of computational cost has to be further studied, and solved. Therefore, image compression is always a tradeoff between resource usage and image quality. REFERENCES [1] Sukho Lee, Sang-Wook Park, Paul Oh, and Moon Gi Kang,“Colorization based Image Compression using Optimisation” IEEE Transactions on image processing, vo,l 22, no. 7,july 2013 pp. 2627-2636 [2] L. Cheng and S. V. N. Vishwanathan, “Learning to compress images and videos,” inProc. Int. Conf. Mach. Learn., vol. 227. 2007, pp. 161–168 [3] X. He, M. Ji, and H. Bao, “A unified active and semi-supervised learning framework for image compression,” in Proc. IEEE Comput. Vis. Pattern Recognit., Jun. 2009, pp. 65–72. [4] T. Miyata, Y. Komiyama, Y. Inazumi, and Y. Sakai, “Novel inverse colorization for image compression,” in Proc. Picture Coding Symp.,2009, pp. 1–4.
• 8.
  International Journal ofElectronics and Communication Engineering Research and Development (IJECERD), ISSN 2248-9525(Print), ISSN- 2248-9533 (Online) Volume 4, Number 2, April-June (2014) 63 [5] S. Ono, T. Miyata, and Y. Sakai,“Colorization-based coding by focusing on characteristics of colorization bases,” in Proc.Picture Coding Symp. Dec. 2010, pp. 230–233. [6] A. Levin, D.Lischinski, and Y. Weiss “Colorization using optimization, ACM Trans. Graph, vol. 23, no. 3, Aug. 2004, pp. 689–694. [7] S. S. Chen, D. L. Donoho, and M. A. Saunders, “Atomic decomposition by basis pursuit,” SIAM J. Sci. Comput., vol. 20, no. 1, 1998, pp. 33–61. [8] J.A. Tropp and A.C. Gilbert, “Signal recovery from random measurements via orthogonal matching pursuit,” IEEE Trans. Inf. Theory, vol. 53, no. 12, Dec. 2007 pp. 4655–4666 [9] D.Comaniciu and P.Meer, “Mean shift: A robust approach toward feature space analysis,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 24, no. 5, May 2002, pp. 603– 619