Printer Friendly

Improving JPEG-LS performance using location information.

Abstract

JPEG-LS is an international standard for lossless or near-lossless image-compression algorithms. In this paper, a simple method is proposed to improve the performance of the lossless JPEG-LS algorithm. With respect to JPEG-LS and its supplementary explanation, Golomb-Rice (GR) coding is mainly used for entropy coding, but it is not used for long codewords. The proposed method replaces a set of long codewords with a set of shorter location map information. This paper shows how efficiently the location map guarantees reversibility and enhances the compression rate in terms of performance. Experiments have also been conducted to verify the efficiency of the proposed method.

Keywords: JPEG-LS, Lossless compression, Golomb code, Golomb-Rice, Location map

1. Introduction

The JPEG-LS algorithm [1] is a lossless or near-lossless compression standard for still images. Most of the recent compression algorithms accepted the Modeling and Coding [2] concept to achieve an efficient compression. JPEG-LS uses the two-sided geometric distribution (TSGD) model [3] of the prediction error that is based on the median edge detector (MED) [4], and encodes this model by Golomb-Rice (GR) coding [5]-[6]. As a lossless compression algorithm, it performs quite effectively and is superior to most of the other algorithms including JPEG2000 [7]-[10]. A group of authors tried to improve the performance of JPEG-LS by introducing novel prediction methods. Baligar et al. [7] proposed a linear prediction method that minimizes the squared error and exploits quadtree coding. Bedi et al. [8] proposed a prediction method that detects the diagonal edges in addition to the vertical and horizontal edges. While the compression performances of both studies [7]-[8] exceed that of JPEG-LS, the computational complexities of their algorithms are far greater [9]. Kademi et al. [10] paradoxically showed the superiority of JPEG-LS. Kim et al. [11] proposed hierarchical average and copy prediction (HACP) scheme and showed the upper bound of significant bit truncatuon (SBT) coding. Combinations of multiple predictions [12]-[13] are also used to improve the compression rates. Masmoudi et al. [14] proposed a block-based lossless image compression for which finite-mixture models and adaptive arithmetic coding are used. Zhao et al. [15] and Starosolski [16] showed that the context-based adaptive lossless image codec (CALIC) [17] provides high compression rates within reasonable time frames, while JPEG-LS is effective enough and very fast. As a result, the JPEG-LS algorithm is still considered excellent in terms of the compression rate and the compression time.

Mobasseri et al. [18] proposed a method for the embedding of data into the JPEG bitstream, whereby Huffman-code mapping is used, and the data embedding is performed according to a reversible mapping of the unused codewords; notably, only a fraction of the JPEG codewords are actually used. Later, Qian and Zhang [19] improved their method, whereby the most important contribution of their methods from [18] and [19] is a reversible data hiding capability for the improvement of the compression rate; this reversibility is used in this paper for the replacement of long codewords. Ding et al. [20] proposed a modified Golomb coding for an asymmetric TSGD.

Even though JPEG-LS is almost perfect as a lossless algorithm, its performance can still be improved. The goal of this paper is the improvement of the JPEG-LS performance through a slight modification of the long codewords. JPEG-LS accepted the GR code as a main encoding alogrithm, but this GR code can sometimes produce excessively long codewords. A number of techniques can be used to remedy the long codeword artifact of the GR code; that is, the JPEG-LS algorithm modifies these long GR codewords into a fixed-length code (the authors call this modification JPEG-LS GR), while an additional improvement is proposed in this paper. The GR artifact can also be resolved by utilizing the location map. The location map is a tool for the book-keeping of the side information that assures the reversibility of data hiding schemes [21]-[23]. It is mostly used to avoid underflow, overflow or decoding errors at the decoding stage.

This paper shows that the location map can be used for lossless data compression; moreover, it shows that long codewords can be replaced with shorter codewords. The contribution of this paper consists of three methods that reduce the size of the symbol length in bits, as follows; replacing the fixed-length prefixes with location information, reducing the location map itself using a variable-length information, and reducing the suffix.

This paper is organized as follows. Section 2 briefly summarizes the concepts of GR coding and JPEG-LS GR coding. Section 3 revisits the concept of the location map, and includes an explanation of the application of location information for JPEG-LS GR coding; a simple method for the reduction of the location map size is also presented; along with a demonstration of improvements of the JPEG-LS GR method for specific cases. Section 4 presents an analysis of the experiment results, whereby the performances of the JPEG-LS GR method and the proposed method are compared. Section 5 concludes the paper.

2. Golomb-Rice coding vs. JPEG-LS coding

When an integer N is divided by another integer m, a quotient q and a remainder r are derived so that the number N can be represented as N = q x m + r. As long as m is given, the GR code in the JPEG-LS is represented by [unary quotient q] + [one bit for a separator "1"] + [binary remainder r]. JPEG-LS does not encode the pixel value itself, but encodes the prediction error through the GR coding. The integer notation is defined here as follows: [N.sub.D] is the digit expression (either in 8 bits or 16 bits), [N.sub.B] is the binary expression of [N.sub.D], and [N.sub.U] is the unary expression. For example, when [N.sub.D] is [3.sub.(10)] for an 8-bit depth image, [N.sub.B] is [00000011.sub.(2)] and [N.sub.U] is [000.sub.(1)], and they are the same representations. Note that [N.sub.U] has three zeros since [N.sub.D] is 3. Similarly, when a given prediction error in a decimal number is [N.sub.D] = [73.sub.(10)], its binary representation in 8-bit format is expressed as [N.sub.B] = [01001001.sub.(2)]. Let a divisor be m = [2.sup.k], for example, where k = 2, q is the first 8 - k bits of [N.sub.B], which is q = [010010.sub.(2)] = [18.sub.(10)] = [000000000000000000.sub.(1)]; and r is the last k bits of [N.sub.B,] which is r = [01.sub.(2)]. In this case, the corresponding GR code is represented by the following format:

