K均值聚类在基于OpenCV的图像分割中的应用

K均值聚类在基于OpenCV的图像分割中的应用

摘要：基于人类视觉将图像分割成若干个有意义的区域是目标检测和模式识别的基础。图像分割属于图像处理中一种重要的图像分析技术。图像分割的基本方法是对灰度图像分割，处理图像的亮度分量，简单快速。本论文介绍了传统的图像分割与K-均值聚类算法分割，然后利用OpenCV函数将其实现，并介绍了OpenCV 中图像分割相关的基本函数。

关键词：K 均值聚类，图像分割，OpenCV

一、前言

根据抽象程度和处理方法的不同，图像技术可以分为三个层次：图像处理、图像分析和图像理解，这三个层次的有机结合也可以称为图像工程。图像处理是较低层的操作，主要在图像像素级上进行操作。有代表性的图像处理技术包括图像降噪、图像编码和图像分割。图像分割是一种关键的图像处理技术。作为后续图像分析和图像理解的基础，图像分割技术一直是图像理论发展的瓶颈之一。图像分割在实际中的应用非常广泛，对图像目标的提取、测量都离不开图像分割，是图象处理、模式识别和人工智能等多个领域中一个十分重要且又十分困难的问题。分割的准确性直接影响后续任务的有效性，因此具有十分重要的意义。

图像分割又是一种特殊的图像处理技术。像素级的图像处理可以分成两类，一类是针对像素值的处理，另一类是把像素分类的处理。图像降噪技术、图像编码技术、数字水印技术等虽然各有其特点和应用领域，但其实质都是针对像素值的操作。不同于这些技术，图像分割，其实质是一个按照像素属性（灰度、纹理、颜色等）进行聚类的过程。

二、图像分割概述

图像分割是一种重要的图像分析技术。在对图像的研究和应用中，人们往往仅对图像中的某些部分感兴趣。这些部分常称为目标或前景（其他部分称为背景）。它们一般对应图像中特定的、具有独特性质的区域。为了辨识和分析图像中的目标，需要将它们从图像中分离提取出来，在此基础上才有可能进一步对目标进行测量，对图像进行利用。图像分割就是把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。现有的图像分割方法主要分以下几类：基于阈值的分割方法、基于区域的分割方法、基于边缘的分割方法以及基于特定理论的分割方法等。

1、基于阈值的分割方法

包括全局阈值、自适应阈值、最佳阈值等等。阈值分割算法的关键是确定阈

值，如果能确定一个合适的阈值就可准确地将图像分割开来。阈值确定后，将阈值与像素点的灰度值比较和像素分割可对各像素并行地进行，分割的结果直接给出图像区域。全局阈值是指整幅图像使用同一个阈值做分割处理，适用于背景和前景有明显对比的图像。它是根据整幅图像确定的：T=T(f)。但是这种方法只考虑像素本身的灰度值，一般不考虑空间特征，因而对噪声很敏感。常用的全局阈值选取方法有利用图像灰度直方图的峰谷法、最小误差法、最大类间方差法、最大熵自动阈值法以及其它一些方法。

2、基于边缘的分割方法

检测灰度级或者结构具有突变的地方，表明一个区域的终结，也是另一个区域开始的地方。这种不连续性称为边缘。不同的图像灰度不同，边界处一般有明显的边缘，利用此特征可以分割图像。图像中边缘处像素的灰度值不连续，这种不连续性可通过求导数来检测到。对于阶跃状边缘，其位置对应一阶导数的极值点，对应二阶导数的过零点(零交叉点)。因此常用微分算子进行边缘检测。常用的一阶微分算子有Roberts算子、Prewitt算子和Sobel算子，二阶微分算子有Laplace算子和Kirsh算子等。在实际中各种微分算子常用小区域模板来表示，微分运算是利用模板和图像卷积来实现。这些算子对噪声敏感，只适合于噪声较小不太复杂的图像。

3、基于聚类分析的图像分割方法

特征空间聚类法进行图像分割是将图像空间中的像素用对应的特征空间点表示，根据它们在特征空间的聚集对特征空间进行分割，然后将它们映射回原图像空间，得到分割结果。其中，K均值、模糊C均值聚类(FCM)算法是最常用的聚类算法。K均值算法先选K个初始类均值，然后将每个像素归入均值离它最近的类并计算新的类均值。迭代执行前面的步骤直到新旧类均值之差小于某一阈值。模糊C均值算法是在模糊数学基础上对K均值算法的推广，是通过最优化一个模糊目标函数实现聚类，它不像K均值聚类那样认为每个点只能属于某一类，而是赋予每个点一个对各类的隶属度，用隶属度更好地描述边缘像素亦此亦彼的特点，适合处理事物内在的不确定性。利用模糊C均值(FCM)非监督模糊聚类标定的特点进行图像分割，可以减少人为的干预，且较适合图像中存在不确定性和模糊性的特点。

三、K均值聚类分割算法

3.1 聚类

