图片相似度计算及检索调研

简介: 图片相似度计算和相似图片搜索,是图片识别领域两个常见的应用场景。例如搜索相似商品,和相似的图片,在百度、淘宝中都有应用。在某些业务中,也存在对图片相似度的计算和判断。因此,在这里简单介绍一下相关算法。

背景

   图片相似度计算和相似图片搜索,是图片识别领域两个常见的应用场景。例如搜索相似商品,和相似的图片,在百度、淘宝中都有应用。在某些业务中,也存在对图片相似度的计算和判断。因此,在这里简单介绍一下相关算法。

一 Hash 算法

Hash算法作为大多图片搜索引擎的核心算法,其准确率和效率均很高,本板块将介绍Hash的三种核心算法:aHash、pHash、dHash。

1.1 图像均值哈希算法-aHash

基于均值哈希的算法称为均值哈希算法(Average Hash Algorithm,AHA),此算法是基于比较灰度图每个像素与所有像素点的平均值来实现的,最适用于缩略图,放大图搜索。

步骤:

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

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

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

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

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

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

1.2 图像感知哈希算法-pHash

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

感知哈希,全称是Perceptual Hash,是基于像素点级别的一种散列映射方式,基于认知心理学的信息加工理论为基础,提取图像中的各种特征用于生成独特但不是唯一的指纹,即一串简短且可以表示图像可被人类感知的特征内容的感知数字序列,且这些指纹具有可比性。

步骤:

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 就是两张完全不同的图片)

1.3 图像差异哈希算法-dHash

图像差异哈希,全称是Difference Hash,是基于像素点级别的一种散列映射方式。图像差异哈希是通过逐像素比对相邻像素像素值的差异,即逐像素得到当前像素与右邻像素的差值,得到一个图像差异矩阵,通过该矩阵映射生成哈希值。这个逐像素得到的图像差异矩阵的比原像素矩阵少了一列,即宽度比原像素矩阵少了1,高度不变。

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

步骤:

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

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

3.计算差异值,获得最后哈希值(与aHash主要区别处)。dHash算法工作在相邻像素之间。比较每行左右两个像素,如果左边的像素比右边的更亮(左边像素值大于右边像素值),则记录为1,否则为0。因为每行有9个像素,左右两个依次比较可得出8个值,所以8行像素共可以得出64个值,因此此时哈希值为长度是64的0-1序列。

4.图片配对,计算汉明距离。

汉明距离

汉明距离是以理查德·卫斯里·汉明的名字命名的。在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说,它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如:

1011101 与 1001001 之间的汉明距离是 2。

2143896 与 2233796 之间的汉明距离是 3。

"toned" 与 "roses" 之间的汉明距离是 3。

二 算法比较

图像均值哈希本质上是对颜色的比较,图像感知哈希由于做了 DCT 操作,本质上是对频率的比较,图像差异哈希本质上是基于渐变的感知哈希算法。

下面是对比的素材:

下面是对比的结果:

三 环境搭建与算法实现

3.1 三种hash算法的实现与环境搭建

语言:python, 版本:python2.7 / python3

module依赖:scikit-image , opencv-python

依赖安装:

sudo pip3 install --upgrade setuptoolssudo pip3 install scikit-image -i http://pypi.douban.com/simple/ --trusted-host pypi.douban.com//后面为镜像源加速
pip install --default-timeout=1000 opencv-python
//使用清华源安装
pip3 install opencv-python -i https://pypi.tuna.tsinghua.edu.cn/simple

3.2 aHash、dHash、pHash的实现示例

3.2.1 aHash

# -*- coding: utf-8 -*-
from skimage import transform
import cv2
#aHash方法计算图片的指纹数据
img=cv2.imread('/Users/develop/imageanalysis/RPC框架.png')#读入图片
length = 8
height = 8
sum = 0.0
k = 0
grey = []
# 修改图像大小
dst=transform.resize(img, (length, height))
for i in range(length):
    for j in range(height):
        (b,g,r) = dst[i,j]
        # 计算灰度值
        grey.append(r*0.3+g*0.59+b*0.11)#浮点灰度值计算
        sum+=grey[k]
        k=k+1
average = sum/(length*height)#算出平均的灰度数据
fingerprint = []
for i in range(length*height):
    if grey[i] > average:
        fingerprint.append(1)#如果灰度数据大于平均值,填入元素1,否则填入元素0
    else:
        fingerprint.append(0)
