通过数据库（数百万），指纹查找重复的视频文件？模式识别？

Question

在以下情况下：

我得到了一个目前约有一万个视频文件的目录的项目，该数字将大大增加。

但是，其中很多是重复的。对于每个视频文件，我都有关联的语义和描述性信息，我想合并重复，以便每一个都能获得更好的结果。

现在，我需要在数据库中索引元数据的某种过程，每当新视频输入目录时，都会计算出相同的数据并与数据库中的数据匹配。

问题是视频不是精确的重复。它们可以具有不同的质量，是Amby裁剪，水印或具有续集/前传。或在开始和/或结束时被切断。

不幸的是，比较越好，CPU和内存的密度程度就越大，我计划实施几层比较，这些比较以非常优雅但快速的比较开始（Maby Video Lengh，耐受性为10％），最后以最终比较决定是否决定是否决定是否决定。它确实是重复的（那将是社区投票）。

因此，由于我有一个社区来验证以低失误比率提供“良好猜测”的结果。

所以现在我的问题是你们能想到哪些层次，或者您有更好的方法？

我不在乎创建元数据的努力，我有足够的奴隶来做到这一点。只是比较应该很快。因此，如果有帮助，我也可以将视频转换100次...

这是我目前的想法：

• 视频长度（秒）

• 第一帧图片分析

我会将图片重新置于缩略图大小并获取平均RGB值，然后如果此像素的颜色大于0或1表示的平均值，则由像素序列化像素。 mysql并进行布尔bit-sum（在内部由mysql支撑），并计算剩余的uneval lit（在内部得到支持，这将是二角弦的Levenshtein距离）

• 使用相同的VBR编解码器随着时间的推移而开发比特率

我将视频将视频编码为具有完全相同的设置的VBR视频。然后，我会在某些时间点（视频完成或绝对秒的视频百分比）查看比特率。然后，我们只分析视频的一部分）。与图片一样。 iif比特率更大，平均1否则为0。我们制作二进制字符串并将其存储在db中，并稍后计算Levenshtein距离

• 音频分析（随着时间的时间量，比特率和分贝变体，视频的比特率）

• 关键帧分析

图像comarision就像第一个和最后一个帧一样，但在钥匙帧位置？我们将使用与比特率钙熟悉的相同源文件，因为密钥帧很大，取决于编解码器和设置。

• 随着时间的推移发展颜色

也许让我们在图像中拿一个或多个区域/像素，看看它们如何随着时间的流逝而开发。以及abov的变化/低于平均水平。我认为黑色/白色就足够了。

• 向用户提出建议以供最终批准...

还是我走完全错误的方式？我认为我不能成为第一个遇到这个问题的人，但是我没有任何运气找到解决方案。

Answer 1

这是一个巨大的问题，因此我选择编写一个相当漫长的答复，以尝试将问题分解为可能更容易解决的部分。

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

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

前两个步骤的成本是视频数量O（1）。最后一步的成本必须比O（1）差，可能会更糟。因此，我们的主要目标应该是最大程度地减少最后一步的成本，即使这意味着添加许多早期的简单步骤。

此过程的最佳算法将在很大程度上取决于数据库的特征，即单个匹配和多个匹配的级别。如果100％的视频与其他视频匹配，那么我们将希望最大程度地降低成功匹配的成本。但是，更有可能的情况是比赛将很少见，因此我们希望最大程度地减少不成功的比赛的成本。也就是说，如果有一种快速而肮脏的方法可以说“这两个视频不能成为匹配”，那么我们应该先使用它，然后才开始确认匹配。

要表征数据库，请首先进行一些采样和手工匹配以估计数据库中的匹配程度。该实验应该显示冗余视频如何“结合”：如果给定的视频有匹配，那么它的可能性超过了一场比赛？所有比赛中有多少百分比也是多次匹配的一部分？此过程将产生数据库（统计分布）的“模型”，该数据库将用于帮助算法选择并调整系统。

展望未来，我会认为比赛相对罕见。毕竟，如果有很多匹配项，则视频将“结块”，有效地使数据库较小，从而使问题变得更加简单。让我们假设问题尽可能难。

我主张一种多级分类方法，在其中我们构建了一系列算法，该算法反复执行“这两个视频不匹配” /“这两个视频可能匹配”的二进制决定。链中只有最后一个算法才能输出答案“这两个视频匹配”。

分类/匹配算法可以以两种或两种方式失败：false正面（非匹配视频被误认为是匹配的）和假否定的（匹配的视频被错误标记为无匹配）。这些错误的决策中的每一个都有与之相关的一系列概率，我们希望最大程度地减少两者。

由于我们正在构建算法管道，因此我们希望算法非常擅长识别无错误的不匹配，这意味着它们必须具有极低的错误拒绝率，而且我们不太关心虚假的接受率。例如，Wierd Al的视频克隆可能看起来和听起来很像原始视频，并且我们可能无法证明它直到算法管道后期才与原件匹配。

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

