相似图片搜索的三种哈希算法

摘要:
下载地址:http://download.csdn.net/detail/nash_/5093143要比较的原始图像:图像库中的四个图像:输出结果:similar_Pic.jpg与原始图像非常相似。google.gif与原始图像完全不同。origin.jpg是与原始图像相同的图像。ohter_Word.jpg与原始图像非常相似。2.感知哈希算法的平均哈希算法过于严格且不准确。它更适合搜索缩略图。为了获得更准确的结果,可以选择感知哈希算法。它使用DCT来降低方法步骤的频率:1。缩小图像:32*32是一个很好的尺寸,便于DCT计算。2.转换为灰度图像:将缩放后的图像转换为256级灰度图像。

相似图片搜索的三种哈希算法第1张

想必大家都用google或baidu的识图功能,上面就是我搜索冠希哥一幅图片的结果,达到图片比较目的且利用信息指纹比较有三种算法,这些算法都很易懂,下面分别介绍一下:

一、平均哈希算法(aHash)

此算法是基于比较灰度图每个像素与平均值来实现的,最适用于缩略图,放大图搜索。

步骤:

1.缩放图片:为了保留结构去掉细节,去除大小、横纵比的差异,把图片统一缩放到8*8,共64个像素的图片。

2.转化为灰度图:把缩放后的图片转化为256阶的灰度图。

附上灰度图相关算法(R = red, G = green, B = blue)

1.浮点算法:Gray=R*0.3+G*0.59+B*0.11
2.整数方法:Gray=(R*30+G*59+B*11)/100
3.移位方法:Gray =(R*76+G*151+B*28)>>8;
4.平均值法:Gray=(R+G+B)/3;
5.仅取绿色:Gray=G;

3.计算平均值: 计算进行灰度处理后图片的所有像素点的平均值。

4.比较像素灰度值:遍历灰度图片每一个像素,如果大于平均值记录为1,否则为0.

5.得到信息指纹:组合64个bit位,顺序随意保持一致性即可。

6.对比指纹:计算两幅图片的指纹,计算汉明距离(从一个指纹到另一个指纹需要变几次),汉明距离越大则说明图片越不一致,反之,汉明距离越小则说明图片越相似,当距离为0时,说明完全相同。(通常认为距离>10 就是两张完全不同的图片)

下面是我用java写的此算法的程序,eclipse可直接运行。

下载地址:http://download.csdn.net/detail/nash_/5093143

待比较的原图:

相似图片搜索的三种哈希算法第2张

图片库中的四张图:

相似图片搜索的三种哈希算法第3张

输出结果:

similar_pic.jpg与原图很少相似
google.gif与原图完全不同
origin.jpg与原图是同一张图
ohter_word.jpg与原图极其相似

二、感知哈希算法(pHash)

平均哈希算法过于严格,不够精确,更适合搜索缩略图,为了获得更精确的结果可以选择感知哈希算法,它采用的是DCT(离散余弦变换)来降低频率的方法

步骤:

1.缩小图片:32 * 32是一个较好的大小,这样方便DCT计算

2.转化为灰度图:把缩放后的图片转化为256阶的灰度图。(具体算法见平均哈希算法步骤)

3.计算DCT:DCT把图片分离成分率的集合

4.缩小DCT:DCT是32*32,保留左上角的8*8,这些代表的图片的最低频率

5.计算平均值:计算缩小DCT后的所有像素点的平均值。

6.进一步减小DCT:大于平均值记录为1,反之记录为0.

7.得到信息指纹:组合64个信息位,顺序随意保持一致性即可。

8.对比指纹:计算两幅图片的指纹,计算汉明距离(从一个指纹到另一个指纹需要变几次),汉明距离越大则说明图片越不一致,反之,汉明距离越小则说明图片越相似,当距离为0时,说明完全相同。(通常认为距离>10 就是两张完全不同的图片)

此算法可参考开源项目pHash,下载地址:http://www.phash.org/download/

三、差异哈希算法(dHash)

相比pHash,dHash的速度要快的多,相比aHash,dHash在效率几乎相同的情况下的效果要更好,它是基于渐变实现的。

