- Linde-Buzo-Gray (LBG) 演算法
在編碼簿的產生上,我使用了 LBG 演算法,來簡單的將原始圖片進行 training 的動作,以得到一本屬於該圖片的 Codebook ,而由於整個 training 的動作並未做最佳化的調整,故其並非一個最佳效果的 Implement ,在此特別說明。
Matlab Codefunction [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
- 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') ;
我們以下面幾種方式來進行測試,分別為 Codebook Nc = 64, 128 及 Code Length = 2, 4, 16 在平均失真改善比小於 0.001 時停住。
我們使用的測試圖片就是做影像的人都認識的大美女-Lenna ( 聽說她本人知道他在學術界這麼紅也嚇了一跳.... )
而我們使用 EzVQ 函式之後,可以看到以下的結果:
EzVQ('lenna.bmp', 64, 2, 0.001, 256, 256) ;
EzVQ('lenna.bmp', 64, 4, 0.001, 256, 256) ;
EzVQ('lenna.bmp', 64, 16, 0.001, 256, 256) ;
EzVQ('lenna.bmp', 128, 2, 0.001, 256, 256) ;
EzVQ('lenna.bmp', 128, 4, 0.001, 256, 256) ;
EzVQ('lenna.bmp', 128, 16, 0.001, 256, 256) ;
其實從上面的實驗結果可以得到,影響 VQ 效果最重大的,其實還是你的 Code Length,而提升 Nc 雖然可以得到一個較佳的 MSE ,可是畢竟是數字上的改變,那其實對肉眼的差別並沒有多大的提升。
有興趣的人可以自己拿回去研究囉,不過請注明出處吧。
原作者:
回覆刪除張貼時間: 2008-06-20T04:21:21.000-08:00
??? Error using ==> reshape
To RESHAPE the number of elements must not change.
Error in ==> LBG_training at 3
Training_set = reshape(ImgPxl(:), Training_idx, Vector_Len) ;
Error in ==> EzVQ at 4
[codebook index] = LBG_training(ImgPxl, Nc, Vector_Len, er, x, y) ;
原封不動拿去跑 會有上述的錯誤唷XD~
reshape 好像出問題了
原作者:
回覆刪除張貼時間: 2008-06-20T04:29:49.000-08:00
喔喔 抱歉 我知道哪裡出問題囉~
請問一下,是那裡錯了嗎? 不好意思,是matlab新手,謝謝
回覆刪除??
回覆刪除沒有錯吧?
上面的程式是可以執行的,至少在當年我用的時候可以.. ^^b
謝謝你這麼快的回覆,不知道為何,我也出現這樣的錯誤
回覆刪除??? Error using ==> reshape
To RESHAPE the number of elements must not change.
Error in ==> LBG_training at 3
Training_set = reshape(ImgPxl(:), Training_idx, Vector_Len) ;
Error in ==> EzVQ at 4
[codebook index] = LBG_training(ImgPxl, Nc, Vector_Len, er, x, y) ;
抱歉,我手上沒有 matlab 可以幫你 debug 耶..
回覆刪除不過我只能肯定我當初的 code 就只有這樣啦....
不好意思沒幫上忙..
indxe = zeros(Training_idx,1) ;
回覆刪除這邊應該是index
然後有些CODE在這個網誌好像被強制換行
要記得合併成一行
看來我找個時間把我貼 code 的介面換一下好了...
刪除您好
回覆刪除想請問您
您上面的留言寫道reshape有錯誤
請問是哪裡有錯!?
看起來應該是你的 x 跟 y 輸入的大小跟圖片不同吧...
刪除