大概五年前吧，我那時(shí)還在為一家約會(huì)網(wǎng)站做開發(fā)工作。他們是早期創(chuàng)業(yè)公司，但他們也開始擁有了一些穩(wěn)定用戶量。不像其他約會(huì)網(wǎng)站，這家公司向來以潔身自好為主要市場形象。它不是一個(gè)供你鬼混的網(wǎng)站——是讓你能找到忠實(shí)伴侶的地方。

由于投入了數(shù)以百萬計(jì)的風(fēng)險(xiǎn)資本（在US大蕭條之前），他們關(guān)于真愛并找尋靈魂伴侶的在線廣告勢如破竹。Forbes(福布斯，美國著名財(cái)經(jīng)雜志)采訪了他們。全國性電視節(jié)目也對(duì)他們進(jìn)行了專訪。早期的成功促成了事業(yè)起步時(shí)讓人垂涎的指數(shù)級(jí)增長現(xiàn)象——他們的用戶數(shù)量以每月加倍的速度增長。對(duì)他們而言，一切都似乎順風(fēng)順?biāo)?/p>

但他們有一個(gè)嚴(yán)重的問題——色情問題。

該約會(huì)網(wǎng)站的用戶中會(huì)有一些人上傳色情圖片，然后設(shè)置為其個(gè)人頭像。這種行為破壞了很多其他用戶的體驗(yàn)——導(dǎo)致很多用戶取消了會(huì)員。

可能對(duì)于現(xiàn)在的一些約會(huì)網(wǎng)站隨處可見幾張色情圖片也許并不能稱之為是問題。或者可以說是習(xí)以為常甚至有些期待，只是一個(gè)被接受然后被無視的在線約會(huì)的副產(chǎn)品。

然而，這樣的行為既不應(yīng)該被接受也應(yīng)該被忽視。

別忘了，這次創(chuàng)業(yè)可是將自己定位在優(yōu)秀的約會(huì)天堂，免于用戶受到困擾其他約會(huì)網(wǎng)站的污穢和垃圾的煩擾。簡而言之，他們擁有很實(shí)在的以風(fēng)險(xiǎn)資本作為背后支撐的名聲，而這也正是他們需要保持的風(fēng)格。

該約會(huì)網(wǎng)站為了能迅速阻止色情圖片的爆發(fā)可以說是不顧一切了。他們雇傭了圖片論壇版主團(tuán)隊(duì)，真是不做其他事只是每天盯著監(jiān)管頁面8個(gè)小時(shí)以上，然后移除任何被上傳到社交網(wǎng)絡(luò)的色情圖片。

毫不夸張的說，他們投入了數(shù)萬美元（更不用說數(shù)不清的人工小時(shí)）來解決這個(gè)問題，然而也僅僅只是緩解，控制情況不變嚴(yán)重而不是在源頭上阻止。

色情圖片的爆發(fā)在2009年的七月達(dá)到了臨界水平。8個(gè)月來第一次用戶量沒能翻倍（甚至已經(jīng)開始減少了）。更糟糕的是，投資者聲稱若該公司不能解決這個(gè)問題將會(huì)撤資。事實(shí)上，污穢的潮汐早已開始沖擊這座象牙塔了，將它推翻流入大海也不過是時(shí)間問題。

正在這個(gè)約會(huì)網(wǎng)站巨頭快要撐不住時(shí)，我提出了一個(gè)更魯棒的長期解決方案：如果我們使用圖片指紋來與色情圖片的爆發(fā)斗爭呢？

你看，每張圖片都有一個(gè)指紋。正如人的指紋可以識(shí)別人，圖片的指紋能識(shí)別圖片。

這促使了一個(gè)三階段算法的實(shí)現(xiàn)：

1. 為不雅圖片建立指紋，然后將圖片指紋存儲(chǔ)在一個(gè)數(shù)據(jù)庫中。

2. 當(dāng)一個(gè)用戶上傳一份新的頭像時(shí)，我們會(huì)將它與數(shù)據(jù)庫中的圖片指紋對(duì)比。如果上傳圖片的指紋與數(shù)據(jù)庫任意一個(gè)不雅圖片指紋相符，我們就阻止用戶將該圖片設(shè)置為個(gè)人頭像。

