通过数据库(百万)查找重复的视频文件,指纹?模式识别?

这是一个巨大的问题,所以我选择写一个相当长的回复,试图将问题分解成更容易解决的部分。

使用可用的计算和时间资源进行比较是很重要的:我怀疑一个需要几个月运行的解决方案在动态视频数据库中非常有用。数据库的大小可能会使云计算资源的使用变得不可行。因此,我们真正关心的是在几个不同的领域中每次比较的本地成本:1)数据存储,2)计算资源,3)时间。

需要考虑的一个关键成本是,从每个视频中提取所需的数据,以获得要使用的任何比较指标。一旦提取的数据可用,则必须考虑进行比较的成本。最后,必须进行匹配所有视频所需的比较。

前两步的成本是视频数量的O(1)。最后一步的成本必须比O(1)更糟,可能更糟。所以我们的主要目标应该是最小化最后一步的成本,即使这意味着要添加许多早期的、简单的步骤。

此过程的最佳算法将很大程度上取决于数据库的特性,即存在单个和多个匹配的级别。如果100%的视频与其他视频匹配,那么我们将希望最小化成功匹配的成本。然而,更可能的情况是,比赛将是罕见的,所以我们将要尽量减少失败的比赛成本。也就是说,如果有一个快速而肮脏的方式说“这两个视频不能匹配”,那么我们应该先使用它,然后再开始确认匹配。

为了描述数据库的特征,首先进行一些抽样和手工匹配,以估计数据库中的匹配程度。这个实验应该显示冗余的视频是如何“聚集”的:如果一个给定的视频有匹配,它有多可能有不止一个匹配?在所有比赛中,有多少百分比也是多场比赛的一部分?此过程将生成数据库的“模型”(统计分布),用于辅助算法选择和调整系统。

接下来,我假设比赛相对较少。毕竟,如果有大量的匹配,视频将“聚集”,有效地使数据库更小,从而使问题更简单。让我们假设问题尽可能地难以解决。

我提倡一种多层次的分类方法,在这种方法中,我们将构建一系列算法,重复执行“这两个视频不匹配”/“这两个视频可能匹配”的二进制决策。只有链中最后一个算法需要输出答案“这两个视频匹配”。

分类/匹配算法可能会以两种方式中的一种或两种方式失败:假阳性(不匹配的视频误认为匹配)和假阴性(匹配的视频误认为不匹配)。每一个错误的决策都有一系列与之相关的概率,我们希望将两者都最小化。

由于我们正在构建一个算法管道,我们需要非常擅长无错误地识别不匹配的算法,这意味着它们必须具有极低的错误拒绝率,而且我们不太关心错误接受率。例如,wierd al对视频的克隆看起来和声音可能与原始视频非常相似,我们可能无法证明它与原始视频不匹配,直到后来在算法管道中。

最简单、最快速、最可靠的算法应该首先运行,因为绝大多数测试都会产生“不匹配”的结果。最简单的检查是在数据库中搜索相同的文件,这是由许多快速简单的文件系统和数据库维护实用程序完成的。运行此扫描后,我们可以假定我们实际上需要打开和读取视频文件以检测差异。

由于视频比较比较比较困难,我们从音频开始。将数据库视为可能包含重复项的MP3集合。毕竟,如果我们有一个好的音频匹配,很可能我们会有一个视频匹配,反之亦然。我们可以放心地说,音频是视频的“公平”代表。幸运的是,快速的网络搜索将产生许多可靠、快速和成熟的音频指纹和比较包。需要为数据库中的每个视频生成音频指纹。缺少音频曲目的视频将自动进入“可能匹配”设置。

但这里有一个“抓住”的地方:那语音留言呢?如果一个给定的视频被编码两次,不管有没有声音,它们是匹配的还是不匹配的?法国的音频和西班牙语或英语的对比怎么样?如果这些都被认为是匹配的,那么可能需要跳过音频测试。

此时,我们知道文件系统条目都“足够不同”,而且我们知道音频轨都“足够不同”(如果测试过),这意味着我们不能再推迟查看视频数据。幸运的是,这只需要对视频数据库的一小部分进行,因此我们可以容忍一些成本。和以前一样,我们仍然希望首先快速消除更多的不匹配项,然后再积极标记匹配项。

