一种基于内容的视频检索方法及装置

摘要

本发明提供一种基于内容的视频检索方法及装置，属于计算机搜索技术领域。方法包括：根据任一目标关键帧编码对由关键帧编码构成的多个哈希表进行检索，确定与任一目标关键帧编码匹配的关键帧编码；计算任一目标关键帧编码与每个匹配关键帧编码之间的相似度分值；基于关键帧的时序信息，根据每个目标关键帧编码与每个匹配关键帧编码之间的相似度分值，计算目标视频与每个匹配视频之间的整体相似度分值；将大于自适应得分阈值的整体相似度分值对应的匹配视频作为检索结果。本发明通过根据关键帧的时序信息，来对视频进行检索。由于能够依据时序关系区分出部分内容相似的不同视频。因此，视频检索时的准确率较高，区分重复视频时的效果较好。

权利要求

1.一种基于内容的视频检索方法，其特征在于，所述方法包括：

对于目标视频中任一目标关键帧，根据所述任一目标关键帧编码对由关键帧编码构成的多个哈希表进行检索，确定与所述任一目标关键帧编码匹配的关键帧编码；

计算所述任一目标关键帧编码与每个匹配关键帧编码之间的相似度分值；

基于关键帧的时序信息，根据每个目标关键帧编码与每个匹配关键帧编码之间的相似度分值，计算目标视频与每个匹配视频之间的整体相似度分值；

将每个匹配视频对应的整体相似度分值与自适应得分阈值进行比较，将大于所述自适应得分阈值的整体相似度分值对应的匹配视频作为检索结果；

所述基于关键帧的时序信息，根据每个目标关键帧编码与每个匹配关键帧编码之间的相似度分值，计算目标视频与每个匹配视频之间的整体相似度分值，包括：对于任一匹配视频，按照关键帧的时序信息，计算所述任一匹配视频与所述目标视频之间关键帧匹配对所对应的帧序变化率；

计算每个帧序变化率对应的量化映射值；

对于任一种量化映射值，确定具有相同量化映射值的帧序变化率所对应的关键帧匹配对，对满足条件的关键帧匹配对所对应的相似度分值进行迭加，将迭加得到的结果作为所述任一种量化映射值对应的相似度分值；

选取所有量化映射值对应的相似度分值中最大相似度分值，将所述最大相似度分值作为所述目标视频与所述任一匹配视频之间的整体相似度分值。

2.根据权利要求1所述的方法，其特征在于，所述根据所述任一目标关键帧编码对由关键帧编码构成的多个哈希表进行检索，确定与所述任一目标关键帧编码匹配的关键帧编码，包括：按照构造多个哈希表中关键帧编码的方式，将所述任一目标关键帧编码拆分成预设数量个子编码；

对于任一子编码，在所述多个哈希表中查询与所述任一子编码之间的海明距离小于预设阈值的所有匹配子编码，将查询到的每个匹配子编码对应的关键帧编码作为与所述任一目标关键帧编码匹配的关键帧编码。

3.根据权利要求1或2所述的方法，其特征在于，所述计算所述任一目标关键帧编码与每个匹配关键帧编码之间的相似度分值，包括：对于任一匹配关键帧编码，计算所述任一目标关键帧与所述任一匹配关键帧编码之间相匹配子编码的海明距离；

基于预设阈值，将每对相匹配子编码的海明距离进行迭加，将迭加结果作为所述任一目标关键帧编码与所述任一匹配关键帧编码之间的匹配参数；

根据所述匹配参数，计算所述任一目标关键帧编码与所述任一匹配关键帧编码之间的相似度分值。

4.根据权利要求1所述的方法，其特征在于，所述按照关键帧的时序信息，计算所述任一匹配视频与所述目标视频之间关键帧匹配对所对应的帧序变化率，包括：对于任意两组关键帧匹配对，对第一组与第二组关键帧匹配对中的目标关键帧序号做差值，得到第一差值；

对第一组与第二组关键帧匹配对中的匹配关键帧序号做差值，得到第二差值；

将所述第二差值除以所述第一差值，得到对应的商值，将所述商值的绝对值作为所述任意两组关键帧匹配对所对应的帧序变化率。

5.一种基于内容的视频检索装置，其特征在于，所述装置包括：

检索模块，用于对于目标视频中任一目标关键帧，根据所述任一目标关键帧编码对由关键帧编码构成的多个哈希表进行检索，确定与所述任一目标关键帧编码匹配的关键帧编码；

第一计算模块，用于计算所述任一目标关键帧编码与每个匹配关键帧编码之间的相似度分值；

第二计算模块，用于基于关键帧的时序信息，根据每个目标关键帧编码与每个匹配关键帧编码之间的相似度分值，计算目标视频与每个匹配视频之间的整体相似度分值；

比较模块，用于将每个匹配视频对应的整体相似度分值与自适应得分阈值进行比较，将大于所述自适应得分阈值的整体相似度分值对应的匹配视频作为检索结果；

所述第二计算模块，包括：

第一计算单元，用于对于任一匹配视频，按照关键帧的时序信息，计算所述任一匹配视频与所述目标视频之间关键帧匹配对所对应的帧序变化率；

第二计算单元，用于计算每个帧序变化率对应的量化映射值；

迭加单元，用于对于任一种量化映射值，确定具有相同量化映射值的帧序变化率所对应的关键帧匹配对，对满足条件的关键帧匹配对所对应的相似度分值进行迭加，将迭加得到的结果作为所述任一种量化映射值对应的相似度分值；

选取单元，用于选取所有量化映射值对应的相似度分值中最大相似度分值，将所述最大相似度分值作为所述目标视频与所述任一匹配视频之间的整体相似度分值。

