# Indicator elimination for locally adaptive scheme using data hiding technique.

1. IntroductionModern computer systems become ever more powerful due to advances in the design and development of all aspects of information technology such as, the increasing size of mass storage, and the high speed of processing and transmission. Another advance is that multimedia data is easier to create than before and thus the large size of multimedia becomes the main burden for using, processing, and delivering the multimedia data. Thus, finding ways to effectively reduce the size of multimedia has become an important research issue in recent years. Multimedia includes various representations such as image, audio, video, text, etc. Because of the sensitivity of the human senses and the fact that multimedia consists of a large number of redundant spaces, multimedia data can be reduced, yet without losing acceptable quality.

Images are one of the most popular forms of multimedia in common usage. An image can be created by using computer software, cameras, scanners, etc. "Lossy" and "lossless" are the two data encoding methods in image compression field, where these techniques are used to reduce amount of data of an image, audio or other related multimedia. [1] [2] [3] The lossless image compression is more concerned about the visual quality of the compressed image rather than the performance of the compression rate. In other words, the decompressed image must be the same as the original image.

Lossy image compression is also an important technique for reducing the size of the image file and many lossy image compression techniques have been presented in recent years, for instance JPEG [4], vector quantization (VQ) [5], etc. For lossy image compression, a reduction in image size is more important than maintaining the visual quality. Lossy image compression techniques allow the decompressed image to contain tiny distortions that, due to the sensitivity of the human eye, are hard to distinguish.

The concept of VQ is to divide an image into non-overlapping blocks and compress these blocks with a pre-trained codebook. Here, the pre-trained codebook is trained by using any codebook algorithm (e.g. the LBG algorithm [6]). The compression rate depends on the size of the codebook and the size of codeword. For instance, if a grayscale image sized 256 x 256 is compressed by VQ with a 256 codeword codebook and a codeword size of 16 pixels, then the compression rate is (((256 x 256)/16) x 8)/(256 x 256 x 8) = 0.0625.

Side match vector quantization (SMVQ) [7] is one of the compression methods to further improve the visual quality and the compression rate of VQ. Because of the characteristics of the natural image, a local area of an image has similar pixel distribution; SMVQ uses reconstructed neighboring blocks to predict the possible codewords for encoding a block.

Search-order coding (SOC) [8] was first proposed in 1996. The main idea of SOC is to encode a block by referring to a block which has the same VQ index value as the current encoding block. According to SOC design, if a current encoding block has a neighboring block with the same value (as the current encoding block), then the current block is encoded by using the search-order number. In order to avoid ambiguities, extra indicators are needed to record the source of the encoding codewords.

A locally adaptive scheme (LAS) [2] is also an image compression method that is based on the concept of local adaptively [9] [10]. The main idea of a LAS is to divide a VQ index table into non-overlapping blocks and, using a history list with "moving to the front" strategy, to improve the performance in terms of compression rate. The LAS method requires indicators to indicate the sources of encoding codeword.

This paper presents an indicator elimination method to improve the performance of the LAS method in terms of compression rate, because the indicators of LAS influence compression rate improvement.

We were inspired by a data hiding technique to design an effective compression method to eliminate the indicators of LAS; the purpose of the proposed method is to improve the compression rate of traditional LAS. Data hiding techniques [11-21] use a cover media to carry secret data and deliver it over a public computer network. The method proposed in this paper integrates a dissimilar pairing concept and side match vector quantization concept to conceal indicators of LAS into compression code to improve the performance of the compression rate. From the experimental results, the proposed method successfully achieves the goal of compression rate improvement.

The rest of this paper is organized as follows. Related work is introduced in Section 2. The proposed method is presented in Section 3. Section 4 summarizes the experimental results and conclusions are drawn in Section 5.

2. Related Work

Vector quantization (VQ) is a lossy image compression technique. Here, the file size of image can be significantly reduced by encoding index table which generated by VQ compression. Therefore, the storage requirement of an image can be saved. Fig. 1 shows the VQ encoding and decoding processes. Let a codebook Y = {[y.sub.i]|i = 0, 1,..., m-1} contains m codewords and each codeword contains k x k dimensions. The key steps of VQ compression are summarized as follows: First, the image I is divided into non-overlapping blocks sized k x kpixels and denoted as I = {[B.sub.i]|I = 0, 1,..., M-1}, where M is the total number of blocks of I. Second, to encode blocks Bi, find a codewordymin which has the smallest distance between the codeword and Bi. The codeword [y.sub.min can be found by using Eq. (1).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (1)

where [y.sub.min] is the found codeword which is most similar to the encoding block [B.sub.i]. [B.sub.i](j) and [y.sub.v](j) represent the j-th pixel [B.sub.i] and [y.sub.v], respectively. Third, [B.sub.i] is encoded by using the index of [y.sub.min]. After all the blocks have been encoded, the index table is the compression code. The decoding process uses the index in the table to lookup a decoding codeword from the codebook to reconstruct the block. Here, the codebook in the decoding phase is the same as the codebook used in the encoding phase. For instance, if a grayscale image sized 256 x 256 is compressed by VQ with a 256 codewords codebook and a codeword size of 16 pixels, then the compression rate is (total bits of index table)/(total bits of original image) = (((256 x 256)/16) x 8)/(256 * 256 * 8) = 0.0625.

Line and Chang presented a data hiding technique by using the concept of de-clustring [11]. Lin and Chang's method can effectively embed secret data into the compression code and the original VQ index table can be approximately restored when the secret data has been extracted.

2.2 Side-match Vector Quantization (SMVQ)

Side-match vector quantization (SMVQ) is a VQ-based lossy image compression method. The concept of SMVQ is to use the characteristics of a natural image to improve the visual quality of the decompressed image. The characteristic of the natural image means that the pixels of a local area have a similar distribution. Fig. 2 illustrates the concept of the SMVQ. In Fig. 2, the block B, is the current encoding block and the neighboring border vector (NBV) of block B, is defined by NBV = {[x.sub.0] = ([u.sub.12] + [l.sub.3])/2, [x.sub.1] = [u.sub.13], [x.sub.2] = [u.sub.14], [x.sub.3] = [u.sub.15], [x.sub.4] = [l.sub.7], *, *, *, [x.sub.8] = [l.sub.11], *, *, *, [x.sub.12] = [l.sub.15], *, *, *} which is obtained from B/s upper-side (i.e., block U) and left-side (i.e., block L), where the element '*' means; do not care.

The key steps of SMVQ are summarized as follows: First, for current encoding block [B.sub.i], determine 5 candidate codewords to form a state codebook by using [B.sub.i]'s NBV. Here, the candidate codeword selection is used to compute the distance between NBV and codeword in Y (i.e., Eq. (2)).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (2)

where v is the index value of codewords in the codebook. Here, the state codebook is denoted as SCB = {sc[w.sub.i], | i = 0, 1,..., s-1}. Second, a closest codeword of B, can be found by calculating the distance (i.e., Eq. (3)) between [B.sub.i] and the codeword in SCB. If the distance between [B.sub.i] and sc[w.sub.min] is smaller than a predefined threshold, then the block [B.sub.i] is encoded by SMVQ; otherwise, the block B, is encoded by VQ.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3)

