2008 | OriginalPaper | Buchkapitel
Distance between Histograms with Shuffled Cost Matrix
verfasst von : Sung-Hyuk Cha
Erschienen in: Structural, Syntactic, and Statistical Pattern Recognition
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Comparing two distributions is of fundamental importance to statistics and pattern recognition. The
earth mover’s distance
(
EMD
) has been considered an excellent distance measure between two distributions. It is defined to minimize the cost using a given cost matrix and formulated as the transportation problem which is a hard optimization problem. There are three special type cost matrices where efficient algorithms are known: nominal, ordinal, and modulo. Here the problem of identifying whether a given cost matrix has the shuffled ordinal property is considered and if so, the linear time complexity algorithm can be applied to compute the
EMD
efficiently.