实现面向图像理解的视觉单词生成和评价的系统及方法

摘要

本发明涉及一种实现面向图像理解的视觉单词生成和评价的系统及方法，其中包括特征提取器，用以提取视频图像的局部特征和全局特征；特征融合器，用以将提取出的局部特征信息和全局特征信息进行融合得到融合特征信息描述矩阵；特征降维器，用以运用主成分分析方法对所述的融合特征信息描述矩阵进行降维处理；视觉词典生成器，用以对降维后的融合特征信息矩阵进行处理生成视觉词典；性能评估器，用以对所述的视觉词典的优劣性进行评价。采用该种结构的实现面向图像理解的视觉单词生成和评价的系统及方法，实现结合局部特在和全局特征，缓解维护灾难问题，计算复杂度更小，能在任意形状的样本空间上聚类且收敛于全局最优解，具有更广泛应用范围。

说明书

技术领域

本发明涉及计算机视觉技术领域，尤其涉及计算机视觉单词生成技术领域，具体是指一 种实现面向图像理解的视觉单词生成和评价的系统及方法。

背景技术

图像理解的最终目标是给出图像的解释，这些解释可以说明图像所包含内容的意义。图 像理解是一个基于知识的过程，需要知识的支持，在对图像进行理解时要充分利用和图像有 关的知识，才能实现对图像的正确理解，这是视觉分析的高级语义阶段。如何从低层次的视 觉特征描述得到高级语义理解，近来年，词包模型的提出，使得这一问题得到了有效地支持， 而视觉词典构建的好坏直接影响了图像内容的分析理解效果。目前传统的视觉字典的构造方 法是在提取图像特征例如颜色、纹理等的基础上，将提取的图像特征使用聚类方法，例如K 均值(K-means)聚类，来构造视觉词典。常用的特征向量包括局部特征：基于梯度直方图的 SIFT(尺度不变特征变换)、GLOH(梯度位置及方向直方图)等，它们不但具有很强的可区 分性，可以区分不同的图像内容，同时也能容忍一定程度的图像噪声与特征检测带来的误差。

沈项军等在其申请的发明专利“基于D-S证据理论的视觉词典构建方法”[201310014988.2] 中公开了一种基于D-S证据理论的视觉词典构建方法，通过使用D-S证据理论考察不同特 征的视觉相似性并进行特征融合，从而对初始视觉字典进行更进一步的细分，构造出更加有 效的视觉词典，提高图像的分类准确率。

黄祥林等在其申请的发明专利“一种图像检索中视觉单词的提取方法”[201310159183.7] 中公开了一种图像检索中视觉单词的提取方法，通过对图像库中的局部特征集合进行二值化， 得到特征独特性和信息量保持的二值局部特征，在向量空间上提高特征的空间利用率，有利 于提高视觉单词的独特性，并通过快速计算二值特征的汉明距离在之后的检索或分类应用中 提高计算的速度和减小存储的代价。

焦李成等在其申请的发明专利“基于潜在狄利克雷分配的自然图像分类方法” [201310296468.5]中公开了基于潜在狄利克雷分配的自然图像分类方法，主要解决现有全监督 自然图像分类方法分类时间较长以及在缩短了分类时间的前提下分类精度下降的问题。与经 典分类方法相比，该方法在缩短了平均分类时间的同时提高了分类精度，可用于目标识别。

王爽等在其申请的发明专利“潜在狄利克雷模型的多尺度字典自然场景图像分类方法” [201310306975.2]中公开了潜在狄利克雷模型的多尺度字典自然场景图像分类方法，采用了多 尺度特征和潜在语义主题模型，丰富了图像的特征信息，避免了大量的人工标记工作，提高 了分类正确率，可用于目标识别及车辆、机器人导航。

杨卫国等人在其申请的发明专利“一种人脸识别方法、装置及移动终端”[201010559584.8] 中公开了一种人脸识别方法、装置及移动终端，该方法包括：对目标对象进行预处理、局部 滤波器组根据Gabor算法提取人脸局部特征、通过PCA和LDA对人脸局部特征进行降维、 将特征送分类器判定其是否为人脸图像。该方法可有效提高特征提取速度，减少存储量，且 具有较好的识别性能，适合在移动终端等资源有限的嵌入式平台上使用。

