ResearchBlog‎ > ‎

Computation and Application of Histograms in Image Processing, Graphics and Visualization

posted Nov 9, 2013, 10:30 PM by Teng-Yok Lee   [ updated Nov 12, 2013, 1:20 AM ]
In computer vision, image processing, and computer graphics, the researchers have tried to optimize the computation of local value distribution since it can be applied to common image filtering such as median filtering and bilateral filtering. Recently, the researchers in the visualization society also study algorithms to efficiently query histograms for arbitrary regions and the applications of local distribution. This document lists papers about efficient computation of local distribution from Cartesian grids from these research areas.

This list will keep updating. So far (2013/11/11) my observation is that different area has different research interests about histogram.

  1. The papers in computer graphics and image processing are more related to faster filtering for images/videos.
  2. The papers in information visualization are more related to fast query in order to query the histogram of arbitrary sub block in high dimensional data. (PS. so far I only know 2 papers from info vis researchers in recent years).
  3. The papers in scientific visualization are more related to the application side of local histograms. My hypothesis is that the researchers are looking for concrete examples how histograms can be applied for scientific visualization problems.
  4. On the other hand, scientific visualization conferences also have papers about fast histogram query. These papers are mainly from the research group of Prof. Han-Wei Shen.

Ppers in Computer Vision and Graphics avenues

F. Porikli.
Integral histogram: a fast way to extract histograms in cartesian spaces.
In CVPR ’05: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, volume 1, pages 829 – 836, 2005.

Ben Weiss.
Fast median and bilateral filtering.
In ACM SIGGRAPH 2006, pp. 519-526, 2006.

An O(log N) algorithm to quickly update the histogram per pixel. Based on the histograms, median filtering and bilateral filtering can be efficiently computed.

F. Porikli.
Constant time O (1) bilateral filtering.
In CVPR ’08: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, volume 1, pp. 1 – 8, 2008.

This paper shows that with box filters in the spatial domain, the bilateral filter can be computed on the region histogram. As a result, by combining integral histograms, bilateral filtering can be efficiently applied.

Kass, Michael and Justin Solomon.
Smoothed Local Histogram Filters.
ACM Transactions on Graphics, 29(4): Article No. 100, 2010.

This paper uses kernel-density estimate other than histogram to estimate the local distribution. This paper shows that the computation of kernels-based estimate for all pixels is equivalent to the convolution of kernel value at all point. As a result, the computation can be done in the frequency domain via FFT, which is independent to the region size.

Markus Hadwiger, Ronell Sicat, Johanna Beyer, Jens Krüger, and Torsten Möller.
Sparse PDF maps for non-linear multi-resolution image operations.
ACM Transaction on Graphics, 31(6): Article No. 133, 2012.

This paper present sparse PDF map. Essentially, sparse PDF map stores the models of span distribution.

Papers in Visualization avenue

L. Xu, T.-Y. Lee, and H.-W. Shen,
An Information-Theoretic Framework for Flow Visualization.
IEEE Transactions on Visualization and Computer Graphics, 16(6):1216-1224, Nov.-Dec., 2010

The main focus of this paper is to use information theory to guide the visualization of vector fields. In order to apply information theory, local distribution should be efficiently computed in order to compute information theoretic metrics such as entropy, mutual information, and conditional entropy.

D. Thompson, J. Levine, J. Bennett, P.-T. Bremer, A. Gyulassy, V. Pascucci, and P. Pebay.
Analysis of large-scale scalar data using hixels.
In LDAV ’11: Proceedings of the IEEE Symposium on Large Data Analysis and Visualization, pp. 23 –30, 2011.

Essentially, HIXEL means that each pixel or grid points stores 1 histogram. Based on hixels, this paper show multiple application in scientific visualizaition.

S. Liu, J. Levine, P.-T. Bremer, and V. Pascucci.
Gaussian mixture model based volume visualization.
In LDAV ’12: Proceedings of the IEEE Symposium on Large Data Analysis and Visualization, pp. 73 - 77, 2012.

This paper can be treated as an extension of HIXEL, but the distribution of each pixel is represented by Gaussian mixture models. As storing the parameters of Gaussian kernels is more storage-efficient than storing histograms, this paper presents a GPU-based implementation to utilize the distributions for volume visualization.

A. Chaudhuri, T.-Y. Lee, B. Zhou, C. Wang, T. Xu, H.-W. Shen, T. Peterka and Y.-J. Chiang,
Scalable Computation of Distributions from Large Scale Data Sets.
In LDAV ‘12: IEEE Symposium on Large-Scale Data Analysis and Visualization, pp. 113 - 120, 2012.

This paper studies different strategies to parallelize the computation of region histograms on parallel computers.

Steven Martin and Han-Wei Shen,
Transformations for Volumetric Range Distribution Queries.
In PacificVis '13: Proceedings of IEEE Pacific Visualization Symposium, pp. 89 - 96, 2013.

This paper presents span distributions, which are the distributions of a spatial interval (or called span). With span distributions, the region histogram of arbitrary axis-region can be computed in logarithmic time.

Zhicheng Liu, Biye Jiang, Jeffrey Heer
imMens: Real-Time Interactive Visual Exploration of Big Data
Computer Graphics Forum, 32(3): pp. 421-430, 2013.

T.-Y. Lee and H.-W. Shen
Efficient Local Statistical Analysis via Integral Histograms with Discrete Wavelet Transform.
IEEE Transactions on Visualization and Computer Graphics, 19(12):2693-2701, Dec., 2013.

As integral histograms provide fast compression, its storage overhead can be large to 3D data. This paper use Wavelet transform to compress the integral histograms to sparse set of coefficients.

Lauro Lins, James T. Klosowski, and Carlos Scheidegger
Nanocubes for Real-Time Exploration of Spatiotemporal Datasets
IEEE Transactions on Visualization and Computer Graphics, 19(12):2456 - 2465, 2013.

Appendix: Papers for fast bilateral filtering (without explicit computation of histogram computation)

Sylvain Paris and Frédo Durand. 2009.
A Fast Approximation of the Bilateral Filter Using a Signal Processing Approach.
International Journal on Computer Vision, 81(1):24-52, 2009.

This paper presents an interesting idea to converts the non-linear bilateral filtering operator to a linear convolution operator into a homogeneous coordinates in the product of the Cartesian grids and the value range.

YANG, Q., TAN, K. H., AND AHUJA, N.
Real-time O(1) bilateral filtering.
In CVPR ’09: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 557–564, 2009.

Sylvain Paris, Pierre Kornprobst, Jack Tumblin and Fr ́edo Durand
Bilateral Filtering: Theory and Applications
Foundations and Trends in Computer Graphics and Vision, 4(1): 1 - 7, 2008.
Comments