一种基于改进编辑距离的近似视频检索方法

摘要

本发明涉及一种基于改进编辑距离的近似视频检索方法，属于计算机视频处理、模式识别领域。该方法将视频转换为图像帧序列，使用基于评分的方法计算两帧的相似度，减小了使用词袋模型进行相似度计算过程中的信息损失。使用改进的编辑距离计算视频序列间的相似度，其中通过计算帧序列间相对编辑距离相似度，有效的缩小了检索过程中的查询范围；结合基于动态规划机制的序列相似度评分方法，有效地减少了错误结果，提高了方法的检索精度。

权利要求

1.一种基于改进编辑距离的近似视频检索方法，其特征在于包括以下步骤：步骤1、将视频数据库中的视频提取关键帧，生成关键帧序列；

步骤2、提取步骤1中关键帧中的局部特征点；

步骤3、使用聚类算法将局部特征点进行聚类，生成K个聚类，每个聚类中心表示为一个视觉单词；

步骤4、对步骤2中的每个局部特征点以及其对应的步骤3生成的视觉单词，根据倒排索引机制构建本地索引表；

步骤5、本地索引表构建完成之后，接收查询请求，提取查询视频关键帧；定义当前查询视频为长度为m的序列Q(q1,q2,...,qm)，其中qi(1≤i≤m)为查询视频序列中第i帧关键帧；

提取关键帧中的局部特征点，对于每个特征点进行量化，即计算出与其距离最小的视觉单词并将其分配给该特征点；

步骤6、定义数据库中当前与查询视频计算相似度的视频序列为长度为n的序列R(r1，r2，...，rn)，其中rj(1≤j≤n)为数据库中当前视频序列第j帧关键帧；计算qi(1≤i≤m)和rj(1≤j≤n)之间的相似度得分，并生成相似度得分表score；

步骤7、由步骤6相似度得分表，生成该查询视频Q和数据库当前数据库视频R的编辑距离表dist；

步骤8、根据步骤7所得编辑距离表，计算得出该查询视频Q和当前数据库视频R的相对编辑距离相似度，如果相对编辑距离相似度超过阈值，则认为该数据库视频与查询视频相似，并由上述相似度得分表计算两个视频的相似度得分；如果小于阈值，则过滤掉该视频R；

本方法中进行距离计算中使用的是欧氏距离；

步骤9、对当前查询视频Q和数据库中每一个视频，重复步骤6到步骤8，根据步骤8计算所得视频相似度得分由高到低返回视频列表，即为查询结果。

2.根据权利要求1所述的一种基于改进编辑距离的近似视频检索方法，其特征还在于：定义数据库中当前与查询视频计算相似度的视频序列为长度为n的序列R(r1,r2，...，rn)，其中rj(1≤j≤n)为数据库中当前视频序列第j帧关键帧；计算qi(1≤i≤m)和rj(1≤j≤n)之间的相似度得分，并生成相似度得分表score，具体步骤为：步骤1、对于当前查询帧qi的每个特征点，查询本地索引表，找到rj中与其具有相同视觉单词的特征点，两个特征点看做一个点对；

步骤2、对于每个具有相同视觉单词的特征点对，使用海明嵌入方法生成两点的海明码，如果两点海明距离超过阈值，则过滤掉该点对；如果两点海明距离没有超过阈值，则保留该点对，并进行下一步运算；

步骤3、使用改进的弱几何一致性方法，统计匹配点对的尺度和方向变化信息，如果点对方向和尺度变化在阈值之内，则保留该点对；否则，则过滤掉该点对；

步骤4、计算剩余每个点对中两个特征点a,b的相似度得分：

其中idf(x)表示视觉单词x的逆词频： |D|表示数据库中视频总数，Q(x)表示特征点x所对应的单词，|Q(x)|表示包含视觉单词x的视频数量；Wdist(x)为海明距离为x的权重得分，具体地， 其中，db为特征的维度；Hdist(a，b)表示a,b两个特征点的海明距离； 表示qi中所有特征点的对应的单词的逆词频的求和，m表示qi中特征点的数目； 表示qi中所有特征点的对应的单词的逆词频的求和；对所有点对的相似度得分求和，所得为qi和rj的相似度得分；

步骤5、重复步骤1到步骤4进行两帧相似度得分计算，生成相似度得分表score。

