Vector Quantizer LBG 矢量量化简要实例算法

尊重原创,请勿转载!  作者:图林根的烤肠

文章来源: www.mahong.me/archives/63

最近忙于考试复习 ADSP (数字信号处理) 中,查看了一些资料,大多写的十分繁琐,一点都不生动形象,特此举个实例,方便理解,文章内容来源于课上的课件.

基本名词解释等相关资料请查询其它网站,这里只是实例举例:

输入的 Training Set 为:x = [3,2,4,5,7,8,8,9]. 注:(我个人理解Training Set是一种替代pdf的方法,按照N维向量分割后的输入信号,这里我个人也不是特别明白,希望他人讲解。)

N=2,这里是维数,2维空间,xy二轴

 


第一步:随机生成两个codebook vectors y1与y2,比如说y1=[1,2] ;y2 =[5,6]: 然后把x数值按照N维空间分类,这里N=2,所以分为[3,2], [4,5], [7,8], [8,9]

第二步:求出decision boundary bk ,其中bk等于(y1+y2)/2 ,我们求出bk为[3,4],然后画出一条直线,用来划分空间,注:此处的直线是垂直于连接y1y2的直线,作用是为了便于观察才画出来的, 不影响计算机的其他运算。第三步的图片可以清晰说明。

第三步:把所有的x点归类,划分到y1或者y2的空间里面,距离计算公式就是简单的两点间向量计算公式

对于点x1=[3,2]到y1=[1,2]的距离为:d1=√(3−1)2+(2−2)2=√4

到y2 =[5,6]的距离为 d2=(5−3)+(6−2)=√20

所以划分到y1区间,同理计算出其它x点的所属范围。如下图所示

v1

第四步:计算新的codewords yk 作为Voronoi空间的质心(centroid or conditional expectation ),其中的yk计算方法为

v2

简要的说就是Vornonoi空间里所有的点的数值求和在除以在这个空间里面点的个数,此处的例子是

在Voronoi region1中只有一个点x1,所以新的y1为x1,也就是[3,2]

再来看Voronoi region 2里面,y2的计算方法为:

v3

计算完后移动这两个y1y2为新的质心重复第二步骤即可

v4

编程的例子就不写了,原理大概明白编起来也不是很困难的,最后通过这个算法的实际图例大概如下图所示,当然不是上面所举的那个例子

v5

最后推荐一个很好中文翻译相关博客,欢迎指出错误,发言回复。

 

参考资料:

1. Digital Signal Processing 2/ Advanced Digital Signal Processing  Lecture 5, Vector Quantizer, LBG  Gerald Schuller, TU Ilmenau

2. http://www.data-compression.com/vq.html