基于K-Means的时间季节反演识别方法

Time and Season Recognition Method via K-Means

摘要: 不同的时间季节有不同的特征，根据季节的特征，我们在计算机上利用各种方法可以清楚的识别不同的季节。本文利用HSV图像色彩模型，主要对各个季节的图片的特征进行分析和研究，进行颜色间的对比，比较其色彩值的平均值与方差，运用光学图像处理技术，采用近邻分类的方法，对比各季节图像的特征差异，对所选图像进行分类与识别，进而达到自动识别季节的目的。实验结果证实了此研究方法的可行性，在季节识别上能够达到自动识别的效果。

Abstract: Different time seasons have different characteristics. According to the characteristics of the season, we use various methods on the computer to clearly identify different seasons. Based on HSV color model, the characteristics of the images of each season are analyzed and studied, and in the colors contrast, the mean value and variance of them are compared. Through using the optical image processing technology, adopting the nearest neighbor classification method, comparing the characteristics of different season images, and then classifying and recognizing the selected images, thus the season can be identified automatically. The experimental results confirm the feasibility of this method, and can achieve high performance in season recognition.

1. 引言

随着互联网技术与数字化的飞速发展，以及电子数码产品的普及，人们能够获取的数字图像数据已经越来越多。图像作为一种表现直观、内容丰富的多媒体信息，在各行各业中也得到越来越广泛的应用，如数字多媒体图书馆、医学图像应用管理、卫星遥感图像和地理信息系统、身份认证识别系统、电子商务、商标版权的监管等。随之带来的是图像处理技术的不断提升，目前，图形分类主要包括图像采集、图像预处理、图像特征值的选择和提取、图像分类模型建立四个步骤 [1] 。图像处理方法的重要性源于两个主要应用领域：1) 改善图示信息以便人们解释；2) 为存储、传输和表示而对图像数据进行处理，以便于机器自动理解。本文基于光学图像处理技术，针对天气现象光学特征来反演时间季节，对不同时间季节图片的天气特征进行了提取并研究，给出合理分类，为天气现象的自动分类和观测提供光学技术、方法和手段。

图像特征提取是自动识别图像的基础。获得高效的图像不仅可以降低计算复杂度，还可以准确地表述图像的原始信息 [2] 。目前，常用的图像底层特征包括颜色、纹理和形状等。在基于内容的图像处理技术中特征提取有着重要的意义：一方面，图像的特征提取与表示是图像识别过程中一个很重要的步骤，所提取的特征直接影响后续的图像相似度匹配过程，识别精度等；另一方面，由于图像所包含的内容和图像类型各异，有些图像颜色特征较为突出，有些图像纹理特征占主导，有些图像则可能用形状来描述更加合适，而有些图像单纯用某一种特征都不足以表示，因此我们需要研究新颖全面的方法来提取图像特征并表示图像。此外，新颖合适的图像特征提取方法对别的领域如人工智能、模式识别等也会有一定的促进作用 [3] 。因此，如何有效的提取低层视觉特征成为基于内容的图像识别中的一个关键步骤，也成为图像识别领域研究的热点内容。

在前人的研究基础上加上教员的指导下，本文基于HSV的颜色空间模型，提取了不同季节图像中的H (色调)、S (饱和度)、V (亮度)的数据，并对这三类数据进行了求平均、方差，最后再利用K-means聚类算法等方法对之前提到的数据进行了分类聚类研究，最终达到时间季节自动识别效果。本文着重于使用matlab对上述提出的算法进行时间分析并设计了图像识别的有效程序。

2. 图像分类

2.1. 典型的分类方法

1) 神经网络分类 [4] 的方法

人工神经网络是人们对自身大脑神经网络认识理解的基础上人工构造的可以实现某种功能的网络系统 [5] 。人工神经网络是对生物神经元的模拟，生物的每一个神经元相当于一个基本单元，且每个单元关联一个权值。神经网络较复杂，需要较长的时间来训练，因而这种方法比较适合训练时间长的应用。神经网络的参数大多数靠总结历史数据所得的经验所得。一般可分为以下几类：

人工神经网络从结构方面讲可以分为前馈网络(如BP网络)和反馈网络(如Hopfield)；从状态方面来讲又可分为离散性网络和连续性网络；从学习的方法方面又可分为监督学习网络(如BP、RBF网络)和无监督学习网络 [6] (如自组织网络)。

2) 贝叶斯分类方法

这个分类方法的主要思想：先计算每个类别在训练集的分布，将这种分布看作为不同类别的概率分布，最后在测试过程中运用统计学原理和概率统计原理中的贝叶斯定理来估计某个特定样本属于某一类的概率0.6。

