利用前端技术生成图片相似度hash-逐梦个人博客

前端时间做了这么一个需求，设计师通过photoshop软件设计主题模板，然后我们通过程序解析psd文件中的图层信息，比如装饰图，文本框，图片框，背景图等之类的元素（这里可能会涉及一些图层标记），关于如何解析psd文件可以参考文章：/js-parse-psd.html，你也可以在/psd-js-common-cases.html这篇文章中找到一些常见的psd.js使用过程中的坑的解决办法。

回到正题，对于图片框和文本框由于后期的内容是用户自定义的，所以我们只需要生成相应的元素用于承载这些元素就可以了，但是对于背景和贴纸却是需要我们真正的上传到我们的系统，后期直接使用的，一般做法，我们肯定会直接将解析出来的背景和贴纸图片直接上传就好，但是同一类型的主题可能会多次使用同一张背景货贴纸，如果我们不做任何处理，后期系统中会有很多重复的其实画面完全一样的背景和贴纸，这里我们需要做去重操作，去重就需要计算图片的相似度，可能很多人会说这是后端的活，和前端没毛关系呀，其实不然，我们分析一下后端直接做去重会有什么样的问题。

1、每次上传一张贴纸和素材，都需要去库里和现有的素材进行两两比对，这个计算量非常大，对于整个上传的影响是灾难性的，体验巨差。

2、上传和去重的逻辑偶合在一起，对于后端来说也并不太合理

3、由于去重这个计算量非常大，所以对于服务器的负载又有不小的影响。

最终我们选择在前端生成相似度hash（其实应该是特征值），不选择直接去重是因为每次导入都是独立的，我们没有上下人，没办法和现有库里的素材做对比。那么如何生成图片的特征值呢？

去度娘搜索一下图片相似度算法，提的最多的也比较简单的就是感知hash算法，其原理就是将图片缩小，一般是8X8，然后根据得到的64个像素的灰度平均值得到指纹，这种方法比较简单，在大部分情况下运行效果还是不错的，但是出现误判的几率很大，类png图片出现大量透明区域，这个算法出现误判的几率更大，而且大图缩小到极小会丢失非常非常多的细节，后来我们参考了这个算法的基本原理实现了另外一个算法，怎么做呢？

寿险我们也需要将图片缩小，但是并不是缩小到8X8，会更大一点，比如500X500，而且我们会保持图片的宽高比，这样细节会保留的更多，但是如果我们直接用500X500的图片生成指纹，那么直接的长度会达到250000+（当然也可能小于这个数），这肯定是不行的，最终我们选择将图片分区，比如分成5X5个区，

将每个分区内像素进行采样，将灰度平均值作为一个特征点，最终我们可以近似得到一个25（有可能大于或者小于25位）位数字组成的特征数组。特征数组提取方法：

getImageHash(img, { width = 100, height = 100, pieces = 5 } = {}) {
    // 缩小图片
    const imgData = getResizedImgData(img, width, height);
    const { width: imgWidth, height: imgHeight } = imgData;
    const grayStyles = [];
    const stepX = Math.floor(imgWidth / pieces );
    const stepY = Math.floor(imgHeight / pieces );

    const features = [];
    for (let y = 0; y < imgHeight; y += stepY) {
        for (let x = 0; x < imgWidth; x += stepX) {
            const grayStyles = [];
            for (let j = 0; j < stepY; j++) {
                const yy = y + j;
                for (let i = 0; i < stepX; i++) {
                    const xx = x + i;
                    const index = (yy * imgWidth + xx) * 4;
                    grayStyles.push(this.getGrayStyle(imgData, index));
                }
            }
            const average = Math.round(grayStyles.reduce((a, b) => {
                return a + b;
            }, 0) / grayStyles.length);
            features.push(average);
        }
    }

    return features;
}

其中使用到的getResizedImgData方法定义：

getResizedImgData(img, width = 8, height = 8) {
    let imgWidth = img.width, imgHeight = img.height;
    const ratio = imgWidth / imgHeight;
    if (imgWidth > imgHeight) {
        imgWidth = width;
        imgHeight = Math.floor(imgWidth / ratio);
    } else {
        imgHeight = height;
        imgWidth = Math.floor(imgHeight * ratio);
    }
    const canvas = document.createElement('canvas');
	   canvas.width = imgWidth;
	   canvas.height = imgHeight;
    const ctx = canvas.getContext('2d');
    ctx.drawImage(img, 0, 0, img.width, img.height, 0, 0, imgWidth, imgHeight);
    return ctx.getImageData(0, 0, imgWidth, imgHeight);
}

根据上面的方法我们可以得到图片的特征数组，利用汉明距离或者余弦相似度就可以对比图片的相似度。

虽然通过上面的步骤我们得到了图片的特征数组，而且也可以通过一些算法对比图片的额相似度，但是离我们说的hash还是有一定的距离，那么如何得到一致性hash呢？