本专利“实现面向图像理解的视觉单词生成和评价的系统和方法”与上述专利“一种人 脸识别、装置及移动终端”存在如下不同：

(1)面向应用不同：本专利是面向图像理解的视觉单词生成方法，而专利“一种人脸识 别方法、装置及移动终端”是仅仅应用在人脸识别中，而本专利可以应用在一切基于视觉单 词的图像理解领域中。

(2)输出结果不同：本专利输出的是视觉单词及其有效性评价，而专利“一种人脸识别、 装置及移动终端”输出的是人脸识别的结果。

(3)流程不同：本专利包含有特征提取器、特征融合器、特征降维器、视觉词典生成器 及性能评估器，其中的特征提取器又包含有局部特征提取器和全局信息提取器，提取的局部 特征和全局信息分别为尺度不变特征转换(Scale-invariant feature transform，SIFT)和采用 Canny边缘检测子得到的前景物体外部轮廓信息；而专利“一种人脸识别方法、装置及移动 终端”包含有对目标图像进行预处理、局部滤波器组根据Gabor算法提取人脸局部特征、通 过PCA和LDA对人脸局部特征降维、将特征宋分类器判定是否为人脸图像。两篇专利的不 同之处在于，本文的专利采用的特征是局部特征和全局特征融合后的特征，只是采用PCA进 行降维，生成了视觉词典，并对视觉词典的有效性进行评价，而专利“一种人脸识别方法、 装置及移动终端”首先要进行预处理，采用的仅仅是Gabor提取的局部特征，并采用PCA和 LDA共同进行降维，输出的结果为判定图像是否为人脸的分类结果。

因此，本专利“面向图像理解的视觉单词生成及评价系统”和专利“一种人脸识别方法、 装置及移动终端”虽然看起来有些许相似，但是从根本上看，有本质的不同，且本专利首次 将轮廓系数引入作为视觉词典的评价，极大地提高了视觉单词评价的有效性和快速性。

综上可知，现有的视觉词典生成方法大多基于局部特征SIFT，并采用常见的K-means聚 类方法得到视觉词典。但是图像的局部特征向量维数较高，在进行向量之间的相似性比较时， 随着维数的增加，局部特征的向量分布变得稀疏，并且大部分向量产生高相关距离，从而降 低了视觉模式的比较性和普适性。同时，K-means聚类方法存在着聚类效果不稳定，对初始 聚类中心较为敏感的问题。

发明内容

本发明的目的是克服了上述现有技术的缺点，提供了一种能够实现结合局部特在和全局 特征、缓解维护灾难问题、具有更广泛应用范围的实现面向图像理解的视觉单词生成和评价 的系统及方法。

为了实现上述目的，本发明的实现面向图像理解的视觉单词生成和评价的系统及方法具 有如下构成：

该实现面向图像理解的视觉单词生成和评价的系统，其主要特点是，所述的系统包括：

特征提取器，用以提取视频图像的局部特征和全局特征；

特征融合器，用以将提取出的局部特征信息和全局特征信息进行融合得到融合特征信息 描述矩阵；

特征降维器，用以运用主成分分析方法对所述的融合特征信息描述矩阵进行降维处理；

视觉词典生成器，用以对降维后的融合特征信息矩阵进行处理生成视觉词典；

性能评估器，用以对所述的视觉词典的优劣性进行评价。

较佳地，所述的性能评估器用以采用轮廓系数指标对所述的视觉词典的优劣性进行评价。

本发明还涉及一种实现面向图像理解的视觉单词生成和评价的方法，其特征在于，所述 的方法包括以下步骤：

(1)所述的特征提取器提取视频图像的局部特征和全局特征；

(2)所述的特征融合器将提取出的局部特征信息和全局特征信息进行融合得到融合特征 信息描述矩阵；

