摘 要

随着互联网时代的发展，图像作为一种重要的信息载体，在各个领域都充当着愈发重要的角色。而图像检索可以有效的管理基于图像的信息库，其中，基于图像内容的检索是相对成熟的领域，在各界都有着广泛的应用。而在现有的图像检索算法中，大多都是在离线的情况下进行的，即对目标数据集中的图像进行批量预处理，再对特征进行学习与检索。即当下图像检索数据库的建立，往往是在假设所有样本都已经获取的情况下。然而，随着近年来互联网飞速发展，如果每个样本都要以传统的离线方式学习图像特征，代价将会非常高。

因此，本文致力于研究出一种在线学习算法，利用在线学习技术从数据中挖掘重要特征，通过学习构建一个有效的预测模型，使其能对新接受的数据进行准确的预测。通过这种算法，图像检索技术可以摆脱在离线情况下一次性批处理所有样本的限制，对于流数据的到来也可以及时处理，还可以大幅度的提高训练效率，减少储存空间。本文的设计思路大致为：对于每一个到来的流数据块，都采用FD等方法，生成一个比数据块尺寸小很多，但保留了数据块主要特征的草图，用草图来代替原数据。再用Anchor方法处理草图中每一个样本数据的特征向量，将每一个数据与锚的相似度值作为数据的特征向量代入计算。在生成草图的过程中，流数据的均值会不断发生改变，使得草图的计算过程复杂且困难。为了减小时间和空间上的复杂度，对于这类问题，我们采取零均值的方式解决。最后采用SVD分解方法，对哈希函数进行学习和更新。

通过这种方法，可以得到一个时间和空间复杂度都得到很大提升的在线算法，更加适应大数据时代中图像检索的节奏。且这种算法运行结果较准确，算法稳定性较高，提高了运行速度，减少了内存的占用。

关键词：图像检索；在线学习；哈希；草图；锚

Abstract

With the development of the Internet era, as an important information carrier, images have played an increasingly important role in various fields. The image retrieval can effectively manage the image-based information database. Among them, the content based image retrieval is a relatively mature method and is widely used in various fields. However, most of the existing image retrieval algorithms are performed offline, that is, batch preprocessing of the images in the target data set, and then learning and retrieving image features. And the establishment of the current image retrieval database is often under the assumption that all samples have been obtained. However, with the rapid development of the Internet in recent years, if each sample has to learn image features in a traditional offline way, the cost will be very high.

Therefore, this article is devoted to researching an online learning algorithm, using online learning technology to mine important features from the data, and constructing an effective prediction model through learning, so that it can accurately predict the newly accepted data. Through our algorithm, the image retrieval technology can get rid of the limitation of batch processing all samples at once in offline situations, and can also process the arrival of streaming data in time, which can greatly improve training efficiency and reduce storage space. The design idea is roughly as follows: First, for each incoming stream data block, methods such as FD are used to generate a sketch that is much smaller than the data block size, but retains the main features of the data block, and uses the sketch to replace the original data. Then use the Anchor method to process the feature vector of each sample data in the sketch, and substitute the similarity value of each data and the anchor as the feature vector of the data for calculation. In the process of generating sketches, the mean value of streaming data will continue to change, making the calculation process of sketches complicated and difficult. In order to reduce the complexity in time and space, for this type of problem, we adopt the method of zero mean. Finally, the SVD decomposition method is used to learn and update the hash function.

Through this method, an online algorithm with greatly improved time and space complexity can be obtained, which is more suitable for image retrieval in the era of big data. Moreover, the running result of this algorithm is more accurate, the stability of the algorithm is higher, the running speed is improved, and the memory occupation is reduced.

Key Words：Image retrieval；Online learning；Hash；Sketch；Anchor

目 录

第1章 绪论 1

1.1 研究背景与现状 1

1.2 本文结构 2

第2章 相关工作 3

2.1 哈希 3

2.2 在线学习方法 3

2.3 在线哈希 4

第3章 目标方法 6

3.1 哈希函数 6

3.2 草图生成 7

3.2.1 Anchor特征向量处理 7

3.2.2 零均值处理 8

3.3 在线哈希学习 9

3.4复杂度分析 10

第4章 实验结果与分析 12

4.1 实验环境 12

4.2 数据集 12

4.3 实验结果分析 13

4.3.1 平均精度与数据集大小 13

4.3.2 平均精度与哈希码位数 15

第5章 总结与展望 17

5.1 本文总结 17

5.2 未来展望 17

参考文献 18

致谢 21

第1章 绪论

1.1研究背景与现状

现在普遍应用的图像检索方法，是在假设训练样本集及所有特征信息都已经预先获取的情况下，用离线操作对目标数据集中的图像进行批量预处理的。批量解析提取局部特征描述，具体方法通常是对这些特征描述进行聚类，聚类后得到的质心为聚类单词，进而建立当前数据集的视觉词库。这种操作是离线的在整个检索系统生命周期开始阶段实施，一般情况仅执行一次，是针对目标检索文本数据集进行的非频繁性操作。而随着信息技术的迅速发展，如今的图像大多呈现高维度，数据海量，更新速度快的特征，上述假设自然是不成立的，这种方法是不够完善的。因此，更先进、更适应这个时代的方法是很有必要的。

所以在此基础上，越来越多的研究集中用在线学习的方案代替线下参数学习，以便适应大流量、大数据的图像库。在线学习算法的本质是利用在线学习技术从数据中挖掘出重要特征，通过学习构建一个有效预测模型，使其能对新接受的数据进行较为准确的预测。近年来涌现出多种在线学习算法，它们虽然表现形式和具体方法各不相同，但都遵循统一的算法框架，即对于某一线性二分类问题，我们建立一个适当的预测模型，根据“赏罚判断”思想，对新样本进行预测，“奖励”分类正确的模型，“惩罚”分类错误的结果，进而对模型进行适当的修改。