English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/30603
logo share SHARE logo core CORE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:


Signatures versus histograms: Definitions, distances and algorithms

AuthorsSerratosa, Francesc; Sanfeliu, Alberto
KeywordsDistance between graphs
Multi-dimensional histograms
Pattern recognition
Issue Date2006
CitationPattern Recognition 39(5): 921-934 (2006)
AbstractThe 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 respect the methods presented before. This reduction is statistically and analytically demonstrated in the paper. The distances between histograms that we present 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, being z’ 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 makes the time consuming of the comparison drastically decrease. 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).
Publisher version (URL)http://dx.doi.org/10.1016/j.patcog.2005.12.005
Appears in Collections:(IRII) Artículos
Files in This Item:
File Description SizeFormat 
Signatures versus histograms.pdf1,45 MBAdobe PDFThumbnail
Show full item record
Review this work

Related articles:

WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.