圖像比較-快速算法

我正在尋找建立圖像的基本表，然後将其與任何新圖像進行比較，以确定新圖像是否與基礎完全相同（或近似）。

例如：如果您想減少同一圖像的存儲100次，則可以存儲它的一個副本并提供指向它的參考連結。 輸入新圖像後，您想與現有圖像進行比較以確定它不是重複的...想法嗎？

我的一個想法是縮小到小縮略圖，然後随機選擇100個像素位置并進行比較。

#1樓

這篇文章是我解決方案的起點，這裡有很多好主意，是以我雖然會分享我的結果。 我的主要見解是，我找到了一種方法，可以通過利用相移速度來解決基于關鍵點的圖像比對的緩慢性。

對于一般解決方案，最好采用幾種政策。 每種算法最适合某些類型的圖像轉換，您可以利用它。

最頂端的是最快的算法； 在最慢的底部（盡管更準确）。 如果在較快的級别找到合适的比對項，則可以跳過較慢的比對項。

• 基于檔案哈希（md5，sha1等）的精确重複項
• 縮放後的圖像的感覺哈希（phash）
• 基于特征（SIFT）的修改圖像

我的phash效果非常好。 精度對于重新縮放的圖像來說很好。 這對（在感覺上）修改過的圖像（裁剪，旋轉，鏡像等）不利。 為了處理哈希速度，我們必須使用磁盤緩存/資料庫來維護幹草堆的哈希值。

phash的真正好處是，一旦您建構了哈希資料庫（對我而言，它約為1000張圖像/秒），搜尋就可以非常非常快，特别是當您可以将整個哈希資料庫儲存在記憶體中時。 這是相當實用的，因為哈希隻有8個位元組。

例如，如果您有一百萬個圖像，則将需要一百萬個64位哈希值（8 MB）的數組。 在某些CPU上，這适合L2 / L3緩存！ 在實際使用中，我看到corei7的速度超過1 Giga-hamm / sec，這隻是CPU的記憶體帶寬問題。 一個十億圖像資料庫可以在64位CPU（需要8GB RAM）上使用，并且搜尋不會超過1秒！

對于修改/裁剪的圖像，似乎要采用像SIFT這樣的變換不變特征/關鍵點檢測器。 SIFT将産生良好的關鍵點，将檢測作物/旋轉/鏡像等。但是，與phash使用的漢明距離相比，描述符比較非常慢。 這是一個主要限制。 有很多比較要做，因為與查找一個圖像相比，最大IxJxK描述符進行比較（I =幹草堆圖像，J =每個幹草堆圖像的目标關鍵點，K =每個針圖像的目标關鍵點）。

為了解決速度問題，我嘗試在每個找到的關鍵點周圍使用phash，并使用特征大小/半徑确定子矩形。 使其正常工作的技巧是增大/縮小半徑以生成不同的子矩形水準（在針圖像上）。 通常，第一個級别（未縮放）将比對，但是經常需要更多級别。 我不是100％知道為什麼會這樣，但是我可以想象它啟用的功能太小而無法使用phash（phash将圖像縮小至32x32）。

另一個問題是，SIFT不會以最佳方式配置設定關鍵點。 如果圖像的某個部分的邊緣很多，則關鍵點将聚集在此處，而其他區域則不會有任何關鍵點。 我在OpenCV中使用GridAdaptedFeatureDetector來改善分布。 不确定哪種網格尺寸最佳，我使用的是小網格（根據圖像方向，為1x3或3x1）。

您可能希望在進行特征檢測之前将所有幹草堆圖像（和針頭）縮放到較小的尺寸（我沿最大尺寸使用210像素）。 這将減少圖像中的噪聲（對于計算機視覺算法而言始終是一個問題），還将使檢測器專注于更突出的功能。

對于人的圖像，您可以嘗試面部檢測并使用它來确定要縮放到的圖像大小和網格大小（例如，最大的臉部縮放為100px）。 特征檢測器考慮了多個比例級别（使用金字塔），但是它會使用多少個級别是有限制的（當然這是可調的）。

當關鍵點檢測器傳回的數量少于您想要的功能數量時，它可能會工作得最好。 例如，如果您要求400并取回300，那很好。 如果您每次都得到400，那麼可能不得不放棄一些出色的功能。

針圖像可以比幹草堆圖像具有更少的關鍵點，并且仍然可以獲得良好的效果。 添加更多并不一定能獲得巨大收益，例如，在J = 400和K = 40的情況下，我的點選率約為92％。 在J = 400和K = 400的情況下，命中率僅上升到96％。

我們可以利用漢明功能的極高速度來解決縮放，旋轉，鏡像等問題。可以使用多遍技術。 在每次疊代中，變換子矩形，重新哈希，然後再次運作搜尋功能。

#2樓

我公司每個月大約有2400萬張圖像來自制造商。 我一直在尋找一種快速的解決方案，以確定我們上傳到目錄中的圖像是新圖像。

