Animeloop 动漫循环识别方法

PDF: https://s3.moeoverflow.com/animeloop-production/static/technical_report_zh.pdf

Abstract

This article presents a method for identifying loops in anime video. By finding the same frame in the source video to determine the begin and end timepoint of the loop can be fragmented, roughly get the matching loop fragments, and then through some specific filters to filter out the meaningless fragments, and ultimately come to an effective loop fragment.

摘要

这篇文章描述了一种识别动漫视频里循环片段的方法。通过匹配出源视频中相同的帧画面来确定循环片段的起始帧和结束帧，再通过一系列过滤方法过滤出无意义的结果，最后得出一些可用的循环片段。

序言

这篇文章提出了一种程序识别动漫视频里可循环片段的方法。通过找出源视频中相同的画面来确定可循环片段的首尾画面，进而粗略得出符合的循环片段，再通过一些特定的过滤器来过滤掉无意义的片段，得出最终有效的循环片段。这个方法只针对动漫视频，是由于动漫的特殊制作过程——原画师画出关键帧再通过程序手段补帧——因此视频中会有很大几率能找到几乎完全相同的两幅画面。

图1：图片出自《日常 Nichijou》OP1

目标结果

https://animeloop.org/loop/591446415f6e5e51d937db6f

https://animeloop.org/loop/59283bcd79a9dc78dc42e981

https://animeloop.org/loop/5960b0ccbc2ef8075782ad3e

https://animeloop.org/loop/591446415f6e5e51d937db8c

可循环片段，即循环播放一个视频时，看不出开头和结尾的片段，整个播放可以无限进行下去。对循环片段的判断即是判断一个视频首帧画面和尾帧画面是否相同。（并不是只要相似就足够，需要相似程度高到几乎完全一致）

但是实际上靠这样的单一判断条件识别裁剪出来的循环片段，会有大量没有意义的结果。对循环片段的分类，大致上可以从场景转变、镜头跟随、明暗变化、前景动作等的角度来区分：

• 明暗变化——从有内容的画面转出黑（白）幕或者从黑（白）幕转入（需要过滤掉的结果）
• 镜头切换——由一个场景跳转到另一个场景或者短时间内多场景跳转（需要过滤掉的结果）
• 镜头平移——背景单向平移的情况下，前景人物（或物体）的动作（需要过滤掉的结果）
• 镜头平移——背景来回平移或者抖动的情况下，前景人物（或物体）的动作（期望的结果）
• 前景动作——背景不动的情况下，前景人物（或物体）的动作（期望的结果）

三种指纹哈希算法

图像指纹哈希简单来讲，就是根据图像像素点的分布按照一定的哈希算法，经过运算后得出的一组二进制数字或字符串，这组数据就称为图像的指纹哈希。指纹哈希可以代替原始图片，进行更方便的对比。

平均哈希算法（Average hash algorithm）

平均哈希算法，以下简称 aHash。aHash 是通过对比灰度图每个像素与所有像素平均值来实现的，一般步骤如下：

1. 缩放图片到适合大小（一般情况为 8x8）
2. 转换图片为 256 阶灰度图
3. 计算所有像素点的平均值
4. 比较每个像素灰度值与平均灰度值，如果大于等于平均值，则记录为 1，反之为 0
5. 上一步骤得到的记录值按顺序组合可构成一定长度的信息指纹
6. 获得任意两张图片的信息指纹，取汉明距离即可得出相似关系

图 2

感知哈希算法（Perceptual hash algorithms）

感知哈希算法 ^[1]，以下简称 pHash。pHash 描述了一类可比较的哈希函数。图像特征被用于生成独特的（但不是唯一的）指纹，并且这些指纹是可做对比的。

pHash 基于每一行像素前后渐变关系实现，一般步骤如下：

1. 缩放图片到适合大小（一般为 8x8 或者 32x32）
2. 转换图片为灰度图
3. 计算 DCT(Discrete Cosine Transform 离散余弦变换) 值。 DCT 将图片分离为频率和标量的集合。
4. 根据 32x32 DCT 值，取左上⾓ 8x8 的矩阵像素展平为 64 位的⽐特指纹。⾮常神奇的⼀个步骤，将每⼀个 DCT 值与所有 DCT 值的平均值做⽐较，如果⼤于平均值，则为 0，反之为 1
5. 根据 64 位的比特指纹构造出哈希指纹。将 64 位的比特指纹设置为一个 64 位的长整型作为哈希指纹
6. 获得任意两张图片的信息指纹，取汉明距离即可得出相似关系

