web前端開發之利用JS實現多種圖片相似度算法

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

特徵提取算法

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

平均哈希算法

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

第一步，縮小尺寸為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 
 }) 
} /<imagedata>

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

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

圖片灰度化

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

在計算機領域中，灰度（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 均值的辦法，在這裡我們使用加權的方式去實現。為什麼要這麼做呢？這裡涉及到顏色學的一些概念。

採用 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 
} 

兩種比對算法的適用場景

明白了“漢明距離”和“餘弦相似度”這兩種特徵比對算法以後，我們就要去看看它們分別適用於哪些特徵提取算法的場景。

首先來看“顏色分佈法”。在“顏色分佈法”裡面，我們把一張圖的顏色進行區間劃分，通過統計不同顏色區間的數量來獲取特徵，那麼這裡的特徵值就和“數量”有關，也就是非 0-1 矩陣。

顯然，要比較兩個“顏色分佈法”特徵的相似度，“漢明距離”是不適用的，只能通過“餘弦相似度”來進行計算。

接下來看“平均哈希算法”和“內容特徵法”。從結果來說，這兩種特徵提取算法都能獲得一個 N×N 的 0-1 矩陣，且矩陣內元素的值和“數量”無關，只有 0-1 之分。所以它們同時適用於通過“漢明距離”和“餘弦相似度”來計算相似度。

計算精度

明白瞭如何提取圖片的特徵以及如何進行比對以後，最重要的就是要了解它們對於相似度的計算精度。

本文所講的相似度僅僅是通過客觀的算法來實現，而判斷兩張圖片“像不像”卻是一個很主觀的問題。於是我寫了一個簡單的服務，可以自行把兩張圖按照不同的算法和精度去計算相似度，經過對不同素材的多方比對，我得出了下列幾個非常主觀的結論。

• 對於兩張顏色較為豐富，細節較多的圖片來說，“顏色分佈法”的計算結果是最符合直覺的。

• 對於兩張內容相近但顏色差異較大的圖片來說，“內容特徵法”和“平均/感知哈希算法”都能得到符合直覺的結果。

• 針對“顏色分佈法“，區間的劃分數量對計算結果影響較大，選擇合適的區間很重要。

總結一下，三種特徵提取算法和兩種特徵比對算法各有優劣，在實際應用中應該針對不同的情況靈活選用。

閱讀更多 扣丁學堂 的文章

關鍵字: Google 電腦 前端開發