从视频提取循环播放式GIF动画的算法

840 查看

这是互联网时代用数学解决的另一个大问题。

循环播放式的 GIF 动图是网络上一种流行的艺术形式，在Reddit有两个专属的论坛（r/perfectloops 和r/cinemagraphs），还有数不尽的Tumblr 页面。

找到并提取电影中的循环片段，需要极大的注意力和耐心，电脑前的你，很可能就像下面这样：

为了使事情变得简单点，我写了个Python脚本来自动完成这个任务。这篇博文解释了算法背后的数学并提供了一些使用范例。

何时视频片段循环是无缝衔接？

如果一段视频的第一帧和最后一帧很相似，我们就说它循环起来是无缝衔接的。视频的一帧可以表示为一个整数序列，数值表明了图片像素的颜色。例如，, 和给出了第一个像素的红、绿、蓝的数值。, , 给出了第二个像素的值，等等。

给定同一视频的两帧, , 我们定义它们的差别为颜色差别的和：

如果小于某个任意阈值，我们就认为这两帧相似。

要理解接下来的内容，很重要的一点是注意到定义了两帧的距离，可以看作是平面上两点几何距离的一般化。

因此有很好的数学性质，在下一节我们利用它来加快计算。

找到无缝衔接循环的片段

在这一节，我们想要找到给定视频中所有无缝衔接循环、3秒钟内的片段的时间（起始时间和终止时间）。有一种简单的做法，比较每一帧和之前3秒的所有帧。当我们发现相似的两帧时（即距离小于某个预设的阈值），就把对应的时间加到列表中。

问题是这种方法需要大量的比较（对于一部标准视频大约一千万），耗时以小时计。因此我们来看看使计算更快的一些技巧。

技巧一：使用缩减版的帧。HD高清视频帧有数百万的像素，因此计算它们之间的距离要数百万次操作。当把帧缩小成缩略图（150像素宽）时，对于我们的目的它们仍然足够精细，距离计算却可以快得多（内存占用也更少）。

技巧二：利用三角不等式。有这个非常高效的技巧，在不计算两帧距离的情况下，我们就能推断出它们是否匹配。因为定义了两帧之间的数学距离，很多经典几何的结论都能用得上，特别是下面的关于三角形边的长度的不等式：

第一个不等式告诉我们如果A接近于B，且B接近于C，那么A接近于C。对于视频帧来说就是：

在实际中我们这么来利用这个不等式：如果我们已知帧和帧很相似，和另一帧很相似，那么我们不用计算就知道和很相似。

第二个不等式告诉我们如果点A接近于B，而B远离C，那么A也远离C。对于帧来说就是：

如果和很相似，而和大不相同，那么我们无需计算就知道和也有很大差别。

下面就开始有点复杂了：我们应用这些三角不等式来获得帧距离上界和下界的信息，在每次计算两帧距离时这些都会得到更新。比如，计算后，的上下界（分别用和表示）可以如下更新：

如果更新后，，我们可以下结论：和匹配得很好。如果在某个时刻，，我们就知道和不匹配。如果用这个技术不能决定和是否匹配，那我们最终需要计算，但知道后反过来可以让我们更新另一个距离（）的界，以此类推。

作为说明，假设一部视频依次有如下帧：

当算法计算到时，它首先计算这帧和的距离，发现它们不匹配。在这个时候，算法已经发现和及相似，因此推断出和都不和匹配（当然，之前的十几帧也是）。在实际中，这种方法能避免80%到90%的帧距离计算。

技巧三：用高效的公式计算距离。当我们用上一节的公式来计算两帧之间的距离时，需要大约3N次操作：N次减法，N次乘法，(N-1)次加法来得到最终的和。但是的公式也可以重写为如下形式，也就是余弦定理：

其中我们用了如下记号：

的这个表达式的有趣之处在于，我们先对每帧计算一次范数，那么对于每对, 只需计算就可以得到它们之间的距离。而这只需2N次操作，比之前快了50%。

对每帧计算的另一个好处是，对于两帧和，我们有：

这提供了技巧二里两帧之间距离上下界的初始值。

用伪代码表示的最终算法。总结起来，我们得到了如下算法：

for each frame F1 in the movie:

F1 <- downsized( F1 )

previous_frames <- list of frames in the 3 seconds before F1

list_of_matching_couples = []

compute and store |F1|

for each frame F2 in previous_frames:

compute upper_F1_F2 and lower_F1_F2 using Eq.2

if upper_F1_F2 < T:

mark (F1, F2) as matching

add (F1, F2) to the list_of_matching_couples

if lower_F1_F2 > T:

mark (F1, F2) as non-matching

for each frame F2 in previous_frames:

if couple (F1,F2) isn't already marked matching or non-matching:

compute d(F1, F2)

for each frame F3 after F2 in previous_frames:

update upper_F1_F3 and lower_F1_F3 using Eq.1

if upper_F1_F3 < T:

