Accelerating earth movers distance with instruction set extension for image retrieval

Image retrieval is one of the most popular applications for computer vision and pattern recognition, in which similarity computation is the computational bottleneck. Earth Movers Distance (EMD) is one of the most popular similarity measure for image retrieval, which has a high time complexity of O(n
³
log n). Recently, with the explosion of image data, EMD acceleration has been emerging. In this paper, we propose an EMD acceleration architecture based on instruction set extensions for image retrieval. The EMD acceleration architecture achieves a speedup of 1.3x-2.2x over software implementations. The main advantage of the proposed architecture over existing hardware accelerations is that it can support larger histograms. Specifically, the number of supported variables in histograms has 1-2 orders of magnitude improvement.