(3)所述的特征降维器运用主成分分析方法对所述的融合特征信息描述矩阵进行降维处 理；

(4)所述的视觉词典生成器对降维后的融合特征信息矩阵进行处理生成视觉词典；

(5)所述的性能评估器对所述的视觉词典的优劣性进行评价。

较佳地，所述的特征提取器提取视频图像的局部特征和全局特征，包括以下步骤：

(1-1)所述的特征提取器采用尺度不变特征变换方法提取视频图像的尺度不变转换特征 来对图像的局部特征信息进行描述；

(1-2)所述的特征提取器采用傅里叶形状描述符对形状特征进行描述来对图像的全局特 征信息进行表示。

更佳地，所述的特征提取器采用傅里叶形状描述符对形状特征进行描述来对图像的全局 特征信息进行表示，包括以下步骤：

(1-2-1)对给定物体的图像采用Canny边缘检测子得到对前景物体的外部轮廓描述；

(1-2-2)利用边界曲线的多边形近似方法快速计算傅里叶描述子；

(1-2-3)在前景外部轮廓的基础上，采用傅里叶形状描述子对前景轮廓形状进行描述并 通过形状的主方向消除边界起始点相位影响。

较佳地，所述的特征融合器将提取出的局部特征信息和全局特征信息进行融合得到融合 特征信息描述矩阵，具体为：

所述的特征融合器采用矩阵相加求平均法和矩阵列连接方法对提取出的局部特征信息和 全局特征信息进行融合得到融合特征信息描述矩阵。

较佳地，所述的特征降维器运用主成分分析方法对所述的融合特征信息描述矩阵进行降 维处理，包括以下步骤：

(3-1)对融合特征信息描述矩阵进行标准化处理；

(3-2)计算标准化后的融合特征信息描述矩阵的相关系数矩阵；

(3-3)采用雅克比方法求相关系数矩阵的特征值和相应的特征向量；

(3-4)根据各个主成分累计贡献率的大小选取部分主成分并写出主成分表达式；

(3-5)根据标准化的融合特征信息描述矩阵中的原始数据按照各个样品分别写入所述的 主成分表达式得到主成分得分。

更佳地，所述的融合特征信息描述矩阵D中的图像特征集合为：

$D=\left(\begin{array}{cccc}{x}_{11}& x_{12}& ...& x_{1p}\\ x_{21}& x_{22}& ...& x_{2p}\\ ...& ...& ...& ...\\ x_{n1}& x_{n2}& ...& x_{np}\end{array}\right);$

其中，x_ij指的是第i幅图像的第j个融合特征；

所述的对融合特征信息描述矩阵进行标准化处理，具体为：

根据以下公式对融合特征信息描述矩阵进行标准化处理：

$x_{ij}^{*}=\frac{x_{ij}-{\bar{x}}_j}{\sqrt{\mathrm{var}\left(x_j\right)}},(i=1,2,\mathrm{...},n;j=1,2,\mathrm{...},p)$

其中${\bar{x}}_j=\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{x}_{ij},\mathrm{var}\left(x_j\right)=\frac{1}{n-1}\underset{i=1}{\overset{n}{\Sigma }}{(x_{ij}-{\bar{x}}_j)}^2(j=1,2,\mathrm{...},p).$

更进一步地，所述的计算标准化后的融合特征信息描述矩阵的相关系数矩阵，包括以下 步骤：

(3-2-1)根据如下公式计算标准化后的融合特征信息描述矩阵的相关系数：

$r_{ij}=\frac{1}{n-1}\underset{t=1}{\overset{n}{\Sigma }}{x}_{ti}{x}_{tj},(i=1,2,\mathrm{...},n;j=1,2,\mathrm{...},p);$

(3-2-2)根据如下公式计算相关系数矩阵：

$R=\left(\begin{array}{cccc}{r}_{11}& r_{12}& \mathrm{...}& r_{1p}\\ r_{21}& r_{22}& \mathrm{...}& r_{2p}\\ \mathrm{...}& \mathrm{...}& \mathrm{...}& \mathrm{...}\\ r_{p1}& r_{p2}& \mathrm{...}& r_{pp}\end{array}\right).$