2.3 Locally Adaptive Scheme (LAS)

In 1997, Chang et al. proposed a locally adaptive scheme (LAS) image compression to improve the performance of VQ in terms of compression rate [9]. The main idea of the LAS is to use a history list to play as a codebook cache of codebook and used it to further reduce the size of the compression code. The key steps of the LAS's method are summarized as follows: first, the index table is partitioned into non-overlapping blocks sized k x k index values. Second, for the current encoding index, check the index value in the history list. If the list contains the same index value, then use the sequence number of index value in the list to encode the index value and move the index value to the front of the list. On the Contrary, if the list has no the index the same with as the current encoding index, then add the current encoding index into the front of the list staying the front. In order to distinguish the confusing indicators with two different cases, one more bit as indicator is needed to put in front of the codeword, to ensure that the correct encoded codes can be retrieved as the same of original one. For instance, if an index can be encoded by using LAS, then the indicator is set as '1'; otherwise, the indicator is set as '0'.

The decoding process is the reverse work of the encoding process. If an indicator taken from compression code equals to '0', then the following [[log.sub.2] n] bits are taken from the compression code to form the VQ codeword index, which is used to reconstruct the decoding block and to add the index into the history list. Here, n is the number of codewords in the codebook. If the indicator is equals to '1', then the following ["[log.sub.2] m] bits are taken from the compression code to form the sequence number in index stay in the history list. Note that, m is the size of the history list. According to the sequence number, the codeword index can be found from the history and used it to reconstruct the image block. Also, the corresponding index is moved to the front of the history list.

For example, if a block of VQ index table sized 4 x 4 is B = {31, 207, 207, 213, 31, 207, 207, 207, 31, 211, 8, 8, 35, 31, 7, 7}, according to the LAS encoding rule, the history index list = {7, 31, 35, 8, 211, 207, 213}. Also, every index value is concatenated with one indicator. So the compression code is "0 00011111 0 11001111 1 0 0 11010101 1 10 1 10 1 00 1 00 1 01 0 11010011 0 00001000 1 000 0 00100011 1 011 0 00000111 1 000".

In the LAS decoding rule the indicator is taken from the compression code which is used to indicate the source of the decoding codeword. Tables 1 and 2 show the entire encoding and decoding process.

3. The Proposed Scheme

As mentioned above, the LAS method requires an indicator to indicate the source of a codeword which decreases the benefits of LAS compression. Thus, an indicator elimination method is proposed to further improve the performance of LAS in terms of the compression rate. The proposed method adopts the concept of a data hiding technique to conceal indicators in the compression code. The proposed method uses a sorted codebook to encode image blocks. Here, any sorting method can be used to sort the codebook. A characteristic of a sorted codebook is that any two adjacent codewords are similar to each other. Before applying the proposed indicator elimination encoding, an image I = {[p.sub.i] | i = 1, 2,..., N} sized N pixels is first compressed by VQ, and an index table T = {[b.sub.i] | i = 1, 2,..., NB} where NB is the total number of blocks is used.

3.1 Scan Order and History List

The traditional LAS method divides the index table into none overlapping blocks which are independent from each other. The LAS method transgresses the characteristic of natural images; that is the local area has a similar pixel distribution. The proposed method accommodates the characteristic to further improve the performance of LAS in terms of compression rate by adopting the Fractal-Hilbert-curve scan order (as shown in Fig. 3). Any scan order (e.g., Parallel-scan, Zig-Zag scan, N-scan, Fractal-Hilbert-curve) can be adopted in the proposed method. The reason the proposed method chose the Fractal curve scan order is that the Fractal curve scan order can achieve a better compression rate. Furthermore, the proposed method maintains a history list during the compression and the content of the list is updated by adopting a First-In-First-Out (FIFO) operation.

The history list is sorted by using decreasing order and denoted as H = {[cw.sub.k] | k = 0, 1,..., h-1}. Note that, the first and last element in the list (i.e., 0 and [N.sub.h]-1) are reversed for handling special cases. Here, [N.sub.h] represents the size of the history list. Many history lists maintain strategies can be adopted in the proposed method. The maintain rule of the proposed method is to remove an "oldest" element in the list when a new index is add into a full history list. Here, the oldest means the element that has been in the list the longest time.

3.2 The Encoding Phase

The proposed indicator elimination from LAS encoding is inspired from Chang and Lin's method [11]. Chang and Lin proposed a data hiding technique to conceal secret data in a VQ index table to achieve the goal of secret data delivery. In the proposed method a side-match-distortion function (SMD) is adopted to conceal the indicators in the compression code, to achieve the goal of indicator elimination.

Note that the first block (i.e., [b.sub.1]) is set as a seed block and encoded by VQ. Before adopting the encoding procedure, the codewords remaining in the VQ codebook and history list are paired. The paring strategy is to sort the codewords in the codebook and to divide the codebook into two parties. The pairing rule is ([cw.sub.1], [cw.sub.N/2]), ([cw.sub.2], [cw.sub.N/2+1]),..., ([cw.sub.N/2-1], [cw.sub.N-2]). Fig. 4 illustrates the example for the codeword pairing. The codewords remaining in the same pair are dissimilar to each other. For simplicity, ([alpha], [beta]) represents a selected codeword pair.

First, the index values are added into the list until the list is full. After that, the current encoding block [b.sub.i] is either encoded by VQ or LAS. The proposed method adopts the side-match distortion (SMD) function to achieve indicator elimination. Because several scan orders can be used in the encoding phase, the SMD function needs to choose different temporal pixels from [b.sub.i]. Here [GAMMA] is used to denote the set of temporal pixels. According to different scan orders for encoding, block [b.sub.i] will stay as one of fifteen types (the types are summarized in Table 3).

The SMD function is defined as follows,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (4)

where [alpha] and [beta] represent two different blocks reconstructed by the pairing codewords, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the nearboaring block of the current block b (see L and U in Fig. 2 (a)), [GAMMA] is the location set of current block [b.sub.i], which locatons are closed to the nearboaring blocks.

One example of two blocks with two paring words 4 and 131 are shown in Fig. 2 (b). The location set [GAMMA] are {0, 1, 2, 3, 4, 8, 12}, the pixel value of block [alpha] with corresponding location are {39, 42, 47, 52, 51, 57, 98}, and the value of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are {(36 + 59)/2, 90, 120, 37, 51, 57, 98}. Then the [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be calculated by the distance measure with [alpha] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] using (4), 5554 = [[absolute value of 39 - 47.5].sup.2] + [[absolute value of 42 - 90].sup.2] + [[absolute value of 47 - 120].sup.2] + [[absolute value of 52 - 37].sup.2] + [[absolute value of 51 - 51].sup.2] + [[absolute value of 57 - 57].sup.2] + [[absolute value of 98 - 98].sup.2]. Also, the [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] value can be obtained in the same procedure.

According to the source of current encoding block bi and next block [b.sub.i+1], the encoding situation can be divided into the following cases:

Case 1: if IND([b.sub.i]) = IND([b.sub.i+1]) = '0' (i.e., the block [b.sub.i+1] cannot be encoded by LAS) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [b.sub.i] is encoded by using [alpha].

Case 2: if IND([b.sub.i]) = IND([b.sub.i+1]) = '0' and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [b.sub.i] is encoded by using 0 [parallel] [alpha].

Case 3: if IND([b.sub.i]) = '0', IND([b.sub.i+1]) = '1' (i.e., the block [b.sub.i+1] can be encoded by LAS) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [b.sub.i] is encoded by using [beta].

Case 4: if IND([b.sub.i]) = '0', IND([b.sub.i+1]) = '1' and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [b.sub.i] is encoded by using m - 1 [parallel] [alpha].

Case 5: if IND([b.sub.i]) = '1', IND([b.sub.i+1]) = '0' (i.e., the block [b.sub.i] and [b.sub.i+1] are encoded by LAS and VQ, respectively) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [b.sub.i] is encoded by using [[alpha].sub.h].

Case 6: if IND([b.sub.i]) = '1', IND([b.sub.i+1]) = '0' and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [b.sub.i] is encoded by using 0 [parallel] [[alpha].sub.h].

Case 7: if IND([b.sub.i]) = IND([b.sub.i+1]) = '1' (i.e., the block [b.sub.i] and [b.sub.i+1] are both encoded by LAS) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [b.sub.i] is encoded by using [[beta].sub.h].

Case 8: if IND([b.sub.i]) = IND([b.sub.i+1]) = '1' and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [b.sub.i] is encoded by using [N.sub.h-1] [parallel] [[alpha].sub.h].

Table 4 summarizes all possible cases of the proposed encoding rules.

The key steps of the proposed encoding method are summarized in the following procedure.

Example: LAS Indicator Elimination Encoding

From Table 5, the k-th~(k+4)-th VQ index list is L = {..., 31, 29, 31, 35, 31,...} and the corresponding SMD value are {..., 0, 1, 1, 1, 0,...}. Also, the sample of (k-1)-th history list is known and shown in Fig. 5. Based on this information, the concatenated compression code is "... 111 010 [parallel] 001 [parallel] 010 [parallel] 00100011 [parallel] 00000000 00100010"

3.3 The Decoding Phase

The decoding procedure is the reverse of the encoding procedure. The image can be decompressed by applying the proposed decoding procedure to extract the indicator embedded in the compression code. The key steps of the proposed decoding procedure are described as follows: First, the seed blocks are reconstructed by taking the indices values from the compression code. Before the history list is full, the blocks belong to the seed blocks. In other words, the seed blocks are reconstructed by using the codewords from VQ codebook directory. Second, the remaining blocks are reconstructed using either VQ or LAS. If the decoding index taken from the code stream is equal to 0 or NB-1 and IND([b.sub.i]) = '0' then the indicator of [b.sub.i+1] is 0 or 1, respectively. In this case the following [[log.sub.2] [N.sub.B]] bits are used to reconstruct block b. Furthermore, if the decoding index taken from the code stream is equal to 0 or [N.sub.h]-1 and IND([b.sub.i]) = '1' then the indicator of [b.sub.i+1] is 0 or 1, respectively. Also, the following [[log.sub.2] [N.sub.h]] bits are used to take a codeword from the history list and use it to reconstruct block [b.sub.i].

For general cases in the remaining blocks, the SMD function is adopted to extract the indicator of block [b.sub.i+1]. For instance, if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the index of codeword is [alpha], then the indicator of [b.sub.i+1] is '1'. Contrary, the indicator of [b.sub.i+1] is '0'.

The key steps of the proposed decoding process are summarized as follows.

Procedure: Decoding

Input: Streams of encoded code EC and the pre-shared codebook

Output: Index table T

Step 1: Take [[log.sub.2] m] bits from EC to reconstruct the image block and fill the codeword index into H, where m is the size of VQ codebook, repeat until H is full.

Step 2: The remaining block reconstruction can be done by one of following cases:

Case 1: If IND([b.sub.i]) == 0 and [b.sub.i] == 0, then take following [[log.sub.2] m] bits from EC to replace [b.sub.i], use it to reconstruct the image block, and set IND([b.sub.i+1]) = 0.

Case 2: If IND([b.sub.i]) == 0 and [b.sub.i] = m - 1, then take following [[log.sub.2] m] bits from EC to replace [b.sub.i], use it to reconstruct the image block, and set IND([b.sub.i+1]) = 1.

Case 3: If IND([b.sub.i]) == 0 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then use [alpha] to reconstruct the block, and set IND([b.sub.i+1]) = 0.

Case 4: If IND([b.sub.i]) == 0 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then use [beta] to reconstruct the block, and set IND([b.sub.i+1]) = 1.

Case 5: If IND([b.sub.i]) == 1 and [b.sub.i] == 0, then take following [[log.sub.2] [N.sub.h]] bits from EC to replace [b.sub.i], use it to reconstruct the image block, and set IND([b.sub.i+1]) = 0.

Case 6: IND([b.sub.i]) == 1 and [b.sub.i] = [N.sub.h]-1, then take following [[log.sub.2] [N.sub.h]] bits from EC to replace [b.sub.i], use it to reconstruct the image block, and set IND([b.sub.i+1]) = 1.

Case 7: If IND([b.sub.i]) == 1 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then use [alpha] to reconstruct the block, and set IND([b.sub.i+1]) = 0.

Case 8: If IND([b.sub.i]) == 1 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then use [beta] to reconstruct the block, and set IND([b.sub.i+1]) = 1.

Step 3: Repeat Step 2 until all the blocks have been reconstructed.

Example: LAS indicator elimination decoding

Take the fist compression bit pattern "... 111 010..." for example. As the following bit pattern is "111," it means the current index can be found in the history list (see Fig. 5), and the next point IND([b.sub.i+1]) is " 1." So, the first restored index is 31 as it is located in the [(010).sub.2] position of the history list.

4. Experiment Results and Discussion

In order to evaluate the performance of the proposed method, the encoding methods were simulated using MATLAB software on a Pentium IV 2.6 GHz CPU with 2 GB main memory. Nine test images were used in these simulations, and are listed in Fig. 6. The size of test images was 512 x 512 pixels. The test images included smooth images (e.g., Jet(F16), Tiffany) and complex content images (e.g., Baboon, Goldhill) for fair testing the performance on a natural image.

LAS is adopted to further improve the compression rate of VQ compression. Thus, the visual quality of the LAS compression is the same as VQ compression. Because the purpose of the proposed method is to improve the compression rate of the LAS method, the visual quality of the decompression image generated by the proposed method is the same as the VQ compression method. Furthermore, the compression rate (i.e., denoted as CR) is the most important factor for evaluating a compression method. The compression rate is defined as follows:

CR = [parallel] CE [parallel]/[W x H], (5)

where W and H are the width and height of the image, and [parallel] CE [parallel] represent the total bits of compression code CE.

According to the characteristics of a natural image, the local area has a similar pixel distribution, the local area also has a similar index distribution. Thus, a good scan order can help the index history construction. We implemented Parallel-scan, Zig-Zag scan, N-scan, and Fractal-Hilbert-curve to determine a suitable scan in order to improve compression rate as much as possible. Fig. 7 illustrates the implemented scan orders. Table 6 summarizes the number of indices that can be compressed by LAS. Because Fractal-Hilbert-curve scan order tries to visit the neighboring VQ index first, thus it can as many as possible retain recently used indexes in the history list. Table 6 shows that Fractal-Hilbert-curve is the most suitable for our method, as this scan order can achieve the greatest probability to retain the recently used indexes in history list. Table 7 summarizes the bit-rate comparison for testing the different scan order. From experimental results, the Fractal-Hilbert-curve can help LAS to achieve a good bit rate. Thus, we suggest that the Fractal-Hilbert-curve scan order is a suitable scan order in the proposed method.

The size of the history list is an important factor in helping LAS compression. Table 8 and Table 9 summarize the simulation results for the number of indices encoded by LAS, and the compression rate, respectively. As we see, a large index history list can provide more help for LAS encoding. However, the compression rate may not have a better compression outcome, because a large index history list needs more bits to represent the location number in the history list. Thus, to consider the computation cost and compression rate, we suggest that a suitable size for the index history list is eight.

The proposed method fixed the size of the index history list. The index history list maintenance significantly affects the performance of the proposed method in terms of compression rate. Here, we test two maintenance rules: 1) to retire the index with the lowest frequency of use; 2) to retire the index with the longest time in the history list. Table 10 summarizes the number of indices retired by different maintenance rules. Table 11 summarizes the compression rate by adopting different index history list maintenance rules. From experimental results, rule 2 is adopted in the proposed improved LAS compression method.

