利用JS實現多種圖片相似度算法

作者：jrainlau 2019-12-11 10:50:06

為了便于理解，每種算法都會經過“特征提取”和“特征比對”兩個步驟進行。接下來將著重對每種算法的“特征提取”步驟進行詳細解讀，而“特征比對”則單獨進行闡述。

在搜索領域，早已出現了“查找相似圖片/相似商品”的相關功能，如 Google 搜圖，百度搜圖，淘寶的拍照搜商品等。要實現類似的計算圖片相似度的功能，除了使用聽起來高大上的“人工智能”以外，其實通過 js 和幾種簡單的算法，也能八九不離十地實現類似的效果。

在閱讀本文之前，強烈建議先閱讀完阮一峰于多年所撰寫的《相似圖片搜索的原理》相關文章，本文所涉及的算法也來源于其中。

體驗地址：https://img-compare.netlify.com/

特征提取算法

平均哈希算法

參考阮大的文章，“平均哈希算法”主要由以下幾步組成：

第一步，縮小尺寸為8×8，以去除圖片的細節，只保留結構、明暗等基本信息，摒棄不同尺寸、比例帶來的圖片差異。

第二步，簡化色彩。將縮小后的圖片轉為灰度圖像。

第三步，計算平均值。計算所有像素的灰度平均值。

第四步，比較像素的灰度。將64個像素的灰度，與平均值進行比較。大于或等于平均值，記為1；小于平均值，記為0。

第五步，計算哈希值。將上一步的比較結果，組合在一起，就構成了一個64位的整數，這就是這張圖片的指紋。

第六步，計算哈希值的差異，得出相似度（漢明距離或者余弦值）。

明白了“平均哈希算法”的原理及步驟以后，就可以開始編碼工作了。為了讓代碼可讀性更高，本文的所有例子我都將使用 typescript 來實現。

圖片壓縮：

我們采用 canvas 的 drawImage() 方法實現圖片壓縮，后使用 getImageData() 方法獲取 ImageData 對象。

export function compressImg (imgSrc: string, imgWidth: number = 8): Promise<ImageData> {  
  return new Promise((resolve, reject) => {  
    if (!imgSrc) {  
      reject('imgSrc can not be empty!')  
    }  
    const canvas = document.createElement('canvas')  
    const ctx = canvas.getContext('2d')  
    const img = new Image()  
    img.crossOrigin = 'Anonymous'  
    img.onload = function () {  
      canvas.width = imgWidth  
      canvas.height = imgWidth  
      ctx?.drawImage(img, 0, 0, imgWidth, imgWidth)  
      const data = ctx?.getImageData(0, 0, imgWidth, imgWidth) as ImageData  
      resolve(data)  
    }  
    img.src = imgSrc  
  })  
}

可能有讀者會問，為什么使用 canvas 可以實現圖片壓縮呢？簡單來說，為了把“大圖片”繪制到“小畫布”上，一些相鄰且顏色相近的像素往往會被刪減掉，從而有效減少了圖片的信息量，因此能夠實現壓縮的效果：

在上面的 compressImg() 函數中，我們利用 new Image() 加載圖片，然后設定一個預設的圖片寬高值讓圖片壓縮到指定的大小，最后獲取到壓縮后的圖片的 ImageData 數據——這也意味著我們能獲取到圖片的每一個像素的信息。

關于 ImageData，可以參考 MDN 的文檔介紹。

圖片灰度化

為了把彩色的圖片轉化成灰度圖，我們首先要明白“灰度圖”的概念。在維基百科里是這么描述灰度圖像的：

在計算機領域中，灰度（Gray scale）數字圖像是每個像素只有一個采樣顏色的圖像。

大部分情況下，任何的顏色都可以通過三種顏色通道（R, G, B）的亮度以及一個色彩空間（A）來組成，而一個像素只顯示一種顏色，因此可以得到“像素 => RGBA”的對應關系。而“每個像素只有一個采樣顏色”，則意味著組成這個像素的三原色通道亮度相等，因此只需要算出 RGB 的平均值即可：

