【MATLAB图像处理实用案例详解（7）】—— 基于K-means聚类算法的图像区域分割

一、背景意义

图像分割就是把图像分成各具特性的区域并提取感兴趣目标的技术和过程， 是目标检 测和模式识别的基础。现有的图像分割方法主要有：基于阈值的分割方法、基于区域的分割方法、基于边缘的分割方法、基于特定理论的分割方法等。 聚类分析是一种无监督的学习方法，能够从研究对象的特征数据中发现关联规则， 因而是一种强大有力的信心处理方法。聚类法进行图像分割就是将图像空间中的像素点用对应的特征向量表示，根据它们在特征空间的特征相似性，对特征空间进行分割，然后将其映射回原图像空间， 得到分割结果。其中， K 均值和模糊C 均值聚类( FCM ) 算法是最常用的聚类算法。

二、理论基础 2.1 K-means聚类算法原理

K-means 算法首先从数据样本中选取K 个点作为初始聚类中心；其次计算各个样本到聚类的距离，把样本归到离它最近的那个聚类中心所在的类；然后计算新形成的每个聚类的数据对象的平均值来得到新的聚类中心；最后重复以上步骤，直到相邻两次的聚类中心没有任何变化， 说明样本调整结束，聚类准则函数达到最优。 流程图如下：

2.2 K-means聚类算法的要点

1） 选定某种距离作为数据样本间的相似性度量 在计算数据样本之间的距离时，可以根据实际需要选择某种距离（欧式距离、曼哈顿距离、绝对值距离、切比雪夫距离等）作为样本的相似性度量，其中最常用的是欧式距离： 距离越小，样本xi，和xj越相似， 差异度越小； 距离越大，样本xi，和xj越不相似， 差异度越大。

2） 聚类中心迭代终止判断条件 K-means 算法在每次迭代中都要考察每个样本的分类是否正确， 若不正确 则需要调整。在全部样本调整完毕后，再修改聚类中心， 进入下一次迭代， 直到满足某个终止条件： A. 不存在能重新分配给不同聚类的对象； B. 聚类中心不再发生变化； C. 误差平方和准则函数局部最小。

3）误差平方和准则函数评价聚类性能 假设给定数据集X 包含k 个聚类子集X1,X2, … , Xn，各个聚类子集中的样本数量分别为n1,n2, … ,nk，各个聚类子集的聚类中心分别为μ1,μ1, …，μk，则误差平方和准则函数公式为：

2.3 K-means聚类算法的缺点

K-means 聚类算法是解决聚类问题的一种经典算法，简单、快速，该算法对于处理大 数据集是相对可伸缩和高效率的，结果类是密集的，而类与类之间区别明显时，其效果较好。但是K-mean 聚类算法由于其算法的局限性也存在以下缺点。

1. K-means 需要给定初始聚类中心来确定一个初始划分，另外对于不同的初始聚类中心，可能会导致不同的结果。通过对样本进行数理统计来获取优化的初始聚类中心，另外通过引入加权欧氏距离来度量样本之间的相关性，从而实现彩色图像的快速、准确分割。
2. K-means 必须事先给定聚类数目，然而聚类个数K值往往是难以估计的。提出了一种自动确定聚类数目K 和初始聚类中心的方法。另外也可以通过类的自动合并和分裂，来得到合理的聚类数目K, 如ISODATA 算法在迭代过程中可将一个类一分为二，亦可将两个类合二为一，即“ 自组织“。
3. K-means 对于＂躁声”和孤立点很敏感，少量的该类数据能够对平均值产生极大的影响。改进的K-center算法不采用簇中的平均值作为参照点，可以选用类中位置最中心的对象，即中心点作为参照点，从而解决K-means 算法对于孤立点敏感的问题。
4. K-means 在类的平均值被定义的情况下才能使用，这对于处理符号属性的数据不适用，如姓名、性别、学校等。K-modes 算法实现了对离散数据的快速聚类，可处理具有分类属性等类型的数据。它采用差异度D 来代替K-means 算法中的距离，差异度越小， 则表示距离越小。一个样本和一个聚类中心的差异度就是它们各个属性不相同的个数，属性相同为0, 不同为1，并计算1的总和，因此D越大两者之间的不相关程度越强。

