乘碼

乘碼（Product code），是藉由許多小型編碼簿相乘而形成。如果一個向量可以用某個獨立的特性來描述的話，例如長度或方向，那麼就可以針對每一個特性分別為此設計一個編碼簿，最後所要的乘碼向量便是將各個小型編碼簿的向量相乘而得到。

概要 
在相同數目的碼向量下，乘碼編碼簿的效率比完全搜尋的編碼簿差。但是在相同的複雜度與位元率下，它的效果比完全搜尋的編碼簿好。這是因為在相同的複雜度下，乘碼編碼簿的有效碼向量會遠比完全搜尋的編碼簿之碼向量多許多，而且乘碼編碼簿可以在同樣位元率下編碼更大維度的向量。

以下介紹三種乘碼，分別為增益/形狀VQ（Gain/Shape vector quantization, G/S VQ）、平均值/餘值VQ（Mean/Residual vector quantization, M/R VQ）及內插法/餘值VQ（Interpolating/Residual vector quantization, I/R VQ）。

增益/形狀VQ 
增益/形狀VQ（Gain/Shape vector quantization, G/S VQ）使用兩個編碼簿，分別用以編碼向量的增益（Gain）和形狀（Shape）。向量的增益指的是這個向量的能量或方差，而向量的形狀則是原影像向量去掉增益後之正常化向量（Normalized vector）。

演算法 
第一步：
將原影像切割成不重疊的方塊形成影像向量，令其大小為n（一般取n = 4 x 4 = 16）。

第二步：
從形狀編碼簿中，找出和影像向量內積（Inner product）所得值最大的單位能量形狀碼向量，。

第三步：
給定所選擇的形狀碼向量後，找出純量的增益值，其中純量使得重建向量，與原向量X之間的失真最小。

第四步：
送出形狀碼向量的指標及增益的碼給接收端。

第五步：
將解碼所得知形狀碼向量與增益值相乘，即得到重建向量。

平均值/餘值VQ 
平均值/餘值VQ（Mean/Residual vector quantization, M/R VQ），是將影像方塊的平均值重複拷貝做為該方塊內所有像素的預測值，最後產生整個預測影像。再將原影像減去預測影像，便形成我們的餘值影像。

使用M/R VQ的優點是許多的影像向量（由影像方塊所組成）都在不同的平均值附近展現類似的方差，只要將每一個向量的平均值（方塊平均值）在做量化之前予以去除，那麼我們所需要用以表示餘值向量的碼向量就會比較少。

演算法 
第一步：
將原影像切割成不重疊的方塊，其大小為n（一般n = 4 x 4 = 16），以形成影像向量，並計算每一個方塊的平均值。

第二步：
以純量量化器編碼平均值（一般使用8個位元）並送出給接收端，也可以用傳統的壓縮法，如DPCM，做平均值的編碼以更進一步降低位元率。

第三步：
將該方塊之原影像向量減去量化後之平均值得到平均約等於0的餘值。

第四步：
以VQ做餘值向量之量化，然後將最接近之餘值碼向量的指標送給接收端。

第五步：
將平均值加回解碼所得之餘值向量得到重建方塊。

內插法/餘值VQ 
內插法/餘值VQ（Interpolating/Residual vector quantization, I/R VQ），是藉由原影像之次取樣（Subsampling）與內插（Interpolating）得到預測影像，然後再將原影像減去預測影像得到的餘值影像。這個方法基本上和Mean/Residual vector quantization（M/R VQ）很像，只不過在此用的是次取樣值而非平均值，以及內插法而不是簡單的重複拷貝。

使用I/R VQ的優點是，其預測影像會比M/R VQ的重複拷貝平均值所得的預測影像還平滑，因此方塊假象（Blocking artifacts）會減少。實驗結果也顯示，在相同的位元率下，I/R VQ的重建影像品質會比M/R VQ的好。

演算法 
第一步：
以L：1的比例（一般L = 8）為原影像做次取樣得到的次取樣影像（原影像為解析度為NxN），每一個次取樣值以純量量化器予以量化，並送出給接收端。

第二步：
傳送端與接收端都利用將量化後之次取樣影像以內插法擴張成NxN的預測影像，將原影像減去預設影像得到傳送端的預測影像。

第三步：
將餘值影像切割成不重疊的方塊以形成向量（一般大小為n = 4 x 4 = 16）。

第四步：
使用VQ為餘值向量做量化，並送出最接近的餘值碼向量之指標給接收端。

第五步：
將解碼所得之餘值碼向量加回次取樣/內插後之預測影像得到重建影像。

參考資料 
 戴顯權，資料壓縮 
 Bhaskar Ramamurthi and Allen::Gersho, Fellow, IEEE ,"Classified Vector Quantization of Images ", IEEE Transactions On Communications, VOL. Com-34, NO. 11, November 1986
 Allen Gersho and Robert M. Gray, "Vector Quantization And Signal Compression"

数据压缩