Vector Quantization(学习Free Mind知识整理)

时间:2021-06-08 16:53:49

阅读http://blog.pluskid.org/?p=57文章中的一些知识整理:

=====================================================================

矢量量化(Vector Quantization)其实也就是逼近,VQ 是将一个向量空间中的点用其中的一个有限子集来进行编码的过程。Vector Quantization------------>http://www.data-compression.com/vq.html#lbg

因为在很多各种能用的聚类方法都可以用,下面是Free Mind的python实现:

from scipy.cluster.vq import kmeans, vq
from numpy import array, reshape, zeros
from mltk import image

vqclst = [2, 10, 100, 256]

data = image.read('example.jpg')
(height, width, channel) = data.shape

data = reshape(data, (height*width, channel))
for k in vqclst:
print 'Generating vq-%d...' % k
(centroids, distor) = kmeans(data, k)
(code, distor) = vq(data, centroids)
print 'distor: %.6f' % distor.sum()
im_vq = centroids[code, :]
image.write('result-%d.jpg' % k, reshape(im_vq,
(height, width, channel)))

=====================================================================

Vector Quantization也介绍了LBG算法,LBG-VQ算法是一个迭代算法,它交替地调整P和C(两个优化准则Nearest NeighborCondition 最近邻条件:Vector Quantization(学习Free Mind知识整理)Centroid Condition质心条件:Vector Quantization(学习Free Mind知识整理) ),使失真度不断地趋向于它的局部最小值(有点EM的思想哦)。最小的C(码书Codebook)和P(空间划分)。

  LBG Design Algorithm

  1. Given Vector Quantization(学习Free Mind知识整理). FixedVector Quantization(学习Free Mind知识整理) to be a ``small'' number.
  2. Let Vector Quantization(学习Free Mind知识整理) and
    Vector Quantization(学习Free Mind知识整理)
    Calculate
    Vector Quantization(学习Free Mind知识整理)
  3. Splitting: For Vector Quantization(学习Free Mind知识整理), set
    Vector Quantization(学习Free Mind知识整理)
    Set Vector Quantization(学习Free Mind知识整理).
  4. Iteration: Let Vector Quantization(学习Free Mind知识整理). Set the iteration indexVector Quantization(学习Free Mind知识整理).
    1. For Vector Quantization(学习Free Mind知识整理), find the minimum value of
      Vector Quantization(学习Free Mind知识整理)
      over all Vector Quantization(学习Free Mind知识整理). LetVector Quantization(学习Free Mind知识整理) be the index which achieves the minimum. Set
      Vector Quantization(学习Free Mind知识整理)
    2. For Vector Quantization(学习Free Mind知识整理), update the codevector
      Vector Quantization(学习Free Mind知识整理)
    3. Set Vector Quantization(学习Free Mind知识整理).
    4. Calculate
      Vector Quantization(学习Free Mind知识整理)
    5. If Vector Quantization(学习Free Mind知识整理), go back to Step (i).
    6. Set Vector Quantization(学习Free Mind知识整理). ForVector Quantization(学习Free Mind知识整理), set
      Vector Quantization(学习Free Mind知识整理)
      as the final codevectors.
  5. Repeat Steps 3 and 4 until the desired number of codevectors is obtained.

LBG-VQ的matlab实现:

LBG:

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,:
)
) ; % 因为这一行太长,所以断行成这样.. =.=b
end

% 给予一个初始的平均改善临界值 ( > 0 就行了.. )
thd = 10 ;

% 给予一个极大的上一代 MSE
er_o = 1000000000000000 ;

% 设定初始代数
tol = 0 ;

% 最多 training 代数
mtol = 1000 ;

indxe = 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
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:

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’) ;
===================================================================
原文:

http://www.data-compression.com/vq.shtml