Diffusion distance for histogram comparison

Abstract

A new measure to compare histogram-based descriptors, a diffusion distance, is disclosed. The difference between two histograms is defined to be a temperature field. The relationship between histogram similarity and diffusion process is discussed and it is shown how the diffusion handles deformation as well as quantization effects. As a result, the diffusion distance is derived as the sum of dissimilarities over scales. Being a cross-bin histogram distance, the diffusion distance is robust to deformation, lighting change and noise in histogram-based local descriptors. In addition, it enjoys linear computational complexity which significantly improves previously proposed cross-bin distances with quadratic complexity or higher The proposed approach is tested on both shape recognition and interest point matching tasks using several multi-dimensional histogram-based descriptors including shape context, SIFT and spin images. In all experiments, the diffusion distance performs excellently in both accuracy and efficiency in comparison with other state-of-the-art distance measures. In particular, it performs as accurate as the Earth Mover's Distance with a much greater efficiency.