基于spark的海量图像检索系统设计.pdf

microcomputer applications vol. 31, no.11, 2015 基金项目 微型电脑应用 2015 年第 31 卷第 11 期 11 文章编号：1007-757x(2015)11-0011-03 基于 spark 的海量图像检索系统设计 王迅，冯瑞 摘要：随着互联网，多媒体技术快速发展，互联网上的图像数量飞速增长，如何快速、有效地在海量的图像数据中找到用 户需要的图像成为研究的热点。传统的图像检索系统基于单节点的架构，在处理海量图像数据时存在速度慢、并行性差、 内存不足等问题。提出了一种基于 spark 的海量图像检索方法,将图像检索技术与 spark 计算框架相结合。图像集分布式 地存储在 hdfs 中，能够进行分布式地特征提取、模型训练、在线检索。与单节点检索系统相比,该方法在处理大数据图 像检索时，具有速度快，可扩展性强等优点，能够处理单机无法处理的海量图像数据。在 holiday 数据集上的实验结果表 明，该方法有效地提高了算法的运行速度。 关键词：图像检索；海量数据；spark；hdfs 中图分类号：g642.423 文献标志码：b 0 引言 基于内容的图像检索是指根据查询图像的视觉特征， 在 图像库中找出与之相似的图像。 随着计算机科学技术和数字 图像采集技术的迅速发展以及互联网的普及应用， 每天从各 行各业都产生出大量的多媒体数据， 这些数据大部分是以图 片和视频等形式表现的， 传统基于单节点架构的图像检索系 统存在检索速度慢、并发性差,实时性和稳定性无法保障等 问题，已经不能满足人们对于检索性能的要求。因此分布式 地图像处理、快速及时地图像检索方法成为了研究热门。 本文提出了一种基于 spark1的图像检索方法，能够处 理海量图像上的图像检索问题。 该系统主要由离线特征提取， 视觉词袋模型2训练，在线图像检索 3 部分构成。原始图像 集和提取的 sift3特征都存储在 hadoop 文件系统 hdfs4 上。集群能够随图像数据的增大，动态地增加集群节点数。 1 基于 bovw 的图像检索 视觉词袋模型（bag-of-visual-word，bovw）是将文本 检索中的 bag-of-words 模型应用于图像检索。 和文本检索相 似，为了表示一幅图像，我们可以将图像看作是若干个“视 觉单词”组成的文档，视觉单词相互之间没有顺序。基于视 觉词袋模型的图像检索方法由 sivic 和 zisserman 等人于 03 年首次提出。 bovw 是一种无监督学习， 可以高效的对未经 过标注的的图像数据集建立索引。 基于视觉词袋模型的图像 检索方法主要有如下步骤构成： （1）特征提取 将图像集中的图像进行特征提取，基于 bovw 的图像 检索一般使用图像的 sift 特征。 （2）视觉词袋模型训练 利用聚类算法对提取的特征进行训练获得视觉词袋模 型。 （3）构建视觉词频向量 对于图像的每一个特征， 通过最近邻的方法在视觉词典 中找到对应的视觉单词。记录每个视觉单词出现的次数,这 样一张图像就可以用视觉单词的视觉词频向量 （term vector） 表示。 （4）相似图像检索 根据视觉词袋模型，计算出图像库中每张图像的视觉 词频向量。输入查询图像，提取图像特征，根据训练出的视 觉词袋模型计算出查询图像的视觉词频向量， 然后和图像库 中每张图像对应的视觉词频向量计算相似度， 相似度靠前的 图像即为相似图像。 1.1 特征提取 本文采用 sift 特征作为图像的基本特征。sift 特征提 取方法是一种提取图像局部特征的算法， 在尺度空间寻找极 值点，提取位置，尺度，旋转不变量。由于 sift 特征具有 尺度和旋转不变性，对视角变化、仿射变换、噪声也保持一 定程度的稳定性。因此，sift 是基于视觉词袋模型的图像 检索方法中中最常用的特征。sift 征提取算法主要步骤如 下： （1）检测关键点 首先，构建图像的尺度空间，然后，通过关键点检测算 法检测图像的关键点，并分配关键点的方向。得到关键点信 息：位置、尺度、方向，如图 1 所示： 图 1 图 1 提取的关键点信息如图 2 所示： 图 2 图中圆心表示关键点的坐标位置，半径表示尺度，角度 表示方向。 （2）提取描述子 根据关键点及关键点周围的像素点梯度信息提取图像 的 sift 描述子，通常描述子大小为 128 维，关键点的个数 基金项目：国家科技支撑计划（2013bah09f01） ；上海市科委科技创新行动计划 作者简介：王 讯（1990-） ，男，复旦大学，计算机科学技术学院，上海市视频技术与系统工程研究中心，硕士研究生，研究方向：机器学习与模 式识别，上海，201203 冯 瑞（1971-） ，男，复旦大学，计算机科学技术学院，上海市视频技术与系统工程研究中心，副教授，研究方向：计算机图像识别与 处理，上海，201203 microcomputer applications vol. 31, no.11, 2015 基金项目 微型电脑应用 2015 年第 31 卷第 11 期 12 由图像大小和图像梯度分布所决定。 从图1中提取的sift特征如下所示， 关键点个数： 2367， sift 描述子维度：128 传统的特征提取是在单机下运行的， 无法快速处理海量 图像数据的情况。在单台机器无法存储海量图像时，需要将 图像分批地存放在多台机器上， 在进行特征提取时需要在每 一台机器上运行特征提取算法，效率低下。这时需要将图像 数据集存储在分布式文件系统中，如 andrew 系统，kass 系统，hdfs 等。由于 hdfs 的易用开源，且 spark 能很好 地兼容 hdfs 的读取， 本文采用spark来进行图像特征提取， 将提取好的特征以二进制形式保存在 hdsf 中。 1.2 视觉词袋模型 和文本检索中的分词一样， 在多张图像之间虽然存在差 异，但是在这些差异中存在相同的地方。如在人脸检测中， 虽然不同的人脸在视觉上有差别，但眼睛，嘴，鼻子等一些 比较细小的部位却是相似的，从而可以将眼睛，嘴，鼻子等 这些部位作为人脸的基本特征，从而用来检测人脸。同样， 如果我们把同一类图像之间共同的特征提取出来， 就可以作 为识别这一类目标的视觉单词，从而可以区分相似图像。这 是视觉词袋模型用于图像检索的基本思想。 对于提取的 sift 特征，可以利用 k-means 聚类算法构 建视觉词典。将图像集提取的所有特征进行聚成 k 类，每 一个类中心代表一个视觉单词， 这样就建立了一个视觉词典。 k-means 聚类算法是一种无监督的学习算法， 可以用于训练 未标注的图像数据集。 k-means 是一种基于样本间相似性度 量的间接聚类方法，算法以 k 为参数， 把 n 个对象分为 k 个簇，目的是使簇内具有较高的相似度，而簇间具有较低的 相似度。利用 k-means 算法合并词义相近的视觉单词，过 程如图 3 所示： 图 3 k-means 过程 k-means 将 sift 特征聚成 k 类后，每一个类的中心点 向量为一个视觉单词， 这些视觉单词被看作是组成任意一幅 图像的基本单位，k 个视觉单词构成一个视觉词典。可视化 后的视觉词典如图 4 所示： 图 4 视觉词典可视化 有了视觉词典后， 可以用视觉词典中的单词表示一张图 像。对于图像中提取的每一个 sift 特征，都可以通过最近 邻的方法在视觉词典中找到与之最相似的单词， 即该特征与 该视觉单词所表示的特征最相近， 我们可以认为该视觉单词 在图像中出现了一次，对于一张图像的所有 sift 特征，通 过统计视觉词典中每个单词在图像中出现的次数， 就可以将 图像量化为成为一个 k 维的视觉单词直方图，即视觉词频 向量，如图 5 所示： 图 5 词频直方图 右上角为一张需要量化的图像， 词频直方图的高度代表 视觉单词出现在该图像中的次数。 对于一个图像数据集， 视觉词袋模型的建立的主要流程 如图 6 所示： 图 6 视觉词袋模型建立 1.3 索引与检索 根据视觉词袋模型， 计算出图像库中每张图像的视觉词 频向量。输入查询图像，提取图像特征，根据训练出的视觉 词袋模型计算出查询图像的视觉词频向量， 然后和图像库中 每张图像对应的词频向量计算相似度， 相似度靠前的图像即 为相似图像，如图 7 所示： 图 7 相似图像检索 图像之间的相似度可以用图像词频向量之间的欧式距 离度量。对于海量数据集，并且词频向量非常稀疏的情况， 可以建立视觉单词-图像倒排索引机制以加快检索的速度。 2 spark 大数据计算平台 传统图像检索系统是在单机上运行的， 在海量图像情况 下，无法有效地训练视觉词袋模型。本文将 spark 计算框架 与图像检索技术相结合，该方法在处理大数据图像检索时, 具有速度快，可扩展性强等优点，能有效对海量图像进行视 觉词袋模型训练。 spark 诞生于伯克利大学 amplab，是现今大数据领域 microcomputer applications vol. 31, no.11, 2015 基金项目 微型电脑应用 2015 年第 31 卷第 11 期 13 里最为活跃，最为热门，最为高效的大数据通用计算平台。 随着大数据时代的到来， 用户对于大数据处理系统的要求也 越来越高。而 spark 大数据处理框架因为其出色的性能，越 来越受到人们的关注。 spark 是基于 mapreduce 思想实现的 一个分布式计算框架，spark 继承了 hadoop 的 mapreduce 的优点，但是比 hadoop 更为高效。spark 开创性地提出了 抽象弹性数据集 rdd 的概念，使得 spark 在处理迭代式， 交互式，流式数据时非常高效。 大数据计算中计算过程通常分为多个阶段，在 mapreduce 中， 不同计算阶段之间重用数据， 需要将上一个 阶段的输出数据保存到外部存储系统中， 例如分布式文件系 统，这就导致了大量的数据复制、磁盘 i/o、序列化，反序 列化等开销，这些甚至会占据整个应用执行的大部分时间。 而 spark 基于内存的计算框架在内存大小足够的情况下，不 同计算阶段之间只需要读写内存即可，无需读写磁盘，在磁 盘空间不足情况下，也可以像 hadoop 一样使用磁盘作为中 间结果存储的媒介。对于迭代式的算法，spark 相比 hadoop 能提高 100 倍的速度。 spark 计算框架使包括 sparksq、 sparkstreaming、 mllib、 graphx 子框架，子框架和 spark 库之间可以无缝地共享数 据和操作，解决了大数据中的 batch processing、streaming processing、ad-hoc query 三大核心问题。spark 使用 scala 语言编写，运行在 jvm 上，能够很好地兼容其他基于 java 语言的大数据系统， 如本文中使用的hadoop文件系统hdfs。 spark 提供的 api 相比 hadoop 更加丰富， spark 程序的编写 也更加简单易用， spark 集群的配置相比 hadoop 更加简单， 这使得 spark 成为了大数据处理首选的计算平台，也是本文 将 spark 应用在海量图像检索系统中的原因。 spark 计算框架如图 8 所示： 图 8 spark 计算框架 3 实验结果及分析 本文提出的计算平台在实验集群上实现。实验集群由 1 台主节点，4 台从节点组成，均为物理机，操作系统皆使用 centos6.5。 集群使用的 hadoop 版本 hadoop-2.4， spark 版 本为 spark1.3.1。 主节点在 hadoop 中充当 namenode，在 spark 中充当 master。 从节点在 hadoop 中充当 datanode，在 spark 中充当 worker，如表 1 所示： 表 1 集群配置 本文使用 k-means 聚类算法训练视觉词袋模型。由于 k-means 是一种迭代式的计算， 用 hadoop 的 mapreduce 框 架计算， 每次需要将中间的 map 结果写到 hdfs， 然后再从 hdfs 读取数据，进行下一次 map。但不同于 mapreduce 的是 job 中间输出和结果可以保存在内存中， 从而不再需要 读写 hdfs，从而大大减少了模型的训练时间。 本文在 holiday5数据集上实验，提取后的 sift 特征集 大小为 5m，在视觉词典大小分别为 100、200、300 的情况 下，通过改变集群 worker 节点数，视觉词袋模型训练的时 间测试结果如图 9 所示： 图 9 视觉词袋模型训练的时间测试结果 通过实验表明， 单机情况无法有效训练视觉词袋模型在 holiday 数据集上训练大小为 300 的视觉词袋模型需要 21 小 时。而在 4 个 worker 节点上训练视觉词典模型只需要 5.2 小时， 大大减少了模型训练时间， 单位为小时， 如表 2 所示： 表 2 1 2 3 4 100 6.9 3.2 2.2 1.7 200 14.0 6.3 4.3 3.4 300 21.0 9.7 6.4 5.2 表 2 给出了不同词典大小和不同节点个数下视觉词袋 模型的具体时间，与图 9 对应。 加速比是指同一个任务在单机系统和分布式系统中运 行消耗的时间的比率， 用来衡量分布式系统或的性能和效果， 加速比的计算公式为 sp=t1/tp，sp 是加速比，t1 是单节点 下算法的运行时间， tp 是在 p 个节点下的运行时间。 当 sp=p 时，是理想加速比。 表 2 中的测试数据对应的加速比，如图 10 所示： 图 10 加速比 从图 10 中可以看出， spark 集群在做视觉词袋模型训练 时，因为算法的运行时间远大于网络传输和磁盘 io 时间， 加速比是随着节点个数的增加而近似线性增长的， 这证明算 法的性能能够随着节点数的增加而成线性提升， 具有良好的 可扩展性。 通过spark集群可以高效地训练海量的图像数据， 并且可以动态的增加集群节点，以适应图像数据集的增加， （下接第 17 页） 节点 角色 cpu 内存 master master/namenode 16 核 24g slave1 worker1/datanode1 4 核 8g slave2 worker2/datanode2 4 核 8g slave3 worker3/datanode3 4 核 8g slave4 worker4/datanode4 4 核 8g 节点数 时 间 (h)词典大小 microcomputer applications vol. 31, no.11, 2015 基金项目 微型电脑应用 2015 年第 31 卷第 11 期 17 项，其中 2013 年“挑战杯”全国大学生课外学术科技 作品竞赛二等奖 1 项、三等奖 1 项、 “科教杯”学术论文大 赛国家级一等奖 1 项，全国“第九届青少年科技创新奖”1 项、 中国计算机学会百名大学生奖 2 项； 学生发表专业论文 10 余篇，其中 ei 检索 5 篇。 4 总结 在“数据结构与算法”课程不断的教学改革与实践中， 强化实践教学活动中的“教、学、做”合一，教师的“教” 是前提、学生的“学”是主体、学生的“做”是实践，让学 生在学习中感受到愉快活泼的情绪， 抒发自己的情感，发挥 潜能与创造力。通过师师、生师、生生的协作，突出以学生 发展为中心， 让学生真正 “动” 起来， 从而创设和谐、 生动、 愉快的课堂教学环境。 参考文献 1 刘晓静,黄维通,王晓英.西部地区 cdio 理念下的数 据 结 构 与 算 法 课 程 建 设 j. 计 算 机 教 育,2013,17:107-111. 2 刘晓静,王晓英,张玉安等.以创新人才培养为目标的 数据结构实验改革j.实验技术与管理,2014,31(11): 184-187. 3 李晓鸿,骆嘉伟,季洁.“数据结构与算法分析”研究 型 实 践 教 学 的 探 索 j. 实 验 室 研 究 与 探 索,31(1):121-125. 4 刘越畅,钟秀玉,钟治初等.数据结构课程工程化实验 教 学 的 探 索 和 实 践 j. 实 验 室 研 究 与 探 索,2012,31(8):339 -341. 5 xiaojing liu,weitong huang,xiaoying wang,xiaoqing wang. application research of blending learning in course studyj. advances in intelligent and soft computing,2012,146:337-342. 6 xiaojing liu,xiaoying wang,rui wang.application of blended learning in data structures and algorithms course teachingj.advances in intelligent systems research,2013:1070-1074. 7 熊岳山,钱程东,徐凯.数据结构课程教学中的数据抽 象 能 力 培 养 体 会 j. 计 算 机 工 程 与 科 学,36(a1):27-30. 8 李晓鸿,骆嘉伟,颜华,等.研究型大学创新性“数据结 构 与 算 法 分 析 ” 课 程 建 设 j. 计 算 机 教 育,2011(8):34-38. 9 张同珍.数据结构课程实验教学探索与实践j.实验 室研究与探索,2011,30(9):293-295. 10 刘晓静,王晓英,薛媛媛,等.让趣味教学进驻数据结构 与算法课堂j.青海大学学报,2011,29(5):95-97. 11 谭定英,陈平平,刘慧玲.以问题为中心的案例教学法 在数据结构与算法课程中的应用j.计算机教 育,2013,12: 50-53. 12 刘晓静,王晓英.基于项目导向的数据结构与算法课 程 教 学 研 究 与 实 践 j. 微 型 电 脑 应 用,2014,30(9):48-50. 13 唐艳琴,陈卫卫,施蕾.“数据结构”小班化教学探讨 j.计算机工程与科学,2014,36(a1):244-247. 14 顾佩华,沈民奋,李升平.从 cdio 到 eip-cdio汕头 大学工程教育与才培养模式探索j.高等工程教育 研究,2008(1):12-20 15 王晓英,靳力,王晓青等.基于序列匹配的作业相似度 检测系统j.计算机工程,2012,38(24):53-61. （收稿日期：2015.08.18） （上接第 13 页） 具可扩展性，高效性的特点。理论上可以处理任意大小的数 据集。 训练好视觉词袋模型后，在 holiday 数据集上 0.1 秒内 即可查询到相似图像。查询结果如图 11 所示： （a）查询图像 （b）相似图像 图 11 查询结果 4 总结 本论文提出了一种基于 spark 的海量图像检索系统，使 用 hdfs 作为图像和特征的存储系统， 用 spark 计算框架进 行分布式计算。 实验表明本系统与传统单节点图像检索系统 相比，具有快速，高效，可扩展性强等优点，适合在大规模 图像数据集上使用。 参考文献 1 zaharia. m, chowdhury .m, franklin .m. j, shenker .s, and i. stoica, spark: cluster computing with working sets. the 2nd usenix conference on hot topics in cloud computing, 2010:10c. 2 sivic j,zisserman a.video google: a text retrieval approach to object matching in videosc. nice, france: iccv, 2003 3 davidg.lowe.distinctive image features from scale-invariant keypointsj. international journal of computer vision 2004, 60(2): 91110. 4 borthakur .d, “the hadoop distributed file system: architecture and design,”c hadoop project website, 2007,11:21. 5 herve jegou, matthijs douze and cordelia schmid. hamming embedding and weak geometry consistency for large scale image searchc