基于低频的pHash算法 和 汉明距离 实现图像相似度对比算法

背景

在实现基于图像识别技术的桌面端元素捕获功能后，用户录制时捕获好了某张图像上的某个元素，在机器人回放时，需要重新进行图像识别，构建索引结构信息，然后对目标图像和识别后的各图像主体进行相似度比对，选择相似度最高的主体图像，然后基于该图像搜索索引结构，获取该图像的信息，最后，基于pyautogui进行模拟操作。

上述逻辑流程中核心点是图像相似度算法的选择和实现，在搜索了资料后，得出几种特征提取的算法,分别是基于低频的aHash/pHash/dHash, HOG, 三直方图和单通道直方图等。因此在学习这些算法后，选择了aHash作为特征提取算法，使用汉明距离计算相似度，并记录下自己学习的心得。

图像的高频和低频

低频：图像信号中的低频分量，指的是图像灰度变换平缓的地方，代表着连续渐变的一块区域，对应的是图像边缘以内的内容，即能够表示图像的大部分信息。

高频：与低频相反，高频即频率变化块的区域，就是相邻区域之间的灰度相差很大。在图像主体和图像背景的边缘部分，通常会有明显的差别，也就是说在变化的边缘处，灰度变化很大，频率高。同样，能被人眼一眼识别出来的图像细节处也是属于高频区域，正是因为灰度的急剧变化，才会出现细节。

在了解了低频和高频的概念后，接下来进入pHash算法。

注：在图像处理过程中，通常我们会对图像进行噪点处理，噪点是指该点的像素值和正常点明显不一样，即灰度值不一样，相邻区域灰度值发生明显的变化，因而噪点也位于高频区域。

pHash算法

pHash算法的思路是对每个图片生成一个指纹字符串，pHash算法是改进版的aHash算法，aHash算法有两兄弟，pHash, dHash， 它们三个都是基于低频的算法。在前面介绍的低频的概念中，我们可以知道，低频能够表示图像的大部分信息，而高频表示的是图像中的轮廓和边缘部分。所以理论上来说，频度越低，计算出来的相似度越准确。

先来看下aHash算法的步骤，再看pHash算法的改进：

• 将图片缩小到8 * 8，总共64个像素，这个步骤的作用是去除图片部分详细信息，去除图像的结构、明暗等细节信息，摒弃图像尺寸、缩放比例带来的差异。

• 将缩放后的图像转为灰度图，这个步骤的作用是减少图像色差所带来的的影响，同时方便转二值化图，进行汉明距离的计算。

• 计算灰度图中各点像素的均值，便于计算二值化。

• 二值化操作，扁平化二维数组, 遍历各点像素值，大于均值的设为1，小于均值的设为0, 这样就得到一个大小为64的一位数组。方便进行异或运算。

• 最后采用异或的方法计算汉明距离，汉明距离越小说明两个图像越相似。

pHash算法采用了DCT(离散余弦变换)进一步降低图像的频率, 步骤如下:

• 将图片缩小到 32 * 32大小, 便于生成DCT矩阵。

• 将缩放后的图像转为灰度图，步骤作用同aHash。

• 计算DCT，并选取坐上叫8 * 8的矩阵。DCT是一种特殊的傅里叶变换，将图片从像素域变换为频率域，并且DCT矩阵满足从左上角到右下角频率从小到大的系数变换，因此只需取左上角8 * 8的区域。

• 计算8 * 8区域中各点像素的均值。

• 二值化操作，扁平化二维数组, 遍历各点像素值，大于均值的设为1，小于均值的设为0, 这样就得到一个大小为64的一位数组。方便进行异或运算

• 最后采用异或的方法计算汉明距离，汉明距离越小说明两个图像越相似。

未完待续~