Google圖片搜索的原理
發(fā)布時(shí)間：2022-09-27 點(diǎn)擊：640
google的搜索引擎算法是強(qiáng)大的，針對(duì)這個(gè)問(wèn)題，一些人址請(qǐng)教了算法組的朋友，他們分享了基本的思路，在這里表示感謝：
對(duì)于這種圖像搜索的算法，一般是三個(gè)步驟：
1. 將目標(biāo)圖片進(jìn)行特征提取，描述圖像的算法很多，用的比較多的是：sift描述子，指紋算法函數(shù)，bundling features算法，hash function(散列函數(shù))等。也可以根據(jù)不同的圖像，設(shè)計(jì)不同的算法，比如圖像局部n階矩的方法提取圖像特征。
2. 將圖像特征信息進(jìn)行編碼，并將海量圖像編碼做查找表。對(duì)于目標(biāo)圖像，可以對(duì)分辨率較大的圖像進(jìn)行降采樣，減少運(yùn)算量后在進(jìn)行圖像特征提取和編碼處理。
3. 相似度匹配運(yùn)算：利用目標(biāo)圖像的編碼值，在圖像搜索引擎中的圖像數(shù)據(jù)庫(kù)進(jìn)行全局或是局部的相似度計(jì)算;根據(jù)所需要的魯棒性，設(shè)定閾值，然后將相似度高的圖片預(yù)保留下來(lái);最后應(yīng)該還有一步篩選最佳匹配圖片，這個(gè)應(yīng)該還是用到特征檢測(cè)算法。
其中每個(gè)步驟都有很多算法研究，圍繞數(shù)學(xué)，統(tǒng)計(jì)學(xué)，圖像編碼，信號(hào)處理等理論進(jìn)行研究。
下面是阮一峰的一個(gè)最簡(jiǎn)單的實(shí)現(xiàn)：
你輸入google圖片的網(wǎng)址，或者直接上傳圖片，google就會(huì)找出與其相似的圖片。下面這張圖片是美國(guó)女演員alyson hannigan。
上傳后，google返回如下結(jié)果：
這種技術(shù)的原理是什么?計(jì)算機(jī)怎么知道兩張圖片相似呢?
根據(jù)neal krawetz博士的解釋?zhuān)矸浅：?jiǎn)單易懂。我們可以用一個(gè)快速算法，就達(dá)到基本的效果。
這里的關(guān)鍵技術(shù)叫做"感知哈希算法"(perceptual hash algorithm)，它的作用是對(duì)每張圖片生成一個(gè)"指紋"(fingerprint)字符串，然后比較不同圖片的指紋。結(jié)果越接近，就說(shuō)明圖片越相似。
下面是一個(gè)最簡(jiǎn)單的實(shí)現(xiàn)：
第一步，縮小尺寸。
將圖片縮小到8x8的尺寸，總共64個(gè)像素。這一步的作用是去除圖片的細(xì)節(jié)，只保留結(jié)構(gòu)、明暗等基本信息，摒棄不同尺寸、比例帶來(lái)的圖片差異。
第二步，簡(jiǎn)化色彩。
將縮小后的圖片，轉(zhuǎn)為64級(jí)灰度。也就是說(shuō)，所有像素點(diǎn)總共只有64種顏色。
第三步，計(jì)算平均值。
計(jì)算所有64個(gè)像素的灰度平均值。
第四步，比較像素的灰度。
將每個(gè)像素的灰度，與平均值進(jìn)行比較。大于或等于平均值，記為1;小于平均值，記為0。
第五步，計(jì)算哈希值。
將上一步的比較結(jié)果，組合在一起，就構(gòu)成了一個(gè)64位的整數(shù)，這就是這張圖片的指紋。組合的次序并不重要，只要保證所有圖片都采用同樣次序就行了。
得到指紋以后，就可以對(duì)比不同的圖片，看看64位中有多少位是不一樣的。在理論上，這等同于計(jì)算"漢明距離"(hamming distance)。如果不相同的數(shù)據(jù)位不超過(guò)5，就說(shuō)明兩張圖片很相似;如果大于10，就說(shuō)明這是兩張不同的圖片。
具體的代碼實(shí)現(xiàn)，可以參見(jiàn)wote用python語(yǔ)言寫(xiě)的imghash.py。代碼很短，只有53行。使用的時(shí)候，第一個(gè)參數(shù)是基準(zhǔn)圖片，第二個(gè)參數(shù)是用來(lái)比較的其他圖片所在的目錄，返回結(jié)果是兩張圖片之間不相同的數(shù)據(jù)位數(shù)量(漢明距離)。
這種算法的優(yōu)點(diǎn)是簡(jiǎn)單快速，不受圖片大小縮放的影響，缺點(diǎn)是圖片的內(nèi)容不能變更。如果在圖片上加幾個(gè)文字，它就認(rèn)不出來(lái)了。所以，它的最佳用途是根據(jù)縮略圖，找出原圖。
實(shí)際應(yīng)用中，往往采用更強(qiáng)大的phash算法和sift算法，它們能夠識(shí)別圖片的變形。只要變形程度不超過(guò)25%，它們就能匹配原圖。這些算法雖然更復(fù)雜，但是原理與上面的簡(jiǎn)便算法是一樣的，就是先將圖片轉(zhuǎn)化成hash字符串，然后再進(jìn)行比較。
從Google身上反思創(chuàng)新：中國(guó)互聯(lián)網(wǎng)的差距
分享7個(gè)谷歌瀏覽器SEO利器
外貿(mào)網(wǎng)站推廣主要的細(xì)節(jié)
外貿(mào)網(wǎng)站SEO如何做好優(yōu)化工作
外貿(mào)營(yíng)銷(xiāo)型網(wǎng)站的用戶(hù)體驗(yàn)如何提升?
SEO小貼士讓你像谷歌一樣思考
http狀態(tài)碼中英文詳解
Google優(yōu)化方法及Google SEO策略
對(duì)于這種圖像搜索的算法，一般是三個(gè)步驟：
1. 將目標(biāo)圖片進(jìn)行特征提取，描述圖像的算法很多，用的比較多的是：sift描述子，指紋算法函數(shù)，bundling features算法，hash function(散列函數(shù))等。也可以根據(jù)不同的圖像，設(shè)計(jì)不同的算法，比如圖像局部n階矩的方法提取圖像特征。
2. 將圖像特征信息進(jìn)行編碼，并將海量圖像編碼做查找表。對(duì)于目標(biāo)圖像，可以對(duì)分辨率較大的圖像進(jìn)行降采樣，減少運(yùn)算量后在進(jìn)行圖像特征提取和編碼處理。
3. 相似度匹配運(yùn)算：利用目標(biāo)圖像的編碼值，在圖像搜索引擎中的圖像數(shù)據(jù)庫(kù)進(jìn)行全局或是局部的相似度計(jì)算;根據(jù)所需要的魯棒性，設(shè)定閾值，然后將相似度高的圖片預(yù)保留下來(lái);最后應(yīng)該還有一步篩選最佳匹配圖片，這個(gè)應(yīng)該還是用到特征檢測(cè)算法。
其中每個(gè)步驟都有很多算法研究，圍繞數(shù)學(xué)，統(tǒng)計(jì)學(xué)，圖像編碼，信號(hào)處理等理論進(jìn)行研究。
下面是阮一峰的一個(gè)最簡(jiǎn)單的實(shí)現(xiàn)：
你輸入google圖片的網(wǎng)址，或者直接上傳圖片，google就會(huì)找出與其相似的圖片。下面這張圖片是美國(guó)女演員alyson hannigan。
上傳后，google返回如下結(jié)果：
這種技術(shù)的原理是什么?計(jì)算機(jī)怎么知道兩張圖片相似呢?
根據(jù)neal krawetz博士的解釋?zhuān)矸浅：?jiǎn)單易懂。我們可以用一個(gè)快速算法，就達(dá)到基本的效果。
這里的關(guān)鍵技術(shù)叫做"感知哈希算法"(perceptual hash algorithm)，它的作用是對(duì)每張圖片生成一個(gè)"指紋"(fingerprint)字符串，然后比較不同圖片的指紋。結(jié)果越接近，就說(shuō)明圖片越相似。
下面是一個(gè)最簡(jiǎn)單的實(shí)現(xiàn)：
第一步，縮小尺寸。
將圖片縮小到8x8的尺寸，總共64個(gè)像素。這一步的作用是去除圖片的細(xì)節(jié)，只保留結(jié)構(gòu)、明暗等基本信息，摒棄不同尺寸、比例帶來(lái)的圖片差異。
第二步，簡(jiǎn)化色彩。
將縮小后的圖片，轉(zhuǎn)為64級(jí)灰度。也就是說(shuō)，所有像素點(diǎn)總共只有64種顏色。
第三步，計(jì)算平均值。
計(jì)算所有64個(gè)像素的灰度平均值。
第四步，比較像素的灰度。
將每個(gè)像素的灰度，與平均值進(jìn)行比較。大于或等于平均值，記為1;小于平均值，記為0。
第五步，計(jì)算哈希值。
將上一步的比較結(jié)果，組合在一起，就構(gòu)成了一個(gè)64位的整數(shù)，這就是這張圖片的指紋。組合的次序并不重要，只要保證所有圖片都采用同樣次序就行了。
得到指紋以后，就可以對(duì)比不同的圖片，看看64位中有多少位是不一樣的。在理論上，這等同于計(jì)算"漢明距離"(hamming distance)。如果不相同的數(shù)據(jù)位不超過(guò)5，就說(shuō)明兩張圖片很相似;如果大于10，就說(shuō)明這是兩張不同的圖片。
具體的代碼實(shí)現(xiàn)，可以參見(jiàn)wote用python語(yǔ)言寫(xiě)的imghash.py。代碼很短，只有53行。使用的時(shí)候，第一個(gè)參數(shù)是基準(zhǔn)圖片，第二個(gè)參數(shù)是用來(lái)比較的其他圖片所在的目錄，返回結(jié)果是兩張圖片之間不相同的數(shù)據(jù)位數(shù)量(漢明距離)。
這種算法的優(yōu)點(diǎn)是簡(jiǎn)單快速，不受圖片大小縮放的影響，缺點(diǎn)是圖片的內(nèi)容不能變更。如果在圖片上加幾個(gè)文字，它就認(rèn)不出來(lái)了。所以，它的最佳用途是根據(jù)縮略圖，找出原圖。
實(shí)際應(yīng)用中，往往采用更強(qiáng)大的phash算法和sift算法，它們能夠識(shí)別圖片的變形。只要變形程度不超過(guò)25%，它們就能匹配原圖。這些算法雖然更復(fù)雜，但是原理與上面的簡(jiǎn)便算法是一樣的，就是先將圖片轉(zhuǎn)化成hash字符串，然后再進(jìn)行比較。
從Google身上反思創(chuàng)新：中國(guó)互聯(lián)網(wǎng)的差距
分享7個(gè)谷歌瀏覽器SEO利器
外貿(mào)網(wǎng)站推廣主要的細(xì)節(jié)
外貿(mào)網(wǎng)站SEO如何做好優(yōu)化工作
外貿(mào)營(yíng)銷(xiāo)型網(wǎng)站的用戶(hù)體驗(yàn)如何提升?
SEO小貼士讓你像谷歌一樣思考
http狀態(tài)碼中英文詳解
Google優(yōu)化方法及Google SEO策略