3. 當(dāng)圖片監(jiān)管人標(biāo)記新的色情圖片時(shí)，這些圖片也被賦予指紋并存入我們的數(shù)據(jù)庫，建立一個(gè)能用于阻止非法上傳且不斷進(jìn)化的數(shù)據(jù)庫。

我們的方法，盡管不十分完美，但是也卓有成效。慢慢地，色情圖片爆發(fā)的情況有所減慢。它永遠(yuǎn)不會(huì)消失——但這個(gè)算法讓我們成功將非法上傳的數(shù)量減少了80%以上。

這也挽回了投資者的心。他們繼續(xù)為我們提供資金支持——直到蕭條到來，我們都失業(yè)了。

回顧過去時(shí)，我不禁笑了。我的工作并沒持續(xù)太久。這個(gè)公司也沒有堅(jiān)持太久。甚至還有幾個(gè)投資者卷鋪蓋走人了。

但有一樣確實(shí)存活了下來。提取圖片指紋的算法。幾年之后，我把這個(gè)算法的基本內(nèi)容分享出來，期望你們可以將它應(yīng)用到你們自己的項(xiàng)目中。

但最大的問題是，我們怎么才能建立圖片指紋呢？

繼續(xù)讀下去一探究竟吧。
即將要做的事情

我們打算用圖片指紋進(jìn)行相似圖片的檢測。這種技術(shù)通常被稱為“感知圖像hash”或是簡單的“圖片hash”。
什么是圖片指紋/圖片哈希

圖片hash是檢測一張圖片的內(nèi)容然后根據(jù)檢測的內(nèi)容為圖片建立一個(gè)唯一值的過程。

比如，看看本文最上面的那張圖片。給定一張圖片作為輸入，應(yīng)用一個(gè)hash函數(shù)，然后基于圖片的視覺計(jì)算出一個(gè)圖片hash。相似的圖片也應(yīng)當(dāng)有相似的hash值。圖片hash算法的應(yīng)用使得相似圖片的檢測變得相當(dāng)簡單了。

特別地，我們將會(huì)使用“差別Hash”或簡單的DHash算法計(jì)算圖片指紋。簡單來說，DHash算法著眼于兩個(gè)相鄰像素之間的差值。然后，基于這樣的差值，就建立起一個(gè)hash值了。
為什么不使用md5,sha-1等算法？

不幸的是，我們不能在實(shí)現(xiàn)中使用加密hash算法。由于加密hash算法的本質(zhì)使然，輸入文件中非常微小的差別也能造成差異極大的hash值。而在圖片指紋的案例中，我們實(shí)際上希望相似的輸入可以有相似的hash輸出值。
圖片指紋可以用在哪里？

正如我上面舉的例子，你可以使用圖片指紋來維護(hù)一個(gè)保存不雅圖片的數(shù)據(jù)庫——當(dāng)用戶嘗試上傳類似圖片時(shí)可以發(fā)出警告。

你可以建立一個(gè)圖片的逆向搜索引擎，比如TinEye，它可以記錄圖片以及它們出現(xiàn)的相關(guān)網(wǎng)頁。

你還可以使用圖片指紋幫助管理你個(gè)人的照片收集。假設(shè)你有一個(gè)硬盤，上面有你照片庫的一些局部備份，但需要一個(gè)方法刪除局部備份，一張圖片僅保留一份唯一的備份——圖片指紋可以幫你做到。

簡單來說，你幾乎可以將圖片指紋/哈希用于任何需要你檢測圖片的相似副本的場景中。
需要的庫有哪些？

為了建立圖片指紋方案，我們打算使用三個(gè)主要的Python包：

1. PIL/Pillow用于讀取和載入圖片
2. ImageHash，包括DHash的實(shí)現(xiàn)
3. 以及NumPy/SciPy，ImageHash的依賴包

你可以使用下列命令一鍵安裝所需要的必備庫：
 

