Finding Median Point-Set Using Earth Mover's Distance


  • Hu Ding State University of New York at Buffalo
  • Jinhui Xu State University of New York at Buffalo



prototype learning, earth mover's distance, affine transformation, object recognition


In this paper, we study a prototype learning problem, called Median Point-Set, whose objective is to construct a prototype for a set of given point-sets so as to minimize the total Earth Mover's Distances (EMD) between the prototype and the point-sets, where EMD between two point-sets is measured under affine transformation. For this problem, we present the first purely geometric approach. Comparing to existing graph-based approaches (e.g., median graph, shock graph), our approach has several unique advantages: (1) No encoding and decoding procedures are needed to map between objects and graphs, and therefore avoid errors caused by information losing during the mappings; (2) Staying only in the geometric domain makes our approach computationally more efficient and robust to noise. We evaluate the performance of our technique for prototype reconstruction on a random dataset and a benchmark dataset, handwriting Chinese characters. Experiments suggest that our technique considerably outperforms the existing graph-based methods.




How to Cite

Ding, H., & Xu, J. (2014). Finding Median Point-Set Using Earth Mover’s Distance. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1).



Main Track: Novel Machine Learning Algorithms