[N.sub.GR] = [000000000000000000|1|01.sub.(2)]

The output [N.sub.GR] is of a pseudo-binary form. Namely, it looks like a binary sequence, but it is actually a combination of binary symbols. The GR code starts with 18 leading zeros that are equivalent to the unary representation of the quotient. The first "1" that separates the quotient and the remainder with two red bars is a separator. The last part of "01" is just the remainder r in binary format.

Another given number [73.sub.(10)] can be represented in a different form depending on the k value. Let k be 1 so that q = [0100100.sub.(2)] = [36.sub.(10)] = [000000000000000000000000000000000000.sub.(1)] and r = [1.sub.(2)]. As a result, its GR code is obtained according to the following format:

[N.sub.GR] = [000000000000000000000000000000000000|1|1.sub.(2)]

In this case, the total length of the GR code is 38 bits, which seems excessively long; therefore, this lengthy GR code [N.sub.GR] is not used whenever q [greater than or equal to] [23.sub.(10)], but a shorter code [N.sub.LS] is used in a different format as follows:

[N.sub.LS] = [00000000000000000000000|1|01001000.sub.(2)]

where the eight LSB bits are represented as [N.sub.D] -1 = [72.sub.(10)] = [01001000.sub.(2)]. Now, 32 bits (i.e., [23 bits of leading zeros] + [1-bit separator "1"] + [8-bits of [N.sub.D] -1]) are needed for [N.sub.LS] rather than 38 bits for [N.sub.GR]. This representation mostly shortens the length of the GR code.

To achieve consistency with the GR code, 23 zeros are leading both the separator and the eight bits of [N.sub.D] --1 itself for the pixels quantized with 8-bit depth; then, maximally 32 bits are needed in any case. A gain by the JPEG-LS GR code is obtained when the quotient is large enough, and the gain of the JPEG-LS GR code is six bits, which is six bits less than the GR code in this example.

Such a gain, however, does not always occur with the use of JPEG-LS GR coding. For example, a given number [47.sub.(10)] can be represented as follows:

[N.sub.B] = [00101111.sub.(2)]

For k = 1, its GR code is represented with 23 leading zeros, as follows:

[N.sub.GR] = [00000000000000000000000|1|1.sub.(2)]

However, the JPEG-LS GR code should be used whenever q [greater than or equal to] 23. The JPEG-LS GR code is, therefore, represented as follows:

[N.sub.LS] = [00000000000000000000000|1|00101110.sub.(2)]

It is obvious that the JPEG-LS GR code needs 32 bits while the GR code needs only 25 bits. Even though the JPEG-LS GR code is not always superior to the GR code, the former code is used in the JPEG-LS algorithm. The length of the JPEG-LS GR code that includes a prefix, a separator, and a suffix is always 32 bits. A combination of the [prefix and separator] of the JPEG-LS GR code is called the replaceable JPEG-LS GR prefix or replaceable prefix for short in this paper. This replaceable prefix consists of 24 bits that comprise 23 leading zeros plus the separator "1". The 8-bit suffix is called intact suffix in this paper. If the prefixes are replaceable, their associated suffixes are intact suffixes.

Notably, most images are quantized with eight bits per pixel and eight bits per color (such as red, green, and blue); however, some accurate images are quantized with 16 bits per pixel and 16 bits per color. In this case, the JPEG-LS GR code consists of a 47-bit prefix, a 1-bit separator, and a 16-bit suffix; therefore, the replaceable JPEG-LS GR prefix is 48 bits for the 16-bit-depth images.

3. Proposed Method

Both the run and regular modes are used for JPEG-LS. The run mode encodes the run length, which is the count of the same continuous values. Either GR or JPEG-LS GR code is used for each codeword when the regular mode is utilized, and this regular mode is the sole focus of this paper.

In this section, three contributions are introduced. First, the replacement of the replaceable JPEG-LS GR prefix with location information can reduce the codeword size. Second, the size of the location information itself can be reduced. Third, the intact suffix code size can also be reduced.

3.1 Use of Location Information & Occurrence Gain

Location information is a kind of side information to guarantee reversibility. The encoder and decoder can perform the same job if they share the same location information. If the encoder modifies the pixel values, the modification can cause an overflow or underflow error. Obviously, in that case, the encoder skips the pixel to avoide the causing of an error, and the pixel should be marked in the location map. The decoder also skips the decoding when it encounters the marked position. A set of the marked position information is called the location map.

The first contribution of this paper is the replacement of the replaceable prefixes. This paper identifies the possibility that the JPEG-LS GR codeword can still be shortened using a simple method; that is, the location information is used instead of the replaceable JPEG-LS GR prefix. Even though the replaceable prefix is removed, the intact suffix is not altered. The position information of the replaceable prefix will be used here instead of the lengthy JPEG-LS GR code.

The location map consists of the simple (row, col) coordinates of such JPEG-LS GR code in this paper. The map of each row and column are of an 8-bit length in the 256 x 256 images, while a 9-bit length applies for the 512x512 images. For the 256x256 images, the coding gains for each replaceable prefix are therefore 8 (i. e., 24 - 2 x 8) bits for the 8-bit-pixel depth, and 32 (i, e., 43 - 2 x 8) bits for the 16-bit depth. For the 512 x 512 images, the coding gains for each prefix are 6 (i. e., 24 - 2 x 9) bits for the 8-bit depth and 30 bits for the 16-bit depth. This location information is subsequent to the total number information of these locations at the beginning of the bitstream.