6.根据权利要求5所述的装置，其特征在于，所述检索模块，用于按照构造多个哈希表中关键帧编码的方式，将所述任一目标关键帧编码拆分成预设数量个子编码；对于任一子编码，在所述多个哈希表中查询与所述任一子编码之间的海明距离小于预设阈值的所有匹配子编码，将查询到的每个匹配子编码对应的关键帧编码作为与所述任一目标关键帧编码匹配的关键帧编码。

7.根据权利要求5或6所述的装置，其特征在于，所述第一计算模块，用于对于任一匹配关键帧编码，计算所述任一目标关键帧与所述任一匹配关键帧编码之间相匹配子编码的海明距离；基于预设阈值，将每对相匹配子编码的海明距离进行迭加，将迭加结果作为所述任一目标关键帧编码与所述任一匹配关键帧编码之间的匹配参数；根据所述匹配参数，计算所述任一目标关键帧编码与所述任一匹配关键帧编码之间的相似度分值。

8.根据权利要求5所述的装置，其特征在于，所述第一计算单元，用于对于任意两组关键帧匹配对，对第一组与第二组关键帧匹配对中的目标关键帧序号做差值，得到第一差值；

对第一组与第二组关键帧匹配对中的匹配关键帧序号做差值，得到第二差值；将所述第二差值除以所述第一差值，得到对应的商值，将所述商值的绝对值作为所述任意两组关键帧匹配对所对应的帧序变化率。

说明书

一种基于内容的视频检索方法及装置

技术领域

[0001] 本发明涉及计算机搜索技术领域，更具体地，涉及一种基于内容的视频检索方法及装置。

背景技术

[0002] 随着互联网技术的飞速发展、视频采集设备以及视频编辑软件的不断更新，网络上流传的视频数量呈爆炸式增长。各种社交应用上每天都会有大量的视频被上传、下载和分享。人们在能很方便的获取各种视频资源的同时，还可以利用各种视频编辑软件对视频进行编辑，如可以从简单的视频格式转换到视频剪辑、多种变换混合等。这导致社交应用服务器上会存储许多重复或近似重复的视频，从而耗费了大量的存储空间。因此，如何检索出视频数据库中重复或近似重复的视频是人们关注的重点。现有的视频检索技术主要是先通过提取目标视频中的目标关键帧，根据目标关键帧编码对由视频关键帧编码构成的哈希表进行检索。当在哈希表中检索到与目标关键帧编码相似的关键帧编码时，则可确定目标视频为重复或近似重复的视频。

[0003] 在实现本发明的过程中，发现现有技术至少存在以下问题：

[0004] 由于在对目标视频进行检索时，通常是将目标视频作为关键帧静态图像集合来处理，而视频之间通常会存在场景相似的关键帧，从而导致在对由视频关键帧哈希编码构成的哈希表进行检索，可能会检索出与目标视频关键帧编码相似、但与目标视频关键帧时序交错的视频关键帧编码。根据单纯基于关键帧编码相似性的判断机制，目标视频会被判定为重复或近似重复的视频。但实际上，在不同视频中由于相似场景发生的时序并不同，相似视频关键帧编码对应的视频与目标视频在全局上并不重复，上述判断结果会导致目标视频被误判为重复或近似重复的视频。因此，视频检索时的准确率较低。

发明内容

[0005] 本发明提供一种克服上述问题或者至少部分地解决上述问题的。

[0006] 根据本发明的一个方面，提供了一种基于内容的视频检索方法，该方法包括：

[0007] 对于目标视频中任一目标关键帧，根据任一目标关键帧编码对由关键帧编码构成的多个哈希表进行检索，确定与任一目标关键帧编码匹配的关键帧编码；

[0008] 计算任一目标关键帧编码与每个匹配关键帧编码之间的相似度分值；

[0009] 基于关键帧的时序信息，根据每个目标关键帧编码与每个匹配关键帧编码之间的相似度分值，计算目标视频与每个匹配视频之间的整体相似度分值；

[0010] 将每个匹配视频对应的整体相似度分值与自适应得分阈值进行比较，将大于自适应得分阈值的整体相似度分值对应的匹配视频作为检索结果。

[0011] 根据本发明的另一个方面，提供了一种基于内容的视频检索装置，该装置包括：

[0012] 检索模块，用于对于目标视频中任一目标关键帧，根据任一目标关键帧编码对由关键帧编码构成的多个哈希表进行检索，确定与任一目标关键帧编码匹配的关键帧编码；

[0013] 第一计算模块，用于计算任一目标关键帧编码与每个匹配关键帧编码之间的相似度分值；

[0014] 第二计算模块，用于基于关键帧的时序信息，根据每个目标关键帧编码与每个匹配关键帧编码之间的相似度分值，计算目标视频与每个匹配视频之间的整体相似度分值；

[0015] 比较模块，用于将每个匹配视频对应的整体相似度分值与自适应得分阈值进行比较，将大于自适应得分阈值的整体相似度分值对应的匹配视频作为检索结果。

[0016] 本申请提出的技术方案带来的有益效果是：

[0017] 通过根据任一目标关键帧编码对由关键帧编码构成的多个哈希表进行检索，确定与任一目标关键帧编码匹配的关键帧编码。计算任一目标关键帧编码与每个匹配关键帧编码之间的相似度分值。基于关键帧的时序信息，根据每个目标关键帧编码与每个匹配关键帧编码之间的相似度分值，计算目标视频与每个匹配视频之间的整体相似度分值。将每个匹配视频对应的整体相似度分值与自适应得分阈值进行比较，将大于自适应得分阈值的整体相似度分值对应的匹配视频作为检索结果。由于在考虑到关键帧图像内容相似性的基础上，还考虑到了视频帧之间的时序关系，从而在检测出重复或近似重复的视频，能够依据时序关系区分出部分内容相似的不同视频。因此，视频检索时的准确率较高，区分重复视频时的效果较好。

