高效計算兩張黑白圖片相似度：基於餘弦定理與位運算優化

問題背景

給定兩張 32×33 像素的黑白圖片（僅含黑、白兩種顏色），如何快速計算它們的相似度？這在驗證碼識別、圖像去重等場景中非常常見。

理論基礎：向量夾角餘弦

根據《數學之美》系列文章介紹，將每張圖片展平為 1024 維向量（32×32=1024），兩向量夾角的餘弦值即為相似度指標。餘弦值越接近 1，代表兩圖片越相似；經驗值超過 0.8 即可判定為同一圖片。

存儲優化：位壓縮

因像素只有 0（白）和 1（黑）兩種值，可用 1 bit 表示。將每行 32 像素打包進一個 32 位整數，整張圖片僅需 32 個整數存儲，極大節省空間並降低運算複雜度。

核心算法：位運算加速餘弦計算

標準餘弦公式需逐位相乘、平方求和，效率極低。利用二進制特性可大幅優化：

• 分子：對應位相乘 → 位與運算（&）
• 分母：平方求和 → 直接位相加（因 0²=0, 1²=1）

具體步驟：

1. 將圖片按行存入 int[32] 數組
2. 計算分子：兩數組對應元素按位與，結果按位累加
3. 計算分母：各數組所有元素按位累加，分別開根號後相乘
4. 分子除以分母得餘弦值

關鍵代碼實現

public double GetCosine(int[] e1, int[] e2)
{
    int a = 0, b = 0, c = 0;
    for (int y = 0; y < 32; ++y)
    {
        int i = e2[y] & e1[y];  // 位與運算
        for (int x = 1; x < 33; ++x)
        {
            c += (i >> x) & 1;      // 分子累加
            a += (e2[y] >> x) & 1;  // 分母1累加
            b += (e1[y] >> x) & 1;  // 分母2累加
        }
    }
    int d = a * b;
    return d == 0 ? 0 : c / Math.Sqrt(d);
}

實戰應用

若已知一張驗證碼圖片的值，通過相似度比對即可破解外觀相似的驗證碼。此算法時間複雜度 O(32×32)，配合位運算極快，適合實時場景。