最大间隔方法及其在图像检索中的应用

论文摘要

随着图像获取、传输、存储等技术的进步,各种数字图像资源变得越来越丰富。为了对图像资源进行有效的利用,首先要求能够快速准确地从规模日益庞大的图像数据库中查找到需要的图像。图像检索是一个综合性的问题,为建立一个成功的图像检索系统,需要首先解决许多相关的基本问题,如图像相似性的度量、图像相关排序、图像分类以及聚类等。近年来,机器学习理论与算法的长足发展为各种实际问题的解决提供了有力的工具。在众多的机器学习算法中,支持向量机模型因在理论上具有坚实的基础并在实践中表现出优异的性能而受到广泛的关注。本文在支持向量机模型和间隔最大化准则的基础上,提出了一系列最大间隔算法,对图像检索中相关的问题展开了研究。本论文首先研究了当用局部特征表示图像时,如何通过局部特征的匹配,度量图像之间的相似度,并在此基础上用支持向量机实现图像分类。文中提出了一种新颖的双空间金字塔匹配算法,能够快速地计算两个特征集合间的隐式匹配关系。该算法首先对特征空间和图像空间分别进行多分辨率的划分,然后将一幅图像对应的局部特征的集合映射成建立在双空间中的多分辨率直方图,最后通过直方图的加权相交实现两个特征集合的快速匹配。由于充分利用了局部特征在两个空间中的分布特点,因此相比于只在单空间中进行匹配的算法,双空间金字塔匹配能够更准确地反映局部特征集合之间的关系。同时,基于双空间金字塔匹配的相似性度量满足半正定条件,因此能够作为支持向量机的核函数,用于对图像进行分类。在ImageCLEF医学图像分类任务上,基于双空间金字塔匹配的支持向量机取得了比2005年公布的最佳参赛结果更小的分类错误率。本论文然后研究了在基于关键词的图像检索中,如何有效地将图像按照与关键词的相关程度的大小进行排序。与传统工作将检索问题建模成二分类问题并优化分类性能不同,本文将问题建模成一个排序学习问题,并直接优化与排序性能相关的目标函数。本文基于支持向量机模型和间隔最大化准则提出了一种新颖的多示例排序学习框架。该框架采用基于区域的图像表示,并利用一组具有优先关系的图像对学习图像排序模型。利用学到的排序模型,能够计算新图像的排序分数,并按排序分数的大小对图像进行排序。在这个框架下,基于对区域和图像排序分数关系的不同假设,本文分别提出了三种具体的多示例排序学习算法。对从Flickr上搜集的图像进行的实验表明,多示例排序学习算法能够极大地提高图像的排序质量。这项工作是最早将排序学习与多示例学习结合进行考虑的工作。本论文还研究了基于支持向量机模型和间隔最大化原理的聚类算法,由此可以对图像进行聚类。这种最大间隔聚类算法通过寻找使类间间隔最大的分类面,实现对数据集的划分。与传统的聚类算法相比,最大间隔聚类具有良好的推广性能,因此在大规模的聚类问题中能够发挥重要的作用。本文在分析现有最大间隔聚类算法不足的基础上,提出了基于成对约束的半监督最大间隔聚类算法。该算法通过在最大间隔聚类的目标函数中添加针对成对约束的损失项,使得求得的聚类分界面尽量满足给定的约束条件,从而提高最大间隔聚类的性能。本文不仅在标准支持向量机模型的基础上讨论了两类情况下的聚类,还从多类支持向量机出发,详细讨论了多类情况下基于成对约束的最大间隔聚类。对于聚类问题所对应的非凸优化问题,本文提出了基于CCCP过程的迭代解法来进行高效地求解。在多类情况下为了保证聚类速度,还为CCCP迭代中子问题的求解提出了基于割平面法的快速算法。对标准的图像数据集进行聚类的结果表明,成对约束的引入,能有效地弥补现有最大间隔聚类算法的不足,并极大地提高其聚类准确性。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第1章 绪论
• 1.1 研究背景
• 1.1.1 图像检索及相关问题
• 1.1.2 支持向量机与最大间隔方法
• 1.2 论文的主要工作
• 1.3 论文的组织结构
• 第2章 支持向量机与最大间隔方法
• 2.1 标准支持向量机模型
• 2.1.1 线性可分情况与最优分类超平面
• 2.1.2 线性不可分情况
• 2.1.3 非线性情况
• 2.1.4 对偶问题
• 2.2 支持向量机的特点与研究现状
• 2.2.1 支持向量机的特点及优势
• 2.2.2 支持向量机的研究现状
• 2.3 其他最大间隔方法
• 2.3.1 结构支持向量机
• 2.3.2 排序支持向量机
• 2.3.3 最大间隔聚类
• 2.4 本章小结
• 第3章 双空间金字塔匹配算法
• 3.1 研究背景
• 3.1.1 局部特征表示
• 3.1.2 基于局部特征表示的相似性度量与学习算法
• 3.1.3 金字塔匹配算法
• 3.2 双空间金字塔匹配
• 3.2.1 部分匹配
• 3.2.2 特征空间金子塔匹配
• 3.2.3 双空间金字塔匹配
• 3.3 实验与结果分析
• 3.3.1 ImageCLEF医学图像分类任务
• 3.3.2 实验设置与结果分析
• 3.4 本章小结
• 第4章 多示例排序学习算法
• 4.1 引言
• 4.2 排序学习与多示例学习
• 4.2.1 排序学习与相关工作
• 4.2.2 多示例学习与相关工作
• 4.3 基于最大间隔的多示例排序学习
• 4.3.1 Ranking SVM算法
• 4.3.2 多示例排序算法框架
• 4.3.3 Average方法
• 4.3.4 Max方法
• 4.3.5 Softmax方法
• 4.4 实验与结果分析
• 4.4.1 实验数据集
• 4.4.2 评价准则
• 4.4.3 实验设置
• 4.4.4 实验结果
• 4.5 本章小结
• 第5章 基于最大间隔准则的聚类算法
• 5.1 引言
• 5.2 研究背景
• 5.2.1 最大间隔聚类
• 5.2.2 iterSVR算法
• 5.2.3 iterSVR算法的不足
• 5.2.4 基于成对约束的半监督聚类
• 5.3 半监督最大间隔聚类
• 5.4 多类半监督最大间隔聚类
• 5.4.1 多类最大间隔聚类
• 5.4.2 基于成对约束的多类最大间隔聚类
• 5.4.3 Cutting-Plane算法
• 5.5 实验与结果分析
• 5.5.1 实验数据与评价准则
• 5.5.2 初始化敏感性分析
• 5.5.3 聚类准确性比较
• 5.5.4 推广性能分析
• 5.6 本章小结
• 第6章 总结与展望
• 6.1 论文总结
• 6.2 进一步的研究与展望
• 参考文献
• 附录 定理证明
• 致谢
• 在读期间发表的学术论文与取得的研究成果