目前贝叶斯方法主要包括贝叶斯信念网络和朴素贝叶斯方法两类，其中前者在当前社会应用最多，但是这种方法的训练较为复杂，用来评估的函数比较难选，这是现在需要研究解决的问题。

2.2. 图像聚类的研究现状及发展

聚类分析作为数据挖掘领域的一个重要分支，已被广泛研究多年。当人们利用数据挖掘工具对数据关系和模型进行识别的时候，通常首要步骤就是聚类，目的是将初始时大量无规律的数据按照一定的规则重新组合成若干类，使同一类内各对象之间尽可能最相似、不同类之间尽可能不相似，以揭示数据分布的规律性，发现数据属性之间重要的相互关系以及数据全局的分布模式 [7] 。聚类分析在客户分类、基因识别、文本分类、图像处理中有着广泛的应用 [8] 。

聚类分析是个具有很强挑战性的领域，目前的研究主要有以下几个方向：

1) 发现任意形状的聚类的能力

许多聚类分析算法采用的是基于欧氏距离或曼哈顿距离的相似度度量方法来决定簇，这类算法通常趋于发现的是一些尺寸和密度相近的、球状的类 [9] 。但是，现实数据库中的聚类可以是任意的形状，甚至是具有分层树的形状，故要求算法具有发现任意形状的聚类的能力。

2) 输入参数对领域知识的弱依赖性

一些聚类算法在聚类分析开始前要求用户输入一定的参数，例如期望得到的聚类数目、置信度、支持度等。最终聚类的结果通常对这些参数较为敏感 [10] 。另一方面，对于高维对象数据集来说，这些参数的值通常也很难确定。这样不仅加重了用户使用该聚类分析工具的负担，也难以保障聚类质量的好坏。因此就需要一个较好的方案来解决这个问题。

3) 初始值的选择以及输入顺序对聚类结果的影响

有些聚类算法对初始值的选择和数据的输入顺序很敏感。即对同一个数据集，将其以不同的次序输入到分析算法中，可能得到差别很大的聚类。开发对输入不敏感的算法是目前研究的一个重点。

4) 高维数据的处理能力

数据库或数据仓库都包含若干字段或者是属性，一些聚类分析算法对处理维数较少的数据集时效果不错，例如二维三维数据 [11] 。但是对于高维数据空间，比如图像数据、视频数据等就没那么乐观了。所以对高维数据的聚类分析是非常有挑战性的，特别是考虑到数据在高维空间中，其数据分布通常比较稀疏，而且形状也可能不规则，因此这方面的研究是当前聚类分析中一个很重要的分支。

目前，主要存在着如下几种聚类方法:划分方法、层次方法、基于密度的方法、基于网格的方法以及基于模型的方法等。图像聚类的目的是在图像识别前为图像数据库建立有效的识别类型，以加快图像识别速度，提高图像识别的精确性。图像聚类的关键问题之一是如何选取合适高效的聚类算法。目前应用于图像数据的聚类分析算法主要有K-means算法、模糊C均值方法、遗传算法、近邻传播算法(Affinity Propagation, AP)以及这些方法的改进等 [12] 。

3. HSV空间模型

HSV模型在1978年由埃尔维·雷·史密斯创立(图1)。

HSV色彩模型从CIE三维颜色空间演变而来，它采用的是用户直观的色彩描述方法，它跟孟塞尔显色系统的HVC球型色立体较接近。(如图HSV色彩六棱锥)只不过HSV色彩模型是一个倒立的六菱锥，只相当于孟塞尔球型色立体的一半(南半球)，所以不含黑色的纯净颜色都处于六菱锥顶面的一个色平面上 [13] 。在HSV六菱锥色彩模型中，色相(H)处于平行于六菱锥顶面的色平面上，它们围绕中心轴V旋转和变化，红、黄、绿、青、蓝、品红六个标准色分别相隔60度 [14] 。色彩明度(B)沿六菱锥中心轴V从上至下变化，中心轴顶端呈白色(V = 1)，底端呈黑色(V = 0)，它们表示无彩色系的灰度颜色。色彩饱和度(S)沿水平方向变化，越接近六菱锥中心轴的色彩，其饱和度越低，六边形正中心的色彩饱和度为零(S = 0)，与最高明度的V = 1相重合，最高饱和度的颜色则处于六边形外框的边缘线上(S = 1) [15] 。

1) 色相、饱和度与六棱锥色平面(H和S)色平面(H、S)的基础是CIE色度图的x、y色平面。

2) 明度与六棱锥中轴色(v)色明度(V)的基础是CIE三维颜色空间的亮度因素Y。