$ pip install pillow imagehash

第一步：為一個(gè)圖片集建立指紋

第一步就是為我們的圖片集建立指紋。

也許你會(huì)問，但我們不會(huì)，我們不會(huì)使用那些我為那家約會(huì)網(wǎng)站工作時(shí)的色情圖片。相反，我創(chuàng)建了一個(gè)可供使用的人工數(shù)據(jù)集。

對(duì)計(jì)算機(jī)視覺的研究人員而言，數(shù)據(jù)集CALTECH-101 是一個(gè)傳奇般的存在。它包含來自101個(gè)不同分類中的至少7500張圖片，內(nèi)容分別有人物，摩托車和飛機(jī)。

從這7500多張圖片中，我隨機(jī)的挑選了17張。

然后，從這17張隨機(jī)挑選的圖片中，以幾個(gè)百分點(diǎn)的比例隨機(jī)放大/縮小并創(chuàng)建N張新圖片。這里我們的目標(biāo)是找到這些近似副本的圖片——有點(diǎn)大海撈針的感覺。

你也想創(chuàng)建一個(gè)類似的數(shù)據(jù)集用于工作嗎？那就下載CALTECH-101 數(shù)據(jù)集，抽取大概17張圖片即可，然后運(yùn)行repo下的腳本文件gather.py。

回歸正題，這些圖片除了寬度和高度，其他各方面都是一樣的。而且因?yàn)樗麄儧]有相同的形狀，我們不能依賴簡單的md5校驗(yàn)和。最重要的是，有相似內(nèi)容的圖片可能有完全不相同的md5哈希。然而，采取圖片哈希，相似內(nèi)容的圖片也有相似的哈希指紋。

所以趕緊開始寫代碼為數(shù)據(jù)集建立指紋吧。創(chuàng)建一個(gè)新文件，命名為index.py，然后開始工作：

# import the necessary packages
from PIL import Image
import imagehash
import argparse
import shelve
import glob
 
# construct the argument parse and parse the arguments
ap = argparse.ArgumentParser()
ap.add_argument("-d", "--dataset", required = True,
help = "path to input dataset of images")
ap.add_argument("-s", "--shelve", required = True,
help = "output shelve database")
args = vars(ap.parse_args())
 
# open the shelve database
db = shelve.open(args["shelve"], writeback = True)

要做的第一件事就是引入我們需要的包。我們將使用PIL或Pillow中的Image類載入硬盤上的圖片。這個(gè)imagehash庫可以被用于構(gòu)建哈希算法。

Argparse庫用于解析命令行參數(shù)，shelve庫用作一個(gè)存儲(chǔ)在硬盤上的簡單鍵值對(duì)數(shù)據(jù)庫（Python字典）。glob庫能很容易的獲取圖片路徑。

然后傳遞命令行參數(shù)。第一個(gè)，—dataset是輸入圖片庫的路徑。第二個(gè)，—shelve是shelve數(shù)據(jù)庫的輸出路徑。

下一步，打開shelve數(shù)據(jù)庫以寫數(shù)據(jù)。這個(gè)db數(shù)據(jù)庫存儲(chǔ)圖片哈希。更多的如下所示：
 

# loop over the image dataset
for imagePath in glob.glob(args["dataset"] + "/*.jpg"):
  # load the image and compute the difference hash
  image = Image.open(imagePath)
  h = str(imagehash.dhash(image))
 
  # extract the filename from the path and update the database
  # using the hash as the key and the filename append to the
  # list of values
  filename = imagePath[imagePath.rfind("/") + 1:]
  db[h] = db.get(h, []) + [filename]
 
# close the shelf database
db.close()

以上就是大部分工作的內(nèi)容了。開始循環(huán)從硬盤讀取圖片，創(chuàng)建圖片指紋并存入數(shù)據(jù)庫。

現(xiàn)在，來看看整個(gè)范例中最重要的兩行代碼：
 

filename = imagePath[imagePath.rfind("/") + 1:]
db[h] = db.get(h, []) + [filename]

