动漫循环识别

最近给 moeoverflow.org 更换了新主页,其中背景不再是一张图片,而是循环短视频。

<video loop="" autoplay="" muted="" webkit-playsinline="" width=90%" playsinline="">


Your browser does not support the video tag.

目前放上去的几个循环视频都是自己手动裁剪的,虽然效果很高,但是效率太低了。两个小时才切出几个循环段出来。于是考虑使用程序自动识别视频里的循环段并生成新的视频,经过一整天 18 小时的努力,赶出了 animeloop[1] 的第一个版本。

这个项目实现主要利用图片的颜色特征,依赖于一系列哈希算法[2],其中目前主要使用到了 aHashdHash 的具体算法实现,并用到了 OpenCV 3[3]

aHash 基于待处理图像相对应的灰度图每一个像素与平均值的比较,一般步骤如下:

  1. 缩放图片到适合大小(为了提高计算速度适当降低精度)
  2. 转换图片为灰度图(可以直接用 OpenCV 提供的函数)
  3. 计算所有像素点的平均值
  4. 比较每个像素灰度值与平均灰度值,如果大于等于平均值,则记录为 1,反之为 0
  5. 上一步骤得到的记录值按顺序组合可构成一定长度的信息指纹
  6. 获得任意两张图片的信息指纹,取汉明距离即可得出相似关系

dHash 基于每一行像素前后渐变关系实现,一般步骤如下:

  1. 缩放图片到适合大小(为了提高计算速度适当降低精度)
  2. 转换图片为灰度图(可以直接用 OpenCV 提供的函数)、
  3. 取每一行像素,相邻像素灰度值做比较,如果前者大于后者,记录为 1, 反之为 0
  4. 上一步骤得到的记录值按顺序组合可构成一定长度的信息指纹
  5. 获得任意两张图片的信息指纹,取汉明距离即可得出相似关系

总的来讲,aHash 和 dHash 基本是一致,只在取指纹这一步有所不同,前者从整体角度上来计算相似,后者从图片像素点颜色渐变实现的。

在这个项目中,目标是找出一个视频中所有的循环段落开始时间点和结束时间点,并输出到单独的视频文件中。

那么最先想到的方式就是,找出视频中相似度很高的两个帧图片,这两个图片帧之间的段落即为循环段落。为了提高运算速度,我们可以提前定义两个变量 kMinDurationkMaxDuration 来限制循环视频的长度。以下是实现伪代码(因为是伪代码所以有些细节就不处理了,具体实现可以看项目代码):

frames[1791]
indexes = 1791
for index in 0..<indexes:
	for i in kMinDuration..<kMaxDuration:
		hash1 = dhash(frames[index])
		hash2 = dhash(frames[index+i])
		if (hamming_distance(hash1, hash2) < 1):
			// duration: index ~ index+i

这是最简单的实现方式,但是实际效果并不理想,会发现结果中会出现大量画面静止不动的结果和大量时间段重复的结果,于是就要想办法过滤。

前一个问题,通过引入一个方差值(也许)可以解决问题。在找到的每一个循环时间段之间计算相邻帧画面 dHash 哈希指纹的汉明距离,如果得到的一组汉明距离值平均值相对于 0 偏大,说明这一段视频画面变化比较多,不是静止画面,保留结果,反之抛弃这一组结果。

后一个问题,比较粗暴的解决办法是依次序排除多余于项,比如某一个循环段是 00:11:32.4 ~ 00:11:35.8,如果下一个循环段是 00:11:33.2 ~ 00:11:36.4,这一组和上一组循环段有重复部分,那么后一组应该抛弃。但是实际上发现这么做太过严格了,所以把时间段重复筛选定在了前一个时间段开始时间点和最小循环时间之间。

distances = []
for i in start..<(end-1):
	hash1 = hash(frames[i])
	hash2 = hash(frames[i+1])
	distances += hamming_distance(hash1, hash2)
average = sum(distances) / distances.length

最后还可以再筛选一次,只对比循环段第一帧和最后一帧是否相同(严格相似对比),可以进一步减少最终的结果数量。

以上便是第一个版本的实现思路,测试了一下,识别《这个美术社大有问题!》第三集整个视频,最终生成循环视频有 50 几个,还是存在不少的误判问题,比如字幕误判和 Ken Burns 平移效果误判。

看上去效果还不错,但是在写完以上内容我就发现,我这个实现方式实在是太过粗糙想当然了。可以去看看项目代码,里面甚至还保留了好几个 Magic Number。如果测试其他的一些动漫视频可能出来的效果就很有问题了。

不过毕竟是第一版实现,在这个过程中慢慢的找到新的思路,有时间会实验更好的实现新方案。


程序重写

文件结构
  • main
  • loop-video
    • loop_video.cpp/hpp
    • algorithm.cpp/hpp
    • filter.cpp/hpp
    • utils.cpp/hpp
    • models.cpp/hpp
  • cxxopts
  • jsoncpp

步骤

Step 1

init() 缩小目标视频尺寸,一般和计算 Hash 的尺寸一致,默认为 8x8,接下来在计算 dHash 和 pHash(类型可更换),最后再获取目标视频的基础信息,比如 FPS、FOURCC、SIZE 和 FRAME_COUNT。

特别喜感的一点是,我一直很关心程序的运行效率,写代码的时候也很尽量的用更高效的写法。但是后来我才发现,这个计算 Hash 的过程其实相对来说并不耗时,大部分时间都浪费在了用 OpenCV 压缩视频尺寸的步骤,所以现在直接把视频 resize 之后存储缓存了。

并通过 filter_0 计算出所有可能的循环片段(所有起始帧和结束帧相同的片段),并去重。

Step 2

通过一系列设定好的规则筛选出需要的循环片段。

...


  1. 项目地址: https://github.com/moeoverflow/animeloop-cli 另外还有 BlueCocoa 的另一个实现 https://github.com/moeoverflow/longest-animeloop-cli ↩︎

  2. aHash 平均哈希算法;pHash 感知哈希算法;dHash 算法 ↩︎

  3. 这是一套图像视频处理方面非常强大的框架,可以干很多事包括图像滤镜处理,视频物件识别甚至涉及到机器学习。在我接触这个东西之前,一直认为这个东西太高端了以至于不敢去碰。这次趁着这个机会,接触了解了一下,算是满满的入坑了。 ↩︎