步骤:

1.缩小图片:收缩到9*8的大小,一遍它有72的像素点

2.转化为灰度图:把缩放后的图片转化为256阶的灰度图。(具体算法见平均哈希算法步骤)

3.计算差异值:dHash算法工作在相邻像素之间,这样每行9个像素之间产生了8个不同的差异,一共8行,则产生了64个差异值

4.获得指纹:如果左边的像素比右边的更亮,则记录为1,否则为0.

需要说明的是这种指纹算法不仅可以应用于图片搜索,同样适用于其他多媒体形式。除此之外,图片搜索特征提取方法有很多,很多算法还有许多可以改进的地方,比如对于人物可以先进行人脸识别,再在面部区域进行局部的哈希,或者背景是纯色的可以先过滤剪裁等等,最后在搜索的结果中还可以根据颜色、风景、产品等进行过滤。

==================================================================================================

  作者:nash_  欢迎转载,与人分享是进步的源泉!

  转载请保留原文地址:http://blog.csdn.net/nash_/article/details/8618775

免责声明:文章转载自《相似图片搜索的三种哈希算法》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇linux网络编程-socket(1)【javaweb】库存物资管理系统思路与总结下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

一种面向高维数据的集成聚类算法

聚类集成已经成为机器学习的研究热点,它对原始数据集的多个聚类结果进行学习和集成,得到一个能较好地反映数据集内在结构的数据划分。很多学者的研究证明聚类集成能有效地提高聚类结果的准确性、鲁棒性和稳定性。本文提出了一种面向高维数据的聚类集成算法。该方法针对高维数据的特点,先用分层抽样的方法结合信息增益对每个特征簇选择合适数量比较重要的特征的生成新的具代表意义的...

数据挖掘——聚类算法(一)

数据挖掘——聚类算法(一)1、聚类的定义     俗话说“人以群分、物以类聚”,聚类的思想就是通过将属性相近的数据分为一类。聚类算法属于非监督算法,即不需要专家样本,让无序的数据自行进行组合,最后达到某种要求之后停止聚集。 2、聚类分类聚类按照原理角度可以大体分为四类:1)基于原型的聚类(也成为基于距离的聚类);2)基于密度的聚类;3)基于凝聚层次聚类;4...

[PHP] 6种负载均衡算法

CP from : https://www.cnblogs.com/SmartLee/p/5161415.html http://www.dataguru.cn/thread-559329-1-1.html 1、轮询法 将请求按顺序轮流地分配到后端服务器上,它均衡地对待后端的每一台服务器,而不关心服务器实际的连接数和当前的系统负载。 2、随机法 通过...

机器学习 —— 概率图模型(推理:团树算法)

  在之前的消息传递算法中,谈到了聚类图模型的一些性质。其中就有消息不能形成闭环,否则会导致“假消息传到最后我自己都信了”。为了解决这种问题,引入了一种称为团树(clique tree)的数据结构,树模型没有图模型中的环,所以此模型要比图模型更健壮,更容易收敛。 1.团树模型   链模型是一种最简单的树模型,其结构如下图所示,假设信息从最左端传入则有以下式...

图算法概论

1. 图的表示 图的表示法有两种,邻接表和邻接矩阵法,这两种方法既可以表示有向图也可以用于表示无向图。邻接表方法在稀疏的图中比较节省资源,但是邻接矩阵法在密度比较高的情况下比较好。 2. 搜索算法 搜索一个图示有序地沿着图的边访问所有的定点,图的搜索技术是图算法领域的核心 a. 广度优先搜索(Breadth-first search,BFS) 过程: 对...

Kubernetes增强型调度器Volcano算法分析

【摘要】 Volcano 是基于 Kubernetes 的批处理系统,源自于华为云开源出来的。Volcano 方便 AI、大数据、基因、渲染等诸多行业通用计算框架接入,提供高性能任务调度引擎,高性能异构芯片管理,高性能任务运行管理等能力。 1      为什么K8S需要Volcano     K8S自带的的资源调度器,有一个明显的特点是:依次调度每个容器...