再进一步地，所述的贡献率为：

其中，(λ₁,λ₂,...,λ_p)为相关系数矩阵R的特征值；

所述的根据标准化的融合特征信息描述矩阵中的原始数据按照各个样品分别写入所述的 主成分表达式得到主成分得分，具体为：

根据标准化的融合特征信息描述矩阵中的原始数据按照各个样品分别吸入所述的主成分 表达式得到各主成分下的各个样品的新数据，即为按照如下公式的主成分得分：

$D^{\dim en\_reduction}=\left(\begin{array}{cccc}{F}_{11}& F_{12}& \mathrm{...}& F_{1k}\\ F_{21}& F_{22}& \mathrm{...}& F_{2k}\\ .& .& .& .\\ .& .& .& .\\ .& .& .& .\\ F_{n1}& F_{n2}& \mathrm{...}& F_{nk}\end{array}\right)$

其中，F_ij指的是降维后，第i幅图像的第j个主成分。

较佳地，所述的视觉词典生成器对降维后的融合特征信息矩阵进行处理生成视觉词典， 包括以下步骤：

(4-1)所述的视觉词典生成器采用层次聚类方法对降维后的融合特征信息矩阵进行处理 得到第一阶段的视觉词典结果；

(4-2)所述的视觉词典生成器采用谱聚类处理第一阶段的视觉词典得到最终的视觉词 典。

更佳地，所述的视觉词典生成器采用谱聚类处理第一阶段的视觉词典得到最终的视觉词 典，包括以下步骤：

(4-2-1)根据数据构造一个Graph，Graph的每一个节点对应一个数据点，将相似的点 进行连接，且边的权重用于表示数据之间的相似度，把这个Graph用邻接矩阵的形式表示为 W；

(4-2-2)把W的每一列元素加起来得到N个数，把它们放在对角线上(其他地方都是 零)，组成一个N×N的矩阵，记为D，并令L＝D-W；

(4-2-3)求出L的前k个特征值以及对应的特征向量

(4-2-4)把这k个特征(列)向量排列在一起组成一个N×k的矩阵，将其中每一行看 作k维空间中的一个向量，并使用K-means算法进行聚类。

较佳地，所述的性能评估器对所述的视觉词典的优劣性进行评价，具体为：

所述的性能评估器采用轮廓系数指标对所述的视觉词典的优劣性进行评价。

更佳地，所述的性能评估器采用轮廓系数指标对所述的视觉词典的优劣性进行评价，包 括以下步骤：

(5-1)对于各个对象i，计算其轮廓系数如下：

$S_i=\frac{b_i-a_i}{max(a_i,b_i)}$

其中，a_i为对象i到本簇中其他对象的平均距离，b_i是对象i到其他簇中对象平均距离的 最小值；

(5-2)对于数据集各个聚类计算其轮廓系数如下：

$S_k=\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{S}_i$

其中，n为数据集中样本点个数，k为聚类数；

(5-3)根据所述的轮廓系数指标对所述的视觉词典的聚类效果进行评价。

采用了该发明中的实现面向图像理解的视觉单词生成和评价的系统及方法，具有如下有 益效果：

(1)将局部特征和全局特征融合起来对视频图像进行描述，使得视觉词典更加有效，可 以更好地进行图像理解分析；

(2)引入主成分分析方法对维度灾难问题进行处理，有效地缓解了这一现象；

(3)在视觉词典生成阶段，采用谱聚类方法进行处理，和K-means方法相比，计算复杂 度比K-means要小，在高维数据上表现尤为明显；同时，谱聚类算法建立在谱图理论基础上， 与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点；

(4)引入聚类评价方法轮廓系数值对视觉词典进行评价，更加简单有效，适用于大规模 推广应用。

附图说明

图1为本发明的实现面向图像理解的视觉单词生成和评价的系统的结构示意图。

图2为本发明的特征提取器的工作原理图。

图3为本发明的局部特征提取器的工作原理图。

图4为本发明的全局特征提取器的工作原理图。