3.根据权利要求1所述的一种基于改进编辑距离的近似视频检索方法，其特征还在于“相对编辑距离相似度”通过如下公式进行计算：其中，m和n分别为查询视频Q和数据库视频R的序列长度，dist(m，n)为两个视频的编辑距离。

4.根据权利要求1所述的一种基于改进编辑距离的近似视频检索方法，其特征还在于两个视频的相似度得分通过如下公式进行迭代计算：具体地，m和n分别为查询视频Q和数据库视频R的序列长度，i＝m，j＝n，result(m，n)为Q和R两个视频的相似度得分；score(i，j)表示i，j两帧的相似度得分，η表示两帧相似度的阈值，i为查询视频Q的第i帧关键桢，j为当前数据库视频R的第j帧关键帧。

说明书

一种基于改进编辑距离的近似视频检索方法

技术领域

[0001] 本发明涉及一种基于改进编辑距离的近似视频检索方法，属于计算机视频处理、模式识别领域。

背景技术

[0002] 视觉是人类认知世界最基本最有效的途径之一，视频便是建立在人类视觉基础之上的一种信息载体。通过视频信息，人们能够直观、准确、高效的对客观世界进行感知。随着信息技术的发展，尤其是互联网社交网站的兴起，企业、机构以及用户可以越来越方便地创建、编辑以及分享视频，导致互联网上视频数量急剧增加，在这些视频中不可避免的会有大量的近似视频。近似视频是指具有相同的视频来源，但是在文件格式、编码参数、光度(颜色、明暗)不同的或者具有不同编辑操作(如标题、徽标等的增删，以及图像帧的增删等)的两个以上视频。

[0003] 当前，近似视频检索技术在日常生活中主要有以下应用：

[0004] (1)数字视频的版权保护；

[0005] (2)视频广告投放频率监测；

[0006] (3)视频节目内容审查；

[0007] (4)视频内容检索结果的去重。

[0008] 目前的近似视频检索方法一般将关键帧作为基本单元，即将视频看作关键帧序列，将视频间的比较转化为关键帧序列间的比较，已提出的算法可以分为四大类：第一类是基于序列关联性的方法，例如分析序列间的互信息判断序列的相似性；第二类是基于序列连通关系的方法，例如通过构建序列间的二向图分析相似性；第三类是基于投票的方法，例如通过分析关键帧中局部特征的变化情况判断序列的相似性；第四类是基于动态规划的方法，例如构建序列的相似度量矩阵，通过路径搜索机制来分析序列的相似性。前两类方法的主要不足是计算量大，检索复杂度较高，对于复杂视频检索精度较差。基于投票的方法当局部特征变化较大时检索效果会产生较大误差。而基于动态规划的方法精度高，鲁棒性较强，是目前使用最多的一类算法。本发明提出的基于编辑距离的近似视频检测方法属于基于动态规划的方法，涉及的基础背景技术主要为视觉词袋模型和编辑距离。

[0009] 视觉词袋模型是把每幅图像描述为一个局部特征的无序集合。该模型首先使用某种聚类算法将局部特征进行聚类，每个聚类中心被看作是词典中的一个视觉单词，视觉单词由聚类中心对应特征的编码来表示。所有视觉词汇形成一个视觉词典，词典中所含词的个数反映了词典的大小。图像中的每个特征都将被映射到视觉词典的某个词上。视觉词袋模型在图像分类、检索等领域有着广泛的应用。

[0010] 编辑距离是从一个字符串变换到另一个字符串所需要的最少变化的操作次数。

[0011] 修改一个字符串q为另外一个字符串r的时候有三种方法——删除、替换、插入，按照编辑代价算，删除、替换、插入这三种编辑的代价是1，即修改一个字符；不变则是0，即编辑代价是0，表示没有修改。编辑距离计算过程如下：

[0012] 定义函数dist(i,j)，它表示一个字符串q的长度为i的子串到一个字符串r长度为j的子串的编辑距离。定义运算如下：

[0013] 初始化：

[0014]

[0015] 迭代计算：

[0016]

发明内容

[0017] 本发明目的是为实现自然场景下的近似视频检索，并解决现有近似视频检索算法中的由于复杂场景影响而造成结果不精确的问题，提出一种基于改进编辑距离的近似视频检索方法，能够实现在自然场景下的近似视频检索，提高了检索精度，对于复杂视频具有较好的鲁棒性。

