譯者注：本文以一段自打24小時耳光的視頻為例子，介紹了如何利用均值哈希算法來檢查重復(fù)視頻幀。以下是譯文。

有人在網(wǎng)上上傳了一段視頻，他打了自己24個小時的耳光。他真的這么做了嗎?看都不用看，肯定沒有!

前幾天，我瀏覽YouTube的時候，看到了一段非常流行的視頻。在視頻里，一個人聲稱自己要連續(xù)打臉24小時。視頻的長度就是整整的24小時。我跳著看完了這個視頻，確實，他就是在打自己的臉。許多評論都說這個視頻是偽造的，我也是這么想的，但我想確定這個結(jié)論。 

 

 

 

計劃

寫一個程序來檢測視頻中是否有循環(huán)。我之前從來沒有用Python處理過視頻，所以這對我來說有點難度。

首次嘗試

看一個視頻就像是在快速地翻看圖片，這也是使用python讀取視頻數(shù)據(jù)的方式。我們看到的每個“圖片”都是視頻的一個幀。在視頻播放時，它是以每秒30幀的速度進(jìn)行播放。

在視頻數(shù)據(jù)中，每一幀都是一個巨大的數(shù)組。該數(shù)組通過指定數(shù)量的紅、綠、藍(lán)進(jìn)行混合來告訴我們每個位置上每個像素的顏色。我們想看看視頻中是否有多個幀出現(xiàn)了多次，有一個方法，就是計算我們看到的每一幀的次數(shù)。

我用兩個字典類型的變量來進(jìn)行計數(shù)。一個跟蹤我已經(jīng)看到的幀，另一個跟蹤所有完全相同的幀。當(dāng)我逐個瀏覽每一幀時，首先檢查以前是否看過這一幀。如果沒有，則把這一幀添加到我已看過的幀字典中(見下面的seen_frames)。如果以前看過這一幀，則將它添加到另一個字典(dup_frames)的列表中，這個字典包含了其他一模一樣的幀。

代碼如下：

def find_duplicates():   
 
    # 載入視頻文件   
 
    filename = 'video.mp4'   
 
    vid = imageio.get_reader(filename,  'ffmpeg')   
 
    all_frames = vid.get_length()   
 
   
 
    # 重復(fù)的幀保存在這里   
 
    seen_frames = {}   
 
    dup_frames = {}   
 
   
 
    for x in range(all_frames):   
 
        # 獲取單個幀   
 
        frame = vid.get_data(x)   
 
   
 
        # 取幀的哈希值   
 
        hashed = hash(frame.tostring())   
 
   
 
        if seen_frames.get( hashed, None):   
 
            # 如果之前看到過這一幀，則添加到dup_frames中具有相同的哈希值的幀列表中   
 
            dup_frames[hashed].append(x)   
 
        else:   
 
            # 如果這是第一次看到這一幀，則保存到seen_frames中   
 
            seen_frames[hashed] = x   
 
            dup_frames[hashed] = [x]   
 
   
 
    # 返回重復(fù)幀列表的列表   
 
    return [dup_frames[x] for x in dup_frames if len(dup_frames[x]) > 1]  

這段代碼在我的macbook pro上跑了大約一個小時。 我們來看看結(jié)果： 

 

 

 

很好，結(jié)果看起來很直觀，從下圖中可以看出，幀5928與幀2048454相同，幀5936與幀2048462相同，以此類推。讓我們目視確認(rèn)。

完美。所以，這個視頻肯定是偽造的。 然而，幀匹配的數(shù)量看起來實在太低了，值得懷疑啊。 真的只有25個相同的幀嗎?在整整24小時的視頻中這25幀的長度幾乎不到1秒鐘。我們來進(jìn)一步看一下!

情況變復(fù)雜了

該程序的作用是確定相同的幀，這樣我就能知道視頻是在循環(huán)播放。讓我們來看看上面兩幅圖像的后2秒的幀(幀5936 + 60和幀2048462 + 60)是什么樣的。

等等…… 這兩個圖像看起來是一樣的啊!但是他們?yōu)槭裁礇]有標(biāo)記為匹配呢?我們可以把其中一個幀減去另外一個幀來找出不同之處。這個減法是對每個像素的紅、綠、藍(lán)的值分別做減法。 

 

 

 

太好了，我們創(chuàng)造出了一個很酷的故障藝術(shù)!但是，實際上兩個幀的差值僅僅是視頻被壓縮后的兩個幀的差異。由于經(jīng)過了壓縮，原來相同的兩個幀可能會受到噪音的影響而導(dǎo)致失真，從而在數(shù)值上不再一樣(盡管它們在視覺上看起來是一樣的)。

對上面的說明總結(jié)一下，當(dāng)我將數(shù)據(jù)存儲在字典中時，我取了每個圖像的哈希。哈希函數(shù)將圖像(數(shù)組)轉(zhuǎn)換為整數(shù)。如果兩個圖像完全相同，則哈希函數(shù)將得到相同的整數(shù)。如果兩個圖像不同，我們將得到兩個不同的整數(shù)。但是我們實際想要的是，如果兩個圖像只是稍微不同，我們?nèi)蝗匀荒艿玫较嗤恼麛?shù)。

