相似性︱python+opencv实现pHash算法+hamming距离(simhash)(三)

pHash跟simhash很多相近的地方。一个是较多用于图像,一个较多用于文本。

之前写关于R语言实现的博客: R语言实现︱局部敏感哈希算法(LSH)解决文本机械相似性的问题(一,基本原理) R语言实现︱局部敏感哈希算法(LSH)解决文本机械相似性的问题(二,textreuse介绍)

机械相似性python版的四部曲: LSH︱python实现局部敏感随机投影森林——LSHForest/sklearn(一) LSH︱python实现局部敏感哈希——LSHash(二) 相似性︱python+opencv实现pHash算法+hamming距离(simhash)(三) LSH︱python实现MinHash-LSH及MinHash LSH Forest——datasketch(四)

一、pHash跟simhash

1、simhash

可参考:Python基础教程-python实现simhash算法实例详细介绍 Simhash的算法简单的来说就是,从海量文本中快速搜索和已知simhash相差小于k位的simhash集合,这里每个文本都可以用一个simhash值来代表,一个simhash有64bit,相似的文本,64bit也相似,论文中k的经验值为3。 该方法的缺点如优点一样明显,主要有两点, 对于短文本,k值很敏感; 另一个是由于算法是以空间换时间,系统内存吃不消。

.

2、感知哈希算法(pHash)

节选自: 图像检索︱图像的相似性搜索与图像向量化、哈希化(文献、方法描述) 平均哈希算法过于严格,不够精确,更适合搜索缩略图,为了获得更精确的结果可以选择感知哈希算法,它采用的是DCT(离散余弦变换)来降低频率的方法

一般步骤:

  • 缩小图片:32 * 32是一个较好的大小,这样方便DCT计算
  • 转化为灰度图:把缩放后的图片转化为256阶的灰度图。(具体算法见平均哈希算法步骤)
  • 计算DCT:DCT把图片分离成分率的集合
  • 缩小DCT:DCT计算后的矩阵是32 * 32,保留左上角的8 * 8,这些代表的图片的最低频率
  • 计算平均值:计算缩小DCT后的所有像素点的平均值。
  • 进一步减小DCT:大于平均值记录为1,反之记录为0.
  • 得到信息指纹:组合64个信息位,顺序随意保持一致性。
  • 最后比对两张图片的指纹,获得汉明距离即可。

这等同于”汉明距离”(Hamming distance,在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数)。如果不相同的数据位数不超过5,就说明两张图像很相似;如果大于10,就说明这是两张不同的图像。

.

二、pHash算法python+opencv实现

参考自:opencv resize (C/C++/Python) 主要针对图像来进行解析。下面的是pHash算法的主函数:

import cv2
import numpy as np
from compiler.ast import flatten
import sys

def pHash(imgfile):
    """get image pHash value"""
    #加载并调整图片为32x32灰度图片
    img=cv2.imread(imgfile, 0) 
    img=cv2.resize(img,(64,64),interpolation=cv2.INTER_CUBIC)

        #创建二维列表
    h, w = img.shape[:2]
    vis0 = np.zeros((h,w), np.float32)
    vis0[:h,:w] = img       #填充数据

    #二维Dct变换
    vis1 = cv2.dct(cv2.dct(vis0))
    #cv.SaveImage('a.jpg',cv.fromarray(vis0)) #保存图片
    vis1.resize(32,32)

    #把二维list变成一维list
    img_list=flatten(vis1.tolist()) 

    #计算均值
    avg = sum(img_list)*1./len(img_list)
    avg_list = ['0' if i<avg else '1' for i in img_list]

    #得到哈希值
    return ''.join(['%x' % int(''.join(avg_list[x:x+4]),2) for x in range(0,32*32,4)])

'''
cv2.imread
flags>0时表示以彩色方式读入图片 
flags=0时表示以灰度图方式读入图片 
flags<0时表示以图片的本来的格式读入图片

interpolation - 插值方法。共有5种:
1)INTER_NEAREST - 最近邻插值法
2)INTER_LINEAR - 双线性插值法(默认)
3)INTER_AREA - 基于局部像素的重采样(resampling using pixel area relation)。对于图像抽取(image decimation)来说,这可能是一个更好的方法。但如果是放大图像时,它和最近邻法的效果类似。
4)INTER_CUBIC - 基于4x4像素邻域的3次插值法
5)INTER_LANCZOS4 - 基于8x8像素邻域的Lanczos插值
http://blog.csdn.net/u012005313/article/details/51943442
'''

其中需要关注的是这段代码:

''.join(avg_list[x:x+4]),2) for x in range(0,32*32,4)]

把数字变为字符型,然后进行对比。 001.jpg:7ffc0000ffffe000 002.jpg:7fff0000fffff800

