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

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

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

 

 

 

計劃

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

首次嘗試

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

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

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

代碼如下：

def find_duplicates():   
 
    # 載入視頻文件   
 
    filename = 'video.mp4'   
 
    vid = imageio.get_reader(filename,  'ffmpeg')   
 
    all_frames = vid.get_length()   
 
   
 
    # 重復的幀保存在這里   
 
    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]   
 
   
 
    # 返回重復幀列表的列表   
 
    return [dup_frames[x] for x in dup_frames if len(dup_frames[x]) > 1]  

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

 

 

 

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

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

情況變復雜了

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

等等…… 這兩個圖像看起來是一樣的啊!但是他們為什么沒有標記為匹配呢?我們可以把其中一個幀減去另外一個幀來找出不同之處。這個減法是對每個像素的紅、綠、藍的值分別做減法。 

 

 

 

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

對上面的說明總結一下，當我將數據存儲在字典中時，我取了每個圖像的哈希。哈希函數將圖像(數組)轉換為整數。如果兩個圖像完全相同，則哈希函數將得到相同的整數。如果兩個圖像不同，我們將得到兩個不同的整數。但是我們實際想要的是，如果兩個圖像只是稍微不同，我們然仍然能得到相同的整數。

簡化我們的壓縮問題

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

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

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

這可能很復雜。

均值哈希的參數選擇

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

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

 

 

 

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

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

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

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

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

 

 

 

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

結果

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

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

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

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

好極了!

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

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