// 根據 RGBA 數組生成 ImageData  
export function createImgData (dataDetail: number[]) {  
  const canvas = document.createElement('canvas')  
  const ctx = canvas.getContext('2d')  
  const imgWidth = Math.sqrt(dataDetail.length / 4)  
  const newImageData = ctx?.createImageData(imgWidth, imgWidth) as ImageData  
  for (let i = 0; i < dataDetail.length; i += 4) {  
    let R = dataDetail[i]  
    let G = dataDetail[i + 1]  
    let B = dataDetail[i + 2]  
    let Alpha = dataDetail[i + 3]  
    newImageData.data[i] = R  
    newImageData.data[i + 1] = G  
    newImageData.data[i + 2] = B  
    newImageData.data[i + 3] = Alpha  
  }  
  return newImageData  
}  
export function createGrayscale (imgData: ImageData) {  
  const newData: number[] = Array(imgData.data.length)  
  newData.fill(0)  
  imgData.data.forEach((_data, index) => {  
    if ((index + 1) % 4 === 0) {  
      const R = imgData.data[index - 3]  
      const G = imgData.data[index - 2]  
      const B = imgData.data[index - 1] 
       const gray = ~~((R + G + B) / 3)  
      newData[index - 3] = gray  
      newData[index - 2] = gray  
      newData[index - 1] = gray 
       newData[index] = 255 // Alpha 值固定為255  
    }  
  })  
  return createImgData(newData)  
}

ImageData.data 是一個 Uint8ClampedArray 數組，可以理解為“RGBA數組”，數組中的每個數字取值為0~255，每4個數字為一組，表示一個像素的 RGBA 值。由于ImageData 為只讀對象，所以要另外寫一個 creaetImageData() 方法，利用 context.createImageData() 來創建新的 ImageData 對象。

拿到灰度圖像以后，就可以進行指紋提取的操作了。

指紋提取

在“平均哈希算法”中，若灰度圖的某個像素的灰度值大于平均值，則視為1，否則為0。把這部分信息組合起來就是圖片的指紋。由于我們已經拿到了灰度圖的 ImageData 對象，要提取指紋也就變得很容易了：

export function getHashFingerprint (imgData: ImageData) {  
  const grayList = imgData.data.reduce((pre: number[], cur, index) => {  
    if ((index + 1) % 4 === 0) {  
      pre.push(imgData.data[index - 1])  
    }  
    return pre  
  }, [])  
  const length = grayList.length  
  const grayAverage = grayList.reduce((pre, next) => (pre + next), 0) / length  
  return grayList.map(gray => (gray >= grayAverage ? 1 : 0)).join('')  
}

通過上述一連串的步驟，我們便可以通過“平均哈希算法”獲取到一張圖片的指紋信息（示例是大小為8×8的灰度圖）：

感知哈希算法

關于“感知哈希算法”的詳細介紹，可以參考這篇文章：《基于感知哈希算法的視覺目標跟蹤》。

簡單來說，該算法經過離散余弦變換以后，把圖像從像素域轉化到了頻率域，而攜帶了有效信息的低頻成分會集中在 DCT 矩陣的左上角，因此我們可以利用這個特性提取圖片的特征。

該算法的步驟如下：

縮小尺寸：pHash以小圖片開始，但圖片大于88，3232是最好的。這樣做的目的是簡化了DCT的計算，而不是減小頻率。
簡化色彩：將圖片轉化成灰度圖像，進一步簡化計算量。
計算DCT：計算圖片的DCT變換，得到32*32的DCT系數矩陣。
縮小DCT：雖然DCT的結果是3232大小的矩陣，但我們只要保留左上角的88的矩陣，這部分呈現了圖片中的最低頻率。
計算平均值：如同均值哈希一樣，計算DCT的均值。
計算hash值：這是最主要的一步，根據8*8的DCT矩陣，設置0或1的64位的hash值，大于等于DCT均值的設為”1”，小于DCT均值的設為“0”。組合在一起，就構成了一個64位的整數，這就是這張圖片的指紋。

回到代碼中，首先添加一個 DCT 方法：