附图说明

[0018] 图1为本发明实施例的一种基于内容的视频检索方法的流程示意图；

[0019] 图2为本发明实施例的一种基于内容的视频检索方法的流程示意图；

[0020] 图3为本发明实施例的一种关键帧匹配对的存储结构示意图；

[0021] 图4为本发明实施例的一种相似度分值的统计直方图；

[0022] 图5为本发明实施例的一种相似度分值的统计直方图；

[0023] 图6为本发明实施例的一种相似度分值的统计直方图；

[0024] 图7为本发明实施例的一种基于内容的视频检索装置的结构示意图；

[0025] 图8为本发明实施例的一种第二计算模块的结构示意图。

具体实施方式

[0026] 下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述。以下实施例用于说明本发明，但不用来限制本发明的范围。

[0027] 随着视频采集设备及视频编辑软件的不断更新，网络上流传的视频数量呈爆炸式增长。各种社交应用上每天都会有大量的视频被上传、下载和分享。人们在上传原创视频之外，还可以利用各种视频编辑软件对已有视频进行编辑，如可以从简单的视频格式转换到视频剪辑、多种变换混合等，从而将自己制作的视频上传到网络中。这让服务器上会存储许多重复或近似重复的视频，从而耗费了大量的存储空间，导致可用存储空间与视频增长速度之间失衡。

[0028] 针对上述问题，可先建立视频检索数据库，再通过在视频检索数据库中对上传视频进行检索，从而验证上传视频是否与服务器中已存储的视频重复。其中，建立视频检索数据库的过程可如下所示：对于服务器中存储的任一视频，提取服务器中该视频的关键帧；对提取的关键帧进行图像特征提取，得到图像特征数据；对图像特征数据进行关键帧编码，从而建立该视频对应的关键帧编码集合。通过得到每个视频对应的关键帧编码集合，可得到视频数据库的哈希表。

[0029] 基于由关键帧编码集合构成的关键帧编码哈希表，现有的视频检索技术主要是先通过提取目标视频中的目标关键帧，根据目标关键帧编码对由视频关键帧编码构成的哈希表进行检索。当在哈希表中检索到目标关键帧编码时，则可确定目标视频为重复或近似重复的视频。由于在对目标视频进行检索时，通常是将目标视频作为关键帧静态图像集合来处理，而视频之间通常会存在场景相似的关键帧，从而导致在对由视频关键帧哈希编码构成的哈希表进行检索，可能会检索出与目标视频关键帧编码相似、但与目标视频关键帧时序交错的视频关键帧编码。根据单纯基于关键帧编码相似性的判断机制，目标视频会被判定为重复或近似重复的视频。但实际上，在不同视频中由于相似场景发生的时序并不同，相似视频关键帧编码对应的视频与目标视频在全局上并不重复，上述判断结果会导致目标视频被误判为重复或近似重复的视频。因此，视频检索时的准确率较低。

[0030] 例如，当用户上传视频中关键帧对应的图像是海洋场景时，此时，在服务器中势必会存在许多包含海洋场景的视频，且对应的关键帧编码很可能会非常近似。若用户上传视频中的内容与服务器中存储视频的内容仅仅只是海洋场景近似，而海洋场景发生的时序并不相同。即查询到的视频与目标视频在全局上可能并不重复。根据单纯基于关键帧编码相似性的判断机制，该用户上传视频会被误判为重复或近似重复视频。

[0031] 由于在对用户上传的目标视频进行检索时，可能会检索到某一视频中某一帧编码与目标视频中的关键帧编码近似。但当目标视频内容实质上与服务器中存储的视频内容不同时，近似关键帧对应的时序序号差异会很大。基于上述原理，针对现有技术中的问题，本实施例提供了一种基于内容的视频检索方法，该视频检索方法流程包括：101、对于目标视频中任一目标关键帧，根据任一目标关键帧编码对由关键帧编码构成的多个哈希表进行检索，确定与任一目标关键帧编码匹配的关键帧编码。102、计算任一目标关键帧编码与每个匹配关键帧编码之间的相似度分值。103、基于关键帧的时序信息，根据每个目标关键帧编码与每个匹配关键帧编码之间的相似度分值，计算目标视频与每个匹配视频之间的整体相似度分值。104、将每个匹配视频对应的整体相似度分值与自适应得分阈值进行比较，将大于自适应得分阈值的整体相似度分值对应的匹配视频作为检索结果。

[0032] 101、对于目标视频中任一目标关键帧，根据任一目标关键帧编码对由关键帧编码构成的多个哈希表进行检索，确定与任一目标关键帧编码匹配的关键帧编码。

[0033] 102、计算任一目标关键帧编码与每个匹配关键帧编码之间的相似度分值。

[0034] 103、基于关键帧的时序信息，根据每个目标关键帧编码与每个匹配关键帧编码之间的相似度分值，计算目标视频与每个匹配视频之间的整体相似度分值。

[0035] 104、将每个匹配视频对应的整体相似度分值与自适应得分阈值进行比较，将大于自适应得分阈值的整体相似度分值对应的匹配视频作为检索结果。

