# An Innovative Recompression Scheme for VQ Index Tables
## 2 Related Work
### Search-Order Coding Algorithm  
SOC [24] is a technique proposed by [PERSON] and [PERSON] in 1996 for achieving further compression without causing image distortion. The SOC algorithm aims to further compress VQ compressed data. It utilizes a raster scan approach, moving from left to right and top to bottom. The current search point serves as the search center (SC), and a spiral search is conducted along the search path. The search-order code is expressed in binary, where \(n\) represents the number of bits, and the search range is \(2^{n}\). Typically, the SOC algorithm performs best when \(n\) is set to 2 or 3. If an index value equal to the center is found, the new SOC index can replace the VQ index, resulting in recompression. If a match is not  
Figure 1: Encoding step of VQ.  
found, the original VQ index is still used for representation. To differentiate between the two cases, an additional 1-bit indicator is required. Due to the high degree of similarity between neighboring blocks, the SOC algorithm is capable of successfully searching for a large number of indices, effectively achieving the goal of recompression.  
As shown in Figure 2, the SOC algorithm defines four starting search points (SSPs), which can be used as needed. If a fixed SSP is preset and remains unchanged, no additional auxiliary information is required. However, if the SSP needs to be determined dynamically, an additional bit is required as an indicator to record the SSP.  
Figure 3 depicts two examples at different SSPs, specifically the cases where the SSP is 1 and 4. The search is performed starting from the block currently being processed, following the spiral search path originating from the respective SSP. Since the SOC algorithm operates based on raster search, we can only search blocks that have been processed. Blocks that have not been processed cannot participate in the search, as doing so would result in an irreversible final index with respect to the original VQ index. In the figure, we use a black circle to represent the SC and a gray block to represent the SSP. Blocks with solid borders represent points that can be searched, while blocks with dashed borders represent points that cannot be searched. We connect the points with blue arrows to represent the search path.  
Figure 3: Search path of SOC algorithm at different SSPs. (**a**) SSP = 1. (**b**) SSP = 4.  
Figure 2: Four starting search points.  
Figure 4 provides an example with \(n=2\), where the blue square represents the starting search center with an index value of 44. The solid blocks indicate valid search points. Each search step is encoded in binary format. In the starting step, \"00\", the value is 48, which is not the target value of 44. The search continues, and the step count increases until either a 44 is found or the predetermined 2-bit tolerance search count is reached. If an index value appears earlier in the search path, it signifies a repetition that can be skipped, and the search count is not increased. In the example shown in Figure 4, a match of 44 is found in the last step, which corresponds to \"11\". Therefore, we can substitute the SOC index for the VQ index. Assuming a codebook size of 256, which represents the VQ index using 8 bits, we can use \"11\" to replace the binary representation \"00101100\" for the value 44.  
The decoding step also follows the order of raster scanning. Upon receiving the compressed code, the decoder can differentiate between the SOC index and the original VQ index based on the index indicator. It then performs a search process similar to encoding, utilizing the same SSP and \(n\) as used in encoding. Finally, the original VQ index can be restored and the VQ codebook enables the reconstruction of the image.