At a position (row, col) = (339, 211) of the 512x512 image in Table 1, for example, the JPEG-LS GR code is [00000000000000000000000|1|01101110.sub.(2)], and a replaceable prefix [000000000000000000000001.sub.(2)] is encountered. This prefix is removed during the proposed encoding and only the intact suffix of [01101110.sub.(2)] (i.e., [N.sub.D] - 1) remains. After removing the replaceable prefix, its position information of [101010011011010011.sub.(2)], which is equivalent to (339, 211), is recorded at the header of the bitstream and a coding gain of six bits is obtained. The replaceable prefixes are underlined in Table 1.

Let H and W be the height and width of the image, respectively. As long as the value [[log.sub.2] H] + [[log.sub.2]W] is smaller than 24 for the 8-bit depth, or less than 48 for the 16-bit depth, the replacement with the location map results in a coding gain; such a gain is called occurrence gain in this paper. Of course, the number of replaceable prefixes should be delivered to the decoder as a part of the side information.

3.2 Map Gain

The second contribution is a possible reduction of the location information itself. The position information of the first replaceable prefix is marked as it is because the reference information regarding the position is not available; however, for the rest of the replaceable prefixes, the information regarding the previous position is available. The available information can be exploited for the attainment of further gain. In the example in Table 1, four replaceable prefixes appear where the positions are (197, 256), (339, 211), (480, 290) and (480, 394); here, the row positions {197, 339, 480, and 480} are in an ascending order. For the first position (197, 256) for a 512 x 512 image, 18 (i.e., 9 plus 9) bits are needed to record [011000101100000000.sub.(2)]. The next position (339, 211) is [101010011011010011.sub.(2)]; here, because of the fact that 339 [greater than or equal to] 256, it is obvious that 339 is located in the second half (bottom part) of the image, and the subsequent row positions that are larger than 256 indicate that they are located in the second half. As a result, these rows are all marked as [1xxxxxxxx.sub.(2)]. Because both the encoder and the decoder recognize this fact, it is not necessary to encode the first bit of "1", and only the 8-bit [xxxxxxxx.sub.(2)] is needed without the "1" in this case; therefore, only the 17 (i.e., 8 plus 9) bits of [11100000100100010.sub.(2)] are recorded as the location information of (480, 290).

If a replaceable prefix is in the second half of the image, one bit of gain can be attained in the recording of the next piece of location information; similarly, if an i-th replaceable prefix is placed in the fourth quarter, two bits of gain can be attained in the recording of the position of the (i+1)-th prefix.

The column information in the same row can also be reduced by using a similar method because the columns of the same row are of an ascending order; therefore, the location information of (480, 394) in Table 1 is [1110000010001010.sub.(2)] in 16 (i.e., 8 plus 8) bits according to a referencing of the position information of (480, 290).

This type of gain is called map gain in this paper. Of course, the replaceable prefix positions occur randomly; therefore, such a gain is not always achieved.

3.3 K3 (or K10) Gain

The third contribution is a size reduction of the intact suffix. When the replaceable prefix is encountered for a pixel that is quantized by eight bits, the manifestation of the leading 23 zeros means that this sample is encoded by the JPEG-LS GR method, whereby the value of the quotient q [greater than or equal to] 23 and the suffix value is [N.sub.D] - 1; that is, the replaceable prefix does not occur whenever q < 23. By utilizing this fact, the divisor information k can be exploited to reduce the size of the intact suffix. With respect to k = 3 regarding the 8-bit pixel values, for example, the value range of the first five bits of any q is from 0 to 31 ; as a result, [N.sub.B] ranges from [00000xxx.sub.(2)] to 11111[xxx.sub.(2)], where [xxx.sub.(2)] stands for three bits of "don't care" binary numbers (i.e., remainders).

Regarding the quotient part, numbers from 0 to 22 do not appear when q [greater than or equal to] 23, and, in this case, numbers from 23 to 31 appear when k is 3; that is, only nine numbers are actually used. Thus, quotient values from 23 to 31 can therefore be reassigned to other values from 0 to 8, respectively. Table 2 shows the reassigned number representation.

A modified quotient of 0 is equivalent to the unmodified quotient value of 23, a modified quotient of 1 is equivalent to the unmodified quotient value 24, and so on. Only four bits are consequently needed to represent the nine numbers from 0 to 8 ([0000.sub.(2)] to [1000.sub.(2)]), rather than the use of five bits to represent numbers from 23 to 31 ([10111.sub.(2)] to [11111.sub.(2)]); moreover, one more bit can be saved here. Three bits are assigned to represent the numbers from 0 to 6, and four bits are assigned to represent 7 and 8.

[N.sub.B] is used rather than [N.sub.B] -- 1 to record the suffix in this case. The intact suffix of position (480, 290), for example, is [11101110.sub.(2)] in Table 1. The original [N.sub.B] = [11101110.sub.(2)] + 1 = [11101111.sub.(2)] can be split into two parts. If k is 3, then the unmodified-quotient part is [11101.sub.(2)] and the remainder part is [111.sub.(2)]. The unmodified-quotient part of [11101.sub.(2)] (i.e., [29.sub.(10)]) is modified to [110.sub.(2)] (i.e., [6.sub.(10)]) by the subtraction of 23. Through this modification, the intact suffix is changed to [110111.sub.(2)], which requires six bits rather than eight bits, and saves two bits. This type of gain is called K3 gain in this paper.