我想說的是，我已經在網際網路上進行了廣泛搜尋，試圖找到理想的解決方案。 我什至開發了自己的邊緣檢測算法。

我評估了多個模型的速度和準确性。 我的圖像具有白色背景，在進行相位調整時效果非常好。 就像redcalx所說的，我推薦phash或ahash。 請勿使用MD5散列或任何其他加密散列。 除非您隻希望完全比對圖像。 圖像之間發生的任何調整大小或操作都會産生不同的哈希值。

對于phash / ahash，請檢視以下内容： imagehash

我想通過釋出代碼和準确性來擴充* redcalx的文章。

我所做的：

from PIL import Image
from PIL import ImageFilter
import imagehash

img1=Image.open(r"C:\yourlocation")
img2=Image.open(r"C:\yourlocation")
if img1.width<img2.width:
    img2=img2.resize((img1.width,img1.height))
else:
    img1=img1.resize((img2.width,img2.height))
img1=img1.filter(ImageFilter.BoxBlur(radius=3))
img2=img2.filter(ImageFilter.BoxBlur(radius=3))
phashvalue=imagehash.phash(img1)-imagehash.phash(img2)
ahashvalue=imagehash.average_hash(img1)-imagehash.average_hash(img2)
totalaccuracy=phashvalue+ahashvalue
           

這是我的一些結果：

item1  item2  totalsimilarity
desk1  desk1       3
desk1  phone1     22
chair1 desk1      17
phone1 chair1     34
           

希望這可以幫助！

#3樓

我認為，将圖像的大小降低到幾乎是圖示的大小（例如48x48），然後轉換為灰階，然後考慮像素之間的差異，即Delta，應該很好。 因為我們是在比較像素顔色的變化，而不是實際像素顔色的變化，是以圖像的亮度是多少還是暗一點都不重要。 大的變化将很重要，因為像素太亮/太暗将丢失。 您可以将其應用于一行，也可以根據需要将其應用到任意行中以提高準确性。 您最多需要進行47x47 = 2,209次減法，以形成可比較的Key。

#4樓

我所知道的最好的方法是使用感覺哈希。 在以下位置可以找到這種哈希的良好開源實作：

http://phash.org/

主要思想是，通過識别原始圖像檔案中的顯着特征并對這些特征的緊湊表示進行哈希處理（而不是直接對圖像資料進行哈希處理），将每個圖像簡化為小的哈希碼或“指紋”。 這意味着通過一種簡單的方法（例如将圖像縮小到很小的指紋大小的圖像并比較指紋）可以大大降低誤報率。

phash提供了多種類型的哈希，可用于圖像，音頻或視訊。

#5樓

如果您有大量圖像，請檢視Bloom過濾器 ，該過濾器使用多個散列來獲得機率高但效率高的結果。 如果圖像數量不是很大，那麼像md5這樣的加密哈希就足夠了。

#6樓

選擇100個随機點可能意味着相似（或有時甚至不相似）的圖像将被标記為相同圖像，我認為這不是您想要的圖像。 如果圖像的格式不同（png，jpeg等），尺寸不同或中繼資料不同，則MD5哈希将不起作用。 将所有圖像縮小到較小的大小是一個不錯的選擇，隻要您使用的是良好的圖像庫/快速語言，并且像素間比較小，那麼進行像素間比較就不會花費太長時間。

您可以嘗試将它們縮小，然後如果它們相同，則在更大的尺寸上進行另一個比較-可能是速度和準确性的完美結合...

#7樓

正如cartman所指出的，您可以使用任何類型的哈希值來查找精确的重複項。

尋找接近圖像的起點可能在這裡 。 CG公司使用此工具來檢查修改後的圖像是否仍顯示基本相同的場景。

#8樓

以下是解決此問題的三種方法（還有許多其他方法）。

• 第一種是計算機視覺，關鍵點比對的标準方法。 這可能需要一些背景知識來實施，并且可能很慢。
• 第二種方法僅使用基本圖像處理，并且可能比第一種方法更快，并且易于實作。 但是，它在可了解性上獲得的東西卻缺乏魯棒性-在縮放，旋轉或變色的圖像上比對失敗。
• 第三種方法既快速又健壯，但可能是最難實作的方法。

關鍵點比對

比選擇100個随機點好得多，而是選擇100個重要點。 圖像的某些部分比其他部分（尤其是在邊緣和角落）具有更多資訊，而這些正是您要用于智能圖像比對的部分。 Google的“ 關鍵點提取 ”和“ 關鍵點比對 ”，您會發現很多關于該主題的學術論文。 如今， SIFT關鍵點可以說是最受歡迎的，因為它們可以比對不同比例，旋轉和光照下的圖像。 一些SIFT實作可以在這裡找到。

關鍵點比對的一個缺點是天真的實作的運作時間：O（n ^ 2m），其中n是每個圖像中關鍵點的數量，m是資料庫中圖像的數量。 一些聰明的算法可能會更快地找到最接近的比對項，例如四叉樹或二進制空間分區。