4. 最近邻分类

假定有c个类别 ${\omega }_1,{\omega }_2,\cdots ,{\omega }_c$ ， ${\omega }_c$ 的模式识别问题，每类有标明类别的样本有 $N_i$ 个，那么可以轨道 ${\omega }_i$ 类的判别函数为 $g_i\left(x\right)=\min \Vert x=x_i^k\Vert$ ，其中 $k=1,2,\cdots ,N_i$ 。表示 ${\omega }_i$ 类，k表示 ${\omega }_i$ 类的 $N_i$ 个样本中的第k个。决策规则为：若 $g_j\left(x\right)=m_{k}in{g}_i\left(x\right),i=1,2,\cdot \cdot \cdot ,c$ ，则决策 $x\in {\omega }_j$ [16] 。

最近邻分类的另一个直观解释是:令 $D^n=\left\{x_1,x_2,\cdot \cdot \cdot ,x_n\right\}$ ，其中每一个样本 $x_i$ 所属的类别均己标记。对于参数样本点x，在集合 $D^n$ 中距离它最近的点记为 $x^{\prime }$ 那么最近邻分类规则就是把点x分为 $x^{\prime }$ 所属的类别 [17] 。

Figure 1. HSV model

图1. HSV模型

5. K-Means聚类算法

K-means算法是硬聚类算法，是典型的基于原型的目标函数聚类方法的代表，它是数据点到原型的某种距离作为优化的目标函数，利用函数求极值的方法得到迭代运算的调整规则。K-means算法以欧式距离作为相似度，它是求对应某一初始聚类中心向量V最优分类，使得评价指标J最小。算法采用误差平方和准则函数作为聚类准则函数 [18] 。

聚类分析的目的在于把集中的数据划分为一系列有意义的子集(或称类)，使得每个子集中的数据尽量“相似”或“接近”，而子集与子集间的数据尽可能有较大差异 [19] 。聚类分析通常遇到的困难是：

1) 聚类个数K并不能预先确定。我们需要找到一个有效性指标，来确定最佳聚类个数。

2) 类中心点不能预先知道，需要用某种方法初设“种子”。

K-means聚类算法的主要思想可用下式描述：

$\text{Minimize}J\left(X,U,V\right)={\displaystyle \underset{i=1}{\overset{k}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{u}_{ij}{\Vert x_j-v_i\Vert }^2}}$ (1)

其中：n是给定数据集中的数据个数，k是聚类个数。

$X=\left\{x_1,x_2,\cdots ,x_n\right\}\subset R^S$ 是给定的数据集， $V=\left\{v_1,v_2,\cdots ,v_k\right\}\subset R^S$ 是类中心点，用 $X_1,X_2,\cdots ,X_k$ 表示k个类， $n_i$ 表示 $X_i$ 中数据个数， $U={\left(u_{ij}\right)}_{k\times n}$ 是聚类矩阵，由和 $X_i$ 的成员关系组成， $d\left(x,y\right)=\Vert x-y\Vert ,x,y\in R^S$ 是一个距离函数(例如，欧几里得距离)。为了极小化 $J\left(X,U,V\right)$ 类中心点 $v_i\left(i=1,2,\dots ,k\right)$ 和成员关系矩阵 $U$ 需要用以下的迭代公式逐步计算：

$u_{ij}=\{\begin{array}{l}1;\Vert x_j-v_i\Vert \le \Vert x_j-v_h\Vert ,h=1,2,\dots ,k,h\ne i\\ 0;否则\end{array}$ (2)

而

$v_i=\frac{{\displaystyle \underset{j=1}{\overset{n}{\sum }}{u}_{ij}{x}_j}}{{\displaystyle \underset{j=1}{\overset{n}{\sum }}{u}_{ij}}}=\frac{{\displaystyle \underset{x_j\in X_i}{\sum }{x}_j}}{n_i}$ (3)

通过某些方法(如随机抽取)初始化类中心点然后通过方程式(2)计算成员关系矩阵

$u_{ij}\left(i=1,2,\dots ,k,j=1,2,\dots ,n\right)$ 。K-means算法就是基于(2)、(3)的迭代过程： $V_{t-1}\to U_t\to V_t$ ，直到 $\Vert v_t-v_{t-1}\Vert \le \epsilon$ 。其中 $\epsilon$ 是给定终止条件。最终的聚类结果通过成员关系矩阵确定，即如果 $u_{ij}=1$ ，则说明 $x_{ij}\left(j=1,2,\dots ,n\right)$ 属于类 $X_i\left(1\le i\le k\right)$ [20] 。

将此算法归纳如下：

算法A

1) 输入聚类数口 $k$ ，确定距离函数，给定迭代终止条件 $\epsilon$ ；

