Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

fastGCVM: A Fast Algorithm for the Computation of the Discrete Generalized Cramér-von Mises Distance

 
: Meyer, J.; Längle, Thomas; Beyerer, Jürgen

:
Postprint urn:nbn:de:0011-n-4618704 (721 KByte PDF)
MD5 Fingerprint: 865bd42e97070e5edafc8fb37e1a69fe
Erstellt am: 24.10.2017


Skala, Vaclav (Ed.):
WSCG 2017, 25. International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision : WSCG 2017 Plzen, Czech Republic May 29 - June 2, 2017
Plzen, 2017 (Computer Science Research Notes 2702)
ISBN: 978-80-86943-50-3
6 S.
International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision <25, 2017, Plzen>
Englisch
Konferenzbeitrag, Elektronische Publikation
Fraunhofer IOSB ()
distance; summed area table; random vector; speed up; histogram comparison; localized cumulative distribution; generalized Cramér-von Mises distance

Abstract
Comparing two random vectors by calculating a distance measure between the underlying probability density functions is a key ingredient in many applications, especially in the domain of image processing. For this purpose,
the recently introduced generalized Cramér-von Mises distance is an interesting choice, since it is well defined even for the multivariate and discrete case. Unfortunately, the naive way of computing this distance, e.g., for two discrete two-dimensional random vectors ˜x; ˜y 2 [0; : : : ;n-1]2;n 2 N has a computational complexity of O(n5) that is impractical for most applications. This paper introduces fastGCVM, an algorithm that makes use of the well known concept of summed area tables and that allows to compute the generalized Cramér-von Mises distance with a computational complexity of O(n3) for the mentioned case. Two experiments demonstrate the achievable speed
up and give an example for a practical application employing fastGCVM.

: http://publica.fraunhofer.de/dokumente/N-461870.html