内容纲要

本文主要讲EMD和Mallows distance之间的关系。ICCV2001的论文。并讲了两者的优点和缺点,分析一些情况。

Introduction

EMD在图像检索上性能表现优异。ED有一些属性和,某种程度上模拟人类对于纹理相似度的概念,他允许部分匹配,存在优秀的算法计算这种距离。然而并没有理论进行分析。同时也存在一种等价的度量,关于概率分布的,mallows或wasserstein距离,有着清晰的概率解释。
对于质量相等的两个分布,EMD与Mallows距离完全相同。MD对于不相等质量的并没有完整的介绍,因为所有的概率分布都需要归一化总共质量为1。在这种情况下,EMD和MD表现不同,根据上下文的不同,距离可能也有着不同的性能。

定义和表达式

EMD

首先是一个‘signatures,签名’file 其中xi表示数据簇i的中心,pi表示簇中的点的数量。这个signatures不是归一化的,因此,两个签名的总共masses可能不相等。给定两个签名P Q,则EMD优化下面问题:
file
其中,d_ij是两个点xi yj之间的不相似度度量党法,比如欧式距离。在EMD术语中,W是一项工作,要求从一个签名中移动土地到另一个,这个流需要满足以下约束:
file
一旦最优流确定f*ij,则PQ之间的距离为:
file

Mallows Distance

X Y是分布P Q的随机变量。则P Q的Mallow距离通常可以定义为X Y之间的不同的最小值,考虑所有的联合概率分布F,X的边际分布为P,Y的边际分布为Q:
file
其中,p可以是任意大于1的值,最常用的还是p=1或p=2. 也就是通常作为欧式番薯或L1番薯。为了使上述定义有意义,P Q的分布比附有有限的P moment:
file
注意到,指纹可以转化成合适的概率分布,通过归一化权重分布到1,沃恩需要减少F的期望,通过以下的联合分布:
file
分布F需要满足以下约束:
file
约束6 9 为了确保F使一个分布,和EMD相同。4和9也相同。只要P和Q有着相同的total mass,EMD约束2 3被强制变成等式约束,以满足约束4. 对于有着相同的total mass,EMD是在分布上一个true的度量,和MD完全相同。注意,归一化signature到相同的1,不会影响EMD距离。

两者不相同的例子

当两个签名有着不同的masses,EMD和MD完全不一样。举一个toy的例子,假设我们有两组数据x={1,4}和Y={1,2,3,4}.如果我们归一化这些有着总量mass为1,则,x中每个点的权重都是1/2,Y中的每个点权重为1/4。很容易测出最优解是 XY的联合分布对(1,1)(1,2)(4,3)(4,4)的权重为1/4,其他为0.如果我们使用L1范数来层梁距离,则M(X,Y)=EMD(X,Y)=1/2.然而,如果给每个点的权重都是1,(X的total masses=2,Y的total masses=4)则,EMD的距离=0. 如图所示:
file
从上述toy emample分析来看:EMD可能是一个缺点。尽管Y可能包含了其他上千的点,不同的value,但是XY之间距离始终为0,这种情况下,两个点就决定了距离。然而,其中比较适合图像检索,因为允许部分匹配。但是因为EMD允许匹配分布的任意部分,不管数据如何小,部分匹配可能是虚假的,特别是当两个指纹的size非常不同时。因此文字可能会产生虚假的匹配。因此,很有可能,纹理会产生严重的虚假匹配。需要注意的时,出色EMD分类结果,两个签名的size相同,不允许部分匹配。同时,EMD对权重的尺度缩放不敏感,除非两个签名都使用相同的因子缩放。例如两个纹理patches中的一个复制一下来产生一个更大的图像,则EMD距离会改变。部分匹配是一种计算有效且方便的方法,可以在大图像中搜索小匹配,但应谨慎使用,尤其不是在图像检索上下文领域。

计算Mallows距离

如果我们想计算P Q之间的距离,一般情况下我们无法获取P Q真实的分布,但可以获得大致的分布。我们的目标是估计:
file
理论上,Mallows distance适用于各种概率分布:离散或连续,使用优化算法来解决运输问题,因此分布需要离散化。如果我们有两个大小相同的样本X =(x1…,xn,}且Y = {yl,…,Yn}并使用经验分布函数为我们的估计。(也就是说每个点的分布权重为1/n,不装箱)此时MD距离为:
file
可以使用 Hungarian algorithm 解决最佳匹配。如果分布是一维的,优化问题可以很明确的解决:
file
有趣的是,一维“未展开直方图”上的纹理强度匹配距离[131及其多维扩展[141]可以用等式10的形式表示。它们都不过是应用于经验分布的Mallows距离.
如果我们有两个大小不相等的m和n样本,则仍然可以通过复制每个观察值来应用Hungarian algorithm,以使两个样本的大小都为m和n的最小公倍数。 当然,只有当m和n的最小公倍数不太大时,才有意义。 否则,在实践中,对分布进行分类或将通用算法应用于矩形矩阵。
聚类方法还是有参数的,因此仍然会受簇数影响。另一方面,如果始终经验分布,则少引入额外的算法或参数,然后会导致更精确的估计和分布之间的距离。(如果使用更全部的样本)。然而数据的维度需要被考虑在内。一维的数据比较特殊,如果更高维的话,我们需要粗化分布估计。

最后修改日期:2020年11月7日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。