Lossless Volume Compression
James E. Fowler,
Roni Yagel
The following describes an algorithm for the lossless compression
of volume data and represents work done in conjunction with
Roni Yagel of the Computer Science Department's
Volume Graphics Research Group
For more information, contact
Jim Fowler
or see our paper,
FY94
Index:
Compression for efficient storage and transmission of digital data
has become routine as the application of such data has grown.
Several common data-compression programs are readily available on many
computers to fight the burgeoning demand for storage space.
These programs are typically generic; that is, they can compress data
regardless of its nature. It is common that a single program is
used to compress not only English text, but also
source code, executable binaries,
and raw data. Although generic programs have some advantages,
such as greater portability, it may be worthwhile, in cases
in which the demand for storage space is particularly high, to
consider compression algorithms that have been tailored specifically
for a single application.
One such application is volume graphics,
the extension of computer graphics that addresses
rendering directly from volume data.
Since volume size grows as the cube of the resolution, even
a moderate-resolution volume requires a great amount of storage space.
We are currently working on a data-compression algorithm which,
being oriented specifically for volume data, will alleviate some of the
storage-space problems associated with volume graphics.
The algorithm we propose for volume compression is
a combination of differential pulse-code modulation (DPCM) and
Huffman coding. Both techniques have been used extensively
in compression of 2D images.
DPCM belongs to a family of compression algorithms known as
predictive techniques. In a volume, adjacent voxels usually possess
a high degree of spatial coherence; that is, adjacent voxel values are
highly correlated. Predictive techniques exploit this spatial
coherence and encode only the new information between successive
voxels. Predictive techniques feature a predictor that
calculates a value from previously encoded voxels. This
predicted value is subtracted from the current voxel, yielding
a difference value. The resulting difference value is then
Huffman coded. Thus, only the new information provided by the current voxel
is encoded.
The following table compares the compression performance
of our volume compression algorithm, compvox, with compress, a lossless,
generic compression program found on many UNIX systems.
Using compvox on the entire collection of the volumes saves
9 megabytes over compress.
Percentage Compression of Several Data-Compression
Programs on Volume Data
| Volume | Original Data | compress | compvox |
|---|
| Resolution | Size (Mb) | % Comp. | % Comp. |
|---|
| 3dknee | 256×256×127 | 15.9 | 17.2 | 40.1 |
| CThead | 256×256×113 | 14.1 | 46.0 | 53.3 |
| MRbrain | 256×256×109 | 13.6 | 40.2 | 52.7 |
| 3dhead | 256×256×109 | 13.6 | 29.9 | 48.5 |
| sod.30 | 97×97×116 | 1.0 | 65.3 | 63.7 |
| hipiph | 64×64×64 | 0.5 | 26.8 | 41.9 |
| rna | 100×120×16 | 0.2 | 33.1 | 55.4 |
The
source code for the compvox algorithm is available via
anonymous ftp to ftp://eeftp.eng.ohio-state.edu/pub/IPS/volume/compvox1.1.tar.Z.
Last update: 25-oct-96
Tansu A. Demirbilek / demirbit@ece.osu.edu