Image compression is a popular research issue that focuses on the problems of reducing the size of multimedia files. Vector Quantization (VQ) is a wellknown 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.
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 nonoverlapping blocks and compress these blocks with a pretrained codebook. Here, the pretrained 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.
Searchorder 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 searchorder 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 nonoverlapping 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
= {
y_{i}

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 nonoverlapping blocks sized
k
×
k
pixels and denoted as
I
= {
B_{i}

I
= 0, 1, …,
M
1}, where
M
is the total number of blocks of
I
. Second, to encode blocks
B_{i}
, find a codeword
y
_{min}
which has the smallest distance between the codeword and
B_{i}
. The codeword
y
_{min}
can be found by using Eq. (1).
where
y
_{min}
is the found codeword which is most similar to the encoding block
B_{i}
.
B_{i}
(
j
) and
y_{v}
(
j
) represent the
j
th pixel
B_{i}
and
y_{v}
, respectively. Third,
B_{i}
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.
The concept of VQ compression
Line and Chang presented a data hiding technique by using the concept of declustring
[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 Sidematch Vector Quantization (SMVQ)
Sidematch vector quantization (SMVQ) is a VQbased 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_{i}
is the current encoding block and the neighboring border vector (NBV) of block
B_{i}
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
B_{i}
’s upperside (i.e., block
U
) and leftside (i.e., block
L
), where the element ‘*’ means; do not care.
The concept of the SMVQ
The key steps of SMVQ are summarized as follows: First, for current encoding block
B_{i}
, determine
s
candidate codewords to form a state codebook by using
B_{i}
’s
NBV
. Here, the candidate codeword selection is used to compute the distance between
NBV
and codeword in
Y
(i.e., Eq. (2)).
where
v
is the index value of codewords in the codebook. Here, the state codebook is denoted as
SCB
= {
scw_{i}

i
= 0, 1, …,
s
1}. Second, a closest codeword of
B_{i}
can be found by calculating the distance (i.e., Eq. (3)) between
B_{i}
and the codeword in
SCB
. If the distance between
B_{i}
and
scw
_{min}
is smaller than a predefined threshold, then the block
B_{i}
is encoded by SMVQ; otherwise, the block
B_{i}
is encoded by VQ.
 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 nonoverlapping 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
An example of the LAS encoding process
An example of the LAS decoding process
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
= {
p_{i}

i
= 1, 2, …,
N
} sized
N
pixels is first compressed by VQ, and an index table
T
= {
b_{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 FractalHilbertcurve scan order (as shown in
Fig. 3
). Any scan order (e.g., Parallelscan, ZigZag scan, Nscan, FractalHilbertcurve) 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 FirstInFirstOut (FIFO) operation.
FractalHilbertcurve scan order with block size 8 × 8
The history list is sorted by using decreasing order and denoted as
H
= {
cw_{k}

k
= 0, 1, …,
h
1}. Note that, the first and last element in the list (i.e., 0 and
N_{h}1
) are reversed for handling special cases. Here,
N_{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 sidematchdistortion 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_{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_{1}
,
cw
_{N/2}
), (
cw
_{2}
,
cw
_{N/2+1}
), …, (
cw
_{N/21}
,
cw
_{N2}
).
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.
The codewords pairing example
First, the index values are added into the list until the list is full. After that, the current encoding block
b_{i}
is either encoded by VQ or LAS. The proposed method adopts the sidematch 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_{i}
. Here Γ is used to denote the set of temporal pixels. According to different scan orders for encoding, block
b_{i}
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)
The list of total types of current encoding block b_{i} (i.e., gray block: encoded block; white block: current encoding block)
The SMD function is defined as follows,
where
α
and
β
represent two different blocks reconstructed by the pairing codewords,
NBV_{bi}
is the nearboaring block of the current block
b_{i}
(see
L
and
U
in
Fig. 2
(a)), Γ is the location set of current block
b_{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 Γ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
NBV_{bi}
are {(36+59)/2, 90, 120, 37, 51, 57, 98}. Then the
SMD
(
α
,
NBV_{bi}
) can be calculated by the distance measure with
α
and
NBV_{bi}
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
(
β
,
NBV_{bi}
) value can be obtained in the same procedure.
According to the source of current encoding block
b_{i}
and next block
b
_{i+1}
, the encoding situation can be divided into the following cases:
Case 1:
if
IND
(
b_{i}
) =
IND
(
b
_{i+1}
) = ‘0’ (i.e., the block
b
_{i+1}
cannot be encoded by LAS) and
SMD
(
α
,
NBV_{bi}
) ≤
SMD
(
β
,
NBV_{bi}
), then
b_{i}
is encoded by using
α
.
Case 2:
if
IND
(
b_{i}
) =
IND
(
b
_{i+1}
) = ‘0’ and
SMD
(
α
,
NBV_{bi}
) >
SMD
(
β
,
NBV_{bi}
), then
b_{i}
is encoded by using 0║
α
.
Case 3:
if
IND
(
b_{i}
) = ‘0’,
IND
(
b
_{i+1}
) = ‘1’ (i.e., the block
b
_{i+1}
can be encoded by LAS) and
SMD
(
α
,
NBV_{bi}
) ≤
SMD
(
β
,
NBV_{bi}
), then
b_{i}
is encoded by using
β
.
Case 4:
if
IND
(
b_{i}
) = ‘0’,
IND
(
b
_{i+1}
) = ‘1’ and
SMD
(
α
,
NBV_{bi}
) >
SMD
(
β
,
NBV_{bi}
), then
b_{i}
is encoded by using
m
1║
α
.
Case 5:
if
IND
(
b_{i}
) = ‘1’,
IND
(
b
_{i+1}
) = ‘0’ (i.e., the block
b_{i}
and
b
_{i+1}
are encoded by LAS and VQ, respectively) and
SMD
(
α
,
NBV_{bi}
) ≤
SMD
(
β
,
NBV_{bi}
), then
b_{i}
is encoded by using
α_{h}
.
Case 6:
if
IND
(
b_{i}
) = ‘1’,
IND
(
b
_{i+1}
) = ‘0’ and
SMD
(
α
,
NBV_{bi}
) >
SMD
(
β
,
NBV_{bi}
), then
b_{i}
is encoded by using 0║
α_{h}
.
Case 7:
if
IND
(
b_{i}
) =
IND
(
b
_{i+1}
) = ‘1’ (i.e., the block
b_{i}
and
b
_{i+1}
are both encoded by LAS) and
SMD
(
α
,
NBV_{bi}
) ≤
SMD
(
β
,
NBV_{bi}
), then
b_{i}
is encoded by using
β_{h}
.
Case 8:
if
IND
(
b_{i}
) =
IND
(
b
_{i+1}
) = ‘1’ and
SMD
(
α
,
NBV_{bi}
) ≤
SMD
(
β
,
NBV_{bi}
), then
b_{i}
is encoded by using
N
_{h1}
║
α_{h}
.
Table 4
summarizes all possible cases of the proposed encoding rules.
The encoding rules for eight cases
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
History list from (k1)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
(
b_{i}
) = ‘0’ then the indicator of
b
_{i+1}
is 0 or 1, respectively. In this case the following ⎾log
_{2}
N_{B}
⏋ bits are used to reconstruct block
b_{i}
. Furthermore, if the decoding index taken from the code stream is equal to 0 or
N_{h}
1 and
IND
(
b_{i}
) = ‘1’ then the indicator of
b
_{i+1}
is 0 or 1, respectively. Also, the followingfollowing ⎾log
_{2}
N_{h}
⏋ bits are used to take a codeword from the history list and use it to reconstruct block
b_{i}
.
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
(
α
,
NBV_{bi}
) ≤
SMD
(β,
NBV_{bi}
) 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 preshared 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=m1, 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=Nh1, 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.
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:
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 Parallelscan, ZigZag scan, Nscan, and FractalHilbertcurve 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 FractalHilbertcurve 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 FractalHilbertcurve 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 bitrate comparison for testing the different scan order. From experimental results, the FractalHilbertcurve can help LAS to achieve a good bit rate. Thus, we suggest that the FractalHilbertcurve scan order is a suitable scan order in the proposed method.
Four types of scan order
The number of indices compressed by our method (image size 512 × 512)
The number of indices compressed by our method (image size 512 × 512)
The bit rate testing for different scan orders (image size 512 × 512)
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
The simulation results for different size of index history list
The bit rate in different history list size
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
The number of index values that can be compressed in the two cases
The bit rate comparison for different maintenance rules
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 (3bit or 6bit), to achieve a better compression rate.
Comparison of the compression rate results for traditional LAS and the proposed method
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
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
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
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 signaltonoise ratio) is used to measure the visual quality. The
PSNR
is defined as,
where
MSE
(meansquare error) is used to determin the diffirence with two different image
I
and
I
with the same height
H
and width
W
.
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
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
HonHang 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.
YungChen 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 elearning.
Hsieh C. H.
,
Tsai J. C.
1996
"Lossless compression of VQ index with searchorder 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
Wallace G.K.
1992
"JPEG still image data compressing standard,"
IEEE Transactions on Consumer Electronics
38
DOI : 10.1109/30.125072
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
"Searchorder coding method with indicatorelimination 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 VQcompressed images using dissimilar pairs,"
Journal of computers
17
3 
10
Thein C. C.
,
Lin J. C.
2003
"A simple and highhiding capacity method for hiding digitbydigit data in images based on modulus function,"
Pattern Recognition
36
2875 
2881
DOI : 10.1016/S00313203(03)002218
Wang R. Z.
,
Lin C. F.
,
Lin G. C.
2000
"Hiding data in images by optimal moderatelysignificantbit replacement,"
IEE Electronics Letters
36
2069 
2070
DOI : 10.1049/el:20001429
Wu D. C.
,
Tsai W. H.
2000
"Spatialdomain image hiding using image differencing,"
IEE Proceeding on Vision, Image and Signal Processing
147
29 
37
DOI : 10.1049/ipvis:20000104
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
Chang C. C.
,
Chou Y. C.
,
Lin C. Y.
2013
"An indicator elimination method for sidematch vector quantization,"
Journal of Information Hiding and Multimedia Signal Processing
4
(4)
233 
249