基于Hadoop 的图像存储和检索的研究与实现
2019-10-31徐振涛林清滢
徐振涛，林清滢
（韩山师范学院计算机与信息工程学院，潮州521041）
0 引言
移动互联网的发展和智能手机的普及，使得图像数据开始快速增长，无论是图像存储还是图像处理都将面临着巨大的挑战，然而，如何实现在大规模的图像数据中检索出与目标图像高度相似的图像是一个热门问题。随着云计算模式的普及和发展，各种云计算平台也就相继出现。其中，Hadoop 就是一个开源的云计算平台，它有两个核心子项目HDFS 和MapReduce，主要用于对海量数据的分布式存储和处理，其设计思想来源于Google 的GFS 和MapReduce。
本文首先利用SIFT 算法提取图像特征，获得大量图像特征点。然后利用K-means 算法对图像特征点进行聚类，降低特征点数量，提高图像检索效率。此外，利用TF-IDF 算法对图像聚类中心进行量化，获取聚类中心的TF-IDF 值，优化图像检索结果。最后利用HDFS 对海量图像数据进行分布式存储，利用MapReduce 实现了之前的相关算法。分布式的图像检索方法可以大大减少图像检索系统所耗费的时间，对分布式图像检索的发展有巨大的推动。
1 相关算法
1.1 构建高斯差分金字塔，检查极值点
金字塔是模仿不同尺度的图像，大尺度图像相当于近距离观察实体的图像，比较清晰，显示的是细节信息。小尺度图像相当于远距离观察实体，比较模糊，显示的是轮廓信息。接着利用不同参数的高斯模板对金字塔的每一层图像进行模糊处理，使得金字塔的每一层具有多张高斯图像，金字塔每层的所有图像被称为八度。当前八度的底层图像是前一个八度的倒数第三层图像，且需要对图像进行降采样法。
金字塔层数计算公式如下：
n：金 字 塔 的 层 数；(M,N)：原 图 像 的 尺 寸；t：log2min( m,n)-1 min( m,n )＞1；(m,n)：顶 端 图 像 的尺寸；
二维空间正态分布方程公式如下：
m*n：二维模板大小；(x,y)：模板元素；
尺度空间理论的思想是在视觉信息处理模型中引入一个连续变化的尺度参数，获得不同尺度下的视觉信息，然后综合这些信息深入地挖掘图像本质特征[1]。
尺度计算公式如下：
σ：某八度的某层尺度；σ0：初始尺度；o：第几个八度；s：八度中第几层S：在高斯差分金字塔的八度中只有S 层能求极值点；O：八度的数量；S+3：高斯金字塔八度的层数；
构建高斯金字塔公式如下：
图1 高斯金字塔
L( x,y ,σ)：尺度空间；G( x,y ,σ)：高斯函数；I( x,y )：图像；*：卷积运算；
构建高斯差分金字塔公式如下：
图2 高斯差分金字塔
根据Lowe 论文，像素点要在三维中比较。因此可知，尺度空间理论中S 表示高斯差分金字塔的八度中只有S 层能求极值点，所以高斯差分金字塔的八度有S+2 层，又因为高斯差分金字塔是由高斯金字塔八度相邻层相减得到的，所以高斯金字塔的八度有S+3 层。
图3 像素点在三维中比较
1.2 关键点的精确定位，去除低对比度的点，消除边缘响应
离散空间的极值点不是真正的极值点，如图4所示。
图4 离散空间极值点与连续空间极值点的差别
利用已知离散空间极值点插值得到连续空间极值点的方法叫做子像素插值[2]。为了提高关键点的稳点性，需要对DOG 函数进行曲线拟合，DOG 函数的泰勒展开式[3]：
对D(X)求导，并令其等于0，可得到极值点的偏移量：
边缘图像与二次型函数曲面等高线图像相对应，其中二次型函数的Hessian 矩阵也可以通过对二次型函数进行偏导数得到，我们只需要判断该点Hessian 矩阵的特征值是否相差较大，来判断是否是边缘点。
该点Hessian 矩阵公式如下：
假设α 为较大特征值，β 为较小特征值，令α=rβ。
成立则保留关键点，不成功则剔除。根据Lowe 论文，取r=10。
1.3 特征点方向分配，特征点描述子生成，根据SIFT进行匹配
为了使图像不受旋转变化的影响，采用梯度的公式，计算特征点局部窗口的一个基准方向，局部窗口的半径为3×1.5×σ_oct，公式如下：
利用上述公式计算高斯图像特征点局部窗口内像素的梯度方向和模值，然后采用梯度方向直方图进行统计，根据Lowe 论文，梯度模值m( )x,y 需要按σ=0.5σ_oct 进行高斯加权。在特征点领域梯度信息图像中，纵横线段表示像素点，圆表示高斯加权范围。在梯度方向直方图中，纵坐标表示梯度模值累加，横坐标表示梯度方向，把360 度分为36 个方向，为了简化，笔者只画出8 个方向，实践编程是以36 个方向。梯度方向直方图最高柱表示特征点的主方向，大于最高柱80%的柱表示次方向，一个特征点可以有很多个方向，这样可以提高图像匹配的稳定性。为了使梯度方向直方图的方向角更加准确，需要进行插值拟合。
图5 特征点领域梯度信息和梯度方向直方图
特征点描述子就是一组向量，将高斯图像特征点附近领域划分成4×4 个窗口，计算每个窗口8 个方向的梯度信息，并用梯度方向直方图进行统计，特征点描述子为128 维向量。
SIFT 算法通过构建高斯金字塔，去除了图像尺度变化的影响，通过对特征点方向分配以及生成特征点描述子，去除了图像旋转变化的影响，通过对特征点描述子向量归一化处理，去除了图像光照变化的影响，当使用欧氏距离进行相似度度量时，可去除图像背景混乱和遮挡物的影响，利用一张图像的所有描述子向量与另一张图像的所有描述子向量进行欧氏距离计算，求出最近描述子向量除次近描述子向量的值，当该值小于某个阈值则，则接受这个点。在Lowe 论文中ratio=0.8，然而有人通过大量实验发现，当ratio=0.4 时，特征点匹配精确度最高，当ratio=0.5 时，特征点匹配一般，ratio=0.8 时，特征点匹配数量最多。
欧氏距离：
特征点p 和q 的描述子向量Desp和Desq。
1.4 K-means算法
图6 特征点聚类
（1）从N 个元素选取k 个初始聚类中心,如S1、S2。
（2）计算每个元素到每个聚类中心的欧氏距离，如A、B、C 距离S1 最近，则A、B、C 属于S1 簇集。
（3）求误差平方和，若误差平方和与上次相同，则结束，否则进行（4）。
（4）计算簇集的平均值，得到新的聚类中心。
（4）重复（2）～（4）。
1.5 TF-IDF算法
TF-IDF 算法是一种信息检索和数据挖掘的加权算法，用于评估一个词语在文件集的类别区分能力，通过SIFT 算法提取图像特征和K-means 算法对特征点聚类，获得k 个聚类中心，每个聚类中心可以看作一个词语，所有图像看作文件集，计算词语的TF-IDF 值。
TF（词频）：表示词语在文件中出现的次，需要进行归一化；IDF（逆向文件频率）：表示含该词语的文件数除文件总数，得到的商再取对数。
2 基于Hadoop图像存储和检索
2.1 把大量小文件（图像）合并成大文件上传到HDFS
输入：外部图像数据
处理：把图像转化为＜key,value＞形式，key 是图像名，value 是图像内容，每个＜key,value＞为一行，形成总字符串后存入HDFS 中
输出：一个含义所有图像且以＜key,value＞形式存储的文件，即顺序文件
2.2 利用MapReduce编写框架提取图像特征
IPO 描述
Mapper 类
输入：HDFS 中顺序文件
处理：通过SIFT 算法提取图像特征
中国英语学习者的实验在被试所在中学或大学的教师办公室进行，英语母语者分别在各自所在大学的图书馆中进行，一次仅有一个被试在房间中接受测试。被试首先阅读实验要求，然后开始测试。在电脑的自测步速阅读完成后，被试还要做二语水平测试，并填个人语言背景表。二语水平测试题选自Oxford Proficiency Test，共50道语法选择题，用以检测学生的二语语法水平。所有学生均未在之前做过这一测试。语法选择题每题1分，小于30分被界定为低水平;30～35分为低到中等水平;35分以上为中等以上水平。
输出：＜key,value＞,key 是图像名，value 是多个描述子向量，即特征文件
Reducer 类
无
2.2 利用MapReduce编写框架对特征点进行聚类和聚类中心量化
IPO 描述
Mapper 类
输入：HDFS 中的特征文件
处理：通过K-Means 算法对特征点聚类，再利用TF-IDF 算法计算聚类中心TF 值
输出：＜key,value＞，key 是图像名，value 是多个聚类中心和每个聚类中心的TF 值，即图像总特征文件
Reducer 类
无
2.3 利用MapReduce编写框架实现匹配算法
先通过SIFT 算法提取检索图像的特征，再通过K-means 算法对特征点聚类，然后把检索图像的所有聚类中心存入HDFS 文件中，最后编写MapReduce 程序进行匹配相似图像。
IPO 描述
Mapper 类
输入：HDFS 中图像总特征文件
处理：通过setup 方法获取HDFS 中检索图像的特征文件，利用欧式距离进行计算检索图像与图像总特征文件中图像的匹配率
输出：＜key,value＞，key 是图像名，value 是匹配率
Reducer 类
无
2.4 实验结果
图7 检索结果
图8 普通检索和Hadoop检索效率对比
图9 普通检索和Hadoop检索准确率
3 结语
在图像检索方面，本文首先利用SIFT 算法提取图像特征，获得大量图像特征点。然后利用K-means 算法对图像特征点进行聚类，降低特征点数量，提高图像检索效率。此外，利用TF-IDF 算法对图像聚类中心进行量化，获取聚类中心的TF-IDF 值，优化图像检索结果。在基于Hadoop 的图像检索方面，先采用了HDFS对图像文件进行分布式存储，然后基于MapReduce 对图像进行分布式计算处理。
