A Linear Approximate Algorithm for Earth Mover's Distance with Thresholded Ground Distance
المؤلفون المشاركون
Ma, Min
Wang, Xiaoping
Chen, Xiaoyun
Li, Longjie
Lei, Peng
المصدر
Mathematical Problems in Engineering
العدد
المجلد 2014، العدد 2014 (31 ديسمبر/كانون الأول 2014)، ص ص. 1-9، 9ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2014-03-09
دولة النشر
مصر
عدد الصفحات
9
التخصصات الرئيسية
الملخص EN
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(N2logN)).
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, EMD+, which applies a threshold to the ground distance.
To compute EMD+, the FastEMD approach can be employed.
We also propose a novel linear approximation algorithm.
Our algorithm achieves ON 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.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Li, Longjie& Ma, Min& Lei, Peng& Wang, Xiaoping& Chen, Xiaoyun. 2014. A Linear Approximate Algorithm for Earth Mover's Distance with Thresholded Ground Distance. Mathematical Problems in Engineering،Vol. 2014, no. 2014, pp.1-9.
https://search.emarefa.net/detail/BIM-469577
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Li, Longjie…[et al.]. A Linear Approximate Algorithm for Earth Mover's Distance with Thresholded Ground Distance. Mathematical Problems in Engineering No. 2014 (2014), pp.1-9.
https://search.emarefa.net/detail/BIM-469577
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Li, Longjie& Ma, Min& Lei, Peng& Wang, Xiaoping& Chen, Xiaoyun. A Linear Approximate Algorithm for Earth Mover's Distance with Thresholded Ground Distance. Mathematical Problems in Engineering. 2014. Vol. 2014, no. 2014, pp.1-9.
https://search.emarefa.net/detail/BIM-469577
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-469577
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر