基于卷积特征提取和DTW的图像相似度评估算法

宋珣，刘一廷

（西安交通大学自动化系，西安 710049）

0 引言

图像相似度评估是计算机视觉和图像分析中最基本的任务之一。在低级的任务中可用于宽基线匹配，建立全景图等。在高级的任务中可用于目标识别与检测、图像恢复等。

现有的方法中，有些方法需要进行人工特征提取，例如通过提取图像的SIFT特征来描述需要进行比较的两幅图像，再进行特征的匹配。不过这种方法不适用于解析图片中的更高级别的特征，例如桌子、水杯等特征。还有的方法不需要进行人工特征特征提取，而是借助于卷积层。例如siamese方法，该方法将两张图片分别通过一个由若干卷积层堆叠而成的网络结构得到两个输出，再将两个输出拼接起来，送入一个由若干全连接层组成的网络结构，得到相似度输出。这种方法对特征的解析和提取更加全面，但其训练所需的数据集中，相似度标签是一个偏向于主观的量，不同的人定义相似的标准是不同的，这就削弱了该种方法的说服力。

本文采用的相似度的评估标准是用图像特征矩阵之间的距离表征的。距离通过二维动态时间规整求得，具有很强的客观性，特征则是选用目标检测网络的卷积层进行提取的，一定程度继承了siamese算法的优越性。本项目已在GitHub开源：https://github.com/SongXuningithub/Similarity-Evaluation.git。

1 模型实现

1.1 特征提取

特征提取依靠若干卷积层进行，我们选用YOLO v1的前面卷积部分进行特征提取。首先对YOLO v1进行了结构的调整，本文所用的YOLO由ResNet-18（已在Image-Net数据集上预训练）和若干卷积层、批量归一化层、LeakyReLu层的堆叠，最后加两个全连接层组成。YOLO在VOC2007数据集上训练（冻结ResNet-18部分的参数）后，去掉最后的一层卷积层以及其后的所有全连接层，得到的网络结构即为用于特征提取的网络结构。网络结构如图1所示，所需的输出特征由Conv48层直接输出，其后的所有层只用于模型训练。

这里选用YOLO的卷积层进行特征提取而不是用GoogleNet、ResNet这种仅仅用于目标分类的网络的卷积层，是因为我们认为后者提取出的特征表征的是整个图片的特征，而对于图片中目标的移位没有足够的敏感度；相反，YOLO不仅仅关注图像中的目标是什么，还关注目标的位置。因此同一场景中目标的移位也会更好地反映在卷积层提取的特征中。这有利于模型区分出场景或目标移位大小不同的图片。

不直接用YOLO的最后一层输出作为特征，是因为最后一层输出的特征向量中，每一个值都代表对应种类的物品出现在该负责区域的置信度。当负责区域中没有该种类物体时，会被抑制为一个很小的值，所以当场景中没有特别典型的物体时，输出特征整体会趋于零，这是不利于后续处理的。所以使用过高级的特征在这里是不合适的。但我们可以借鉴skip-gram模型，使用网络的中间输出作为输入的特征的间接表达，于是就选用中间的卷积层输出作为其特征。

通过YOLO提取出的特征矩阵Feature Matrix的维度是[H，W，C]，H代表特征图的高度，W代表特征图的宽度，C代表每一个特征向量的维度，本文中C为48，即每个特征是一个48维的向量。

图1 提取特征所用网络结构

1.2 动态时间规整

（1）背景：一维动态时间规整

一维动态时间规整用于求取两个数字序列之间的距离。对于两个等长序列seq1={ }a1,a2,…an和seq2={b1,b2,…bn}，我们可以直接用欧式距离来表示他们之间的距离：

但是，当两个序列的长度不相等时，就不能用这种方式了。所以引入了动态时间规整。对于不等长的两个序列和首先计算出它们的距离矩阵Distance Matrix（m行×n列，简写为DM）。矩阵元素DM(p,q)可以通过欧氏距离来计算，即它代表seq1的p点和seq2的q点的相似程度，距离越小则相似程度越高。所以DM包含了seq1的每个点和seq2的每个点之间的相似程度。之后利用动态规划的思想找到一条从DM(1,1)到DM(m,n)的路径。

具体实现时，我们只关心两个序列之间的距离，所以可以不用记录具体路径，只用多维护一个表示累积距离的矩阵 Cumulative Distance Matrix（m行×n列，简写为CDM）即可。CDM的元素CDM(p,q)代表DM(1,1)到DM(p,q)的最短路径长度，即两个子序列和之间的距离。那么CDM(m,n)即为seq1和seq2之间的距离。

算法的思想是动态规划，其递推公式为：

具体的伪代码形式将在后面二维动态时间规整中给出。

（2）特征矩阵距离测算：二维动态时间规整

实际要计算的是两个三维特征矩阵之间的距离，涉及到一些向量操作，所以先将所用到的符号整理至表1。

表1 符号含义

