在查找范畴，早已出现了“查找类似图片/类似产品”的相关功用，如 Google 搜图，百度搜图，淘宝的摄影搜产品等。要完成类似的核算图片类似度的功用，除了运用听起来巨大上的“人工智能”以外，其实通过 JS 和几种简略的算法，也能八九不离十地完成类似的作用。

在阅览本文之前，强烈建议先阅览完阮一峰于多年所编撰的《类似图片查找的原理》相关文章，本文所触及的算法也来源于其间。

体会地址：https://img-compare.netlify.com/

特征提取算法

为了便于了解，每种算法都会通过“特征提取”和“特征比对”两个过程进行。接下来将侧重对每种算法的“特征提取”过程进行具体解读，而“特征比对”则独自进行论述。

均匀哈希算法

参阅阮大的文章，“均匀哈希算法”主要由以下几步组成：

第一步，缩小尺度为8×8，以去除图片的细节，只保存结构、明暗等基本信息，摒弃不同尺度、份额带来的图片差异。

第二步，简化色彩。将缩小后的图片转为灰度图画。

第三步，核算均匀值。核算一切像素的灰度均匀值。

第四步，比较像素的灰度。将64个像素的灰度，与均匀值进行比较。大于或等于均匀值，记为1；小于均匀值，记为0。

第五步，核算哈希值。将上一步的比较成果，组合在一起，就构成了一个64位的整数，这便是这张图片的指纹。

第六步，核算哈希值的差异，得出类似度（汉明间隔或许余弦值）。

理解了“均匀哈希算法”的原理及过程今后，就可以开端编码工作了。为了让代码可读性更高，本文的一切比如我都将运用 typescript 来完成。

图片紧缩：

咱们选用 canvas 的 drawImage() 办法完成图片紧缩，后运用 getImageData() 办法获取 ImageData 方针。

exportfunctioncompressImg(imgSrc:string,imgWidth:number=8):Promise<ImageData>{
returnnewPromise((resolve,reject)=>{
if(!imgSrc){
reject('imgSrccannotbeempty!')
}
constcanvas=document.createElement('canvas')
constctx=canvas.getContext('2d')
constimg=newImage()
img.crossOrigin='Anonymous'
img.onload=function(){
canvas.width=imgWidth
canvas.height=imgWidth
ctx?.drawImage(img,0,0,imgWidth,imgWidth)
constdata=ctx?.getImageData(0,0,imgWidth,imgWidth)asImageData
resolve(data)
}
img.src=imgSrc
})
}

可能有读者会问，为什么运用 canvas 可以完成图片紧缩呢？简略来说，为了把“大图片”制作到“小画布”上，一些相邻且色彩附近的像素往往会被删减掉，然后有用减少了图片的信息量，因而可以完成紧缩的作用：

在上面的 compressImg() 函数中，咱们使用 new Image() 加载图片，然后设定一个预设的图片宽高值让图片紧缩到指定的巨细，最终获取到紧缩后的图片的 ImageData 数据——这也意味着咱们能获取到图片的每一个像素的信息。

关于 ImageData，可以参阅 MDN 的文档介绍。

图片灰度化

为了把五颜六色的图片转化成灰度图，咱们首要要理解“灰度图”的概念。在维基百科里是这么描绘灰度图画的：

在核算机范畴中，灰度（Gray scale）数字图画是每个像素只需一个采样色彩的图画。

大部分情况下，任何的色彩都可以通过三种色彩通道（R, G, B）的亮度以及一个色彩空间（A）来组成，而一个像素只显示一种色彩，因而可以得到“像素 => RGBA”的对应联系。而“每个像素只需一个采样色彩”，则意味着组成这个像素的三原色通道亮度持平，因而只需要算出 RGB 的均匀值即可：

//依据RGBA数组生成ImageData
exportfunctioncreateImgData(dataDetail:number[]){
constcanvas=document.createElement('canvas')
constctx=canvas.getContext('2d')
constimgWidth=Math.sqrt(dataDetail.length/4)
constnewImageData=ctx?.createImageData(imgWidth,imgWidth)asImageData
for(leti=0;i<dataDetail.length;i+=4){
letR=dataDetail[i]
letG=dataDetail[i+1]
letB=dataDetail[i+2]
letAlpha=dataDetail[i+3]
newImageData.data[i]=R
newImageData.data[i+1]=G
newImageData.data[i+2]=B
newImageData.data[i+3]=Alpha
}
returnnewImageData
}
exportfunctioncreateGrayscale(imgData:ImageData){
constnewData:number[]=Array(imgData.data.length)
newData.fill(0)
imgData.data.forEach((_data,index)=>{
if((index+1)%4===0){
constR=imgData.data[index-3]
constG=imgData.data[index-2]
constB=imgData.data[index-1]
constgray=~~((R+G+B)/3)
newData[index-3]=gray
newData[index-2]=gray
newData[index-1]=gray
newData[index]=255//Alpha值固定为255
}
})
returncreateImgData(newData)
}

