比较两个直方图

Question

对于一个小项目,我需要将一个图像与另一个图像进行比较 - 以确定图像是否大致相同.图像很小,从25到100px不等.图像意味着具有相同的图像数据但是非常不同,因此简单的像素相等检查将不起作用.考虑以下两种可能的情况:

1. 观看展览的博物馆中的安全(CCTV)摄像机:我们希望快速查看两个不同的视频帧是否显示相同的场景,但是照明和摄像机焦点的细微差别意味着它们将不相同.
2. 与以48x48渲染的相同图标相比,以64x64渲染的矢量计算机GUI图标的图片(但是两个图像将缩小到32x32,因此直方图具有相同的总像素数).

我决定使用直方图来表示每个图像,使用三个1D直方图:每个RGB通道一个 - 我可以安全地使用颜色并忽略纹理和边缘直方图(另一种方法是为每个图像使用单个3D直方图,但我避免这样做,因为它增加了额外的复杂性).因此,我需要比较直方图,看看它们有多相似,如果相似性度量超过某个阈值,那么我可以放心地说各个图像在视觉上是相同的 - 我将比较每个图像的相应通道直方图(例如图像1的红色直方图带有图像2的红色直方图,然后是图像1的蓝色直方图和图像2的蓝色直方图,然后是绿色直方图 - 所以我不是将图像1的红色直方图与图像2的蓝色直方图进行比较,这只是愚蠢的.

假设我有这三个直方图,它们代表三个图像的红色RGB通道的摘要(为简单起见,使用5个像素用于7像素图像):

H1            H2            H3 

  X           X                     X
  X   X       X       X             X
X X   X X     X X   X X     X X X X X
0 1 2 3 4     0 1 2 3 4     0 1 2 3 4

H1 = [ 1, 3, 0, 2, 1 ]
H2 = [ 3, 1, 0, 1, 2 ]
H3 = [ 1, 1, 1, 1, 3 ] 

图像1(H1)是我的参考图像,我想看看图像2(H2)和/或图像3(H3)是否与图像1相似.请注意,在此示例中,图像2类似于图像1,但图像3是不.

当我粗略地搜索"直方图差异"算法(至少是我能理解的那些)时,我发现一种流行的方法是只计算每个bin之间的差异,但是这种方法通常会失败,因为它会使所有bin差异相同.

为了演示这种方法的问题,在C#代码中,像这样:

Int32[] image1RedHistogram = new Int32[] { 1, 3, 0, 2, 1 };
Int32[] image2RedHistogram = new Int32[] { 3, 2, 0, 1, 2 };
Int32[] image3RedHistogram = new Int32[] { 1, 1, 1, 1, 3 };

Int32 GetDifference(Int32[] x, Int32[] y) {
    Int32 sumOfDifference = 0;
    for( int i = 0; i < x.Length; i++ ) {
        sumOfDifference += Math.Abs( x[i] - y[i] );
    }
    return sumOfDifferences;
}

其输出是:

GetDifference( image1RedHistogram, image2RedHistogram ) == 6
GetDifference( image1RedHistogram, image3RedHistogram ) == 6

这是不正确的.

有没有办法确定两个直方图之间的差异,考虑到分布的形状？

Answer 1

比较直方图本身就是一个主题.

你有两大类比较函数:bin-to-bin比较和cross-bin比较.

• Bin-to-bin比较:正如您所说,差异的标准总和非常糟糕.有一个改进,即卡方距离,即使在两种情况下 ,如果H1.red[0] = 0.001 and H2.red[0] = 0.011比如果重要得多那么重要.H1.red[0] = 0.1 and H2.red[0] = 0.11|H1.red[0] - H2.red[0]| = 0.01
• 交叉区间比较:称为区间相似性矩阵的标准示例需要一些相似性矩阵M,其中in M(i,j)是区间i和j之间的相似性.假设bin[i]是红色的.如果bin[j]是深红色,则M(i,j)很大.如果bin[j]是绿色,M(i,j)则很小.然后,直方图H1和H2之间的距离将是sqrt((H1-H2)*M*(H1-H2)).这种方法考虑了你所说的"关闭"垃圾箱!地球移动距离(EMD)是另一种跨越距离.

总而言之,我有三点:

• 你应该阅读这篇关于直方图距离的论文.它非常简单,并向您介绍直方图距离.我所谈到的所有距离都很好地总结了第1章.老实说,文章中描述的最后一件事情并不复杂,但对你的案子来说可能有些过分.
• 跨箱距离非常好,但成本可能很高(即:计算时间长,因为它涉及矩阵,因此是O(n ^ 2)).绕过昂贵的跨仓计算(并且广泛完成)的最简单方法是做一些软分配:如果一个像素是红色的,那么你应该填充远程看起来像红色的所有箱子(当然,提供更多重量到最接近的颜色).然后您可以使用bin-to-bin算法.
• 更多以数学为中心:前一点是关于减少与垃圾箱到垃圾箱比较的垃圾箱比较.事实上,它由隐含的对角化相似矩阵M.如果你可以对角化M = P'*D*P,其中P'是的转置P,然后sqrt((H1-H2)'*M*(H1-H2)) = sqrt((H1-H2)'*P'*D*P*(H1-H2)) = sqrt((P(H1-H2))'*D*(P(H1-H2))).根据您计算的微不足道P(H1-H2),这可以节省您的计算时间.直观地,如果H1是您的原始直方图,P*H1则是软分配,并且您正在使用隐式相似度矩阵M = P'*Id*P

Answer 2

我很惊讶没有人提到直方图比较的opencv实现,并且可以轻松处理不同格式的多通道图像(灰度,rgb,rgba等)(uchar,float,double等)

包括Bhattacharyya距离,卡方,相关和交叉方法.你可以找到

compareHist(InputArray H1, InputArray H2, int method)

这里的手册功能.

Answer 3

地球移动距离(EMD)通常用于此类直方图比较.EMD使用一个值来定义从直方图的一个区域到另一个区域"移动"像素的成本,并提供将特定直方图转换为目标直方图的总成本.垃圾箱越远,成本越高.

在您的示例中,将5个单位从红色[0] 移动到红色1将花费,(c*1*5)而将5个单位从红色[0]移动到红色[10]将花费(c*10*5).

有几种实现方式. FastEMD具有C++,Java和Matlab代码.我相信OpenCV也有一些支持.

使用该技术发表了许多论文用于大型图像数据库相似性搜索.

Answer 4

我发现比较直方图时,卡方检验是一个很好的起点.如果在每个直方图中没有相同数量的条目,则必须更加小心,因为您不能使用"正常"表达式.从记忆中,如果你假设直方图具有不等数量的条目,则卡方检验可以推导出来

1 /(MN)SUM_i [((Mni-Nmi)^ 2)/(mi + ni)].

M和N是每个直方图中的条目总数,mi是直方图M的bin i中的条目数,ni是直方图N的bin i中的条目数.

另一个测试是Kolmogorov-Smirnov测试.该测试着眼于两个直方图的累积概率分布之间的最大差异.这很难实现,我认为C中的数字配方在C中有一个代码片段,我很确定它在Matlab中.如果你对这个差异更感兴趣的是直方图形状,而不是确切的值,这可能是一个更好的测试,也是非参数.

Answer 5

你基本上想看一个概率距离。有很多，您必须决定哪个适合您的应用程序。最近，我在卡方和 Kullback-Leibler 方面很幸运。