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

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

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

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

要表征数据库，首先要进行一些采样和手动匹配，以确定数据库中的匹配程度。这个实验应该展示冗余视频如何“聚集”：如果给定的视频匹配，那么多于一次匹配的可能性有多大？所有比赛的百分比也是多场比赛的一部分？该过程将产生数据库的“模型”(统计分布)，该模型将用于帮助算法选择和调整系统。

展望未来，我将假设比赛相对较少。毕竟，如果有很多匹配，视频将“聚集”，有效地使数据库变小，从而使问题更简单。让我们假设问题尽可能地保持不变。

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

分类/匹配算法可能以两种方式中的一种或两种方式失败：假阳性(非匹配视频被误认为匹配)和假阴性(匹配视频被错误标记为不匹配)。这些错误决策中的每一个都有一系列与之相关的概率，我们希望最大限度地减少两者。

由于我们正在构建算法管道，我们希望算法能够非常好地识别不匹配的非匹配，这意味着它们必须具有极低的错误拒绝率，并且我们并不太关心错误接受率。例如，Wierd Al对视频的克隆可能看起来和声音非常像原始视频，我们可能无法证明它与原始视频不匹配，直到后来的算法管道中。

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

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

但这里有一个’陷阱’：画外音怎么样？如果给定的视频被编码两次，无论是否有画外音，它们是否匹配？法语音频与西班牙语或英语相比怎么样？如果这些都应该被认为是匹配的，那么可能需要跳过音频测试。

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

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

然后有一些转换同时影响所有这些，例如HD和PAL之间的转码，它可以同时影响色彩空间，帧速率，宽高比和分辨率。表征还应该能够容忍某种程度的裁剪和/或填充，例如在4：3和16：9纵横比之间来回切换(信箱，但不是扫描和扫描)。我们还应该处理已截断的视频，例如从功能影片的末尾删除信用。而且，显然，我们还必须处理由相同视频流提供的不同编码器所产生的差异。

这是一个很清单！让我们考虑一些我们可能选择不考虑的事情：我怀疑在图像变形存在的情况下找不到匹配是可以的，尽管变形翘曲并不罕见，特别是在直接35毫米宽屏电影中扫描没有变形重建(高瘦的人)。我们也可能选择在框架中间存在大水印时失败，但我们会想要容忍角落中较小的水印。最后，没有匹配时间扭曲或空间翻转的视频，例如当一个是另一个的慢动作，或者从左到右翻转时。

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

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

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

从上面可能看起来我可能认为我们必须完全解码视频才能对其进行任何比较。虽然编码数据的比较具有许多限制其有用性的困难，但情况不一定如此。对此的一个重要例外是对象级视频编码，例如MP4，其中已经执行了非常高级的多帧比较。不幸的是，MP4流之间的对象比较还没有多少研究，我知道没有能够执行此功能的包。但如果找到一个，请使用它！

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

我将使用的一个技巧是完全解码帧，而不是将它们解码为单独的组件通道(HSV，HSL，YUV，无论如何)，而不是一直到RGB帧缓冲区(除非那是已编码的，当然)。从这里开始，我接下来会创建单独的亮度和色度(颜色)帧，因此可以在相关域中执行比较。一直解码到RGB帧缓冲区可能会引入错误，这可能使查找匹配更加困难。

接下来，我将丢弃颜色信息。由于单色视频应与原色相匹配，我们根本不关心颜色！

如何将最终的单色帧序列与另一个可能看起来非常不同的序列进行比较，但仍然可能匹配？在这方面已经进行了数十年的研究，其中大部分都是在“尺度不变的匹配检测”下进行的。不幸的是，这项研究很少直接应用于确定视频何时匹配或不匹配。

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

一种简单(但缓慢)的方法是将每个图像转换为独立于分辨率和纵横比的形式。一个这样的变换是进入空间频率域，并且2D FFT是理想的。在丢弃虚部之后，可以在高频处截断实部以去除噪声，并且在低频处去除实际分量以消除纵横比效应，然后归一化到标准尺度以消除分辨率差异。结果数据看起来像一个奇怪的微小图像，可以直接在视频流中进行比较。

还有许多其他可能的帧转换策略，许多比FFT更有效，文献检索应该突出它们。不幸的是，我知道很少有软件库中实现的那些像FFT一样容易使用。

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

如果你看一下FFT帧的序列，你会发现一些非常不同的行为。场景衰落是突然的并且非常容易发现，也可以区分切割，并且通常在切割之间仅在FFT中看到缓慢的变化。根据FFT的序列，我们可以将每个帧标记为剪切/淡入之后的第一个帧，或者作为剪切/淡入之间的帧。重要的是每次剪切/淡入淡出之间的时间，与它们之间的帧数无关，这会创建一个很大程度上与帧速率无关的签名或指纹。

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

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

我不会在这里进行2D FFT的比较，因为有大量的参考资料可以比我更好地完成这项工作。

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

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

首先，我们不希望打开和读取每个视频文件超过必要的次数，否则cpu可能会停止等待来自磁盘的数据。我们也不想进一步阅读文件而不是需要，尽管我们不想过早停止阅读并可能错过以后的比赛。是否应保存表征每个视频的信息，还是应在需要时重新计算？解决这些问题将允许开发，测试和部署高效且有效的视频比较系统。

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

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