由于视频比较相对较难，因此让我们从音频开始。将数据库视为首先是可能包含重复项的MP3集合。毕竟，如果我们获得了一场良好的音频比赛，那么我们很可能会进行视频匹配，反之亦然。我们可以肯定地说，音频是视频的“公平”代表。幸运的是，快速的网络搜索将产生许多音频指纹和可靠，快速和成熟的比较软件包。数据库中的每个视频都需要生成音频指纹。缺少音轨的视频将自动落入“可能匹配”集中。

但是这里有一个“陷阱”：配音呢？如果给定的视频是两次编码，则有没有配音，它们是否是匹配？法国音频与西班牙语或英语呢？如果应该将这些都视为匹配，则可能需要跳过音频测试。

在这一点上，我们知道文件系统条目都“足够不同”，并且我们知道音轨都“足够不同”（如果已测试），这意味着我们不能再查看视频数据了。幸运的是，这只需要仅占视频数据库的一小部分，因此我们可以容忍一些成本。和以前一样，在我们尝试对比赛进行积极标签之前，我们仍然希望首先尝试快速消除更多的不匹配。

由于我们需要考虑解决方案的更改（例如，从1080p到iPod），我们将需要一种表征视频信息不仅是独立于解决的视频信息，而且还可以容忍添加的噪声和/或数据作为一部分丢失的噪声和/或数据。改变分辨率。我们必须忍受帧速率的变化（例如，从电影的24 fps到视频的30 fps）。纵横比也需要考虑的变化，例如从4：3 NTSC到16：9 HD。我们希望处理颜色空间的变化，例如从颜色到单色。

然后，有一些转换会立即影响所有这些，例如在HD和PAL之间转码，它们可以同时影响颜色空间，框架速率，纵横比和分辨率。该表征还应耐受一定程度的裁剪和/或填充，例如从4：3至16：9的宽高比之间来回切换（信箱，而不是Pan＆Scan）。我们还应该处理已被截断的视频，例如从功能电影结束时删除积分。而且，显然，我们还必须处理馈送相同视频流的不同编码器所产生的差异。

那是一个清单！让我们考虑一些我们可能会选择不考虑的事情：我怀疑在存在图像翘曲时找不到匹配，尽管事实上变形的翘曲并不少见，尤其是在直接直接的35毫米宽屏幕上扫描没有变形的重建（高肤色的人）。当框架中间存在大型水印时，我们也可能会选择失败，尽管我们希望忍受拐角处的较小水印。最后，可以无法匹配暂时扭曲或空间翻转的视频，例如一个是另一个是另一个的slo-mo，或者是从左到右的。

这仅仅覆盖了视频空间吗？希望很明显，为什么从文件系统和音频开始很重要！也就是说，首先将您的数据库视为MP3集合，然后将其视为视频集合。

忽略音频，视频只是静止图像的有序序列。因此，我们实际上正在寻找一种或多种图像比较算法与一个或多个时间序列比较算法相结合。这可以是一对单独的算法对（表征每个帧，然后表征帧的序列），也可以将其合并为单个算法（查看帧之间的差异）。

图像本身可以进一步分解成单色的“结构”图像和颜色“覆盖”。我相信，如果它在计算上很方便，我们可以安全地忽略颜色信息。

从上面的角度来看，听起来我认为我们必须完全解码视频才能对其进行任何比较。尽管编码数据的比较有许多限制其有用性的困难，但不一定是这种情况。一个重要的例外是对象级别的视频编码，例如MP4，在其中进行了非常高级的多框架比较。不幸的是，MP4流之间的对象比较并没有看到太多研究，我知道没有能力执行此功能的软件包。但是，如果找到一个，请使用它！

大多数其他数字视频流都使用编码方案，例如MPEG2，QuickTime或类似的内容。这些方案都使用了关键框架和差异帧的概念，尽管每个方案都以不同的方式实现。当比较不同的视频（不相同的视频）时，关键框架和差异框架不太可能与任何有用的程度匹配。但是，这并不意味着它是不可能的，并且存在包装，这些软件包试图从此类流中提取有用的信息而不执行完整解码。如果您发现一个快速的方法，它可能会属于“为什么不尝试”类别的测试类别。

我要使用的一个窍门是不是完全解码帧，而是将它们仅将其解码为单独的组件通道（HSV，HSL，YUV，其他任何），而不是一直到RGB Framebuffer（除非那是编码，当然是所编码的）。从这里开始，我接下来创建单独的亮度和色彩（颜色）帧，因此可以在相关域中进行比较。将一路解码到RGB FrameBuffer可能会引入错误，这可能会使查找匹配项更加困难。

接下来，我会丢弃颜色信息。由于单色视频应该匹配其颜色原件，因此我们根本不在乎颜色！

