图像相似性搜索的原理

副标题#e#

本文转自:

http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html

http://www.voidcn.com/article/p-nvcdxgfv-bnx.html

http://blog.sina.com.cn/s/blog_b27f71160101gp9c.html

http://www.voidcn.com/article/p-ojqegjmq-wy.html

http://www.voidcn.com/article/p-cttqtaiy-g.html

http://blog.sina.com.cn/s/blog_b27f71160101gpep.html

计算机怎么知道两张图片相似呢?

根据Neal Krawetz博士的解释,原理非常简单易懂。我们可以用一个快速算法,就达到基本的效果。

这里的关键技术叫做”感知哈希算法”(Perceptual hash algorithm),它的作用是对每张图片生成一个”指纹”(fingerprint)字符串,然后比较不同图片的指纹。结果越接近,就说明图片越相似。

下面是一个最简单的实现:

一、平均哈希算法(aHash)

此算法是基于比较灰度图每个像素与平均值来实现的。

第一步,缩小尺寸。

将图片缩小到8×8的尺寸,总共64个像素。这一步的作用是去除图片的细节,只保留结构、明暗等基本信息,摒弃不同尺寸、比例带来的图片差异。

图像相似性搜索的原理

?

图像相似性搜索的原理

第二步,简化色彩。

将8*8的小图片转换成灰度图像,将64个像素的颜色(red,green,blue)转换成一种颜色(黑白灰度)。

第三步,计算平均值。

计算所有64个像素的灰度平均值。

第四步,比较像素的灰度。

将每个像素的灰度,与平均值进行比较。大于或等于平均值,记为1;小于平均值,记为0。

第五步,计算哈希值。

将上一步的比较结果,组合在一起,就构成了一个64位的整数,这就是这张图片的指纹。组合的次序并不重要,只要保证所有图片都采用同样次序就行了。

?=?

图像相似性搜索的原理

?= 8f373714acfcf4d0

得到指纹以后,就可以对比不同的图片,看看64位中有多少位是不一样的。在理论上,这等同于计算”汉明距离”(Hamming distance)。如果不相同的数据位不超过5,就说明两张图片很相似;如果大于10,就说明这是两张不同的图片。

步骤说明:

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

算法实现

#p#副标题#e##p#分页标题#e#

关于均值哈希算法的实现,请参考:Google?以图搜图?-?相似图片搜索原理?-?Java实现http://blog.csdn.net/luoweifu/article/details/7733030

下面给出matlab实现平均哈希算法(aHash)

%http://blog.sina.com.cn/s/blog_b27f71160101gp9c.html
%输入两幅图片,返回值为它们的为汉明距离。
%相似图片搜索原理:平均哈希算法
%对两幅图分别作如下处理:
%1:将两副256等级的灰度图像转化成8x8大小的64等级的灰度图像
%2:求全局灰度平均值
%3:逐次将灰度值与平均灰度值比较,大于等于的置为1,否则置为0
%4:将0、1序列看做8个字节(统一顺序)
%5:比较两幅图的数据位,如果不同的数据为不超过5位,则非常相似,若超过10为则认为两幅图无关
function v=tineyesearch_ahash(picture1,picture2)
t1=imresize(picture1,[8 8],'bicubic'); %图片放缩到固定大小
t2=imresize(picture2,'bicubic'); %图片放缩到固定大小
t1=round(t1/4);
t2=round(t2/4);
mem1=round(sum(sum(t1))/64);
mem2=round(sum(sum(t2))/64);
for i=1:8
    for j=1:8
        if t1(i,j)>=mem1
            t1(i,j)=1;
        else
            t1(i,j)=0;
        end
        if t2(i,j)>=mem2
            t2(i,j)=1;
        else
            t2(i,j)=0;
        end
    end
end
h=abs(t1-t2);
v=sum(sum(h));

#p#副标题#e##p#分页标题#e#

