• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>European Conference on Computer Vision(ECCV 2006) pt.3; 20060507-13; Graz(AT) >EMD-L_1: An Efficient and Robust Algorithm for Comparing Histogram-Based Descriptors
【24h】

EMD-L_1: An Efficient and Robust Algorithm for Comparing Histogram-Based Descriptors

机译：EMD-L_1：一种比较高效的基于直方图的描述符的算法

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We propose a fast algorithm, EMD-L_1, for computing the Earth Mover's Distance (EMD) between a pair of histograms. Compared to the original formulation, EMD-L_1 has a largely simplified structure. The number of unknown variables in EMD-Li is O(N) that is significantly less than O(N~2) of the original EMD for a histogram with N bins. In addition, the number of constraints is reduced by half and the objective function is also simplified. We prove that the EMD-Li is formally equivalent to the original EMD with L_1 ground distance without approximation. Exploiting the L_1 metric structure, an efficient tree-based algorithm is designed to solve the EMD-L_1 computation. An empirical study demonstrates that the new algorithm has the time complexity of O(N~2), which is much faster than previously reported algorithms with super-cubic complexities. The proposed algorithm thus allows the EMD to be applied for comparing histogram-based features, which is practically impossible with previous algorithms. We conducted experiments for shape recognition and interest point matching. EMD-L_1 is applied to compare shape contexts on the widely tested MPEG7 shape dataset and SIFT image descriptors on a set of images with large deformation, illumination change and heavy noise. The results show that our EMD-L_1-based solutions outperform previously reported state-of-the-art features and distance measures in solving the two tasks.
机译：我们提出了一种快速算法EMD-L_1，用于计算一对直方图之间的地球移动者距离（EMD）。与原始配方相比，EMD-L_1的结构大大简化。对于具有N个bin的直方图，EMD-Li中未知变量的数量为O（N），大大小于原始EMD的O（N〜2）。此外，约束的数量减少了一半，目标函数也得以简化。我们证明EMD-Li在形式上等效于原始EMD，接地距离为L_1，没有近似值。利用L_1度量结构，设计了一种有效的基于树的算法来解决EMD-L_1计算。实证研究表明，该新算法具有O（N〜2）的时间复杂度，比以前报道的具有超立方复杂度的算法要快得多。因此，所提出的算法允许将EMD应用于比较基于直方图的特征，而以前的算法实际上是不可能的。我们进行了形状识别和兴趣点匹配的实验。 EMD-L_1用于比较经过广泛测试的MPEG7形状数据集上的形状上下文和具有较大变形，照度变化和重噪声的一组图像上的SIFT图像描述符。结果表明，我们的基于EMD-L_1的解决方案在解决这两项任务方面优于先前报道的最新功能和距离测量。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号