# Adaptive Vector Quantization for Lossy Compression of Image Sequences +
## 2 The Adaptive Vector Quantization (AVQ) Algorithm
### Compression and Decompression Phases  
Algorithm 1 highlights the pseudo-code of the AVQ compression phase. Firstly, the dictionary \(D\) and the _GPP_ are initialized. The dictionary \(D\) is initialized by one entry for each value that a pixel can assume (i.e., in the case of grayscale images, \(D\) will be initialized with 256 values, from 0 to 255). At each step, the AVQ algorithm selects a growing point from the growing point pool _GPP_ (we referred to as _gp_), according to a specified growing heuristic (GH). The algorithm ends when there are no further selectable growing points (i.e., the _GPP_ is empty). Figure 4: An example of the _OneRow+OneColumn_ Dictionary Update Heuristic. (**a**) The matched block; (**b**) The first added block into the dictionary; (**c**) The second block added into the dictionary. Subsequently, the encoder uses a match heuristic (MH) to individuate which block, stored in the local dictionary \(D\), is the best match for the one anchored to \(gp\) (see Figure 5). In general, the matching heuristics prefer the largest block in \(D\), which presents a distortion measure that is less than or equal to a threshold \(T\), when compared with the block anchored to \(gp\). The threshold \(T\) can be fixed for the whole image or can be dynamically adjusted by considering the image content, in order to improve the quality perception. Once the match is performed and a block in \(D\) is identified, the index of this block (denoted as \(b\) in Algorithm 1) can be stored or transmitted. An index can be represented with \(\log_{2}|D|\) bits (\(|D|\) is the size of the dictionary \(D\)). After that, the dictionary \(D\) is updated, by adding one or more blocks to it. The update is directed by the rules defined by a dictionary update heuristic (DUH). If \(D\) is full, a deletion heuristic (DH) is invoked to eventually make space in \(D\). Finally, the GPP is also updated by using a growing update heuristic (GUH). The processed growing point (i.e., \(gp\)) is removed from the \(GPP\). Thus, such a growing point will not be further processed. It is important to point out that the compression performances are strictly dependent on the number of indexes that will be stored or transmitted by the encoder. Indeed, by considering that each block is represented by its index in the dictionary, more blocks will be necessary to cover the input image, and it will be necessary for more indices to be stored or transmitted. Vice versa, less blocks will be necessary to cover the input image, and it will be necessary for less indices to be stored or transmitted. Consequently, even the dimensions of the matched blocks can influence the compression performances. In fact, the matched blocks with larger dimensions can increase the compression performances, since they cover larger portions of the input image. Algorithm 2 reports the pseudo-code related to the AVQ decompression phase. Substantially, the pseudo-code is symmetrical, except for the fact that the decompression phase does not need to identify the match, since it receives the indices from the encoder (or reads the indices from a file). ```
1.\(GPP\leftarrow\) Initial GPs (e.g., the \(GP\) at coordinates \((0,\ 0)\))
2.\(D\leftarrow\) Use an IDH for the initialization
3.whileGP has more elements do
4. Use a \(GH\) to identify the next \(GP\)
5. Let \(gp\) be the current \(GP\)
7. Receive \(\log_{2}|D|\) bits representing the index of a block \(b\) into the dictionary \(D\)
8. Anchor \(b\) to the current \(GP,gp\), in order to reconstruct the output image
9. Update \(D\) with a \(DUH\)
10.if\(D\) is full then
11. Use a \(DH\)
12.endif
13. By using a \(GPU\), update the \(GPP\)
14. Remove \(gp\) from \(GPP\)
15.endwhile
```  
**Algorithm 2** Pseudo-code of the _decompression stage_ (AVQ algorithm). Figure 5: Examples of matching heuristics. In Figure 6a, we graphically show, in _false-colors_, the progress of Algorithm 1, on the image denoted as _Lena_.