.

得到哈希值之后,需要求距离,这里较多使用海明距离来源)。 这等同于”汉明距离”(Hamming distance,在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数)。如果不相同的数据位数不超过5,就说明两张图像很相似;如果大于10,就说明这是两张不同的图像。

def hammingDist(s1, s2):
    assert len(s1) == len(s2)
    return sum([ch1 != ch2 for ch1, ch2 in zip(s1, s2)])

那么有了主函数,有了海明距离,就可以简单地实现:

HASH1=pHash('C:\\001.png')
HASH2=pHash('C:\\002.png')
out_score = 1 - hammingDist(HASH1,HASH2)*1. / (32*32/4)

先导入,然后哈希化。同时,得到海明相似性。

.

三、海量数据查找经验

本节来源于:海量数据相似度计算之simhash短文本查找

simhash的数据也会暴增,如果一天100w,10天就1000w了。 我们如果插入一条数据就要去比较1000w次的simhash,计算量还是蛮大,普通PC 比较1000w次海明距离需要 300ms ,和5000w数据比较需要1.8 s。看起来相似度计算不是很慢,还在秒级别。 原来是5000w次顺序比较,现在是少了2的16次方比较,前面16位变成了hash查找。后面的顺序比较的个数是多少? 2^16 = 65536, 5000w/65536 = 763 次。。。。实际最后链表比较的数据也才 763次!所以效率大大提高!

到目前第一点降到3.6毫秒、支持5000w数据相似度比较做完了。还有第二点同一时刻发出的文本如果重复也只能保留一条和短文本相识度比较怎么解决。其实上面的问题解决了,这两个就不是什么问题了。

  • 之前的评估一直都是按照线性计算来估计的,就算有多线程提交相似度计算比较,我们提供相似度计算服务器也需要线性计算。比如同时客户端发送过来两条需要比较相似度的请求,在服务器这边都进行了一个排队处理,一个接着一个,第一个处理完了在处理第二个,等到第一个处理完了也就加入了simhash库。所以只要服务端加了队列,就不存在同时请求不能判断的情况。
  • simhash如何处理短文本?换一种思路,simhash可以作为局部敏感哈希第一次计算缩小整个比较的范围,等到我们只有比较700多次比较时,就算使用我们之前精准度高计算很慢的编辑距离也可以搞定。当然如果觉得慢了,也可以使用余弦夹角等效率稍微高点的相似度算法。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏WOLFRAM

用 ContourPlot3D 绘制多面体

1385
来自专栏大数据挖掘DT机器学习

文本挖掘模型:本特征提取

文本挖掘模型结构示意图 ? 1. 分词 分词实例: 提高人民生活水平:提高、高人、人民、民生、生活、活水、水平 分词基本方法: 最...

3496
来自专栏大数据

大数据图:循环点阵

本文的内容最初由Marko Rodriguez和Bobby Norton在Aurelius博客上共同撰写。

1775
来自专栏PPV课数据科学社区

[SAS代码模板]抽样_surveyselect

SAS抽样代码模板 黄色部分为套用部分,红色部分为可选部分 ——————————模板—————————— proc surveyselect data=总体数据...

2639
来自专栏AI科技大本营的专栏

XGBoost参数调优完全指南(附Python代码)

作者 | Aarshay Jain 简介 如果你的预测模型表现得有些不尽如人意,那就用XGBoost吧。XGBoost算法现在已经成为很多数据工程师的重要武器。...

6426
来自专栏xingoo, 一个梦想做发明家的程序员

Spark MLlib 之 大规模数据集的相似度计算原理探索

在spark中RowMatrix提供了一种并行计算相似度的思路,下面就来看看其中的奥妙吧!

770
来自专栏深度学习之tensorflow实战篇

R语言之主成分分析-PCA 贡献率

1、关键点 综述:主成分分析 因子分析典型相关分析,三种方法的共同点主要是用来对数据降维处理的 从数据中提取某些公共部分,然后对这些公共部分进行分析和处理。 ...

3328
来自专栏编程

图像处理基础

作者简介 本文来自鲍骞月的投稿,主要讲解图像处理基础,欢迎大家积极留言,提出你的疑问或者建议,与投稿小伙伴交流。 GitHub地址:https://github...

1876
来自专栏简书专栏

基于RandomForestRegressor的波士顿房价回归预测

2018年8月27日笔记 sklearn官方英文用户使用指南:https://sklearn.org/user_guide.html sklearn翻译中文...

953
来自专栏机器学习算法与Python学习

Machine learning -- C4.5算法详解及Python实现

程序实现部分转自 Wsine的博客小站 地址:http://www.cnblogs.com/wsine/p/5180315.html C4.5是一系列用在机器...

3898

扫码关注云+社区