将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。聚类分析又称群分析，它是研究（样品或指标）分类问题的一种统计分析方法。聚类分析计算方法主要有如下几种：划分方法，

层次方法，基于密度的方法，基于网格的方法，基于模型的方法。

K-均值聚类算法是著名的划分聚类分割方法。划分方法的基本思想是：给定一个有N 个元组或者纪录的数据集，分裂法将构造K 个分组，每一个分组就代表一个聚类，K

3.2 K-均值聚类算法的工作原理：

K-means 算法的工作原理：算法首先随机从数据集中选取 K 个点作为初始聚类中心，然后计算各个样本到聚类中心的距离，把样本归到离它最近的那个聚类中心所在的类。计算新形成的每一个聚类的数据对象的平均值来得到新的聚类中心，如果相邻两次的聚类中心没有任何变化，说明样本调整结束，聚类准则函数 已经收敛。本算法的一个特点是在每次迭代中都要考察每个样本的分类是否正确。若不正确，就要调整，在全部样本调整完后，再修改聚类中心，进入下一次迭代。这个过程将不断重复直到满足某个终止条件，终止条件可以是以下任何一个：

（1）没有对象被重新分配给不同的聚类。

（2）聚类中心再发生变化。

（3）误差平方和局部最小。

3.3 K-means 聚类算法的一般步骤：

处理流程：

（1）从 n 个数据对象任意选择 k 个对象作为初始聚类中心；

（2）循环（3）到（4）直到每个聚类不再发生变化为止；

（3）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；

（4）重新计算每个（有变化）聚类的均值（中心对象），直到聚类中心不再变化。这种划分使得下式最小

2

1i j k i j j x E x m ω=∈=-∑∑

3.4 K-均值聚类法的缺点： （1）在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。

（2）在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。

（3） K-means算法需要不断地进行样本分类调整 不断地计算调整后的新的聚类中心 因此当数据量非常大时 算法的时间开销是非常大的。

（4）K-means算法对一些离散点和初始k值敏感，不同的距离初始值对同样的数据样本可能得到不同的结果。

四、基于灰度空间的彩色图像像素聚类

OpenCV中K均值函数为：

void cvKMeans2(const CvArr* samples,int cluster_count,

CvArr* labels,CvTermCriteria tercrit);

Samples:输入样本的浮点矩阵，每个样本一行。

cluster_count:所给定的聚类数目

labels:输出整数向量：每个样本对应的类别标识

termcrit:指定聚类的最大迭代次数和／或精度（两次迭代引起的聚类中心的移动距离）

其执行 k-means 算法搜索 cluster_count 个类别的中心并对样本进行分类，输出 labels(i) 为样本i的类别标识。

其中CvTermCriteria为OpenCV中的迭代算法的终止准则，其结构如下：#define CV_TERMCRIT_ITER 1

#define CV_TERMCRIT_NUMBER CV_TERMCRIT_ITER

#define CV_TERMCRIT_EPS 2

typedef struct CvTermCriteria

{

int type;

int max_iter;

double epsilon;

} CvTermCriteria;

max_iter：最大迭代次数。

epsilon：结果的精确性。

利用OpenCV对彩色图像进行颜色聚类的基本步骤及核心代码如下：

1、读取彩色图像。

2、利用k均值聚类对像素的灰度值进行划分，提取特征点。

(1)获取彩色图像RGB三通道的值并将像素点三通道的值按顺序排入样本矩阵。

for (i=0;iwidth;i++)

{

for (j=0;jheight;j++)

{

CvScalar s;

//获取图像各个像素点的三通道值（RGB）

s.val[0]=(float)cvGet2D(m_imagesrc,j,i).val[0];

s.val[1]=(float)cvGet2D(m_imagesrc,j,i).val[1];

s.val[2]=(float)cvGet2D(m_imagesrc,j,i).val[2];

cvSet2D(samples,k++,0,s); }

}

这里用到cvGet2D函数获取三通道值并利用cvSet2D函数将三通道的值排入样本。函数如下：

CvScalar cvGet2D( const CvArr* arr, int idx0, int idx1 );

Arr:输入数组。

idx0:元素下标第一个以0为基准的成员。

idx1:元素下标第二个以0为基准的成员。

void cvSet2D( CvArr* arr, int idx0, int idx1, CvScalar value );

arr：输入数组。

idx0：元素下标的第一个成员，以0为基点。

idx1：元素下标的第二个成员，以0为基点。

（2）对样本矩阵的值进行迭代聚类，迭代100次，终止误差1.0。

cvKMeans2(samples,nCuster,clusters,cvTermCriteria(CV_TERMCRIT_ITE R,100,1.0));

3、绘制聚类后的图像。

将聚类后的不同类别取不同的像素值，并对聚类后的图像的每个像素点赋值。

float step=255/(nCuster-1);

for (i=0;iwidth;i++)

{

for (j=0;jheight;j++)

{

val=(int)clusters->data.i[k++];

CvScalar s;

s.val[0]=255-val*step;，

cvSet2D(bin,j,i,s);

}

}