print(fingerprint)

3.2.2 dHash

# -*- coding: utf-8 -*-
from skimage import transform,data
import matplotlib.pyplot as plt
from skimage import io
import cv2
img=cv2.imread('/Users/develop/imageanalysis/RPC框架.png')#读入图片
length = 9
height = 8
sum = 0.0
k = 0
grey = []
dst=transform.resize(img, (length, height))
#灰度图转化
for i in range(length):
    for j in range(height):
        (b,g,r) = dst[i,j]
        grey.append(r*0.3+g*0.59+b*0.11)#浮点灰度值计算
        sum+=grey[k]
        k=k+1
# 获取每行的差值,为64位
differ = []
for i in range(length-1):#i 8
    for j in range(height):#j 8
        differ.append(grey[j*8+i+1]-grey[j*8+i])
#获取01值
fingerprint = []
for i in range((length-1)*height):#8*8
    if differ[i] > 0:
        fingerprint.append(1)
    else:
        fingerprint.append(0)
print(fingerprint)

3.2.3 pHash

# -*- coding: utf-8 -*-
import cv2
from skimage import transform
import numpy as np
#利用phash计算图像指纹
img=cv2.imread('/Users/develop/imageanalysis/RPC框架.png')#读入图片
length = 32
s_length = 8
dst=transform.resize(img, (length, length))
#print(type(dst))
#all 代表全图,建议32*32
matrix_all_grey = [[0 for i in range(length)] for i in range(length)]
#small 代表最低频率,8*8大小
matrix_small_grey = [[0 for i in range(s_length)] for i in range(s_length)]
# 灰度图转化
k = 0
for i in range(length):
    for j in range(length):
        (b,g,r) = dst[i,j]
        matrix_all_grey[i][j] = ( b + g + r )/3
# 缩小
fft_matrix_grey = np.fft.fft(matrix_all_grey)
for i in range(s_length):
    for j in range(s_length):
        matrix_small_grey[i][j] = fft_matrix_grey[i][j]
# 计算平均
sum_pixel = 0
for i in range(s_length):
    for j in range(s_length):
        sum_pixel += matrix_small_grey[i][j]
average = sum_pixel / (s_length*s_length)
bite = []
#赋予01值
for i in range(s_length):
    for j in range(s_length):
        if matrix_small_grey[i][j] > average :
            bite.append(1)
        else:
            bite.append(0)
print(bite)

3.3 高效对比检索

   通过上面的几种hash算法,我们可以得到一系列图片的hash值。接下来,如果需要对比去除重复图片,或者要检索,怎样才能加快查询速度呢?

   暴力的遍历显然是不太靠谱的,少量图片还好,当达到百万、千万、甚至亿级十亿级的图片数量时,O(n)的复杂度显然无法保障查询速度。

   可以考虑的是一种内存换速度的方式,64位的的hash值,分为八组,每组八位。建立八个dict,每个dict代表一组,以每组的值作为key,value是一个list,存放key相同的hash值。查找的时候,把hash值分成八个,分别在八个map里边查找,如果有key相同的,取出key相同的所有hash值进行遍历。

示例代码:

split_count = 8  # 每个64位的phash值分为八段,每段8位
def split(key, split_count):
    pre_length = 64 / split_count
    return [key[i * pre_length: (i + 1) * pre_length] for i in range(split_count)]
class ImageManager(object):
    def __init__(self):
        self.phash = pHash() # pHash类
        self.phash_cache = [defaultdict(list) for i in range(split_count)] #
        self.init_phash_map()
    def init_phash_map(self):
        #把所有的phash存在sqlite里边,这边取出所有的Image
        for image in Image.select():
            self.add_to_image_cache(image)
    def add_to_image_cache(self, image):
        # 将hash值分割为8段
        key_split = split(bin(int(image.phash))[2:].rjust(64, '0'), split_count)
        for index, k in enumerate(key_split):
            self.phash_cache[index][k].append(image)
    def has_same(self, ori_image):
        phash = ori_image.phash
        key_split = split(bin(int(phash))[2:].rjust(64, '0'), split_count)
        result = set()
        for index, k in enumerate(key_split):
            if k in self.phash_cache[index]:
                for image in self.phash_cache[index][k]:
                    distance = self.distance(int(phash), int(image.phash))
                    if distance < 5 and ori_image.key != image.key:
                        result.add(image)
        if result:
            return True,list(result)
        return False,[]