function memoizeCosines (N: number, cosMap: any) {  
  cosMapcosMap = cosMap || {}  
  cosMap[N] = new Array(N * N)  
  let PI_N = Math.PI / N  
  for (let k = 0; k < N; k++) {  
    for (let n = 0; n < N; n++) {  
      cosMap[N][n + (k * N)] = Math.cos(PI_N * (n + 0.5) * k)  
    }  
  }  
  return cosMap  
}  
function dct (signal: number[], scale: number = 2) {  
  let L = signal.length  
  let cosMap: any = null  
  if (!cosMap || !cosMap[L]) {  
    cosMap = memoizeCosines(L, cosMap)  
  }  
  let coefficients = signal.map(function () { return 0 })  
  return coefficients.map(function (_, ix) {  
    return scale * signal.reduce(function (prev, cur, index) {  
      return prev + (cur * cosMap[L][index + (ix * L)])  
    }, 0)  
  })  
}

然后添加兩個矩陣處理方法，分別是把經過 DCT 方法生成的一維數組升維成二維數組（矩陣），以及從矩陣中獲取其“左上角”內容。

// 一維數組升維  
function createMatrix (arr: number[]) {  
  const length = arr.length  
  const matrixWidth = Math.sqrt(length)  
  const matrix = []  
  for (let i = 0; i < matrixWidth; i++) {  
    const _temp = arr.slice(i * matrixWidth, i * matrixWidth + matrixWidth)  
    matrix.push(_temp)  
  }  
  return matrix  
}  
// 從矩陣中獲取其“左上角”大小為 range × range 的內容  
function getMatrixRange (matrix: number[][], range: number = 1) {  
  const rangeMatrix = []  
  for (let i = 0; i < range; i++) {  
    for (let j = 0; j < range; j++) {  
      rangeMatrix.push(matrix[i][j]) 
     }  
  }  
  return rangeMatrix  
}

復用之前在“平均哈希算法”中所寫的灰度圖轉化函數createGrayscale()，我們可以獲取“感知哈希算法”的特征值：

export function getPHashFingerprint (imgData: ImageData) {  
  const dctdctData = dct(imgData.data as any)  
  const dctMatrix = createMatrix(dctData)  
  const rangeMatrix = getMatrixRange(dctMatrix, dctMatrix.length / 8)  
  const rangeAve = rangeMatrix.reduce((pre, cur) => pre + cur, 0) / rangeMatrix.length  
  return rangeMatrix.map(val => (val >= rangeAve ? 1 : 0)).join('')  
}

顏色分布法

首先摘抄一段阮大關于“顏色分布法“的描述：

阮大把256種顏色取值簡化成了4種。基于這個原理，我們在進行顏色分布法的算法設計時，可以把這個區間的劃分設置為可修改的，唯一的要求就是區間的數量必須能夠被256整除。算法如下：

// 劃分顏色區間，默認區間數目為4個  
// 把256種顏色取值簡化為4種  
export function simplifyColorData (imgData: ImageData, zoneAmount: number = 4) {  
  const colorZoneDataList: number[] = []  
  const zoneStep = 256 / zoneAmount  
  const zoneBorder = [0] // 區間邊界 
   for (let i = 1; i <= zoneAmount; i++) {  
    zoneBorder.push(zoneStep * i - 1)  
  }  
  imgData.data.forEach((data, index) => {  
    if ((index + 1) % 4 !== 0) {  
      for (let i = 0; i < zoneBorder.length; i++) {  
        if (data > zoneBorder[i] && data <= zoneBorder[i + 1]) {  
          data = i  
        }  
      }  
    }  
    colorZoneDataList.push(data)  
  })  
  return colorZoneDataList  
}

把顏色取值進行簡化以后，就可以把它們歸類到不同的分組里面去：

export function seperateListToColorZone (simplifiedDataList: number[]) {  
  const zonedList: string[] = []  
  let tempZone: number[] = []  
  simplifiedDataList.forEach((data, index) => {  
    if ((index + 1) % 4 !== 0) {  
      tempZone.push(data)  
    } else { 
       zonedList.push(JSON.stringify(tempZone))  
      tempZone = []  
    }  
  })  
  return zonedList  
}

最后只需要統計每個相同的分組的總數即可：

export function getFingerprint (zonedList: string[], zoneAmount: number = 16) {  
  const colorSeperateMap: {  
    [key: string]: number  
  } = {}  
  for (let i = 0; i < zoneAmount; i++) {  
    for (let j = 0; j < zoneAmount; j++) {  
      for (let k = 0; k < zoneAmount; k++) {  
        colorSeperateMap[JSON.stringify([i, j, k])] = 0  
      }  
    }  
  }  
  zonedList.forEach(zone => {  
    colorSeperateMap[zone]++  
  })  
  return Object.values(colorSeperateMap)  
}

內容特征法

”內容特征法“是指把圖片轉化為灰度圖后再轉化為”二值圖“，然后根據像素的取值（黑或白）形成指紋后進行比對的方法。這種算法的核心是找到一個“閾值”去生成二值圖。

對于生成灰度圖，有別于在“平均哈希算法”中提到的取 RGB 均值的辦法，在這里我們使用加權的方式去實現。為什么要這么做呢？這里涉及到顏色學的一些概念。

具體可以參考這篇《Grayscale to RGB Conversion》，下面簡單梳理一下。

采用 RGB 均值的灰度圖是最簡單的一種辦法，但是它忽略了紅、綠、藍三種顏色的波長以及對整體圖像的影響。以下面圖為示例，如果直接取得 RGB 的均值作為灰度，那么處理后的灰度圖整體來說會偏暗，對后續生成二值圖會產生較大的干擾。

那么怎么改善這種情況呢？答案就是為 RGB 三種顏色添加不同的權重。鑒于紅光有著更長的波長，而綠光波長更短且對視覺的刺激相對更小，所以我們要有意地減小紅光的權重而提升綠光的權重。經過統計，比較好的權重配比是 R:G:B = 0.299:0.587:0.114。

于是我們可以得到灰度處理函數：

enum GrayscaleWeight {  
  R = .299,  
  G = .587,  
  B = .114  
}  
function toGray (imgData: ImageData) {  
  const grayData = []  
  const data = imgData.data  
  for (let i = 0; i < data.length; i += 4) {  
    const gray = ~~(data[i] * GrayscaleWeight.R + data[i + 1] * GrayscaleWeight.G + data[i + 2] * GrayscaleWeight.B)  
    data[i] = data[i + 1] = data[i + 2] = gray  
    grayData.push(gray)  
  }  
  return grayData  
}

上述函數返回一個 grayData 數組，里面每個元素代表一個像素的灰度值（因為 RBG 取值相同，所以只需要一個值即可）。接下來則使用“大津法”（Otsu's method）去計算二值圖的閾值。關于“大津法”，阮大的文章已經說得很詳細，在這里就不展開了。我在這個地方找到了“大津法”的 Java 實現，后來稍作修改，把它改為了 js 版本：

/ OTSU algorithm  
// rewrite from http://www.labbookpages.co.uk/software/imgProc/otsuThreshold.html  
export function OTSUAlgorithm (imgData: ImageData) {  
  const grayData = toGray(imgData)  
  let ptr = 0  
  let histData = Array(256).fill(0)  
  let total = grayData.length  
  while (ptr < total) {  
    let h = 0xFF & grayData[ptr++]  
    histData[h]++  
  }  
  let sum = 0  
  for (let i = 0; i < 256; i++) {  
    sum += i * histData[i]  
  }  
  let wB = 0  
  let wF = 0  
  let sumB = 0  
  let varMax = 0  
  let threshold = 0  
  for (let t = 0; t < 256; t++) {  
    wB += histData[t]  
    if (wB === 0) continue  
    wF = total - wB  
    if (wF === 0) break  
    sumB += t * histData[t]  
    let mB = sumB / wB  
    let mF = (sum - sumB) / wF  
    let varBetween = wB * wF * (mB - mF) ** 2  
    if (varBetween > varMax) {  
      varMax = varBetween  
      tthreshold = t  
    }  
  }  
  return threshold  
}

OTSUAlgorithm() 函數接收一個 ImageData 對象，經過上一步的 toGray() 方法獲取到灰度值列表以后，根據“大津法”算出最佳閾值然后返回。接下來使用這個閾值對原圖進行處理，即可獲取二值圖。