2) 初始化中心点谓 $v_i^0\left(i=1,2,\cdots ,k\right)$ ；

3) 利用方程式(2)计算 $u_{ij}\left(i=1,2,\cdots ,k,j=1,2,\cdots ,n\right)$ ；

4) 利用方程式(3)计算新的中心点 $v_i^1\left(i=1,2,\cdots ,k\right)$ ；

5) 如果 $\underset{1\le i\le k}{\max }\Vert v_i^0-v_i^1\Vert \le \epsilon$ ，那么迭代终止，转向6)，否则令： $v_i^0=v_i^1\left(i=1,2,\cdots ,k\right)$ 转向3)；

6) 出分类结果：类中心点 $v_i^1\left(i=1,2,\cdots ,k\right)$ 和成员关系矩阵 $U$ ；

7) 终止。

确定最佳聚类数目的算法B：

1) 选取 $k_{\min }$ 和 $k_{\max }$ ；

2) For $k=k_{\min }$ to $k_{\max }$ ;

① 初始化类中心点；

② 利用算法A，更新计算 $U^k$ 和 $V^k$ ；

③ 检查终止条件，如不满足，则转向②；

④ 利用方程式(4)计算 $V_{km}\left(k\right)$ ，转向2)；

3) 选择 $k_{opt}$ 使聚类有效函数 $V_{km}\left(k\right)$ 达到最优(最小)；

4) 输出聚类结果：类中心点砂 $V_{k_{opt}}$ ，成员关系矩阵 $U_{k_{opt}}$ ，最佳聚类数目 $k_{opt}$ ；

5) 终止。

5.1. 利用HSV空间模型进行特征提取

本节主要利用了上文中介绍的H (色调)、S (饱和度)、V (亮度)的空间模型，在matlab中实现了特征提取。我分别选取了50张春天、41张夏天、50张秋天和48张冬天天气图作为特征提取的样本，

通过matlab软件的处理得到了各类天气图像的色调平均值、方差(主要为H通道数据)，以及每张天气图像的各个像素点的方差(去除异常值后)和各类天气图像的方差的均值。在对时间季节图像的HSV特征数据提取后，我对这三类数据又分别做了求平均和标准差的处理，最后，时间季节H、S、V三个通道的特征数据体情况如表1。

由表1可知，在时间季节方面的识别-色调是最主要的依据，通过HSV，我发现在时间季节方面对于秋天、冬天与(春天和夏天)的识别有较好的结果，但是对于春天和夏天的识别明显有较大的误差。

5.2. K-Means聚类法的实现

分类算法是给出一个数据，然后判断这个数据属于已分好的类中哪一类。在4.1中，我所做的工作就是基于HSV空间模型给时间季节的特征数据提取，并提出一个分类的依据。

聚类算法是给一大堆原始数据，然后通过算法将其中具有相似特征的数据聚为一类。这个过程在我理解看来，也可以是一种特征数据的整合、自动聚类实现特征数据的提取。

本节采用了2.2中介绍的K-means的聚类算法，在Matlab中实现对数据的聚类算法。

5.3. K-NN最邻近法的实现

在实现了特征提取，现在的问题就是如何对处理后的特征数据进行分类，本节本节利用了第二章中介绍的K-邻近分类算法.

我选取了50张春天、50张夏天、50张秋天和50张冬天图像作为待识别图像样本库，经过对每一张图像的识别分类，最终各项识别准确度如表3。

6. 总结

不同的时间季节有不同的特征，根据季节的特征，我们在计算机上利用各种方法可以清楚的识别不同的季节。本文利用HSV图像色彩模型，主要对各个季节的图片的特征进行分析和研究，进行颜色间的对比，比较其色彩值的平均值与方差，运用光学图像处理技术，采用近邻分类的方法，对比各季节图像

Table 1. Time-season picture HSV feature data

表1. 时间季节图像HSV特征数据

注：H_avg表示色调均值；H_var表示色调标准差；S_avg表示饱和度均值；S_var表示饱和度标准差；V_avg表示亮度均值；V_var表示亮度标准差。

Table 2. The seasonal tonal feature data of clustering algorithm

表2. 聚类算法的季节色调特征数据情况

Table 3. Image recognition accuracy

表3. 图像识别准确度

的特征差异，对所选图像进行分类与识别，进而达到自动识别季节的目的。实验结果证实了此研究方法的可行性，在季节识别上能够达到较高自动识别图片的目标。

致谢

论文得到国家自然科学基金(No.61471412, 61771020)的支持。