图像相似度比较哈希算法
相似图像搜索的哈希算法有三种:
1.均值哈希算法
2.差值哈希算法
3.感知哈希算法
什么是哈希(Hash)
• 散列函数(或散列算法,又称哈希函数,英语: Hash Function )是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定下来。该函数将数据打乱混合,重新创建一个叫做散列值( hash values hash codes hash sums或 hashes )的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。
• 通过哈希算法得到的任意长度的二进制值映射为较短的固定长度的二进制值,即哈希值。此外,哈希值是一段数据唯一且极其紧凑的数值表示形式,如果通过哈希一段明文得到哈希值,哪怕只更改该段明文中的任意一个字母,随后得到的哈希值都将不同 。
• 哈希算法是一个函数,能够把几乎所有的数字文件都转换成一串由数字和字母构成的看似乱码的字符串。
哈希函数作为一种加密函数,其拥有两个最重要特点:
1.不可逆性。输入信息得出输出的那个看似乱码的字符串(哈希值)非常容易,但是从输出的字符
串反推出输入的结果却是却非常非常难。
2.输出值唯一性和不可预测性。只要输入的信息有一点点区别,那么根据哈希算法得出来的输出值
也相差甚远。
哈希算法是一类算法的总称,共有三种:
1.均值哈希算法 aHash
2.差值哈希算法 dHash
3.感知哈希算法 pHash
汉明距离
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
均值哈希算法
步骤
1.缩放:图片缩放为 8*8 ,保留结构,除去细节。
2.灰度化:转换为灰度图。
3.求平均值:计算灰度图所有像素的平均值。
4.比较:像素值大于平均值记作 1 ,相反记作 0 ,总共 64 位。
5.生成 hash :将上述步骤生成的 1 和 0 按顺序组合起来既是图片的指纹( hash )。
6.对比指纹:将两幅图的指纹对比,计算汉明距离,即两个 64 位的 hash 值有多少位是不一样的,不相同位数越少,图片越相似。
差值哈希算法
差值哈希算法相较于均值哈希算法,前期和后期基本相同,只有中间比较
hash 有变化。
步骤
1.缩放:图片缩放为 8* 9 ,保留结构,除去细节。
2.灰度化:转换为灰度图。
3.求平均值:计算灰度图所有像素的平均值。 这步没有,只是为了与均值哈希做对比
4.比较:像素值大于后一个像素值记作 1 ,相反记作 0 。本行不与下一行对比,每行 9 个像素,
八个差值,有 8 行,总共 64 位
5.生成 hash :将上述步骤生成的 1 和 0 按顺序组合起来既是图片的指纹( hash )。
6.对比指纹:将两幅图的指纹对比,计算汉明距离,即两个 64 位的 hash 值有多少位是不一样
的,不相同位数越少,图片越相似。
感知哈希算法
均值哈希算法过于严格,不够精确,更适合搜索缩略图,为了获得更精确的结果可以选择感知哈希
算法,它采用的是 DCT (离散余弦变换)来降低频率的方法。
步骤:
1.缩小图片: 32 * 32 是一个较好的大小,这样方便 DCT 计算
2.转化为灰度图:把缩放后的图片转化为灰度图。
3.计算 DCT:DCT 把图片分离成分率的集合
4.缩小 DCT DCT 计算后的矩阵是 32 * 32 ,保留左上角的 8 * 8 ,这些代表图片的最低频率。
5.计算平均值:计算缩小 DCT 后的所有像素点的平均值。
6.进一步减小 DCT :大于平均值记录为 1 ,反之记录为 0.
7.得到信息指纹:组合 64 个信息位,顺序随意保持一致性。
8.最后比对两张图片的指纹,获得汉明距离即可。