Representative Pixel (RP) Extraction Based on L1 Minimization Model for Efficient Image Compression

Call for Papers - April 2019

Download Full-Text PDF Cite this Publication

Text Only Version

Representative Pixel (RP) Extraction Based on L1 Minimization Model for Efficient Image Compression

1Amara Krishna Sai Kumar: Department of Electronics and Communication Dayanandasagar College of Engineering,


2Prof . Dr . K . Karibasappa

Department of Electronics and Communication Dayanandasagar College of Engineering

. Bangalore,INDIA

Dr . Sudha K L

Department of Electronics and Communication Dayanandasagar College of Engineering

. Bangalore,INDIA

Abstract In this paper we formulate the colorization- based coding problem into an optimization problem, i.e., an L1 minimization problem. In colorization-based coding, the encoder chooses a few representative pixels (RP) for which the chrominance values and the positions are sent to the decoder, whereas in the decoder, the chrominance values for all the pixels are reconstructed by colorization methods. The main issue in colorization- based coding is how to extract the RP well therefore the compression rate and the quality of the reconstructed color image becomes good. By formulating the colorization-based coding into an L1 minimization problem, it is guaranteed that, given the colorization matrix, the chosen set of RP becomes the optimal set in the sense that it minimizes the error between the original and the reconstructed color image. In other words, for a fixed error value and a given colorization matrix, the chosen set of RP is the smallest set possible. the proposed method outperforms conventional colorization-based coding methods as well as the JPEG standard and is comparable with the JPEG2000 compression standard, both in terms of the compression rate and the quality of the reconstructed color image.

IndexTermsDCT Co-efficients, Representative pixels (RP) set , Sparse L1 minimization.


A new compression technique for color images, which is based on the use of colorization methods. The main task in colorization based compression is to extract these representative pixels in the encoder. In other words, the encoder selects the pixels required for the colorization process, which are called representative pixels (RP) in, and maintains the color information only for these RP. The position vectors and the chrominance values are sent to the decoder only for the RP set together with the luminance

channel, which is compressed by conventional compression techniques. 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 set so that the compression rate and the quality of the restored color image become good. The main contribution of this paper is that we formulated the RP selection problem into an optimization problem, that is, an L1 minimization problem. The formatter will need to create these components, incorporating the applicable criteria that follow selection of the RP is optimal with respect to the given colorization matrix in the sense that the difference error between the original color image and the reconstructed color image becomes minimum with respect to the L2 norm error. Furthermore, the number of pixels in the RP set is also minimized by the L1 minimization. The optimal set of RP is obtained by a single minimization step, and does not require

Any refinement, i.e., any additional RP extraction/reduction methods. The optimization problem can also be considered as a variation approach, and therefore, the rich research results of the variational approach. In this paper we propose a method to determine the colorization matrix from the given luminance channel before the RP selection.


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. Then, in the encoder, the colorization matrix Cis constructed by performing the decompressed luminance channel. The decompressed simulation results. Finally, conclusion and future work is presented in Section V. Luminance channel is used to consist with that in the decoder. Using this matrix C and the original chrominance values obtained from the original color image, the RP set is extracted by solving into an optimization problem, i.e., L1minimization problem. This RP set is sent to the decoder, where the colorization matrix C is also reconstructed from the decompressed luminance channel. Then, by performing a colorization using

the matrix C and the RP set, the color image is reconstructed. Frame work is shown in figure (1)

De-compressed Channel (Y)

Conventional De-compression

Conventional 1 Channel Compression (JPEG)

Luminance Channel (Y)


Original Image (I)

Co- efficients

Re-constructed Image


RP Set Extraction (L1 Minimization)




Constructing the Color Matrix

Encoder Decoder

