有限状态向量量化器

有限状态VQ（Finite state vector quantization, FSVQ）是有记忆性的VQ（Vector quantization, VQ），它可以用一个有限状态机（Finite-state machine）来描述，其中每一个状态各代表一个分开的VQ编码簿。

概要

有限状态VQ与分类VQ（Classified vector quantization，CVQ）相同的是都使用好几个小号编码簿而不是单一一个大型的编码簿。但是，由于FSVQ是利用下一状态函数（Next-state function）来决定哪一个编码簿，而非分类器，因此并没有CVQ所遭遇的问题，像是送与不送用以指明所选用之编码簿的额外信息。下一状态函数是以目前的状态（即其编码簿）及目前的输出码向量为输入，以另一个状态的函数为输出。使用FSVQ的优点是因为相邻的像素方块通常是相似的，因此可以利用这种相关性或累赘，在知道前面方块的结果后，选择一个合适的编码簿。实验的结果显示，FSVQ改善了VQ的效率。

算法

• 第一步：

将原影像切割成大小为n（一般为n = 4 x 4 = 16）而且不相重叠的方块。这些方块排顺序成为一串影像向量，$X_{i},i={0,1,\ldots ,{\frac {N^{2}}{n-1}}}$。

• 第二步：

给定一个起始状态$S_{0}$及其连带之编码簿$C_{S0}$，我们首先为第一个影像向量，$X_{0}$，编码，找出$C_{S0}$中和它最接近的码向量，${\hat {X}}_{0}$，提交${\hat {X}}_{0}$的指针给接收端。

• 第三步：

以前一个状态$S_{0}$、及前一个状态的输出码向量${\hat {X}}_{0}$做为下一状态函数f（.）的输入，求出下一个状态$S_{1}$，即$S_{1}=f(S_{0},{\hat {X}}_{0})$；使用下一个状态$S_{1}$的编码簿$C_{S1}$为下一个影像向量$X_{1}$做编码；假设从$C_{S1}$中所找得最接近的码向量为${\hat {X}}_{1}$，则提交${\hat {X}}_{1}$在$C_{S1}$中的指针给接收端。

• 第四步：

以同样的程序为其余的影像向量做编码（即，求新的状态$S_{n+1}=f(S_{n},{\hat {X}}_{n})$，然后从$C_{Sn+1}$中找出与$X_{n+1}$最接近的码向量${\hat {X}}_{n+1}$并提交奇指针给接收端）。

如前所述，由于下一个状态是以前一个状态以及输出码向量（而不是影像向量本身）的函数，因此接收端可以完全与发送端同步地改变状态而不需要使用额外的信息。但是，这也为这个方法带来了一个缺点：如果发送线发生错误，这个错误会一直影响下去而可能导致即严重的重建误差。

'参考资料

• 戴显权, "资料压缩"
• Allen Gersho, Robert M. Gray, "Finite - State Vector Quantization", The Springer International Series in Engineering and Computer Science Volume 159, 1992, pp 519-553
• Allen Gersho and Robert M. Gray, "Vector Quantization And Signal Compression"