替代解決方案：直方圖方法

另一個不那麼健壯但可能更快的解決方案是為每個圖像建構特征直方圖，并選擇直方圖最接近輸入圖像直方圖的圖像。 我将其實作為大學，我們使用了3個顔色直方圖（紅色，綠色和藍色）以及兩個紋理直方圖（方向和比例）。 我将在下面提供詳細資訊，但我應該注意，這僅适用于非常比對資料庫圖像的比對圖像。 重新縮放，旋轉或變色的圖像可能無法使用此方法，但像裁切這樣的小變化不會破壞算法

計算顔色直方圖非常簡單-隻需選擇直方圖桶的範圍，然後為每個範圍計算該範圍内顔色的像素數即可。 例如，考慮“綠色”直方圖，并假設我們為直方圖選擇4個存儲分區：0-63、64-127、128-191和192-255。 然後，對于每個像素，我們檢視綠色值，然後将計數添加到适當的存儲桶中。 完成計數後，我們将每個存儲桶總數除以整個圖像中的像素數，以獲得綠色通道的歸一化直方圖。

對于紋理方向直方圖，我們首先對圖像進行邊緣檢測。 每個邊緣點都有一個法線向量，指向垂直于邊緣的方向。 我們将法線向量的角度量化為0和PI之間的6個桶中的一個（由于邊具有180度對稱性，是以将-PI和0之間的角度轉換為0和PI之間的角度）。 計算每個方向上的邊緣點數量後，我們得到了代表紋理方向的未歸一化直方圖，我們通過将每個存儲桶除以圖像中的邊緣點總數來對其進行歸一化。

為了計算紋理比例直方圖，對于每個邊緣點，我們測量了到具有相同方向的下一個最近邊緣點的距離。 例如，如果邊緣點A的方向為45度，則算法沿該方向行走，直到找到具有45度方向（或在合理偏差内）的另一個邊緣點。 在計算完每個邊緣點的距離之後，我們将這些值轉儲到直方圖中，并通過除以邊緣點的總數對其進行歸一化。

現在，每個圖像都有5個直方圖。 要比較兩個圖像，請擷取每個直方圖桶之間的差的絕對值，然後對這些值求和。 例如，要比較圖像A和B，我們将計算

|A.green_histogram.bucket_1 - B.green_histogram.bucket_1| 
           

對于綠色直方圖中的每個存儲桶，對其他直方圖重複上述操作，然後将所有結果相加。 結果越小，比對越好。 對資料庫中的所有圖像重複以上操作，結果最小的比對獲勝。 您可能希望有一個門檻值，在該門檻值之上算法将得出結論，未找到比對項。

第三選擇-關鍵點+決策樹

第三種方法可能比其他兩種方法快得多，這是使用語義文本森林 （PDF）。 這涉及提取簡單的關鍵點，并使用收集決策樹對圖像進行分類。 這比簡單的SIFT關鍵點比對要快，因為它避免了昂貴的比對過程，并且關鍵點比SIFT簡單得多，是以關鍵點提取要快得多。 但是，它保留了SIFT方法對旋轉，縮放和照明的不變性，這是直方圖方法缺少的一個重要功能。

更新 ：

我的錯誤-Semantic Texton Forests論文不是專門針對圖像比對，而是針對區域标注。 進行比對的原始論文是： 使用随機樹進行關鍵點識别 。 此外，以下論文繼續發展這些思想并代表了最新技術水準（約2010年）：

• 使用随機蕨類進行快速關鍵點識别 -比Lepetit 06更快，更可擴充
• 簡介：二進制健壯的獨立基本功能 -健壯性較低但速度非常快-我認為此處的目标是在智能手機和其他手持裝置上進行實時比對

#9樓

我有一個主意，它可以奏效，而且很有可能很快。 您可以以80x60分辨率或類似分辨率對圖像進行二次采樣，然後将其轉換為灰階（二次采樣後速度會更快）。 處理要比較的兩個圖像。 然後運作兩個圖像（查詢圖像以及來自db的每個圖像）之間的平方差的平方和，或者運作更好的歸一化互相關，如果兩個圖像相似，則響應接近1。 然後，如果圖像相似，則可以繼續使用更複雜的技術來驗證它是否為相同圖像。 顯然，就您的資料庫中的圖像數量而言，此算法是線性的，是以即使在現代硬體上，它每秒将非常快地達到10000個圖像。 如果您需要旋轉不變性，則可以為這個小圖像計算一個主梯度，然後可以将整個坐标系旋轉到規範方向，盡管這樣會比較慢。 不，這裡沒有縮放的不變性。

如果您想要更通用的東西或使用大型資料庫（上百萬張圖檔），則需要研究圖檔檢索理論（最近五年出現了大量論文）。 在其他答案中有一些指針。 但這可能是過大的，建議的直方圖方法可以勝任。 盡管我認為将許多不同的快速方法結合起來會更好。