Categories

Calendar

January 2022
M T W T F S S
« Jun    
 12
3456789
10111213141516
17181920212223
24252627282930
31  

漫谈 Clustering (番外篇): Vector Quantization

stallman本文是“漫谈 Clustering 系列”中的第 3 篇,参见本系列的其他文章。

在接下去说其他的聚类算法之前,让我们先插进来说一说一个有点跑题的东西:Vector Quantization 。这项技术广泛地用在信号处理以及数据压缩等领域。事实上,在 JPEG 和 MPEG-4 等多媒体压缩格式里都有 VQ 这一步。

Vector Quantization 这个名字听起来有些玄乎,其实它本身并没有这么高深。大家都知道,模拟信号是连续的值,而计算机只能处理离散的数字信号,在将模拟信号转换为数字信号的时候,我们可以用区间内的某一个值去代替着一个区间,比如,[0, 1) 上的所有值变为 0 ,[1, 2) 上的所有值变成 1 ,如此类推。其这就是一个 VQ 的过程。一个比较正式一点的定义是:VQ 是将一个向量空间中的点用其中的一个有限子集来进行编码的过程。

一个典型的例子就是图像的编码。最简单的情况,考虑一个灰度图片,0 为黑色,1 为白色,每个像素的值为 [0, 1] 上的一个实数。现在要把它编码为 256 阶的灰阶图片,一个最简单的做法就是将每一个像素值 x 映射为一个整数 floor(x*255) 。当然,原始的数据空间也并不以一定要是连续的。比如,你现在想要把压缩这个图片,每个像素只使用 4 bit (而不是原来的 8 bit)来存储,因此,要将原来的 [0, 255] 区间上的整数值用 [0, 15] 上的整数值来进行编码,一个简单的映射方案是 x*15/255 。

VQ 2

VQ 2

不过这样的映射方案颇有些 Naive ,虽然能减少颜色数量起到压缩的效果,但是如果原来的颜色并不是均匀分布的,那么的出来的图片质量可能并不是很好。例如,如果一个 256 阶灰阶图片完全由 0 和 13 两种颜色组成,那么通过上面的映射就会得到一个全黑的图片,因为两个颜色全都被映射到 0 了。一个更好的做法是结合聚类来选取代表性的点。

实际做法就是:将每个像素点当作一个数据,跑一下 K-means ,得到 k 个 centroids ,然后用这些 centroids 的像素值来代替对应的 cluster 里的所有点的像素值。对于彩色图片来说,也可以用同样的方法来做,例如 RGB 三色的图片,每一个像素被当作是一个 3 维向量空间中的点。

用本文开头那张 Rechard Stallman 大神的照片来做一下实验好了,VQ 2、VQ 10 和 VQ 100 三张图片分别显示聚类数目为 2 、10 和 100 时得到的结果,可以看到 VQ 100 已经和原图非常接近了。把原来的许多颜色值用 centroids 代替之后,总的颜色数量减少了,重复的颜色增加了,这种冗余正是压缩算法最喜欢的。考虑一种最简单的压缩办法:单独存储(比如 100 个)centroids 的颜色信息,然后每个像素点存储 centroid 的索引而不是颜色信息值,如果一个 RGB 颜色值需要 24 bits 来存放的话,每个(128 以内的)索引值只需要 7 bits 来存放,这样就起到了压缩的效果。

VQ 100

VQ 100

VQ 10

VQ 10

实现代码很简单,直接使用了 SciPy 提供的 kmeans 和 vq 函数,图像读写用了 Python Image Library :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#!/usr/bin/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 并不一定要用 K-means 来做,各种能用的聚类方法都可以用,只是 K-means 通常是最简单的,而且通常都够用了。

26 comments to 漫谈 Clustering (番外篇): Vector Quantization

  • rss有问题,至少google reader读不出来

  • james :
    rss有问题,至少google reader读不出来

    不是,因为现在 Host 还没有着落,这个还只是放在内网里的,所以 Google Reader 访问不到。

  • Passer Dj

    最近用VQ遇到个问题
    就拿RGB压缩来说,把一个颜色值作为3维空间中的一个点,用欧式距离进行聚类,得到k个centroids,也就是k个颜色索引。这时如果任意给出一个颜色值(RGB),怎么知道应该归入那种索引颜色,也就是在空间中这个点离哪个centroid最近。
    不至于非要全都比一遍吧。

  • @Passer Dj
    你说得没错,但是如果你觉得这个过程很慢的话,可以用一些特殊的数据结构进行加速,不过这方面我没有研究过,所以也不能提供什么具体的建议了。

  • Alex

    这个初始值最好是在0-255之间吧,否则有可能是悲剧啊.
    pluskid这个专题做的真棒,赞一个

  • […] Clustering 有密切联系。比如我们在谈 Vector Quantization 的时候就曾经用 K-means […]

  • maxint

    总结的很细致,不错!

  • […] Clustering 有密切联系。比如我们在谈 Vector Quantization 的时候就曾经用 K-means […]

  • […] Clustering 有密切联系。比如我们在谈 Vector Quantization 的时候就曾经用 K-means […]

  • 我又來捉虫了:
    [cite]
    …代替对应的 cluster 里的说有点的像素值
    [/cite]

    說有點 -> 所有點

  • […] Clustering 有密切联系。比如我们在谈 Vector Quantization 的时候就曾经用 K-means […]

  • […] Vector Quantization : 漫谈 Clustering (番外篇): Vector Quantization […]

  • yuan

    那个图像的例子貌似应该属于scalar quantization而不是vector quantization吧。图像处理里的VQ一般是对一块一块的区域(比如3*3的block)进行量化吧。

    • 向量空间中把点 assign 到某些固定的点应该都叫 vector quantization ,图像中每个像素 RGB 值其实也是一个向量。不过我确实不知道是不是图像处理中有把按照像素来 quantization 称作 scalar quantization 的专门称呼。

  • Yukis

    测试之后感觉kmeans的速度不咋地=。=
    kmeans的向量个数在图片较大的时候太多会很慢,所以图像大的时候我均匀地取了图像上很多个点出来kmeans。但是这样的话其他没有被选出来的点就要和每个类比较一遍距离的远近了,速度上不太好上去呢。

    • KMeans 加速工作有不少的,你可以搜一下 MPIKmeans 。另外,关于近邻搜索,有不少 approximate nearest neighbor 的工作,用 KDTree 之类的,特别在维度低的时候应该是非常有效的,如果有需要的话,也可以查阅一下相关工作。

  • 看到vector quantization还以为是将代码的向量化加速呢……原来还有这种意思,看来要多看看算法了!
    其实图像压缩用DCT和小波比较成熟和实用

  • […] Clustering 有密切联系。比如我们在谈 Vector Quantization 的时候就曾经用 K-means […]

  • Jinfeng

    学长的blog写的真棒,MSTCer过来帮学长打打气~~

  • fk

    看了楼主博客,感觉真心不错,学到不少东东。有一个低级问题想问下:VQ2不应该是分别对RBG三个通道进行计算吗?所以出来应该是个彩色的而不是黑白的图像吧?怎么弄?

  • NotDeep

    博主,您好。。这篇博文很经典! 想请教您一下,code中from mltk import image 这里的image是个什么库

  • Yizhi Li

    写得很棒,一下就懂了

Leave a Reply to james

 

 

 

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>