[0036] 本发明实施例提供的方法，通过根据任一目标关键帧编码对由关键帧编码构成的多个哈希表进行检索，确定与任一目标关键帧编码匹配的关键帧编码。计算任一目标关键帧编码与每个匹配关键帧编码之间的相似度分值。基于关键帧的时序信息，根据每个目标关键帧编码与每个匹配关键帧编码之间的相似度分值，计算目标视频与每个匹配视频之间的整体相似度分值。将每个匹配视频对应的整体相似度分值与自适应得分阈值进行比较，将大于自适应得分阈值的整体相似度分值对应的匹配视频作为检索结果。由于在考虑到关键帧图像内容相似性的基础上，还考虑到了视频帧之间的时序关系，从而在检测出重复或近似重复的视频，能够依据时序关系区分出部分内容相似的不同视频。因此，视频检索时的准确率较高，区分重复视频时的效果较好。

[0037] 作为一种可选实施例，根据任一目标关键帧编码对由关键帧编码构成的多个哈希表进行检索，确定与任一目标关键帧编码匹配的关键帧编码，包括：

[0038] 按照构造多个哈希表中关键帧编码的方式，将任一目标关键帧编码拆分成预设数量个子编码；

[0039] 对于任一子编码，在多个哈希表中查询与任一子编码之间的海明距离小于预设阈值的所有匹配子编码，将查询到的每个匹配子编码对应的关键帧编码作为与任一目标关键帧编码匹配的关键帧编码。

[0040] 作为一种可选实施例，计算任一目标关键帧编码与每个匹配关键帧编码之间的相似度分值，包括：

[0041] 对于任一匹配关键帧编码，计算任一目标关键帧与任一匹配关键帧编码之间相匹配子编码的海明距离；

[0042] 基于预设阈值，将每对相匹配子编码的海明距离进行迭加，将迭加结果作为任一目标关键帧编码与任一匹配关键帧编码之间的匹配参数；

[0043] 根据匹配参数，计算任一目标关键帧编码与任一匹配关键帧编码之间的相似度分值。

[0044] 作为一种可选实施例，基于关键帧的时序信息，根据每个目标关键帧编码与每个匹配关键帧编码之间的相似度分值，计算目标视频与每个匹配视频之间的整体相似度分值，包括：

[0045] 对于任一匹配视频，按照关键帧的时序信息，计算任一匹配视频与目标视频之间关键帧匹配对所对应的帧序变化率；

[0046] 计算每个帧序变化率对应的量化映射值；

[0047] 对于任一种量化映射值，确定具有相同量化映射函数值的帧序变化率所对应的关键帧匹配对，对满足条件的关键帧匹配对所对应的相似度分值进行迭加，将迭加得到的结果作为任一种量化映射值对应的相似度分值；

[0048] 选取所有量化映射值对应的相似度分值中最大相似度分值，将最大相似度分值作为目标视频与任一匹配视频之间的整体相似度分值。

[0049] 作为一种可选实施例，按照关键帧的时序信息，计算任一匹配视频与目标视频之间关键帧匹配对所对应的帧序变化率，包括：

[0050] 对于任意两组关键帧匹配对，对第一组与第二组关键帧匹配对中的目标关键帧序号做差值，得到第一差值；

[0051] 对第一组与第二组关键帧匹配对中的匹配关键帧序号做差值，得到第二差值；

[0052] 将第二差值除以第一差值，得到对应的商值，将商值的绝对值作为任意两组关键帧匹配对所对应的帧序变化率。

[0053] 上述所有可选技术方案，可以采用任意结合形成本发明的可选实施例，在此不再一一赘述。

[0054] 本发明实施例提供了一种基于内容的视频检索方法，该方法可运用于存储视频的服务器上，本实施例对此不作具体限定。基于图1对应实施例中的内容，由于在提取目标视频的关键帧时，提取到的关键帧数量通常不只一个。因此，在本实施例提供的方法中，一些过程会以目标视频中任一目标关键帧为例，对便于进行说明。其中，目标视频即为待查询视频。参见图2，本实施例提供的方法流程包括：201、根据目标关键帧编码对由关键帧编码构成的多个哈希表进行检索，确定与关键帧编码匹配的关键帧编码。202、计算目标关键帧编码与每个匹配关键帧编码之间的相似度分值。203、基于关键帧的时序信息，根据每个目标关键帧编码与每个匹配关键帧编码之间的相似度分值，计算目标视频与每个匹配视频之间的整体相似度分值。204、将每个匹配视频对应的整体相似度分值与自适应得分阈值进行比较，将大于自适应得分阈值的整体相似度分值对应的匹配视频作为检索结果。

[0055] 其中，201、根据目标关键帧编码对由关键帧编码构成的多个哈希表进行检索，确定与关键帧编码匹配的关键帧编码。

[0056] 由于本实施例提供的视频检索方法是基于多个哈希表的，为了便于理解，在执行本步骤之前在此先对构建多个哈希表的过程进行简单地描述。一种基于编码划分的哈希表构建方式：将每个关键帧编码拆成若干部分，将每个关键帧编码相同部分所对应的子编码构成相应的子哈希表，从而再由多个子哈希表构成多个哈希表。除了上述构造方式之外，还可以有其它构造多个哈希表的方式，本实施例不对构造多个哈希表的构造方式作具体限定，也不对构造子哈希表的数量及后续构造哈希表的数量作具体限定。理论证明，对于目标关键帧编码的检索次数可随着哈希表的数量增多而减少。相比于构造单一哈希表，本实施例中构造多个哈希表的方式可以减少后续检索次数，从而能够提高检索速度。除此之外，还能便于对关键帧编码进行存储，且能提高检索时的召回率。通过划分多个子哈希表，在后续检索过程中还可以采用并行检索的方式，从而进一步地提高了检索效率。

