阅读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 最近邻条件: 和Centroid Condition质心条件: ),使失真度不断地趋向于它的局部最小值(有点EM的思想哦)。最小的C(码书Codebook)和P(空间划分)。
LBG Design Algorithm
- Given . Fixed to be a ``small'' number.
- Let and
-
Splitting: For , set
-
Iteration: Let . Set the iteration index.
- For , find the minimum value of
- For , update the codevector
- Set .
- Calculate
- If , go back to Step (i).
- Set . For, set
- For , find the minimum value of
- 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