图5为本发明的特征融合器的工作原理图。

图6为本发明的特征降维器的工作原理图。

图7为本发明的视觉词典生成器的工作原理图。

图8为本发明的性能评估器的工作原理图。

具体实施方式

为了能够更清楚地描述本发明的技术内容，下面结合具体实施例来进行进一步的描述。

本发明引入主成分分析方法PCA(Principle Component Analysis)，并在视觉词典生成阶 段，采用两层架构进行处理，引入层次聚类方法和谱聚类方法生成视觉词典，可以很好的缓 解特征维度灾难，并且具有很好的稳定性。同时将局部特征和全局特征融合起来，可以对图 像内容进行更好分析，为高层次的图像语义理解提供支持。此外，将聚类算法评价方法轮廓 系数引入对得到的视觉词典进行评价，简单有效。

本发明的目的在于公开了面向图像理解的视觉单词生成及评价系统，如图1所示，该系 统包括：

特征提取器：采用尺度不变特征转换方法(Scale-invariant feature transform，SIFT)提取 视频图像的局部特征之尺度不变转换特征；采用傅里叶形状描述符对全局特征之形状特征进 行描述；

特征融合器：在特征提取器的基础上，采用矩阵相加求平均法和矩阵列连接方法对特征 提取器获取的局部特征和全局特征信息进行融合；

特征降维器：在特征融合器的基础上，采用主成分分析方法对融合得到的混合特征信息 进行降维；

视觉词典生成器：在视觉词典生成器中，采用谱聚类进行处理，将聚类结果作为视觉词 典；

性能评估器：采用轮廓系数指标对视觉词典生成器得到的结果进行评估。

首先，通过特征提取器对视频图像两类特征进行提取：(1)局部特征：采用尺度不变特 征转换方法(Scale-invariant feature transform，SIFT)提取视频图像的尺度不变转换特征，来 对图像的局部特征信息进行描述；(2)全局特征：采用傅里叶形状描述符对形状特征进行描 述，以此对图像的全局特征信息进行表示；然后，在特征提取器的基础上，采用矩阵相加求 平均法和矩阵列连接方法对局部特征信息和全局特征信息进行融合，得到融合特征信息描述 矩阵；然后，采用特征降维器对特征进行降维，运用主成分分析方法对融合特征信息进行降 维处理，得到低维的融合特征信息描述矩阵；之后，采用视觉词典生成器生成视觉词典：首 先采用层次聚类方法对降维后的融合特征信息矩阵进行处理，得到第一阶段的视觉词典结果， 然后，在第一阶段得到的视觉词典上采用谱聚类进行处理，得到最终的视觉词典；最后，采 用性能评估器对视觉词典的优劣性进行评价，采用的是轮廓系数指标，该指标是进行聚类效 果评价的常见的成熟的性能系数，引入其对视觉词典质量进行评价简单且有效。

面向图像理解的视觉单词生成及评价系统，包括以下步骤：

(1)特征提取器102：

在特征提取器中，分别对视频图像101的局部特征之尺度不变转换特征SIFT和全局特征 之形状特征进行提取：

局部特征提取201：301采用尺度不变特征SIFT方法得到视频图像的SIFT特征，得到特 征样本集F＝{f1,f2,…,fm},m表示图像的数目，fi表示图像i的局部特征向量集合，fi可以表示 为fi＝{ti1,ti2,…,tim},m表示图像的局部特征向量数目，tim表示图像i的第m个特征，这些 样本特征构成图像特征集合302(Dlocal)，每一行表示一幅图像，128列代表SIFT特征。

全局特征提取器202：采用傅里叶描述子对视频图像的形状特征进行提取，得到图像中 物体的形状描述，作为全局特征，采用描述矩阵403(Dglobal)表示，具体步骤如下：

(1.2.1)对给定物体的图像，首先通过401采用Canny边缘检测子得到对前景物体的粗略 外部轮廓描述；

(1.2.2)然后，在前景外部轮廓的基础上，402采用傅里叶形状描述子对前景轮廓形状进行 描述；利用边界曲线的多边形近似方法快速计算傅立叶描述子，并通过形状的主方向消除边 界起始点相位影响。