The same number of bits can be saved for the values that are quantized by a 16-bit depth with k = 10. Then, the [N.sub.B] ranges from 000000[xxxxxxxxxx.sub.(2)] to 111111[xxxxxxxxxx.sub.(2)] in normal case. Similarly, only 17 numbers from 101111[xxxxxxxxxx.sub.(2)] to 111111[xxxxxxxxxx.sub.(2)] are actually replaceable since the replaceable prefix does not occur whenever q < 47. As a result, the assignment of six bits is not required, but five or four bits are enough. Two bits can be saved by assigning short binary numbers from [0000.sub.(2)] to [1110.sub.(2)] (for the unmodified [47.sub.(10)] to [61.sub.(10)], respectively) or one bit can be saved by assinging [11110.sub.(2)] and [11111.sub.(2)] (for the unmodified [62.sub.(10)] and [63.sub.(10))], respectively) (See Table 3). This gain is called K10 gain in this paper.

4. Experiment Results

The performance of the proposed method was compared with that of the JPEG-LS algorithm (see Tables 4 to 8). A variety of uncompressed images ([24]-[25], Figs. 1 and 2) are used for the comparison; here, a few images do not have a replaceable prefix, while most of the images have a sufficient number of replaceable prefixes.

In the experiments, 12 gray-scale images of a 256x256 size and 12 gray-scale 512x512 images, all quantized by eight bits, are used; in addition, 8 color images of varying sizes that have been quantized by eight bits are used (see Fig. 1). The images quantized by 16 bits are shown in Fig. 2, and include 15 gray-scale images and 14 color images.

Before the compressed bitstream is recorded, the overhead representing the number of location information is first recorded.

For the lena (256 x256) image with an 8-bit pixel depth, the replaceable prefixes occur 20 times, and 160 bits (i.e., 20x8) can be reduced purely by the occurrence gain. For the recording of the 20 occurrences, five bits are needed to represent the number [20.sub.(10)] or [10100.sub.(2)], and this number of bits, five, is expressed as [0101.sub.(2)]. The entirety of the overhead information is therefore expressed with nine bits as [0101|10100.sub.(2)] and this overhead header is preserved at the beginning of the binary stream for this image.

Among the nine bits in the overhead header, the first four bits are used to represent the following number of bits representing the number of replaceable prefixes; therefore, the leading four bits can represent numbers from 0 [(0000.sub.(2)]) to 15 ([1111.sub.(2)]). The maximum number of overhead bits is 19 (four bits of leading "1111" plus 15 bits to represent the number of replaceable prefixes).

The exact output bitstream size of JPEG-LS depends on two kinds of zero padding. The first type pads a number of zeros at the end to make the bitstream size a multiple of eight; for example, when the actual output bitstream is [00000000110.sub.(2)] (11 bits), five zeros are padded to make 16 bits in total and the output is then [0000000011000000.sub.(2)]. The second type of zero padding occurs whenever the consecutive eight bits are all "1". For the bit stream [11111111110.sub.(2)], where the first eight bits are all "1", one zero is inserted as a delimiter and four zeros are padded to make [1111111101100000.sub.(2)]. Such a zero-padding rule is briefly stated to calculate the exact number of the output bits of the JPEG-LS algorithm.

For the lena image (256x256), the original GR and JPEG-LS GR output stream size without any padding is 299,901 bits, and 123 bits are added through the padding process to make 300,024 bits; notably, since 300,024 is a multiple of eight, the first type of zero padding is not necessary. In the pure output bit string of 299,901 bits, 123 cases of [11111111.sub.(2)] occurs, and the same number of zero bits are inserted as a second type of zero padding.

In the proposed method of this paper, nine bits of overhead header (i.e., "[0101|10100.sub.(2)]") are added to the pure JPEG-LS output of 299,901 bits; alternatively, 160 bits are reduced by the occurrence gain due to the 20 replaceable prefixes. In addition, six bits are reduced by the map gain; moreover, two bits are reduced by the K3 gain. The modified JPEG-LS output size is therefore 299,742 bits (i.e., 299, 901 +9-160-6-2). Regarding the 299,742 bits, since there are 122 consecutive eight "1"s, 122 zeros are inserted. As a result, the final output size of the modified JPEG-LS is 299,864 (i.e., 299,742 + 122) bits, which is the final result of the lena image because it is a multiple of eight, and this is slightly more favorable than that of the original JPEG-LS. In Table 4, 5 and 7, the numbers in the upper rows of the occurrence gain and the K3 gain (or K10 gain) are shown in bits, while the numbers in parenthesis in the lower rows indicate the number of occurrences of such gain.

For a few images, replaceable prefixes are not encountered; however, some images have a large number of replaceable prefixes. The artificial image (2,048 x3,072) that has been quantized by 16 bits (see Table 7) has 452,775 bits of occurrence gain meaning that the artificial image has 18,111 replaceable prefixes. Since the image size is 2,048x3,072, 23 bits are needed to mark the positions; therefore, the apparent occurrence gain is 25 bits (i.e., 48 - 23, where the replaceable prefix takes 48 bits for the 16-bit depth images). In this case, 19 bits are required as an overhead header to represent the 18,111 replaceable prefixes (i.e., the mandatory four bits to represent 15, and the next 15 bits to represent 18,111); therefore, the overhead header is represented as [1111|100011010111111.sub.(2)], which needs 19 bits in total. Notably, the artificial image is a synthetic image and not a natural one.

For the cameraman (256 x 256) image, 107 replaceable prefixes are encountered, and this means that 856 bits can be reduced; moreover, 32 bits are reduced due to the map gain, and 12 bits are reduced due to the K3 gain. As a result, the output size of the JPEG-LS and the proposed method are 282,488 bits and 281,576 bits, respectively. For the France image (496 x 672), 289 replaceable prefixes are found, while 112 bits and 33 bits are reduced as the map and K3 gains, respectively.