In Table 12 we can find that the number of index values that can be compressed in the proposed method is higher than in the traditional LAS method in the nine test images. This demonstrates that the proposed method has more index values that can be encoded using fewer bits (3-bit or 6-bit), to achieve a better compression rate.

In the traditional LAS method, every index needs one indicator, so the indicator rate is 1. The indicator rate is calculated by the number of indicators/the size of index table. Table 13 summarizes the indicator rate comparison of traditional LAS and the proposed method. The proposed method tries to embed the LAS indicators into compression code to eliminate the indicators by using the data hiding technique. However, the proposed method needs some extra information to handle the special cases. The experimental results show that the number of extra information bits is less than the number of LAS indicator bits.

Table 14 summarizes the comparison of the compression rate of the traditional LAS method and the proposed method. From experimental results, we found that the proposed method work very well in the case of the local area has similar color distribution (i.e., the smooth image content such as Pepper, Tiffany, etc.). In the case of the local area has dissimilar color distribution, the proposed method can't get too much image compression performance improvement (e.g., Baboon). From the experimental results, the proposed method has better compression rate performance than the traditional LAS method.

Table 15 shows the comparison of compression rate CR with some recent representive techniques. In VQ method, all indexes are encoded in 8 bits, so the compression bit rate is the same as 0.5.