[0057] 基于上述内容，本实施例不对根据目标关键帧编码对由关键帧编码构成的多个哈希表进行检索，确定与关键帧编码匹配的关键帧编码的方式作具体限定，包括但不限于：按照构造多个哈希表中关键帧编码的方式，将任一目标关键帧编码拆分成预设数量个子编码；对于任一子编码，在多个哈希表中查询与任一子编码之间的海明距离小于预设阈值的所有匹配子编码，将查询到的每个匹配子编码对应的关键帧编码作为与任一目标关键帧编码匹配的关键帧编码。

[0058] 需要说明的是，由于在构建哈希表的子哈希表时，是将每个视频关键帧编码进行拆分后，每个视频关键帧编码位于相同部分的子编码构建成一个子哈希表。因此，目标关键帧编码在按照相同的拆分方式进行拆分后，在对任一子编码进行查询时，可在与该子编码对应的子哈希表中进行查询，而不用查询其它的子哈希表。通过上述查询方式，可以提高查询效率。

[0059] 例如，以每个视频对应3个关键帧编码来构建子哈希表为例。其中，3个关键帧编码分别为A、B、C。对于每个关键帧编码，若将每个关键帧编码拆分成3个子编码，如将A拆分成a1、a2、a3，则每个关键帧编码拆分后的第一部分子编码可构成第一个子哈希表，每个关键帧编码拆分后的第二部分子编码可构成第二个子哈希表，每个关键帧编码拆分后的第三部分子编码可构成第三个子哈希表。即a1、b1、c1三者可构成第一个子哈希表T1，a2、b2、c2可构成第二个子哈希表T2，a3、b3、c3可构成第三个子哈希表T3。

[0060] 相应地，在对目标关键帧编码进行拆分时，可按照上述方式拆分成三部分。当对目标关键帧编码拆分后的第一部分子编码进行查询时，可以直接在第一个子哈希表T1中查询，而不用在子哈希表T2及T3中查询，查询其它部分子编码时同理。

[0061] 需要说明的是，上述过程只是其中一种构建多个哈希表方式所对应的查询过程，不同的构建哈希表方式可对应着不同的拆分及查询过程，本实施例对此不作具体限定。

[0062] 在上述计算海明距离的过程中，海明距离为两个子编码的对应比特取值不同的比特位数。预设阈值为编码查询半径，其值可根据整体查询半径R与哈希表的数量L来计算，本实施例对此不作具体限定。其中，预设阈值可表示为 即R与L的比值向下取整的整数。

[0063] 例如，以关键帧编码为1101010101 0101011010 1010011010为例。若构造哈希表时，是按照10位进行拆分的，则上述关键帧编码可拆分为1101010101、0101011010及1010011010。

[0064] 其中，在计算拆分的子编码与哈希表中存储的子编码之间的海明距离时，可通过对两个子编码进行异或运算，运算结果中1的数量即为两个子编码之间的海明距离。以关键帧编码拆分后的第一个子编码为例，若哈希表中存储某一子编码为1000110011，对两者进行异或运算：

[0065]

[0066] 根据上面运算结果可以确定1的数量为5个，即两个子编码的海明距离为5。同理，按照上述方式可以计算得到，目标关键帧编码拆分后的每个子编码与哈希表中子编码之间的海明距离。

[0067] 接着，再将计算得到的海明距离与预设阈值进行比较，即与编码查询半径进行比较。当哈希表中某一子编码与目标关键帧拆分的子编码之间的海明距离小于编码查询半径时，可确定该子编码为匹配子编码。由于哈希表中存储的子编码也是由存储视频对应的关键帧编码拆分而来，从而可将匹配子编码所对应的关键帧编码作为目标关键帧编码的匹配关键帧编码。同理，可将匹配关键帧编码对应的视频作为目标视频的匹配视频。

[0068] 需要说明的是，根据抽屉原理可知，如果两个长度为M的哈希编码的海明距离为R'，那么它们的子编码序列中必定有一对子编码的海明距离小于或等于R'/L。因此，基于上述逻辑可知，本实施例在根据目标关键帧编码的子编码对哈希表进行查询时，可以保证返回查询半径内的结果，同时还可能返回一些与目标关键帧的海明距离稍大于查询半径但仍属于相似视频的结果，从而可以提高检索的召回率。

[0069] 202、计算目标关键帧编码与每个匹配关键帧编码之间的相似度分值。

[0070] 由于在上述步骤201中的检索过程中，可能会存在多个与目标关键帧编码匹配的关键帧编码。为了对关键帧之间相似程度进行描述，现引入相似度分值并对其计算过程进行解释说明。针对任一匹配关键帧编码，关于计算目标关键帧编码与每个匹配关键帧编码之间的相似度分值的方式，本实施例对此不作具体限定，包括但不限于：计算目标关键帧与所匹配关键帧编码之间相匹配子编码的海明距离；基于预设阈值，将每对相匹配子编码的海明距离进行迭加，将迭加结果作为目标关键帧编码与匹配关键帧编码之间的匹配参数；根据匹配参数，计算目标关键帧编码与匹配关键帧编码之间的相似度分值。

[0071] 其中，计算目标关键帧与所匹配关键帧编码之间相匹配子编码的海明距离的过程可参考上述步骤201中的内容，此处不再赘述。上述迭加过程可采用如下公式(1)进行表示：

[0072]

[0073] 在上述公式(1)中，T为目标关键帧与所匹配关键帧编码之间的匹配参数。L为哈希表的总数量，R为整体查询半径。rk表示每对匹配子编码之间的海明距离，θ为依据rk来取值的常量。

[0074] 需要说明的是，L个哈希表中与目标关键帧子编码匹配的子编码匹配对数量越多，每个子编码匹配对所对应的海明距离越小，则对应的总海明距离rk越小。相应地，匹配参数T也越小。T∈[0,R+L)越小，则关键帧相似度越高。当T＝0时，可确定两个关键帧编码完全相同。

