您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 程式開發 >> iOS 開發基礎

自己動手做一個 Mac 相似圖片搜尋工具

編輯:iOS 開發基礎

這篇文章記錄我用一天半時間寫出的一個 macOS 小工具的完整思路。它做的事情很單純:給定一個「原始目錄」和一個「目標目錄」,把目標目錄裡跟原始圖片視覺上最接近的那幾張挑出來。

做這個東西的直接原因很瑣碎。公司 iOS 專案的圖片資源管理一直比較混亂,命名不統一,還存在內容重複但檔名完全不同的情況。更麻煩的是視覺同事交付了一批 3x 解析度的切圖,需要跟專案裡已有的低解析度版本一一對應。靠人工比對當然準,但這種幾乎沒有技術含量的體力活實在太耗時間。

專案地址:https://github.com/yulingtianxia/SimilarImageHunter

最新版本下載:https://github.com/yulingtianxia/SimilarImageHunter/releases

工具的使用方式:選好原始路徑和目標路徑,點擊「HUNT」開始比對。結果以樹形列表呈現,父節點是原始路徑中的圖片,子節點是目標路徑中匹配度最高的結果;若有多張圖並列最高分,會全部列出。第二列是相似度數值,雙擊任一條路徑即可直接開圖。首次執行需要建立圖片資訊,耗時較長,中途可以點「CANCEL」放棄當前任務,「CLEAR」則清空當前結果。

一、把圖片路徑拿出來

我對 shell 略懂皮毛,所以第一反應就是一行 find 搞定:

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

然後用 NSTask 把腳本跑起來,這部分沒什麼可講的。

二、相似度演算法

長寬比

這裡的場景很明確:找出內容相同、解析度不同的圖片,不需要考慮一張圖包含另一張圖這類複雜情形。因此長寬比是個性價比極高的判斷依據。我給它設定的權重是總相似度的 30%,這個比例後續大概還會再調。

像素的 RGBA 分佈

把不同格式的圖片先解成位圖,就能拿到最原始的像素資料。我選用 RGBA 色彩空間,每個像素用 32 bit 大端模式存放。接著統計每種顏色出現的像素數量,算出它佔全圖的比例,再比較兩張圖在「同色像素佔比」上的差異。

像素的位置

只看顏色分佈是不夠的。有些圖長寬比接近、整體色調也差不多,但相同顏色的像素排列方式完全不同。所以必須把位置納入考量,而且同樣用比例而非絕對座標來表示。把位置資訊併進顏色比較之後,判斷的準確度有明顯提升。

構造指紋向量

實測下來,直接用原始的「RGBA + 像素位置」並不理想,統計結果太分散。更麻煩的是,我發現把一張圖縮放之後,它的色彩空間會劇烈膨脹——原圖可能只有 100 種 RGBA 值,處理後卻變成 1000 種。肉眼看上去兩張圖一模一樣,但後者其實有大量「相近但不等」的顏色把同一色塊打散了,於是比對同色佔比時相似度被大幅拉低。

解法是把相近顏色歸併。RGBA 四個通道各 8 bit,我把每個通道按 8 等分劃成 8 個區間,組合數就從 2^32 降到 8^4:

#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;
}

位置資訊同樣要簡化,我用的是九宮格:把圖片按比例切成 3×3,格子從 1 編號到 9。這樣每個像素的位置就壓縮成兩個數字,組合數只有 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 *key, NSNumber *obj, BOOL *stop) {
    pixelBucket[key] = @(obj.doubleValue/(height * width));
}];

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

計算向量相似度

我用的是餘弦相似度,結果介於 0 到 1 之間,越接近 1 表示內容越像:

__block double similarityOfPixelVector = 0;
__block double targetRank = 0;
__block double sourceRank = 0;

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

[targetPixelVector enumerateKeysAndObjectsUsingBlock:^(NSNumber *key, NSNumber *obj, BOOL *stop) {
    targetRank += obj.doubleValue * obj.doubleValue;
}];
targetRank = sqrt(targetRank);

similarityOfPixelVector = similarityOfPixelVector/(sourceRank*targetRank);

選餘弦相似度是因為它的值域剛好落在 0~1,而且方向越一致結果越趨近 1,正好符合需求;歐氏距離和 Jaccard 相似度都不太合用。

餘弦相似度有個眾所皆知的缺陷:它只看方向、不看長度。兩個向量夾角固定時,即使長度變化導致末端歐氏距離改變,餘弦值依然不變。但在這個場景裡,這反而正好——指紋向量所有維度的值加總恆為 1,方向一旦確定,長度也就跟著確定了。把問題降到三維空間就很直觀:所有向量的起點都在原點,終點都落在同一個綠色平面上。

最終的相似度由長寬比與指紋向量兩部分加權而成:

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

這裡 similarityOfAspectRatio 有可能是負數,這不是 bug 而是刻意的:我要匹配的是視覺給出的不同解析度素材,長寬比要是差太多,那肯定不是我要的東西。至於為什麼不直接判斷、不合格就 skip,有兩個原因:

  1. 視覺切圖的尺寸並不總是精準,小圖尤其明顯,我甚至見過本該是正方形的圖長寬不相等。所以這裡需要一點容錯,用「相似度」而不是「是否相等」來描述。
  2. 要給出一個完整可解釋的分數,光靠長寬比是湊不出資料的。這一點其實和效率取向相違背,但最後能拿出一個量化結果,值。

三、UI 部分

我對 Cocoa 不熟,踩坑不少,主要都花在 NSOutlineView 上——為了把結果做成樹形列表,先後研究了它的資料來源機制,以及「表格只顯示 Table View Cell」這類典型的 placeholder 問題。

雙擊路徑直接開圖,用 NSWorkspace 就能實現。另外一個關鍵優化是把上次算好的指紋向量做記憶體快取,二次比對時 UI 更新速度差別非常明顯。

毛玻璃效果、後台非同步任務、Autolayout 這些屬於常識範圍,就不展開了,細節直接看原始碼:SimilarImageHunter。

至於後續想加的一鍵替換檔名功能,雖然是剛需,但得先想清楚一套安全可靠的替換策略才敢放出去。

寫完這天,我看太陽都是綠的。

  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved