Signatures versus histograms: Definitions, distances and algorithms

• Published in: Pattern recognition 2006-05, Vol.39 (5), p.921-934
• Main Authors: Serratosa, Francesc, Sanfeliu, Alberto
• Format: Article
• Language: English
• Subjects: Distance between histograms; Earth mover distance; Second-order random graphs; Signature
• ISSN: 0031-3203; 1873-5142
• DOI: 10.1016/j.patcog.2005.12.005

The aim of this paper is to present a new method to compare histograms. The main advantage is that there is an important time-complexity reduction with respect to the methods presented before. This reduction is statistically and analytically demonstrated in the paper. The distances between histograms that we presented are defined on a structure called signature, which is a lossless representation of histograms. Moreover, the type of the elements of the sets that the histograms represent are ordinal, nominal and modulo. We show that the computational cost of these distances is O ( z ′ ) for the ordinal and nominal types and O ( z ′ 2 ) for the modulo one, z ′ being the number of non-empty bins of the histograms. The computational cost of the algorithms presented in the literature depends on the number of bins of the histograms. In most of the applications, the obtained histograms are sparse; then considering only the non-empty bins drastically decreases the time consumption of the comparison. The distances and algorithms presented in this paper are experimentally validated on the comparison of images obtained from public databases and positioning of mobile robots through the recognition of indoor scenes (captured in a learning stage).