ImageData.data 是一个 Uint8ClampedArray 数组，可以了解为“RGBA数组”，数组中的每个数字取值为0~255，每4个数字为一组，表明一个像素的 RGBA 值。因为ImageData 为只读方针，所以要别的写一个 creaetImageData() 办法，使用 context.createImageData() 来创立新的 ImageData 方针。

拿到灰度图画今后，就可以进行指纹提取的操作了。

指纹提取

在“均匀哈希算法”中，若灰度图的某个像素的灰度值大于均匀值，则视为1，否则为0。把这部分信息组合起来便是图片的指纹。因为咱们现已拿到了灰度图的 ImageData 方针，要提取指纹也就变得很简略了：

exportfunctiongetHashFingerprint(imgData:ImageData){
constgrayList=imgData.data.reduce((pre:number[],cur,index)=>{
if((index+1)%4===0){
pre.push(imgData.data[index-1])
}
returnpre
},[])
constlength=grayList.length
constgrayAverage=grayList.reduce((pre,next)=>(pre+next),0)/length
returngrayList.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 办法：

functionmemoizeCosines(N:number,cosMap:any){
cosMapcosMap=cosMap||{}
cosMap[N]=newArray(N*N)
letPI_N=Math.PI/N
for(letk=0;k<N;k++){
for(letn=0;n<N;n++){
cosMap[N][n+(k*N)]=Math.cos(PI_N*(n+0.5)*k)
}
}
returncosMap
}
functiondct(signal:number[],scale:number=2){
letL=signal.length
letcosMap:any=null
if(!cosMap||!cosMap[L]){
cosMap=memoizeCosines(L,cosMap)
}
letcoefficients=signal.map(function(){return0})
returncoefficients.map(function(_,ix){
returnscale*signal.reduce(function(prev,cur,index){
returnprev+(cur*cosMap[L][index+(ix*L)])
},0)
})
}

然后增加两个矩阵处理办法，分别是把通过 DCT 办法生成的一维数组升维成二维数组（矩阵），以及从矩阵中获取其“左上角”内容。

//一维数组升维
functioncreateMatrix(arr:number[]){
constlength=arr.length
constmatrixWidth=Math.sqrt(length)
constmatrix=[]
for(leti=0;i<matrixWidth;i++){
const_temp=arr.slice(i*matrixWidth,i*matrixWidth+matrixWidth)
matrix.push(_temp)
}
returnmatrix
}
//从矩阵中获取其“左上角”巨细为range×range的内容
functiongetMatrixRange(matrix:number[][],range:number=1){
constrangeMatrix=[]
for(leti=0;i<range;i++){
for(letj=0;j<range;j++){
rangeMatrix.push(matrix[i][j])
}
}
returnrangeMatrix
}

复用之前在“均匀哈希算法”中所写的灰度图转化函数createGrayscale()，咱们可以获取“感知哈希算法”的特征值：

exportfunctiongetPHashFingerprint(imgData:ImageData){
constdctdctData=dct(imgData.dataasany)
constdctMatrix=createMatrix(dctData)
constrangeMatrix=getMatrixRange(dctMatrix,dctMatrix.length/8)
constrangeAve=rangeMatrix.reduce((pre,cur)=>pre+cur,0)/rangeMatrix.length
returnrangeMatrix.map(val=>(val>=rangeAve?1:0)).join('')
}

色彩散布法

首要摘录一段阮大关于“色彩散布法“的描绘：

阮大把256种色彩取值简化成了4种。依据这个原理，咱们在进行色彩散布法的算法设计时，可以把这个区间的区分设置为可修正的，仅有的要求便是区间的数量有必要可以被256整除。算法如下：

//区分色彩区间，默许区间数目为4个
//把256种色彩取值简化为4种
exportfunctionsimplifyColorData(imgData:ImageData,zoneAmount:number=4){
constcolorZoneDataList:number[]=[]
constzoneStep=256/zoneAmount
constzoneBorder=[0]//区间鸿沟
for(leti=1;i<=zoneAmount;i++){
zoneBorder.push(zoneStep*i-1)
}
imgData.data.forEach((data,index)=>{
if((index+1)%4!==0){
for(leti=0;i<zoneBorder.length;i++){