由于我们需要考虑分辨率变化(例如从1080p到iPod),我们需要一种方法来描述视频信息,它不仅与分辨率无关,而且能够容忍在更改分辨率时增加的噪声和/或丢失的数据。我们必须容忍帧速率的变化(例如,从电影的24帧到视频的30帧)。还需要考虑纵横比的变化,例如从4:3 NTSC到16:9 HD。我们希望处理颜色空间的变化,例如从颜色到单色。

然后会同时影响所有这些转换,例如HD和PAL之间的转码,这会同时影响颜色空间、帧速率、纵横比和分辨率。特征化还应能够容忍一定程度的裁剪和/或填充,例如,从4:3和16:9纵横比之间来回切换时会发生这种情况(字母框,而不是平移和扫描)。我们还应该处理被截断的视频,例如从一部电影的结尾删除片头。很明显,我们还必须处理由不同的编码器产生的差异,这些编码器被输入相同的视频流。

这真是一张清单!让我们考虑一些我们可能选择不考虑的事情:我怀疑当图像扭曲存在时,找不到匹配是可以的,尽管变形扭曲并不罕见,特别是在35毫米宽的电影,直接扫描没有变形重建(高瘦的人)。我们也可能选择失败时,大型水印存在于帧的中间,虽然我们将要容忍较小的水印在角落。最后,不匹配那些被暂时扭曲或空间翻转的视频是可以的,比如当一个视频是另一个的slo-mo,或者是从左向右翻转的视频。

这仅仅是为了覆盖视频空间吗?希望能够清楚地知道为什么从文件系统和音频开始是很重要的!也就是说,在将数据库视为视频集之前,首先要将其更像MP3集。

忽略音频,视频只是静态图像的有序序列。所以我们实际上在寻找一个或多个图像比较算法和一个或多个时间序列比较算法的结合。这可以是一对单独的算法(描述每个帧,然后描述帧序列),也可以合并为一个单独的算法(查看帧之间的差异)。

图像本身可以进一步分解为单色的“结构”图像和彩色的“叠加”。我相信如果计算上方便的话,我们可以安全地忽略颜色信息。

从上面看来,我认为我们必须完全解码一个视频,以便对其进行任何比较。虽然比较编码数据有许多困难,限制了它的实用性,但情况未必如此。其中一个重要的例外是对象级视频编码(如MP4),在MP4中执行了非常高级别的多帧比较。不幸的是,MP4流之间的对象比较没有看到太多的研究,我知道没有任何包能够执行此功能。但如果你找到了,就用它!

大多数其他数字视频流使用编码方案,如MPEG2、QuickTime或类似方案。这些方案都使用关键帧和不同帧的概念,尽管每个框架的实现方式不同。当比较不同的视频(大小不同的视频)时,关键帧和不同帧不太可能匹配到任何有用的程度。然而,这并不意味着这是不可能的,并且存在一些包试图从这些流中提取有用的信息而不执行完全解码。如果你找到了一个快速的,它可能属于“为什么不尝试它”的测试类别。

我将使用的一个技巧是不完全解码帧,而是只将它们解码为单独的组件通道(hsv、hsl、yuv,无论什么),而不是一直解码到rgb帧缓冲区(当然,除非这是编码的)。接下来,我将创建单独的亮度和色度(颜色)帧,以便在相关领域进行比较。一直解码到RGB帧缓冲区可能会导致错误,这可能会使查找匹配更加困难。

接下来,我将放弃颜色信息。既然一个单色视频应该和它原来的颜色相匹配,我们根本不在乎颜色!

如何才能最好地将产生的单色帧序列与另一个可能看起来非常不同但仍可能匹配的序列进行比较?在这一领域已经有了几十年的研究,其中大部分被归为“尺度不变匹配检测”。不幸的是,这项研究很少直接用于确定视频的匹配时间。

出于我们的目的,我们可以从几个方向来处理这个问题。首先,我们必须自己知道什么是单色域中的匹配项,什么不是单色域中的匹配项。例如,我们不关心像素级别的差异,因为即使两个匹配但不同的视频具有相同的分辨率,我们也必须容忍某些级别的噪声,例如编码器差异。

一个简单(但缓慢)的方法是将每个图像转换成独立于分辨率和纵横比的形式。其中一个转换是空间频率域,而二维快速傅立叶变换是理想的。丢弃虚部后,可在高频处截断实部以去除噪声,在低频处截断实部以去除纵横比效应,然后归一化为标准尺度以消除分辨率差异。产生的数据看起来像一个奇怪的微小图像,可以直接在视频流之间进行比较。

