# An Innovative Recompression Scheme for VQ Index Tables
## 3 Proposed Scheme  
In this section, we present a scheme that combines the SOC algorithm with the side match algorithm, allowing for a higher number of codewords to be searched and significantly improving the compression rate. In our proposed scheme, we classify all the indices in the index table into three types. The first type consists of indices generated by the SOC algorithm for search-order coding. The second type comprises indices generated by the side match algorithm for match order coding. The third type includes indices representing the original VQ codewords, excluding the first two types. To enable the decoder to distinguish between these three types in the compressed code, an additional indicator should be added in front of the compressed code for each index. Since we only have three types, we can use one or two bits to represent them. Based on the experimental results, it was observed that the first type generally allows for a greater number of codewords to be searched. Consequently, for achieving more efficient compression, it is \begin{table}
\begin{tabular}{c c} \hline \hline \multicolumn{2}{c}{The similar neighboring (3, 2), which equals “55”} \\ \hline The index of the state codebook & The indices of the closest codewords of “55” in the codebook \\ \hline
0000 & 51 \\ — & 52 \\
0001 & 53 \\
0010 & 54 \\
0010 & 56 \\
0011 & 57 \\ \hline \hline \multicolumn{2}{c}{The similar neighboring (2, 2), which equals “54”} \\ \hline The index of the state codebook & The indices of the closest codewords of “54” in the codebook \\ \hline
0100 & 49 \\
0101 & 50 \\
0110 & 58 \\
0111 & 89 \\ \hline \hline \multicolumn{2}{c}{The similar neighboring (2, 4), which equals “52”} \\ \hline The index of the state codebook & The indices of the closest codewords of “52” in the codebook \\ \hline
1000 & 47 \\
1001 & 48 \\
1010 & 60 \\
1011 & 61 \\ \hline \hline \multicolumn{2}{c}{The similar neighboring (3, 1), which equals “46”} \\ \hline The index of the state codebook & The indices of the closest codewords of “46” in the codebook \\ \hline
1100 & 44 \\
1101 & 45 \\
1110 & 62 \\
1111 & 63 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The state codebook of Figure 6.  
common to utilize shorter designators for the more frequently occurring types. Specifically, we commonly assign \"0\" to the first type, \"10\" to the second type, and \"11\" to the third type. Subsequently, we elucidate the three types of situations by providing concrete examples as follows:  
In the given examples, we train a codebook with 256 codewords, and each codeword is a 16-dimensional vector. The SOC algorithm operates according to the rule that SSP equals 1, and the bit number \(n\) of the search-order code is equal to 2. Case 1: The index is found by the SOC algorithm. As shown in Figure 7, the index equal to the SC is located at (3, 1). Additionally, we observe that the indices at (2, 3) and (2, 4) are duplicates, both equal to 41, which is the same as the index at (2, 2). Hence, they can be ignored. By searching sequentially, we find that the search-order code corresponding to the SC is \"10\". Since the first type of indicator is \"0\", the final index value is \"010\". **Case 2:** The SOC algorithm does not find it, and the index is found through the side match algorithm. As shown in Figure 8, because the blocks of the image are searched in raster scan order, for the processed block \(P\), the indices of the upper neighboring block \(U\) and left neighboring block \(L\) have been restored. We need to use the data of \(U\) and \(L\) to find some of the closest codewords from the codebook to restore \(P\). We define the pixels adjacent to \(U\) and \(L\) in \(P\) as \(P_{1}=\frac{U_{41}+U_{41}}{2}\), \(P_{2}=U_{42}\), \(P_{3}=U_{43}\), \(P_{4}=U_{44}\), \(P_{5}=L_{24}\), \(P_{6}=L_{34}\), and \(P_{7}=L_{44}\). We extract the codewords from the codebook one by one. For each 16-dimensional codeword, we convert it into a \(4\times 4\) calculated block \(C\). For simplicity, we replace their coordinates with numbers.