[0018] 本发明目的是通过下述技术方案实现的。

[0019] 一种基于改进编辑距离的近似视频检索方法，包括以下步骤：

[0020] 步骤1、将视频数据库中的视频提取关键帧，生成关键帧序列；

[0021] 步骤2、提取步骤1中关键帧中的局部特征点；

[0022] 步骤3、使用聚类算法将局部特征点进行聚类，生成K个聚类，每个聚类中心表示为一个视觉单词；

[0023] 步骤4、对步骤2中的每个局部特征点以及其对应的步骤3生成的视觉单词，根据倒排索引机制构建本地索引表；

[0024] 步骤5、本地索引表构建完成之后，接收查询请求，提取查询视频关键帧。定义当前查询视频为长度为m的序列Q(q1,q2,…,qm)，其中qi(1≤i≤m)为查询视频序列中第i帧关键帧；提取关键帧中的局部特征点，对于每个特征点进行量化，即计算出与其距离最小的视觉单词并将其分配给该特征点；

[0025] 步骤6、定义数据库中当前与查询视频计算相似度的视频序列为长度为n的序列R(r1,r2,…,rn)，其中rj(1≤j≤n)为数据库中当前视频序列第j帧关键帧。计算qi(1≤i≤m)和rj(1≤j≤n)之间的相似度得分，并生成相似度得分表score，具体步骤为：

[0026] 步骤6.1、对于当前查询帧qi的每个特征点，查询本地索引表，找到rj中与其具有相同视觉单词的特征点，两个特征点看做一个点对；

[0027] 步骤6.2、对于每个具有相同视觉单词的特征点对，使用海明嵌入(Hamming Embedding)方法生成两点的海明码，如果两点海明距离超过阈值，则过滤掉该点对；如果两点海明距离没有超过阈值，则保留该点对，并进行下一步运算。

[0028] 步骤6.3、使用改进的弱几何一致性(Enhanced Weak Geometric Consistency,E-WGC)方法，统计匹配点对的尺度和方向变化信息，如果点对方向和尺度变化在阈值之内，则保留该点对；否则，则过滤掉该点对；

[0029] 步骤6.4、计算剩余每个点对中两个特征点a,b的相似度得分：

[0030]

[0031] 其中idf(x)表示视觉单词x的逆词频： |D|表示数据库中视频总数，Q(x)表示特征点x所对应的单词，|Q(x)|表示包含视觉单词x的视频数量。Wdist(x)为海明距离为x的权重得分，具体地， 其中，db为
特征的维度。Hdist(a,b)表示a,b两个特征点的海明距离。 表示qi中所有特征点的对应的单词的逆词频的求和，m表示qi中特征点的数目。同理，表示rj中所有特征点的对应的单词的逆词频的求和。

[0032] 对所有点对的相似度得分求和，所得为qi和rj的相似度得分。

[0033] 步骤6.5、重复6.1到6.4进行两帧相似度得分计算，生成相似度得分表score。

[0034] 步骤7、由步骤6相似度得分表，生成该查询视频Q和数据库当前数据库视频R的编辑距离表dist；

[0035] 具体地，编辑距离根据如下公式计算：

[0036] 初始化：

[0037]

[0038] 迭代计算：

[0039]

[0040] 其中score(i,j)表示i，j两帧的相似度，η表示两帧相似度的阈值，i为查询视频Q的第i帧关键桢，j为当前数据库视频R的第j帧关键帧。

[0041] 步骤8、根据步骤7所得编辑距离表，计算得出该查询视频Q和当前数据库视频R的相对编辑距离相似度，如果相对编辑距离相似度超过阈值，则认为该数据库视频与查询视频相似，并由上述相似度得分表计算两个视频的相似度得分；如果小于阈值，则过滤掉该视频R；

[0042] “相对编辑距离相似度”通过如下公式进行计算：

[0043]

[0044] 其中，m和n分别为查询视频Q和数据库视频R的序列长度，dist(m,n)为两个视频的编辑距离。

[0045] 本方法中进行距离计算中使用的是欧氏距离。

[0046] 具体地，两个视频的相似度得分通过如下公式进行迭代计算：

[0047]

[0048]