图 3

差异哈希算法（Different hash algorithm）

差异哈希算法，以下简称 dHash。dHash 是基于相邻像素点渐变实现的，具体步骤如下：

1. 缩放图片到适合大小（一般为 8x9）
2. 转换图片为灰度图
3. 取每一行像素，相邻像素灰度值做比较，如果前者大于后者，记录为 1， 反之为 0
4. 上一步骤得到的记录值按顺序组合可构成一定长度的信息指纹
5. 获得任意两张图片的信息指纹，取汉明距离即可得出相似关系

以上三种算法都是用来识别相似图片，但是由于实现原理不同，实际识别的效果侧重点也不一样。aHash 更适合缩略图的相似识别，而 pHash 识别能力则更加精确，dHash 由于其原理相邻像素点渐变更适合于识别裁剪过的相似图像识别。

图 4

指纹哈希算法的选用

与前文讲到的识别相似图像的通常做法不一样，为了更加准确的找出循环片段，需要更精准的识别精度，这个精度主要体现在，平移前后两张图片应该被判定为相似但不相同。

图 5：图片出自《日常 Nichijou》第一集

P1 为原图；P2 被切去了一部分；P3 亮度变暗；P4 有文字加入。这四张图片都可以说是相似，但是不能说是相同。

为了测试对比三种哈希函数识别图片相似相同的精度，计算出多种尺寸下的 aHash、dHash 和 pHash 值，并分别拿 P1 与 P2、P3、P4 计算汉明距离得出相似度。见表I、表 II、表 III，表内值代表 P1 与 Px($x \in 2, 3, 4$) 的相似程度，值越大说明相似程度越高，最大为 1。

P1	P2	P3	P4
8x8	0.562500	1.000000	0.984375
32x32	0.692383	0.995117	0.944336
64x64	0.676758	0.998047	0.958740

表 I： aHash 图片相似值

P1	P2	P3	P4
DCT8/8x8	0.593750	1.000000	0.937500
DCT8/32x32	0.640625	1.000000	0.921875
DCT16/32x32	0.589844	0.992188	0.878906
DCT16/64x64	0.625000	1.000000	0.953125

表 II： pHash 图片相似值

P1	P2	P3	P4
8x8	0.609375	0.968750	0.890625
32x32	0.551758	0.924805	0.819336
64x64	0.523926	0.915527	0.806396

表 III： dHash 图片相似值

我们希望能够通过对比指纹哈希的方式，将图 2 中 P1 与 P2 的相似差距放大，将 P1 与 P4 的相似差距缩小。可以看到，pHash DCT16/64x64 对于区分图片裁剪或者有局部不同的效果比较好，而且可以减小局部变化对相似判定的影响，只有色彩明暗变化无法区分。因此，我们可以选用 pHash DCT16/64x64 作为计算指纹哈希的方法，并且在比较两张图片的时候，计算汉明距离算出相似度，如果相似度大于等于 0.98（这个阈值是一个魔法数字 Magic Number，针对不同的数据可以自由调整），则可以得出两张图片相同。之后我们只需要再增加一个过滤器过滤掉颜色明暗不同的相似图片即可。

失败的方法

尝试过一些非常粗暴的办法，比如：

• 提取任意两张图片中均匀分布的一些像素点构成一个新的像素矩阵，直接对比两张图相同位置像素点的色彩值（RGB 或者 Grayscale）是否一致，计算出不同像素点个数占所有像素点个数的比例。
• 先缩小图片的尺寸，在直接对比缩小后图片的所有相同位置对应的像素点色彩值是否相同，计算出比例。
• 甚至不缩小尺寸，直接对比整张图片所有像素点是否相同，计算出比例。

实际上发现效果并不好。

判断镜头切换

为了能找到同一个镜头下的循环片段，需要先找出在同一镜头内的起始结束时间点。这里我们可以使用帧差法来判断镜头切换——相邻前后两帧像素作差求绝对值，非黑色像素点所占的比例占用的比例越高，则说明前后两帧画面内容变动较大，由此判断为镜头切换。见图 6、图 7。

图 6

图 7

帧差法的具体步骤如下：

1. 压缩视频到适合大小（一般为 64x64 的大小）
2. 依次迭代获取相邻两张帧图像
3. 转换图片为灰度图
4. 对两张图像做作差求绝对值，获取一张新的帧差图像
5. 计算新获取的帧差图像中非黑色像素点所占的比例，如果大于 0.85，则说明有镜头切换；反之，没有镜头切换

