Header

UZH-Logo

Maintenance Infos

Tensor Decompositions for Integral Histogram Compression and Look-Up


Ballester-Ripoll, Rafael; Pajarola, R (2019). Tensor Decompositions for Integral Histogram Compression and Look-Up. IEEE Transactions on Visualization and Computer Graphics, 25(2):1435-1446.

Abstract

Histograms are a fundamental tool for multidimensional data analysis and processing, and many applications in graphics and visualization rely on computing histograms over large regions of interest (ROI). Integral histograms (IH) greatly accelerate the calculation in the case of rectangular regions, but come at a large extra storage cost. Based on the tensor train decomposition model, we propose a new compression and approximate retrieval algorithm to reduce the overall IH memory usage by several orders of magnitude at a user-defined accuracy. To this end we propose an incremental tensor decomposition algorithm that allows us to compress integral histograms of hundreds of gigabytes. We then encode the borders of any desired rectangular ROI in the IH tensor-compressed domain and reconstruct the target histogram at a high speed which is independent of the region size. We furthermore generalize the algorithm to support regions of arbitrary shape rather than only rectangles, as well as histogram field computation, i.e., recovering many histograms at once. We test our method with several multidimensional data sets and demonstrate that it radically speeds up costly histogram queries while avoiding storing massive, uncompressed IHs.

Abstract

Histograms are a fundamental tool for multidimensional data analysis and processing, and many applications in graphics and visualization rely on computing histograms over large regions of interest (ROI). Integral histograms (IH) greatly accelerate the calculation in the case of rectangular regions, but come at a large extra storage cost. Based on the tensor train decomposition model, we propose a new compression and approximate retrieval algorithm to reduce the overall IH memory usage by several orders of magnitude at a user-defined accuracy. To this end we propose an incremental tensor decomposition algorithm that allows us to compress integral histograms of hundreds of gigabytes. We then encode the borders of any desired rectangular ROI in the IH tensor-compressed domain and reconstruct the target histogram at a high speed which is independent of the region size. We furthermore generalize the algorithm to support regions of arbitrary shape rather than only rectangles, as well as histogram field computation, i.e., recovering many histograms at once. We test our method with several multidimensional data sets and demonstrate that it radically speeds up costly histogram queries while avoiding storing massive, uncompressed IHs.

Statistics

Citations

Dimensions.ai Metrics

Altmetrics

Downloads

13 downloads since deposited on 30 Aug 2019
9 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Informatics
Dewey Decimal Classification:000 Computer science, knowledge & systems
Scopus Subject Areas:Physical Sciences > Software
Physical Sciences > Signal Processing
Physical Sciences > Computer Vision and Pattern Recognition
Physical Sciences > Computer Graphics and Computer-Aided Design
Language:English
Date:February 2019
Deposited On:30 Aug 2019 10:27
Last Modified:29 Jul 2020 11:13
Publisher:Institute of Electrical and Electronics Engineers
ISSN:1077-2626
OA Status:Green
Publisher DOI:https://doi.org/10.1109/TVCG.2018.2802521
Other Identification Number:merlin-id:18085

Download

Green Open Access

Download PDF  'Tensor Decompositions for Integral Histogram Compression and Look-Up'.
Preview
Content: Accepted Version
Filetype: PDF
Size: 2MB
View at publisher