export function binaryzation (imgData: ImageData, threshold: number) {  
  const canvas = document.createElement('canvas')  
  const ctx = canvas.getContext('2d') 
   const imgWidth = Math.sqrt(imgData.data.length / 4)  
  const newImageData = ctx?.createImageData(imgWidth, imgWidth) as ImageData  
  for (let i = 0; i < imgData.data.length; i += 4) {  
    let R = imgData.data[i]  
    let G = imgData.data[i + 1]  
    let B = imgData.data[i + 2]  
    let Alpha = imgData.data[i + 3]  
    let sum = (R + G + B) / 3  
    newImageData.data[i] = sum > threshold ? 255 : 0  
    newImageData.data[i + 1] = sum > threshold ? 255 : 0  
    newImageData.data[i + 2] = sum > threshold ? 255 : 0  
    newImageData.data[i + 3] = Alpha  
  }  
  return newImageData  
}

若圖片大小為 N×N，根據二值圖“非黑即白”的特性，我們便可以得到一個 N×N 的 0-1 矩陣，也就是指紋：

特征比對算法

經過不同的方式取得不同類型的圖片指紋（特征）以后，應該怎么去比對呢？這里將介紹三種比對算法，然后分析這幾種算法都適用于哪些情況。

漢明距離

摘一段維基百科關于“漢明距離”的描述：

在信息論中，兩個等長字符串之間的漢明距離（英語：Hamming distance）是兩個字符串對應位置的不同字符的個數。換句話說，它就是將一個字符串變換成另外一個字符串所需要替換的字符個數。

例如：

1011101與1001001之間的漢明距離是2。
2143896與2233796之間的漢明距離是3。
"toned"與"roses"之間的漢明距離是3。

明白了含義以后，我們可以寫出計算漢明距離的方法：

export function hammingDistance (str1: string, str2: string) {  
  let distance = 0  
  const str1str1Arr = str1.split('')  
  const str2str2Arr = str2.split('')  
  str1Arr.forEach((letter, index) => {  
    if (letter !== str2Arr[index]) {  
      distance++  
    }  
  })  
  return distance  
}

使用這個 hammingDistance() 方法，來驗證下維基百科上的例子：

驗證結果符合預期。

知道了漢明距離，也就可以知道兩個等長字符串之間的相似度了（漢明距離越小，相似度越大）：

相似度 = (字符串長度 - 漢明距離) / 字符串長度

余弦相似度

從維基百科中我們可以了解到關于余弦相似度的定義：

余弦相似性通過測量兩個向量的夾角的余弦值來度量它們之間的相似性。0度角的余弦值是1，而其他任何角度的余弦值都不大于1；并且其最小值是-1。從而兩個向量之間的角度的余弦值確定兩個向量是否大致指向相同的方向。兩個向量有相同的指向時，余弦相似度的值為1；兩個向量夾角為90°時，余弦相似度的值為0；兩個向量指向完全相反的方向時，余弦相似度的值為-1。這結果是與向量的長度無關的，僅僅與向量的指向方向相關。余弦相似度通常用于正空間，因此給出的值為0到1之間。

注意這上下界對任何維度的向量空間中都適用，而且余弦相似性最常用于高維正空間。

余弦相似度可以計算出兩個向量之間的夾角，從而很直觀地表示兩個向量在方向上是否相似，這對于計算兩個 N×N 的 0-1 矩陣的相似度來說非常有用。根據余弦相似度的公式，我們可以把它的 js 實現寫出來：

export function cosineSimilarity (sampleFingerprint: number[], targetFingerprint: number[]) {  
  // cosθ = ∑n, i=1(Ai × Bi) / (√∑n, i=1(Ai)^2) × (√∑n, i=1(Bi)^2) = A · B / |A| × |B|  
  const length = sampleFingerprint.length  
  let innerProduct = 0  
  for (let i = 0; i < length; i++) {  
    innerProduct += sampleFingerprint[i] * targetFingerprint[i]  
  }  
  let vecA = 0  
  let vecB = 0  
  for (let i = 0; i < length; i++) {  
    vecA += sampleFingerprint[i] ** 2  
    vecB += targetFingerprint[i] ** 2  
  }  
  const outerProduct = Math.sqrt(vecA) * Math.sqrt(vecB)  
  return innerProduct / outerProduct  
}