虽然特征矩阵是三维的。但其实可将矩阵中的特征向量先简化为一个点，那么可将特征矩阵简化为二维平面，其尺寸为[H，W]。若直接将一维动态时间规整推广到二维，则由于一维情况实际是在seq1和seq2计算出的m×n的二维空间中寻找最短路径，二维情况也应该是在FM1和FM2构造的四维距离矩阵中寻找最短路径。前者的时间复杂度为O(m×n)。若FM1尺寸为h1×w1，FM2尺寸为h2×w2，则由一维动态时间规划直接推广得到的二维动态时间规划地时间复杂度为O(h1×w1×h2×w2)。显然，复杂度提升了很多，这会导致算法难以应用于流数据的实时检测中。所以，本算法采用的是基于列对齐的二维动态时间规划算法，以下简称为COL-DTW。

在COL-DTW中，最终还是在二维的距离矩阵DM中求解最短路径，算法示意图如图2所示。要构造这个二维距离矩阵，前提是FM1和FM2的列向量长度相等，即行数相等，有h1=h2。而DM中的每个元素则由对应于FM1和FM2中的列之间的距离求得。即。 用 于 计算列向量之间距离的函数Distance_of_cols伪代码如下：

该函数相当于计算两个特征列向量的每一个对应特征向量之间的欧氏距离，再将其做和、求平均。

计算两个向量欧氏距离的伪代码如下：

图2 COL-DTW结构

最终得到了二维的DM，该DM的尺寸为w1×w2，它的最短路径距离也就是两个三维特征矩阵之间的最短距离。如之前所述，实际的DTM计算过程不用关心具体路径，只需维护一个累积距离矩阵CDM，算法具体流程如下：

则DTM（DM）输出的距离即为两张图片的相似度：距离越大则相似度越小，距离越小则相似度越大。

2 算法性能分析

2.1 多图片相似度比较

在进行相似度的计算之前，首先要确定一个基准量Vbase，这是由于进行比较的两张图片本就不可能是完全相同的两张图片，所谓相似最多是对同一场景的条件相近的两次拍摄，所以基准量Vbase可以不是0。这里的Vbase定义为待匹配图像（本例为A1）的左边90%部分和右边90%部分经过运动模糊之后进行匹配的结果，即假设对该场景的两次拍摄的差别只是相机移动了一个微小的角度。加入运动模糊则是为模拟真实拍摄过程中可能出现的抖动，实践证明加不加此操作影响不大。Vbase计算如图3所示。

图3 Vbase的计算方法

要评估两张图片的相似度，就要整合上一节的两个步骤：特征提取和2D-DTW（本文采用COL-DTW作为2D-DTW的具体实现）距离计算。整合算法伪代码如下，其输入为两张图片，输出为模型评估的相似度。

本节使用材料有：一张基准图片A1，与A1拍摄场景相同但拍摄角度和焦距不同的另一张图片A2、若干与A1拍摄场景截然不同的7张图片（B，C…H）。将A1分别与A2，B，C..H做比较，用2D-DTW距离表示它们两两之间的相似程度，距离大则认为相似程度低，反之则认为相似程度大。所用的与A1进行比较的图片及其对应名称如表2所示。

表2 与A1比较的图片

原图A1及其与A2的关系如图4所示。

图4 A1与A2

通过计算，得出A1与其余8张图片的距离如表3所示。

表3 与A1的2D-DTW距离

分析结果，A2作为与A1拍摄场景相同的图片，与A1的2D-DTW距离最小，只有其他图片的10%不到，而距离小代表相似度高，所以这个结果是符合预期的。

2.2 保真度评估

在图像恢复、图像压缩等领域，常常会损失原图像的质量。所以在图像被恢复之后，需要一个方法确定图像相对于原图像之间的保真度。保真度越高，则说明损失越小。例如图5、图6、图7三张图。

图5 原图

图6 有损图像1

图7 有损图像2

图5是原始的无损图像，图6和图7是图5不同程度受损后的图片。可以看到，虽然图6中出现了一些无规律的锯齿，使得原有的一些边缘变得模糊，但却较好地保留了有效信息。反观图7，虽然没有锯齿，但很多线条都已经消失不见了，对原图的信息出现了较大程度的损失。所以在实际评估中，我们应该给图6打出更高的分数。以下是两种算法对上述两张图的评估。

（1）均方根误差（RMS）算法

假设原始图为f，受损图像为̂，则均方根误差计算方式为：

其计算结果如表4所示。

表4 RMS计算结果

结果表示有损图像2的RMS比有损图像1的小，也就是说用RMS做评估的话有损图像2的质量高于有损图像1。结合上面的分析，这显然是不合理的。

（2）特征提取+2D-DTW算法

换用本文所提的（特征提取+2D-DTW）算法，结果如表5所示。

表5 特征提取+DTW计算结果

结果表示，特征提取之后，有损图像2与原图的2D-DTW距离相较于有损图像1更大，也就是说用本文所提方法做评估的话有损图像1的质量高于有损图像2，这是符合上述分析的。

3 结语

本文给出了基于卷积特征提取和二维动态时间规整的图像相似度评估算法。该方法不需要特殊的数据集进行训练，在拥有已经训练好的YOLO网络的情况下，甚至可以免去训练的步骤。通过DTW进行最后的距离测算提升了算法的客观性与灵活性。在已经进行的图像相似度评估实验中表现出良好的性能，并且在图像保真度评估中体现出比传统的模板匹配算法更强的科学性，具有一定的实际意义。