前景目标轮廓线是一条封闭的曲线，把轮廓边界上的每一点看成一个矢量，用复数形式 表示如下：zi＝xi+jyj，i＝1,2,…,N，N为轮廓像素点数，前景目标轮廓的重心坐标为(xc，yc)， 选定某点为初始起点，沿逆时针方向展开并计算前景轮廓上任 一点跟重心的距离di，将一个序列的2D轮廓图像对应转化为一 个序列的1D距离信号，所有距离构成的一个特征序列D＝{d1,d2,…,dN}，对D进行离散傅里 叶变换(Discrete Fourier Transform，DFI)，得到离散傅里叶变换系数an，即前景目标轮廓的 傅里叶描述子：

$a_n=\frac{1}{N}\underset{i=1}{\overset{N}{\Sigma }}d\left(i\right)e^{-\frac{j2\pi ni}{N}},n=1,2,\mathrm{...},N$

对傅里叶描述子进行归一化处理，以a₁为基准归一化傅里叶描述子，得到归一化后的傅 里叶描述子为a_n^*，归一化后的傅里叶描述子具有尺度、平移和旋转的 不变性。

(2)特征融合器103：

在得到的局部特征信息302(Dlocal)和全局特征信息403(Dglobal)的基础上，501采用矩 阵列链接的方法来实现两类信息的融合，设n₁表示局部特征信息的维度，n2表示全局特征信 息的维度，502(Densemble)来表示融合结果，具体计算过程为：

$D^{ensemble}[i,j]=\left(\begin{array}{c}{D}^{local}[i,j],1\le j\le n_1\\ D^{global}[i,j],n_1\le j\le n_1+n_2\end{array}\right)$

其中，Densemble的维度为(n₁+n₂)。

(3)特征降维器104：

采用主成分分析方法对融合后特征信息502(Densemble)进行处理，得到降维后的图像 特征描述信息605(Ddimen_reduction)。具体过程如下：

对于图像特征集合

$D^{ensemble}=\left(\begin{array}{cccc}{x}_{11}& x_{12}& \mathrm{...}& x_{1p}\\ x_{21}& x_{22}& \mathrm{...}& x_{2p}\\ .& .& .& .\\ .& .& .& .\\ .& .& .& .\\ x_{n1}& x_{n2}& \mathrm{...}& x_{np}\end{array}\right)$

主成分生成的具体步骤为：

(3.1)601对原始数据进行标准化处理

对图像特征矩阵进行标准化处理，标准化后的数据为：

$x_{ij}^{*}=\frac{x_{ij}-{\bar{x}}_j}{\sqrt{\mathrm{var}\left(x_j\right)}},(i=1,2,\mathrm{...},n;j=1,2,\mathrm{...},p)$

其中${\bar{x}}_j=\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{x}_{ij},\mathrm{var}\left(x_j\right)=\frac{1}{n-1}\underset{i=1}{\overset{n}{\Sigma }}{(x_{ij}-{\bar{x}}_j)}^2,(j=1,2,\mathrm{...},p).$

(3.2)602计算样本相关系数矩阵

计算标准化后的特征矩阵的相关系数矩阵，为方便，假定原始数据标准化后仍用X表示， 则经标准化处理后的数据的相关系数为：

$r_{ij}=\frac{1}{n-1}\underset{t=1}{\overset{n}{\Sigma }}{x}_{ti}{x}_{tj},(i=1,2,\mathrm{...},n;j=1,2,\mathrm{...},p)$

得到相关系数矩阵：

$R=\left(\begin{array}{cccc}{r}_{11}& r_{12}& \mathrm{...}& r_{1p}\\ r_{21}& r_{22}& \mathrm{...}& r_{2p}\\ .& .& & .\\ .& .& \mathrm{...}& .\\ .& .& & .\\ r_{p1}& r_{p2}& \mathrm{...}& r_{pp}\end{array}\right)$

