language-agnostic - 通过数据库(百万)，指纹查找重复的视频文件？模式识别？

Question

在以下情况下:

我有一个项目，该项目的目录目前包含大约一万个视频文件，并且数量将急剧增加。

但是它们很多都是重复的。对于每个视频文件，我都有关联的语义和描述性信息，我希望将这些信息合并在一起，以使每个视频文件获得更好的结果。

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

问题是视频并非完全重复。它们可以具有不同的质量，被裁剪，加水印或具有续集/前传。或在开始和/或结束处切断。

不幸的是，比较效果越好，cpu和内存就越多，所以我计划实现几层比较，这些步骤以非常优雅但快速的比较开始(Maby Video lengh，容差为10％)，最后以最终的比较决定是否它确实是重复的(这将是社区投票)。

因此，当我有一个社区来验证结果时，就足以以较低的未命中率提供“良好的猜测”。

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

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

这是我目前的想法:

视频长度(秒)

第一帧和最后一帧图像分析

我将图片重新采样为缩略图大小，并获取平均rgb值，然后如果该像素处的颜色大于/小于由0或1表示的平均值，则逐个像素地序列化。因此，我得到了一个二进制字符串，可以将其存储到其中mysql并做一个 bool(boolean) 位和(由mysql内部支持)并计算剩余的unval位(内部也支持，这将是bianry字符串的Levenshtein距离)

使用相同的vbr编解码器

比特率随时间的发展

我将使用完全相同的设置将视频转码为vbr视频文件。
那么我将查看某些时间点的比特率(已完成视频的百分比或绝对秒数。然后，我们将仅分析视频的一部分)。
与图片相同。如果比特率大于平均值，则为1，否则为0。
我们制作一个二进制字符串并将其存储在db中，然后计算Levenshtein距离

音频分析(随时间变化的比特率和分贝变化与视频的比特率一样)

关键帧分析

图像协调就像第一帧和最后一帧一样，但是在关键帧位置？我们将使用与比特率计算相同的源文件，因为关键帧在很大程度上取决于编解码器和设置。

颜色随时间的发展

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

向用户展示建议，以供最终批准...

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

Answer 1

这是一个很大的问题，因此，我选择写一个较长的答复，以尝试将问题分解为可能更易于解决的部分。

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

要考虑的一项关键成本是，无论使用哪种比较指标，都需要从每个视频中提取所需的数据。一旦提取的数据可用，则必须考虑执行比较的成本。最后，必须执行将所有视频相互匹配所需的比较。

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

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

为了表征数据库，首先进行一些采样和手动匹配，以估计数据库内的匹配程度。该实验应显示出冗余视频是如何“聚集成团”的:如果给定视频有匹配项，那么多于一个匹配项的可能性是多少？所有比赛中有多少百分比也是多重比赛的一部分？该过程将产生数据库的“模型”(统计分布)，该模型将用于辅助算法选择和调整系统。

展望 future ，我认为比赛是相对罕见的。毕竟，如果有很多匹配项，视频将“结块”，有效地使数据库变小，从而使问题更简单。让我们假设问题仍然存在。

我主张采用多级分类方法，在该方法中，我们将构建一系列算法，重复执行“这两个视频不匹配” /“这两个视频可能匹配”的二元决策。只有链中的最后一个算法才需要输出答案“这两个视频匹配”。

分类/匹配算法可能会以两种方式中的一种或两种方式失败:误报(误匹配的视频被误标记为匹配)和误报(误匹配的视频被误标记为不匹配)。这些错误的决定中的每一个都有一系列相关的概率，我们希望将两者最小化。

由于我们正在构建算法流水线，因此我们希望算法能够很好地识别无错误的不匹配项，这意味着它们必须具有极低的错误拒绝率，并且我们不太关心错误接受率。例如，Wierd Al的视频克隆可能在外观和声音上都非常类似于原始视频，并且在算法管道中的稍后阶段，我们可能无法证明它与原始视频不匹配。

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

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

但是这里有一个“陷阱”:旁白怎么样？如果给定视频经过两次编码(带或不带旁白)，它们是否匹配？法语音频与西类牙语或英语呢？如果这些都应视为匹配项，则可能需要跳过音频测试。

至此，我们知道文件系统条目都“足够不同”，并且我们知道音轨都“足够不同”(如果经过测试)，这意味着我们不能再推迟查看视频数据了。幸运的是，只需要对视频数据库的一小部分进行此操作，因此我们可以承受一些费用。和以前一样，我们仍然希望先尝试快速消除更多不匹配项，然后再尝试对匹配项进行正面标记。

由于我们需要考虑分辨率的变化(例如，从1080p到iPod)，因此我们将需要一种表征视频信息的方法，该信息不仅与分辨率无关，而且可以容忍作为噪声一部分而添加的噪声和/或数据丢失。更改分辨率。我们必须容忍帧速率的变化(例如，从电影的24 fps到视频的30 fps)。还需要考虑宽高比的更改，例如从4:3 NTSC到16:9 HD。我们将要处理颜色空间的更改，例如从彩色更改为单色。

