机器学习Matlab实战之图像压缩————Kmeans算法

浏览数：61 / 时间：2015年06月08日

本系列来自于我《人工智能》课程复习总结以及机器学习部分的实验总结

Kmeans是机器学习中最经典的无监督学习聚类算法，本文复习了无监督学习定义和Kmeans算法，然后提出了一种基于Kmeans算法的图像压缩方案，并给出了其在Matlab中的实现

1.无监督学习

通过非标记数据样本 $(\vec{X_i})，i=1,...,N$ 且 $\vec{X_i}\in \mathcal{X}$ ，来学习发现这些无标记样本之间内在的相似联系，叫做无监督学习

无监督学习由于没有标记，那就不存在学习误差或奖惩函数来评估一个可行解，这是无监督学习和监督学习最大的差别

2.Kmeans聚类

2.2聚类

最常见的无监督学习的方法是聚类，聚类是把数据对象集合通过静态分类的方法划分成多个不相交子集并且让这些子集中的对象都有一些相似的属性的机器学习方法

相似的定义量化到多维坐标系中就是拥有更短的空间距离

最经典也最简单的聚类算法是Kmeans聚类

2.3Kmeans算法

Kmeans算法需要预先设定聚类个数K，然后以K个点为中心进行迭代聚类，每轮迭代中把数据归结到离自己最近的中心点所代表的类中，然后更新中心点继续迭代

算法可以归纳为：

选择聚类个数K
选择K个初始中心点（一般随机产生或数据可视化后挑选较优聚类中心）
迭代开始，对每个数据点计算其到所有K个中心点的距离，选取距其最近的中心点所代表的聚类作为该数据点的聚类
在所有数据点确定其新聚类后，更新每个聚类的新中心点（通常聚类中所有数据点求平均值作为该聚类新中心点）
重复3、4直到聚类中心点收敛（通常会定义最大迭代次数）

Kmeans算法简洁易懂、收敛速度较快，是机器学习算法中最经典的聚类算法，但它也有以下缺点：

K需要预先设定，在无法直接观察数据分布的情况下较难确定聚类个数
对初始聚类中心的优良性依赖较大
抗干扰性较弱

3.Kmeans与图像压缩

3.1压缩算法设计

怎样把聚类算法应用到图像压缩中呢？

我们可以从颜色空间压缩入手：

考虑一个512x512大小的RGB图像，若每个像素点都有3个8bit（uint8类型，0-255）的值分别对应其红、绿、蓝三种颜色的色彩强度，则这幅图像需要512x512x3x8bit = 786432Byte = 768KB来保存图像信息（不包括文件头）

很容易发现一幅图像中一般不会囊括RGB色彩空间中的每一种颜色，而其往往包含多个主色调，那么我们可以通过Kmeans算法来减少图片中的颜色，如降低到K=16种颜色（记该颜色空间为K颜色空间），则每个像素点仅需要log2(16)=4bit来标识颜色

我们可以设计一种新的图片格式，除了必要的文件头以外，还需要记录：

压缩K颜色空间和RGB颜色空间的映射关系：即给出0-15代表的K=16种颜色，需要索引出对应的uint8类型RGB值
每个像素点的K颜色空间颜色值

那么我们可以粗略计算理想压缩比为：

786432 B 512 \times 512 \times ( l o g 2 ( 16 ) / 8 ) B + 16 \times 3 B = 786432 B 131120 B = 5.99780

$\frac{786432B}{512\times 512 \times (log_2(16) / 8) B + 16 \times 3B}=\frac{786432B}{131120B}=5.99780$

实际压缩比应该比该值小，需要注意的是这事一种有损图像压缩方案并且压缩比率也不是很高（只利用了色彩信息，没有利用空间信息），并且人眼察觉明显（见结果部分），这里只是作为基本机器学习算法的练习，实际图像压缩一般不会采取该压缩方案

3.2Kmeans图像压缩

Kmeans可以作为颜色空间压缩的聚类算法，具体的做法是

取聚类个数K=16
随机产生K个初始中心二维坐标，选取出它们的颜色（1x3向量）作为颜色聚类初始中心点
迭代开始，枚举图像中所有像素点，对每个像素点计算其颜色到所有K个中心点的距离，这里可以用欧式距离，选取距其最近的中心点所代表的聚类作为该像素点颜色的聚类
在所有像素点确定其颜色的新聚类后，更新每个颜色聚类的新中心点（求平均值）
重复3、4直到最大迭代次数

如果我们直接考虑对原始图像颜色聚类，单线程Matlab程序需要较长时间，因此我们先对其较小的压缩过的图像进行颜色聚类，选取出16个颜色中心后，在枚举较大图像所有像素点，做一次聚类然后更改颜色即可（注：此方法仅仅出于节约时间的目的，老师要求）

3.3Matlab实现

下面给出Matlab用Kmeans算法压缩图片的代码：

clear all;

small = double(imread(‘../data/bridge_small.bmp‘));

h = size(small, 1);
w = size(small, 2);

kn = 16;
key = zeros(kn, 3);

for i = 1 : kn
    x = round(random(‘unif‘, 1, h));
    y = round(random(‘unif‘, 1, w));
    for j = 1 : 3
        key(i, j) = small(x, y ,j);
    end
end

iterate = 50;

for t = 1 : iterate
    sum = zeros(kn, 3);
    count = zeros(kn, 1);

    for i = 1 : h
        for j = 1 : w
            mind = dis(key(1, :), small(i, j, :));
            mink = 1;
            for k = 2 : kn
                d = dis(key(k, :), small(i, j, :));
                if d < mind
                    mind = d;
                    mink = k;
                end
            end
            count(mink) = count(mink) + 1;
            for c = 1 : 3
                sum(mink, c) = sum(mink, c) + small(i, j, c);
            end
        end
    end

    for k = 1 : kn
        key(k, :) = round(sum(k, :) / count(k));
    end
end

large = double(imread(‘../data/bridge_large.bmp‘));
compressed = large;

h = size(large, 1);
w = size(large, 2);

for i = 1 : h
    for j = 1 : w
        mind = dis(key(1, :), large(i, j, :));
        mink = 1;
        for k = 2 : kn
            d = dis(key(k, :), large(i, j, :));
            if d < mind
                mind = d;
                mink = k;
            end
        end
        for c = 1 : 3
            compressed(i, j, c) = key(mink, c);
        end
    end
end

figure
subplot(1,2,1)
imshow(uint8(round(large)))
title(‘original‘)

subplot(1,2,2)
imshow(uint8(round(compressed)))
title(‘compressed‘)

imwrite(uint8(round(compressed)), ‘compressed.bmp‘);