簡化我們的壓縮問題

有幾種不同的哈希算法，每種都有專門的使用場景。我們在這里將要看到的是感知哈希。與其他類型的哈希不同的是，對于靠近在一起的輸入，它們的感知哈希值是相同的。反向圖像搜索網(wǎng)站顯然使用的是類似的技術(shù)，這些網(wǎng)站只是抓取他們遇到的網(wǎng)絡(luò)和哈希圖像。由于同一張圖片在互聯(lián)網(wǎng)上可能存在多種不同的分辨率和剪裁，所以檢查其他具有相同哈希值的東西則更為方便。

然而，對于我們來說，又有新的麻煩了，因為我們處理的并不完全是圖像，而是一系列的圖像，每一張圖片都是相差1/30秒。這意味著我們的哈希函數(shù)需要：

• 足夠的寬松，兩個僅因為壓縮而產(chǎn)生噪聲的幀的哈希值是相同的
• 足夠的靈敏，兩個相鄰幀的哈希值是不同的

這可能很復(fù)雜。

均值哈希的參數(shù)選擇

我要嘗試使用的哈希算法稱為均值哈希(aHash)。在網(wǎng)上能找到很多的信息，它的處理過程一般是這樣的：降低圖像分辨率，轉(zhuǎn)換為灰度圖，然后取哈希值。通過降低分辨率，我們可以消除噪聲的影響。然而，我們冒著相鄰幀可能會被標(biāo)記為重復(fù)幀的風(fēng)險，因為它們是相似的。通過調(diào)整分辨率可以稍稍解決這個問題。

下面，我分別以分辨率8×8和64×64顯示均值哈希的結(jié)果。8×8看起來降采樣的太多了，我們失去了太多的信息，似乎大多數(shù)圖像看起來都是一樣的了。對于64×64，它看起來和原來的圖像沒什么不同，兩者之間可能沒有足夠大的區(qū)別來忽略壓縮產(chǎn)生的噪聲。 

 

 

 

為了找到適合我們的分辨率，我試著在兩段類似的視頻中通過設(shè)置一系列不同的分辨率來尋找匹配項。返回的匹配項將出現(xiàn)在以下輸出中：

• [8,108]
• [9,109]
• [10,11,110,111]

上述的解釋是，第8幀和第108幀相同。第9幀和第109幀相同，但不同于8、108。第10、11、110、111幀與其他幀都不同，但彼此相同。這種情況很有可能發(fā)生，因為算法并不完美，偶爾也會混淆，認(rèn)為兩個相鄰的幀是相同的。我們看看下面這幾個數(shù)字：

• 有多少個匹配的桶?從上面可以看到，有3個。
• 每個桶中的平均幀數(shù)是多少?平均值為(2 + 2 + 4)/ 3 = 2.7。
• 所有桶中最多的幀是多少? 4。

這里的目標(biāo)是獲得大量的桶(第一個數(shù)字)，并且每個桶內(nèi)的幀數(shù)盡可能的少(平均或最差情況)。理論上來說，由于我正在看的這段視頻有1個循環(huán)，所以每桶應(yīng)該只有2幀。 

 

 

 

好的，看起來64太極端了，我們幾乎沒有一個桶在這一點上。另一方面，在圖形的左側(cè)，桶的大小(Bucket Size)有一個爆炸點，其中所有的幀都被檢測為重復(fù)的。這個爆炸點似乎是在20附近。從最大桶的大小(Max Bucket Size)那根曲線來看，20的那個數(shù)據(jù)點似乎有些奇怪。為了反駁這一段網(wǎng)上視頻，我也只愿意做到這些了，那么，讓我們一起去看看把分辨率設(shè)置為24后取哈希的情況吧。

結(jié)果

我把原來的哈希函數(shù)換成了這個新的均值哈希函數(shù)，并重新計算分析。瞧，出現(xiàn)了太多的匹配幀!匹配幀太多了，沒辦法全部顯示出來，這里我顯示了同一桶中的一些數(shù)據(jù)：

• 4262
• 72096
• 124855
• 132392
• 147466
• 162540
• 170077
• 185151
• 207762
• 252984
• etc…

這些都是我們找到的重復(fù)幀。將它們轉(zhuǎn)換為大概的時間戳(以秒為單位，譯者注：視頻鏈接指向YouTube網(wǎng)站，請科學(xué)上網(wǎng))：

• 142.07
• 2403.2
• 4161.83
• 4413.07
• 4915.53
• 5418.0
• 5669.23
• 6171.7
• 6925.4
• etc…

好極了!

如果你想要查看這些重復(fù)的位置，你可以看看這段視頻剪輯。它正好發(fā)生在掌摑的中間! 雖說不一定能保證每個匹配幀都能找到，但是這比我們以前做的要詳細(xì)得多，我認(rèn)為這已經(jīng)夠好了。

我并沒有訂閱這個YouTube用戶，所以我不知道這個視頻是一個內(nèi)部笑話還是其他什么(它發(fā)布于4月1日)，但這絕對是一個有趣的項目。