The clegg color image (880 x 814) in Table 6 has 7,872 bits of occurrence gain for the red channel, 6,832 bits for the green channel, and 8,456 bits for the blue channel, since the image has 1,968, 1,708, and 2,114 replaceable prefixes, respectively. For the red color, 7,872 bits, 1,669 bits, and 536 bits are the occurrence gain, map gain, and K3 gain, respectively. For the images quantized with 16 bits, the K10 gain is a counterpart of the K3 gain, as shown in Tables 7 and 8.

5. Conclusion and Discussion

In this paper, a new lossless compression method is proposed. When the codeword length is longer than the position information, the codeword can be replaced with a shorter piece of position information. JPEG-LS reference software uses either 24-bit or 48-bit replaceable prefixes to avoid the long codewords of the GR code; however, it is obvious that they are still long, and that replaceable prefixes of less than 24 bits or 48 bits can be used to enhance the compression rate. Future work includes the employment of various lengths of the replaceable prefix to maximize the performance. In this paper, the potential of the location information is manifested resulting in additional gains.

6. Acknowledgement

This work was supported in part by a National Research Foundation of Korea (NRF) grant funded by the Korean Government (MEST) (NRF-2015R1A2A2A01004587), and Korea University.

References

[1] M. J. Weinberger, G. Seroussi, and G. Sapiro, "The LOCO-I lossless image compression algorithm: Principles and standardization into JPEG-LS," IEEE Transactions on Image Processing, vol. 9, no. 8, pp. 1309-1324, Aug. 2000. Article (CrossRef Link)

[2] J. Rissanen and G. G. Langdon, Jr, "Universal modeling and coding," IEEE Transactions on Information Theory, vol. 27, pp. 12-23, Jan. 1981. Article (CrossRef Link)

[3] N. Merhav, G. Seroussi, and M.J. Weinberger, "Optimal Prefix Codes for Sources with Two-Sided Geometric Distributions," IEEE Transactions on Information Theory, vol. 46, no. 1, pp. 120-135, Jan. 2000. Article (CrossRef Link)

[4] S. A. Martucci, "Reversible compression of HDTV images using median adaptive prediction and arithmetic coding," in Proc. of IEEE International Symposium on Circuits and Systems, pp.1310-1313, 1990. Article (CrossRef Link)

[5] S. W. Golomb, "Run Length Encodings," IEEE Transactions on Information Theory, vol. 12, pp. 399-401, 1966. Article (CrossRef Link)

[6] R. F. Rice, "Practical Universal Noiseless Coding," in Proc. of SPIE 0207, Applications of Digital Image Processing III, 247, 1979. Article (CrossRef Link)

[7] V. P. Baligar, L. M. Patnaik, and G. R. Nagabhushana, "High compression and low order linear predictor for lossless coding of grayscale images," Image and Vision Computing, vol. 21, pp. 543-550, 2003. Article (CrossRef Link)

[8] S. Bedi, E. A. Edirisinghe, and G. Grecos, "Improvements to the JPEG-LS prediction scheme," Image and Vision Computing, vol. 22, pp. 9-14, Sep. 2004. Article (CrossRef Link)

[9] K. Horvath, H. Stogner, and G. Weinhandel, "Experimental study on lossless compression of biometric iris data," in Proc. of the 7th International Symposium on Image and Signal Processing and Analysis, pp. 379-384, Sep. 2011. Article (CrossRef Link)

[10] A. Khademi and S Krishnan, "Comparison of JPEG 2000 and other lossless compression schemes for digital mammograms," in Proc. of 27th Annual International Conference of the Engineering in Medicine and Biology Society, pp. 3771-3774, Jan. 2006. Article (CrossRef Link)

[11] J. Kim and C. M. Kyung, "A lossless embedded compression using significant bit truncation for HD video coding," IEEE Transactions on Circuits and Systems for video technology, vol. 20, no. 6, Jun. 2010. Article (CrossRef Link)

[12] G. Deng, H. Ye, and L. Cahill, "Adaptive techniques for lossless data compression," in Proc. of the Australia and New Zealand Conference on Intelligent Information Systems, pp. 345-350, 2001. Article (CrossRef Link)

[13] A. Martchenko and G. Deng, "Bayesian predictor combination for lossless image compression,"

IEEE Transactions on Image Processing, vol.22, pp.5263-5270, 2013. Article (CrossRef Link)

[14] A. Masmoudi, W. Puech, and A. Masmoudi, "An improved lossless image compression based arithmetic coding using mixture of non-parametric distributions," Multimedia Tools and Applications, vol. 74, no. 23, pp. 10605-10619, 2015. Article (CrossRef Link)

[15] S. Zhao, Y. Xu, H. Li, and H. Yang, "A comparison of lossless compression methods for palmprint images," Journal of Software, vol. 7, no. 3, pp.594-598, Mar. 2012. Article (CrossRef Link)

[16] T. Starosolski, "Simple fast and adaptive lossless image compression algorithm," Software: Practice and Experience, vol. 37, no. 1, pp. 65-91, Jan. 2007. Article (CrossRef Link)

[17] X. Wu and N. Memon, "Context-based, adaptive, lossless image codec," IEEE Transactions on Communications, vol. 45, no. 4, pp. 437-444, Apr. 1997. Article (CrossRef Link)

[18] B. G. Mobasseri, R. J. Berger, M. P. Marcinak, and Y. J. NaikRaikar, "Data embedding in JPEG bitstream by code mapping," IEEE Transactions on Image Processing, vol. 19, no. 4, pp. 958-966,

Apr. 2010. Article (CrossRef Link)

[19] Z. Qian and X. Zhang, "Lossless data hiding in JPEG bitstream," Journal of Systems and Software, vol. 85, no. 2, pp. 309-313, Feb. 2012. Article (CrossRef Link)

