# An Innovative Recompression Scheme for VQ Index Tables
###### Abstract  
As we move into the digital era, the pace of technological advancement is accelerating rapidly. Network traffic often becomes congested during the transmission of large data volumes. To mitigate this, data compression plays a crucial role in minimizing transmitted data. Vector quantization (VQ) stands out as a potent compression technique where each image block is encoded independently as an index linked to a codebook, effectively reducing the bit rate. In this paper, we introduce a novel scheme for recompressing VQ indices, enabling lossless restoration of the original indices during decoding without compromising visual quality. Our method not only considers pixel correlations within each image block but also leverages correlations between neighboring blocks, further optimizing the bit rate. The experimental results demonstrated the superior performance of our approach over existing methods. compression; vector quantization; search-order coding; side match; codebook; codeword; state codebook +
Footnote †: journal: Computer Science  
0000-0001-9991-4000-9991-4000]J.-C. Liu  
0000-0001-9991-4000]Liu  
0000-0001-9991-4000]Liu  
0000-0001-9991-4000]Liu  
VQ compression schemes can be divided into memory VQ and memoryless VQ. In memory VQ, image blocks are coded independently, utilizing the correlation of neighboring blocks. As a result, finite-state VQ (FSVQ) [12] was proposed, employing the statistical correlation between neighboring blocks to reduce the bit rate. On the other hand, side match VQ (SMVQ) [13] utilizes the correlation of neighboring block edges to build a state codebook, with the aim of reducing the bit rate. However, this approach may introduce additional coding distortion, potentially leading to poor image quality. In recent years, several algorithms [14; 15; 16; 17; 18] were proposed to enhance the performance of SMVQ. Furthermore, there are other relevant techniques, namely predictive VQ (PVQ) [19; 20] and address VQ (AVQ) [21]. Generally speaking, most memory VQ schemes are more complex and require higher computational costs compared to memoryless VQ ones. Differing from memory VQ, memoryless VQ primarily exploits the correlation between adjacent pixels within a block while disregarding the correlation between neighboring blocks. Several effective schemes were proposed in the past, including the predictive mean search (PMS) algorithm [22], index-compressed VQ (ICVQ) [23], search-order coding (SOC) [24], and the index searching algorithm with index associated list (ISA-IAL) [25]. In particular, the SOC algorithm focuses on searching for indices of the same value from neighboring blocks and utilizing a search-order code to replace the original VQ index. This approach enables effective compression by identifying a significant number of indices with the same value. Building upon this concept, [PERSON] et al. [26] proposed a state codebook scheme in 2009. They sorted the VQ code table using the principal component analysis (PCA) [27] algorithm and enhanced the similarity search with the SOC algorithm, facilitating the detection of highly similar indices. The method introduced by [PERSON] et al. [26] set a milestone and achieved excellent results with the SOC algorithm. However, our new scheme has significantly improved the compression performance. Based on the SOC algorithm, this paper further employs the side match algorithm to recompress the VQ index and achieve lossless restoration of the original VQ index. In comparison to the scheme of [PERSON] et al. [26], our method does not rely on the PCA algorithm and takes into account the similarity between neighboring blocks and the similarity of pixels within each block. Therefore, our contribution is a significant improvement on the compression rate of the VQ index table. The structure of this paper is as follows: Section II discusses the related work, including VQ, SOC, SMVQ, and [PERSON]'s state codebook scheme. In Section III, we present our compression scheme. Section IV presents the experimental results.