相似圖像查找的基礎演算法邏輯是如何的？

01-14

類似google的相似圖片查找，其演算法基礎是如何的？

說個最簡單粗暴的方法吧，color histogram方法。

把RGB顏色空間按照2:4:2（還有其他比例，記得不是很清楚）劃分成16塊，然後對每張圖片數落在每塊里的像素數目，構成一個16維向量。

對於待檢索的輸入圖片，用同樣的方法算出這個向量，跟圖片庫里所有向量用餘弦定理算角度，這個角度就是相似度。恩，返回相似度最大的n張圖/相似度大於某個閾值的所有圖，或者如果圖片庫里的圖都是有tag標記的，返回平均相似度最高的tag（相當於分類器）

這演算法太尼瑪粗糙了而且居然真的work。。缺點也非常明顯，完全沒有利用圖片的輪廓信息，對付灰度圖效果很差，純黑白圖沒轍。

問題本質就是把圖片變成某種維數較低的feature，然後在feature space里算距離。

用什麼feature，現在有深度學習大法，肯定可以搞出比較強的feature。我感覺Auto-encoder就可以干這個。。。

在我記憶中看到過一種演算法(記不得出處了也懶得查):

首先將所有伺服器上的圖像分割成8*8的方塊區域(尺寸不固定為8*8, 可以為其他值), 然後將方塊區域的平均灰度值作為此方塊的特徵值(也可以取中值或方差或一些組合值), 保存這個8*8的圖片為此圖像的一個映射, 當用戶上傳一張圖片A時, 我們只需對A進行一次上述操作, 再遍歷圖像庫中存儲的所有映射, 求出差異最小且滿足一定閾值條件的映射對應的圖像B, 返回即可.
這種方法對於拉伸一類的變換魯棒性較高.

以上.

阮一峰曾經就這個問題做過一個很不錯的分析，就不轉過來了，有興趣的可以點連接過去看看~大量乾貨喲~

相似圖片搜索的原理

相似圖片搜索的原理（二）

這個是我們上個學期大作業的選題。

我們採用的方法是color histogram+3*3格子的平均顏色。其實這個方法在我們當時的數據集上準確率算很高的了。考慮了顏色又考慮了形狀。。然後用knn演算法發現找瓶子特別准。之後我們又用各種機器學習的辦法來搞，發現隨機森林真是好東西 0 0。。

我們另外採用的辦法還有SIFT什麼的，好像還試圖用顏色生長來除去背景，還是有效果的，只不過比較狗就是了。。Orz

相似圖像搜索個人覺得是一片很深的水域，研究相似圖像檢索接近兩年，先回答題主問的基礎演算法邏輯，然後在做些拓展及個人對圖像檢索的一些理解。

先說說相似圖像搜索分類：主要分基於文本的圖像搜索（TBIR）和基於（CBIR），在相似圖像搜索發展的早期，採取TBIR較多，主要是那時候在互聯網沒有發展起來時圖像庫一般都很小，完全可以採用人工標註後去做搜索；後來隨著互聯網的迅速發展以及移動設備的普及，圖像在互聯網上爆炸式增長，相應的圖像庫也變得極其龐大，動則就是百萬，所以大概從90年代開始，人們開始探索CBIR技術。

CBIR技術可以說是現代相似圖像搜索演算法邏輯的基礎，它最初最簡單的方法是：在圖像庫中對每幅圖像提取它們的特徵，比如顏色直方圖，紋理，形狀等，當然還有後來很多比較高級的特徵，比如bovw、FV(fisher向量）、VLAD、卷積網路CNN提取的特徵等，對於進來的查詢圖像，同樣提取對應的特徵，然後採用某種距離比如歐式距離進行相似度量，再根據計算出來的相似性做一個從大到小的排序即可。

對於CBIR技術，同樣可以做一個簡要的分類：2000年以前CBIR主要側重在探索比較有效的圖像特徵；而2000年以後，隨著機器學習的發展，人們將視野從尋求比較有效的特徵轉移到對特徵數據的分析上，以及怎樣建立高效的索引機制。

相關問題：如果一年後研究生畢業想進BAT，現在應該怎麼準備，女生，圖像檢索方向？

大概分兩步，第一是找特徵值，第二是計算距離......先mark一下，上完課在具體說(苦逼學生黨)

---------- 分割線 --------

特徵值的選取有很多方法，有一般就是像@lancelod所說，基本想法是將圖片弄成n*n的小圖片並去掉細節內容(將像素調至統一大小，像素統一調低)，將圖片灰度化，去除色彩，根據灰度確定一個閾值，然後轉換成01矩陣。有一種確定閾值的方法叫大律法(或者叫最大類間方差法 )，其演算法思想是使分配後的方差儘可能的大(細節請挪步http://wapbaike.baidu.com/item/otsu/16252828)。現在通過這麼多處理得到了一個圖片的特徵值的01矩陣，之後可以將兩個圖片的特徵矩陣同或，然後數1的個數。

當然，特徵值的處理也可以直接對圖片的灰度矩陣進行處理，計算兩個圖片灰度矩陣相應元素的差值，之後求這些差值的方差，方差小的就相似(只是初步想法，沒有驗證可行性)。像這樣確定特徵值的方法很多，只要可以提取特徵，咋都可以整。當然演算法要進行驗分析，這是後話。

現有比較成熟的應用就是google使用的感知哈希演算法(PHA) (細節請挪步http://wapbaike.baidu.com/view/10360775.htm)。圖片所包含的特徵被用來生成一組指紋（而不是上述所說的矩陣）,之後將這些指紋放入資料庫。需要的時候就進行比較(距離使用Hammingdistance)。

最後附上相關的問題 http://www.zhihu.com/question/19726630

沒時間詳細解答了具體請搜索 phash

題主如果有時間可以稍微關注一下我們的cdvs(compact discriptor for visual search)

今年已經作為國際標準發布了

我記得樓上說的16緯向量的方法是google用的，糙快猛的演算法語氣說是圖匹配不如說是給出縮略圖求原圖。。。據說百度用得學習方法，雖然效果也一般的感覺。

有sift演算法，很強。

當然SIFT演算法做搜索需要的運算力會大一點。