%http://blog.sina.com.cn/s/blog_b27f71160101gp9c.html
clear;
close all;
clc;
srcDir=uigetdir('Choose source directory.'); 
cd(srcDir);
allnames=struct2cell(dir('*.jpg'));
[k,len]=size(allnames); 
FinalResult = {};

for i=1:len
    name=allnames{1,i};
picture1 = imread(name);
picture2 = imread('006.jpg');
v=tineyesearch_ahash(picture1,picture2);
FinalResult{i,1} = char('006.jgp');
FinalResult{i,2} = name;
FinalResult{i,3} = v;
end

figure('NumberTitle','off','Name','统计表');
columnname =   {'ReferenceImage','TestImage','SimilarScore'};     %各列的名称
% columnformat = {'numeric','bank','numeric'};  %各列的数据类型
columneditable =  [false true true];                %各列是否是可编辑的,true是可以编辑,false是不可编辑
t = uitable('Units','normalized','Position',...
    [0.1 0.1 0.9 0.9],'Data',FinalResult,...
    'ColumnName',columnname,...
    'ColumnEditable',columneditable);

具体的代码实现,可以参见Wote用python语言写的imgHash.py。代码很短,只有53行。使用的时候,第一个参数是基准图片,第二个参数是用来比较的其他图片所在的目录,返回结果是两张图片之间不相同的数据位数量(汉明距离)。

这种算法的优点是简单快速,不受图片大小缩放的影响,缺点是图片的内容不能变更。如果在图片上加几个文字,它就认不出来了。所以,它的最佳用途是根据缩略图,找出原图。

实际应用中,往往采用更强大的pHash算法和SIFT算法,它们能够识别图片的变形。只要变形程度不超过25%,它们就能匹配原图。这些算法虽然更复杂,但是原理与上面的简便算法是一样的,就是先将图片转化成Hash字符串,然后再进行比较。

如果图片放大或缩小,或改变纵横比,结果值也不会改变。增加或减少亮度或对比度,或改变颜色,对hash值都不会太大的影响。最大的优点:计算速度快!

如果你想比较两张图片,为每张图片构造hash值并且计算不同位的个数。(汉明距离)如果这个值为0,则表示这两张图片非常相似,如果汉明距离小于5,则表示有些不同,但比较相近,如果汉明距离大于10则表明完全不同的图片。

二、效果更佳的感知哈希算法pHash

虽然均值哈希更简单且更快速,但是在比较上更死板、僵硬。它可能产生错误的漏洞,如果有一个伽马校正或颜色直方图被用于到图像。这是因为颜色沿着一个非线性标尺?-?改变其中“平均值”的位置,并因此改变哪些高于/低于平均值的比特数。

一个更健壮的算法叫pHash,?pHash的做法是将均值的方法发挥到极致。使用离散余弦变换(DCT)降低频率。

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

1.缩小尺寸

pHash以小图片开始,但图片大于8*8,32*32是最好的。这样做的目的是简化了DCT的计算,而不是减小频率。

2.简化色彩

将图片转化成灰度图像,进一步简化计算量。

3.计算DCT

DCT是把图片分解频率聚集和梯状形,虽然JPEG使用8*8的DCT变换,在这里使用32*32的DCT变换。

4.缩小DCT

虽然DCT的结果是32*32大小的矩阵,但我们只要保留左上角的8*8的矩阵,这部分呈现了图片中的最低频率。

5.计算平均值

如同均值哈希一样,计算DCT的均值,

6.进一步减小DCT

这是最主要的一步,根据8*8的DCT矩阵,设置0或1的64位的hash值,大于等于DCT均值的设为”1”,小于DCT均值的设为“0”。结果并不能告诉我们真实性的低频率,只能粗略地告诉我们相对于平均值频率的相对比例。只要图片的整体结构保持不变,hash结果值就不变。能够避免伽马校正或颜色直方图被调整带来的影响。

7.构造hash值

