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

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

為了使事情變得簡單點，我寫了個Python腳本來自動完成這個任務。這篇博文解釋了算法背后的數(shù)學并提供了一些使用范例。

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

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

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

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

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

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

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

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

問題是這種方法需要大量的比較（對于一部標準視頻大約一千萬），耗時以小時計。因此我們來看看使計算更快的一些技巧。

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

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

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

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

第二個不等式告訴我們?nèi)绻cA接近于B，而B遠離C，那么A也遠離C。對于幀來說就是：

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

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

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

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

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

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

其中我們用了如下記號：

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

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

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

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

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

挑選有趣的片段

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

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

序列中必須至少有一幀和第一幀不匹配。這個標準能夠排除靜止片段。

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

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

使用范例

I我實現(xiàn)了這個算法，作為我的Python視頻庫MoviePy的插件。這里是一個包含很多細節(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")

這里是我用迪士尼的《白雪公主》來試驗時得到的：

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

（更多圖片，請查看）

這里有些GIF可以切割得更好，有些也不太有趣（太短），還有些循環(huán)片段被錯過了。我認為罪魁禍首是最后一步過濾的參數(shù)，這些本可以被調(diào)整得更好。

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

既然你讀到了這，這有個為你準備的更高級的技巧：

輪到你了！

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

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

更多信息請查看IT技術專欄