[0049] 具体地，m和n分别为查询视频Q和数据库视频R的序列长度，当i＝m，n＝j时，result(m,n)为Q和R两个视频的相似度得分。score(i,j)表示i，j两帧的相似度得分，η表示两帧相似度的阈值，i为查询视频Q的第i帧关键桢，j为当前数据库视频R的第j帧关键帧。

[0050] 步骤9、对当前查询视频Q和数据库中每一个视频，重复步骤6到步骤8，根据步骤8计算所得视频相似度得分由高到低返回视频列表，即为查询结果。

[0051] 优选地，所述步骤2及步骤5中使用RootSIFT特征点作为局部特征点。RootSIFT特征点相比于SIFT特征点在匹配过程中更加稳定，并且没有明显增加计算量。

[0052] 有益效果

[0053] 本发明将视频看做图片序列，使用基于评分的方法计算两帧相似度，减小了基于词袋模型的相似度计算过程中的信息损失；使用改进的编辑距离方法计算两个序列的相似度，可以准确地反映出两个序列的相似情况。与已有技术相比具有精确度高，方法鲁棒性强的特点；本发明在视频检索领域有着重要作用，可以较精确检索或检测出近似视频，可以嵌入到视频检索系统中，改善检索结果。

附图说明

[0054] 图1是本发明所提出的一种基于改进编辑距离的近似视频检索方法框架；

[0055] 图2是视频相似度计算过程中相似度得分表、编辑距离表的示例；

具体实施方式

[0056] 为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施方案仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方案方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

[0057] 如图1所示，一种基于改进编辑距离的近似视频检索方法：

[0058] 根据步骤1，将视频数据库中的视频提取关键帧；

[0059] 具体地，提取关键帧的方法，可以采用均匀采样的方法，即隔几帧提取一帧的方法，也可以采用基于场景或子镜头的关键帧提取的方法等。在本发明实例中，对于目标视频采取何种方法进行关键帧抽取可以根据视频的具体情况而定，本发明对此不作具体限定。

[0060] 根据步骤2，提取步骤1中关键帧中的局部特征点；

[0061] 具体地，可以采用SIFT，PCA-SIFT，SURF，RootSIFT等方法进行提取，优选地，本发明采用RootSIFT特征点作为局部特征点。RootSIFT特征点相比于SIFT特征点在匹配过程中更加稳定，并且没有明显增加计算量。

[0062] 根据步骤3，使用聚类算法将局部特征点进行聚类，生成K个聚类，每个聚类中心表示为一个视觉单词；

[0063] 具体地，可以使用K-Means、K-Means++、Hierarchical K-Means等方法进行聚类，本发明对此不作具体限定。优选地，本发明使用K-Means++方法进行聚类，相对于其它方法，K-Means++方法不需要人为初始化类心，属于K-Means方法的改进。对于K值的选取，应根据不同的数据库的数据量进行不同的选择，本发明对此不作具体限定。举例说明，在CC_WEB_VIDEO数据集中，K选取为20000。

[0064] 根据步骤4，对步骤2中每个局部特征点以及对应的步骤3生成的视觉单词，根据倒排索引机制构建本地索引表；

[0065] 根据步骤5，本地索引表构建完成之后，接收查询请求，提取查询视频关键帧。定义当前查询视频为长度为m的序列Q(q1,q2,…,qm)，其中qi(1≤i≤m)为查询视频序列中第i帧关键帧。提取关键帧中的局部特征点，对于每个特征点进行量化，即计算出与其距离最小的视觉单词并将其分配给该特征点；

[0066] 具体地，对于查询视频的关键帧提取可以采用与步骤1中相同的提取方法，如两者都使用均匀间隔采样或者基于场景的关键帧提取方法，也可以采用不同的关键帧提取方法，举例说明，对于数据库视频采取基于场景的关键帧提取方法，而对于查询视频采用均匀间隔采样的方法。

[0067] 根据步骤6，定义数据库中当前与查询视频计算相似度的视频序列为长度为n的序列R(r1,r2,…,rn)，其中rj(1≤j≤n)为数据库中当前视频序列第j帧关键帧。计算qi(1≤i≤m)和rj(1≤j≤n)之间的相似度得分，并生成相似度得分表score，具体步骤为：

[0068] 步骤6.1、对于当前查询帧qi的每个特征点，查询本地索引表，找到rj中与其具有相同视觉单词的特征点，两个特征点看做一个点对；

