這周花了一天半的時間做了個 Mac OS X 上的小工具，用來查找相似內容的圖片。起因是公司的 iOS 項目中已有的圖片管理混亂，有些圖片文件名不規范，還有一些內容重復但文件名不同的圖片。現在視覺要給出一些 3x 分辨率的圖片，如何與已有的低分辨率圖片匹配，這又是個問題。人工一個個去找固然好，但這種技術含量低的體力活很浪費精力和時間。

Github 地址：https://github.com/yulingtianxia/SimilarImageHunter

最新 Release 下載：https://github.com/yulingtianxia/SimilarImageHunter/releases

我開發的這款工具可以在目標路徑中找出與原始路徑中圖片最為相似的圖片。如果目標路徑中有多張圖片相似度相同且最大，這些圖片都會被列出來。樹形列表第一列的父節點內容為原始路徑中的圖片，子節點為目標路徑中匹配到的最佳相似內容圖片。列表第二列為相似度。雙擊圖片路徑即可打開該圖片。點擊 “HUNT” 按鈕開始尋找相似圖片，第一次使用時處理圖片信息耗時較長，可在中途點擊 “CANCEL” 按鈕取消當前任務。“CLEAR” 按鈕則可清除當前界面信息。

獲取圖片路徑

因為會一點 shell，所以第一反應是一行腳本：

find $1 -name '*.jpg' -or -name '*.png'

接下來用 NSTask 跑腳本太 esay 就不細說了。

算法實現

AspectRatio

因為不用考慮一張圖片包含另一張圖片等復雜情況，此處的場景是尋找內容相同分辨率不同的圖片，所以比較圖片的寬高比自然是一個重要的環節。在相似度的計算上，我設定寬高比的相似度權重占到總體相似度的30%。（這個阈值以後可能還會調整）

像素 RGBA 信息

把不同格式的圖片解壓成位圖，就可以得到所有像素最原始的信息。我這裡使用的色彩空間是 RGBA，每個像素用 32 bit 大端模式存儲。然後統計每種顏色(RGBA)的像素數量，並計算其占像素總數的比例。比較兩張圖片相同顏色像素比例的差異就行了。

像素位置信息

光有顏色信息還是不夠的，因為有一些圖片可能寬高比相似，大體的色彩也差不多，但是相同顏色的像素排列卻不一樣。所以也需要考慮到每個像素所處圖片中的位置。這個位置信息也是采用比例的方式來計算，而不是像素到原點的絕對距離。把像素位置信息加入到比較顏色相似度的過程中，大大提升了准確度。

構造指紋向量

在實際統計中會發現使用原始的 “RGBA+像素位置” 信息並不理想，因為這會使得統計結果更加分散。更致命的是在實驗中我嘗試調整了一張圖片的尺寸後，其色彩空間也發生了很大變化。比如原圖只有 100 種 RGBA 值，而處理後的圖片則有 1000 種 RGBA 值！雖然肉眼上看起來兩張圖片內容一樣，但實際上後者卻有很多顏色相似的像素被分散開了，而在比較相同顏色的像素比例時，因為後者的像素數量被稀釋成了多種相似的顏色，使得計算後的相似度大幅降低。

所以需要將相似顏色的像素歸為一類，RGBA 四個通道共 32 bit，每個通道占 8 bit，數值范圍是 0~127，我將其劃分為 8 個區間，這樣總共只有 8^4 個組合（要知道這在簡化之前可是 2^32 個組合！）：

#define Mask8(x) ( (x) & 0xFF )
#define R(x) ( Mask8(x) )
#define G(x) ( Mask8(x >> 8 ) )
#define B(x) ( Mask8(x >> 16) )
#define A(x) ( Mask8(x >> 24) )

-(UInt32)fingerprintOfColor:(UInt32)color
{
    return [self areaOfComponent:R(color)]*1000+[self areaOfComponent:G(color)]*100+[self areaOfComponent:B(color)]*10+[self areaOfComponent:A(color)];
}

-(UInt32)areaOfComponent:(UInt32)component
{
    return component/8;
}

像素的位置信息也同樣需要簡化，我采用 9 宮格的方案：即將圖片按比例劃分成九宮格，並將每個方格從 1 到 9標記。這樣就直接把像素的位置比例簡化為兩個數字（x 和 y），只有 9^2 個組合：

-(UInt32)areaOfX:(NSUInteger)x y:(NSUInteger)y width:(NSUInteger)width height:(NSUInteger)height
{
    UInt32 result = 0;
    if (x<=width/3) {
        result+=0;
    }
    else if (x<=2*width/3) {
        result+=3;
    }
    else {
        result+=6;
    }
    
    
    if (y<=height/3) {
        result+=1;
    }
    else if (y<=2*height/3) {
        result+=2;
    }
    else {
        result+=3;
    }
    
    return result;
}

