循環(huán)播放式的 GIF 動(dòng)圖是網(wǎng)絡(luò)上一種流行的藝術(shù)形式，在Reddit有兩個(gè)專屬的論壇（r/perfectloops 和r/cinemagraphs），還有數(shù)不盡的Tumblr 頁(yè)面。

找到并提取電影中的循環(huán)片段，需要極大的注意力和耐心，電腦前的你，很可能就像下面這樣：

為了使事情變得簡(jiǎn)單點(diǎn)，我寫了個(gè)Python腳本來(lái)自動(dòng)完成這個(gè)任務(wù)。這篇博文解釋了算法背后的數(shù)學(xué)并提供了一些使用范例。

何時(shí)視頻片段循環(huán)是無(wú)縫銜接？

如果一段視頻的第一幀和最后一幀很相似，我們就說它循環(huán)起來(lái)是無(wú)縫銜接的。視頻的一幀(F) 可以表示為一個(gè)整數(shù)序列，數(shù)值表明了圖片像素的顏色。例如，(F[1]) , (F[2]) 和(F[3]) 給出了第一個(gè)像素的紅、綠、藍(lán)的數(shù)值。(F[4]) , (F[5]) , (F[6]) 給出了第二個(gè)像素的值，等等。

給定同一視頻的兩幀(F_1) , (F_2) , 我們定義它們的差別為顏色差別的和：

如果(d(F_1,F_2)) 小于某個(gè)任意閾值(T) ，我們就認(rèn)為這兩幀相似。

要理解接下來(lái)的內(nèi)容，很重要的一點(diǎn)是注意到(d(F_1, F_2)) 定義了兩幀的距離，可以看作是平面上兩點(diǎn)幾何距離的一般化。

因此(d(F_1, F_2)) 有很好的數(shù)學(xué)性質(zhì)，在下一節(jié)我們利用它來(lái)加快計(jì)算。

找到無(wú)縫銜接循環(huán)的片段

在這一節(jié)，我們想要找到給定視頻中所有無(wú)縫銜接循環(huán)、3秒鐘內(nèi)的片段的時(shí)間（起始時(shí)間和終止時(shí)間）。有一種簡(jiǎn)單的做法，比較每一幀和之前3秒的所有幀。當(dāng)我們發(fā)現(xiàn)相似的兩幀時(shí)（即距離小于某個(gè)預(yù)設(shè)的閾值(T) ），就把對(duì)應(yīng)的時(shí)間加到列表中。

問題是這種方法需要大量的比較（對(duì)于一部標(biāo)準(zhǔn)視頻大約一千萬(wàn)），耗時(shí)以小時(shí)計(jì)。因此我們來(lái)看看使計(jì)算更快的一些技巧。

技巧一：使用縮減版的幀。HD高清視頻幀有數(shù)百萬(wàn)的像素，因此計(jì)算它們之間的距離要數(shù)百萬(wàn)次操作。當(dāng)把幀縮小成縮略圖（150像素寬）時(shí)，對(duì)于我們的目的它們?nèi)匀蛔銐蚓?xì)，距離計(jì)算卻可以快得多（內(nèi)存占用也更少）。

技巧二：利用三角不等式。有這個(gè)非常高效的技巧，在不計(jì)算兩幀距離的情況下，我們就能推斷出它們是否匹配。因?yàn)?d(F_1, F_2)) 定義了兩幀之間的數(shù)學(xué)距離，很多經(jīng)典幾何的結(jié)論都能用得上，特別是下面的關(guān)于三角形邊的長(zhǎng)度的不等式：

第一個(gè)不等式告訴我們?nèi)绻鸄接近于B，且B接近于C，那么A接近于C。對(duì)于視頻幀來(lái)說就是：

在實(shí)際中我們這么來(lái)利用這個(gè)不等式：如果我們已知幀(F1) 和幀(F2) 很相似，(F2) 和另一幀(F3) 很相似，那么我們不用計(jì)算(d(F_1, F_3)) 就知道(F1) 和(F3) 很相似。

第二個(gè)不等式告訴我們?nèi)绻c(diǎn)A接近于B，而B遠(yuǎn)離C，那么A也遠(yuǎn)離C。對(duì)于幀來(lái)說就是：

如果(F1) 和(F2) 很相似，而(F2) 和(F3) 大不相同，那么我們無(wú)需計(jì)算(d(F_1, F_3)) 就知道(F1) 和(F3) 也有很大差別。

下面就開始有點(diǎn)復(fù)雜了：我們應(yīng)用這些三角不等式來(lái)獲得幀距離上界和下界的信息， 在每次計(jì)算兩幀距離時(shí)這些都會(huì)得到更新。比如，計(jì)算(d(F_1, F_2)) 后，(d(F_1, F_3)) 的上下界（分別用和表示）可以如下更新：

如果更新后，，我們可以下結(jié)論：(F_1) 和(F_3) 匹配得很好。如果在某個(gè)時(shí)刻，，我們就知道(F_1) 和(F_3) 不匹配。如果用這個(gè)技術(shù)不能決定(F_1) 和(F_3) 是否匹配，那我們最終需要計(jì)算(d(F_1, F_3)) ，但知道(d(F_1, F_3)) 后反過來(lái)可以讓我們更新另一個(gè)距離（(d(F_1, F_4)) ）的界，以此類推。

