视频基因

视频基因[e-mail]@[e-mail]n,Haifa32000,IsraelMarch30,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中引起的突变。理想情况下