还有许多其他可能的帧转换策略,许多比快速傅立叶变换更有效,文献搜索应该突出它们。不幸的是,我知道很少有在软件库中实现的软件库和fft一样容易使用。

一旦我们将单色帧转换成一个更小更有用的领域,我们仍然必须对另一个视频流进行比较。而且这段视频几乎可以肯定不会是帧对帧的匹配,所以一个简单的比较肯定会失败。我们需要一个考虑到时间域差异的比较,包括添加/删除帧和帧速率差异。

如果你观察FFT帧的序列,你会发现一些非常明显的行为。场景淡出是突然的,并且非常容易被发现,切割也可以被区分,并且在切割之间的FFT中通常只有缓慢的变化。从FFT序列中,我们可以将每个帧标记为剪切/淡入后的第一帧,或作为剪切/淡入之间的帧。重要的是每次剪切/褪色之间的时间,与它们之间的数字帧无关,这就创建了一个签名或指纹,这在很大程度上与帧速率无关。

获取整个视频的指纹会产生比视频本身小得多的数据。它也是一个数字的线性序列,一个简单的时间序列向量,很像音频,可以使用许多相同的工具进行分析。

第一个工具是执行相关性,以确定一个视频中的剪切模式是否与另一个视频中的剪切模式紧密匹配。如果有显著差异,那么视频是不同的。如果它们是一个密切的匹配,那么需要比较每个相关切割后的几个FFT,以确定帧是否足够相似以匹配。

这里我不讨论2dffts的比较,因为有大量的参考资料比我做得更好。

注意:有许多其他的操作(除了二维FFT)可以应用于单色帧以获得额外的指纹。可以通过提取图像的内部边缘(字面上类似于FBI指纹)或选择性地对图像进行阈值设定并执行“blobbing”操作(创建相关区域描述符的链接列表)来创建实际图像内容的表示。跟踪帧之间边缘和/或斑点的演变不仅可用于生成切割列表,还可用于提取使用二维FFT将丢失的其他高级图像特征。

我们构建了一系列比较算法,这些算法在查找不匹配项时应该非常快,并且不需要太多时间来确定匹配项。唉,拥有算法并不能解决问题!我们必须考虑与如何最好地实现这些算法相关的几个问题。

首先,我们不希望打开和读取每个视频文件的次数超过需要的次数,否则CPU可能会停止等待来自磁盘的数据。我们也不想在一个文件中读取任何超出需要的内容,尽管我们不想过早停止读取,可能会错过稍后的匹配。是应该保存每个视频的特征信息,还是应该在需要时重新计算?解决这些问题将允许开发、测试和部署一个高效的视频比较系统。

我们已经证明了将视频与在高度可变的条件下寻找匹配的希望进行比较的可能性,以及计算效率。

剩下的部分留给读者做练习。^)

好问题!只有测试才能知道哪些因素是最好的指标。一些想法:

• 随着时间的推移,使用相同的VBR编解码器开发比特率:听起来CPU非常密集,但我认为这会产生很好的效果。音频分析似乎能以较少的工作量得出类似的结果。
• 第一帧和最后一帧图片分析:50%的图片不是黑色的吗?一个更好的主意可能是使用非常中间的框架,但我不指望这种技术是可靠的。
• 使用贝叶斯统计 记录哪些因素对正匹配做出了最好的贡献。这可以在测试阶段完成,以消除无用和昂贵的比较。
• 让用户帮忙! 让用户将找到的重复项组合在一起。他们投票选出质量最好的一个,该版本将作为集团内的主要/官方版本。
• 从最简单的比较开始 当您发现简单测试的缺点时,可以添加更复杂的测试。视频长度将是一个很好的开始,然后可能一些基本的音频分析,并从那里开始工作。

试试这个产品- Duplicate Video Search (例如视觉搜索小马),可以找到各种比特率、格式、分辨率等的重复视频文件。

例如,星战.avi(640x480 h.264)和sw.mpg(1280x720 mpeg)将被检测为副本,以防它们都是一部伟大电影《星球大战》的副本。

根据他们的网站,该产品使用一些视频指纹技术,如关键帧exctraction或smth。像这样,必须独立于视频编码、分辨率、质量、比特率等。