Advanced
Indicator Elimination for Locally Adaptive Scheme Using Data Hiding Technique
Indicator Elimination for Locally Adaptive Scheme Using Data Hiding Technique
KSII Transactions on Internet and Information Systems (TIIS). 2014. Dec, 8(12): 4624-4642
Copyright © 2014, Korean Society For Internet Information
  • Received : May 19, 2014
  • Accepted : November 09, 2014
  • Published : December 31, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Hon-Hang Chang
Department of Computer Science and Information Engineering, National Central University, Taoyuan 32001, Taiwan, R.O.C.
Yung-Chen Chou
Department of Computer Science and Information Engineering, Asia University, Taichung 41354, Taiwan, R.O.C.
Timothy K. Shih
Department of Computer Science and Information Engineering, National Central University, Taoyuan 32001, Taiwan, R.O.C.

Abstract
Image compression is a popular research issue that focuses on the problems of reducing the size of multimedia files. Vector Quantization (VQ) is a well-known lossy compression method which can significantly reduce the size of a digital image while maintaining acceptable visual quality. A locally adaptive scheme (LAS) was proposed to improve the compression rate of VQ in 1997. However, a LAS needs extra indicators to indicate the sources, consequently the compression rate of LAS will be affected. In this paper, we propose a novel method to eliminate the LAS indicators and so improve the compression rate. The proposed method uses the concept of data hiding to conceal the indicators, thus further improving the compression rate of LAS. From experimental results, it is clearly demonstrated that the proposed method can actually eliminate the extra indicators while successfully improving the compression rate of the LAS.
Keywords
1. Introduction
M odern 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 × 256 is compressed by VQ with a 256 codeword codebook and a codeword size of 16 pixels, then the compression rate is (((256 × 256) / 16) × 8) / (256 × 256 × 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
- 2.1 Vector Quantization
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 = { yi | i = 0, 1, …, m -1} contains m codewords and each codeword contains k × k dimensions. The key steps of VQ compression are summarized as follows: First, the image I is divided into non-overlapping blocks sized k × k pixels and denoted as I = { Bi | I = 0, 1, …, M -1}, where M is the total number of blocks of I . Second, to encode blocks Bi , find a codeword y min which has the smallest distance between the codeword and Bi . The codeword y min can be found by using Eq. (1).
PPT Slide
Lager Image
where y min is the found codeword which is most similar to the encoding block Bi . Bi ( j ) and yv ( j ) represent the j -th pixel Bi and yv , respectively. Third, Bi is encoded by using the index of y 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 × 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 × 256) / 16) × 8) / (256 × 256 × 8) = 0.0625.
PPT Slide
Lager Image
The concept of VQ compression
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 Bi is the current encoding block and the neighboring border vector (NBV) of block Bi is defined by NBV = { x 0 = ( u 12 + l 3 )/ 2 , x 1 = u 13 , x 2 = u 14 , x 3 = u 15 , x 4 = l 7 , *, *, *, x 8 = l 11 , *, *, *, x 12 = l 15 , *, *, *} which is obtained from Bi ’s upper-side (i.e., block U ) and left-side (i.e., block L ), where the element ‘*’ means; do not care.
PPT Slide
Lager Image
The concept of the SMVQ
The key steps of SMVQ are summarized as follows: First, for current encoding block Bi , determine s candidate codewords to form a state codebook by using Bi ’s NBV . Here, the candidate codeword selection is used to compute the distance between NBV and codeword in Y (i.e., Eq. (2)).
PPT Slide
Lager Image
where v is the index value of codewords in the codebook. Here, the state codebook is denoted as SCB = { scwi | i = 0, 1, …, s -1}. Second, a closest codeword of Bi can be found by calculating the distance (i.e., Eq. (3)) between Bi and the codeword in SCB . If the distance between Bi and scw min is smaller than a predefined threshold, then the block Bi is encoded by SMVQ; otherwise, the block Bi is encoded by VQ.
PPT Slide
Lager Image
- 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 × 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 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 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 × 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.
An example of the LAS encoding process
PPT Slide
Lager Image
An example of the LAS encoding process
An example of the LAS decoding process
PPT Slide
Lager Image
An example of the LAS 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 = { pi | i = 1, 2, …, N } sized N pixels is first compressed by VQ, and an index table T = { bi | 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.
PPT Slide
Lager Image
Fractal-Hilbert-curve scan order with block size 8 × 8
The history list is sorted by using decreasing order and denoted as H = { cwk | k = 0, 1, …, h -1}. Note that, the first and last element in the list (i.e., 0 and Nh-1 ) are reversed for handling special cases. Here, Nh 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., b1 ) 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 ( cw1 , cw N/2 ), ( cw 2 , cw N/2+1 ), …, ( cw N/2-1 , cw 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, ( α , β ) represents a selected codeword pair.
PPT Slide
Lager Image
The codewords pairing example
First, the index values are added into the list until the list is full. After that, the current encoding block bi 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 bi . Here Γ is used to denote the set of temporal pixels. According to different scan orders for encoding, block bi will stay as one of fifteen types (the types are summarized in Table 3 ).
The list of total types of current encoding blockbi(i.e., gray block: encoded block; white block: current encoding block)
PPT Slide
Lager Image
The list of total types of current encoding block bi (i.e., gray block: encoded block; white block: current encoding block)
The SMD function is defined as follows,
PPT Slide
Lager Image
where α and β represent two different blocks reconstructed by the pairing codewords, NBVbi is the nearboaring block of the current block bi (see L and U in Fig. 2 (a)), Γ is the location set of current block bi , 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 Γare {0, 1, 2, 3, 4, 8, 12}, the pixel value of block α with corresponding location are {39, 42, 47, 52, 51, 57, 98}, and the value of NBVbi are {(36+59)/2, 90, 120, 37, 51, 57, 98}. Then the SMD ( α , NBVbi ) can be calculated by the distance measure with α and NBVbi using (4), 5554 = |39 - 47.5| 2 + |42 - 90| 2 + |47 - 120| 2 + |52 - 37| 2 + |51 - 51| 2 + |57 - 57| 2 + |98 - 98| 2 . Also, the SMD ( β , NBVbi ) value can be obtained in the same procedure.
According to the source of current encoding block bi and next block b i+1 , the encoding situation can be divided into the following cases:
Case 1: if IND ( bi ) = IND ( b i+1 ) = ‘0’ (i.e., the block b i+1 cannot be encoded by LAS) and SMD ( α , NBVbi ) ≤ SMD ( β , NBVbi ), then bi is encoded by using α .
Case 2: if IND ( bi ) = IND ( b i+1 ) = ‘0’ and SMD ( α , NBVbi ) > SMD ( β , NBVbi ), then bi is encoded by using 0║ α .
Case 3: if IND ( bi ) = ‘0’, IND ( b i+1 ) = ‘1’ (i.e., the block b i+1 can be encoded by LAS) and SMD ( α , NBVbi ) ≤ SMD ( β , NBVbi ), then bi is encoded by using β .
Case 4: if IND ( bi ) = ‘0’, IND ( b i+1 ) = ‘1’ and SMD ( α , NBVbi ) > SMD ( β , NBVbi ), then bi is encoded by using m -1║ α .
Case 5: if IND ( bi ) = ‘1’, IND ( b i+1 ) = ‘0’ (i.e., the block bi and b i+1 are encoded by LAS and VQ, respectively) and SMD ( α , NBVbi ) ≤ SMD ( β , NBVbi ), then bi is encoded by using αh .
Case 6: if IND ( bi ) = ‘1’, IND ( b i+1 ) = ‘0’ and SMD ( α , NBVbi ) > SMD ( β , NBVbi ), then bi is encoded by using 0║ αh .
Case 7: if IND ( bi ) = IND ( b i+1 ) = ‘1’ (i.e., the block bi and b i+1 are both encoded by LAS) and SMD ( α , NBVbi ) ≤ SMD ( β , NBVbi ), then bi is encoded by using βh .
Case 8: if IND ( bi ) = IND ( b i+1 ) = ‘1’ and SMD ( α , NBVbi ) ≤ SMD ( β , NBVbi ), then bi is encoded by using N h-1 αh .
Table 4 summarizes all possible cases of the proposed encoding rules.
The encoding rules for eight cases
PPT Slide
Lager Image
The encoding rules for eight cases
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║001║010║00100011║00000000 00100010”
Known information
PPT Slide
Lager Image
Known information
PPT Slide
Lager Image
History list from (k-1)-th to (k+3)-th
- 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 ( bi ) = ‘0’ then the indicator of b i+1 is 0 or 1, respectively. In this case the following ⎾log 2 NB ⏋ bits are used to reconstruct block bi . Furthermore, if the decoding index taken from the code stream is equal to 0 or Nh -1 and IND ( bi ) = ‘1’ then the indicator of b i+1 is 0 or 1, respectively. Also, the followingfollowing ⎾log 2 Nh ⏋ bits are used to take a codeword from the history list and use it to reconstruct block bi .
For general cases in the remaining blocks, the SMD function is adopted to extract the indicator of block b i+1 . For instance, if SMD ( α , NBVbi ) ≤ SMD (β, NBVbi ) and the index of codeword is α , then the indicator of b i+1 is ‘1’. Contrary, the indicator of b 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
Step1: Take ⎾log 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: IfIND(bi) == 0 andbi== 0, then take following ⎾log2m⏋ bits fromECto replacebi, use it to reconstruct the image block, and setIND(bi+1) = 0.
  • Case 2: IfIND(bi) == 0 andbi=m-1, then take following ⎾log2m⏋ bits fromECto replacebi, use it to reconstruct the image block, and setIND(bi+1) = 1.
  • Case 3: IfIND(bi) == 0 andSMD(α,NBVbi) ≤SMD(β,NBVbi), then useαto reconstruct the block, and setIND(bi+1) = 0.
  • Case 4: IfIND(bi) == 0 andSMD(α,NBVbi) >SMD(β,NBVbi), then useβto reconstruct the block, and setIND(bi+1) = 1.
  • Case 5: IfIND(bi) == 1 andbi== 0, then take following ⎾log2Nh⏋ bits fromECto replacebi, use it to reconstruct the image block, and setIND(bi+1) = 0.
  • Case 6: IfIND(bi) == 1 andbi=Nh-1, then take following ⎾log2Nh⏋ bits from EC to replacebi, use it to reconstruct the image block, and setIND(bi+1) = 1.
  • Case 7: If IND(bi) == 1 andSMD(α,NBVbi) ≤SMD(β,NBVbi), then useαto reconstruct the block, and setIND(bi+1) = 0.
  • Case 8: IfIND(bi) == 1 andSMD(α,NBVbi) >SMD(β,NBVbi), then useβto reconstruct the block, and setIND(bi+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 i+1 ) is “1.” So, the first restored index is 31 as it is located in the (010) 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 × 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.
PPT Slide
Lager Image
Nine test images
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:
PPT Slide
Lager Image
where W and H are the width and height of the image, and ║ CE ║ 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.
PPT Slide
Lager Image
Four types of scan order
The number of indices compressed by our method (image size 512 × 512)
PPT Slide
Lager Image
The number of indices compressed by our method (image size 512 × 512)
The bit rate testing for different scan orders (image size 512 × 512)
PPT Slide
Lager Image
The bit rate testing for different scan orders (image size 512 × 512)
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 simulation results for different size of index history list
PPT Slide
Lager Image
The simulation results for different size of index history list
The bit rate in different history list size
PPT Slide
Lager Image
The bit rate in different history list size
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.
The number of index values that can be compressed in the two cases
PPT Slide
Lager Image
The number of index values that can be compressed in the two cases
The bit rate comparison for different maintenance rules
PPT Slide
Lager Image
The bit rate comparison for different maintenance rules
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.
Comparison of the compression rate results for traditional LAS and the proposed method
PPT Slide
Lager Image
Comparison of the compression rate results for traditional LAS and the proposed method
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.
The indicator rate in the traditional LAS method and proposed method
PPT Slide
Lager Image
The indicator rate in the traditional LAS method and proposed method
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.
Comparison of the bit rate between the LAS method and the proposed method
PPT Slide
Lager Image
Comparison of the bit rate between the LAS method and the proposed 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.
Comparison of the bit rate between recent techniques and the proposed method
PPT Slide
Lager Image
Comparison of the bit rate between recent techniques and the proposed method
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,
PPT Slide
Lager Image
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 .
PPT Slide
Lager Image
where I ij and I’ ij 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.
Comparison of thePSNRvalue (dB) between between recent techniques and the proposed method
PPT Slide
Lager Image
Comparison of the PSNR value (dB) between between recent techniques and the proposed method
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.
BIO
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.
References
Hsieh C. H. , Tsai J. C. 1996 "Lossless compression of VQ index with search-order coding," IEEE Transactions on Image Professing 5 (November) 1579 - 1582    DOI : 10.1109/83.541428
Bentley J. L. , Sleator D. D. , Tarjan R. E. , Wei V. K. 1986 "A locally adaptive data compression scheme," Commun. ACM 29 320 - 330    DOI : 10.1145/5684.5688
Maniccam S. S. , Bourbakis N. 2001 "Lossless compression and information hiding in images," Pattern Recognition 37 475 - 486    DOI : 10.1016/j.patcog.2003.08.010
Wallace G.K. 1992 "JPEG still image data compressing standard," IEEE Transactions on Consumer Electronics 38    DOI : 10.1109/30.125072
Gary R. 1984 "Vector quantization," IEEE ASSP Magazine 1 4 - 29    DOI : 10.1109/MASSP.1984.1162229
Linde Y. 1980 "An algorithm for vector quantize design," IEEE Transactions on Communication 28 84 - 95    DOI : 10.1109/TCOM.1980.1094577
Kim T. 1992 "Side match and overlap match vector quantizes for images," IEEE Transactions on Image Professing 1 170 - 185    DOI : 10.1109/83.136594
Chang C. C. , Chou Y. C. , Hsieh Y. P. 2009 "Search-order coding method with indicator-elimination property," Journal of Systems and Software 82 516 - 525    DOI : 10.1016/j.jss.2008.08.024
Chang C. C. , Sung C. H. , Chen T. S. "A locally adaptive scheme for image index compression," in Proc. of the 1997 Conference on Computer Vision, Graphics, and Image Processing August 1997 93 - 99
Tseng H. S. , Chang C. C. 2006 "Error resilient locally adaptive data compression," Journal of Systems and Software (8) 1156 - 1160    DOI : 10.1016/j.jss.2006.01.004
Lin C. Y. , Chang C. C. 2008 "Hiding data in VQ-compressed images using dissimilar pairs," Journal of computers 17 3 - 10
Chen C. C. a. L. 2001 "Hiding data in images by simple LSB substitution," Pattern recognition 37 469 - 474    DOI : 10.1016/j.patcog.2003.08.007
Lin C. C. , Tsai W. H. 2004 "Secret image sharing with steganography and authentication," Journal of Systems and Software 73 405 - 414    DOI : 10.1016/S0164-1212(03)00239-5
Thein C. C. , Lin J. C. 2003 "A simple and high-hiding capacity method for hiding digit-by-digit data in images based on modulus function," Pattern Recognition 36 2875 - 2881    DOI : 10.1016/S0031-3203(03)00221-8
Wang R. Z. , Lin C. F. , Lin G. C. 2001 "Image hiding by optimal LSB substitution and genetic algorithm," Pattern Recognition 34 671 - 683    DOI : 10.1016/S0031-3203(00)00015-7
Wang R. Z. , Lin C. F. , Lin G. C. 2000 "Hiding data in images by optimal moderately-significant-bit replacement," IEE Electronics Letters 36 2069 - 2070    DOI : 10.1049/el:20001429
Wu D. C. , Tsai W. H. 2000 "Spatial-domain image hiding using image differencing," IEE Proceeding on Vision, Image and Signal Processing 147 29 - 37    DOI : 10.1049/ip-vis:20000104
Wu Y. S. , Thein C. C. , Lin J. C. 2004 "Sharing and hiding secret images with size constraint," Pattern Precognition 37 1377 - 1385    DOI : 10.1016/j.patcog.2004.01.002
Lin I. C. , Lin Y. B. , Wang C.M. 2009 "Hiding data in spatial domain images with distortion tolerance," Computer Standards and Interfaces 31 458 - 464    DOI : 10.1016/j.csi.2008.05.010
Tseng H.W. , Hsieh C. P. 2009 "Prediction-based reversible data hiding," Information Sciences 79 2460 - 2469    DOI : 10.1016/j.ins.2009.03.014
Chang C. C. , Chou Y. C. , Lin C. Y. 2013 "An indicator elimination method for side-match vector quantization," Journal of Information Hiding and Multimedia Signal Processing 4 (4) 233 - 249