内容纲要

这是Scott Cohen的博士毕业论文,阅读其中关于EMD的部分。论文中的file不是“等价于”,而是“减法”。并没有阅读到为什么要这样表示,可能因为是向量的减法?或者是外部的参数?

前言

EMD中的概念: signature/summary 就是指图像中的有限的带权重的一些点。例如:有些权重是图像像素的分类分数。
两个分布的EMD则是,从一个分布变成另一个分布所需要的最少的工作量。另外有些工作还把weight称作mass,其实都一样。
EMD的一个重要属性是,它允许部分匹配。当分布的分布总权重不相等时,EMD则连接所有lighter的分布到heavier的分布,heavier的分布的一些点则不会匹配到lighter的分布。
当权重不相等时,可以认为是权重流的问题。
file
如图所示,两个颜色表示两个分布,每个点的面积表示每个点的权重。a b c三个图是equal weight,d是unequal weight。
EMD是一个线性规划的问题,我们后续讨论运输问题和它与EMD的关系,一些特殊的匹配等

基本定义和注释

file
file
约束4.1是非负的,约束4.2确保y中的连接到xi的权重不炒作wi。相似的,4.3确保x中的权重不超过u。最终4.4的话是保证流fij是两个签名总权重的较小值。
我们的目标是:
file
EMD距离则是:
file

EMD只有在两者权重相等时才是一个度量。证明略:
file

和运输问题的联系

file
对于不平衡的运输问题,我们需要增加一些dummy的点,赋予一些权重来平衡内容,只不过它要到其他点的cost为0。

特例

讨论两个特例,一个是one-to-one的matching,还有一个是equal-weight分布。

点对点的匹配

这种特殊情况下,所有的权重全都相等。在运输问题上,所有的供应商和需求全都相同。此时f_ij全都是0或1.可以使用单纯形法的方法。同时,这种也有点像分配问题。

一维的EMD

可以使用作者的CDFflow方法。

变体

两个变体,一个是部分匹配,另一个是约束最大的匹配。

部分匹配

部分匹配的话多一个最后的约束项
file
最后一项M(γ)则是流的权重和,部分匹配的例子如图所示:
file

假设x的总权重大于y,转化成平衡的运输问题:
file
图像的表达如下图所示,总供给为s,总需求为d,两者都和file相等。dummy供应点m+1给定一个权重为对面未赋予的权重。同时之间的距离为图中所示。为0的目的是,让dummy点随意匹配,为无穷大的目的是禁止两个虚拟点之间相互运输,不然没有意义。
file

受限的EMD

这种就是,距离最大不能超过T,超过T的距离不能连接。例子如下图所示
file
t-EMD 和不能匹配的权重的相等,因此,t-EMD是一个不相似度度量方法,而不是相似度方法。
这样更改后的线性规划为:
file

在尺度估计中的应用

(这一段我就机器翻译了,属于应用范畴)
尺度估计是准确有效地解决模式问题的关键步骤。良好的尺度估计对于精度很重要,因为适度可确定将图像中的信息与图案相比的多少;这对于提高效率很重要,因为尝试许多尺度是无效的,尤其是如果有兴趣发现很小一部分模式的情况。除了尺度估算之外,我们的方法还返回一个度量,该度量指示预测比例尺上的图案与图像之间的距离。如果此距离较大,则图案可能不会出现在图像内。如图所示:
file
我们将图像视为位置空间中颜色质量或曲线方向质量(针对形状图案问题)的分布。 我们的尺度估计方法使用EMD在边缘化边缘位置之后比较图像摘要分布。忽略位置信息确实会丢弃有用的信息,但是它降低了摘要分布的复杂性,因此可以快速进行比例估计。我们将证明,如果图案相对于图像具有单个独特特征,则无需位置信息即可获得非常好的比例估计。在颜色图案问题中,边缘分布是颜色空间中的分布。为了保持较小的分布大小,图像的颜色会聚集成少量的组(大约20个)。CIE-lab空间中颜色簇的权重是分类为该颜色的总图像区域的分数。因此,摘要分发的总权重为1。
假设图案出现在图像中占图像总面积的分数c属于[0;1],如上图(a)所示,令x和y =(Y; u)表示单位重量颜色,如图(b)(d)。由于(Y; cu)比lighter,因此EMD找出图像颜色权重c和(中的)颜色权重之间的最佳匹配(Y; cu)。考虑精确的图案出现的理想情况,在x和y中使用相同的颜色簇来显示图案颜色,然后由图案出现引起的x的颜色权重中的c与( Y; cu),EMD(x;(Y; cu))=0。此外,对于c属于(0; c],EMD(x;(Y; cu))= 0,因为每个图像的权重仍然足够 以匹配(Y; cu)中的所有权重。通常,我们将证明EMD(x;(Y; cu))随着c的减小而减小,并最终对于c属于(0; c0]变为常数,在图(e)中,水平的转折点可以认为是图像的尺度。
后面就是2分查找,计算时间复杂度较高。

EMD的下边界

这样的目的是加快EMD的计算过程。通常大多数情况下,两个签名的总权重是不相同的。由于不能假设所有数据库图像和查询都将包含相同数量的信息,因此不等权重分布之间的EMD下限在检索系统中可能非常有用。

基于质心的下边界

分布X的质心可以定义为:file
如果是equal weights,则在使用L2距离的情况下,质心就是EMD的下边界。同时,如果x权重分布比y高,那么所有的y都会连接x。此时定义x的子集x’,x’的分布的权重和与y的权重分布和相等。
file

权重和相等

这种情况下的EMD的下边界是质心距离,使用了三角不等式。
file
在使用L2距离的平方,即||a-b||的平方。
这样就有了定理:
file

权重和不相等

容易证明:
file
作者使用两种方法来解决这个问题,一个是质心下届,使用四元数和线性规划,但是这种算法复杂度要比解决EMD的算法复杂度还要高。第二种方法是计算质心边框的下边界。

首先定义c alpha:
file
file
然后预先计算C的包围框B,取一些采样值α=0.05k, k=1,…,20。当查询时,给定一个轻的分布y,y的质心到这些包围框的最小距离时EMD的下边界。其中,a是最大的采样样本,值不超过u/w。
这种情况下,我们定义:
file
file
需要解决线性规划:
file
file
三者的对比:
file

基于投影的下边界

定义投影
file
改变分布的投影,而不改变分布的权重。
一个引理:
file
一个修建策略是选择一组随机的方向V,然后获得一个低边界。验证一个方向,捕捉不同。
【太难了,不看放弃】
主要是
file

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

作者

留言

撰写回覆或留言

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