[20] J. J. Ding, W. Y. Wei, and G. C. Pan, "Modified Golomb coding algorithm for asymmetric two-sided geometric distribution data," in Proc. of The 20th European Signal Processing Conference, pp.1548-1552, 2012. Article (CrossRef Link)

[21] J. Tian, "Reversible data embedding using a difference expansion," IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 8, pp. 890-896, Aug. 2003. Article (CrossRef Link)

[22] Z. Ni, Y.-Q. Shi, and N. Ansari, "Reversible data hiding," IEEE Transactions on Circuits and Systems for Video Technology, vol. 16, no. 3, pp. 354-362, Mar. 2006. Article (CrossRef Link)

[23] H.J. Kim, V. Sachnev, Y. Q. Shi, J. Nam, and H. G. Choo, "A novel difference expansion transform for reversible data embedding," IEEE Transactions on Information Forensics and Security, vol. 3, no. 3, pp. 1147-1156, Sep. 2008. Article (CrossRef Link)

[24] http://links.uwaterloo.ca/Repository.html

[25] http://imagecompression.info/test_images

[26] http://www.stat.columbia.edu/~jakulin/jpeg-ls/mirror.htm

[27] http://kr.mathworks.com/matlabcentral/fileexchange/53039-jpegls-codec

Jae Hyeon Woo (1), Hyoung Joong Kim (1)

(1) Graduate School of Information Security Korea University Seoul 136-701, Korea

(1) [e-mail: {bull0330, khj-}@korea.ac.kr]

(*) Corresponding author: Hyoung Joong Kim

Received July 11, 2016; revised September 2, 2016; accepted October 2, 2016; published November 30, 2016

Jae Hyeon Woo received a B.S. degree in Mechanical Engineering and a M.S. degree in Electrical and Computer Engineering from Seoul National University, Seoul, Korea, in 1996, 2002, respectively. He joined Multimedia Security Laboratory at the Center of Information Security and Technology (CIST), Graduate School of Information Management and Security, Korea University, Seoul, Korea in 2007, where he is currently pursuing Ph.D. His research interests include multimedia security, reversible and robust watermarking, steganography, phychology, and big-data.

Hyoung Joong Kim received his B.S., M.S., and Ph.D. degrees from Seoul National University, Seoul, Korea, in 1978, 1986, and 1989,respectively. He joined the faculty of the Department of Control and Instrumentation Engineering, Kangwon National University, Korea, in 1989. He is currently a Professor of the Graduate School of Information Management and Security, Korea University, Korea since 2006. His research interests include parallel and distributed computing, multimedia computing, multimedia security, and big-data.

Table 1. Example of the JPEG-LS codewords for a 512 X 512 image

Position    [N.sub.D]  k    Prefix                   Separator

  (0, 0)     33        2    00000000                 1

(197, 256)   84        1    00000000000000000000000  1

(339, 211)  111        2    00000000000000000000000  1

(480, 290)  239        3    00000000000000000000000  1

(480, 394)  139        0    00000000000000000000000  1
            ...        ...  ...                      ...
(511, 511)  ...        ...  ...                      ...

Position    Suffix

  (0, 0)      01

(197, 256)  01010011

(339, 211)  01101110

(480, 290)  11101110

(480, 394)  10001010
            ...
(511, 511)  ...

Table 2. q representation method with K3 gain in 8-bit image

Unmodified q  Bit expression  Modified q  Recorded bits

23            10111           0            000
24            11000           1            001
25            11001           2            010
26            11010           3            011
27            11011           4            100
28            11100           5            101
29            11101           6            110
30            11110           7           1110
31            11111           8           1111

Table 3. q representation method with K10 gain in 16-bit image

Unmodified q  Bit expression  Modified q  Recorded bits

47            101111           0            0000
48            110000           1            0001
49            110001           2            0010
...              ...         ...             ...
59            111011          12            1100
60            111100          13            1101
61            111101          14            1110
62            111110          15           11110
63            111111          16           11111

Table 4. Result of 8-bit Gray Images I.

Image                                  map        K3
(HxW)                  occurrence      gain       gain

bird                   gain             0 bits z   0 bits z
(256 x 256)              8 bits (1)
bridge (256 x 256)     152 bits (19)    0 bits     0 bits
cameraman (256 x 256)  856 bits (107)  32 bits    22 bits (12)
circles (256 x 256)     24 bits (3)     0 bits     0 bits
corsses (256 x 256)     48 bits (6)     2 bits     0 bits
goldhill (256 x 256)    64 bits (8)     2 bits     2 bits (1)
horiz (256 x 256)       56 bits (7)     4 bits     0 bits
lena (256 x256)        160 bits (20)    6 bits     2 bits (1)
montage (256 x 256)    504 bits (63)   34 bits     6 bits (3)
slope (256 x 256)      648 bits (81)   49 bits     8 bits (4)
squares (256 x 256)     24 bits (3)     0 bits     0 bits
text (256 x 256)       184 bits (23)   11 bits     0 bits

Image                            output bits
(HxW)                  Original  JPEG-LS      Proposed

bird                   524,288   227,272      227,264
(256 x 256)
bridge (256 x 256)     524,288   379,264      379,128
cameraman (256 x 256)  524,288   282,488      281,576
circles (256 x 256)    524,288     9,784        9,768
corsses (256 x 256)    524,288    25,048       25,008
goldhill (256 x 256)   524,288   345,896      345,840
horiz (256 x 256)      524,288     5,928        5,880
lena (256 x256)        524,288   300,024      299,864
montage (256 x 256)    524,288   178,240      177,712
slope (256 x 256)      524,288   102,760      102,064
squares (256 x 256)    524,288     4,840        4,824
text (256 x 256)       524,288   106,728      106,536

Table 5. Result of 8-bit Gray Images II.

Image                 occurrence         map       K3
(HxW)                 gain               gain      gain

