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

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

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

計(jì)劃

寫(xiě)一個(gè)程序來(lái)檢測(cè)視頻中是否有循環(huán)。我之前從來(lái)沒(méi)有用Python處理過(guò)視頻，所以這對(duì)我來(lái)說(shuō)有點(diǎn)難度。

首次嘗試

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

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

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

代碼如下：

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):   
 
        # 獲取單個(gè)幀   
 
        frame = vid.get_data(x)   
 
   
 
        # 取幀的哈希值   
 
        hashed = hash(frame.tostring())   
 
   
 
        if seen_frames.get( hashed, None):   
 
            # 如果之前看到過(guò)這一幀，則添加到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上跑了大約一個(gè)小時(shí)。 我們來(lái)看看結(jié)果： 

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

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

情況變復(fù)雜了

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

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

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

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

簡(jiǎn)化我們的壓縮問(wèn)題

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

然而，對(duì)于我們來(lái)說(shuō)，又有新的麻煩了，因?yàn)槲覀兲幚淼牟⒉煌耆菆D像，而是一系列的圖像，每一張圖片都是相差1/30秒。這意味著我們的哈希函數(shù)需要：

• 足夠的寬松，兩個(gè)僅因?yàn)閴嚎s而產(chǎn)生噪聲的幀的哈希值是相同的
• 足夠的靈敏，兩個(gè)相鄰幀的哈希值是不同的

這可能很復(fù)雜。

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

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

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

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

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

上述的解釋是，第8幀和第108幀相同。第9幀和第109幀相同，但不同于8、108。第10、11、110、111幀與其他幀都不同，但彼此相同。這種情況很有可能發(fā)生，因?yàn)樗惴ú⒉煌昝?，偶爾也?huì)混淆，認(rèn)為兩個(gè)相鄰的幀是相同的。我們看看下面這幾個(gè)數(shù)字：

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

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

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

結(jié)果

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

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

這些都是我們找到的重復(fù)幀。將它們轉(zhuǎn)換為大概的時(shí)間戳(以秒為單位，譯者注：視頻鏈接指向YouTube網(wǎng)站，請(qǐ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ā)生在掌摑的中間! 雖說(shuō)不一定能保證每個(gè)匹配幀都能找到，但是這比我們以前做的要詳細(xì)得多，我認(rèn)為這已經(jīng)夠好了。

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