(12)发明专利申请
(10)申请公布号 CN 105653700 A (43)申请公布日 2016.06.08
(21)申请号 201511025719.1(22)申请日 2015.12.29(30)优先权数据
14/656,979 2015.03.13 US
(71)申请人TCL集团股份有限公司
地址516006 广东省惠州市仲恺高新技术开
发区惠风三路17号TCL科技大厦23楼(72)发明人汪灏泓 杨益敏
(74)专利代理机构深圳市君胜知识产权代理事
务所 44268
代理人王永文(51)Int.Cl.
G06F 17/30(2006.01)
权利要求书3页 说明书9页 附图6页
(54)发明名称
视频检索方法及系统(57)摘要
本发明公开一种视频检索方法及系统，包括：将视频数据库中存储的视频序列划分为多个视频帧；通过预定的特征提取算法从所述多个视频帧中提取多个表示所述若干视频帧特定特征信息的特征选择指纹；将提取的所述若干选择指纹存储在指纹数据库中；接收用户提交的查询视频序列；通过预定的特征提取算法从接收到的所述查询视频序列中至少提取一个表示至少一个查询帧的查询指纹；计算所述查询指纹和所述指纹数据库中选择指纹的相似度以搜索所述查询指纹的匹配；通过快速动态规划算法确定所述选择指纹中的匹配指纹；以及基于所述匹配指纹生成展示给用户的匹配结果。本发明提供的视频检索方法及系统，提高了视频检索的效率。 C N 1 0 5 6 5 3 7 0 0 ACN 105653700 A
权 利 要 求 书
1/3页
1.一种视频检索方法，其特征在于，包括：
将视频数据库中存储的视频序列划分为多个视频帧；
通过预定的特征提取算法从所述多个视频帧中提取若干表示所述多个频帧特定特征信息的特征的选择指纹；
将提取的所述若干选择指纹存储在指纹数据库中；接收用户提交的查询视频序列；
通过预定的特征提取算法从接收到的所述查询视频序列中至少提取一个表示至少一个查询帧的查询指纹；
计算所述查询指纹和所述指纹数据库中选择指纹的相似度以搜索所述查询指纹的匹配；
通过快速动态规划算法确定所述选择指纹中的匹配指纹；以及基于所述匹配指纹生成展示给用户的匹配结果。2.如权利要求1所述的视频检索方法，其特征在于，其中所述通过快速动态规划算法确定所述选择指纹中的匹配指纹步骤进一步包括：
分析由于使用有限数量的选择指纹导致的查询错误以近似原始指纹集合；
基于所述指纹数据库中存储的多个指纹建立索引以生成指纹的倒排文件索引表格，其中每一所述选择指纹划分为若干单词，所述倒排文件索引表格的垂直方向和水平方向分别表示指纹中单词的可能值和单词的位置；
基于所述倒排文件索引表格，通过使用基于投票匹配方法将所述查询视频的指纹和所述指纹数据库中存储的指纹进行匹配；以及
确定在存储受限时最小化查询错误的期望的选择指纹的集合。3.如权利要求2所述的视频检索方法，其特征在于，其中通过使用基于投票匹配方法将所述查询视频的指纹和所述指纹数据库中存储的指纹进行匹配步骤进一步包括：
计算与所述查询指纹至少有一个匹配单词的每个指纹的匹配单词的总数量；将与所述指纹具有最多数量匹配单词的匹配指纹确定为匹配指纹；以及当多种指纹有相同数量的匹配单词时，进行线性搜索以找到具有最大相似度值的指纹。
4.如权利要求2所述的视频检索方法，其特征在于，其中所述找到在存储受限时最小化查询错误的期望的选择指纹的集合步骤进一步包括：在有向无环图中找到独立资源最短路径，其中所有节点都与代表所述原始视频指纹序列中的一个指纹的每一个节点按拓扑次序排列。
5.如权利要求1所述的视频检索方法，其特征在于，其中所述基于所述匹配指纹生成展示给用户的匹配结果步骤还进一步包括：将所述匹配结果和从所述指纹数据库中获取的补充信息合并以给用户形成搜索报告。
6.如权利要求2所述的视频检索方法，其特征在于，其中假设F＝{fi|0≤i≤n-1}表示所述查询视频序列的至少一个指纹，所述查询定义为：
2
CN 105653700 A
权 利 要 求 书
2/3页
其中，sim(·)为在0和1之间实数的相似度函数，x1为所述原始视频序列中选择指纹的索引，m为选择指纹X＝{fx1|x0＜x1＜…＜xm-1，0≤1≤m-1，m≤n}的总数量，n为所述查询视频序列中帧的总数量，THs为满足相似度要求的预设阈值。
7.如权利要求6所述的视频检索方法，其特征在于，其中当所述查询的输出等于x1时，查询结果表示为xE满足预期；当所述查询的输出不等于x1时，出现查询错误，其中：
当所有所述选择指纹都不满足最小的相似度要求(THs)时，这种错误可
以表示为：
以及
当所述查询的输出不是xE时，但是所述查询指纹和其最接近的选择指纹的相似度等于或大于预设阈值THs，这种错误可以表示为：
8.如权利要求2所述的视频检索方法，其特征在于，其中：假设所述指纹数据库中的任意选择指纹在所述倒排文件索引表格中有h个编号，存储所述倒排索引表格的总体空间定义为：
其中，m为所述指纹数据库中选择指纹的总数量；c为衡量，C＝c·h表示准确地保持指纹的一个编号所需存储空间的固定数值。
9.一种视频检索系统，其特征在于，包括：视频数据库，用于存储视频序列和所述视频序列的元数据；视频指纹提取模块，用于通过预定的特征提取算法从多个视频帧中提取若干表示所述多个视频帧特定特征信息的特征的选择指纹；
指纹数据库，用于存储提取的若干选择指纹；倒排索引生成模块，用于基于所述指纹数据库中存储的若干选择指纹建立索引以生成指纹的倒排文件索引表格，其中每一选择指纹划分为若干单词，所述倒排文件索引表格的垂直方向和水平方向分别表示选择指纹中单词的可能值和单词的位置；
查询视频指纹提取模块，用于当用户提交查询视频序列时通过预定特征提取算法从所述接收到的查询视频序列中提取至少一个表示查询帧的查询指纹；以及
搜索模块，用于计算所述查询指纹和选择指纹之间相似度、通过快速动态规划算法在所述选择指纹中确定匹配指纹和基于所述匹配指纹生成提供给用户的匹配结果。
10.如权利要求9所述的视频检索系统，其特征在于，其中所述搜索模块还用于：分析由于使用有限数量导致的选择指纹查询错误以近似原始指纹集合；
基于所述倒排文件索引表格通过使用基于投票匹配方法将所述查询视频的指纹和所
3
CN 105653700 A
权 利 要 求 书
3/3页
述指纹数据库中存储的指纹进行匹配；以及
确定在存储受限时最小化查询错误的期望的选择指纹的集合。11.如权利要求10所述的视频检索系统，其特征在于，其中所述搜索模块还进一步用于：
计算与所述查询指纹至少有一个匹配单词的每个指纹的匹配单词的总数量；将与所述指纹具有最多数量匹配单词的匹配指纹确定为匹配指纹；以及当多种指纹有相同数量的匹配单词时，进行线性搜索以找到具有最大相似度值的指纹。
12.如权利要求10所述的视频检索系统，其特征在于，其中所述搜索模块在有向无环图中找到独立资源最短路径，其中所有节点都与代表所述原始视频指纹序列中的一个指纹的每一个节点按拓扑次序排列。
13.如权利要求9所述的视频检索系统，其特征在于，其中所述搜索模块将所述匹配结果和从所述指纹数据库中获取的补充信息合并以给用户形成搜索报告。
14.如权利要求10所述的视频检索系统，其特征在于，其中假设F＝{fi|0≤i≤n-1}表示所述查询视频序列的至少一个指纹，所述查询定义为：
其中，sim(·)为在0和1之间实数的相似度函数，x1为所述原始视频序列中选择指纹的索引，m为选择指纹X＝{fx1|x0＜x1＜…＜xm-1，0≤1≤m-1，m≤n}的总数量，n为所述查询视频序列中帧的总数量，THs为满足相似度要求的预设阈值。
15.如权利要求14所述的视频检索系统，其特征在于，其中当所述查询的输出等于x1时，查询结果表示为xE满足预期；
当所述查询的输出不等于x1时，出现查询错误，其中：
当所有所述选择指纹都不满足最小的相似度要求(THs)时，这种错误可以表示为：
以及
当所述查询的输出不是xE时，但是所述查询指纹和其最接近的选择指纹的相似度等于或大于预设阈值THs，这种错误可以表示为：
16.如权利要求10所述的视频检索系统，其特征在于，其中：假设所述指纹数据库中的任意选择指纹在所述倒排文件索引表格中有h个编号，存储所述倒排索引表格的总体空间定义为：
其中m为所述指纹数据库中选择指纹的总数量；c为衡量，C＝c·h表示准确地保持指纹的一个编号所需存储空间的固定数量。
4
CN 105653700 A
说 明 书视频检索方法及系统
1/9页
技术领域
[0001]本发明涉及计算机技术领域，尤其涉及一种视频检索方法及系统。
背景技术
[0002]随着近年互联网和数字技术的高速发展，获取视频内容愈加容易。在现今的商业和娱乐业中，视频检索技术已经变得特别流行。传统的视频检索的方法大多基于源自信号处理领域的序列匹配策略，这种方法主要集中在探索新的特征和距离/相似度测量功能而在一定程度上忽略了搜索效率。尽管现有一些视频检索技术能为高效率的检索提供一种简洁的视频内容的表示，考虑到海量视频档案指纹数据库将非常庞大。可通过一些技术比如时间编码和粗粒度搜索(temporal pruning and coarser granularity searching)技术来尝试加快线性搜索，但搜索过程依然类似于穷举搜索。因此，数字视频的扩散要求一种高效和强劲得视频内容的管理和检索的方法。[0003]为解决上述一个或多个技术问题，本发明公开多种方法和系统。例如，本发明公开的多种方法和系统提供一种在现有视频检索系统中提升搜索效率和指纹库的存储空间的解决方案。例如，本发明公开的多种方法和系统可应用于版权侵权(如互联网上非法重新编码的电影或电影提取)的检测系统，可在存储受限时将查询错误最小化。发明内容
[0004]为了解决上述现有技术中视频检索效率不高的技术问题，根据本发明的一个方面，提供一种视频检索方法，包括：将视频数据库中存储的视频序列划分为多个视频帧；通过预定的特征提取算法从所述多个视频帧中提取若干表示所述多个视频帧特定特征信息的特征的选择指纹；将提取的所述若干选择指纹存储在指纹数据库中；接收用户提交的查询视频序列；通过预定的特征提取算法从接收到的所述查询视频序列中至少提取一个表示至少一个查询帧的查询指纹；计算所述查询指纹和所述指纹数据库中选择指纹的相似度以搜索所述查询指纹的匹配；通过快速动态规划算法确定所述选择指纹中的匹配指纹；以及基于所述匹配指纹生成展示给用户的匹配结果。[0005]本发明的另一个方面，还提供一种视频检索系统，包括：视频数据库，用于存储视频序列和所述视频序列的元数据；视频指纹提取模块，用于通过预定的特征提取算法从所述多个视频帧中提取若干表示多个视频帧特定特征信息的特征的选择指纹；指纹数据库，用于存储提取的若干选择指纹；倒排索引生成模块，用于基于所述指纹数据库中存储的若干选择指纹建立索引以生成指纹的倒排文件索引表格，其中每一所述选择指纹划分为若干单词，所述倒排文件索引表格的垂直方向和水平方向分别表示指纹中单词的可能值和单词的位置；查询视频指纹提取模块，用于当用户提交查询视频序列时通过预定特征提取算法从所述接收到的查询视频序列中提取至少一个表示查询帧的查询指纹；以及搜索模块，用于计算所述查询指纹和选择指纹之间相似度、通过快速动态规划算法在所述选择指纹中确定匹配指纹和基于所述匹配指纹生成提供给用户的匹配结果。
5
CN 105653700 A[0006]
说 明 书
2/9页
本发明提供的视频检索方法和系统，通过将所述视频检索任务制定为在特定存储
限制下将查询错误最小化问题，通过使用倒排索引表格获取高效率和有效的检索的最佳视频指纹的提取，并通过兼顾指纹的略读和索引权衡视频查询的准确性和存储空间，提高了视频检索的效率。
附图说明
[0007]图1为本发明特定实施例的示范环境的示意图。[0008]图2为本发明公开实施例中典型计算系统的示意图。
[0009]图3为本发明公开实施例中典型的视频检索系统的示意图。
[0010]图4为本发明公开实施例中视频检索系统的多个模块的典型工作流程的流程示意图。
[0011]图5为本发明公开实施例中视频序列划分为不同视频组件的示意图。[0012]图6为本发明公开实施例中满足期望的典型查询结果的示意图。[0013]图7a和7b为本发明公开实施例中两种查询错误的示意图。[0014]图8为本发明公开实施例中典型倒排文件索引表格的示意图。
[0015]图9为本发明公开实施例中检测和移除版权侵权典型过程的示意图。
具体实施例
[0016]对于本发明领域的技术人员而言，本发明公开实施例的其他方面都可以通过说明书、权利要求书和说明书附图来进行理解。[0017]为使本发明的目的、技术方案及优点更加清楚、明确，以下参照附图并举实施例对本发明进一步详细说明。在可能的情况下，附图中相同的附图标记指代相同或相似的部件。[0018]术语“视频指纹”是一种软件识别、提取和简略视频特征组件的技术，可通过其因而产生的“指纹”唯一性地识别视频。这种技术包括关键帧分析、颜色和动作变化序列分析、相机拍摄分析等等，分析结果可作为视频序列的指纹。
[0019]图1为本发明特定实施例的示范环境100的示意图。如图1所示，所述环境100包括
用户108和网络110。当然，其他设备也可包括在内。电视(TV)102、遥控器104、服务器106、
[0020]电视102可包括任何合适类型的电视，如等离子电视、液晶电视、投影电视、非智能电视或智能电视。电视102可包括其他的计算系统，比如个人电脑(PC)、平板电脑、移动计算机、智能手机等。进一步的，电视102可以是任何通过遥控器104控制在一个或多个频道展示多种节目的内容展示设备。
[0021]遥控器104可为任何类型的控制电视102以及与所述电视102通讯的遥控器，比如用户个性化的电视遥控器、通用遥控器、平板电脑、智能手机或其他可执行遥控功能的计算设备。遥控器104还可包括其他类型的设备，比如基于动作传感器的遥控器、深度相机增强的遥控器以及简单的输入/输出设备，比如键盘、鼠标、语言激活输入设备等。[0022]此外，所述服务器106为任何类型的给用户108提供个性化内容的一个或多个服务器计算机。服务器106可使所述遥控器104和电视102之间的通讯、数据存储和数据处理更加便利。所述电视102、遥控器104和服务器106可通过一个或多个通讯网络110相互进行通讯，所述网络110为比如有线网络、手机网络和/或卫星网络等。
6
CN 105653700 A[0023]
说 明 书
3/9页
用户108可使用遥控器104与电视102交互，观看多种节目和进行其他兴趣活动。或
者，如果电视102可使用动作传感器或深度相机，用户108还可简单地通过手势或身体姿势控制电视102。所述用户108可以为一个或多个用户，比如一起观看电视节目的家庭成员。[0024]所述电视102、遥控器104和/或服务器106可应用于任何计算电路平台。图2为可运行所述电视102、遥控器104和/或网络106的典型计算系统的示意图。[0025]如图2所示，所述计算系统200包括处理器202、存储介质204、显示器206、通讯模组208、数据库214和外围设备212。当然，特定设备可以忽略以及其他设备还可以包括进来。[0026]所述处理器202可以包括任何一个或多个处理器。此外，所述处理器202可包括用于多线程或并行处理的多个核。所述存储介质204可以为内存模块比如ROM、RAM和闪存模块(flash)，以及大容量存储模块比如光盘CD-ROM和硬盘等。当所述处理器202运行计算机程序时，所述存储介质204可存储执行多种流程的计算机程序。[0027]此外，所述外围设备212可包括多种传感器和其他输入/输出设备，比如键盘、鼠标。所述通讯模块208可包括用于通过通讯网络建立连接的特定网络接口设备。所述数据库214包括用于存储特定数据和在存储的数据(比如数据库搜索)上运行特定操作的一个或更多的数据库。
[0028]所述电视102、遥控器104和/或服务器106可为用户108实施视频检索系统。图3为基于选择指纹(selected fingerprint)和倒排文件索引(inverted-file indexing)的典型视频检索系统300的示意图。[0029]如图3所示，所述视频检索系统300包括查询视频302、查询视频预处理模块304、查询视频指纹提取模块306、检索模块308、视频数据库310、视频预处理模块311、视频指纹提取模块312、指纹数据库314、倒排索引生成模块316和搜索结果318。当然，特定设备可以忽略以及其他设备还可以包括进来。所述视频检索系统300(比如多种组件)可通过硬件、软件及其结合来实施。
[0030]所述检索视频302包括任意类型的视频内容资源，还可包括特定的多种视频资源。来自所述查询视频302的内容可同时包括视频数据和元数据。可将多个帧与所述查询视频302关联并提供给其他模块处理。
[0031]所述查询视频预处理模块304可配置用于执行所述查询视频的视频信号转换、重新采样和过滤。所述查询视频预处理模块304可将视频数据库中的每一个视频序列划分为多个视频帧，通过直方图平衡化操作调整图像的整体对比度，并通过图像融合技术平衡图像质量和整体对比度强度。所述查询视频预处理模块304可设置在所述电视102内，也可根据特殊应用设置在所述电视102外部。[0032]当提交查询视频序列后，所述查询视频指纹提取模块306可配置用于从所述查询视频序列中提取代表至少一个查询帧的至少一个指纹。例如，所述查询视频指纹提取模块306通过预定特征提取算法提取表示查询帧特征信息的查询帧特征，这里可使用视频特征和/或音频特征。
[0033]所述查询模块308可配置用于计算查询指纹和选择指纹之间的相似度以在所述指纹数据库314中搜索查询指纹的匹配，通过快速动态规划算法(fast dynamic programming algorithm)在选择指纹中确定匹配指纹，并基于匹配指纹生成提供给用户的匹配结果。[0034]此外，所述视频数据库310包括可存储视频序列和/或视频序列的元数据的数据
7
CN 105653700 A
说 明 书
4/9页
库。
所述视频预处理模块311的功能类似于所述查询视频预处理模块304的功能。所述
视频预处理模块311可配置用于实施存储在所述视频数据库310中视频序列的视频信号的转换、重新采样和过滤操作。
[0036]所述视频指纹提取模块312可配置用于从多个视频帧中提取多个选择指纹，所述多个选择指纹表示所述多个视频帧特定特征信息的特征。更具体地，所述视频指纹提取模块312使用与所述查询视频指纹提取模块306相同的预定特征提取算法从所述多个视频帧中提取视频指纹。
[0037]所述指纹数据库314可配置用于存储所述多个视频指纹和相关元数据比如视频标题，所述视频指纹是从庞大的视频序列的库中提取获得的。
[0038]所述倒排索引生成模块316可配置用于建立多个索引，并基于存储在所述指纹数据库314中的选择指纹生成选择指纹的倒排文件索引表格。具体地，一个选择指纹被划分为h个单词，其中h为整数。所述表格的垂直和水平方向分别表示一个选择指纹中一个单词的可能值(possible value)和一个单词的位置。假若每个单词的单词长度为w，就有2w个可能值，这样就得到一个2w·h尺寸的表格。对于表格的每一次输入，都存储有一个指纹索引清单。这些指纹在相应单词位置分享相同的值。
[0039]所述搜索结果318是所述搜索模块308输出的。即，基于从所述查询视频提取模块306和倒排索引生成模块316获取的信息，所述搜索模块308可在所述指纹数据库314中搜索到与所述提取的指纹足够接近的匹配以生成所述搜索结果318。图4为本发明公开实施例中视频检索系统的多个模块运行典型过程的流程示意图。[0040]如图4所示，开始，将视频数据库中的每一个视频序列划分为多个视频帧(步骤S402)。因为视频是帧的序列，由于视频典型的帧速率为如25帧/秒，相邻帧之间的变化相对较小，可应用一些集群技术或聚类技术将整个视频划分为不同具有类似帧的帧集合以作进一步处理，以替代对每一个帧作单独处理。[0041]例如，图5为将视频流划分为不同视频组件的示意图。如图5所示，视频流可划分为多个场景，每一个场景又可划分为多个镜头，每一个镜头可划分为多个帧，等等。帧可进一步划分为多个对象，可提取视频帧的特征用作进一步处理。[0042]回到图4，对所述多个视频帧进行预处理(步骤S404)。所述预处理包括进行直方图平衡化和执行图像融合。平衡的目的是调整图像的整体对比对度，以增强图像的骨架结构并展示更多的细节。所述图形融合可平衡图像质量和整体对比度程度。
[0043]从所述视频数据库存储的视频序列的多个视频帧中提取多个选择视频指纹(步骤S406)。所述视频指纹可以是设计用于唯一性辨识视频信号的特征信息。然后，将提取的选择指纹存储在指纹数据库中(步骤S408)。所述指纹数据库可以为搜索树或其他合适的数据结构的形式。将从庞大视频序列库中提取的多个视频指纹和相关元数据比如视频标题可存储在所述指纹数据库中。
[0044]当查询视频序列提交后，从接收到的查询视频序列中提取指纹集合(步骤S410)。所述提交的查询视频包括任意类型的视频内容资源，可包括特定的多种视频资源。来自所述查询视频的内容可同时包括视频数据和元数据。将多个帧与所述提交的查询视频关联并用于指纹提取处理。如果所述查询视频和所述视频数据库中存储的视频序列相同，即使这些视频是不同编
8
[0035]
CN 105653700 A
说 明 书
5/9页
码和不同码率的且作为结果差别巨大，所述指纹确定成功。假设F＝{fi|0≤i≤n-1}表示所述查询视频序列的指纹集合，其中n为所述查询指纹序列中帧的总数量。换言之，所述视频序列中的每一帧都以一个指纹来表示。假设
为选
择指纹(SF)，其中xl为原始视频序列中选择指纹的索引，m为选择的指纹的总数量。所述原始视频序列可简略表示为选择指纹的最佳集合。
[0045]计算查询指纹和选择指纹的相似度以找到与所述查询指纹足够接近的匹配(步骤S412)。所述查询定义为：
[0046]
其中，sim(·)为在0和1之间实数的相似度函数，THs为预设的阈值。如果所述查询指纹和匹配选择的指纹之间的相似度低于THs，则所述查询返回-1。即，所述查询的输入为所述原始查询视频序列(比如fi∈F)中的任意指纹，所述查询的输出为匹配选择的指纹的位置表示为xO。
[0048]在本发明公开实施例中，将两个指纹之间的相似度作为衡量工具以确定这两个指纹的接近程度。应该指出，两个相同的指纹有最大的相似度值，而两个看起来不同的指纹有低的相似度值。基于公式(1)的定义，所述查询也就是在选择指纹(如)中为所述查询指纹查找匹配指纹的过程。图6为本发明公开实施例中典型查询结果满足预期的示意图。
[0047][0049]
如图6所示，和为三个连续的选择指纹。已知查询fi，如果输出等于xl，
然后满足预期的查询结果以xE表示；否则，将会发生查询错误。换言之，期望的查询结果是最接近的(位置方面)选择指纹(且具有最大的相似度)。如果所述原始视频序列的所有指纹都选择作为选择指纹，假设并没有两个指纹相同，则查询应该通常会返回期望的结果。这种假设对大多数视频序列都成立。然而，有限数量的选择指纹用于近似(approximate)所述原始全部指纹集合(出于查询效率和存储目的等)，因此近似可能导致查询错误。由不可预期的结果导致的查询错误，意味着公式(1)中的输出并非与所述输入查询指纹最接近的选择指纹的位置。图7(a)和图7(b)为本发明实施例中两种查询错误情况的示意图。
[0050]
如图7(a)和图7(b)所示，和为三个连续的选择指纹。这种查询的输出
可以归类为以下两种情况：(1)输出为-1，即说明并没有选择指纹满足最低相似度要求(THs)。换言之，如图7(a)所示
(2)输出并非期望的
指纹位置(xE)，但其他的一些选择指纹相比最接近的指纹对于所述查询指纹有更大的相似度。换言之，如图7(b)所示
这两种查询错误都是从相似度的角度分析的。假如所述查询指纹和最接近选择指纹的相似度低于预设阈值THs，输出通常不会是期望的指纹(xE)的位置，这将会导致如图7(a)所示的查询错误情况(1)。因此，如图7(a)所示的这类查询错误可以表示为：
[0052][0053][0051]
另一方面，即使所述查询指纹和其最接近的选择指纹之间的相似度大于预设阈值
9
CN 105653700 A
说 明 书
6/9页
THs，也有可能存在如图7(b)所示的超过期望位置的更为相似的选择指纹。如图7(b)所示的这类查询错误可以表示为：
[0054]
[0055]
因此，公式(2)和公式(3)表示的两种类型的查询错误可代替且仅代替公式(1)中
定义的查询。因此，所述查询错误可以表示为：
[0056]
所述视频数据库的规模随着选择指纹爆发性增长，这给高效率的搜索特别是实时应用提出了巨大挑战。因此，可对于视频检索提供一种倒排文件索引体系。即，基于所述指纹数据库中存储的指纹，建立多个索引以生成选择指纹的倒排文件索引表格。所述倒排文件为索引数据结构，所述索引数据结构存储内容(比如单词或数字)到数据库文件中位置的映射。所述倒排索引的目的是，当一个文件加入到数据库中时，以增加处理为代价实现快速全面的搜索。图8为典型倒排文件索引表格的示意图。[0058]如图8所示，一个指纹被划分为h个单词，其中h为整数。所述倒排文件索引表格的垂直和水平方向分别表示一个指纹中一个单词的可能值和一个单词的位置。假若每个单词的单词长度为w，就有2w可能值，这样就得到一个2w·h尺寸的表格。对于每一个倒排文件索引表格的录入，都存储有一个指纹索引的清单。这些指纹在相应单词的位置分享相同的值。[0059]基于所述倒排文件索引表格可以有很多匹配策略。这里所使用的，通过基于投票匹配方法去匹配所述查询视频的指纹和所述指纹数据库中存储的指纹。[0060]具体地，计算与所述查询指纹至少有一个匹配单词的每个指纹的匹配单词的总数量。然后，最佳匹配为具有最多匹配的单词(投票)的数量。如果多种指纹有相同数量的匹配单词，然后通过线性搜索来确定具有最大相似度值的指纹。基于实验结果，所述基于投票搜索方法可实现查询时间和查询准确性之间的平衡。所述倒排文件索引表格有几个特性：(1)在图8中，每一列都包括2w个单元格，所述指纹数据库中任意的选择指纹在所述2w个单元格中的都有一个且仅有一个编号；(2)所述指纹数据库中的任意选择指纹在所述倒排文件索引表格中有h个编号，每列对应一个。基于上述特性，单词生成的越多，要保持所述倒排文件
也需要更多的时间去实现匹配。具体的，存储所述倒排索索引表格就需要更多的存储空间，
引表格的总体空间定义为：
[0061][0062]
[0057]
其中，m为所述指纹数据库中选择指纹的总数量；c为衡量，C＝c·h表示准确地保
持指纹的一个编号所需存储空间的固定数值。如公式(5)所示，所述存储空间为m的函数，也就意味着所述存储空间由选择指纹的总数量来确定(为简化分析，假设h为已知)。换言之，所述存储空间是独立于所述输入查询(fi)的。
[0063]现在问题是确定一个在存储受限时能最小化查询错误的最佳选择指纹集合。由于单独的查询操作是随机变量，很难去描绘其行为。作为替代，所述原始视频指纹序列的总体的查询错误(如单独查询错误的积累)可统计性地表示查询过程的通用性能。因此，解决最
10
CN 105653700 A
说 明 书
7/9页
佳化的问题可以定义为：
[0064]
其中Smax为允许的最大存储容量。
[0066]选择指纹选择得越多，查询落入错误情况1(如图7(a)所示)的机会就越少，然而生成错误情况2(如图7(b)所示)的概率就可能增加。换言之，选择指纹的数量在总体查询错误上有“积极”或“消极”的效果。另一方面，选择指纹的尺寸(如m)尽可能保持的小，因为选择指纹的尺寸(如m)影响如公式(5)所示的存储需求。因此，公式(6)中的问题可以解释为查找
以最小化总体查询错误。最合适的选择指纹集合，
[0067]已知N和m分别为原始序列中指纹的总数量和选择的选择指纹的数量，对于特定的m大约有
个可能的解决方案。假设m为变量，评估的解决方案的总数量为
当n和m都很大时，对所有解决方案执行穷举搜索是不可行的。事实上，指纹选择
的问题很像0-1背包问题(knapsack problem)，也就是NP-HARD困难问题。因此，需要提供一种能帮助找到最佳解决方案的快速途径。
[0068]
[0065]
计算φ
如果
仅最近相关的选择指纹。然而，可通过评估所有可获得的选择指纹
的概率能做模型，这样就没有必要去比较每个选择指纹。
来确定
[0069]
具体地，计算F中每对指纹的逐对相似度。对于每一查询输入fi，都有一个相似度
减小的指纹排序清单。已知预设相似度阈值THs，可获取与输入指纹fi相似度值相等或大于
表示。假设每个选择指纹的选择是一个伯努力试验
近似与
阈值THs的指纹清单，指纹清单以
(Bernoulli trial)，F中每个都有相同被选择与否概率的指纹，错误
相等的概率。所述伯努力试验是一种准确地有两种可能的输出“成功”和“失败”的随机实验，其中每次实验的成功概率都一样。因此，公式(3)可改写为：
[0070][0071]
在错误近似之后，最佳化的问题就转化为在有向无环图(Directed Acyclic Graph，DAG)中找到独立源最短路径问题的表格理论问题，其中所有节点都与所述原始视频指纹序列中代表一个指纹的每一个节点按拓扑次序排列。通过快速动态规划算法确定选择指纹中的匹配指纹(步骤S414)。这个公式中重要的部分涉及到权重函数e(·)的定义。基于所述查询错误分析的两类错误的定义，所述权重函数可计算为
[0072][0073]
其中fi和fk为F中任意两个指纹，预期的指纹位置可定义为：
[0074][0075]
当e(fj，fk)＝0 if k-j＝1时并没有意义，因为这意味着fj和fk是两个连续的指
纹。
11
CN 105653700 A[0076]
说 明 书
8/9页
为了最小化全部查询错误，现在的目的是确定最佳的选择指纹
假设
表示基于第一选择指纹的最佳的选择的查询错误，其中
为
最后选择的选择指纹。假设第一帧(f0)通常选择作为选择指纹，则O0[f0]定义为：
[0077][0078]
另一方面，定义为：
[0079][0080]
如公式(11)所示，第一选择指纹的选择独立于先前l-1的选择指纹的选择。一旦每
个Ol计算出来，整个问题的最佳解决方案可通过以下获取：
[0081][0082][0083]
并以减小的顺序回溯(backtracking)，直到满足基本情况(base case)。
如果最佳化的错误函数不是以m增加的，这将没有价值。因此，公式(6)中最佳化问题的解决方案是确定满足存储限制Smax的最大整数m。[0085]回到图4，在使用所述快速动态规划算法后，基于匹配指纹，将匹配结果和从所述指纹数据库中获取的补充信息合并以形成搜索报告，这样用户可基于搜索报告进行相应的操作，比如播放匹配视频(步骤S416)。所述搜索结果可以多种显示格式展示给用户。[0086]通过将所述视频检索任务制定为在特定存储限制下将查询错误最小化问题，通过使用倒排索引表格获取高效率和有效的检索的最佳视频指纹的提取。本发明公开的视频检索方法和系统通过兼顾指纹的略读和索引权衡视频查询的准确性和存储空间。[0087]应该指出，所述视频检索系统和方法的概念还可以拓展到其他的服务。例如，本发明公开的视频检索方法和系统可集成在智能电视系统和/或智能终端上，以帮助组织和分享对于帮助检测和去除版权侵权有价值的生产信息，以及可见地识别来自网站数据库的视频内容，并防止网站用户将来上传视频内容。图9为本发明公开实施例中检测和移除版权侵权典型过程的示意图。所述检测和移除版权侵权的过程可通过软件或硬件进行实施。[0088]如图9所示，开始，从已知不同的待识别视频中提取多个视频指纹(步骤S902)。所述视频指纹可以是设计用于唯一性标示视频信号的特征信息。应当指出，所述已知视频的视频指纹的简介可直接从版权所有人获得，因为版权所有人可能已经分析过视频并生成指纹集合。将提取的多个指纹存储在指纹数据库内(步骤S904)。典型地，所述指纹数据库可存储一系列不同的已知视频提取的指纹。当捕捉到未知视频时，从所述未知视频中提取至少一个指纹(步骤S906)。所述未知视频可以为商业广告、音乐视频、体育片段、新闻片段、通过互联网可获取或可下载到个人通讯设备(如智能手机、平板等)上的版权作品。基于倒排文件索引表格，通过使用基于投票匹配方法将从未知视频上提取的所述至少一个指纹与所述指纹数据库中存储的已知视频指纹进行比较(步骤S908)。基于比较结果确定所述未知视频是否为已知视频中的一个复制(步骤S910)。当所述未知视频为已知视频中的一个复制时，执行移除版权侵权的相关操作(步骤S912)。
12
[0084]
CN 105653700 A[0089]
说 明 书
9/9页
另外举例，集成了所述视频检索系统的电视设备也可以自动识别屏幕上的视频内
容，可以在节目顶部使用交互特征和应用。此外，所述视频指纹还可以用于播出监视(比如广告监视、新闻监视)和通用媒体监视。播出监视的解决方案可通知内容提供方和内容所有人在何时何地他们的视频内容的播放清单。
[0090]本发明公开的系统和方法可推展应用到其他具有显示器的设备，比如智能手机、平板电脑个人电脑和智能手表等，实现视频检索。所述视频检索系统相关的上述说明可能涉及其他的步骤。对于本领域技术人员而言，本发明其他的应用、利用、变换、修改或等同都是显而易见的。
13
CN 105653700 A
说 明 书 附 图
1/6页
图1
图2
14
CN 105653700 A
说 明 书 附 图
2/6页
图3
15
CN 105653700 A
说 明 书 附 图
3/6页
图4
16
CN 105653700 A
说 明 书 附 图
4/6页
图5
图6
17
CN 105653700 A
说 明 书 附 图
5/6页
图7(a)
图7(b)
18
CN 105653700 A
说 明 书 附 图
6/6页
图8
图9
19
因篇幅问题不能全部显示，请点此查看更多更全内容