有限狀態向量量化器

Template:TA Template:Cleanup-jargon 有限狀態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,\dots ,\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"