视频指纹

音频指纹识别最常见的用例之一是电视广播监控。通过分析其音频流来生成有关播放的电视内容的详细报告。如果您想获得有关特定广告发生的准确统计信息，应用音频指纹识别可能看起来足够了。事实上，它在大多数情况下都有效。但有时，广告商使用相同的音频流与修改后的视觉内容配对。在汽车和医疗保健行业，它实际上很普遍。视觉内容的变化可能很小，有时对于普通观众来说甚至是察觉不到的。但是，如果您想提取有关广告商、公司或竞争对手的更多信息，它会产生很大的不同。让我们从几个例子开始来概括这个问题。下面是一个丰田广告的例子，它使用与不同视频配对的相同音频流。当商业报价出现在屏幕上时，差异开始于第 10 秒。它在屏幕上停留 10 秒钟，向观众讲述。由于广告通常阅读速度快且语调相同，因此音频指纹算法可能无法区分它们。第一个示例中的差异很容易观察到。但视觉变化可能更不明显。按难度递增的顺序查看更多示例以检测不同之处。对于“国民”广告，不难发现差异——SiriusXM 文本出现在底部而不是顶部。 “GrubHub”稍微复杂一些——送货袋包含两个不同的标志。还有一个区别。随意深入了解广告以识别它。

以下两个略有不同的示例。尝试自行确定不匹配。护肤乳液广告包含两个不同的瓶子，更准确地说是不同的标签。在“Prevagen”广告中，退出屏幕上的标志不匹配——右下角的沃尔玛和 GNC。此外，对于汽车行业而言，具有不同的出口屏幕是很常见的。由于它们在不同地区播出，因此它们包含特定的经销商信息。以下是具有六个不同结尾的同一商业广告的示例。如果要区分这些广告，仅监控音频内容是不够的。这是视频指纹识别可以帮助您的地方。概述的问题有几个与业务相关的约束，我们在开发算法时必须考虑这些约束。实时数据源来自 1000 多个电视台，每天生成超过 24,000 小时的搜索内容 那么我们如何解决这个问题呢？首先，视频指纹可以被认为是图像搜索，其中图像是从视频中提取的实际视频帧流。视频的每一秒包含 30 个颜色帧，我们可以将其用作我们要检索和比较的参考点。

那些阅读过 SoundFingerprinting 算法描述的人可能会注意到一种模式。我们可以采用为音频搜索开发的 SoundFingerprinting 算法来检索视频帧吗？事实证明我们可以。专为频谱图检索设计的图像搜索对于视频帧非常有效。我们算法的第一步是降低输入视频内容的维度：插入的广告和实时查询。内容以各种格式编码，最常见的是 1080p 高清宽屏格式。这个分辨率对于多维搜索来说太大了。1920×1080 的颜色向量很难搜索。如果在一维数组中编码，其长度为 \(1920*1080*3 = 6,220,800\)。相反，现代近似最近邻搜索算法以高达 1,000 维的向量为基准。值得庆幸的是，我们不需要此分辨率来正确识别广告中的差异，因此让我们将其调整为 128x72 像素图像。在对多种选项进行试验后，我们发现此分辨率是最佳的。为了让您了解它有多小，请查看以 128x72 格式编码的视频。在此分辨率下，您仍然可以区分视频中的重要细节。相关信息将被保留。音频指纹算法中的相应步骤是下采样。以 44.1KHz 采样的高分辨率音频信号被下采样到 5.5KHz，保留了初始音频的最关键位。您可以用来选择调整大小参数的一个简单启发式方法是断言您尝试区分的信息是否在此过程中没有丢失。断言相对简单：可视化降采样的文件，并确保您仍然可以看到（或在音频算法的情况下收听）您试图保留的内容。如果您再也看不到它，那么信息很可能已经无法挽回地丢失了。

降低维度的下一步是将颜色模式编码到 [0, 255] 范围内。不需要保留原始 RGB，因为单色图像可以很好地保留原始图像。音频指纹算法中的相应步骤是将原始音频转换为单声道。在所有这些转换之后，我们实现了 675 倍的降维。我们的向量的长度现在是 9120。从图像中提取特征是一个令人难以置信的研究领域。值得庆幸的是，我们试图解决的问题有几个优点，使它变得更容易。视频中的帧具有稳定的比例和方向。我们只对 128x72 的图像进行操作，这些图像永远不会在任一轴上旋转。此属性极大地简化了任务，因为对于此类图像可以更快地完成特征提取。对图像的重要信息进行编码的特征是什么？人眼的基本能力之一是检测和区分形状。从核心来看，每个形状都是由边缘组成的。举个例子，想想晴朗的蓝天的图像。它几乎没有信息：所有像素都具有相同的值。现在想象一下蓝天中的一个白色平面。这个新图像包含由不同值的相邻像素（白色和蓝色）创建的边缘。这些边缘的存在增加了信息值图片。它突然变得对观察者更有意义。这就是为什么边缘检测是计算机视觉中如此重要的研究领域。看看当使用为边缘检测设计的简单滤波器对其中一个视频帧进行卷积时会发生什么。