Chang et al.'s method [21] is based on SMVQ technique which can estimate the indicator from SMVQ, to further improve the compresstion rate. Chang et al.'s method [8] performs better than VQ, SMVQ and LAS. From experimental results it is clear that our method can perform better compression rate than others.

For the definition of image quality, PSNR (peak signal-to-noise ratio) is used to measure the visual quality. The PSNR is defined as,

PSNR = 10 x [log.sub.10] [[255.sup.2]/MSE](dB), (6)

where MSE (mean-square error) is used to determin the diffirence with two different image I and I with the same height H and width W.

MSE = [1/[H X W]] [[summation].sup.H.sub.i=1][[summation].sup.W.sub.j=1][([I.sub.ij] - [I'.sub.ij]).sup.2], (7)

where [I.sub.i,j] and [I'.sub.i,j] represent the two image in location (i, j), respectively. A large PSNR value represent the higher visual quality of image.

Table 16 demonstrates that the visual quality of SMVQ, LAS, Chang et al.'s method [8] and our method is the same with VQ, it is meant that our method can retrieve the original index table by proposed encoding/decoding phase.

5. Conclusion

In this paper we proposed a novel method to eliminate the indicators of LAS. Although LAS has good performance, the extra indicators of LAS still affect the compression rate. To improve the compression rate of LAS, the proposed method uses the concept of a data hiding method to eliminate indicators. From the experimental results, the proposed method successfully improves the performance of the compression rate by eliminating the indicators of LAS. Moreover, compared with traditional LAS, our proposed method is more flexible and improves the compression rate.

A preliminary version of this paper appeared in IEEE ICC 2009, June 14-18, Dresden, Germany. This version includes a concrete analysis and supporting implementation results on MICAz sensor nodes. This research was supported by a research grant from the IT R&D program of MKE/IITA, the Korean government [2005-Y-001-04, Development of Next Generation Security Technology]. We express our thanks to Dr. Richard Berke who checked our manuscript.

http://dx.doi.org/10.3837/tiis.2014.12.022

References

[1] C. H. Hsieh, J. C. Tsai, "Lossless compression of VQ index with search-order coding," IEEE Transactions on Image Professing, vol. 5, pp. 1579-1582, November 1996. Article (CrossRef Link).

[2] J. L. Bentley, D. D. Sleator, R. E. Tarjan, V. K. Wei, "A locally adaptive data compression scheme," Commun. ACM, vol. 29, pp. 320-330, April 1986. Article (CrossRef Link).

[3] S. S. Maniccam, N. Bourbakis, "Lossless compression and information hiding in images," Pattern Recognition, vol. 37, pp. 475-486, March 2001. Article (CrossRef Link).

[4] G.K. Wallace, "JPEG still image data compressing standard," IEEE Transactions on Consumer Electronics, vol. 38, Feburary 1992. Article (CrossRef Link).

[5] R. Gary, "Vector quantization," IEEEASSPMagazine, vol. 1, pp. 4-29, April 1984. Article (CrossRef Link).

[6] Y. Linde, "An algorithm for vector quantize design," IEEE Transactions on Communication, vol. 28, pp. 84-95, 1980. Article (CrossRef Link).

[7] T. Kim, "Side match and overlap match vector quantizes for images," IEEE Transactions on Image Professing, vol. 1, pp. 170-185, April 1992. Article (CrossRef Link).

[8] C. C. Chang, Y. C. Chou, Y. P. Hsieh, "Search-order coding method with indicator-elimination property," Journal of Systems and Software, vol. 82, pp. 516-525, March 2009. Article (CrossRef Link).

[9] C. C. Chang, C. H. Sung, T. S. Chen, "A locally adaptive scheme for image index compression," in Proc. of the 1997 Conference on Computer Vision, Graphics, and Image Processing, pp. 93-99, August 1997. Article (CrossRef Link).

[10] H. S. Tseng, C. C. Chang, "Error resilient locally adaptive data compression," Journal of Systems and Software, no. 8, pp. 1156-1160, August 2006. Article (CrossRef Link).

[11] C. Y. Lin, C. C. Chang, "Hiding data in VQ-compressed images using dissimilar pairs," Journal of computers, vol. 17, pp. 3-10, June 2008. Article (CrossRef Link).

[12] C. C. a. L. Chen, "Hiding data in images by simple LSB substitution," Pattern recognition, vol. 37, pp. 469-474, March 2001. Article (CrossRef Link).

[13] C. C. Lin, W. H. Tsai, "Secret image sharing with steganography and authentication," Journal of Systems and Software, vol. 73, pp. 405-414, November 2004. Article (CrossRef Link).

[14] C. C. Thein, J. C. Lin, "A simple and high-hiding capacity method for hiding digit-by-digit data in images based on modulus function," Pattern Recognition, vol. 36, pp. 2875-2881, December 2003. Article (CrossRef Link).

[15] R. Z. Wang, C. F. Lin, G. C. Lin, "Image hiding by optimal LSB substitution and genetic algorithm," Pattern Recognition, vol. 34, pp. 671-683, March 2001. Article (CrossRef Link).

[16] R. Z. Wang, C. F. Lin, G. C. Lin, "Hiding data in images by optimal moderately-significant-bit replacement," IEE Electronics Letters, vol. 36, pp. 2069-2070, December 2000. Article (CrossRef Link).

[17] D. C. Wu, W. H. Tsai, "Spatial-domain image hiding using image differencing," IEE Proceeding on Vision, Image and Signal Processing, vol. 147, pp. 29-37, February 2000. Article (CrossRef Link).

[18] Y. S. Wu, C. C. Thein, J. C. Lin, "Sharing and hiding secret images with size constraint," Pattern Precognition, vol. 37, pp. 1377-1385, July 2004. Article (CrossRef Link).

[19] I. C. Lin, Y. B. Lin, C. M. Wang, "Hiding data in spatial domain images with distortion tolerance," Computer Standards and Interfaces, vol. 31, pp. 458-464, February 2009. Article (CrossRef Link).

[20] H. W. Tseng, C. P. Hsieh, "Prediction-based reversible data hiding," Information Sciences, vol. 79, pp. 2460-2469, June 2009. Article (CrossRef Link).

[21] C. C. Chang, Y. C. Chou, C. Y. Lin, "An indicator elimination method for side-match vector quantization," Journal of Information Hiding and Multimedia Signal Processing, Vol. 4, No. 4, Oct. 2013, pp. 233-249. Article (CrossRef Link).

Received May 19, 2014; revised October 11, 2014; accepted November 9, 2014; published December 31, 2014

Hon-Hang Chang (1), Yung-Chen Chou (2), and Timothy K. Shih (1)

(1) Department of Computer Science and Information Engineering, National Central University, Taoyuan 32001, Taiwan, R.O.C. [e-mail: {sicachang, timothykshih}@gmail.com]

(2) Department of Computer Science and Information Engineering, Asia University, Taichung 41354, Taiwan, R.O.C. [e-mail: yungchen@gmail.com]

* Corresponding author: Yung-Chen Chou

Hon-Hang Chang is Ph. D. student at the Department of Computer Science and Information Engineering, National Central University (NCU), Taiwan (R. O. C.). He acquired his Master's degree in Department of Photonics and Communication Engineering of Asia University of Taiwan in 2011. His research fields are image processing, information hiding and water marking.

Yung-Chen Chou is an Assistant Professor at the Department of Computer Science and Information Engineering of Asia University, Taiwan (R. O. C.). He acquired his Ph. D. degree from National Chung Chen University, Taiwan. His research interests are in the area of Information hiding, watermarking and image processing.

Timothy K. Shih is a Professor at Department of Computer Science and Information Engineering, National Central University, Taiwan. Prof. Shih is a Fellow of the Institution of Engineering and Technology (IET). In addition, he is a senior member of ACM and a senior member of IEEE. Prof. Shih also joined the Educational Activities Board of the Computer Society. He acquired his M. S. in Computer Engineering from California State University, Chico, USA in 1985 and Ph. D. in Computer Engineering from Santa Clara University, USA in 1993. His current research interests are mainly in the area of Computer Vision, Interactive Multimedia, Multimedia Processing, Human Computer Interaction and e-learning.

Table 1. An example of the LAS encoding process Step Input History index list Indi- Output cator 1 31 31 0 [00011111.sub.2] 2 207 207, 31 0 [11001111.sub.2] 3 207 207, 31 1 [0.sub.2] 4 213 213, 207, 31 0 [11010101.sub.2] 5 31 31, 213, 207 1 [10.sub.2] 6 207 207, 31, 213 1 [10.sub.2] 7 207 207, 31, 213 1 [00.sub.2] 8 207 207, 31, 213 1 [00.sub.2] 9 31 31, 207, 213 1 [01.sub.2] 10 211 211, 31, 207, 213 0 [11010011.sub.2] 11 8 8, 211, 31, 207, 213 0 [00001000.sub.2] 12 8 8, 211, 31, 207, 213 1 [000.sub.2] 13 35 35, 8, 211, 31, 207, 213 0 [00100011.sub.2] 14 31 31, 35, 8, 211, 207, 213 1 [011.sub.2] 15 7 7, 31, 35, 8, 211, 207, 213 0 [00000111.sub.2] 16 7 7, 31, 35, 8, 211, 207, 213 1 [000.sub.2] Table 2. An example of the LAS decoding process Step Indi- Input History index list Output cator 1 0 [00011111.sub.2] 31 31 2 0 [11001111.sub.2] 207, 31 207 3 1 [0.sub.2] 207, 31 207 4 0 [11010101.sub.2] 213, 207, 31 213 5 1 [10.sub.2] 31, 213, 207 31 6 1 [10.sub.2] 207, 31, 213 207 7 1 [00.sub.2] 207, 31, 213 207 8 1 [00.sub.2] 207, 31, 213 207 9 1 [01.sub.2] 31, 207, 213 31 10 0 [11010011.sub.2] 211, 31, 207, 213 211 11 0 [00001000.sub.2] 8, 211, 31, 207, 213 8 12 1 [000.sub.2] 8, 211, 31, 207, 213 8 13 0 [00100011.sub.2] 35, 8, 211, 31, 207, 213 35 14 1 [011.sub.2] 31, 35, 8, 211, 207, 213 31 15 0 [00000111.sub.2] 7, 31, 35, 8, 211, 207, 213 7 16 1 [000.sub.2] 7, 31, 35, 8, 211, 207, 213 7 Table 4. The encoding rules for eight cases Cases IND IND [MATHEMATICAL ([b.sub.i]) ([b.sub.i+1]) EXPRESSION NOT REPRODUCIBLE IN ASCII] 1 0 0 1 (true) 2 0 0 0 (false) 3 0 1 1 4 0 1 0 5 1 0 1 6 1 0 0 7 1 1 1 8 1 1 0 Cases Coding rule 1 [alpha] 2 0[parallel][alpha] 3 [beta] 4 m-1[parallel][alpha] 5 [[alpha].sub.h] 6 0[parallel][[alpha].sub.h] 7 [[beta].sub.h] 8 [N.sub.h] - 1[parallel][[alpha].sub.h] Table 5. Known information VQ [MATHEMATICAL Index EXPRESSION NOT Table REPRODUCIBLE IN ASCII] k 31 0 (false) k+1 29 1 (true) k+2 31 1 k+3 35 1 k+4 34 0 k+5 39 1 Table 6. The number of indices compressed by our method (image size 512 x 512) Images Parallel- Zig-Zag N-scan Fractal- scan scan Hilbert- curve Baboon 3341 3113 4201 4291 Barbara 6260 5637 7928 8140 GoldHill 7361 5288 7610 7998 Jet(F16) 10783 9658 11080 11351 Lena 6904 7494 10346 10527 Pepper 7813 7410 10243 10510 Sailboat 8316 7506 9050 9259 Tiffany 10928 10178 12241 12717 Zelda 7671 7366 10135 10433 Table 7. The bit rate testing for different scan orders (image size 512 x 512) Images Parallel- Zig-Zag N-scan Fractal- scan scan Hilbert- curve Baboon 0.4691 0.4725 0.4557 0.4538 Barbara 0.4092 0.4199 0.3804 0.377 GoldHill 0.3746 0.4092 0.3697 0.3643 Jet(F16) 0.3056 0.3267 0.3017 0.2967 Lena 0.3788 0.3679 0.3168 0.3138 Pepper 0.3592 0.3671 0.3165 0.3118 Sailboat 0.3632 0.3764 0.35 0.3467 Tiffany 0.2977 0.3135 0.2777 0.2688 Zelda 0.359 0.3642 0.3147 0.3094 Table 8. The simulation results for different size of index history list Images The Size of History List 4 8 16 Baboon 2280 4291 6390 Barbara 6025 8140 9854 GoldHill 5463 7998 10030 Jet(F16) 9642 11351 12439 Lena 8110 10527 11858 Pepper 8145 10510 11862 Sailboat 7389 9259 10532 Tiffany 10377 12717 14124 Zelda 7802 10433 12158 Table 9. The bit rate in different history list size Images The Size of History List 4 8 16 Baboon 0.4803 0.4538 0.4400 Barbara 0.3959 0.3770 0.3806 GoldHill 0.3894 0.3643 0.3620 Jet(F16) 0.3018 0.2967 0.3213 Lena 0.3346 0.3138 0.3299 Pepper 0.3309 0.3118 0.3266 Sailboat 0.3601 0.3467 0.3587 Tiffany 0.2848 0.2688 0.2917 Zelda 0.3351 0.3094 0.3197 Table 10. The number of index values that can be compressed in the two cases Images Rule 1 Compressible Incompressible Baboon 2870 13514 Barbara 5894 10490 GoldHill 5819 10565 Jet(F16) 10300 6084 Lena 7794 8590 Pepper 7837 8547 Sailboat 7354 9030 Tiffany 9022 7362 Zelda 7940 8444 Images Rule 2 Compressible Incompressible Baboon 4291 12093 Barbara 8140 8244 GoldHill 7998 8386 Jet(F16) 11351 5033 Lena 10527 5857 Pepper 10510 5874 Sailboat 9259 7125 Tiffany 12717 3667 Zelda 10433 5951 Table 11. The bit rate comparison for different maintenance rules Images Rule 1 Rule 2 Baboon 0.4755 0.4538 Barbara 0.4137 0.3770 GoldHill 0.3985 0.3643 Jet(F16) 0.3169 0.2967 Lena 0.3612 0.3138 Pepper 0.3589 0.3118 Sailboat 0.3807 0.3467 Tiffany 0.3326 0.2688 Zelda 0.3533 0.3094 Table 12. Comparison of the compression rate results for traditional LAS and the proposed method Images LAS Compressible Incompressible Baboon 4141 12243 Barbara 7424 8960 GoldHill 7274 9110 Jet(F16) 9945 6439 Lena 9223 7161 Pepper 9205 7179 Sailboat 8040 8344 Tiffany 11065 5319 Zelda 9104 7280 Images Proposed Method Compressible Incompressible Baboon 4291 12093 Barbara 8140 8244 GoldHill 7998 8386 Jet(F16) 11351 5033 Lena 10527 5857 Pepper 10510 5874 Sailboat 9259 7125 Tiffany 12717 3667 Zelda 10433 5951 Table 13. The indicator rate in the traditional LAS method and proposed method Images LAS Proposed Method Baboon 1 0.808 Barbara 1 0.776 GoldHill 1 0.584 Jet(F16) 1 0.352 Lena 1 0.440 Pepper 1 0.376 Sailboat 1 0.568 Tiffany 1 0.472 Zelda 1 0.304 Table 14. Comparison of the bit rate between the LAS method and the proposed method Images LAS (A) Proposed Gain Method (B) (A-B) Baboon 0.498 0.454 0.044 Barbara 0.423 0.377 0.046 GoldHill 0.431 0.364 0.067 Jet(F16) 0.348 0.297 0.051 Lena 0.385 0.314 0.071 Pepper 0.383 0.312 0.071 Sailboat 0.402 0.347 0.055 Tiffany 0.337 0.269 0.068 Zelda 0.389 0.309 0.08 Table 15. Comparison of the bit rate between recent techniques and the proposed method Images VQ SMVQ [7] LAS [2] Chang et al., 2009 [8] Baboon 0.5 0.536 0.498 0.465 Barbara 0.5 0.480 0.423 0.440 Goldhill 0.5 0.498 0.431 0.446 Jet(F16) 0.5 0.401 0.348 0.360 Lena 0.5 0.421 0.385 0.417 Pepper 0.5 0.422 0.383 0.422 Sailboat 0.5 0.459 0.402 0.424 Tiffany 0.5 0.401 0.337 0.371 Zelda 0.5 0.438 0.389 0.427 Images Chang et Proposed al., 2013 [21] Baboon 0.490 0.454 Barbara 0.455 0.377 Goldhill 0.454 0.364 Jet(F16) 0.364 0.297 Lena 0.389 0.314 Pepper 0.395 0.312 Sailboat 0.443 0.347 Tiffany 0.354 0.269 Zelda 0.403 0.309 Table 16. Comparison of the PSNR value (dB) between between recent techniques and the proposed method Images VQ SMVQ [7] LAS [2] Chang et al., 2009 [8] Baboon 25.46 25.46 25.46 25.46 Barbara 24.93 24.92 24.93 24.93 Goldhill 28.91 28.91 28.91 28.91 Jet(F16) 27.13 27.13 27.13 27.13 Lena 28.65 28.65 28.65 28.65 Pepper 28.45 28.45 28.45 28.45 Sailboat 25.01 25.01 25.01 25.01 Tiffany 30.24 30.24 30.24 30.24 Zelda 31.31 31.31 31.31 31.31 Images Chang et Proposed al., 2013 [21] Baboon 25.46 25.46 Barbara 24.92 24.93 Goldhill 28.91 28.91 Jet(F16) 27.13 27.13 Lena 28.65 28.65 Pepper 28.00 28.45 Sailboat 25.00 25.01 Tiffany 30.23 30.24 Zelda 31.31 31.31 Fig. 4. The codewords pairing example (a) pairing codewords for VQ codebook 0 [left and right arrow] 255 1 [left and right arrow] 128 2 [left and right arrow] 129 3 [left and right arrow] 130 127 [left and right arrow] 254 (b) pairing codewords for history list 0 [left and right arrow] 7 1 [left and right arrow] 4 2 [left and right arrow] 5 3 [left and right arrow] 6 Fig.5. Hiistory list from (k-1)-th to (k+3-th) (a) k - 1 000 x x 111 001 50 [left and right arrow] 29 100 010 31 [left and right arrow] 27 101 011 30 [left and right arrow] 26 110 (b) k 000 x x 111 001 50 [left and right arrow] 29 100 010 31 [left and right arrow] 27 101 011 30 [left and right arrow] 26 110 (c) k + 1 000 x x 111 001 50 [left and right arrow] 29 100 010 31 [left and right arrow] 27 101 011 30 [left and right arrow] 26 110 (d) k + 2 000 x x 111 001 35 [left and right arrow] 29 100 010 31 [left and right arrow] 27 101 011 30 [left and right arrow] 26 110 (a) k + 3 000 x x 111 001 35 [left and right arrow] 29 100 010 31 [left and right arrow] 27 101 011 30 [left and right arrow] 26 110

Printer friendly Cite/link Email Feedback | |

Author: | Chang, Hon-Hang; Chou, Yung-Chen; Shih, Timothy K. |
---|---|

Publication: | KSII Transactions on Internet and Information Systems |

Article Type: | Report |

Date: | Dec 1, 2014 |

Words: | 7901 |

Previous Article: | Analysing the combined Kerberos timed authentication protocol and frequent key renewal using CSP and rank functions. |

Next Article: | A lightweight integrity authentication scheme based on reversible watermark for Wireless Body Area Networks. |

Topics: |