最後將兩者相結合，構造一個多維向量，pixels 為指向圖片像素數組 RGBA 信息的 UInt32 類型指針：

NSMutableDictionary *pixelBucket = [NSMutableDictionary dictionary];
UInt32 * currentPixel = pixels;
for (NSUInteger j = 0; j < height; j++) {
   for (NSUInteger i = 0; i < width; i++) {
       UInt32 color = *currentPixel;
       UInt32 fingerprint = [self fingerprintOfColor:color]*10+[self areaOfX:i y:j width:width height:height];
       
       pixelBucket[@(fingerprint)] = @(pixelBucket[@(fingerprint)].intValue+1);
       currentPixel++;
   }
}
    
free(pixels);
    
[pixelBucket enumerateKeysAndObjectsUsingBlock:^(NSNumber * _Nonnull key, NSNumber * _Nonnull obj, BOOL * _Nonnull stop) {
   pixelBucket[key] = @(obj.doubleValue/(height * width));
}];

pixelBucket 最多有 8^4*9^2 個鍵值對，也就是指紋向量最大的維度。

計算向量相似性

這裡我采用了向量的余弦相似性：計算結果越接近於 1，兩張圖片內容越相似：

__block double similarityOfPixelVector = 0;
__block double targetRank = 0;
__block double sourceRank = 0;
[sourcePixelVector enumerateKeysAndObjectsUsingBlock:^(NSNumber * _Nonnull key, NSNumber * _Nonnull obj, BOOL * _Nonnull stop) {
   NSNumber *targetObj = targetPixelVector[key];
   if (targetObj) {
       similarityOfPixelVector += obj.doubleValue*targetObj.doubleValue;
   }
   sourceRank += obj.doubleValue * obj.doubleValue;
}];
    
sourceRank = sqrt(sourceRank);
    
[targetPixelVector enumerateKeysAndObjectsUsingBlock:^(NSNumber * _Nonnull key, NSNumber * _Nonnull obj, BOOL * _Nonnull stop) {
   targetRank += obj.doubleValue * obj.doubleValue;
}];

targetRank = sqrt(targetRank);
    
similarityOfPixelVector = similarityOfPixelVector/(sourceRank*targetRank);

采用余弦相似性的主要原因是我它的結果范圍是 0~1，而且向量越相似結果越接近於 1，剛好滿足我的計算要求。而歐氏距離和傑卡德相似性度量都不太滿足我的計算方法上的要求。余弦相似性有個缺點就是只能比較向量的角度，而不能比較距離。也就是說，兩個向量角度固定後，長度若有變化，向量末端的絕對距離（也就是歐氏距離）也會變，但余弦相似性不變。但這在本例中恰巧克服了這個缺點。因為圖片指紋向量所有維度的值之和為 1，也就是說向量的方向固定後，長度也就固定了。如果你還不懂，看下面這張圖。將問題簡化到三維空間，所有三維向量起點都是原點，終點都在綠色平面上：

最後的圖片相似性結合了長寬比相似性與指紋向量相似性：

double similarityOfAspectRatio = 1-fabs(sourceAspectRatio-targetAspectRatio)/sourceAspectRatio;
result = similarityOfAspectRatio*weightOfAspectRatio + similarityOfPixelVector*(1-weightOfAspectRatio);

這裡的 similarityOfAspectRatio 可能為負值，這並不是我一時疏忽，而是有意為之：我的初衷是想匹配視覺提供的不同分辨率的圖片素材，如果連長寬比都差很多，那絕逼不是我要的結果。那為何我不直接加個判斷，如果長寬比不一樣，就直接判斷不符合要求，直接 pass 呢？這裡原因有二：

1. 我曾經發現過視覺切圖的像素尺寸不精確，尤其是小圖。甚至還發現過本應是正方形的圖，長和寬竟然不相同。所以這裡需要容錯，計算長寬比的相似度，即便我想要的結果理論上應該相同，而不是相似。

2. 為了給出兩張圖片的相似度，需要有個全面的分析，光用長寬比得不出數據。這點又與初衷違背，犧牲了效率，只為了最後給出結果裝個逼。

UI 實現

我對 Cocoa 也不熟，自然會踩一些坑的。其中主要是為了展現樹形列表而踩了 NSOutlineView 的坑：

1. NSOutlineView 的數據來源：極簡教程

2. NSTableView only displaying “Table View Cell”

雙擊文件路徑名自動打開圖片，使用 NSWorkspace 即可。

注意用內存緩存上次計算的指紋向量，這樣可以大大減少下次 UI 的更新時間。

毛玻璃效果、後台異步任務、Autolayout 之類的常識這些就不細說了。更多的細節還是看源碼吧：SimilarImageHunter

至於之後的一鍵替換文件名等功能，雖然是剛需，但是還需等安全可靠的替換策略制定出之後才可以祭出。

我現在看太陽都是綠色的。