正如本文早些時(shí)候提到的，有相同指紋的圖片被認(rèn)為是一樣的。

因此，如果我們的目標(biāo)是找到近似圖片，那就需要維護(hù)一個(gè)有相同指紋值的圖片列表。

而這也正是這幾行代碼做的事情。

前一個(gè)代碼段提取了圖片的文件名。而后一個(gè)代碼片段維護(hù)了一個(gè)有相同指紋值的圖片列表。

為了從我們的數(shù)據(jù)庫中提取圖片指紋并建立哈希數(shù)據(jù)庫，運(yùn)行下列命令：
 

$ python index.py —dataset images —shelve db.shelve

這個(gè)腳本會(huì)運(yùn)行幾秒鐘，完成后，就會(huì)出現(xiàn)一個(gè)名為db.shelve的文件，包含了圖片指紋和文件名的鍵值對(duì)。

這個(gè)基本算法正是幾年前我為這家約會(huì)創(chuàng)業(yè)公司工作時(shí)使用的算法。我們獲得了一個(gè)不雅圖片集，為其中的每張圖片構(gòu)建一個(gè)圖片指紋并將其存入數(shù)據(jù)庫。當(dāng)來一張新圖片時(shí)，我只需簡單地計(jì)算它的哈希值，檢測數(shù)據(jù)庫查看是否上傳圖片已被標(biāo)識(shí)為非法內(nèi)容。

下一步中，我將展示實(shí)際如何執(zhí)行查詢，判定數(shù)據(jù)庫中是否存在與所給圖片具有相同哈希值的圖片。
第二步：查詢數(shù)據(jù)集

既然已經(jīng)建立了一個(gè)圖片指紋的數(shù)據(jù)庫，那么現(xiàn)在就該搜索我們的數(shù)據(jù)集了。

打開一個(gè)新文件，命名為search.py，然后開始寫代碼：
 

# import the necessary packages
from PIL import Image
import imagehash
import argparse
import shelve
 
# construct the argument parse and parse the arguments
ap = argparse.ArgumentParser()
ap.add_argument("-d", "--dataset", required = True,
  help = "path to dataset of images")
ap.add_argument("-s", "--shelve", required = True,
  help = "output shelve database")
ap.add_argument("-q", "--query", required = True,
  help = "path to the query image")
args = vars(ap.parse_args())

我們需要再一次導(dǎo)入相關(guān)的包。然后轉(zhuǎn)換命令行參數(shù)。需要三個(gè)選項(xiàng)，—dataset初始圖片集的路徑，—shelve，保存鍵值對(duì)的數(shù)據(jù)庫的路徑，—query，查詢/上傳圖片的路徑。我們的目標(biāo)是對(duì)于每個(gè)查詢圖片，判定數(shù)據(jù)庫中是否已經(jīng)存在。

現(xiàn)在，寫代碼執(zhí)行實(shí)際的查詢：
 

# open the shelve database
db = shelve.open(args["shelve"])
 
# load the query image, compute the difference image hash, and
# and grab the images from the database that have the same hash
# value
query = Image.open(args["query"])
h = str(imagehash.dhash(query))
filenames = db[h]
print "Found %d images" % (len(filenames))
 
# loop over the images
for filename in filenames:
  image = Image.open(args["dataset"] + "/" + filename)
  image.show()
 
# close the shelve database
db.close()

首先打開數(shù)據(jù)庫，然后載入硬盤上的圖片，計(jì)算圖片的指紋，找到具有相同指紋的所有圖片。

如果有圖片具有相同的哈希值，會(huì)遍歷這些圖片并展示在屏幕上。

這段代碼使我們僅僅使用指紋值就能判定圖片是否已在數(shù)據(jù)庫中存在。
結(jié)果

正如本文早些時(shí)候提到的，我從CALTECH-101數(shù)據(jù)集的7500多張圖片中隨機(jī)選取17張，然后通過任意縮放一部分點(diǎn)產(chǎn)生N張新的圖片。

