# Adaptive Vector Quantization for Lossy Compression of Image Sequences +
## 2 The Adaptive Vector Quantization (AVQ) Algorithm
### Logical Architecture  
In Figure 2, we graphically highlight the logical architecture of the AVQ algorithm. As it is noticeable from this figure, the key elements can be subdivided into two distinct categories:  
* _Components_;
* _Heuristics_. A _component_ is a data structure involved in the compression (or in the decompression) phase of the AVQ algorithm. The main components are the following:  
* _Growing Points_ (GPs)  
In contrast with one-dimensional data, two-dimensional data can have several uncoded points, from which an encoding algorithm can continue its encoding process. These points are referred to as _growing points_ (GPs). Figure 3 shows a graphical example in which three GPs are highlighted in red. The encoder selects one GP at each step and identifies a match between the block anchored to the selected GP (we denote the selected GP as \(gp\) from now on) and a similar block (according to a given distortion measure) contained in the dictionary. Therefore, by using the GPs, the AVQ algorithm can continue its encoding process in a deterministic manner. * _Growing Point Pool_ (GPP)  
Figure 3: Examples of growing points. Figure 2: The block diagram of the architecture of the AVQ algorithm. A GPP is a data structure in which all the Growing Points (GPs) are maintained. * _Dictionary_ (D)  
All the blocks derived from the already coded parts of the input image are stored in the dictionary. Such blocks are used to find a match with a block (anchored to a GP) in the not yet coded portion of the input image. It should be noted that the dictionary plays an important role for the compression (and the decompression) of the input image. We can informally define a heuristic as a set of rules that describes the behavior of the AVQ algorithm and its architectural element. Mainly, the heuristics are related to the GPP and the dictionary, and are the following:  
* _Growing Heuristic_ (_GH_)  
A GH highlights the behavior related to the identification of the next GP, which will be extracted from the GPP. Such a GP will be the next one that will be processed by the AVQ algorithm. Several strategies can be adopted to define a GH. The ones used in literature are the following:  
* _Wave Growing Heuristic_  
The Wave GH selects a GP in which the coordinates, \((x_{s},y_{s})\), satisfies the following relationship:  
\[x_{s}+y_{s}\leq x+y\ \forall(x,y)\in\ \mathrm{GPP}.\]  
With this heuristic, the GPP is initialized in this manner: \(\mathrm{GPP}=\ \{(0,\ 0)\}\). The point \((0,\ 0)\) is the pixel at the left top corner. In addition, the image coverage follows perpendicular to the main diagonal by a wavelike trend. * _Diagonal Growing Heuristic_  
The Diagonal GH selects a GP in which the coordinates, \((x_{s},y_{s})\), which satisfies the following relationship:  
\[|x_{s}-y_{s}|\leq|x-y|\ \forall(x,y)\in\ \mathrm{GPP}.\]  
In this scenario, the GPP is initialized in the same way of the initialization of the Wave GH and the image coverage follows perpendicular to the main diagonal. * _LIFO Growing Heuristic_  
A GP is selected from the GPP in _Last-In-First-Out_ (LIFO) order. * _Growing Point Update Heuristic_ (_GPUH_)  
A GPUH defines the behavior related to the updating of the GPP. Indeed, a GPUH defines the set of adding one or more GP to the GPP. * _Init Dictionary Heuristic_ (_IDH_)  
An IDH is a set of rules that define in which manner the dictionary, \(D\), will be initialized. * _Match Heuristic_ (_MH_)  
An MH is used by the AVQ algorithm to identify a match between the block \(b\), anchored to the GP that is undergoing the process (we referred to as \(gp\)), and a block in the dictionary \(D\). Generally,a _distance_ is used (e.g., _Mean Squared Error_ - _MSE_[9], etc.) to define the similarity between a block in the dictionary and the block anchored to _gp_. * _Dictionary Update Heuristic_ (_DUH_)  
A DUH is a set of rules that defines which new block(s) can be added to the dictionary \(D\). Several DUH are explained in literature, as, for instance, the _OneRow_ + _OneColumn_ DUH (outlined in [5]).