然后有一些转换会立即影响所有这些转换，例如HD和PAL之间的转码，这些转换会同时影响色彩空间，帧速率，宽高比和分辨率。表征还应容忍某种程度的裁剪和/或填充，例如在4:3和16:9宽高比之间来回切换时会发生(字母框，但不能平移和扫视)。我们还应处理已被截断的视频，例如从长片结尾删除字幕。而且，显然，我们还必须处理由不同编码器提供的相同视频流产生的差异。

相当多的 list !让我们考虑一些我们可能会选择不解释的事情:我怀疑存在图像变形时可以找到匹配项是可以的，尽管变形变形并不罕见，尤其是在35mm宽屏电影中无需变形重建即可扫描(瘦高个子)。当帧的中间出现大水印时，我们也可能会选择失败，尽管我们希望容忍角落中较小的水印。最后，也可以不匹配在时间上已失真或在空间上发生了翻转的视频，例如，当一个是另一个的慢 Action 时，或者已经从左向右翻转时。

这仅覆盖视频空间吗？希望很清楚为什么从文件系统和音频开始很重要!也就是说，在将数据库视为视频集合之前，首先将其视为MP3集合。

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

图像本身可以进一步分解为单色“结构”图像和彩色“叠加”。我相信我们可以放心地忽略颜色信息，只要这样做在计算上很方便。

从上面看来，听起来我已经假设我们必须完全解码视频才能对其进行任何比较。尽管编码数据的比较存在许多限制其实用性的困难，但不一定是这种情况。一个重要的异常(exception)是对象级视频编码，例如MP4，其中已执行了非常高级的多帧比较。不幸的是，MP4流之间的对象比较还没有进行太多研究，并且我知道没有能够执行此功能的软件包。但是，如果找到一个，请使用它!

大多数其他数字视频流使用诸如MPEG2，Quicktime之类的编码方案。这些方案都使用关键帧和差异帧的概念，尽管它们的实现方式不同。当比较不同的视频(大小不同的视频)时，关键帧和差异帧不太可能匹配到任何有用的程度。但是，这并不意味着不可能，并且存在尝试从此类流中提取有用信息而不执行完全解码的程序包。如果您发现速度很快，则可能属于“为什么不尝试”测试类别。

我将使用的一个技巧是，不是完全解码帧，而是仅将它们解码到单独的分量通道(HSV，HSL，YUV等)中，而不是一直解码到RGB帧缓冲区中(当然，除非已编码) )。接下来，我将从此处创建单独的亮度和色度(颜色)帧，以便可以在相关域中进行比较。一直解码到RGB帧缓冲区可能会引入错误，这些错误可能会使查找匹配项变得更加困难。

接下来，我将丢弃颜色信息。由于单色视频应与其原始颜色匹配，因此我们根本不在乎颜色!

如何将所得的单色帧序列与可能看起来非常不同但仍然可能匹配的另一个序列进行最佳比较？实际上，在该 Realm 已有数十年的研究，其中许多归类于“尺度不变匹配检测”。不幸的是，这项研究很少被直接用于确定视频何时匹配或不匹配。

为了我们的目的，我们可以从多个方向解决这个问题。首先，我们必须亲自了解单色域中的匹配项和不匹配项。例如，我们不关心像素级别的差异，因为即使两个匹配但不同的视频具有相同的分辨率，我们也必须容忍由于诸如编码器差异之类的某种程度的噪声。

一种简单(但很慢)的前进方式是将每个图像转换为与分辨率和纵横比无关的形式。一种这样的变换是进入空间频域，而2D FFT对此是理想的。丢弃虚数分量后，可以在高频处截断实部分量以消除噪声，在低频处截断实部分量以消除纵横比效应，然后将其标准化为标准比例以消除分辨率差异。生成的数据看起来像一个奇怪的微小图像，可以在视频流之间直接进行比较。

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

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

如果查看FFT帧的序列，您会注意到一些非常不同的行为。场景渐变非常突然，非常容易发现，还可以区分剪切，并且通常在剪切之间的FFT中只有缓慢的变化。从FFT序列中，我们可以将每个帧标记为剪切/淡入之后的第一帧，或标记为剪切/淡入之间的帧。重要的是每次剪切/淡入淡出之间的时间，与它们之间的数字帧无关，这会在很大程度上独立于帧频而创建签名或指纹。

拍摄整个视频的指纹后，所产生的数据将大大小于视频本身。它也是数字的线性序列，是简单的时间序列 vector ，非常类似于音频，并且可以使用许多相同的工具进行分析。

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

我不会在这里进行2D FFT的比较，因为有大量的引用文献比我做的要好得多。

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

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

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

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

其余部分留给读者练习。 ; ^)