将帧差法生成的相邻两帧差别值绘制成图表（见图 9），可以发现，出现有一些非常明显的陡增点，我们取纵坐标 0.85 （这个阈值同样是一个魔法数字）以上部分的陡增顶点，结合视频播放人眼观察发现，这些点横坐标代表的正好就是镜头切换时的时间点。

tips: 压缩视频尺寸前后计算得到的结果基本没有差别，压缩之后计算速度变快，见图 8、图 9。

图 8：全尺寸（1920x1080）的非黑色像素点比例

图 9：64x64 尺寸的非黑色像素点比例

失败的方法

尝试过使用 pHash 前后两帧的汉明距离，通过过滤相似度的方式来判断镜头切换。

图 10
可以看到只有少量的时间点有明显的区分出来。

识别循环片段

缓存频繁用到的数据

在分析识别之前，先对需要用到的数据进行缓存：

• 64x64 大小的源视频文件
• 源视频每一帧的 pHash 值
• 镜头切换的时间点

寻找起始结束帧相同的片段

图 11

两条横线代表视频帧序列，蓝色短竖线代表每一帧的 pHash 值，橙色长竖线代表镜头切换的时间点。

首先需要确定期望找到的循环片段长度的最短长度（kMinDuration）和最长长度（kMaxDuration）。初步筛选符合条件的循环片段，最主要的方法就是双重循环遍历任意两个在限制长度内的帧画面，判断是否相同，如果相同，这说明是一个循环片段。

具体看下面的伪代码。

for i in 0..<(frames-kMinDuration):
	for j in kMinDuration..<kMaxDuration:
		hash1 = phash(frames[i])
		hash2 = phash(frames[i+j])
		similar = 1 - hamming_distance(hash1, hash2) / double(64 * 64)
		if (similar >= 0.98):
			// loop fragment: i ~ i+j

过滤器：去除有镜头切换的片段（可选）

判断循环片段的时间段内是否包含有一个或多个镜头切换点，如果有，去掉这个片段。

过滤器：去除内容相近的片段

判断相邻的两个循环片段的起始结束帧画面是否相似，如果相似，去掉前一个片段。

过滤器：去除循环画面动态程度小的片段

计算一个循环片段内的所有帧，两两相邻帧的相似度，对得到的相似度集合计算方差，这个方差值代表了这个片段画面的动态程度。方差值小，说明这段片段动态程度小，应该去掉。

另一种方法：使用帧差法计算循环片段的动态程度。（待验证）

过滤器：去除起始结束帧为黑白纯色的片段

一些识别出的循环片段从黑色或者白色的纯色画面开始（一般更多的出现在 OP、ED 里），计算循环片段里首尾帧的黑色或白色像素点占整个像素点个数的比例，如果这个比例很大，则说明这个片段的起始结束画面为白色或者黑色，应该去掉。

过滤器：去除色彩明暗度不一致的片段

判断首尾帧画面色彩是否一致，如果不一致，则排除掉这个循环片段。直接计算出两张图所有像素点 RGB 的分别取整平均值 (mean_g, mean_b, mean_r)，如果两张图片计算出的平均值相同，则说明色彩一致，见图 12。

图 12

输出结果

得出一个记录了起始帧和结束帧的循环片段列表，从原尺寸源视频中裁剪出需要的循环片段。

程序实现

文件结构

• main
• animeloop-cli
• • loop_video.cpp/hpp
• • algorithm.cpp/hpp
• • filter.cpp/hpp
• • utils.cpp/hpp
• • models.cpp/hpp
• cxxopts
• jsoncpp
• research

源代码

源代码请前往 GitHub 代码仓库查看。https://github.com/moeoverflow/animeloop-cli

git clone https://github.com/moeoverflow/animeloop-cli.git
cd animeloop-cli
git ckeckout 785c7c89218769f851699a450d37ce0cb1e2668a

测试文件：https://s3.moeoverflow.com/animeloop-production/static/technical_report_resources.zip

生成结果《你的名字》1080P ：https://s3.moeoverflow.com/animeloop-production/static/technical_report_output_example.zip

旧文章链接： /recognize-loop-part-of-anime-video/

致谢

感谢次时代 GIF/Sticker 制作团队的成员们不厌其烦地评估质量和建议。

---

1. Dr. Neal Krawetz - Looks Like It http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html ↩︎