其实我们仔细思考一下灰度值的取值方位是0 <= gray <= 255，总共256位数字，我们只需要将256等分成若干个小范围每一个小范围内的数字对应一个hash字符是不是就可以了呢？而每个小范围内数值的格式刚好在一定程度上用于控制精准度的容差，开绿道特殊字符的个数，设容差最小值为4，也是就每个小范围最小4位数字，当然也可以根据情况做调整，这里贴出一个简单的实现：

function getIdentifier(graystyle, devitation = 4) {
    const devi = devitation <= 4 ? 4 : devitation;
    const indentifiers = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ%=';
    return indentifiers[Math.floor(graystyle / devitation)];
}

文末的一些思考：

一、通过上面所述，我们可以提取出图片的特征数组，并可以进一步生成图片相似度hash，我们可以通过调整缩小图片的大小，分区的个数来调整特征数组和hash的准度。

二、有些朋友可能会说在数据量比较大的时候，这个对比的计算量还是很大，这里我们可以通过优化对比算法来优化对比的速度，我们可以从以下几方面来优化（这里主要针对直接使用特征数组的情况）：

1、对比特征数组的长度，如果不相等，那么图片不相似，直接返回。

2、引入突变的概念，什么意思呢？比如以下两组特征数组

const a = [300, 200, 100];
const b = [310, 202, 102];

正常对比，我们会依次对比数组每一个对应的位置，比如200和202做对比，100和102做对比，300和310做对比，正常情况下，如果两个值小于一定的误差比如2，我们就认为是相似的，但是这样计算的话我们需要将数组遍历完才能知道是不是相似的，如果引入突变，假如我们设定突变的临界值为5，如果某族特征值大于5，那么我们直接判定为不相似，直接返回，比如上面的情况，a和b的第一组数字间隔为10大于图标临界值5，数组后面的内容我们就不需要再对比了，直接返回。

三、这种算法虽然较感知hash算法会更优一些，但是依然会出现一些误差，比如下面2组图片，

主题内容完全一致，区别在于边角的留白，而目前的算法对于这个留白是敏感的，因为计算的是平均灰度值，可能边角会直接产生一个突变，判定2个图片不相似，这显然是不符合预期的，当然这个问题归根到底是设计的问题，可以从设计师那边做规范，但是是人总会出错，我们还是需要考虑用程序去弥补这种问题，其实思路也很简单，在图片缩小之前先将图片的主题区域提取出来，然后再做继续上面的流程就可以了，这里实现一个简单的图形主题切割，基于透明度的：

function getSolidImage(img) {
    const oCanvas = new OffscreenCanvas(img.width, img.height);
    const oCtx = oCanvas.getContext('2d');
    const imageData = oCtx.getImageData(0, 0, img.width, img.height);
    const { width, height } = imageData;
    const left = getSolidLeft(imageData);
    const top = getSolidTop(imageData);
    const right = getSolidRight(imageData);
    const bottom = getSolidBottom(imageData);
    const [solidX, solidY, solidWidth, solidHeight ] = [left, top, width - left - right, height - top - bottom];
    let canvas = document.createElement('canvas');
    canvas.width = solidWidth;
    canvas.height = solidHeight;
    const ctx = canvas.getContext('2d');
    ctx.drawImage(mycanvas, solidX, solidY, solidWidth, solidHeight, 0, 0, solidWidth, solidHeight);
    return canvas;
}

function getSolidTop(imageData) {
    const { width, height, data } = imageData;
    for (let j=0; j<height; j++) {
        for (let i=0; i<width; i++) {
            const index = i * 4 + j * width * 4;
            if (data[index+3] > 120) {
                return j;
            }
        }
    }
}

function getSolidRight(imageData) {
    const { width, height, data } = imageData;
    for (let i=width-1; i>=0; i--) {
        for (let j=0; j<height-1; j++) {
            const index = j * width * 4 + i * 4;
            if (data[index+3] > 120) {
                return width-i;
            }
        }
    }
}

function getSolidBottom(imageData) {
    const { width, height, data } = imageData;
    for (let j=height-1; j>=0; j--) {
        for (let i=0; i<width; i++) {
            const index = j * width * 4 + i * 4;
            if (data[index+3] > 120) {
                return height-j;
            }
        }
    }
}

function getSolidLeft(imageData) {
    const { width, height, data } = imageData;
    for (let i=0; i<width; i++) {
        for (let j=0; j<height; j++) {
            const index = j * width * 4 + i * 4;
            if (data[index+3] > 120) {
                return i;
            }
        }
    }
}

好了，本文到这里就结束了，写了这么多肯定有考虑的不是很完善的地方，如果有问题请随时和我联系。

文末附上本文涉及的源码及demo，有需要的朋友请自行下载。

猛戳这里下载本文案例源码包