图像自动标注

武汉理工大学毕业设计（论文）目录摘要 IABSTRACT.II绪论 .11 自动图像标注概述 .31.1 研究目的和意义 .31.2 现有图像标注算法分类 .32 用于图像标注的特征提取 .72.1 颜色特征提取 .72.2 纹理特征提取 .83 支持向量机模型 .123.1 SVM 模型原理及核函数 .123.2 参数设置和训练算法 .163.2.1 参数的设置 .163.3.2 SVM 的训练算法 .173.3 LIBSVM 软件包 194 SVM 技术用于自动图像标注 .234.1 特征提取模块 .234.2 SVM 分类模块 .234.3 实验结果及分析 .24结束语 .26致谢 .27参考文献 .28附录 MATLAB 程序源代码 .29武汉理工大学毕业设计（论文）I摘要近年来，自动图像标注（Automatic Image Annotation,AIA）技术已经成为图像语义理解研究领域的热点。随着机器学习理论的不断发展，包括相关模型、分类器模型等不同的学习模型已经被广泛地应用于自动图像标注研究领域。自动图像标注就是让计算机自动地给无标注的图像加上能够反映图像内容的语义关键词。自动图像标注在图像检索研究领域中非常具有挑战性，是实现图像语义检索的关键。现有的自动图像标注算法可以大致分为基于分类的标注算法、基于概率关联模型的标注算法以及基于图学习的标注算法等三大类。本文重点研究了另外一种自动图像标注算法基于 SVM 技术的标注算法，研究了 SVM 原理，构造 SVM 分类器，应用 matlab 对图像进行纹理、颜色特征的提取，通过分类器，实现图像自动标注。关键词：自动图像标注 标注算法 分类器 SVM 武汉理工大学毕业设计（论文）IIABSTRACTIn recent years, automatic image annotation (AIA) technology has become the hot spots of the field of the image semantic understanding. With the continuous development of the theory of machine learning, including the related model, the classification model of different learning models have been widely used in automatic image annotation research areas. Automatic image annotation is to let the computer automatically mark keywords that can reflect the semantics of image content for the non-marked images. Automatic image annotation is very challenging in the research field of image retrieval, and is the key to achieve the image semantic retrieval. Automatic image annotation algorithm tagging algorithm can be broadly divided into three categories, based on the classification, based on the probability associated with tagging algorithm of the model and based on graph learning labeling algorithm. This paper focuses on another kind of automatic image tagging algorithm - SVM-based tagging algorithm, to study the principle of SVM constructed SVM classifier, application MATLAB for image texture and the color feature extraction, by classifier, to achieve image automatic annotation.Key words: automatic image annotation tagging algorithm the classifier SVM武汉理工大学毕业设计（论文）1绪论随着数码相机和可拍照手机等设备的日益普及，各种各样的图像数量呈现几何级的飞速增长。而同时互联网的快速发展也使得图像传播与共享变得更加快捷。因此，对网络多媒体信息进行有效的管理与检索成为迫切需要解决的问题。虽然基于内容图像检索(Content-based Image Retrieval, CBIR)已经取得了不少的研究成果，但由于受到“语义鸿沟(Semantic Gap)”瓶颈的制约，即底层视觉特征（如颜色、纹理、形状等）不能完全反映和匹配用户的查询意图，导致基于内容图像检索技术的研究遇到了前所未有的巨大挑战，如何真正实现基于语义的图像检索仍旧是一个难题。由于用户更加习惯于利用关键词(Keywords)这种最为直接的方式来表达查询需求，并且现有的互联网搜索引擎均提供基于文本的图像检索功能，而人工标注又是一项相当费时费力的工作，由此催生了自动图像标注技术的发展。自动图像标注(Automatic Image Annotation,AIA)就是让计算机自动地给无标注的图像加上能够反映图像内容的语义关键词。它利用已标注图像集或其他可获得的信息自动学习语义概念空间与视觉特征空间的关系模型，并且此模型标注未知语义的图像，即它试图在图像的高层语义信息和低层特征之间建立一种映射关系，因此在一定程度上可以解决“语义鸿沟”问题。现有的人部分自动图像标注算法，都尝试着直接在图像级别实现语义关键词的标注，即算法无需在图像的区域和关键词之间建立一一刘一应的映射关系。但也有部分工作试图从物体识别的技术角度去解决标注问题，为一幅图像的每个区域均赋予关键词。据此，我们将前者称之为标注(annotation)，而将后者称之为区域命名(region naming, once Lo-one correspondence between words and regions) 。 自动图像标注在图像检索研究领域中非常具有挑战性，是实现图像语义检索的关键。若能实现自动图像标注，则图像检索问题就可以转化为相当成熟的文本检索问题。自动图像标注涉及计算机视觉、机器学习、信息检索等多方而的内容，具有很强的研究价值和潜在的商业应用，如个人桌而照片管理、互联网图像广告自动投放等应用 。1Mori 等人在 1999 年提出的共生模型(Co-occurrence Model)，开辟了自动图像标注领域的研究。此后各种新颖的自动图像标注算法不断涌现，众多的研究者从不同的角度分析和解决标注问题，期望能找到良好的检索和标注方法。这些方法从图像的特征表示机制进行分析，大致可以分为两类:一类是使用图像的全局视觉信息，采用面向图像场景语义的方法进行标注，该类方法将图像特征和文本标注词完全分离，在纯视觉层次上比较图像相似度，是有监督的学习方法。已标注的训练图像集合被用于确定图像特征和标注词间的关系，标注可以通过比较视觉特征并传播标注词实现。另一类是首先将图像划分为若干个同质区域或图像子块，再基于区域划分进行图像语义标注。该类方法采用图像分割算法，试图有效地将图像划分为若干个语义对象单元，通过寻找标注关键词与区域武汉理工大学毕业设计（论文）2语义对象或整幅图像本身间的对应关系来实现自动图像标注。现有主流的标注算法大多采用基于区域划分的表示机制。本文首先介绍基于区域划分的几种自动图像标注算法，然后对基于 SVM 技术的自动图像标注算法重点研究。武汉理工大学毕业设计（论文）31 自动图像标注概述1.1 研究目的和意义随着图像处理、机器学习和自然语言处理等技术的发展，近年来出现了众多对图像进行语义标注的模型，其核心在于对己有的训练数据自动学习底层视觉特征空间与高层语义空间的关系模型，通过训练好的分类模型对未标注的图像进行自动语义标注。因此，图像语义的自动标注可以有效避免基于人工标注的图像检索系统所面临的一系列问题，使大规模图像基于语义检索的应用更具现实性。可以预见，图像自动语义标注具有广泛的应用背景，是一个颇具生命力的研究方向。图像语义的自动标注能够将图像的视觉特征转化为图像的标注字信息，这为用户的使用带来了极大的方便，也克服了手工标注费时费力的缺点，因此，图像语义的自动标注成为了支持图像语义检索的一个重要技术，也成为了图像检索领域一个十分活跃的研究分支 。本文选择了于底层视觉特征的自动图像语义标注这个具有挑战性的研究课题，3,2希望能够将知识学习和数据挖掘的方法同图像语义的自动标注相结合，提高自动图像语义标注的准确性和图像检索的质量。1.2 现有图像标注算法分类图像的语义标注就是为图像添加关键字来表示图像的语义内容。图像的语义标注方式可分为三类：手工标注，半自动标注和自动标注 。4手工标注对图像的内容描述的最为准确，但随着图像数据库的不断增大，手工标注费时费力以及主观偏差的缺点就越来越明显。半自动标注是指通过人机交互手段，采用相关反馈技术对图像进行标注。这种方法随着反馈和检索次数的增多，检索精度会越来越高，标注结果会越来越好。自动标注降低了标注的成本，避免了主观偏见性，也加快了标注的速度。对于大规模数据库，手工标注需要耗费大量的人力资源。另外，由于不同的人对图像数据的理解存在一定的差异，手工标注的信息将会产生不一致性，所以人们加深了对自动图像标注的研究。现有的自动图像标注算法可以大致分为基于分类的标注算法、基于概率关联模型的标注算法以及基于图学习的标注算法等三大类。1) 基于分类的自动图像标注算法较为直观的自动图像标注的思路，是将标注问题看成是图像语义分类问题。若将每个语义关键词都看成是一个类别标记(label)，则图像标注问题就转化为图像分类问题。因此完全可以从图像分类的角度去解决标注问题。但不同于传统的图像分类问题中每幅图像只归属于某一语义类别，自动图像标注问题有其特殊性。从关键词的角度分析，在标注问题中每幅图像同时属于多个语义类别（即标注有多个关键词） ，因此标注问题属于一个典型的多标记学习问题(Multi-Label Learning) 。从图像的角度分析若将整幅图像看作5武汉理工大学毕业设计（论文）4由多个示例（即区域）组成的包，示例没有概念标记，但包有一个概念标记。如果包中至少有一个示例是正例，则该包被标记为正包，如果包中没有任何一个示例是正例，即所有示例都是反例，则该包被标记为反包。而给定的训练集上关键词均只是标注于整幅图像上，而并不知适关键词与图像区域之间的对应关系，因此标注问题的这一歧义性使得其符合典型的多示例学习(Multi-Label Learning)问题。现有的基于分类的标注算法大多单纯从多示例学习的角度或者多标记学习的角度来描述和解决标注问题。尽管这此方法在具体表达上各有特点，但它们的核心思想却是一致的，即利用已知的标注数据建立某种模型来描述文本词汇与图像特征之间的潜在关联或者映射关系，并据此预测未知图像的标注。基于分类的图像标注算法的基本流程图如图 1-1 所示。、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、图 1-1 基于分类的图像自动标注算法的一般流程2) 基于概率关联模型的自动图像标注算法基于概率关联模型的图像标注算法 ，其本质是在概率统计模型的基础上，分析图5像区域特征与语义关键词之间的共生概率关系，并以此为待标注图像进行语义标注。直观地，两幅图像若具有较高的视觉相似性，则两者标注相近关键词序列的概率就越高。这种方法的特点在于，无需通过学习机制为每个语义关键词建立相应的低层视觉特征表示。换句话说，语义关键词与低层视觉特征之间不存在一一对应的映射关系。相关模型是目前基于概率关联模型的自动图像标注领域最重要的算法之一，许多后续的标注算法都是基于相关模型进行改进和提高的。其基本思想主要是建立图像和语义关键词之间的概率相关模型。算法通过为某一幅待标注图像找到与其相关性最大的一组武汉理工大学毕业设计（论文）5语义关键词，来获得图像的标注结果。测试图像标注关键词的概率由该测试图像的所有分割区域共同决定，即通过乘积的方式来得到测试图像的每一个区域与训练集中每个图像的视觉相似性。而对测试图像标注结果影响较大的通常是与其相似度较高的训练图像集合，而与其相似度较小的训练图像对其标注结果的影响通常较小。基于概率关联模型的自动图像标注算法的一般流程如图 1-2 所示。图中虚线部分表示部分算法借助图像检索结果或由 WordNet 得到的标注词本身间的相互关系来决定最终标注结果。、 、 、 、 、 、 、 、 、 、 、 、 (、 、 、 、 、 、 、 、 、 、 、 )、 、 、 、 、 、 (、 、 、 、 、 、 、 、 、 )、 、 、 、 、 、 、 、 、 、 、 、 、 、 (、 、 )、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、WordNet、 、 、 、图 1-2 基于概率关联模型的自动图像标注算法的一般流程3) 基于图学习的自动图像标注算法近年来基于图学习(Graph Learning)的方法作为一中重要的机器学习算法，已经被用来有效地解决图像自动标注这一图像语义理解问题 。基于图学习的算法是一种半监督6,5学习算法，已知类标的训练数据和未知类标的测试数据都将参与到算法的学习过程中。与传统的有监督学习和无监督学习相比，半监督学习可以在学习阶段利用更多的信息，如数据的分布特性等，它适用于总数据量较大、已标记训练数据量相对较小的情况。若我们将每幅图像( 或每个标注词)作为图节点，以图像间(或标注词间)的相似关系作为边，通过图学习算法就可以实现标注信息从已标注图像到未知图像的传播，从而完成图像标注任务。基于图学习的图像标注算法的流程如图 4 所示。其中虚线部分含义是指该步骤是可选项，即表不仅有部分已有算法包含该步骤。武汉理工大学毕业设计（论文）6、 、 、 、 、 、 、 、 、 、 、 WordNet、 、 、 、 、 、 、 -、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、图 1-3 基于图学习的图像标注算法的一般流程利用图像的自动标注来实现图像的语义理解已成为当前的研究热点与重点。本文将对另一种算法基于 SVM 技术的自动图像标注算法进行研究学习。基于 SVM 技术的自动图像标注算法是一种十分简便的图像标注方法，主要是构造SVM 分类器对图像进行分类。图像的色彩、纹理特征提取为图像的自动分类提供了必备的数据基础。将提取的特征数据分成训练集和测试集数据，通过 SVM 进行训练得到分类模型。然后为测试图像集分类，最后实现图像自动标注。基于 SVM 技术的自动图像标注算法的一般流程如图 1-4 所示。SVM、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、图 1-4 基于 SVM 的自动图像标注算法的一般流程武汉理工大学毕业设计（论文）72 用于图像标注的特征提取2.1 颜色特征提取颜色特征是图像的主要属性之一，它是人们对图像的视觉感受，通过颜色特征人们了解图像中事物对象的表面性质。每一种事物都有其独特的颜色，如叶子在生长期间一般是绿色的，枯萎时一般是黄色的，当一副图像上出现了某一事物，则该事物的颜色特征将不会随着图像的旋转、移动等而发生改变，颜色特征具有很强的鲁棒性，因此图像检索中将颜色特征作为首选特征之一 。107本文选择 HSV 颜色模型提取颜色特征。HSV 是一个颜色感知模型，能够较好地表示颜色的三个基本属性：色调、亮度和饱和度。色调(Hue)是指光的颜色，它与混合光谱中主要光波长相联系，不同的波长产生不同的颜色感知，如红、黄、绿等。饱和度(Saturation)是指颜色的深浅或浓淡程度，饱和度越高，颜色越深，如深红、深蓝。饱和度的深浅与颜色中加入白色的比例有关，它反映了某种颜色被白色冲淡的程度。亮度(Value)是指入眼感受到的光的明暗程度，光波的能量越大，亮度就越大，V 通道常用百分比度量，从黑 0到白 100。HSV 颜色空间可用一个圆锥体表示，其中立体的竖直轴代表由黑到白亮度的变化，离开长轴的距离表示饱和度，圆周上各点代表不同的色调。、60、0、120、180、240、 、300、V0 SH1、 、 、 、 、 、 、 、 、 、 、图 2-1HSV 颜色空间HSV 颜色空间主要有两个特点：一，色调和饱和度分量与人感受颜色的方式是紧密武汉理工大学毕业设计（论文）8相连的；二，亮度分量与图像的彩色信息无关。HSV 颜色空间对应于人眼颜色视觉特征的三要素，各通道之间相互独立，可以独立感知各颜色分量的变化，因此在基于内容的图像分类中应用这种色彩模型更能符合人的视觉判断。本文采用一种基于 HSV 颜色空间的非等间隔量化方法，首先，将得到的 RGB 空间上的图像转化到 HSV 空间，然后按照 H、S、V 三个分量按照人的颜色感知进行非等间隔量化。应用 matlab 软件最终得到 H、S、V 的均值、方差和三阶矩 9 维颜色特征向量。2.2 纹理特征提取纹理特征作为图像的全局特征，描述了图像中事物的表面性质，纹理特征可以给出粗糙度(coarseness)、对比度 (contrast)、方向度(directionality)、线性似度(line-likeness)、规则度(regularity)、粗略度(roughness)六种视觉属性，但它不能表现出事物的本质属性，这样单纯纹理特征不能与语义进行一一对应。在图像检索中，要使用纹理特征，必须要先从图像中提取出有效的纹理特征信息 。107本文用统计方法进行图像纹理特征提取。图像中的事物纹理比较细致，但没有一种规则性，比如树木的纹理，其纹理细致，没有一定的规律，在对这些事物进行纹理特征提取时候，可以使用统计方法。其是一种通过对图像中像素间灰度分布进行统计的纹理特征提取方法。典型的统计方法是灰度共生矩阵。灰度共生矩阵是在 1973 年由 Haralick 提出了的，其是一个对称方阵，在该理论中描述纹理的方式是灰度的空间相关特性，其认为纹理是灰度分布在图像空间中反复出现形成的，图像空间不同位置的像素间可能会存在或大或小的距离，但两者之间还是会存在一定空间关系，这种空间关系就是所谓的灰度空间相关特性。灰度共生矩阵是关于亮度变化的二阶统计量，它可以反映图像亮度的分布特性，也描述了亮度相同或相近像素间的位置分布特性。假设一副二维图像 ，大小 ，图像灰度级 N 级，则共生矩阵 为),(yxfM ),(jiMd矩阵，灰度值为 i, j 距离为 d 的两像素同时出现的概率分布为 。如果#x 表示 xNM dP的个数，则满足一定空间关系的灰度共生矩阵为 ，即在 方向上距离为 d,灰度级),(jiPd分别为 i、j 的两像素同时出现的概率。本文 选择四个离散方向： 。135,904,),(),(),(,#),( 2121 jyxfiyxfNyxPd Haralick 等人提出 14 个二次统计量 :角二阶距：(2-1),(12djipQNij对比度（惯性矩）：武汉理工大学毕业设计（论文）9(2-2)Nij djipjiQ122 ),()(相关：(2-3)Nij duji121213 ),(熵：(2-4),(1014 log),(djipNijdjipQ方差：(2-5)Nij djipm125 ),()(均值和：(2-6)(26kpQNkx方差和：(2-7)()(2267 kpkNx逆差距：(2-8)NijjidpQ128)(,差的方差：(2-9)()(102109 kpkNk yy和熵：武汉理工大学毕业设计（论文）10(2-10)(log)(210 kpkpQxNkx逆熵：(2-11)(log)(101 kpkpyNky聚类阴影：(2-12) Nij djipujiQ1 32112 ),()()( 显著聚类：(2-13) Nij djipuji1 42113 ),()()( 最大概率：(2-14),(14djipMAXQ在上述 14 个定义中的参数的含义分别为： (2-15)Nijjiu1),(2-16)jidjp12,(2-17)NiNjjiud112),()(2-18)jidjp1122 ,(2-19),(21jiNmij(2-20),()(1djipkpijx Nk2,3武汉理工大学毕业设计（论文）11(2-21),()(1djipkpNijy 1,0Nk在实际中从(2-1)到(2-14)这 14 个特征量并不是一起使用，可能是某几个特征量的组合，这些特征量描述的信息有一定的重叠，这样使用某几个特征量就可以描述图像纹理的信息，常用的特征量如下：(1)能量：即上述特征量中的角二阶矩，是灰度共生矩阵中各个元素的平方和，该特征量可以描述图像的灰度分布情况以及纹理粗细度，是纹理灰度变化的度量特征量。如果图像纹理粗糙，则该特征量较大，反之，纹理细腻，则该特征量较小。(2)对比度 (惯性矩)：是灰度共生矩阵中主对角线的惯性矩，该特征量是图像清晰程度以及纹理沟纹深浅程度的度量特征量。对比度值较小，说明图像效果清晰，沟纹较浅，反之，对比度值较大，说明图像效果模糊，沟纹较深。(3)相关：是灰度共生矩阵行或者列方向上元素相似程度的度量特征量，该特征量可以作为判断纹理主方向的特征量。(4)熵：图像信息量，是一个随机性的度量特征量，当灰度共生矩阵中元素分散程度较大时候，熵较大，图像为满纹理时候，熵取得最大值，反之如果纹理分布较集中，则熵较小，如果图像中无纹理，则熵取最小值零。(5)逆差距：局部平稳特征量，该特征量可以描述图像纹理局部变化的情况。如果纹理局部变化小，局部较均匀，则该特征量较大，反之，纹理局部变化大，局部粗糙，该特征量较小。本文应用 matlab 选择能量、熵、惯性矩、相关的均值和标准差作为最终 8 维纹理特征。、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、0、 45、 90、 135、 、 、 、 、图 2-2 图像纹理特征提取流程图3 支持向量机模型支持向量机(Support Vector Machine)是 Cortes 和 Vapnik 于 1995 年首先提出的，它在武汉理工大学毕业设计（论文）12解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。支持向量机方法是建立在统计学习理论的 VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy ）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力（或称泛化能力） 。 3.1 SVM 模型原理及核函数SVM 方法是通过一个非线性映射 p，把样本空间映射到一个高维乃至无穷维的特征空间中(Hilbert 空间)，使得在原来的样本空间中非线性可分的问题转化为在特征空间中的线性可分的问题。简单地说，就是升维和线性化。升维，就是把样本向高维空间做映射，一般情况下这会增加计算的复杂性，甚至会引起“维数灾难” ，因而人们很少问津。但是作为分类、回归等问题来说，很可能在低维样本空间无法线性处理的样本集，在高维特征空间中却可以通过一个线性超平面实现线性划分(或回归)。一般的升维都会带来计算的复杂化，SVM 方法巧妙地解决了这个难题：应用核函数的展开定理，就不需要知道非线性映射的显式表达式；由于是在高维特征空间中建立线性学习机，所以与线性模型相比，不但几乎不增加计算的复杂性，而且在某种程度上避免了“维数灾难” 。这一切要归功于核函数的展开和计算理论。在 SVM 的最简单的线性分类中，一个 SVM 是一个将一组正样本从负样本中分离出来，具有最大边界距离的超平面。在线性情况下，边界间距是超平面与正负样本中最近的距离。SVM 最初用来对线性可分数据进行两类问题的分类处理，假设有 N 个训练样本，这里 ，表示样本数据 (一般为一个向量集合) ，),(),(,21nyxyx， niRx，表示样本数据 的类型。在线性支持向量机分类中，最优分类超平面将样本i i数据分成两类，而且使两个类之间具有最大的边界距离 。11) 线性可分最优分类面考虑一个两类训练样本集的分类问题：(3-1)1,),(,),(1 yRxyyxDnn存在如下超平面： ，使得训练样本集完全正确分开，同时满足距离超0XWb平面最近的两类点间隔最大，我们称样本集被超平面最优划分。归一化超平面方程，使得所有样本集满足如下约束条件：(3-2)nibyii ,1,),( 武汉理工大学毕业设计（论文）13+- winm2arg H1 2图 3-1 最优分类面图中，负圆形点和正圆形点代表两类样本，H 为分类线， H1，H2 分别为过各类中离分类线最近的样本且平行于分类线的直线，它们之间的距离叫做分类间隔(margin)。此时分类间隔为 ，最大间隔等价于使 最小。使分类间隔最大实际上就是W/22W对学习机推广能力的控制，这是 SVM 的核心思想之一。统计学习理论指出，在 N 维空间中，设样本分布在一个半径为 R 的超球范围内，则满足条件 的正则超平面构成的A指示函数集)， 的 VC 维满足下面的界：)X,sgn()b,( bf (3-3)1,mi2NAh因此，使 最小就是使 VC 维的上界最小，从而实现结构风险最小化（Structure 2WRisk Minimization，SRM）准则中对函数复杂性的选择。在线性可分情况下，在结构风险最小化准则下的最优超平面问题，可以表示为如下的约束优化问题： (3-4)nibytsii ,1,)X,W(.21min式(3-4)问题的最优解可以通过求解拉格朗日函数的鞍点得到，定义如下的 Lagrange 函数：武汉理工大学毕业设计（论文）14(3-5)1)X,W(21),W(1bybLiini其中， 为各样本对应的 Lagrange 系数。0i求解式(3-5)的最小值，可以令该泛函对 W 和 b 求偏导，并令它们等于 0，就可以把上述求最优分类面的问题转化为较简单的对偶问题。其对偶问题由如下形式给出：(3-6)11,1() X,Y2.0,nnkijijijijni iiQystyn这是一个不等式约束下二次函数寻优的问题，存在唯一解。以上优化问题的最优解为： ，这样，计算得到：Tn),(1(3-7) sriiibyX,W21XW1其中， 和 是两类中任意的支持向量。依据 KKT 互补条件，其中只有少量最靠rXs近超平面样本点的 值不为零，Vapnik 等人称之为支持向量 (SV)。i获得的支持向量及相关参数后，就可以求得上述问题的最优最终判别函数：(3-8)Xsgn()X,sgn()( bybf ii2) 线性不可分最优分类面以上讨论仅限定在训练样本数据是线性可分的情况，即经验风险 为 0 的前提empR下，通过对分类间隔最大化，使分类器获得最好的推广性能。然而，实际中存在大量线性不可分情况，一种解决方案是由 Cortes 和 Vapnik 提出在条件式(3-2)中引入非负松弛项，这时约束条件式成为:nii ,21,0(3-9)nibyiii ,1,1)X,W( 容许错分的分类超平面称作线性软间隔分类超平面。由于允许存在错分样本，此时的软间隔分类超平面表示在剔除那些错分样本后最大分类间隔的超平面。此时，目标函数由式(3-4)变为： (3-10)niiC121),(最小，即折衷考虑最少错分样本和最大分类间隔。其中惩罚参数 C 作为综合这两个武汉理工大学毕业设计（论文）15目标的权重。线性软间隔优化问题对应的拉格朗日函数形式如下：(3-11) niiiiTinii byCbL 112 )XW(W1),( 其中， 。对偶表示可以通过求 的偏导等于 0 得到： 0,ii ,(3-12)00),W(,0),( 11iii ininiibLxybL线性软间隔分类超平面的对偶问题与线性可分目标函数相同。仅有的区别只是约束条件变为： ，最优判别函数的形式与式(3-8)一样。Ci0前面介绍了在样本线性可分和线性不可分的情况下，如何求解最优超平面。而在实际分类问题中，分类问题往往是一个非线性的问题，理想的分类面应该也是非线性的。SVM 处理非线性问题的方法是，首先将训练集从原始模式空间经过特定函数的非线性变换，映射到高维特征空间，将非线性问题转化为某个高维空间中的线性问题，然后在高维特征空间中，寻找最优分类超平面，该超平面实际上对应着原始模式空间中的非线性分类面。因此，SVM 在处理非线性分类问题时，仅比线性情况多了一个非线性映射环节。假定该非线性映射为： ，这时对偶形式的目标函数变为：)X(3-13) nij jijijink yQ11 )X(,2)( +-yx+ -、 、 、 、 、 、 、 、 、 、yx图 3-2 输入空间到高维特征的转换由于对偶形式中只出现两向量的内积运算，Vapnik 等人提出采用满足 Mercer 条件的武汉理工大学毕业设计（论文）16核函数 来代替内积运算，即 实现非线性软间隔分类。)X,(jiK )X(,),X(jijiK常用的核函数包括多项式核、径向基核以及 Sigmoid 核等。其核形式的最优判别函数为：(3-14)(sgn)(XbyfSViii当存在从输入空间到特征空间的映射： ，使得 ，x： )(,)x,( xK则 是核函数。核函数 K(x, x)是输入空间和特征空间之间的映射。选择不同的核)X,(K函数意味着采取不同的标准对相似性和相似程度进行估计。因此，核函数的选择对非线性支持向量机的构建是至关重要的，核函数的选择是一个难题。常用的核函数有：(1) 多项式核：(3-15)dcxxK)(),( 其中， ，常用的多项式核是 c=1 的情况。0c(2) 高斯核：(3-16)2exp(),( K参数 控制核函数的宽度，它的选择很大程度上决定了核函数的好坏，并最终决定了分类的效果。(3)sigmoid 核：(3-17)0,),(tanh),( vkvxkyxK3.2 参数设置和训练算法3.2.1 参数的设置与传统的神经网络方法相比，支持向量机具有出色的性能，它运用结构风险最小化原则，能在经验风险与模型复杂度之间作适当的折衷，从而获得更好的推广能力。但是，支持向量机在实际应用中，关于参数选择的问题仍然没有得到很好地解决，如多项式学习机器的阶数问题、径向基机器中的函数宽度，以及 Sigmoid 机器中函数的宽度和偏移等。统计学习理论目前对这些问题给出了一些建议和解释，但还没有给出实际可行的方案。目前也只有通过实验方法来确定最佳参数。因此，在使用支持向量机进行分类和预测时，如何选择适当的参数就成了个非常重要的问题 。12由上面的 SVM 基本算法可以看出，支持向量机的判决函数的依据是支持向量和偏移值，而支持向量是由训练集中的一部分组成，而不同的训练集中训练出来的支持向量和武汉理工大学毕业设计（论文）17偏移是不一致的，所以 SVM 分类器性能对训练集数据选取是敏感的。为了提高支持向量机的分类性能，通常需要不断调整训练集，并对其进行多次反复的训练，对一个具体分类器找到最佳训练集，即找到分类中用于判别的支持向量，这就是系统的再学习过程。 为了选择一个 SVM 分类器较优的参数，前提是要确定一个好的训练集。比较常用的方法是先用训练集一部分训练，通过实验得到 SVM 对这个训练集的最佳参数，找出对这个训练集中分类错误的样本，这时候把那些分类错误的样本加到训练集中，重新使用新的样本集训练测试 SVM 到最佳参数，若分类结果不满意再重复上述过程。对于确定了的训练样本集，训练分类器的时候我们可以尝试的核函数可以有几种，实验中可以调试的参数有惩罚系数 C 和核函数的其他参数，关于这些参数的选择，只能根据个人经验来选择，然后不断的测试更改这二个值并达到最优效果。而使用交叉选择的办法可以快速达到最优解，一般来说，以高斯核为例 C 的取值一般不超过 ，其最小92取值一般超过 2。 的取值一般也不超过 ，最小取值一般也超过 ，所以可以先把 C323-的值确定为 9 个 ，同样 的值确定为几个，这样再根据经验选择以上组合可),(91以快速达到比较优化的结果，达到结果后可以固定其中一个值，然后微调另一个值，看得到分类结果，调好一个参数后再固定它，微调另一个参数，直到达到最佳而怎样从理论上保证选择最优的核函数仍是一个有待解决的问题，目前多是通过实验来决定。3.3.2 SVM 的训练算法支持向量机的最终求解问题归结为一个有约束的二次型规划(QP, Quadratic Programming)问题。二次规划是一种常见的优化问题，从数学角度分析，SVM 是一个求约束条件的极值问题。在二次规划中，条件极值问题的通常解法有罚函数法和单纯行法。但是，这些方法只适合小样本情况，当样本数目较大时，算法复杂度会急剧增加，占用极大的系统内存，如计算 4000 个样本的核函数矩阵就需要 128M 内存，而且由于迭代误差的积累，也会导致算法精度无法接受。为降低计算资源、提高算法效率，已经提出许多针对大规模样本集的训练算法，多数算法的思想是将大规模的原问题分解为若干小规模的子问题，按照某种迭代策略，反复求解子问题，得到原问题的近似解，并能逐渐收敛到原问题的最优解。这就是分解算法(decomposition)的一般作法，下面给出一般性的分解算法步骤：(1)令 b 为子集大小 (b ： ： 其中 是训练数据集的目标值，对于分类，它是标识某类的整数(支持多个类) ；对于回归，是任意实数。 是以 1 开始的整数，表示特征的序号；为实数，也就是我们常说的特征值或自变量。当特征值为 0 时，特征序号与特征值 value 都可以同时省略，即 index 可以是不连续的自然数。与第一个特征序号、前一个特征值与后一个特征序号之间用空格隔开。测试数据文件中的 label 只用于计算准确度或误差，如果它是未知的，只需用任意一个数填写这一栏，也可以空着不填。例如：+1 1:0.708 2:1 3:1 4:-0.320 5:-0.105 6:-1 8:1.21为了使用的方便，可以编写小程序，将自己常用的数据格式按照这种数据格式要求转换成这种格式供 LIBSVM 直接使用。1) svmscale 的用法对数据集进行缩放的目的在于：(1)避免一些特征值范围过大而另一些特征值范围过小；(2)避免在训练时为了计算核函数而计算内积的时候引起数值计算的困难。因此，通常将数据缩放到-1,1或者是0,1 之间。用法：svmscale -l lower -u upper -y y_lower y_upper-s save_filename -r restore_filename filename（缺省值： lower = -1，upper = 1，没有对 y 进行缩放）其中，-l：数据下限标记；lower ：缩放后数据下限；-u：数据上限标记；upper ：缩放后数据上限；-y：是否对目标值同时进行缩放；y_lower 为下限值，y_upper 为上限值；-s save_filename：表示将缩放的规则保存为文件 save_filename；-r restore_filename：表示将缩放规则文件 restore_filename 载入后按此缩放；filename：待缩放的数据文件（要求满足前面所述的格式） 。缩放规则文件可以用文本浏览器打开，看到其格式为：lower upperlval1 uval1lval2 uval2武汉理工大学毕业设计（论文）21其中的 lower 与 upper 与使用时所设置的 lower 与 upper 含义相同；index 表示特征序号；lval 为该特征对应转换后下限 lower 的特征值； uval 为对应于转换后上限 upper 的特征值。数据集的缩放结果在此情况下通过 DOS 窗口输出，当然也可以通过 DOS 的文件重定向符号“ ”将结果另存为指定的文件。2) svmtrain 的用法svmtrain 实现对训练数据集的训练，获得 SVM 模型。用法： svmtrain options training_set_file model_file其中，options（操作参数）：可用的选项即表示的涵义如下所示-s svm 类型：设置 SVM 类型，默认值为 0，可选类型有：0 - C - SVC1 - n - SVC2 - one - class - SVM3 - e - SVR4 - n - SVR-t 核函数类型：设置核函数类型，默认值为 2，可选类型有：0 - 线性核： vu1 - 多项式核： recofdg )0(2 - RBF 核： )(2vue3 - sigmoid 核： )0tanh(coef-d degree：核函数中的 degree 设置，默认值为 3；-g g ：设置核函数中的 g ，默认值为 1/ k ；-r coef 0：设置核函数中的 coef 0，默认值为 0；-c cost：设置 C - SVC、e - SVR、n - SVR 中从惩罚系数 C，默认值为 1；-n n ：设置 n - SVC、one - class - SVM 与 n - SVR 中参数 n ，默认值 0.5；-p e ：设置 n - SVR 的损失函数中的 e ，默认值为 0.1；-m cachesize：设置 cache 内存大小，以 MB 为单位，默认值为 40；-e e ：设置终止准则中的可容忍偏差，默认值为 0.001；-h shrinking：是否使用启发式，可选值为 0 或 1，默认值为 1；-b 概率估计：是否计算 SVC 或 SVR 的概率估计，可选值 0 或 1，默认 0；武汉理工大学毕业设计（论文）22-wi weight：对各类样本的惩罚系数 C 加权，默认值为 1；-v n：n 折交叉验证模式。其中-g 选项中的 k 是指输入数据中的属性数。操作参数-v 随机地将数据剖分为 n 部分并计算交叉检验准确度和均方根误差。以上这些参数设置可以按照 SVM 的类型和核函数所支持的参数进行任意组合，如果设置的参数在函数或 SVM 类型中没有也不会产生影响，程序不会接受该参数；如果应有的参数设置不正确，参数将采用默认值。training_set_file 是要进行训练的数据集； model_file 是训练结束后产生的模型文件，该参数如果不设置将采用默认的文件名，也可以设置成自己惯用的文件名。3) svmpredict 的用法svmpredict 是根据训练获得的模型，对数据集合进行预测。用法：svmpredict options test_file model_file output_fileoptions（操作参数）：-b probability_estimates：是否需要进行概率估计预测，可选值为 0 或者 1，默认值为 0。model_file 是由 svmtrain 产生的模型文件；test_file 是要进行预测的数据文件；output_file 是 svmpredict 的输出文件，表示预测的结果值。svmpredict 没有其它的选项。4 SVM 技术用于自动图像标注4.1 特征提取模块该模块主要负责对图像数据库中的图像进行特征提取，并对其进行特征归一化处理，然后把图像的特征值输出到相应的文件中，以作为下一个模块的输入。在该模块中，可以进行各个特征的提取形成单个特征向量，还可以对任意两个或多个特征进行组合，形成综合特征向量。本文运用 matlab 软件对图像进行纹理、颜色提取 ，每幅图像纹理特征是 8 维数14,3据，每幅图像的颜色特征为 9 维数据。以其中一幅图来提取颜色特征为例：武汉理工大学毕业设计（论文）23图 4-1 颜色空间 HSV 色调、饱和度和亮度Matlab 软件提取的图像特征数据不能直接被 libsvm 软件包应用，需要先进行数据格式转换。本文采用 FormatDataLibsvm.xls 文件，通过其宏命令进行数据格式转换，由于该文件的运用转换格式会将数据最后一位数据默认为 libsvm 数据格式中的 label，所以在提取特征时可以加入几条命令使数据增加一维，且为整数，作为 label 数。4.2 SVM 分类模块该模块以特征提取模块的输出文件作为输入，可以对支持向量机的各个参数进行选择，包括核函数及其参数，然后用一定量的样本对该学习机进行学习和训练，用测试样本来测试，得到最后的分类结果。4.3 实验结果及分析本文实验所采用的图像来自 Corel 图像库，共 2000 幅 20 大类，每类均为 100 幅。分别为：非洲土著、海滩美景、建筑物、公交车、恐龙、大象、玫瑰花、骏马、山脉、美食、狗、蜥蜴/蛇、人物写真、夕阳美景、跑车、瀑布、家具、轮船、雪景、沙漠美景。类别依次用libsvm 数据格式中 label(019)来表示。图库中的图像均为自然类图像，这些图像背景相似。图库中 20 类图像分别按 9/1 分成训练集和测试集，分别提取它们的图像特征，应用 libsvm 对图像特征数据进行训练测试。本文采用高斯径向核(Gaussian RBF)函数和交叉验证算法进行训练测试，结果如图 4-3 所示。武汉理工大学毕业设计（论文）24图 4-3 训练测试结果图中显示最佳训练参数 c=3