[0069] 步骤6.2、对于每个具有相同视觉单词的特征点对，使用海明嵌入(Hamming Embedding)方法生成两点的海明码，如果两点之间海明距离超过阈值，则过滤掉该点对；如果两点海明距离没有超过阈值，则保留该点对，并进行下一步运算。

[0070] 具体地，计算过程如下：生成一个符合高斯分布的矩阵P，对于每一个类中的RootSIFT向量，使用矩阵P与其运算映射到新的向量a，τ表示该类类心映射后的向量。a的海明码 通过如下公式计算得到：

[0071]

[0072] 其中db表示映射后特征的维度。举例说明，在CC_WEB_VIDEO数据集中，特征点为128维的RootSIFT特征点，db为32，阈值为10。

[0073] 步骤6.3、使用改进的弱几何一致性(Enhanced Weak Geometric Consistency,E-WGC)方法，统计匹配点对的尺度和方向变化信息，如果点对方向和尺度变化在阈值之内，则保留该点对；否则，则过滤掉该点对；

[0074] 具体地，对于点对中由a(xa,ya)到b(xb,yb)的变化s，计算如下：

[0075]

[0076] 统计qi和rj匹配点对的s值及出现的频度，选择出现频度最高的值smax作为主方向。举例说明，在CC_WEB_VIDEO数据集中以0.9*smax为阈值，点对的s值在区间[0.9*smax,smax]内则保留该点对，否则过滤掉该点对。

[0077] 步骤6.4、计算剩余每个点对中两个特征点a,b的相似度得分:

[0078]

[0079] 其中idf(x)表示视觉单词x的逆词频，具体地，计算如下：|D|表示数据库中视频总数，Q(x)表示特征点x所对应的单词，|Q(x)|表示包含视觉单词x的视频数量。Wdist(x)为海明距离为x的权重得分，具体地，其中，db为特征的维度。Hdist(a,b)表示a,b两个特征
点的海明距离。 表示qi中所有特征点的对应的单词的逆词频的求和，m
表示qi中特征点的数目。同理， 表示rj中所有特征点的对应的单词的逆词频的求和。

[0080] 对所有点对的相似度得分求和，所得为qi和rj的相似度得分。

[0081] 步骤6.5、重复步骤6.1到6.4进行两帧相似度得分计算，生成两个视频的相似度得分表score。

[0082] 举例说明，两个视频的相似度得分表如图2(a)所示。

[0083] 根据步骤7，由步骤6相似度得分表，生成该查询视频Q和数据库当前数据库视频R的编辑距离表dist；

[0084] 具体地，编辑距离根据如下公式计算：

[0085] 初始化：

[0086]

[0087] 迭代计算：

[0088]

[0089] 其中score(i,j)表示两帧的相似度，η表示两帧相似度的阈值。举例说明，在CC_WEB_VIDEO数据集中η设置为0.1。

[0090] 举例说明，编辑距离表如图2(b)所示。

[0091] 根据步骤8，由步骤7所得编辑距离表，计算得出该查询视频Q和当前数据库视频R的相对编辑距离相似度，如果超过阈值，则认为该数据库视频与查询视频相似，并由上述相似度得分表计算两个视频的相似度得分；如果小于阈值，则过滤掉该视频R；

[0092] “相对编辑距离相似度”通过如下公式进行计算：

[0093]

[0094] 其中，m和n分别为查询视频Q和数据库视频R的序列长度，dist(m,n)为两个视频的编辑距离。举例说明，在在CC_WEB_VIDEO数据集中，该阈值设置为0.4。

[0095] 具体地，两个视频的相似度得分通过如下公式进行计算：

[0096]

[0097]

[0098] 具体地，m和n分别为查询视频Q和数据库视频R的序列长度，当i＝m，j＝n时，result(m,n)为Q和R两个视频的相似度得分。score(i,j)表示i，j两帧的相似度得分，η表示两帧相似度的阈值，i为查询视频Q的第i帧关键桢，j为当前数据库视频R的第j帧关键帧。

[0099] 根据步骤9，对当前查询视频Q和数据库中每一个视频，重复步骤6到步骤8进行计算，根据步骤8计算所得视频相似度得分由高到低返回视频列表，即为查询结果。