arrow
Volume 3, Issue 2
Fast Multilevel CVT-Based Adaptive Data Visualization Algorithm

M. Emelianenko

Numer. Math. Theor. Meth. Appl., 3 (2010), pp. 195-211.

Published online: 2010-03

Export citation
  • Abstract

Efficient data visualization techniques are critical for many scientific applications. Centroidal Voronoi tessellation (CVT) based algorithms offer a convenient vehicle for performing image analysis, segmentation and compression while allowing to optimize retained image quality with respect to a given metric. In experimental science with data counts following Poisson distributions, several CVT-based data tessellation algorithms have been recently developed. Although they surpass their predecessors in robustness and quality of reconstructed data, time consumption remains to be an issue due to heavy utilization of the slowly converging Lloyd iteration. This paper discusses one possible approach to accelerating data visualization algorithms. It relies on a multidimensional generalization of the optimization based multilevel algorithm for the numerical computation of the CVTs introduced in [1], where a rigorous proof of its uniform convergence has been presented in 1-dimensional setting. The multidimensional implementation employs barycentric coordinate based interpolation and maximal independent set coarsening procedures. It is shown that when coupled with bin accretion algorithm accounting for the discrete nature of the data, the algorithm outperforms Lloyd-based schemes and preserves uniform convergence with respect to the problem size. Although numerical demonstrations provided are limited to spectroscopy data analysis, the method has a context-independent setup and can potentially deliver significant speedup to other scientific and engineering applications.

  • Keywords

Centroidal Voronoi tessellations, computational algorithms, Lloyd's method, acceleration schemes, multilevel method, binning, image analysis, visualization, signal-to-noise ratio.

  • AMS Subject Headings

65D99, 65C20

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{NMTMA-3-195, author = {}, title = {Fast Multilevel CVT-Based Adaptive Data Visualization Algorithm}, journal = {Numerical Mathematics: Theory, Methods and Applications}, year = {2010}, volume = {3}, number = {2}, pages = {195--211}, abstract = {

Efficient data visualization techniques are critical for many scientific applications. Centroidal Voronoi tessellation (CVT) based algorithms offer a convenient vehicle for performing image analysis, segmentation and compression while allowing to optimize retained image quality with respect to a given metric. In experimental science with data counts following Poisson distributions, several CVT-based data tessellation algorithms have been recently developed. Although they surpass their predecessors in robustness and quality of reconstructed data, time consumption remains to be an issue due to heavy utilization of the slowly converging Lloyd iteration. This paper discusses one possible approach to accelerating data visualization algorithms. It relies on a multidimensional generalization of the optimization based multilevel algorithm for the numerical computation of the CVTs introduced in [1], where a rigorous proof of its uniform convergence has been presented in 1-dimensional setting. The multidimensional implementation employs barycentric coordinate based interpolation and maximal independent set coarsening procedures. It is shown that when coupled with bin accretion algorithm accounting for the discrete nature of the data, the algorithm outperforms Lloyd-based schemes and preserves uniform convergence with respect to the problem size. Although numerical demonstrations provided are limited to spectroscopy data analysis, the method has a context-independent setup and can potentially deliver significant speedup to other scientific and engineering applications.

}, issn = {2079-7338}, doi = {https://doi.org/10.4208/nmtma.2010.32s.5}, url = {http://global-sci.org/intro/article_detail/nmtma/5996.html} }
TY - JOUR T1 - Fast Multilevel CVT-Based Adaptive Data Visualization Algorithm JO - Numerical Mathematics: Theory, Methods and Applications VL - 2 SP - 195 EP - 211 PY - 2010 DA - 2010/03 SN - 3 DO - http://doi.org/10.4208/nmtma.2010.32s.5 UR - https://global-sci.org/intro/article_detail/nmtma/5996.html KW - Centroidal Voronoi tessellations, computational algorithms, Lloyd's method, acceleration schemes, multilevel method, binning, image analysis, visualization, signal-to-noise ratio. AB -

Efficient data visualization techniques are critical for many scientific applications. Centroidal Voronoi tessellation (CVT) based algorithms offer a convenient vehicle for performing image analysis, segmentation and compression while allowing to optimize retained image quality with respect to a given metric. In experimental science with data counts following Poisson distributions, several CVT-based data tessellation algorithms have been recently developed. Although they surpass their predecessors in robustness and quality of reconstructed data, time consumption remains to be an issue due to heavy utilization of the slowly converging Lloyd iteration. This paper discusses one possible approach to accelerating data visualization algorithms. It relies on a multidimensional generalization of the optimization based multilevel algorithm for the numerical computation of the CVTs introduced in [1], where a rigorous proof of its uniform convergence has been presented in 1-dimensional setting. The multidimensional implementation employs barycentric coordinate based interpolation and maximal independent set coarsening procedures. It is shown that when coupled with bin accretion algorithm accounting for the discrete nature of the data, the algorithm outperforms Lloyd-based schemes and preserves uniform convergence with respect to the problem size. Although numerical demonstrations provided are limited to spectroscopy data analysis, the method has a context-independent setup and can potentially deliver significant speedup to other scientific and engineering applications.

M. Emelianenko. (2020). Fast Multilevel CVT-Based Adaptive Data Visualization Algorithm. Numerical Mathematics: Theory, Methods and Applications. 3 (2). 195-211. doi:10.4208/nmtma.2010.32s.5
Copy to clipboard
The citation has been copied to your clipboard