Fast Random Access to Wavelet Compressed Volumetric Data Using Hashing

Flemming Friche Rodler, Rasmus PaghBRICS 2001 · DOI

Abstract

We present a new approach to lossy storage of the coefficients of wavelet transformed data. While it is common to store the coefficients of largest magnitude (and let all other coefficients be zero), we allow a slightly different set of coefficients to be stored. This brings into play a recently proposed hashing technique that allows space efficient storage and very efficient retrieval of coefficients. Our approach is applied to compression of volumetric data sets. For the "Visible Man" volume we obtain up to 80% improvement in compression ratio over previously suggested schemes. Further, the time for accessing a random voxel is quite competitive.

1. Introduction

Volumetric data sets, such as those generated by CT, MRI, or PET scans, are essential in medical imaging and scientific visualization. However, their sheer size presents a significant challenge for storage and interactive processing. For instance, the "Visible Man" dataset, a 512x512x512 grid, required approximately 1 GB of storage in its uncompressed form—a volume that far exceeded the RAM capacity of standard workstations at the time of this research in 2001.

To facilitate interactive visualization, lossy compression is required. Traditional high-ratio compression methods, such as those employing Huffman or Arithmetic coding, are inherently sequential. Accessing a specific voxel within the volume typically requires decompressing all preceding data, which is computationally prohibitive for real-time applications. This paper addresses the conflict between high compression ratios and the need for fast, constant-time random access to individual voxels.

2. Methodology

The proposed approach integrates signal processing with advanced data structures to achieve efficient random-access compression.

2.1 3D Haar Wavelet Transform

The first stage of the pipeline involves a 3D Haar wavelet transform. This decomposition separates the volume into various subbands representing averages and directional details. In regions where the data is relatively smooth, the majority of the "detail" coefficients are near zero. By discarding these insignificant coefficients, substantial compression can be achieved.

2.2 The "Nearly-Top" Strategy

In standard wavelet compression, one typically retains the $n$ coefficients with the largest magnitudes. However, storing the explicit 3D coordinates $(x, y, z)$ for these sparse coefficients introduces significant overhead.

The authors introduce a "nearly-top" strategy. Instead of strictly adhering to the $n$ largest coefficients, the algorithm selects a set of coefficients that are nearly the largest but are also chosen to minimize collisions within a hash table. This flexibility allows the data to be stored in a highly dense hash structure without the performance degradation typically associated with high load factors. The authors demonstrate that this slight deviation from the mathematical optimum has a negligible impact on visual quality.

2.3 Hashing via Quotienting

To store the selected coefficients efficiently, the authors utilize a specialized hashing technique known as quotienting. In this scheme, the hash function itself determines a portion of the coefficient's location. Only the "remainder" (the quotient) of the location information needs to be stored in the table alongside the coefficient value. This implicit indexing eliminates the need to store full 3D coordinates, drastically reducing the metadata footprint.

To further optimize performance, a tiny "significance map" (a bit-map) is maintained. This map allows the system to skip hash lookups for blocks that are entirely zero, accelerating the reconstruction process.

2.4 Subband Merging and Performance

To further optimize performance on real hardware, the authors merged coefficients from different wavelet levels into a single hash table. This strategy improved CPU cache hit rates, as related coefficients are more likely to be stored in close proximity. This architectural consideration is a key factor in achieving the competitive random access speeds reported.

3. Experimental Evaluation

The algorithm was evaluated using two primary benchmarks:

  • The "Visible Man": A 512 × 512 × 512 CT dataset, representing the gold standard for large-scale volumetric data.
  • Engine Block: A 256 × 256 × 112 CT scan, used to test the algorithm's performance on data with sharp edges and non-cubic dimensions.

4. Results and Analysis

The proposed method demonstrates significant improvements over existing random-access compression schemes.

4.1 Compression Efficiency

On the "Visible Man" dataset, the hashing-based approach achieved an 80% improvement in compression ratio compared to previous state-of-the-art methods (e.g., Ihm & Park) while maintaining the same Peak Signal-to-Noise Ratio (PSNR). At a compression ratio of 44:1, the reconstructed slices were virtually indistinguishable from the original data. Even at a high ratio of 109:1, major anatomical features remained clear.

4.2 Access Speed

Random access performance is a critical metric for interactive use. The authors found that accessing a random voxel using their scheme was only 3 to 6 times slower than accessing uncompressed memory. While this is slower than raw RAM access, it represents a significant speedup over other wavelet-based schemes of the era, making it viable for real-time visualization.

5. Conclusion

By combining 3D Haar wavelets with a flexible hashing strategy, this research provides a robust solution for the random-access compression of volumetric data. The "nearly-top" coefficient selection proves to be a powerful heuristic for balancing mathematical optimality with data structure efficiency.

Future work may involve exploring smoother wavelets (such as Daubechies) to mitigate the blocky artifacts sometimes associated with Haar transforms at extreme compression ratios. Additionally, integrating more sophisticated rate-distortion theory could further optimize the selection of coefficients for even higher efficiency.

Summary updated

Abstract

We present a new approach to lossy storage of the coefficients of wavelet transformed data. While it is common to store the coefficients of largest magnitude (and let all other coefficients be zero), we allow a slightly different set of coefficients to be stored. This brings into play a recently proposed hashing technique that allows space efficient storage and very efficient retrieval of coefficients. Our approach is applied to compression of volumetric data sets. For the ``Visible Man'' volume we obtain up to 80% improvement in compression ratio over previously suggested schemes. Further, the time for accessing a random voxel is quite competitive.
BibTeX
@inproceedings{rodler2001fast,
  author = {Flemming Friche Rodler and Rasmus Pagh},
  title = {{Fast Random Access to Wavelet Compressed Volumetric Data Using Hashing}},
  booktitle = {BRICS},
  year = {2001},
  doi = {10.7146/brics.v8i34.21694},
}
Figure