barb (512 x 512)        132 bits (22)     11 bits   0 bits
boat (512 x 512)         84 bits (14)      2 bits   2 bits (1)
France (496 x 672)    1,445 bits (289)   112 bits  65 bits (33)
frog (498 x 621)         60 bits (12)      3 bits   2 bits (1)
goldhill (512 x 512)     24 bits (4)       1 bits   0 bits
lena (512 x 512)         72 bits (12)      6 bits   0 bits
library (352 x 464)     624 bits (104)    50 bits  37 bits (20)
mandrill (512 x 512)    492 bits (82)      0 bits   6 bits (3)
mountain (480 x 640)    885 bits (177)    99 bits  68 bits (39)
peppers (512 x 512)     126 bits (21)      6 bits   2 bits (1)
washsat (512 x 512)      36 bits (6)       1 bits   0 bits
zelda (512 x 512)         6 bits (1)       0 bits   0 bits

Image                            output bits
(HxW)                 Original   JPEG-LS      Proposed

barb (512 x 512)      2,097,152  1,240,584    1,240,448
boat (512 x 512)      2,097,152  1,113,832    1,113,752
France (496 x 672)    2,666,496    470,664      469,048
frog (498 x 621)      2,474,064  1,870,432    1,870,368
goldhill (512 x 512)  2,097,152  1,234,912    1,234,896
lena (512 x 512)      2,097,152  1,112,240    1,112,176
library (352 x 464)   1,306,624    832,936      832,240
mandrill (512 x 512)  2,097,152  1,582,216    1,581,728
mountain (480 x 640)  2,457,600  1,972,616    1,971,592
peppers (512 x 512)   2,097,152  1,176,472    1,176,344
washsat (512 x 512)   2,097,152  1,082,256    1,082,232
zelda (512 x 512)     2,097,152  1,049,760    1,049,752

Table 6. Result of 8-bit Color Images.

Image         occurrence  map     K3                 output bits
(HxW)              gain        gain    gain   Original    JPEG-LS

               R  7,872       1,669     965  5,730,560   1,703,848
               G  6,832       1,045     515  5,730,560   1,794,640
clegg          B  8,456       1,479     988  5,730,560   1,783,608
(880 x 814)    R  4,268          64   1,185  9,883,120   2,431,024
frymire        G  4,224         172     993  9,883,120   2,609,960
(1105 x 1118)  B  3,818         108     906  9,883,120   2,459,416
               R     18           0       0  2,097,152   1,060,280
               G    102           6       0  2,097,152   1,207,568
lena           B    192           0       8  2,097,152   1,284,120
(512 x 512)    R    530          61       6  3,145,728   1,469,288
monarch        G    445          45      14  3,145,728   1,469,056
(512 x 768)    B    415          38      12  3,145,728   1,510,704
               R    114           7       1  2,097,152   1,034,904
peppers        G    108          16       2  2,097,152   1,019,296
(512 x 512)    B    150          16       2  2,097,152   1,029,288
               R    110           3       4  3,145,728   2,060,152
               G    100           0       0  3,145,728   2,042,296
sail           B     95           5       0  3,145,728   2,050,112
(512 x 768)    R  2,972         247     235  3,995,408     826,480
serrano        G  3,104         319     304  3,995,408     867,944
(794 x 629)    B  2,204         254     269  3,995,408     665,408
               R    155           9       0  3,145,728   1,578,680
tulips         G    125           8       0  3,145,728   1,656,520
(512 x 768)    B    160          15       2  3,145,728   1,701,432


Image          Proposed
(HxW)
               1,693,352
clegg          1,786,264
(880 x 814)    1,772,808
frymire        2,425,608
(1105 x 1118)  2,604,648
               2,454,648
               1,060,272
lena           1,207,472
(512 x 512)    1,283,944
monarch        1,468,712
(512 x 768)    1,468,576
               1,510,240
peppers        1,034,784
(512 x 512)    1,019,176
               1,029,120
               2,060,040
sail           2,042,208
(512 x 768)    2,050,024
serrano          823,072
(794 x 629)      864,240
                 662,680
tulips         1,578,520
(512 x 768)    1,656,400
               1,701,272

Table 7. Result of 16-bit Gray Images.

Image               occurrence  map       K10
(H x W)             gain        gain      gain   Original

artificial           452,775    22,765     6     100,663,296
(2048 x 3072)        (18,111)             (3)
big building           5,060         0     0     624,847,872
(5412 x 7216)           (230)
big tree                 198        18     0     443,206,400
(4550 x 6088)             (9)
bridge                   120        12     0     178,091,216
(4049 x 2749)             (5)
cathedral              1,225        84     2      96,256,000
(3008 x 2000)            (49)             (1)
deer                     240         0     0     170,841,008
(2641 x 4043)            (10)
fireworks              4,464       101     0     118,013,952
(2352 x 3136)           (186)
flower foveon          1,375        20     0      54,867,456
(1512 x 2268)            (55)
hdr                      550        28     0     100,663,296
(2048 x 3072)            (22)
leaves iso 200         3,350       125     4      96,256,000
(2000 x 3008)           (134)             (2)
leaves iso 1600        3,075       168     4      96,256,000
(2000 x 3008)           (123)             (2)
nightshot iso 100        648         9     0     118,013,952
(2352 x 3136)            (27)
nightshot iso 1600     2,808        60     0     118,013,952
(2352 x 3136)           (117)
spider web               575        12     0     193,937,408
(2848 x 4256)            (25)
zone_plate             1,675        30    56      96,000,000
(2000 x 3000)            (67)            (30)

Image               output bits
(H x W)             JPEG-LS      Proposed