它从图像中删除了所有非必要的部分，为我们留下了大脑认为有意义的形状——丰田标志和英文字母。可以说，图像最重要的特征是边缘。找到一种专注于对特征向量中的边缘进行有效编码的算法是我们任务的主要挑战。 Haar变换是最简单的正交小波变换。它在\(J=log2(n)−1\)尺度上进行运算，计算输入图像上的一系列粗尺度和细尺度系数。计算是什么意思多分辨率系数，为什么我们需要这个？更直接的解释是，离散 Haar 小波变换是在图像中寻找边缘的最简单方法之一。它在\(J\) 较小的尺度上识别它们。例如，大小为 512x512 像素的图像将生成 8 个粗尺度的系数。降低图像的分辨率是保留最突出边缘的巧妙技巧。您可以通过查看以下应用离散 Haar 小波变换后的视频帧示例来了解图像分辨率降低意味着什么 1。好奇的读者可能会注意到，所应用的变换是一种标准的小波变换，其中所有行都在所有列之前处理。这个决定是经过深思熟虑的，因为它被证明对其他人也能很好地工作。结果很有说服力。你可以注意到如何在越来越小的分辨率上检测到每一步的边缘。在减少原始向量维数的过程中，小波系数给了我们一个强大的机制。

我们在图像处理中使用的最后一步是按大小过滤小波系数，只保留少数几个。通过保留顶部小波系数，我们可以对图像中最重要的特征进行编码。经过大量实验，保留原始向量的 4%小波系数提供了最好的精度/召回率。在将原始图像帧减少到 9120 个浮点数的向量后，其中只有 365 个值不是零，我们可以应用近似最近邻搜索技术，最终以易于搜索和检索的格式对我们的帧进行编码。在这个阶段，我们可以使用与音频指纹算法相同的方法——局部敏感哈希。与音频指纹识别类似，我们将顶部 Haar 小波系数的稀疏向量视为一个集合。我们如何将实数向量视为一个集合？很简单——我们将顶部小波的符号编码为 10（正）和 01（负） 2.通过应用这个技巧，我们将小波系数数组转换为长度为 18,240 的布尔数组。因此，该决定使我们能够在比较两个集合的相似度 3 时使用 Jaccard 索引作为距离度量。Jaccard 索引作为两个集合之间的相似性度量。它们越相似，它就越接近 1。

应用于集合的 LSH 与欧几里得空间中使用的随机投影有很大不同。我鼓励您阅读 LSH 如何用于音频指纹识别，因为我提供了更详细的解释为什么随机最小哈希排列等效于随机投影时使用 Jaccard 距离度量 4. 实现有效的 LSH 模式需要多少个最小哈希排列？与音频指纹识别类似，我们使用 100 个最小哈希排列来生成随机集合排列。它对频谱图非常有效，所以我们决定对视频帧使用相同数量的排列。这 100 个最小散列排列会将生成的散列分组到 25 个散列表中，每个表有 4 个排列。选择的参数可能看起来是任意的，但它们不是。最小散列排列会同意的概率至少在哈希表之一中，由以下公式 5 给出： \[P = 1 - (1 - J^k)^L\] 其中 \(J\) 是 Jaccard 索引，\(k\) 是一个最小哈希排列的数量哈希表，以及 \(L\) 个哈希表。图 4. 至少一个哈希表匹配的概率随着数据点的相似性而增加。注意至少一个成功匹配的概率是如何工作的，几乎就像一个阶梯函数。当两个集合的相似度超过 50% 时，至少一个成功匹配的概率会急剧增加。这正是我们所需要的。过滤掉噪音，只有在它们相似时才能得到好的候选者。我们选择了 \(L=25\) 和 \(n=4\)，因为这种模式更宽容，从搜索请求中返回更多候选者。这种权衡是由视频帧匹配的细节驱动的。作为视频流来自各种来源，它们以不同的格式进行编码：4:3、16:9、1:1 在将其转换为规范格式时，不可避免地会引入转换伪像：像素化、混叠。算法容易受到这些问题的影响。因此更宽松的 LSH 模式是可取的。为了控制算法的敏感度，您还可以只考虑那些在多个哈希表中匹配的候选者。