参考文章

相似图片搜索算法介绍

图像处理 图像相似算法aHash、dHash、pHash解析与对比

最近邻搜索

较大规模图片 使用phash去重

相关文章
|
4月前
|
机器学习/深度学习 算法 搜索推荐
全方位了解向量检索
如果在一个技术方案中,存在寻找“相似”的场景,那么这个场景就有可能使用向量检索的技术方案。
|
11天前
|
数据可视化 数据挖掘
数据分享|R语言IMDb TOP250电影特征数据挖掘可视化分析受众偏好、排名、投票、评分(下)
数据分享|R语言IMDb TOP250电影特征数据挖掘可视化分析受众偏好、排名、投票、评分
|
11天前
|
数据可视化 算法 数据挖掘
数据分享|R语言IMDb TOP250电影特征数据挖掘可视化分析受众偏好、排名、投票、评分(上)
数据分享|R语言IMDb TOP250电影特征数据挖掘可视化分析受众偏好、排名、投票、评分
|
4月前
|
人工智能 自然语言处理 Cloud Native
向量检索服务在语义检索、知识库搭建、AI多模态搜索等场景中有着广泛的应用
向量检索服务在语义检索、知识库搭建、AI多模态搜索等场景中有着广泛的应用
86 0
|
24天前
|
测试技术
Vript:最为详细的视频文本数据集,每个视频片段平均超过140词标注 | 多模态大模型,文生视频
[Vript](https://github.com/mutonix/Vript) 是一个大规模的细粒度视频文本数据集,包含12K个高分辨率视频和400k+片段,以视频脚本形式进行密集注释,每个场景平均有145个单词的标题。除了视觉信息,还转录了画外音,提供额外背景。新发布的Vript-Bench基准包括三个挑战性任务:Vript-CAP(详细视频描述)、Vript-RR(视频推理)和Vript-ERO(事件时序推理),旨在推动视频理解的发展。
36 1
Vript:最为详细的视频文本数据集,每个视频片段平均超过140词标注 | 多模态大模型,文生视频
|
7月前
|
机器学习/深度学习 存储 算法
数据分类分级-结构化数据识别与分类的算法实践
本文分享了用九智汇数据分类分级产品开发过程中,对数据识别和数据分类中涉及的算法进行抽象、融合,以形成标准化产品所做的努力和积累的经验。当然,算法只是分类分级产品的一小部分,整个产品设计,工程实现,也是支撑标准化产品的关键,但是限于作者水平有限,本文只讨论算法相关的话题,欢迎大家关注公众号以了解更多信息。
106 1
|
7月前
|
机器学习/深度学习 自然语言处理 数据挖掘
向量召回:深入评估离线体系,探索优质召回方法
向量召回:深入评估离线体系,探索优质召回方法
向量召回:深入评估离线体系,探索优质召回方法
|
9月前
|
人工智能 自然语言处理 算法
Similarities:精准相似度计算与语义匹配搜索工具包,多维度实现多种算法,覆盖文本、图像等领域,支持文搜、图搜文、图搜图匹配搜索
Similarities:精准相似度计算与语义匹配搜索工具包,多维度实现多种算法,覆盖文本、图像等领域,支持文搜、图搜文、图搜图匹配搜索
Similarities:精准相似度计算与语义匹配搜索工具包,多维度实现多种算法,覆盖文本、图像等领域,支持文搜、图搜文、图搜图匹配搜索
|
9月前
|
机器学习/深度学习 存储 自然语言处理
语义检索系统:基于Milvus 搭建召回系统抽取向量进行检索,加速索引
语义检索系统:基于Milvus 搭建召回系统抽取向量进行检索,加速索引
语义检索系统:基于Milvus 搭建召回系统抽取向量进行检索,加速索引
|
机器学习/深度学习 自然语言处理 搜索推荐
推荐系统[八]算法实践总结V2:排序学习框架(特征提取标签获取方式)以及京东推荐算法精排技术实战
推荐系统[八]算法实践总结V2:排序学习框架(特征提取标签获取方式)以及京东推荐算法精排技术实战
推荐系统[八]算法实践总结V2:排序学习框架(特征提取标签获取方式)以及京东推荐算法精排技术实战