作為說明，假設(shè)一部視頻依次有如下幀：

當(dāng)算法計(jì)算到(F_4) 時(shí)，它首先計(jì)算這幀和(F_3) 的距離，發(fā)現(xiàn)它們不匹配。在這個(gè)時(shí)候，算法已經(jīng)發(fā)現(xiàn)(F_3) 和(F_2) 及(F_1) 相似，因此推斷出(F_1) 和(F_2) 都不和(F_4) 匹配（當(dāng)然，之前的十幾幀也是）。在實(shí)際中，這種方法能避免80%到90%的幀距離計(jì)算。

技巧三：用高效的公式計(jì)算距離。當(dāng)我們用上一節(jié)的公式來(lái)計(jì)算兩幀之間的距離時(shí)，需要大約3N次操作：N次減法，N次乘法，(N-1)次加法來(lái)得到最終的和。但是(d(F_1,F_2)) 的公式也可以重寫為如下形式，也就是余弦定理：

其中我們用了如下記號(hào)：

(d(F_1,F_2)) 的這個(gè)表達(dá)式的有趣之處在于，我們先對(duì)每幀計(jì)算一次范數(shù)(||F||) ，那么對(duì)于每對(duì)(F_1) , (F_2) 只需計(jì)算就可以得到它們之間的距離。而這只需2N次操作，比之前快了50%。

對(duì)每幀計(jì)算(|F|) 的另一個(gè)好處是，對(duì)于兩幀(F_1) 和(F_2) ，我們有：

這提供了技巧二里兩幀之間距離上下界的初始值。

用偽代碼表示的最終算法?？偨Y(jié)起來(lái)，我們得到了如下算法：

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的實(shí)現(xiàn)。計(jì)算時(shí)間可能依賴于視頻文件的質(zhì)量，不過我嘗試的大多數(shù)電影能在大約20分鐘處理完。令人印象深刻，是吧？Eugene。

挑選有趣的片段

前一節(jié)描述的算法找到所有的幀對(duì)，包括連續(xù)的幀（通?？雌饋?lái)非常像）和來(lái)自靜止片段的幀（典型的是黑屏）。因此我們會(huì)得到幾十萬(wàn)個(gè)視頻片段，而只有一些是真正有趣的。在提取GIF之前我們必須找到一種方式來(lái)過濾掉不想要的片段。過濾操作只需幾秒鐘，但它的成功極大地依賴于你用的過濾標(biāo)準(zhǔn)。這里是一些有效的例子：

第一幀和最后一幀必須至少相隔0.5秒。

序列中必須至少有一幀和第一幀不匹配。這個(gè)標(biāo)準(zhǔn)能夠排除靜止片段。

第一幀的起始時(shí)間必須在上一個(gè)提取的片段的起始時(shí)間的0.5秒之后。這是為了避免重復(fù)的片段（即那些起始和終止時(shí)間幾乎一樣的片段）。

我盡量不做太多限制（避免偶然過濾掉好的片段），因此通常得到大約200個(gè)GIF，其中很多只是中等有趣（眨眼之類）。最后一步是人工過濾，就像下面這樣：

使用范例

I我實(shí)現(xiàn)了這個(gè)算法，作為我的Python視頻庫(kù)MoviePy的插件。這里是一個(gè)包含很多細(xì)節(jié)的例子腳本：

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")

這里是我用迪士尼的《白雪公主》來(lái)試驗(yàn)時(shí)得到的：

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")

（更多圖片，請(qǐng)查看）

這里有些GIF可以切割得更好，有些也不太有趣（太短），還有些循環(huán)片段被錯(cuò)過了。我認(rèn)為罪魁禍?zhǔn)资亲詈笠徊竭^濾的參數(shù)，這些本可以被調(diào)整得更好。

另一個(gè)例子：最近有人在r/perfectloops發(fā)了個(gè)Youtube視頻，要求把它轉(zhuǎn)成循環(huán)播放式的 GIF。下面的腳本就做了這件事：從Youtube下載視頻，找到切割成循環(huán)播放序列的最好的時(shí)間(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，你也可以對(duì)GIF做后期處理，加上文字：

既然你讀到了這，這有個(gè)為你準(zhǔn)備的更高級(jí)的技巧：

輪到你了！

我在這里呈現(xiàn)的算法并不完美。對(duì)于低亮度的影片片段，它表現(xiàn)得很糟，有時(shí)輕微的攝像機(jī)移動(dòng)或者背景中的運(yùn)動(dòng)物體都能阻止片段循環(huán)播放。雖然這些片段能被人類輕易地修正，卻很難被算法認(rèn)出、處理。

因此我的腳本并未完全解決問題，制作循環(huán)播放式的 GIF 仍然是門藝術(shù)。如果你對(duì)這個(gè)算法有任何點(diǎn)子或評(píng)論，或者你嘗試后發(fā)現(xiàn)了電影中的有趣的循環(huán)播放，我很樂意聽到！在那之前，快樂地制作GIF吧！

更多信息請(qǐng)查看IT技術(shù)專欄