当前位置: 代码迷 >> 综合 >> 向量相似度度量(一):EMD (Earth Mover‘s Distance)
  详细解决方案

向量相似度度量(一):EMD (Earth Mover‘s Distance)

热度:88   发布时间:2023-12-03 18:28:41.0

EMD即Earth Mover's Distance,是2000年IJCV期刊文章《The Earth Mover's Distance as a Metric for Image Retrieval》提出的一种直方图相似度量(作者在之前的会议论文中也已经提到,不过鉴于IJCV的权威性和完整性,建议参考这篇文章)。基于一个经典的运输问题求解,作者提出的EMD距离本人看来是一个非常好的度量方式。如果想细致深入的理解,建议参考这篇论文。从网上没有搜到多少对它的通俗的解释,这里将尝试以浅显易懂的方式进行阐述,希望对大家能有所帮助。

一、基本概念解释

为了进一步讨论它的细节,首先要介绍一下signature的概念,很简单,一看就懂。

(1) 先说直方图。大家都知道,一个图像的直方图就是把图像像素值量化为一系列bin,统计落在相应bin的像素个数,就形成了直方图。

(2) signature(请恕我不知道怎么准确翻译这个词哈,只能用英文了)的定义为

    

    它代表了一系列特征类别。每个s代表一类特征,m为其类中心,w为属于该类中心的数量。

    为什么要用signature呢?作者的说法是经常性的直方图的内容会聚集在某些bin上,而传统的完整表达的直方图显然太过于浪费空间。而用signature可以很方便的表达比较稀疏的直方图内容。(为什么稀疏?一个灰度图形成的一维直方图可能不会稀疏,但是想象一个三维直方图,它可能就会比较稀疏了)

    对于一个一维直方图,m为直方图的bin索引,w为该bin上的数量,相信就更容易理解了!

二、EMD

接下来言归正传,开始解释EMD。下面都是基于signature,记住它和直方图的对应关系,第一个值是类中心(一维直方图的bin索引),第二值是数量(一维直方图中某个bin中的数量)。

EMD本身是一个线性规划问题。定义如下两个signature P和Q,分别有m和n个类。

另外定义一个类别的距离矩阵,每一项dij为pi和qj的距离(在均匀的直方图中,距离就可以简化为bin的索引的差值的绝对值)。可以发现它是mxn的矩阵。

那么问题就是我们希望找到一个流(flow,我这么翻译合适吗?),当然也是个矩阵[fij],每一项fij代表从pi到qj的流动数量,从而最小化整体的代价函数:

这里就可以把EMD的本质说出来了(Earth就是土的意思,EMD其实就是搬土大赛啊),说白了,就是把P中的m个坑的土,用最小的代价搬到Q中的n个坑中,pi到qj的两个坑的距离由dij来表示。fij是从pi搬到qj的土的量;dij是pi位置到qj位置的代价(距离)。要最小化WORK工作量。EMD是把这个工作量归一化以后的表达,即除以对fij的求和。

这里就要思考它的限制条件了。

  • fij不能小于0(当然了,现实中土的数量怎么可能是负的呢)
  • fij对j的求和不能超过wpi,也即是pi中的土的数量,也就是说,从pi处搬出去的土不能超过它那里存的量
  • fij对i的求和不能超过wqj,也即是qj中的土的数量,也就是说,搬到qj处的土不能超过它那里的总容量
  • fij的总求和一定不能超过wpi的总和,也即是P中的土的总量,也就是说,你搬空了就没了;
  • fij的总求和一定不能超过wqj的总和,也即是Q的土的容量的总量,也就是说,你搬多了没地方放。

写成高大上的数学公式如下:

s.t.

三、EMD的理解

从上面的描述可以看出,EMD并不是一个简单的加加减减,求个直方图的距离。它其实是个线性规划问题,求解的结果才是EMD距离,它可以更好的描述直方图的距离。

本人将在下一篇文章中描述距离的比较分析,就可以更好的理解为什么EMD距离很好,而简单的直方图做差或者直方图交等方法并不好了。

  相关解决方案