视频基因.docx
《视频基因.docx》由会员分享，可在线阅读，更多相关《视频基因.docx（15页珍藏版）》请在冰点文库上搜索。
视频基因
视频基因
AlexanderM.BronsteinMichaelM.Bronstein
alex@michael@
RonKimmel
ron@
BBKTechnologiesltd.
Dept.ofComputerScience
Technion,Haifa32000,Israel
March30,2010
摘要
快速发展的因特网技术导致了视频数据在公共领域爆炸式的增长，在分析，组织，管理以及诸如此类的控制上创造了空前绝后的挑战。
像在大量的数据库中鉴定一个视频，把视频碎片放在一起，在不同的版本中找到相似的部分，以及共同的母体等这一类问题在遗传研究和DNA的分析，蛋白质序列的分析都有相似的副本问题。
在这篇文章中，我们提出了一个由基因组研究启发的分析视频的方法。
视频信息表示为DNA序列，再运用生物信息学算法就实现了在大量的数据库中搜索，匹配，比较视频信息。
我们展现了一个基于内容的元数据在批注的视频版本之间映射的应用。
1.介绍
今天，公共领域中视频内容的数量是巨大的，超过数百万小时并且正在快速增长。
类似的增长情况表征了与视频相关的元数据，比如说字幕，用户生成的注释和附加语。
然而，这两种不同的信息属于两个分离的不同的领域。
例如，一个DVD版本的电影“教父”的英文字幕是硬连接到DVD的时间表上的，并且不能用于不同版本的电影。
比如说，从BT上下载，从优酷网上播放或者广播中的视频都有一个不同的时间表。
类似地，用户生成的注释和优酷网上的“教父”的碎片的批注对于一个在DVD上观看的用户是不可用的。
在不同版本的视频的时间表和相关的元数据的一种调和方法是通过基于内容的同步。
为此目的，一个时间独立的署名对于各个视频都要计算，以致允许在不同版本的视频间能够实现相似部分的匹配和对齐。
因此给出了从一个时间坐标系统到另一个时间坐标系统的转换。
在一个客户端和服务端组成的样本应用中，在视频在客户端播放到发送到服务端与视频署名的一个数据库匹配的过程中，署名是在确定的时间被计算的。
在建立了数据库序列的通讯后，服务端的通讯元数据被发送到客户端。
用这种方法，对于一个用一些带有同步元数据的样本序列计算的视频署名数据库是有重大意义的。
一个先前不可见的来自不同资源的视频新版本能够与样本时间表和检索的通讯与数据匹配的。
因此，至少在理论上，任何视频都能够用元数据来丰富，使得相似的视频在数据库中有相同的署名。
描述的应用在署名结构和匹配算法上提出了一些要求。
首先，它们应该能够去处理大量的数据。
这样，依次加强样本简洁，容易转换，能够快速搜索和匹配的要求。
其次，样本计算应该是有效的，在确定的时间内计算。
最后，也是最重要的，一个视频的两个不同的版本由于后期制作和编辑在很大意义上是不同的。
所以样本匹配算法应该能够应对这样的修改。
令人好奇的是，相似的问题在一个似乎毫不相关的基因研究领域遇到了。
在此基因研究领域的主要问题是DNA和蛋白质序列的匹配问题。
最近的众多努力使得大量的标注的DNA和蛋白质序列被收集。
在这其中，有望发现新的序列。
后期处理中的畸变和编辑问题类似于发生在生物DNA序列中的突变基因数据的规模与视频序列中的那些是可比的（例如，人类基因组序列包含近三十亿符号【11】）。
在过去的十年中，很多有效的方法都被运用于基因序列的分析，并诞生了生物信息学【22】。
在这篇文章中，我们借用了完善的生物信息学的方法分析视频。
这些视频正如第二章中被认为与DNA序列相似，补充材料中的样本应用是在不同视频版本中映射的基于不同内容的元数据。
在第三章中，我们采用了基因研究的类比方法。
就是可以采用动态规划序列标准【23,27】以及其快速的启发式【24,1】，与众多序列标准和系统发育分析一样【19】。
为了探究基因序列的突变和视频的后期制作处理和编辑，我们在第四章提出了一个生成的方法，通过度量的学习区研究这些突变的不变性。
我们得到了一个非常简洁的表示法，这种表示法用于视频转换时合适的，并且也允许有效的指标和研究。
第五章陈述了实验性的结果表明了前面提出的各种方法的完善性和有效性。
包括视频检索和大量（1K小时）数据库的校准。
最后，第六章总结了这篇文章。
1.1相关的工作
在文中元数据映射问题与基于内容的视频【17,6】拷贝检测和搜索是密切相关的。
在那里，人们试图找到一个经历了修改，很可能使其在视觉上不同于原来的视频副本。
这个问题应区别于行动和事件识别【31,3,16】，其中相似准则是语义。
概括地说，复制检测问题归结为不变性的检索（对于某一类转换找到一个不变的视频）并且行为识别是分类问题（在视频中鉴别某一类行为）。
为了说明差异，想象三个序列：
一部与“星球大战”质量相当的电影版本在有广告插播的电视上播放并用摄像机抓获了画面，而且业余演员重演lighsabre战斗场面。
拷贝检测的目的就是说第一个和第二个视频序列相似，另一方面，动作识别需要找到第二个和第三个序列之间的相似性。
基于内容的拷贝检测和搜索中的基本问题之一是视频代表性的创造，它能让人们跨版本的比较和匹配视频。
基于镶嵌【12】，拍摄的边界【10】，运行，颜色和时空的强分布【8】以及彩色直方图【18】，排序方法【9】等不同的代表性都被提出来。
当考虑到版本由于后期修改，基于空间【20,21,2】和时空利益【15】以及局部描述的方法产生大的变化被证明是有利的【14】。
此外，这些被证明的大量的数据库【26,4】中图像搜索时非常高效的。
最近，威勒姆斯【30】提出了连接单独视频帧的视觉信息和续帧之间的时间关系基于特征的时空结合的视频描述。
现在的视频交涉的主要缺点之一是一个建设性的不变的视频转换方法。
通常情况下，代表性的设计是基于数量和视频不敏感的典型转换性能。
例如，使用基于梯度的描述【20,2】是已知不敏感的照明和色彩变化。
这样的结构通常不能推广到其他的转换类别，或者导致在不变性和辨别上的一次次优折中。
在文中采用了另一种可用的方法是从视频转换的例子中研究不变性。
通过模拟后期制作和编辑过程，我们能够从认为是不相似的不同视频中生产出认为是相似的（不同于一个转换）并成对的序列。
为了在视频序列中创建一个能够在培训集中实现最佳的不变性和辨别性的公制，这些序列对于用于相似保存散列和公制学习算法【25,13,29】的培训集。
2.视频DNA
针对生物信息化应用的生物DNA数据时由4个字母（代表DNA分子中的氨基酸，记为A,T,C,G，并被当做核苷酸的一种）组成的长序列。
扩展这个例子，在我们的问题上就可以概念化的认为，视频作为一种可被一些可能非常大的视觉概念字母组成的视觉信息点序列，从而导致一种‘字母’序列（或视觉核苷酸）。
通过类比基因序列，我们称这种序列为视频DNA。
视频DNA测序，即在视频之外创建一个视频DNA序列，该过程是通过计算每帧（或短帧序列）的描述和在视频时间轴（见表1）上进行安排序列来实现的。
在本论文中，我们采用了基于特征的代表性，随之的是特征范例【26,4】的标准功能包。
对于每一个视频帧，我们缩小分辨率到320，检测特征点，并且围绕这些点用一种加速强劲【2】功能检测和描述算法的修改计算局部图像描述（图1，顶部）。
450最强特征点被使用。
每个特征点用一个64维灰度和16维彩色描述来描述。
第二，局部描述用K—MEANS聚类算法来量化，分别为灰度和颜色特征描述，建立灰度和色彩视觉词汇。
2048个词汇和124个视觉单词用于灰度和色彩描述。
各个局部特征描述被词汇中最近的视觉单词的指数取代。
第三，各个帧分为四个有10%的重叠的象限和每个象限被计算的功能包。
4个串联的直方图产生一个大小为d=8688的载体，这些载体被看做是用来描述帧的（图1，底部）。
第四，帧描述的一个中位数在固定的时间间隔内被计算，创造出视频DNA序列。
采取的间隔大小T与步长ΔT有关。
一个类型的选择是T=2sec和ΔT=1sec。
因此视频DNA是一个我们称之为视觉类比生物DNA核苷酸，它是d功能包的定时序列。
两个视频的相似性通过测量相应的视觉核苷酸间的距离来定量，这些用dA来标志。
在最简单的情况下，欧氏距离在Rd
中使用。
在【26】中，结果表明欧氏距离，一个由视觉词（词频逆文件频率或tf-idf）的统计分布加权，是一个更好的比较功能包的方法。
我们将解决第四章中视觉核苷酸之间最佳距离的重建问题。
表1：
视觉核苷酸的构建。
顶部：
视频帧中检测到的特征。
底部：
相应的功能包。
在应用了功能包的散列的相似维护后，帧用64位二进制数223E9DF01ADB3E00来代替。
3.搜索和对齐
用于调整生物的DNA序列。
特别是NW【23】和SWART【27】算法的动态规划能够用于发现不同视频版本之间的相关性
设x=（x1,.......,xm）和y=（y1,.....yn）;xi,yi是两个不同的视频DNA序列，代表不同时间编辑的同一视频的不同版本。
在这种情况下，x和y通常会有相似的核苷酸序列。
为了找到这样的相似性，我们在x和y之间需找一条最佳的直线，即这样的相关指数f1,.........,Ng和f1,.....Mg。
一方面将使相应的核苷酸最相似，另一方面将包含最小总长度的空白。
相关的程度用一个相似的得分来代表，同时考虑到核苷酸和空白区的相似性。
在长度i中x的子链和长度j中y的子链间的最低相异得分由以下递推方程给定。
其中i=1，.....,M;j=1,.....,N和si0=s0j=0对于所有的i=0,....,M;j=0,...,N.dA（a,b）是核苷酸间的相似性；g（a）是空白损失。
S的值由动态规划决定，最佳相关性由回归线[27]建立。
3.1快速启发式
动态规划方法的主要缺点是其高复杂度为0（nm）。
在我们的应用中，当一个短序列（对于一个典型的电影假设ΔT为1秒的
的N顺序）和一个包括数千署名或数百万小时的视频（M在
的顺序内）的数据库比较，这样的方法可能使计算望而止步。
一个相似的复杂问题在生物信息学基因的搜索中被遇到，那里典型的数据库包括序列数百万或数十亿的信息。
为了克服这个问题，如FASTA【24】和BLAST【1】格式的快速启发式已经制定出来。
这些方法的核心思想是首先找到与固定大小为K（在2和10之间变化）的相匹配的核苷酸，建立在两个序列的多个区域之间的初始对应。
使用搜索引擎的术语，最初的由FASTA和BLAST算法建立对应是一个短的候选人名单。
后来初始对应被重新定义为用SWAT算法的带状版本，应用在初始区域周围的序列。
在这个阶段，视频DNA序列在高分辨率下可以使用。
3.2多序列对齐
在众多情况下，希望在两个以上的视频间找到对齐，这与生物信息学上多序列对齐的问题类似。
为了发现在DNA序列间的进化关系，MSA用于系统发育分析【19】。
在视频中，一个类似的问题是版本控制，在那里给出了多个视频版本并希望创立，例如，他们是来自哪些源，哪些序列是原序列。
MSA中动态规划对齐算法简单的概括导致了指数的复杂性。
处于这个原因，使用了次优启发式像进步的序列对齐。
例如，在CLUSTAL【28】中，首先所有的序列对分别对齐。
对齐的花费作为成对序列相异性的衡量。
鉴于两两相异的矩阵指导树由集群的方法构建（例如，相邻的连接）。
最后，成对对齐的系列在以下树上分支程序中执行。
这样，大多数相似的序列首先被对齐，而且最不同的序列最后被对齐（详尽的算法描述见【28】）。
4.突变-不变性的度量
视频后期制作转换类似于生物DNA序列中的突变，并且无论是作为插入或由时间编辑结果导致的视觉核苷酸（插入的缺失突变）的删除，或作为替代突变都可以被证明。
其中，可视内容是由另一空间编辑结果取代，如分辨率或高宽比的改变，剪切，压缩损伤，字幕叠加或通道标志等等。
虽然局部对齐通过对差距损失的适当选择在应对插入或删除突变是有效的，但是替代突变是一个重大的挑战，因为它们可能对整个视频DNA序列有全面的影响（想象一下，例如，由于视频的非均匀缩放，在每个帧上有功能包的变化。
）
在生物的DNA序列分析中，基因突变的确切机制尚不能完全被理解或转载；因此，使用核苷酸突变的概率的经验模型【5】。
在我们的案例中，另一方面，很容易重现后期制作处理中在视频DNA中引起的突变。
理想情况下，我们的视觉核苷酸应是有辨别力的（这样两个属于不同视频的区间是相似的）和不变的（这样相同区间的两个转换是相似的）。
虽然我们视觉核苷酸的建设是依赖于特征描述，这些描述对某些帧的转换（规模，温和的度量和对比度的变化）是不敏感的，但是其他的转换（如裁剪，字幕叠加等）可能会导致不同的视觉核苷酸。
因此，简单的欧几里得度量在这样的转换中不会是不变的。
然而，从培养集上的核苷酸上研究最好的突变-不变性的度量是可能的。
假设我们被给定核苷酸X的一个集合，X用于描述不同的视频的不变性和所有被期望的转换的不变性的T变换。
我们用P值函数
，用
表示所有的正对的集合（相同间隔的视觉核苷酸，一些变换不同的核苷酸）。
负对通过从已知的截然不同的视频中进行许多时间间隔的抽样作为蓝本。
至于正对，我们从T变换中生成典型的转换。
我们的目标是找打一种核苷酸中的度量，这些核苷酸在正集中尽可能小并且在负集中尽可能大。
Shakhnarovich认为参数的度量公式是：
其中，
是在长度为n的二进制序列上的n维汉明空间
中的汉明度量。
A和b是一个n*d的矩阵和一个n*1的向量，依次使度量参数化。
我们的目标是去找到A和b，这样dA,b反应了培养集上成对的视觉核苷酸x,x'的相似性。
理想情况下，我们宁愿实现dA,b（x,x'）≤do,当（x,x'）ϵP,和dA,b（x,x'）>do,当（x,x'）ϵN，这里do是一些起始点。
实际上，很少实现dA，b的分布。
b在P和N中的亮度色度干扰，导致了正数（dA,b≤d0）和负数（dA,b>d0）的不真实。
因此，最优的A，b应该将这些亮度色度干扰降至最低。
在【25】中，Shakhnarovich认为学习最优参数是一个推动二进制分类的问题，那里，dA,b充当一个强的二进制分类器，并且每个符号的维性预测（Akx,bk）作为一个弱的分类器考虑。
这样，AdaBoost算法可用于逐步构建A和b，这将是一个公式（4）很期待的解。
在第K迭代中，矩阵A的第K行和向量b的第K个元素可以发现公式（4）的最小化加权版本。
运用AdaBoost标准算法的重量表【7】，假正数和假负数对的分量在增加，真正数和真负数的分量在降低。
虽然很难去发现Ak公式（4）由于非线性在减少，但是我们发现指数衰减的极小值与另一个简单的问题相关。
其中，Cp和Cn分别是正对和负对的协方差矩阵。
可以证明Ak公式（5）的最大化是
的最大广义特征向量。
由于公式（4）和公式（5）的极小化的实现不一致，在我们的成就中，选择了一个跨越最大是个特征向量的子空间。
此外，方向的选择与阈值参数b使指数衰减最小化的方法一样。
上面所描述的方法有一些优势。
首先，矩阵dA,b被构造去实现培养集中核苷酸序列的合理性和不变性。
如果培养集有足够的代表性，这样的度量能很好地推广。
在第三章描述的对齐和搜索算法中它可以用作dA。
其次，投影本身有降维的效果，并且导致了视觉核苷酸的一个非常紧凑的描述作为代码（例如，图1的框架所代表的十六进制数223E9DF01ADB3E00）。
这些代码可以有效地在标准数据库中存储和操纵。
第三，现代CPU架构允许汉明距的有效计算用位计算和SIMD指令。
由于每个位可以单独计算，对齐算法中的得分计算可以进一步在多个CPU上并行使用或共享，或分布式存储。
由于代码的描述紧凑，搜索可以在内存中进行（一个8GB的记忆系统足以在n=64时，存储1秒分辨率约30万小时的视频）。
5.结果
在实验验证中，我们在一个来自DVD包含了1013小时的各类视频内容（电影，二维和三维的动画片，访谈节目，体育）的数据库中进行。
视频DNA序列用T=2秒和ΔT=1秒来计算。
64维汉明空间被用作代码描述。
公制学习在一个离线的包含2*100000个正对和8*100000个负对的培养集上进行。
用Avisynth的构架服务器模拟转换创造了正对。
大规模搜索。
对于搜索和对齐的评价，我们使用了一个被【17】提出的表格。
从数据库中随机选取短序列用作查询。
这些查询以这样一种方式来构建，与数据库只有一个正确的匹配。
在BLAST和FASTA型算法中，查询代表了新的核苷酸序列。
用于构建初始匹配。
这些查询进行转换（如图2所示），用于后期制作，包括空间和像素转换（剪裁，信邮筒，对比度和色彩平衡，压缩噪声，分辨率，高宽比变化，字幕叠加）和时间转换（帧率改变和时间漂移）。
每个转换有多种强度（1-3）。
与查询匹配的局部短序列在数据库中被发现。
使用了第三章所述的FASTA/BLAST算法。
匹配精确度被测量作为1号回归线的精度，即，第一个正确匹配的百分率。
如果它们在1秒内的误差远离实际匹配的误差，则认为匹配正确（即我们表示的时间分辨率下降）。
典型的搜索时间为250秒。
表1显示了搜索精度的分析是根据转换型和强度来确定的。
每10秒长度进行10770次查询。
表2显示
图2：
在我们的实验中使用了转换的例子。
顶部：
几何变换（非统一尺度，剪裁，信箱和边框）。
底部：
像素转换（模糊，量化，字幕）。
搜索精度作为查询长度（从5到30秒）函数；在一个20160次查询装置上，包括强度1-3的所有转换。
表明在一个包含重大转换长达1013小时的视频数据库中，10秒的视频是足以达到小于3%的搜索错误。
一个20秒的查询，该数字下降至低于1%。
局部对齐。
为了去评估局部对齐，我们从含有将近300小时的视频的数据库子集中执行序列对齐。
这些视频用的第三章中的动态规划算法。
查询序列经历了先前的空间和时间的转换。
后者包括了视频的删除，与其他视频的替换，在黑暗周期的插入（不同连续时间内清晰的或逐步的淡入和淡出的过渡），视频播放的局部加速和减速，以及从原始素材的查询序列的重要部分的删除。
表3显示了对齐精度的分析依据于转换类型和强度。
来自绝望的主妇系列的视频序列的两个对齐版本的一个例子如图3所示。
系统发育分析。
图4显示了一个树状图，该图代表了来自表3中绝望的主妇的六个版本间的关系。
版本x,y通过从序列x上去除一个镜头而得到。
树状图由两两序列的距离（在对准的成对的序列中，被计算作为空白长度与全序列长度的比例）矩阵来构建。
这些距离使用的是临近连接的方法。
人们可以清楚地看到后来的版本是如何被推到的。
图3：
上面：
由于编辑，一个视频的两个版本有不同的时间表。
下面：
基于视频DNA的对齐引出了两个时间表的相关性。
表1：
精确度（第一个匹配1秒内的下降误差百分比）下降依据于转换类型和强度。
图4：
绝望的主妇的6个版本的系统发育分析。
在树状图中的每一个分支代表一个序列，根据它的版本来标记（如图1.1，序列采用使用了消除镜头的方法的序列1）。
垂直轴代表版本间的距离，被计算作为不同部分的百分比。
版本之间的进化关系，可以由树状图清楚地推断出来。
表2：
精确度（第一个匹配1秒内下降误差的百分比）作为以秒为单位的查询长度函数。
表3：
精确度（第一个匹配1秒内下降误差的百分比）下降依据于转换类型和强度。
6.结论
我们指出了一个强大和紧凑型视频描述框架。
通过运用基因序列和视频间的类比，我们采用了生物信息学算法，这种算法允许视频序列的有效搜索和对齐。
此外，我们发现使用公制研究是有可能在视频转换的培养集中设计出一种最佳度量。
我们相信收获视频和收获公共领域的相关元数据和创建一个有评注的与搜索和对齐工具一起的视频DNA序列的数据库，能够像基因研究中的人类基因组项目那样产生相似的影响力。
例如，有一个包括大多数流行的好莱坞电影署名的数据库将允许识别和同步电影的任何版本，无论何时，何地，从哪个源播放。
该数据库能够用来寻找网上电影的副本和版本，以应对盗版行为，增强视频字幕内容，如元数据，或为上下文广告提供关键字。
最后，通过使用数据库中相似视频的匹配信息，人类注释和语义信息使视频得以理解。
参考文献
[1]S.F.Altschul,W.Gish,W.Miller,E.W.Myers,andD.J.Lipman.Basiclocalalignmentsearchtool.J.MolecularBiology,215:
403–410,1990.3,7
[2]H.Bay,T.Tuytelaars,andL.VanGool.SURF:
Speededuprobustfeatures.LectureNotesinComputerScience,3951:
404,2006.4,5
[3]O.BoimanandM.Irani.Detectingirregularitiesinimagesandinvideo.IJCV,74
（1）:
17–31,2007.3
[4]O.Chum,J.Philbin,M.Isard,andA.Zisserman.Scalablenearidenticalimageandshotdetection.InProceedingsofthe6thACMinternationalconferenceonImageandvideoretrieval,pages549–556,2007.4,5
[5]M.O.Dayhoff,R.Schwartz,andB.C.Orcutt.Amodelofevolutionarychangeinproteins.Nat.Biomed.Res.Found.,pages345–358,1978.9
[6]M.Douze,A.Gaidon,H.Jegou,M.Marszalek,andC.Schmid.INRIALEAR’svideocopydetectionsystem.InProc.TRECVID,2008.3
[7]Y.FreundandR.E.Schapire.Adecision-theoreticgeneralizationofon-linelearningandanapplicationtoboosting.InProc.EuropeanConf.ComputationalLearningTheory,1995.10
[8]A.Hampapur,K.Hyun,andR.Bolle.Comparisonofsequencematching
techniquesforvideocopydetection.InConf.onStorageandRetrievalforMediaDatabases,pages194–201,2002.4
[9]X.S.Hua,X.Chen,andH.J.Zhang.Robustvideosignaturebasedonordinalmeasure.InProc.ICIP,2004.4
[10]P.Indyk,G.Iyengar,andN.Shivakumar.Findingpiratedvideosequencesontheinternet.1999.4
[11]InternationalHumanGenomeConsortium.Finishingtheeuchromaticsequenceofthehumangenome.Na
升级会员 