Fig(1). System Diagram


    The colorization process can be expressed in matrix form as follows:

    y= mx+c


    Here, y represents the given data, m represents the chrominance matrix preformed on x represents the sparse vector to obtain the representative pixel set which is one dimensional vector of size n and c represents the noise. m is the chrominance C matrix considered from the color table of the original image. Our method expresses, where c is an m x n matrix, where m is the size of x, and normally m<n. 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, we seek to obtain a sparse vector x. Therefore, we formulate the problem of selecting the RP into L1 minimization problem.

    • To extract the RP set, we consider the chrominance matrix m of size mxn (m<n), by eliminating the zero values, taking the non-zero values, we formulate the indices such a way that considering the values (non- zero) by each row and the column place number. Thereby we obtain the indices for m1, m2, m3… rows. By applying the linear programming (1), finding out the slope values of the each row considering,

    Y1=m1x1+c (2)

    Y2=m2x2+c (3)..

    Here x represents sparse vector, which are the non-zero values of x-coordinates from the indices. By doing this procedure depending up on the number of m non-zero row indices, we formulate the REPRESENTATIVE PIXEL set (RP) in the encoder, sending this RP set to decoder. The size the obtained RP set will be of the minimized mxn where m<n.


    Formulating the RP set into L1 minimization problem, considering the received RP set at the receiving end at the decoder, we once again formulate the linear programming on the RP set to minimize the non-zero elements into minimized set by taking the every m row of RP set, and considering the following:

    1. Initial state of the row m1,

    2. Finding the duality gap (step size) between the element values.

    3. Considering the number of elements in the row


      By this operating process we can formulate the minimized set of Representative pixels to size 1xn. With these 1xn elements, we can formulate the reconstructed image by backtracking algorithm.


    Once we obtain with the minimized set of Representative pixel, considering this 1xn array values, we follow the above Three-step approach considering the 1xn array values we obtain the matrix of size mxn where (m<n). Hence by following this procedure we obtain the reconstructed color image of a finer quality compared to the JPEG 2000 standards. By formulating the colorization by an L1 minimization problem, we obtain the following benefits:

    1. Compared to the sets of RP obtained by other conventional colorization based coding methods, which are updated at each iteration, the set of RP in our method is obtained only once and requires no update.

    2. Compared to other colorization based coding methods, our method needs no extra RP extraction/reduction.

    3. It is mathematically guaranteed that the RP set is optimal with respect to the given matrix C in the sense that it minimizes the number of RP due to the L1 norm. If using (2) (3), then it is also optimal (with respect to given matrix C) in the sense that it makes the square error in minimum. The solution becomes a local optimal minimum of (1).

    4. By formulating the problem of RP selection as an

    optimization problem, we have designed a way to adopt existing optimization techniques to the problem of RP selection.


    Taking an image which is resized into 256X256, which of 65,536 pixels, Hence by formulating the L1 optimization problem we reduced it into 676 pixels. With a finer quality of the image. The quality of the image is measure in terms of the PSNR and MSE values.








    JPEG 2000










In this paper we have formulated the colorization based coding problem into an optimization problem.Further, we proposed a method to compute the colorization matrix which can colorize the image with a small set of Representative pixels. Experimentally we have proved that this method surpasses other colorization based coding method to large extent.


  1. A. Levin, D. Lischinski, and Y.Weiss, Colorization using optimization,ACM Trans. Graph., vol. 23, no. 3, pp. 689694, Aug. 2004.

  2. E. Candés, J. Romberg, and T. Tao, Stable signal recovery from incomplete and inaccurate information, Commun. Pure Appl. Math.,vol. 59, no. 8, pp. 12071233, 2005.

  3. W. Yin, S. Osher, D. Goldfarb, and J. Darbon, Bregman iterative algorithms for 1-minimization with applications to compressed sensing, SIAM J. Imag. Sci., vol. 1, no. 1, pp. 143168, 2008 .

  4. X. He, M. Ji, and H. Bao, A unified active and semi-supervised learningframework for image compression, in Proc. IEEE Comput. Vis. PatternRecognit., Jun. 2009, pp. 6572.

  5. T. Miyata, Y. Komiyama, Y. Inazumi, and Y. Sakai, Novel inversecolorization for image compression, in Proc. Picture Coding Symp., 2009.

  6. S. Ono, T. Miyata, and Y. Sakai, Colorization-based coding by focusingon characteristics of colorization bases, in Proc. Picture Coding Symp.Dec. 2010, pp. 230233.

  7. D. Donoho, Compressed sensing, IEEE Trans. Inf. Theory, vol. 52,no. 4, pp. 12891306, Apr. 2006.

Leave a Reply

Your email address will not be published. Required fields are marked *