artificial           27,167,728   26,692,336
(2048 x 3072)
big building        451,339,088  451,334,028
(5412 x 7216)
big tree            324,584,184  324,583,986
(4550 x 6088)
bridge              135,643,808  135,643,688
(4049 x 2749)
cathedral            69,526,592   69,525,296
(3008 x 2000)
deer                136,309,472  136,309,240
(2641 x 4043)
fireworks            60,353,296   60,348,744
(2352 x 3136)
flower foveon        33,892,768   33,891,376
(1512 x 2268)
hdr                  62,900,288   62,899,720
(2048 x 3072)
leaves iso 200       70,434,464   70,431,000
(2000 x 3008)
leaves iso 1600      74,955,104   74,951,864
(2000 x 3008)
nightshot iso 100    72,684,152   72,683,504
(2352 x 3136)
nightshot iso 1600   88,672,408   88,669,552
(2352 x 3136)
spider web          111,630,984  111,630,400
(2848 x 4256)
zone_plate           95,673,640   95,671,872
(2000 x 3000)

Table 8. Result of 16-bit Color Images.

Image                  occurrence  map       K10
(H x W)             C  gain        gain      gain  Original

artificial          R  440,400     22,646    14    100,663,296
(2048 x 3072)       G  455,325     22,522     5    100,663,296
                    B  392,650     23,018     6    100,663,296
                    R    1,210          0     0    624,847,872
big_building        G    7,568          2     0    624,847,872
(5412 x 7216)       B      990          6     2    624,847,872
                    R      198          0     2    443,206,400
big_tree            G    1,254          6     0    443,206,400
(4550 x 6088)       B      176          0     7    443,206,400
                    R    1,056         37     0    178,091,216
bridge              G       48          3     0    178,091,216
(4049 x 2749)       B        0          0     0    178,091,216
                    R    2,125        172     6     96,256,000
cathedral           G    2,450        204     0     96,256,000
(3008 x 2000)       B    3,025        352     0     96,256,000
                    R       72          0     0    170,841,008
deer                G        0          0     0    170,841,008
(2641 x 4043)       B        0          0     0    170,841,008
                    R    3,864         63     0    118,013,952
fireworks           G    2,424          0     4    118,013,952
(1512 x 2268)       B    7,104         27     0    118,013,952
                    R       50          0     0     54,867,456
flower_foveon       G    1,025         18     0     54,867,456
(1512 x 2268)       B        0          0     0     54,867,456
hdr                 R      300         22     0    100,663,296
(2048 x 3072)       G      250         15     0    100,663,296
                    B      175         11     2    100,663,296
leaves_iso_200      R    2,550        118    15     96,256,000
(2000 x 3008)       G    5,150        251     2     96,256,000
                    B    1,700         58     8     96,256,000
leaves_iso_1600     R      425         11     9     96,256,000
(2352 x 3136)       G    4,025        235     6     96,256,000
                    B      450         13     2     96,256,000
nightshot_iso_100   R    1,080          9     0    118,013,952
(2352 x 3136)       G    1,056         18     0    118,013,952
                    B    1,944         48     0    118,013,952
nightshot_iso_1600  R       72          0     0    118,013,952
(2352 x 3136)       G    2,928          9     0    118,013,952
                    B    2,712          3     0    118,013,952
                    R      115          0     0    193,937,408
spider_web          G      529          8     0    193,937,408
(2848 x 4256)       B      207          2     0    193,937,408

Image                 output bits
(H x W)               JPEG-LS      Proposed

artificial             27,622,520   27,159,592
(2048 x 3072)          26,097,064   25,619,352
                       22,666,056   22,250,512
                      471,972,608  471,971,398
big_building          446,166,904  446,159,336
(5412 x 7216)         457,438,424  457,437,434
                      338,047,656  338,047,458
big_tree              316,958,648  316,957,394
(4550 x 6088)         356,661,248  356,661,072
                      137,191,176  137,190,088
bridge                139,260,144  139,260,096
(4049 x 2749)         141,927,112  141,927,120
                       72,049,384   72,047,096
cathedral              65,756,096   65,753,448
(3008 x 2000)          69,606,856   69,603,488
                      136,085,256  136,085,192
deer                  143,742,960  143,742,968
(2641 x 4043)         147,174,488  147,174,496
                       65,342,088   65,338,176
fireworks              50,603,008   50,600,600
(1512 x 2268)          30,611,824   30,604,712
                       34,634,848   34,634,800
flower_foveon          25,886,872   25,885,840
(1512 x 2268)          34,599,072   34,599,072
hdr                    64,317,448   64,317,136
(2048 x 3072)          64,468,512   64,468,256
                       66,914,480   66,914,288
leaves_iso_200         71,013,008   71,010,336
(2000 x 3008)          70,067,784   70,062,400
                       69,239,256   69,237,488
leaves_iso_1600        76,392,784   76,392,352
(2352 x 3136)          74,091,952   74,087,696
                       73,353,248   73,352,800
nightshot_iso_100      74,671,984   74,670,904
(2352 x 3136)          71,826,064   71,825,000
                       60,798,592   60,796,608
nightshot_iso_1600     90,512,384   90,512,320
(2352 x 3136)          86,662,496   86,659,568
                       80,695,226   80,668,410
                      114,490,864  114,490,752
spider_web            111,667,024  111,666,496
(2848 x 4256)         114,798,856  114,798,656
COPYRIGHT 2016 KSII, the Korean Society for Internet Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Woo, Jae Hyeon; Kim, Hyoung Joong
Publication:KSII Transactions on Internet and Information Systems
Article Type:Report
Date:Nov 1, 2016
Words:7808
Previous Article:Crowd activity classification using category constrained correlated topic model.
Next Article:A two-stage cascaded foreground seeds generation for parametric min-cuts.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters