首頁>技術>

針對這個問題,請教了演算法組的同事,他分享了基本的思路:

對於這種影象搜尋的演算法,一般是三個步驟:

1. 將目標圖片進行特徵提取,描述影象的演算法很多,用的比較多的是:SIFT描述子,指紋演算法函式,bundling features演算法,hash function(雜湊函式)等。也可以根據不同的影象,設計不同的演算法,比如影象區域性N階矩的方法提取影象特徵。

2. 將影象特徵資訊進行編碼,並將海量影象編碼做查詢表。對於目標影象,可以對解析度較大的影象進行降取樣,減少運算量後在進行影象特徵提取和編碼處理。

3. 相似度匹配運算:利用目標影象的編碼值,在影象搜尋引擎中的影象資料庫進行全域性或是區域性的相似度計算;根據所需要的魯棒性,設定閾值,然後將相似度高的圖片預保留下來;最後應該還有一步篩選最佳匹配圖片,這個應該還是用到特徵檢測演算法。

其中每個步驟都有很多演算法研究,圍繞數學、統計學、影象編碼、訊號處理等理論進行研究。

下面是阮一峰的一個最簡單的實現:

你輸入Google圖片的網址,或者直接上傳圖片,Google就會找出與其相似的圖片。下面這張圖片是美國女演員Alyson Hannigan。

上傳後,Google返回如下結果:

這種技術的原理是什麼?計算機怎麼知道兩張圖片相似呢?

根據Neal Krawetz博士的解釋,原理非常簡單易懂。我們可以用一個快速演算法,就達到基本的效果。

這裡的關鍵技術叫做”感知雜湊演算法”(Perceptual hash algorithm),它的作用是對每張圖片生成一個”指紋”(fingerprint)字串,然後比較不同圖片的指紋。結果越接近,就說明圖片越相似。

下面是一個最簡單的實現:

第一步,縮小尺寸。

將圖片縮小到8×8的尺寸,總共64個畫素。這一步的作用是去除圖片的細節,只保留結構、明暗等基本資訊,摒棄不同尺寸、比例帶來的圖片差異。

第二步,簡化色彩。

將縮小後的圖片,轉為64級灰度。也就是說,所有畫素點總共只有64種顏色。

第三步,計算平均值。

計算所有64個畫素的灰度平均值。

第四步,比較畫素的灰度。

將每個畫素的灰度,與平均值進行比較。大於或等於平均值,記為1;小於平均值,記為0。

第五步,計算雜湊值。

將上一步的比較結果,組合在一起,就構成了一個64位的整數,這就是這張圖片的指紋。組合的次序並不重要,只要保證所有圖片都採用同樣次序就行了。

得到指紋以後,就可以對比不同的圖片,看看64位中有多少位是不一樣的。在理論上,這等同於計算”漢明距離”(Hamming distance)。如果不相同的資料位不超過5,就說明兩張圖片很相似;如果大於10,就說明這是兩張不同的圖片。

具體的程式碼實現,可以參見Wote用python語言寫的imgHash.py。程式碼很短,只有53行。使用的時候,第一個引數是基準圖片,第二個引數是用來比較的其他圖片所在的目錄,返回結果是兩張圖片之間不相同的資料位數量(漢明距離)。

這種演算法的優點是簡單快速,不受圖片大小縮放的影響,缺點是圖片的內容不能變更。如果在圖片上加幾個文字,它就認不出來了。所以,它的最佳用途是根據縮圖,找出原圖。

實際應用中,往往採用更強大的pHash演算法和SIFT演算法,它們能夠識別圖片的變形。只要變形程度不超過25%,它們就能匹配原圖。這些演算法雖然更復雜,但是原理與上面的簡便演算法是一樣的,就是先將圖片轉化成Hash字串,然後再進行比較。

原文:http://blog.jobbole.com/20536/

  • BSA-TRITC(10mg/ml) TRITC-BSA 牛血清白蛋白改性標記羅丹明
  • 計算機組成原理(二)- 學什麼?如何學?