一种基于词汇树的鞋印图像可伸缩检索方法

2018-12-26姜乐怡徐晨苗王富平

西安邮电大学学报 2018年5期

刘伟, 姜乐怡, 徐晨苗, 王富平, 刘颖

(1. 电子信息现场勘验应用技术公安部重点实验室, 陕西西安 710121;2. 陕西省无线通信与信息处理技术国际合作研究中心, 陕西西安 710121;3. 西安邮电大学计算机学院, 陕西西安 710121; 4. 西安邮电大学通信与信息工程学院, 陕西西安 710121)

鞋印是案发现场常见的一种物证痕迹，在案件侦破过程中发挥着重要作用。对案发现场发现的鞋印图像进行查询比对在为公安机关缩小侦查范围、提供破案线索、串并案分析以及提供诉讼证据等方面发挥着重要作用。

早期的鞋印图像的检索主要采用了基于文本的人工标注的方式，为了克服在基于文本的图像检索中人工标注的低效性、主观性和工作量大等弊端，基于内容的图像检索(content-based image retrieval，CBIR)方法得到了广泛的研究与应用[1-3]。CBIR中的典型方法是按例查询(query by example，QBE)，即通过计算查询图像的特征并与图像库对应的特征库进行匹配来寻找与查询图像在内容上最“相似”的图像。例如文[4]采用了一种基于纹理与形状特征融合的检索算法，使用街区距离作为相似性度量对刑侦图像进行检索；文[5]提出了一个完整的鞋印图像匹配框架，设计了傅里叶功率谱密度函数用于校正输入的倾斜鞋印图像，校正后的图像通过计算其相关度来确定它们之间的相似性以实现匹配。由于刑事勘验中采集的鞋印图像具有残缺不全且含有噪声的特点，QBE框架下的图像特征提取算法在刑侦图像检索中效果并不理想[6]。

一些研究者采用了局部特征如SIFT算子[7]来进行图像检索。局部特征算子能更好地描述图像内容。例如文[8]采用SIFT特征用于鞋印图像识别与检索；文[9]使用3个鞋印图像数据库，评估了几种鞋印图像识别算法的性能，认为基于图像局部描述子的算法性能较好；文[10]提出了2种描述图像局部特征的算子并用于鞋印图像检索；文[11]用SIFT特征描述图像内容，用随机抽样一致算法进行图像的匹配。基于图像局部特征的方法在部分鞋印图像检索中取得了很好的结果，但是已有的文献均未研究当鞋印图像数据库的容量动态变化时的检索性能。

随着图像数据库的扩大，词汇树在图像检索中得到了广泛的应用。词汇树的结构特点是将海量的鞋印图像数据量化为有限叶子节点上的词频向量，每个词频向量取决于词汇树的深度和聚类中心的个数。在鞋印图像检索阶段，只需要将查询图像的词频向量与叶子节点上的词频向量进行比较就可以快速得出检索结果。正是因为具有如此的特点，适用于海量数据检索[12]。

为了在海量动态变化的鞋印图像数据库中提高检索精度，降低检索时间，本文拟提出一种基于词汇树的鞋印图像可伸缩检索方法。该方法首先提取鞋印图像的SIFT局部特征，采用层次性聚类方法生成词汇树；然后，基于词汇树计算查询图像和数据库图像之间的相似性以得到检索结果。最后拟在鞋印图像数据库上的验证本文所提方法的有效性。

1 算法设计

1.1 算法原理

算法原理如图1所示。

图1 算法原理

如图1所示，首先计算鞋印数据库图像的SIFT特征，并采用层次型K均值聚类算法对所有图像的特征进行聚类以构建词汇树，并生成图像对应的文档向量。文档向量记录着该图像在词汇树节点上的词频向量。其次，查询时计算查询图像的SIFT特征，根据词汇树中的聚类中心与查询图像所有特征分量之间的距离得到查询图像的文档向量。最后，计算查询图像和数据库图像文档向量之间的余弦距离以得到检索结果。

1.2 鞋印的特征提取

SIFT算子[7]可以有效检测鞋印图像的局部特征，它通过对图像尺度的特征选择，建立图像的多尺度空间；在不同尺度下检测到相同的特征点，确定特征的尺度和位置；把对比度较低的点和边缘响应点删除，以提取图像的旋转不变特征描述符。

SIFT算法主要包含4个步骤。

步骤1在鞋印图像中建立空间尺度找到特征选点。图像的尺度空间

L(x,y,σ)=G(x,y,σ)I(x,y)。

其中，(x,y)为图像I的空间坐标，σ是尺度空间因子，G(x,y,σ)表示可变尺度高斯函数。

步骤2通过包含常数因子k的高斯尺度差分空间

D(x,y)=L(x,y,kσ)-L(x,y,σ)

进行曲线拟合，寻找极值点，确定特征点和关键点，删除边缘响应和不稳定点。

步骤3确定特征点的幅度和方向。对于每个图像样本中的像素(x,y)，计算其梯度幅度m(x,y)和方向θ(x,y)，其中