[0075] 为了更直观的表示两个关键帧的相似度得分，使得Sij相似度分值与关键帧的相似程度呈正相关，可对上述过程中得到的匹配参数进行指数运算，将得到的指数运算值作为目标关键帧编码与匹配关键帧编码之间的相似度分值。上述计算过程可如公式(2)所示：

[0076] Sij＝αT(α∈(0.5,1))   (2)

[0077] 其中，α为0.5到1之间的常量。T为目标关键帧与所匹配关键帧编码之间的匹配参数，Sij为相似度分值。当然，除了上述方式之外，在根据匹配参数，计算目标关键帧编码与匹配关键帧编码之间的相似度分值时，还可以采用其它的计算方式。具体计算方式只需满足计算得到的相似度分值与关键帧的相似程度呈正相关即可，本实施例对此不作具体限定。

[0078] 203、基于关键帧的时序信息，根据每个目标关键帧编码与每个匹配关键帧编码之间的相似度分值，计算目标视频与每个匹配视频之间的整体相似度分值。

[0079] 在执行本步骤之前，为了能够便于查找，可将上述步骤得到的关键帧匹配情况用表结构进行表结构表示，本实施例对此不作具体限定，具体存储形式可参考图3。在图3中，表索引(Index of videos in database)表示已入库的视频在数据库中的编号，每一行保存的node节点为目标视频与对应匹配视频的关键帧匹配情况。例如，(Fq,Fb,S)表示目标视频Vq的第Fq帧与入库视频Vb的第Fb帧相匹配，相似度分值为S)。另外，每一行中的节点按照目标视频Vq的关键帧时间顺序排列。

[0080] 本实施例不对基于关键帧的时序信息，根据每个目标关键帧编码与每个匹配关键帧编码之间的相似度分值，计算目标视频与每个匹配视频之间的整体相似度分值的方式作具体限定，对于任一匹配视频，包括但不限于：按照关键帧的时序信息，计算匹配视频与目标视频之间关键帧匹配对所对应的帧序变化率；计算每个帧序变化率对应的量化映射值；对于任一种量化映射值，确定具有相同量化映射值的帧序变化率所对应的关键帧匹配对，对满足条件的关键帧匹配对所对应的相似度分值进行迭加，将迭加得到的结果作为任一种量化映射值对应的相似度分值；选取所有量化映射值对应的相似度分值中最大相似度分值，将最大相似度分值作为目标视频与匹配视频之间的整体相似度分值。

[0081] 关于计算帧序变化率的方式，本实施例对此不作具体限定，包括但不限于：对于任意两组关键帧匹配对，对第一组与第二组关键帧匹配对中的目标关键帧序号做差值，得到第一差值；对第一组与第二组关键帧匹配对中的匹配关键帧序号做差值，得到第二差值；将第二差值除以第一差值，得到对应的商值，将商值的绝对值作为任意两组关键帧匹配对所对应的帧序变化率。

[0082] 上述对帧序变化率的计算过程，可用如下公式(3)表示：

[0083]

[0084] 现以目标视频及匹配视频分别为Vq、Vb，且两个视频中包含n＞＝2个关键帧匹配对，分别为 为例，对上述公式(3)进行解释说明。在进行帧序变化率的运算之前，需先选取两组关键帧匹配对，以匹配帧对分别为及 为例。 为关键帧匹配对 中匹配关键帧的帧序
号，Ib2为关键帧匹配对 中匹配关键帧的帧序号。 为关键帧匹配对
中目标关键帧的帧序号，Iq2为关键帧匹配对 中目标关键帧的帧
序号。 为第二差值， 为第一差值。

[0085] 上述公式(3)计算的即为两组关键帧匹配对的帧序号之差的比率，通过该比率值能够反映目标视频Vq与匹配视频Vb之间帧序号变化的一致性。对于两个完全相同的视频，任意关键帧匹配对的帧序变化率都是同一常数。

[0086] 在计算得到匹配视频与目标视频之间关键帧匹配对所对应的帧序变化率之后，由于将帧序变化率差距较小的关键帧匹配对所对应的相似度分值通过迭加的方式进行统一，并不会影响全局的得分统计。因此，可通过量化映射的方式将差距较小的帧序变化率映射为同一个值，从而将量化映射值相同的帧序变化率所对应的相似度分值进行迭加。为了使得上述过程更加直观，可将帧序变化率量化映射到统计直方图中的特定区域。

[0087] 其中，对帧序变化率进行量化映射计算的过程可如下公式(4)所示：

[0088]

[0089] 在上述公式(4)中，d为帧序变化率，c表示统计直方图的中心区域坐标。例如，图4中统计直方图的中心区域坐标为0。s表示d量化的离散程度。其中，s的值越大，不同帧序变化率d和d'的量化映射值差异越大。考虑到两个近似重复视频所提取出的关键帧很有可能在视觉上高度相似，但在序号上有微小的差异等情况。具体实施时可采用较小的s值，量化过程使得不同关键帧匹配对中d的微小变化不会影响全局的得分统计。如图4中，统计直方图中的横坐标即为对帧序变化率进行量化映射后的量化映射值。

[0090] 在计算得到每个帧序变化率对应的量化映射值后，对于每个量化映射值，可将该量化映射值对应的相似度分值迭加至统计直方图相应区域上。例如，如图4所示，对于量化映射值为0的帧序变化率所对应的两组关键帧匹配对，可将该两组关键帧匹配对所对应的相似度分值迭加至量化映射值为0的上方区域。同理，对于其它量化映射值为0的帧序变化率所对应的两个相似度分值也可以迭加至该区域。