4、绘制灰度直方图。

（1）设置直方图尺寸和灰度范围,这里将显示范围设置为-5到260，防止灰度值为0 和255的直方图不显示。

int hist_size = 256;

int hist_height = 256;

float range[] = {-5,260};

float* ranges[]={range};

(2)创建直方图，统计图像在[0 255]像素的均匀分布

CvHistogram* gray_hist

= cvCreateHist(1,&hist_size,CV_HIST_ARRAY,ranges,1);

cvCalcHist(&bin,gray_hist,0,0);

cvNormalizeHist(gray_hist,1.0);

int scale= 2;

//横坐标为灰度级，纵坐标为像素个数*scale

IplImage* hist_image =

cvCreateImage(cvSize(hist_size*scale,hist_height),8,3);

cvZero(hist_image);

float max_value = 0;

cvGetMinMaxHistValue(gray_hist, 0,&max_value,0,0);

其中CvHistogram为多维直方图类型，其定义如下：

typedef struct CvHistogram

{

int type;

CvArr* bins;

float thresh[CV_MAX_DIM][2];

float** thresh2;

CvMatND mat;

}CvHistogram;

bins : 用于存放直方图每个灰度级数目的数组指针，数组在cvCreateHist 的时候创建其维数由cvCreateHist确定。

而cvCreateHist 创建一个指定尺寸的直方图，并且返回创建的直方图的指针。其定义如下：

CvHistogram* cvCreateHist( int dims, int* sizes, int type,

float** ranges=NULL, int uniform=1 );

dims：直方图维数的数目。

sizes：直方图维数尺寸的数组。

type：直方图的表示格式: CV_HIST_ARRAY 意味着直方图数据表示为多维密

集数组CvMatND; CV_HIST_TREE 意味着直方图数据表示为多维稀疏数组CvSparseMat.

Ranges：图中方块范围的数组. 它的内容取决于参数 uniform 的值。这个

范围的用处是确定何时计算直方图或决定反向映射（backprojected ），每个方

块对应于输入图像的哪个/哪组值。

Uniform：归一化标识。

而CalcHist用来计算图像image的直方图，其定义如下：

void cvCalcHist( IplImage** image, CvHistogram* hist,

int accumulate=0, const CvArr* mask=NULL );

image：输入图像 (也可以使用 CvMat** )。

Hist：直方图指针。

Accumulate：累计标识。如果设置，则直方图在开始时不被清零。这个特征

保证可以为多个图像计算一个单独的直方图，或者在线更新直方图。

Mask：操作mask,确定输入图像的哪个象素被计数。

（3）分别将每个直方块的值绘制到图中

for( i=0;i

{

float bin_val = cvQueryHistValue_1D(gray_hist,i);

int intensity = cvRound(bin_val*hist_height/max_value);

cvRectangle(hist_image,cvPoint(i*scale,hist_height-1), cvPoint((i+1)*scale-1,hist_height-intensity), CV_RGB(255,255,255));

}

cvQueryHistValue_1D用来查询直方块的值，其定义如下：

#define cvQueryHistValue_1D( hist, idx0) \

cvGetReal2D( (hist)->bins, (idx0) )

hist：直方图。

idx0, idx1, idx2, idx3：直方块的下标索引。

idx：下标数组。

函数 cvRound,用一种舍入方法将输入浮点数转换成整数，返回和参数最接

近的整数值。

cvRectangle函数用以绘制简单、指定粗细或者带填充的矩形，其定义如下：void cvRectangle( CvArr* img, CvPoint pt1, CvPoint pt2, CvScalar color, int thickness=1, int line_type=8, int shift=0 );

img：目标图像。

pt1：矩形的一个顶点。

pt2：矩形对角线上的另一个顶点。

Color：线条颜色 (RGB) 或亮度（灰度图像）(grayscale image）。

Thickness：组成矩形的线条的粗细程度。取负值时（如 CV_FILLED）函数绘制填充了色彩的矩形。

line_type：线条的类型。

Shift：坐标点的小数点位数。

5、实现结果如图5-1、图5-2和图5-3：

图4-1 输入聚类类别数

图4-2 分为3类聚类后的图像和直方图

图4-3 分为5类聚类后的图像和直方图

参考文献：

[1]林开颜,吴军辉,徐立鸿. 彩色图像分割方法综述[J ]. 中国图象图形学报, 2005, 10 (1) :1- 10.

[2]滕升华. 黑白影像的彩色化研究[D ]. 北京:中国科学院电子学研究所, 2006.

[3]章毓晋．图像分割[M]．北京：科学出版社，200l

[4]蔡煦，朱波，曾广周．一种彩色多级闯值的图像分割方法及在形状特征提取方面的应用[J]．山东大学学报(工学版)，2002，32(4)：333～336

[5] 吴国雄，陈武凡．图像的模糊增强与聚类分割[J]．小型微型计算机系统，1994，15(11)：21～26