步骤4提取特征描述符。

使用SIFT算子提取鞋印图像局部特征，如图2所示。

图2 鞋印图像的SIFT特征提取

1.3 词汇树的构造

词汇树是实现鞋印图像可伸缩检索的关键结构，可用于物体识别[12]。使用该方法进行鞋印图像可实现伸缩检索。词汇树构造算法如下。

输入鞋印图像数据库

输出构建的词汇树

(1) 计算鞋印图像数据库中每一幅图像的SIFT特征，全部特征数据组成矩阵X；

(2) 对X进行层次聚类。先对X进行一次K均值聚类，得到k个聚类中心和聚类簇；然后对聚类后的每一簇依次进行K均值聚类，直至达到指定词汇树的深度，完成词汇树构建。在完成每一次聚类后，需要计算数据库图像在每个簇中的词频向量，该词频向量用于图像检索的相似性度量。

上述算法中的聚类中心即为视觉词(visual word)，是词汇树上的一个节点。每个节点对应有一个倒排文件。该文件记录数据库图像在该簇中的特征点数。

1.4 可伸缩图像检索

为了实现可伸缩检索，使用文档模型来描述鞋印图像内容，即对图像中出现在每一聚类簇中的特征个数进行统计。假设第i幅图像在每一聚类簇中的SIFT特征点个数分别为n1,n2,…,nc，其中c为聚类簇的个数，则所有鞋印图像可表示为c×N的矩阵D，其中N为数据库中的鞋印图像个数。使用词频-逆文本频率(term frequency-inverse document frequency，TF-IDF)指数方法用于加权。词频和逆文本频率分别为

(1)

其中，FT表示词频，bi表示一幅图像在第i个聚类簇中的特征点个数，NF表示该图像提取的特征点数目。FID表示逆文本频率，N表示数据库中的图像总数，Ii表示在第i个聚类簇中存在特征点的鞋印图像个数。

利用式(1)，数据库中每一幅图像的权重可以计算为FT×FID，可得到一个c×N的权重矩阵W，利用W对矩阵D进行加权得结果矩阵DW。

查询过程为，先提取查询图片的SIFT特征，然后计算查询图像的每一个特征与词汇树中每一个聚类中心之间的欧式距离。计算每个聚类簇中的特征点个数，将查询图像所有特征点记为向量q。然后用式(1)计算查询图像的权重并进行加权。计算查询加权向量qW和矩阵DW中每一列的余弦距离，确定最终的检索结果。

2 实验结果与分析

为了考查基于词汇树的可伸缩检索框架的性能，使用图像检索中的按例检索(query by example，QBE)框架[2]进行对照。

2.1 实验数据与环境

本文实验环境参数为CPU为Intel Core i3双核(64位处理器)，3.4 GHz；内存为8 G；操作系统为Windows 8.1中文版(64位系统)；实验程序用Matlab 2010b编写。

实验数据库中数据来源，包括依托电子信息现场勘验应用技术公安部重点实验室采集的实际案件现场勘验鞋印图像以及从互联网上采集的鞋印图像。数据库中包含了1 916个被试的总计9 691幅图像。每个被试视为1个语义类，采集了2～14幅不等的鞋印图像。数据库中部分图像示例，如图3所示。

图3 鞋印图像数据库示例

实验中从每幅图像上提取100个特征点，层次聚类时K值为3，词汇树深度为3。计算上述指标时，从每个语义类中随机选取2幅图像(有些被试仅采集了2幅图像)，依次作为查询图像进行检索。这样的过程共进行10轮，取所有语义类检索结果指标的平均值作为最终评价指标。

2.2 结果与分析

实验采用查准率、召回率和检索单幅图像所需时间等3个指标作为评价算法性能的指标。查准率和召回率是图像检索中的标准评价指标[4]，查准率是指检索出图像中正确图像的比例，召回率是指检出正确图像数目占整个数据库中所有准确图像的比例。

为了验证本文方法的可伸缩性能，实验中依次取数据库尺寸为1 000、2 000、3 000、4 000、5 000、6 000、7 000、8 000和9 000幅图像，分别计算不同数据库尺寸下的QBE框架和本文方法对应的指标。不同数据库尺寸下查准率、召回率和检索单幅图像所需时间的实验结果，如图4所示。

由图4可知，在查准率和检索时间上，本文算法优于QBE框架，在召回率指标上则略低于QBE框架。当数据库的大小每增加1 000幅图像时，本文方法的单幅图像的查准率平均下降0.008，QBE框架平均下降0.009；本文方法的单幅图像检索时间平均增加0.119 s，QBE框架平均增加1.120 s。导致这一结果的原因可能为，词汇树中节点的个数不会增加且用于相似度比较的矩阵较小。而QBE框架随着数据库尺寸的增大，其需要进行相似度比较的矩阵个数不仅随数据库增大而增大，且其矩阵自身也较大，造成QBE框架检索需要较长时间。这说明所提方法在针对鞋印图像数据库规模增长的情况时具有可伸缩特性，具有应用价值。