将64bit设置成64位的长整型,组合的次序并不重要,只要保证所有图片都采用同样次序就行了。将32*32的DCT转换成32*32的图像。

图像相似性搜索的原理

与均值哈希一样,pHash同样可以用汉明距离来进行比较。(只需要比较每一位对应的位置并算计不同的位的个数)

步骤说明:

步骤:

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

使用matlab实现 PHash 算法

clear;
close all;
clc;
% read image
I = imread('cameraman.tif');

% cosine transform and reduction
d = dct2(I);
d = d(1:8,1:8);

% compute average
a = mean(mean(d));

% set bits,here unclear whether > or >= shall be used
b = d > a;
% maybe convert to string:
string = num2str(b(:)');

#p#副标题#e##p#分页标题#e#

同类中的最佳算法?

自从我做了大量关于数码照片取证和巨幅图片的收集工作之后,我需要一种方法来搜索图片,所以,我用了一些不同的感知哈希算法做一个图片搜索工具,根据我并不很科学但长期使用的经验来看,我发现均值哈希比pHash显著地要快。如果你找一些明确的东西,均值Hash是一个极好的算法,例如,我有一张图片的小缩略图,并且我知道它的大图存在于一个容器的某个地方,均值哈希能算法快速地找到它。然而,如果图片有些修改,如过都添加了一些内容或头部叠加在一起,均值哈希就无法处理,虽然pHash比较慢,但它能很好地容忍一些小的变型(变型度小于25%的图片)。

其次,如果,你运行的服务器像TinEye这样,你就可以不用每次都计算pHash值,我确信它们肯定之前就把pHash值保存在数据库中,核心的比较系统非常快,所以只需花费一次计算的时间,并且几秒之内能进行成千上百次的比较,非常有实用价值。

改进

有许多感知哈希算法的变形能改进它的识别率,例如,在减小尺寸之前可以被剪裁,通过这种方法,主体部分周围额外的空白区域不会产生不同。也可以对图片进行分割,例如,你有一个人脸识别算法,然后你需要计算每张脸的hash值,可以跟踪一般性的着色(例如,她的头发比蓝色或绿色更红,而背景比黑色更接近白色)或线的相对位置。

如果你能比较图片,那么你就可以做一些很酷的事情。例如,?你可以在GazoPa搜索引擎拖动图片,和TinEye一样,我并不知道GazoPa工作的细节,然而它似乎用的是感知哈希算法的变形,由于哈希把所有东西降低到最低频率,我三个人物线条画的素描可以和其它的图片进行比较——如匹配含有三个人的照片。

三、差异哈希算法dHash

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

步骤:

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

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

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

四、直方图相似度

#p#副标题#e##p#分页标题#e#

?每张图片都可以生成其灰度图像直方图(histogram)。如果两张图片的直方图很接近,就可以认为它们很相似。

?????因此,此处我们利用两幅图像的直方图来进行相似度的比较。原理较为简单,具体算法如下:

1、获得输入灰度图像的直方图分布;

2、将直方图划分为64个区,每个区为连续的4个灰度等级;

3、对每个区的4个值进行求和运算,得到1个数据,如此,会得到64个数据,即为该幅图像的一个向量(指纹);

4、根据步骤【1、2、3】,我们将输入的两幅图像转化为了2个向量,记为A、B;

5、计算两个向量的相似度,可以用皮尔逊相关系数或者余弦相似度计算,这里我们采用【余弦相似度】;

下面就顺便介绍一下余弦相似度的概念及用法:

??????对于两个向量,我们可以把它们想象成空间中的两条线段,都是从原点([0,…])出发,指向不同的方向。两条线段之间形成一个夹角,如果夹角为0度,意味着方向相同、线段重合;如果夹角为90度,意味着形成直角,方向完全不相似;如果夹角为180度,意味着方向正好相反。因此,我们可以通过夹角的大小,来判断向量的相似程度。夹角越小,就代表越相似。

?????????????????????????????

数字图像处理算法及原理(四):相似图片搜索(直方图相似度)

以二维空间为例,上图的a和b是两个向量,我们要计算它们的夹角θ。余弦定理告诉我们,可以用下面的公式求得:

??????????????????

数字图像处理算法及原理(四):相似图片搜索(直方图相似度)

?????????????????????????

数字图像处理算法及原理(四):相似图片搜索(直方图相似度)

假定a向量是[x1,y1],b向量是[x2,y2],那么可以将余弦定理改写成下面的形式:

?????????????

数字图像处理算法及原理(四):相似图片搜索(直方图相似度)

????????????

数字图像处理算法及原理(四):相似图片搜索(直方图相似度)

数学家已经证明,余弦的这种计算方法对n维向量也成立。假定A和B是两个n维向量,A是 [A1,A2,…,An] ,B是 [B1,B2,Bn] ,则A与B的夹角θ的余弦等于:

?????????

数字图像处理算法及原理(四):相似图片搜索(直方图相似度)

使用这个公式,我们就可以得到,句子A与句子B的夹角的余弦。

数字图像处理算法及原理(四):相似图片搜索(直方图相似度)

余弦值越接近1,就表明夹角越接近0度,也就是两个向量越相似,这就叫”余弦相似性”。

6、得到两个向量的夹角之后,我们就可以通过角度的大小来判别它们的相似程度。

7、至此,我们就完成了两幅图像的相似度计算,因此,可以通过此算法来寻找相似的图像。

#p#副标题#e##p#分页标题#e#

下面给出matlab实现直方图分布相似度

%相似图像搜索:利用直方图分布相似度
%1:获得输入两幅图片的直方图分布
%2:将直方图依次划分为64个区,即每个区有4个灰度等级
%3:分别将各自的64个区生成64个元素,即一个向量(图像指纹)
%4:计算两个向量的余弦相似度
%5:判断,若相似度
function v=tineyesearch_hist(picture1,picture2)
t1=picture1;
[a1,b1]=size(t1);
t2=picture2;
t2=imresize(t2,[a1 b1],'bicubic');%缩放为一致大小
t1=round(t1);
t2=round(t2);
e1=zeros(1,256);
e2=zeros(1,256);
%获取直方图分布
for i=1:a1
    for j=1:b1
        n1=t1(i,j)+1;
        n2=t2(i,j)+1;
        e1(n1)=e1(n1)+1;
        e2(n2)=e2(n2)+1;
    end
end
figure;
imhist(uint8(t1));
figure;
imhist(uint8(t2));
%将直方图分为64个区
m1=zeros(1,64);
m2=zeros(1,64);
for i=0:63
    m1(1,i+1)=e1(4*i+1)+e1(4*i+2)+e1(4*i+3)+e1(4*i+4);
    m2(1,i+1)=e2(4*i+1)+e2(4*i+2)+e2(4*i+3)+e2(4*i+4);
end
%计算余弦相似度
A=sqrt(sum(sum(m1.^2)));
B=sqrt(sum(sum(m2.^2)));
C=sum(sum(m1.*m2));
cos1=C/(A*B);%计算余弦值
cos2=acos(cos1);%弧度
v=cos2*180/pi;%换算成角度
figure;
imshow(uint8([t1,t2]));
title(['余弦值为:',num2str(cos1),'       ','余弦夹角为:',num2str(v),'°']);

#p#副标题#e##p#分页标题#e#

%http://blog.sina.com.cn/s/blog_b27f71160101gpep.html
clear;
close all;
clc;
srcDir=uigetdir('Choose source directory.'); 
cd(srcDir);
allnames=struct2cell(dir('*.jpg'));
[k,i};
picture1 = imread(name);
picture2 = imread('006.jpg');
v=tineyesearch_hist(picture1,columneditable);

相关文章

发表回复

您的电子邮箱地址不会被公开。