[0091] 上述迭加过程可由如下公式(5)表示：

[0092] value(f(di,j))+＝Si+Sj   (5)

[0093] 其中，di,j为第i个与第j个关键帧匹配对之间的帧序变化率，f(di,j)为帧序变化率对应的量化映射值。Si为第i个关键帧匹配对的相似度分值，Sj为第j个关键帧匹配对的相似度分值，value(f(di,j))为上述两个相似度分值迭加结果。

[0094] 通过上述过程，最终可对每种量化映射值上方区域的相似度分值进行迭加，从而得到每种量化映射值上方区域的相似度分值迭加结果，具体迭加效果可如图5及图6所示。其中，图4、图5及图6的纵坐标得分即为量化映射值上方区域的相似度分值迭加结果。

[0095] 基于统计直方图，完成所有关键帧匹配对Gi(i∈[1,n])的统计后，可选区统计直方图中的最大值作为目标视频Vq与匹配视频Vb之间的整体相似度分值。该过程可用如下公式(6)表示：

[0096] S(q,b)'＝maxvalue(f(di,j))   (6)

[0097] 其中，S(q,b)'为标视频Vq与匹配视频Vb之间的整体相似度分值。

[0098] 考虑到匹配的视频关键帧数量对S(q,b)'有较大影响，使得每个关键帧匹配对的匹配质量(即相似度分值)没有得到足够的体现。例如，两个很长但不相似的视频可能会因为有较多匹配的关键帧对，按照上述计算过程，可能会获得较高的得分，从而导致目标视频最终可能会被误判为相似视频。相反，两个近似重复的短视频却因为提取出的关键帧总数本身就很少，按照上述计算过程，可能会获得较低的得分，从而导致内容重复的目标视频最终可能会被误判为非相似视频。

[0099] 为了避免上述情况，在将最大相似度分值作为目标视频与匹配视频之间的整体相似度分值之后，可先确定目标视频与匹配视频之间关键帧匹配对的匹配数量，再将整体相似度分值除以匹配数量所得到的结果作为最终的匹配得分，即目标视频与匹配视频之间的最终整体相似度分值。通过上述计算过程，能够提高计算整体相似度分值时的鲁棒性。其中，上述计算最终整体相似度分值的过程可如下公式(7)所示：

[0100] S(q,b)＝S(q,b)'/n   (7)

[0101] 上述计算视频间整体相似度分值的过程，提出了一种基于视频时序性的计算方法。为了说明方法的适用性，在此分析该方法在几种视频匹配情况中的应用效果，具体内容如下：

[0102] 1、视频间乱序匹配，即两个不同的视频可能因为包含的场景相似而具有较多匹配关键帧对，但因为相似场景在两个视频中出现的位置是不同的，所以匹配关键帧对之间的时序关系是混乱的。

[0103] 如图5所示，对于这种情况，按照本发明实施例提供的相似度分值计算机制，统计直方图中累加得分的分布应该是散乱的。因此，直方图的最大值应该较小，再除以关键帧匹配对的数量后，最终的视频之间整体相似度分值也就很小。

[0104] 2、视频片段与完整视频之间的匹配，即从完整视频中抽离的视频片段与完整视频进行匹配。

[0105] 在实际判断需求中，上述两者应被视为近似重复视频。考虑两者的关键帧匹配情况，实际情况通常如下：由于视频片段相对于完整视频的起始位置不定，即最开始的场景可能是不完整的。因此，最开始提取出的关键帧有较大可能与完整视频的关键帧不匹配(同样，视频结尾的匹配情况类似)。但对于两者共同包含的场景，基于场景划分的关键帧提取算法提取出的关键帧一般是一致的。按照本发明实施例的视频整体相似性分值的计算机制，对得分有贡献的是中间公共部分的关键帧匹配对，而这部分关键帧匹配对的时序性应是相同的。因此，相似度分值的统计情况应与图4一致，最终的视频整体相似度分值可以反映出两者的近似重复性。

[0106] 3、由完整视频的多个子片段拼合形成的视频片段与完整视频之间的匹配。

[0107] 针对这种情况，对应相似度分值的统计直方图可如图6所示。按照本发明实施例提供的相似度分值计算机制，由于片段视频中每个子片段内部关键帧匹配对的时序性是一致的，所以每个子片段内部的关键帧匹配对之间的相似度分值应该落在直方图内的相同区域(如图6中量化映射值为0所对应的柱状区域)，而各个子片段之间的关键帧匹配对所对应的相似度分值迭加值，其分布可能是散乱的(如图6中量化映射值分别为-2、2及3所对应的柱状区域)。因此，一般来说，得分统计直方图中会有一个较大的峰值(如图6中量化映射值为0所对应的柱状区域)。

[0108] 当子片段的时长差异较大时，不同子片段间的关键帧匹配对组合的数量相对较少，得分散乱分布的比例也就较少。相应地，统计峰值也就越明显。因此，本发明实施例提供的相似度分值计算机制对于由较少子片段构成的片段视频(尤其是子片段间长度差异较大的情况)仍有较好的检测效果。

[0109] 通过上面的过程，在计算得到目标视频与匹配视频之间的整体相似度分值之后，由于与目标视频匹配的视频数量通常可能会有多个。因此，需要根据目标视频与每个匹配视频之间的整体相似度分值，对匹配视频进行筛选，从而筛选出与目标视频相似度较高的匹配视频。具体筛选过程中，可将每个匹配视频对应的整体相似度分值与自适应得分阈值进行比较，从而根据比较结果，将大于自适应得分阈值的整体相似度分值所对应的匹配视频作为最终检索结果。其中，自适应得分阈值的数值可根据视频类型不同来进行变化，本实施例对此不作具体限定。