图 5. 选择一个点必须匹配多少个哈希表才能被认为是候选点 注意如何随着相似度的增加，匹配的哈希表的数量也会增加。简单来说，如果你只需要分析那些被认为是候选的图像80% 相似，您只能检索在至少 5 个哈希表中匹配的候选者。我在开始这篇文章时举了一个例子，将不同的 Toyota 产品注入同一个广告。我们如何使用上述算法发现这些不同之处？我们首先将实时视频流查询发送到我们的 Emy 存储集群。由于每个第二个包含 30 帧，30 个查询点用于检索潜在候选者。我们得到一组匹配的帧并为每个广告重建最佳匹配路径。重建后，我们使用它来检测结果广告中的间隙。检测到间隙的区域，识别视频帧差异。对于第一个丰田示例，不同的商业报价与原始报价产生 10 秒的差距。我将留下关于如何从不同文章的结果帧重建最佳路径的细节。这本身就是一个需要解决的复杂问题，本质上是编辑距离问题的变体 6. 当原始和查询广告有微不足道的区别 - 即不同的标志或电话号码。提供的 LSH 算法不会区分它们，它不会在重建的最佳路径中产生间隙。这是预期的：我们不能让 LSH + Min-Hash 作为一种精确的检索算法，因为根据定义，它是近似最近邻搜索。为了能够检测到微小的变化，必须实施第 2 阶段验证。在重建最佳匹配路径后，我们应用简单的帧到帧比较，比较像素级别的差异。

对于帧间比较，我们的首选是 SSIM 方法。 SSIM 是用于衡量图像质量的指标，但没有什么能阻止我们比较通过 LSH 匹配的帧。由于它旨在检测噪声和压缩伪影，因此它也可以非常有效地检测图像中的细微差异。 SSIM 的问题在于计算方面，它非常昂贵。将其应用于过滤数百个电视台上数千个广告的现实解决方案是不可行的。为了寻找更快的方法，我们决定使用一个简单的方法图像之间的高斯差异以识别包含不同视觉内容的区域 7. 看看下面的例子，并排比较 SSIM 和高斯差异。轮廓用黄色来勾勒出源的确切区域并且目标图像不同。请注意这两种算法如何正确识别右下角丢失的徽标。SSIM 还识别图像顶部的其他更改。这些是存在于其中一个视频中的压缩伪影。当使用不同的视频格式对视频流进行编码时，它们就会出现。高斯的差异忽略了压缩伪影，使其更适合该任务。以下示例包含具有两个不同电话号码的视频帧，其他一切都相同。这两种算法都可以轻松识别不匹配。作为最后一个例子，我将展示 SSIM 方法何时表现更好。注意高斯分布的差异如何无法识别不同的公司名称：“Peoples Gas”与“North Shore Gas”。不难解释为什么会发生这种情况。对帧应用高斯滤波器后，字母像素与背景混合，因为这些像素的颜色相似。 这是高斯差异的局限性 - 如果差异与背景混合，则算法将无法识别它。尽管如此，我决定坚持使用它提供了性能和精度之间的极好权衡。

第 2 阶段验证的最后一步是从包含算法识别的轮廓的最佳重构路径中删除帧一旦这些帧被删除，最佳路径就会有间隙。间隙提供了视频开始不匹配的时间位置。观看以下最佳重建路径示例，通过逐帧比较识别不匹配的轮廓。当 SiriusXM 文本出现时，第 15 秒将在第一个中检测到稳定的轮廓。图 9 显示了差异开始时的一个帧出现。请注意，有时，不仅在 SiriusXM 出现期间识别轮廓。快速运动可能是查询帧和轨迹帧之间不完美的最佳路径对齐的原因。尽管如此，这不是一个值得关注的原因。在 1 秒的播放过程中，30 帧中至少有 1 帧足以正确对齐，以防止意外产生间隙。下一个示例展示了如何检测广告中间和末端的乳液瓶上的轮廓。在开发和集成视频指纹算法后，Emysound 现在可以在同一处理管道中对音频和视频流进行指纹、搜索、检索和比较。视频指纹现在用于识别 1,000 多个电视台显示的 3,000 到 6,000 个广告。使用LSH + MinHash 使我们能够搜索超过 25,000 小时的音频和视频内容。视频指纹算法是在与音频指纹相同的开源解决方案中实现的：SoundFingerprinting。我还没有时间更新 GitHub 页面，其中包含以编程方式生成视频指纹的动手示例，但我将在接下来的几个月中进行。如果您有兴趣使用它，请给我留言。核心指纹算法已获得 MIT 许可，因此您可以自由使用、更改和分发它。如果您有兴趣将内容识别服务用于商业项目，请注册 Emysound。

1 - 生成的图像包含多个 log2(n) 尺度，因为应用的方法是标准的 Haar 小波变换。您可以在此处详细了解应用 2D Haar 小波变换的方式的差异。 2 - 使用小波系数的符号在过去证明是有效的 - C. Jacobs, Finkelstein, A., Salesin, D. (1995) 快速多分辨率图像查询。过程信号图。 3 - Jaccard 相似度和 min-hash 值有很强的关系，其中 min-hash 匹配的概率等于 Jaccard 指数。更多细节在这里。 5 - 如果您想直观地了解 LSH 在欧几里得空间中的应用，我会推荐这篇文章作为介绍。作者使用随机旋转作为随机投影对点进行散列，这是一种用于构建视觉直观分区的巧妙技巧。 6 - 尝试对齐时间序列的最常见算法之一称为动态时间扭曲。编辑距离问题的解决方案更通用，也可以应用在相应的上下文中。 7 - 与高斯算法的原始差异的唯一变化是我们对两个图像使用相同的 sigma。