设Q为待查询的鞋印样图, 首先, 提取其SIFT局部特征 , 其中： 表示第j个SIFT描述子, n_q表示SIFT描述子的数量。为了在鞋印图像库T中查询到与之相似的其他图像, 传统方法就是计算F_Q与F_set中每一个SIFT描述子 的相似性。具体方法是^{[6, 10]}：对于F_Q中的任意Y_j, 基于欧氏距离在中搜索它的最近特征点X_ij1与次近特征点X_ij2。然后, 计算Y_j与它们之间的欧氏距离 , 若D₁与D₂的比值D_{1 /} D₂小于某个阈值σ （后续实验中取σ =0.5）, 则认为X_ij1与Y_j是一对匹配点。反之则不是匹配点。通过上述方法, 设鞋印图像IMG_i与Q的SIFT描述子总共匹配的点数为M(IMG_i, Q), 则其相似度定义如下：

其中, 即可以通过式（3）计算Q与鞋印图像库T中所有幅鞋印图像之间的相似度, 再按相似度由大到小进行排序, 从而得到比对查询结果。

在鞋印比对实际应用中, 通常面对的是大规模鞋印图像库, 且每幅鞋印图像提取的SIFT描述子的数量也会达到上千个, 若直接采用第2.1节所述方法进行逐个穷举匹配, 则比对速度会非常慢。所以, 本文提出一种基于稀疏编码与反向索引的快速比对算法, 相关原理与步骤如下：

2.2.1 构造视觉字典

为了构造视觉字典, 本文将F_set中所有图像对应的SIFT描述子排在一起, 记作：

其中 为SIFT描述子的总数。具有相同花纹结构的鞋印图像其局部区域对应的SIFT描述子在特征空间将会聚集在一起, 采用K-Means方法将Set中SIFT描述子聚成K类（后续实验中K=6000）, 每个聚类中心通常都代表一组具有相同视觉特征的图像区域, 称之为“ 视觉字” , 记作 ; 称这K个“ 视觉字” 为“ 视觉字典” , 记作：

其中D的每一列表示字典中的一个码元（视觉字）, K表示字典的长度。

2.2.2 计算稀疏编码特征

设 为第i幅鞋印图像IMG_i对应的SIFT描述子数据集, 对于F_i中的每一个SIFT描述子 , 采用OMP方法求解式（6）优化问题^[9], 得到其稀疏编码系数 ：

其中λ > 0正则系数（后续试验中λ =0.15）, 表示系数a_j的L₁范数。然后, 将F_i中所有SIFT描述子的稀疏编码系数按列排在一起, 记为：

其中B_i中的每一列表示一个SIFT描述子的稀疏编码系数。最后, 对中的数据进行最大池化（max pooling）处理, 即在所有编码系数a_j的各个维度上取最大值, 也就相当于在B_i的每一行分别取大值, 从而得到的稀疏编码特征 , 记为：

其中： 表示B_i中第k行的最大池化处理结果。

2.2.3 反向索引

反向索引也常被称为倒排索引^[10], 是一种起源于文档快速检索的索引方法, 本文将它用于鞋印图像比对, 其主要原理是：首先, 对于鞋印图像库 中每一幅图像, 通过第2.2.2节所述方法, 计算它的稀疏编码特征（列向量）, 记为： , 其中 K示第j个码元（视觉单词）对应编码系数（注：因为是稀疏编码, 这些系数中大部分是0）; 然后, 将所有鞋印图像对应的稀疏编码特征排在一起, 则得到“ 词-图像矩阵” , 记为：

其中A_{k× N}每一行对应一个“ 视觉字” , 每一列对应一幅鞋印图像。也就是说：在A_{k× N}这个“ 词-图像矩阵” 中, 竖向每一列就是一个正排表, 若该列向量第k个维度上的数值非0, 则说明图像存在第k个视觉单词, 反之则不存在; 而横向每一行就是一个倒排表（反向表）, 若该行向量第i个维度上的数值非0, 则说明第i幅鞋印图像包含相应视觉单词, 反之则不包含。

在鞋印图像比对应用系统中, 建立反向索引其实就是计算“ 词-图像矩阵” A_{k× N}, 因为A_{k× N}中的每一行对应着一个视觉单词的反向索引表, 可以将中的数据以序列化的方式存储在一个文件里。在查找比对时, 先从相应文件加载A_{k× N}, 然后只要根据比对样图所包含的视觉单词信息, 就可快速找到所有包含相同视觉单词的其他图像, 以实现快速相似计算与比对。

设Q为待查询的鞋印样图, 首先, 提取其SIFT局部特征 , 其中：Y_j表示第j个SIFT描述子, n_q表示SIFT描述子的数量; 然后, 采用第2.2.2节所述方法对F_Q进行稀疏编码与最大池化处理, 从而可得到它的稀疏编码特征 。设 表示Q与T中每幅鞋印图像的相似度, 为了利用反向索引快速计算 , 具体方法是：首先 , 在寻找非0系数（因为是稀疏编码, 中绝大部分系数是0）, 若 则说明鞋印图像Q包含有第k个视觉单词, 则将视觉单词对应的反向索引表（即A_{k× N}的第k行）中的数据与 相乘, 再累加到 之中。

将本文提出的基于稀疏编码与反向索引的鞋印图像比对算法主要步骤总结如下：

算法：CS-RI鞋印图像快速比对算法

输入：鞋印图像集, K-Means字典构造聚类数量K, 比对样图Q;

输出：字典D, “ 词-图像矩阵” A_{k× N}, 相似度 。

2.4.1 离线建立反向索引表

Step 1：SIFT局部特征提取

对 , 用第1节所述方法对其进行SIFT特征提取, 从而得到式（2）所示的特征数据集F_set;

Step 2：构造字典

利用特征数据集F_set, 采用2.2.1节所述方法进行K-Means聚成, 从而得到式（5）所示字典D;

Step 3：稀疏编码特征提取

对 , 首先, 在特征数据集F_set中找到其SIFT描述子集 ; 然后, 采用2.2.2节所述方法对F_i每个SIFT描述子X_ij进行稀疏编码, 并进行最大池化处理, 从而得到式（8）所示的稀疏编码特征b_i;

Step 4：建立反向索引表

将鞋印图像库T中所有图像对应的稀疏编码特征排在一起, 得到式（9）所示的“ 词-图像矩阵” A_{k× N}; 因为A_{k× N}中的每一行分别对应着一个“ 视觉字” 的“ 反向索引表” , 则将A_{k× N}存储起来, 以用于后续在线鞋印图像快速比对。

2.4.2 在线快速比对

对于比对样图Q, 采用上述相同方法, 提取其SIFT局部特征, 并计算其稀疏编码特征 ; 然后, 采用下述方法计算Q与T中所有鞋印图像的相似度：

Step 1： 初始化

For (i=1; i< =N; i++) ; //N幅图像的相似度先初始化为0

Step 2：利用反向索引计算相似度

For (k=1; k< =K; k++)

//将第k个视觉单词对应的反向索引表（即A_{k× N}中的第k行）与 相乘, 且累加到Sim中

End if

End For

Step 3：相似排序, 返回比对结果

对 的N个数值由大到小进行排序, 并呈现对应鞋印图像, 返回比对结果。