2.4 基于K-means的图像分割

K-means 聚类算法简捷，具有很强的搜索力，适合处理数据量大的情况，在数据挖掘 和图像处理领域中得到了广泛的应用。采用K-means 进行图像分割，将图像的每个像素点的灰度或者RGB 作为样本（特征向量） ，因此整个图像构成了一个样本集合（特征向量空间），从而把图像分割任务转换为对数据集合的聚类任务。然后，在此特征空间中运用K-means 聚类算法进行图像区域分割， 最后抽取图像区域的特征。

例如，对512x256x3 的彩色图像进行分割，则将每个像素点的RGB 值作为一个样本， 最后将图像数组转换成(512 x 256) x 3=131072 x 3 样本集合矩阵，矩阵中每行表示一个样本（像素点的RGB ) ，总共包含131 072 个样本，矩阵中的每列表示一个变量。从图像中选择几个典型的像素点，将其RGB 作为初始聚类中心，根据图像上每个像素点RGB 值之间的相似性，调用K-means 进行聚类分割。

采用K-means 聚类分析处理复杂图像时，如果单纯使用像素点的RGB 值作为特征向量，然后构成特征向量空间，则算法鲁棒性往往比较脆弱。一般情况下，需要将图像转换到合适的彩色空间（如Lab 或HSL 等），然后抽取像素点的颜色、纹理和位置等特征，形成特征向量。

三、程序实现 3.1 样本间的距离

距离是对样本间相似性的度量，最常用的是欧式距离。sampledist()函数支持欧式距离和城市距离。函数代码如下：

function D=sampledist(X,C,method,varargin)
%计算样本空间和聚类中心C的距离
% X:样本空间,n*p数组
% C:聚类中心,k*p数组
% method:距离公式
% varargin:其他参数
% D:每个点到聚类中心的欧式距离
[n,p]=size(X);
K=size(C,1);
D=zeros(n,K);%初始化距离矩阵
switch lower(method(1))
    %循环计算到聚类中心的距离
    case 'e'%euclidean
        for i=1:K
            D(:,i)=(X(:,1)-C(i,1)).^2;
            for j=2:p
                D(:,i)=D(:,i)+(X(:,j) - C(i,j)).^2;
            end
        end
    case 'c'%cityblock
        for i=1:K
            D(:,i)=abs(X(:,1) - C(i,1));
            for j=2:p
                D(:,i)=D(:,i) + abs(X(:,j) - C(i,j));
            end
        end
end

3.2 图像聚类分割

图像聚类分割首先提取像素点的特征向量exactvector()，然后搜索初始聚类中心searchintial()，最后执行K-means核心算法：

function [F,C]=imkmeans(I,C)
% I:图像矩阵,支持彩色或者灰度图
% C:聚类中心，可以是整数或者数组，整数表示随机选择K个聚类中心
% F:样本聚类编号
if nargin~=2
    error('IMKMEANS:InputParamterNotRight','只能有两个输入参数！');
end
if isempty(C)
    K=2;
    C=[];
elseif isscalar(C)
    K=C;
    C=[];
else
    K=size(C,1);
end
%% I.提取像素点特征向量
X=exactvecotr(I);
%% II.搜索初始聚类中心
if isempty(C)
    C=searchintial(X,'sample',K);
end
%% III.循环搜索聚类中心
Cprev=rand(size(C));
while true
    %计算样本到中心的距离
    D=sampledist(X,C,'euclidean');
    %找出最近的聚类中心
    [~,locs]=min(D,[],2);
    %使用样本均值更新中心
    for i=1:K
        C(i,:)=mean(X(locs==i,:),1);
    end
    %判断聚类算法是否收敛
    if norm(C(:)-Cprev(:))