Title: | fastGCVM: a fast algorithm for the computation of the discrete generalized cramér-von mises distance |
Authors: | Meyer, Johannes Längle, Thomas Beyerer, Jürgen |
Citation: | WSCG '2017: short communications proceedings: The 25th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision 2016 in co-operation with EUROGRAPHICS: University of West Bohemia, Plzen, Czech RepublicMay 29 - June 2 2017, p. 147-152. |
Issue Date: | 2017 |
Publisher: | Václav Skala - UNION Agency |
Document type: | konferenční příspěvek conferenceObject |
URI: | wscg.zcu.cz/WSCG2017/!!_CSRN-2702.pdf http://hdl.handle.net/11025/29745 |
ISBN: | 978-80-86943-45-9 |
ISSN: | 2464-4617 |
Keywords: | vzdálenost náhodných vektorů;souhrnné tabulky oblastí;zrychlení;srovnání histogramu;lokalizovaná kumulativní distribuce;generalizovaná Cramér-von Misesova vzdálenost |
Keywords in different language: | cistance of random vectors;summed area tables;speedup;histogram comparison;localized cumulative distributions;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; : : : ;n1]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. |
Rights: | © Václav Skala - UNION Agency |
Appears in Collections: | WSCG '2017: Short Papers Proceedings |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/29745
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.