(3.3)603用雅克比方法求相关系数矩阵R的特征值(λ₁,λ₂,…,λ_p)和相应的特征向量 ai＝(ai1,ai2,…,aip),i＝1,2,…,p。

(3.4)604选择重要的主成分，并写出主成分表达式

根据各个主成分累计贡献率的大小选取前k个主成分，这里贡献率就是指某个主成分的 方差占全部方差的比重，即：

一般要求累计贡献率达到85％以上，这样才能保证综合变量能包括原始变量的绝大多数 信息。

(3.5)605计算主成分得分,得到主成分结果矩阵

根据标准化的原始数据，按照各个样品，分别入主成分表达式，就可以得到各主成分下 的各个样品的新数据，即为主成分得分，具体形式可下：

$D^{\dim en\_reduction}=\left(\begin{array}{cccc}{F}_{11}& F_{12}& \mathrm{...}& F_{1k}\\ F_{21}& F_{22}& \mathrm{...}& F_{2k}\\ .& .& .& .\\ .& .& .& .\\ .& .& .& .\\ F_{n1}& F_{n2}& \mathrm{...}& F_{nk}\end{array}\right)$

(4)视觉词典生成器105：

采用谱聚类进行处理，将聚类结果作为视觉词典；具体步骤如下：

(4.1)701根据数据构造一个Graph，Graph的每一个节点对应一个数据点，将相似的点连 接起来，并且边的权重用于表示数据之间的相似度。把这个Graph用邻接矩阵的形式表示出 来，记为W。

(4.2)702把W的每一列元素加起来得到N个数，把它们放在对角线上(其他地方都是零)， 组成一个N×N的矩阵，记为D。并令L＝D-W。

(4.3)703求出L的前k个特征值(在本文中，除非特殊说明，否则“前k个”指按照特征 值的大小从小到大的顺序)以及对应的特征向量

(4.4)704把这k个特征(列)向量排列在一起组成一个N×k的矩阵，将其中每一行看作 k维空间中的一个向量，并使用K-means算法进行聚类。聚类的结果中每一行所属的类别就 是原来Graph中的节点亦即最初的N个数据点分别所属的类别，得到706视觉词典V。

(5)性能评估器106：

采用轮廓系数值对视觉词典生成的聚类效果进行评价，轮廓系数是一种将簇的凝聚度和 分离度有机结合的而形成的一种聚类有效性评价指标。

(5.1)801计算数据集中每一个对象的轮廓系数值：

对于某一对象i，其轮廓系数为：

$S_i=\frac{b_i-a_i}{max(a_i,b_i)}$

其中，a_i是对象i到本簇中其他对象的平均距离，b_i是对象i到其他簇中对象平均距离的 最小值。

(5.2)802对所有对象的轮廓系数值先求和再求平均，即得到803某次聚类的评估系数之 轮廓系数值：

对于数据集某次聚类而言，其轮廓系数Sk定义如下：

$S_k=\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{S}_i$

其中n为数据集中样本点个数，k为聚类数，Sk也可以称做平均轮廓系数，803采用Sk 进行聚类有效性分析。而轮廓系数和聚类效果的关系是：轮廓系数值愈大，聚类效果愈佳。

采用了该发明中的实现面向图像理解的视觉单词生成和评价的系统及方法，具有如下有 益效果：

(1)将局部特征和全局特征融合起来对视频图像进行描述，使得视觉词典更加有效，可 以更好地进行图像理解分析；

(2)引入主成分分析方法对维度灾难问题进行处理，有效地缓解了这一现象；

(3)在视觉词典生成阶段，采用谱聚类方法进行处理，和K-means方法相比，计算复杂 度比K-means要小，在高维数据上表现尤为明显；同时，谱聚类算法建立在谱图理论基础上， 与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点；

(4)引入聚类评价方法轮廓系数值对视觉词典进行评价，更加简单有效，适用于大规模 推广应用。

在此说明书中，本发明已参照其特定的实施例作了描述。但是，很显然仍可以作出各种 修改和变换而不背离本发明的精神和范围。因此，说明书和附图应被认为是说明性的而非限 制性的。