%0 Journal Article
%T A Linear Approximate Algorithm for Earth Mover's Distance with Thresholded Ground Distance
%A Longjie Li
%A Min Ma
%A Peng Lei
%A Xiaoping Wang
%A Xiaoyun Chen
%J Mathematical Problems in Engineering
%D 2014
%I Hindawi Publishing Corporation
%R 10.1155/2014/406358
%X 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( )). 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, , which applies a threshold to the ground distance. To compute , the FastEMD approach can be employed. We also propose a novel linear approximation algorithm. Our algorithm achieves 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. 1. Introduction The development of advanced multimedia technology increases the importance of image retrieval, since large-scale image datasets are proliferating. Effective and efficient methods for computing the similarity between images is vitally important to content-based image retrieval (CBIR) systems. The earth moverĄ¯s distance (EMD) is a famous measure for image retrieval [1]. It not only takes the corresponding bins into account, but also considers the correlations between noncorresponding bins and thus is robust to histogram shift and rotation. The effectiveness of EMD and/or its variants is witnessed in many application domains, such as image retrieval [1¨C4], common pattern discovery [5, 6], mathematical symbol retrieval [7], contour matching [8], texture retrieval [1, 9], shape matching [10], graph matching [11], visual event recognition [12], face verification [13, 14], visual tracker [15], and uncertain or probability data [16, 17]. The EMD defines the comparison of two histograms as the transportation problem. (In [1], EMD is used to compute the distance between two signatures. For the convenience of statement, we use histogram in this paper. In fact, our algorithm can be used to both histogram and signature.) The minimum cost to transport one histogram to another one is taken as the distance of the two histograms.
%U http://www.hindawi.com/journals/mpe/2014/406358/