mark (F1, F3) as matching

add (F1, F3) to the list_of_matching_couples

if lower_F1_F3 > T:

mark (F1, F3) as non-matching

这里是Python的实现。计算时间可能依赖于视频文件的质量，不过我尝试的大多数电影能在大约20分钟处理完。令人印象深刻，是吧？Eugene。

挑选有趣的片段

前一节描述的算法找到所有的帧对，包括连续的帧（通常看起来非常像）和来自静止片段的帧（典型的是黑屏）。因此我们会得到几十万个视频片段，而只有一些是真正有趣的。在提取GIF之前我们必须找到一种方式来过滤掉不想要的片段。过滤操作只需几秒钟，但它的成功极大地依赖于你用的过滤标准。这里是一些有效的例子：

第一帧和最后一帧必须至少相隔0.5秒。
序列中必须至少有一帧和第一帧不匹配。这个标准能够排除静止片段。
第一帧的起始时间必须在上一个提取的片段的起始时间的0.5秒之后。这是为了避免重复的片段（即那些起始和终止时间几乎一样的片段）。

我尽量不做太多限制（避免偶然过滤掉好的片段），因此通常得到大约200个GIF，其中很多只是中等有趣（眨眼之类）。最后一步是人工过滤，就像下面这样：

使用范例

I我实现了这个算法，作为我的Python视频库MoviePy的插件。这里是一个包含很多细节的例子脚本：

from moviepy.editor import VideoFileClip

from moviepy.video.tools.cuts import FramesMatches

# Open a video file (any format should work)

clip = VideoFileClip("myvideo.avi")

# Downsize the clip to a width of 150px to speed up things

clip_small = clip.resize(width=150)

# Find all the pairs of matching frames an return their

# corresponding start and end times. Takes 15-60 minutes.

matches = FramesMatches.from_clip(clip_small, 5, 3)

# (Optional) Save the matches for later use.

# matches.save("myvideo_matches.txt")

# matches = FramesMatches.load("myvideo_matches.txt")

# Filter the scenes: keep only segments with duration >1.5 seconds,

# where the first and last frame have a per-pixel distance < 1,

# with at least one frame at a distance 2 of the first frame,

# and with >0.5 seconds between the starts of the selected segments.

selected_scenes = matches.select_scenes(match_thr=1,

min_time_span=1.5, nomatch_thr=2, time_distance=0.5)

# The final GIFs will be 450 pixels wide

clip_medium = clip.resize(width=450)

# Extract all the selected scenes as GIFs in folder "myfolder"

selected_scenes.write_gifs(clip_medium, "myfolder")

这里是我用迪士尼的《白雪公主》来试验时得到的：

import moviepy.editor as mp

from moviepy.video.tools.cuts import FramesMatches

clip = mp.VideoFileClip("snowwhite.mp4")

scenes = FramesMatches.from_clip(clip.resize(width=120), 5, 2)

selected_scenes = scenes.select_scenes(2, 0.5, 4, 0.5)

selected_scenes.write_gifs(clip.resize(width=270), "snow_white")

（更多图片，请查看http://imgur.com/a/nVcqQ）

这里有些GIF可以切割得更好，有些也不太有趣（太短），还有些循环片段被错过了。我认为罪魁祸首是最后一步过滤的参数，这些本可以被调整得更好。

另一个例子：最近有人在r/perfectloops发了个Youtube视频，要求把它转成循环播放式的 GIF。下面的脚本就做了这件事：从Youtube下载视频，找到切割成循环播放序列的最好的时间(t1, t2)，然后生成GIF：

import moviepy.editor as mpy

from moviepy.video.tools.cuts import FramesMatches

# Get the video from youtube, save it as "hamac.mp4"

mpy.download_webfile("NpxD9TZIlv8", "hamac.mp4")

clip = mpy.VideoFileClip("hamac.mp4").resize(width=200)

matches = FramesMatches.from_clip(clip, 40, 3) # loose matching

# find the best matching pair of frames > 1.5s away

best = matches.filter(lambda x: x.time_span >1.5).best()

# Write the sequence to a GIF (with speed=30% of the original)

final = clip.subclip(best.t1, best.t2).speedx(0.3)

final.write_gif("hamac.gif", fps=10)

利用MoviePy，你也可以对GIF做后期处理，加上文字：

代码

既然你读到了这，这有个为你准备的更高级的技巧：

代码

轮到你了！

我在这里呈现的算法并不完美。对于低亮度的影片片段，它表现得很糟，有时轻微的摄像机移动或者背景中的运动物体都能阻止片段循环播放。虽然这些片段能被人类轻易地修正，却很难被算法认出、处理。

因此我的脚本并未完全解决问题，制作循环播放式的 GIF 仍然是门艺术。如果你对这个算法有任何点子或评论，或者你尝试后发现了电影中的有趣的循环播放，我很乐意听到！在那之前，快乐地制作GIF吧！