[0110] 本发明实施例提供的方法，通过根据目标关键帧编码对由关键帧编码构成的多个哈希表进行检索，确定与目标关键帧编码匹配的关键帧编码。计算目标关键帧编码与每个匹配关键帧编码之间的相似度分值。基于关键帧的时序信息，根据每个目标关键帧编码与每个匹配关键帧编码之间的相似度分值，计算目标视频与每个匹配视频之间的整体相似度分值。将每个匹配视频对应的整体相似度分值与自适应得分阈值进行比较，将大于自适应得分阈值的整体相似度分值对应的匹配视频作为检索结果。由于在考虑到关键帧图像内容相似性的基础上，还考虑到了视频帧之间的时序关系，从而在检测出重复或近似重复的视频，能够依据时序关系区分出部分内容相似的不同视频。因此，视频检索时的准确率较高，区分重复视频时的效果较好。

[0111] 另外，由于在检索相似的视频关键帧及计算相似性分值时，综合考虑关键帧子编码的海明距离和子编码匹配数量。同时，有效地融合了对多个哈希表检索后的检索结果，从而使得计算关键帧匹配对的相似度分值时计算结果更加准确。由于相似度分值后续会用于重复近似视频的判断，从而间接地提高了视频检索的准确率。

[0112] 最后，根据上述对几种视频匹配实际情况的分析结果可知，基于时序性的视频相似性检索方法对不同类型的视频匹配情况都有较好的检测效果。同时，设定的得分阈值随输入视频不同可相应发生变化，具有自适应性。因此，整体方法对于不同应用场景具有较好的适用性。

[0113] 本发明实施例提供了一种基于内容的视频检索装置，该装置用于执行上述图1或图2对应的实施例中所提供的基于内容的视频检索方法。参见图7，该装置包括：

[0114] 检索模块701，用于对于目标视频中任一目标关键帧，根据任一目标关键帧编码对由关键帧编码构成的多个哈希表进行检索，确定与任一目标关键帧编码匹配的关键帧编码。

[0115] 第一计算模块702，用于计算任一目标关键帧编码与每个匹配关键帧编码之间的相似度分值。

[0116] 第二计算模块703，用于基于关键帧的时序信息，根据每个目标关键帧编码与每个匹配关键帧编码之间的相似度分值，计算目标视频与每个匹配视频之间的整体相似度分值。

[0117] 比较模块704，用于将每个匹配视频对应的整体相似度分值与自适应得分阈值进行比较，将大于自适应得分阈值的整体相似度分值对应的匹配视频作为检索结果。

[0118] 作为一种可选实施例，检索模块701，用于按照构造哈希表中关键帧编码的方式，将任一目标关键帧编码拆分成预设数量个子编码；对于任一子编码，在多个哈希表中查询与任一子编码之间的海明距离小于预设阈值的所有匹配子编码，将查询到的每个匹配子编码对应的关键帧编码作为与任一目标关键帧编码匹配的关键帧编码。

[0119] 作为一种可选实施例，第一计算模块702，用于对于任一匹配关键帧编码，计算任一目标关键帧与任一匹配关键帧编码之间相匹配子编码的海明距离；基于预设阈值，将每对相匹配子编码的海明距离进行迭加，将迭加结果作为任一目标关键帧编码与任一匹配关键帧编码之间的匹配参数；根据匹配参数，计算任一目标关键帧编码与任一匹配关键帧编码之间的相似度分值。

[0120] 作为一种可选实施例，参见图8，第二计算模块703，包括：

[0121] 第一计算单元7031，用于对于任一匹配视频，按照关键帧的时序信息，计算任一匹配视频与目标视频之间关键帧匹配对所对应的帧序变化率；

[0122] 第二计算单元7032，用于计算每个帧序变化率对应的量化映射值；

[0123] 迭加单元7033，用于对于任一种量化映射值，确定具有相同量化映射值的帧序变化率所对应的关键帧匹配对，对满足条件的关键帧匹配对所对应的相似度分值进行迭加，将迭加得到的结果作为任一种量化映射值对应的相似度分值；

[0124] 选取单元7034，用于选取所有量化映射值对应的相似度分值中最大相似度分值，将最大相似度分值作为目标视频与任一匹配视频之间的整体相似度分值。

[0125] 作为一种可选实施例，第一计算单元7031，用于对于任意两组关键帧匹配对，对第一组与第二组关键帧匹配对中的目标关键帧序号做差值，得到第一差值；对第一组与第二组关键帧匹配对中的匹配关键帧序号做差值，得到第二差值；将第二差值除以第一差值，得到对应的商值，将商值的绝对值作为任意两组关键帧匹配对所对应的帧序变化率。

[0126] 本发明实施例提供的装置，通过根据目标关键帧编码对由关键帧编码构成的多个哈希表进行检索，确定与目标关键帧编码匹配的关键帧编码。计算目标关键帧编码与每个匹配关键帧编码之间的相似度分值。基于关键帧的时序信息，根据每个目标关键帧编码与每个匹配关键帧编码之间的相似度分值，计算目标视频与每个匹配视频之间的整体相似度分值。将每个匹配视频对应的整体相似度分值与自适应得分阈值进行比较，将大于自适应得分阈值的整体相似度分值对应的匹配视频作为检索结果。由于在考虑到关键帧图像内容相似性的基础上，还考虑到了视频帧之间的时序关系，从而在检测出重复或近似重复的视频，能够依据时序关系区分出部分内容相似的不同视频。因此，视频检索时的准确率较高，区分重复视频时的效果较好。

[0127] 最后，本申请的方法仅为较佳的实施方案，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。