Matlab - Easy Vector Quantization Implement

在學校修了資料壓縮的課程，而期中的 Project 是要完成一個 Vector Quantization 的圖像壓縮程式，為了結省開發成本，決定使用 Matlab 來開發( 其實是因為這個 Project 我拖到 deadline 前五天才寫....)，以下為整個程式的簡單介紹及成果。

---

1. Linde-Buzo-Gray (LBG) 演算法
   
   在編碼簿的產生上，我使用了 LBG 演算法，來簡單的將原始圖片進行 training 的動作，以得到一本屬於該圖片的 Codebook ，而由於整個 training 的動作並未做最佳化的調整，故其並非一個最佳效果的 Implement ，在此特別說明。
   Matlab Code

   function [codebook index] = LBG_training(ImgPxl, Nc, Vector_Len, er, x, y) 
     Training_idx = (x*y)/Vector_Len ; 
     Training_set = reshape(ImgPxl(:), Training_idx, Vector_Len) ; 
   
     codebook = zeros(Nc, Vector_Len) ; 
   
     for i = 1 : Nc 
       % 此為最原始設計之初使化 Codebook 演算法，但因效果太差 
       % 更換為下面那一種先做一些平均的動作後取得之演算法。 
       %mean(Training_set((i-1)*Training_idx/Nc+1:i*Training_idx/Nc,:)) 
       % 
   
       Child_num = Training_idx/Nc ; 
   
       codebook(i,:) = mean(Training_set(
              ((i-1)*Child_num+1)+Child_num/4:i*Child_num-Child_num/4,:));
     end 
   
     % 給予一個初始的平均改善臨界值 ( > 0 就行了.. ) 
     thd = 10 ; 
   
     % 給予一個極大的上一代 MSE 
     er_o = 1000000000000000 ; 
   
     % 設定初始代數 
     tol = 0 ; 
   
     % 最多 training 代數 
     mtol = 1000 ;
   
     index = zeros(Training_idx,1) ; 
     ver_d = zeros(Training_idx,1) ; 
   
     % Training 初始化 
     for i = 1 : Training_idx 
       tmp = Training_set(i,:) ; 
       er_ds = sum( 
                ((tmp(ones(size(codebook,1),1),:)-codebook).^2).' 
               )/Vector_Len ; 
   
       [ver_d(i) index(i)] = min(er_ds) ; 
     end 
   
     while( er < thd && tol < mtol) 
       for i = 1 : Nc 
         codeset = find(index == i) ; 
         if ~isempty(codeset) 
           codebook(i,:) = mean([Training_set(codeset,:) ;codebook(i,:)]) ; 
         else 
           % 更新法則，非常精簡及沒有特別的理論版。  
           if i == 1 
             codebook(i,:) = mean(codebook([2 3],:)) ; 
           elseif i == Nc 
             codebook(i,:) = mean(codebook([Nc-1 Nc-2],:)) ; 
           else 
             codebook(i,:) = mean(codebook([i+1 i-1],:)) ; 
           end 
         end 
       end 
   
       while (1) 
         %以新的 Codebook 針對每一筆 block ，進行選擇 Code 的動作 
         for i = 1 : Training_idx 
           tmp = Training_set(i,:) ; 
           % 計算這一代的誤差 
           er_ds = sum( 
               ((tmp(ones(size(codebook,1),1),:)-codebook).^2).' 
                   )/Vector_Len ; 
           [ver_d(i) index(i)] = min(er_ds) ; 
         end 
   
         if (~(er_o == mean(ver_d)))  
           break ; 
         else 
         % 若誤差完全沒有改善，則想辨法再弄一本新的 Codebook 
         % 這一部份是我自己做的改進，因為有時會太早收歛， 
         % 且太誇張，所以我會希望他再繼續做下去。 
         % 同樣的，這個演算法也很爛，要有好的效果，請改寫這一段 
           for i = 2 : Nc-1 
             codebook(i,:) = mean(codebook([i-1 i i+1],:)) ; 
           end     
         end 
       end 
   
       thd = abs((er_o - mean(ver_d.^2))/er_o) ; 
       er_o = mean(ver_d.^2) ; 
   
       tol = tol + 1 ; 
     end 
     tol 
     thd
   

2. VQ Implement
   
   而當我們利用上面的函式取得 Codebook 之後，我們便可進行編碼的動作，由於我的LBG-training除了計算出 Codebook，也有將原圖參考 Codebook 後的 Code 輸出(index)，於是，我們可以利用這個來將圖形做一個重建的動作。

Matlab Code

function EzVQ(ImgFile, Nc, Vector_Len, er, x, y) 
    ImgPxl = double(imread(ImgFile)) ;
    [codebook index] = LBG_training(ImgPxl, Nc, Vector_Len, er, x, y) ; 

    VQImg = ones((x*y)/Vector_Len, Vector_Len) ; 

    % 利用 codebook 來進行解碼 
    VQImg = codebook(index,:) ; 

    VQImg = reshape(VQImg(:), x, y) ; 
    MSE = mse(ImgPxl - VQImg) 

    figure(gcf()+1) ; 
    imshow(uint8(ImgPxl)) ; 
    title('Source Image') ; 
    figure(gcf()+1) ; 
    imshow(uint8(VQImg)) ; 
    title('VQ Image') ;

Results
我們以下面幾種方式來進行測試，分別為 Codebook Nc = 64, 128 及 Code Length = 2, 4, 16 在平均失真改善比小於 0.001 時停住。

我們使用的測試圖片就是做影像的人都認識的大美女-Lenna ( 聽說她本人知道他在學術界這麼紅也嚇了一跳.... )

Lenna.jpg

而我們使用 EzVQ 函式之後，可以看到以下的結果：

EzVQ('lenna.bmp', 64, 2, 0.001, 256, 256) ;

64_2_256_256jpg.jpg

EzVQ('lenna.bmp', 64, 4, 0.001, 256, 256) ;

64_4_256_256.jpg

EzVQ('lenna.bmp', 64, 16, 0.001, 256, 256) ;

64_16_256_256.jpg

EzVQ('lenna.bmp', 128, 2, 0.001, 256, 256) ;

128_2_256_256.jpg

EzVQ('lenna.bmp', 128, 4, 0.001, 256, 256) ;

128_4_256_256.jpg

EzVQ('lenna.bmp', 128, 16, 0.001, 256, 256) ;

128_16_256_256.jpg

Concrusion
其實從上面的實驗結果可以得到，影響 VQ 效果最重大的，其實還是你的 Code Length，而提升 Nc 雖然可以得到一個較佳的 MSE ，可是畢竟是數字上的改變，那其實對肉眼的差別並沒有多大的提升。

有興趣的人可以自己拿回去研究囉，不過請注明出處吧。

By Lak@CYUT