跳至內容

乘碼

維基百科,自由的百科全書

乘碼(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"[1]頁面存檔備份,存於網際網路檔案館