A linear approximate algorithm for Eerth mover's distance with thresholded ground distance
type: Item
instance of: scholarly article
title: A linear approximate algorithm for Eerth mover's distance with thresholded ground distance
zbMATH Open document ID: 1407.68497
DOI: 10.1155/2014/406358
author: Longjie Li
author: Min Ma
author: Peng Lei
author: Xiao Ping Wang
author: Xiaoyun Chen
published in: Mathematical Problems in Engineering
publication date: 2019-02-08T00:00:00Z
review text: Summary: Effective and efficient image comparison plays a vital role in content-based image retrieval (CBIR). The earth mover's distance (EMD) is an enticing measure for image comparison, offering intuitive geometric interpretation and modelling the human perceptions of similarity. Unfortunately, computing EMD, using the simplex method, has cubic complexity. FastEMD, based on min-cost flow, reduces the complexity to \((O(N^2\log N))\). Although both methods can obtain the optimal result, the high complexity prevents the application of EMD on large-scale image datasets. Thresholding the ground distance can make EMD faster and more robust, since it can decrease the impact of noise and reduce the range of transportation. In this paper, we present a new image distance metric, \(\mathrm{EMD}^+\), which applies a threshold to the ground distance. To compute \(\mathrm{EMD}^+\), the FastEMD approach can be employed. We also propose a novel linear approximation algorithm. Our algorithm achieves \(O \left(N\right)\) complexity with the benefit of qualified bins. Experimental results show that (1) our method is 2 to 3 orders of magnitude faster than EMD (computed by FastEMD) and 2 orders of magnitude faster than FastEMD and (2) the precision of our approximation algorithm is no less than the precision of FastEMD.
Mathematics Subject Classification ID: 68T45
Mathematics Subject Classification ID: 68U10
Mathematics Subject Classification ID: 68T10
zbMATH DE Number: 7016362
Wikidata QID: Q59066821
describes a project that uses: EMD
describes a project that uses: SIMPLIcity
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2014/406358
OpenAlex ID: W2061496024
cites work: The earth mover's distance as a metric for image retrieval
cites work: Computer Vision - ECCV 2004
cites work: Face Recognition Using Spatially Constrained Earth Mover's Distance
description: scientific article; zbMATH DE number 7016362