這些圖片在尺寸上僅僅是少數(shù)像素不同—但也是因?yàn)檫@一點(diǎn)我們不能依賴于文件的md5哈希（這一點(diǎn)已在“優(yōu)化算法”部分進(jìn)行了詳盡的描述）。然而，我們可以使用圖片哈希找到近似圖片。

打開你的終端并執(zhí)行下述命令：
 

$ python search.py —dataset images —shelve db.shelve —query images/84eba74d-38ae-4bf6-b8bd-79ffa1dad23a.jpg

如果一切順利你就可以看到下述結(jié)果：

左邊是輸入圖片。載入這張圖片，計(jì)算它的圖片指紋，在數(shù)據(jù)庫中搜索指紋查看是否存在有相同指紋的圖片。

當(dāng)然——正如右邊所示，我們的數(shù)據(jù)集中有其他兩張指紋相同的圖片。盡管從截圖中還不能十分明顯的看出，這些圖片，雖然有完全相同的視覺內(nèi)容，也不是完全相同！這三張圖片的高度寬度各不相同。

嘗試一下另外一個(gè)輸入圖片：
 

$ python search.py —dataset images —shelve db.shelve —query images/9d355a22-3d59-465e-ad14-138a4e3880bc.jpg

下面是結(jié)果：

左邊仍然是我們的輸入圖片。正如右邊展示的，我們的圖片指紋算法能夠找出具有相同指紋的三張完全相同的圖片。

最后一個(gè)例子：
 

$ python search.py —dataset images —shelve db.shelve —query images/5134e0c2-34d3-40

這一次左邊的輸入圖片是一個(gè)摩托車。拿到這張摩托車圖片，計(jì)算它的圖片指紋，然后在指紋數(shù)據(jù)庫中查找該指紋。正如我們在右邊看到的，我們也能判斷出數(shù)據(jù)庫中有三張圖片具有相同指紋。
優(yōu)化算法

有很多可以優(yōu)化本算法的方法——但最關(guān)鍵性的是要考慮到相似但不相同的哈希。

比如，本文中的圖片僅僅是一小部分點(diǎn)重組了（依比例增大或減小）。如果一張圖片以一個(gè)較大的因素調(diào)整大小，或者縱橫比被改變了，對(duì)應(yīng)的哈希就會(huì)不同了。

然而，這些圖片應(yīng)該仍然是相似的。

為了找到相似但不相同的圖片，我們需要計(jì)算漢明距離（Hamming distance）.漢明距離被用于計(jì)算一個(gè)哈希中的不同位數(shù)。因此，哈希中只有一位不同的兩張圖片自然比有10位不同的圖片更相似。

然而，我們遇到了第二個(gè)問題——算法的可擴(kuò)展性。

考慮一下：我們有一張輸入圖片，又被要求在數(shù)據(jù)庫中找到所有相似圖片。然后我們必須計(jì)算輸入圖片和數(shù)據(jù)庫中的每一張圖片之間的漢明距離。

隨著數(shù)據(jù)庫規(guī)模的增長，和數(shù)據(jù)庫比對(duì)的時(shí)間也隨著延長。最終，我們的哈希數(shù)據(jù)庫會(huì)達(dá)到一個(gè)線性比對(duì)已經(jīng)不實(shí)際的規(guī)模。

解決辦法，雖然已超出本文范圍，就是利用K-d trees和VP trees將搜索問題的復(fù)雜度從線性減小到次線性。
總結(jié)

本文中我們學(xué)會(huì)了如何構(gòu)建和使用圖片哈希來完成相似圖片的檢測。這些圖片哈希是使用圖片的視覺內(nèi)容構(gòu)建的。

正如一個(gè)指紋可以識(shí)別一個(gè)人，圖片哈希也能唯一的識(shí)別一張圖片。

使用圖片指紋的知識(shí)，我們建立了一個(gè)僅使用圖片哈希就能找到和識(shí)別具有相似內(nèi)容的圖片的系統(tǒng)。

然后我們又演示了圖片哈希是如何應(yīng)用于快速找到有相似內(nèi)容的圖片。

從repo目錄下下載代碼。

最新評(píng)論