Introduction to SPIHT
The SPIHT method is not a simple extension of traditional methods for image compression, and represents an important advance in the field. The method deserves special attention because it provides the following:
Highest Image Quality
If, after what we said, you are still not certain that you should believe us (because in the past you heard claims like that and then were deeply disappointed), we understand your point of view.
Progressive Image Transmission
The problem is that such widely used schemes employ a very primitive progressive image transmission method. On the other extreme, SPIHT is a state-of-the-art method that was designed for optimal progressive transmission (and still beats most non-progressive methods!). It does so by producing a fully embedded coded file (see below), in a manner that at any moment the quality of the displayed image is the best available for the number of bits received up to that moment.
So, SPIHT can be very useful for applications where the user can quickly inspect the image and decide if it should be really downloaded, or is good enough to be saved, or need refinement.
Optimized Embedded Coding
Let's see how this abstract definition is used in practice. Suppose you need to compress an image for three remote users. Each one have different needs of image reproduction quality, and you find that those qualities can be obtained with the image compressed to at least 8 Kb, 30 Kb, and 80 Kb, respectively. If you use a non-embedded encoder (like JPEG), to save in transmission costs (or time) you must prepare one file for each user. On the other hand, if you use an embedded encoder (like SPIHT) then you can compress the image to a single 80 Kb file, and then send the first 8 Kb of the file to the first user, the first 30 Kb to the second user, and the whole file to the third user.
But what is the price to pay for this "amenity"? Surprisingly, with SPIHT all three users would get (for the same file size) an image quality comparable or superior to the most sophisticated non-embedded encoders available today. SPIHT achieves this feat by optimizing the embedded coding process and always coding the most important information first.
An even more important application is for Progressive Image Transmission, where the user can decide at which point the image quality satisfies his needs, or abort the transmission after a quick inspection, etc.
A straightforward consequence of the compression simplicity is the greater coding/decoding speed. The SPIHT algorithm is nearly symmetric, i.e., the time to encode is nearly equal to the time to decode. (Complex compression algorithms tend to have encoding times much larger than the decoding times.)
Some of our demo programs use floating-point operations extensively, and can be slower in some CPUs (floating points are better when people want to test our programs with strange 16 bpp images). However, this problem can be easily solved: try the Lossless version to see an example. Similarly, the use for progressive transmission requires a somewhat more complex and slower algorithm. Some shortcuts can be used if progressive transmission is not necessary.
SPIHT has also been tested for some less usual purposes, like the compression of medical data, (e.g., electro-cardiogram (ECG) signals,) elevation maps, scientific data, and others.
For lossless compression we proposed an integer multiresolution transformation, similar to the wavelet transform, which we called S+P transform (see papers). It solves the finite-precision problem by carefully truncating the transform coefficients during the transformation (instead of after).
A codec that uses this transformation to yield efficient progressive transmission up to lossless recovery is among the SPIHT demo programs. A surprising result obtained with this codec is that for lossless compression it is as efficient as the most effective lossless encoders (lossless JPEG is definitely not among them). In other words, the property that SPIHT yields progressive transmission with practically no penalty in compression efficiency applies to lossless compression too. Below are examples of Lossless and lossy (200:1) images decoded from the same file.
Rate or Distortion Specification
The Optimized Embedded Coding property of SPIHT allows exact bit rate control, without any penalty in performance (no bits wasted with padding, or whatever). The same property also allows exact mean squared-error (MSE) distortion control. Even though the MSE is not the best measure of image quality, it is far superior to other criteria used for quality specification.
SPIHT is not an exception for this rule. One difference, however, is that due to SPIHT's Optimized Embedded Coding property, it is much easier to design efficient error-resilient schemes.
Another reason is that SPIHT generates two types of data. The first is sorting information, which needs error protection as explained above. The second consists of uncompressed sign and refinement bits, which do not need special protection because they affect only one pixel.
While SPIHT can yield gains like 3 dB PSNR over methods like JPEG, its use in noisy channels, combined with error protection as explained above, leads to much larger gains, like 6-12 dB. (Such high coding gains are frequently viewed with skepticism, but they do make sense for combined source-channel coding schemes.)
SPIHT Software Suite
The D-SPIHT software is capable of the most efficient compression of monochrome, 1 and 2 byte per pel, and color images. It has the features of specifying bit rate or quality at encoding time. For bit rate specification, the compressed file is completely and finely rate-embedded. Rate-embedded means that any lower rate D-SPIHT file is a subset of the full file and can be decoded to the given smaller rate. The decoding has the special feature of producing smaller resolution image reconstructions (such as thumbnails) directly from the compressed file without offline processing.
S-SPIHT (Striped)The S-SPIHT software shares many features of D-SPIHT, but encodes stripes consisting typically of 64 rows of an image. It therefore works with a small active memory. The small memory leads to a slight degradation in performance compared to D-SPIHT. Therefore, this software is ideal for compression of very large images, such as those from GIS and remote sensing systems. It is both efficient and fast.
T-SPIHT is a specially designed form of SPIHT that compresses large images in tiles. Remote sensing, geographical, and meteorological data are often handled in tiles rather than all at once. Therefore, systems for processing such data would prefer to use a compression by tiles. T-SPIHT can efficiently compress, with constant quality and without tile boundary artifacts, large image or data sets, whether in tile format or not. In fact, the compression is significantly more efficient than JPEG2000 in its tiled compression mode.
P-SPIHT is especially designed to efficiently compress small grayscale and color images. It is more efficient in this application than JPEG2000 or any other competing software. It is ideal for storage of photo ID’s on plastic cards with magnetic strips.
PROGRES (Progressive Resolution Decompression)
PROGRES is a progressive resolution, extremely fast version of SPIHT that has full capability of random access decoding. It chooses a quality factor for lossy compression of any size image and can decompress a given arbitrary region to any resolution very quickly. It comes either in a command line version for WINDOWS/DOS or UNIX (or Linux) or with additional region-of-interest (ROI) encoding and decoding in a UNIX (or Linux) GUI version. It is an excellent choice for remote sensing and GIS applications, where rapid browsing of large images is necessary.
PROGCODE (Lossless & Progressive)
PROGCODE is our pioneering progressive lossy to purely lossless (reversible) greyscale compression algorithm. It sets the standard for lossless compression. For larger images, the compression is still efficient, but the larger memory utilization slows down execution. This algorithm can efficiently compress medical images either lossless or with any desired rate. Moreover, the lossless file can act as an archive in a file server, from within which any desired lossy lower rate file can be extracted and decompressed directly without offline processing. This software is also ideal for multi-user storage or transmission systems, where users with different capabilities and requirements can receive the image to their desired accuracy from a single file or transmission. There are both 2-D and 3-D versions of ProgRes in console and GUI modes. The GUI mode is called xProgRes.
SPIHT, like all variable length coders, is normally sensitive to channel bit errors, in that a bit error in part of the bitstream called the significance map will cause loss of synchronization in the decoder and render all the following bits useless for improving reconstruction quality. We have inserted error-resilient properties into SPIHT through specially designed algorithms that can mitigate the loss to be only local and/or even correct the bit errors. We have built still-image and motion video codecs with these error-resilient properties.
SPM (Fastest Lossless!)
SPM software is especially designed for lossless and lossy compression of medical images. The method is not based on SPIHT, but on our patented quadrature splitting algorithm called AGP (for Amplitude and Group Partitioning). SPM calls for a quality factor, with 0 giving perfectly lossless compression. Because the intended application is medical images, the allowed lossy compression adheres to degrees of high quality. The outstanding characteristics of SPM, besides efficiency, are very fast compression and decompression, regardless of image size. It comes either in a console version or GUI version. All versions allow reduced resolution decoding from a single compressed file.