EMD(Earth Mover's Distance)
Earth Mover's Distance(EMD)是由Rubner[13]等人所提出用於影像搜
寻之上,当特徵间(bin与bin)的距 可以使用ground distance求得时,用
Earth Mover's Distance做相似 计算可以得到较好的结果.
EMD与weighted quadratic distance 是cross-bin的测 方式,但是他们
主要的 同是,在weighted quadratic distance的计算方法中会与所有的bin相
似 加以计算,而EMD是将它视为一种transportation problem,去找到一个最
佳的相似 .另外在weighted quadratic distance的计算中 个histogram必须
要有相同bin的属性.
在EMD的计算方法上,直观的我们把 个分布的其中一个视为地球表面
的高山,另一分布则视为地球表面的低漥部分,而EMD主要的目的是要找出
可以将低漥部分填平的最小成本.而 ground distance是用 计算高山与低漥部
分的距 也就是搬移一个单位所需花费的成本,而当EMD的值愈小时则表示
这 个分布愈相似.接著我们介绍EMD的基本定义:
假设这 有 个signatures分别为 与
在signature P中以m个clusters 描述影像内容并且 为这个cluster i的中心,
是在cluster i中所包含的个 ,而在signature Q中共包含 n个Clusters.
在这 我们还需要一个ground distance ,用 衡 clusters 与 之
间的距 .