将产生的单色帧序列与另一个可能看起来非常不同的序列进行比较，但可能仍然可能是匹配的序列？从字面上看，这一领域已经进行了数十年的研究，其中大部分在“规模不变匹配检测”下进行了分类。不幸的是，这项研究很少直接用于确定视频何时进行匹配。

出于我们的目的，我们可以从多个方向解决此问题。首先，我们必须自己知道什么是单色域中的匹配和不是匹配。例如，我们不在乎像素级差异，因为即使两个匹配但不同的视频具有相同的分辨率，我们也必须忍受由于诸如编码器差异之类的噪声。

一个简单的（但缓慢）的方向是将每个图像转换为独立于分辨率和纵横比的形式。这样的转换是进入空间频域，而2D FFT是理想的选择。丢弃虚构组件后，可以在高频下截断实际的组件以消除噪声和低频以去除纵横比效应，然后将其归一化为标准尺度，从而消除了分辨率的差异。所得数据看起来像是一个奇怪的微小图像，可以在视频流中直接比较。

还有许多其他可能的框架转换策略，比FFT更有效，文献搜索应该突出它们。不幸的是，我知道在软件库中实施的很少有像FFT一样易于使用的。

一旦我们将单色帧转换为一个较小且更有用的域，我们仍然必须对另一个视频中的另一个此类流进行比较。而且该视频几乎可以肯定不是框架匹配，因此简单的比较肯定会失败。我们需要进行比较，该比较将在时间域上考虑差异，包括添加/删除的帧和帧速率差异。

如果您查看FFT框架的顺序，您会发现一些非常不同的行为。场景褪色突然且非常容易发现，也可以区分切割，通常在割之间的FFT中只有缓慢的变化。从FFT的序列中，我们可以将每个框架标记为切割/褪色后的第一个或切割/褪色之间的框架。重要的是，每个切割/淡出之间的时间，与它们之间的数字框架无关，这会产生签名或指纹，这在很大程度上与帧速率无关。

拿出整个视频的指纹产生的数据比视频本身小。它也是数字的线性序列，一个简单的时间序列向量，非常类似于音频，并且可以使用许多相同的工具进行分析。

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

我不会在这里进行2D FFT的比较，因为有大量的参考可以比我能做的要好得多。

注意：还有许多其他操纵（超出2D FFT）可以应用于单色框架以获得其他指纹。可以通过提取图像的内部边缘（从字面上像FBI指纹）或选择性地阈值进行图像并执行“ Blobbing”操作（创建相关区域描述符的链接列表）来创建实际图像内容的表示形式。跟踪帧之间边缘和/或斑点的演变不仅可以用于生成切割列表，而且还可以用于提取使用2D FFT丢失的其他高级图像特性。

我们已经构建了一系列比较算法，这些算法应该很快找到非匹配，并且不需要太多时间来确定匹配项。 las，具有算法不是解决方案的！我们必须考虑与这些算法如何最好地实施有关的几个问题。

首先，我们不想打开并阅读每个视频文件的次数，否则CPU可以停下来等待磁盘的数据。我们也不想将任何内容读取到所需的文件中，尽管我们不想太早停止阅读，并且可能会错过以后的比赛。是否应该保存每个视频的特征的信息，还是在需要时重新计算？解决这些问题将允许开发，测试和部署一个高效有效的视频比较系统。

我们已经表明，可以将视频与在高度可变条件下找到匹配和计算效率的希望进行比较。

其余的是作为读者的练习。 ;^）

Answer 2

好问题！只有测试才能说明其中哪些因素将是最佳指标。一些想法：

• 随着时间的流逝，比特率的开发使用相同的VBR编解码器：听起来很密集，但我想这将带来很好的结果。音频分析似乎会以更少的工作给出类似的结果。
• 首先和最后一帧图片分析：其中50％不会是黑人吗？一个更好的主意可能是使用中间框架，但我不会指望这种技术是可靠的。
• 使用贝叶斯统计 记录哪些因素为积极匹配带来最佳贡献。这可以在测试阶段进行，以消除无用且昂贵的比较。
• 让用户提供帮助！ 让用户将发现的重复分组在一起。他们对质量最佳的人进行投票，并且将充当小组中的主要/官方版本。
• 从最简单的比较开始 当您发现简单的测试的缺点时，添加更复杂的测试。视频长度将是一个很好的开始，然后是一些基本的音频分析，然后从那里开始工作。

Answer 3

只需尝试这个产品 - 重复的视频搜索 （例如，视觉搜索小马），可以找到各种比特率，格式，分辨率等的重复视频文件。

例如，Star -Wars.avi（640x480 H.264）和SW.MPG（1280x720 MPEG）将被检测为重复项，以防两者都是出色的电影 - 《星球大战》的副本。

根据他们的网站，该产品使用了一些视频指纹技术，例如键框式或SMTH。这样，请独立于视频编码，分辨率，质量，比特率和等。