Wavelet Compression and MrSid

Jin  ZHANG 
Dep. Surveying and Mapping of Taiyuan University of Technology  030024
E-mail: zhangjin@public.ty.sx.cn

[Abstract] There are two basic kinds of compression schemes: lossless and lossy. A lossy compression scheme has the advantage that one can achieve much higher compression ratios than with lossless compression. The underlying idea of any compression scheme is to remove the correlation present in the data. The main idea of image compression and multiresolution analysis is to decompose the given function into a simpler low and a high resolution detail part so that the original function can be recovered from the combination of the two parts. This process of filtering the function into subbands continues recursively on the low-resolution part until the most basic (crude) representation is reached. In wavelet analysis, named also discrete wavelet transform (DWT), the scale used for observing the image data is of special importance, therefore wavelet algorithm process data at different scales or resolutions.  MrSID, short for Multi-Resolution Seamless Image Database, utilizes a patented wavelet-based compression technology for compressing and viewing digital raster imagery.
[Key Words]   Wavelet  Image Compression  MrSid   GIS

1.	Indroduction
There are two basic kinds of compression schemes: lossless and lossy. In the case of lossless compression one is interested in reconstructing the data exactly, without any loss of information. Lossless compression is often used for text files. In the case of lossy compression we allow an error as long as the quality after compression is acceptable. A lossy compression scheme has the advantage that one can achieve much higher compression ratios than with lossless compression; however, it can only be used in case one can replace the original data with an approximation which is easier to compress. We have to be specific in what we mean by an “acceptable” representation. For example, in image compression an acceptable approximation of an image is one that is visually indistinguishable from the original image. The underlying idea of any compression scheme is to remove the correlation present in the data. Correlated data is characterized by the fact that one can, given one part of the data, fill in the missing part. Several types of correlation exist. We give some examples:

  . Spatial correlation: One can often predict the value of a pixel in an image by looking at the neighboring pixels.
  . Spectral correlation: The Fourier transform of a signal is often smooth. This means that one can predict one frequency component by looking at the neighboring frequencies.
  . Temporal correlation: In a digital video, most pixels of two neighboring frames change very little in the time direction (e.g. the background).
One of the standard procedures for lossy compression is through transform coding, as indicated in Figure 1

Original          forward         coding          inverse        reconstructed
Signal           transform       coefficients      transform         signal

Figure 1: Transform coding.
The remainder of this paper is arranged follow: Section 2 is Compression algorithm and formats. Section3 is unique features of MrSid. Section 4 is the main idea of wavelet compression and multiresolution analysis. Section 5 is DWT algorithm. 

2.	Compression algorithm and image formats[11]
In 1984,  a compression algorithm known as LZW was introduced, named for its three developers A. Lempel-J.Ziv-T.A.Welch. This loss-less data compression algorithm proved so useful that CompuServe employed it in its GIF image file format (Graphic Interchange Format). It has also been used in other graphic formats, such as TIFF (Tagged Image File Format). While other methods of loss-less data compressing are available, LZW has been the foremost technique for general purpose loss-less data compression due to its simplicity and versatility and therefore one of the most widely used and accepted. When GIF and TIFF with LZW image file formats were first implemented, the LZW algorithm was thought to be in public domain. This, however, is not true as it turned out that the Unisys Corporation is the patent owner..

The TIFF format was formerly owned and maintained by the Aldus Developer's Association. TIFF is not a specific encoding format, but can be considered as a framework for encoding techniques. An open-ended format, based on the use of tagged fields, gives TIFF the flexibility to adapt to changing needs. Since its introduction, TIFF has been modified and improved with many additional capabilities, therefore along with standard TIFF also its different subclasses were developed to cover various image types..

Many methods of lossy compression have been developed. Transform compression is based on a simple premise: when the signal is passed through the Fourier or other transform, the resulting data values will in their information no longer be equal to the source. The obvious goal of the transform process is to remove as many as possible bits from the original data and at the same time removing a minimum of information.

Probably the most widely used image compression technique of this type at present is JPEG (Joint Photographic Expert Group). Its compression technique is a transform coding method based on the discrete cosine transform (DCT). JPEG is non-proprietary and in the public domain. JPEG is designed to exploit known limitations of the human eye, notably the fact that small color changes are perceived less accurately than small changes in brightness. Thus, JPEG is intended for compressing images that will be looked at by humans. The method is related to Fourier transform by representing or approximating the image as a superposition of cosine waves. 

The next well-known and newer image compression technique is the fractal compression, which converts an image into its multi-resolution representation..

The basic idea of wavelet compression is to analyse according to scale. In wavelet analysis, named also discrete wavelet transform (DWT) the scale used for observing the image data is of special importance, therefore wavelet algorithms process data at different scales or resolutions. Wavelet analysis is taking into account that the level of detail in an image is not constant, some parts of the image may have a lot of detail (like urban territories) and other parts have little of detail (like fields in the agricultural area). Wavelets are therefore a perfect match for representing image data with quick changes in image contents using approximating functions neatly contained inside finite areas. This introduction finally brings us to the software MrSID, which is an excellent example of efficient use of discrete wavelet transform technique in image compression.

MrSID is an abbreviation that stands for Multi-resolution Seamless Image Database. This compression technology was developed by the Computer Research and Applications Group at Los Alamos National Laboratory. MrSID utilizes a wavelet transform-based algorithm to achieve both the efficient storage and retrieval of digital images of very large dimensions. Image data compression improves the utilisation of storage and transmission resources, while MrSID multiscale image representation provides a multiresolution browsing capability. These features allow seamless DWT compression and smooth multi-scale browsing of image data sets of almost unlimited size. Recent breakthroughs in wavelet-based compression have removed memory limits from image compression. MrSID is applying a recently developed method for the seamless compression of image sub-blocks, where every block goes through additional correction procedure that eliminates artificial interior block boundaries. This way the algorithm works on a large image as if it had been stored in memory at once.

3. Unique Features of MrSid[10]
3.1 High Compression Ratios. MrSID was designed to dramatically compress massive images without compromising image quality. Actual compression ratios achieved can vary depending on image content and color depth, but generally averages 20:1 for grayscale and 50:1 for color. And, the user controls the compression ratio so you can determine the appropriate trade-off between compression ratio and image quality. 
3.2  Superior Image Quality. MrSID can compress any image of any size with little or no degradation in image quality, even at very high compression ratios. 
3.3  Seam Multiple Images. Users can compress multiple image tiles or mosaics of any size together into a single file. This allows you to manipulate massive images originally stored in multiple files from a single MrSID image with no visible seams. 
3.4  Multiresolution Browsing. MrSID creates many resolutions of the same image, from the same file. 
3.5 Selective Decompression. One reason why MrSID is so fast is we only decompress the portion of the image selected by the user at a time, instead of rendering the entire image.
The compression image examples of using MrSid indicate in Figure 2.

4.	The Main Idea of Wavelet Compression and Multiresolution Analysis[Lounsbery,1997 and Gortler et al, 1995]
The main idea of multiresolution analysis is to decompose the given function into a simpler low-resolution part and a high-resolution detail part so that the original function can be recovered from the combination of the two parts, while trying to decorrelate the data by compacting most of the energy in the low-resolution part and keeping the data perturbations, called wavelet coefficients, in the second parts[Lounsbery, 1997]. This process of filtering the function into subbands continues recursively on the low-resolution part until the most basic (crude) representation is reached. The motivation behind the low-pass and high-pass filtering is that for most practical functions, the data will be correlated and predictable so that most of the wavelet coefficients (or the prediction error) are going to be 

     (a) The original image                         (b) 30:1 compression ration
Figure 2  The example of using MrSid compressing LandSat TM images
                           (Used MrSid Photo Edition 1.1)
negligible, and therefor, good approximations of the function could be obtained with only a few large wavelet coefficients. This is the basis for wavelet compression methods, where the wavelet coefficients are subjected to a thresholding scheme that preserves only the most significant ones, given a certain threshold value. By manipulating the threshold (also called the quantization parameter), one can achieve multiresolution representations and varying level of detail.

The low-resolution part typically consists of a subset of the data points with weighted averages of neighbors at each of the elected data points. These averages basically implement a low-pass filter L that eliminates fine-level details. On the other hand, the detail part usually consists of abstract wavelet coefficients, computed as weighted differences that implement a high-pass filter H. This decomposition process, also called analysis, is typically used to recursively decompose the low-resolution part further into two new subbands, and so on. The whole cascading process is referred to as a filter bank and terminates when reaching the coarsest level representation, which, along with the wavelet coefficients from each level, forms the final wavelet representation of the decomposed signal.(In Fig. 3)

    
       (a) Original Image               (b) Level1 Appriximation        (c) Level1 Detail
Fig.3  level 1 approximation and detail

The analysis filters L and H are built in such a way that the orginal function can be reconstructed from the decomposed subbands. The recovery process, called synthesis, starts from the lowest(coarest) level and typically uses some kind of subdivision scheme together with the wavelet coefficients to successively refine the model until the finest(or desired) resolution is achieved. The refining and perturbing steps are implemented through two other filters, collectively called synthesis filters.

5.	DWT algorithm

The discrete wavelet transform (DWT)provides a means of decomposing sequences of real numbers in a basis of compactly supported orthonormal sequences each of which is related by being a scaled and shifted version of a single function. As such it provides the possibility of efficiently representing those features of a class of sequences localized in both position and scale. Compactly supported wavelet bases, like complex exponential bases, carry the significant advantage that fast, numerically stable algorithms exist for sequence analysis (decomposition into the wavelet basis coordinates)and synthesis (reconstruction from the coordinates in the wavelet basis).[Getz, 1992; Chui,1992; Mallat,1989 and Meyer,1993]

5.1	The Discrete Wavelet Transform
The standard form of the DWT analysis algorithm applied to a real valued sequence f ∈l2 (z ) is defined recursively by the level p decomposition
         fp-1 =Lfp
         wp-1 =Hfp                                                 (1)
where fp=f ,and L and H are respectively l2 (z) →l2 (z)low-pass and decimate and high-pass and decimate linear filter operators. The decimation is usually by a factor of 2 (Decimation by 2 of a sequence x produces a sequence y defined by yn =x2n ,n∈z). The inverse discrete wavelet transform (IDWT)creates sequences fp, p∈Z ,from the set of wavelet coordinate vectors {wk} , k∈Z , with wk∈l2 (z), and is defined recursively by the level p reconstruction
              fp = L* fp-1 +H* wp-1                               (2)
where L* and H *denote the adjoints of the maps L and H with respect to the standard inner product on l2(z). We will sometimes refer to both the forward and inverse algorithm pair as the DWT. Let L2(R) denote the square integrable functions over the real numbers. The wavelet basis of L2(R) is implicit in the DWT. The basis functions are indexed by level and shift. The basis function corresponding to level q and shift n is the limit as p goes to infinity, when such a limit exists, of the interpolated sequences f p produced by the inverse DWT with wkq =δk,n ,k ∈z ,and all other wkq zero. The convergence of these limits and the particulars of the interpolation scheme are discussed thoroughly in [ Daubechies,1988 ]. We will be more concerned with sequence spaces and will describe bases of wavelet sequences below.

In order for the algorithm (1), (2) to correspond to an orthogonal DWT we require that L and H obey the following perfect reconstruction criteria:
                LL*=I                                            (3)
                HH*=I                                            (4)
                LH*=0                                            (5)
                L*L +H*H =I                                       (6)
where I , and 0 refer respectively to the identity operator and zero operator, l2(z) →l2 (z). In practice the DWT (1) is implemented through the sums
                 fip-1 =Σfkp lk-2i
                 wip-1=Σfkp hk-2i                                        (7)
where l and h are equal length finite impulse response (FIR)filter coefficients and are designed such that (3),(4),(5),and (6) are satisfied. The IDWT (2) is implemented by the sum
              fip=Σfkp-1li-2k+wkp-1hi-2k                                                        (8)
By choosing l to have support QN≡{0 ,1 ,...,2N-1 }and to satisfy (3) one may easily create an h which allows satisfaction of (4) and (5) with 
              hk =(-1)k l2q-k-1                                          (9)
for some q in z .In this paper we will always take q=N . For convenience later we tag l and h by their support size and will refer to them as lN and hN .With each lN ,hN pair we will associate the finite impulse response FIR filters LN and HN having l-kN and h-kN  respectively, as their impulse responses. Since L and H are FIR we may relax the requirements on fp and wp to being bounded sequences in l∞(z) rather than square summable sequences l2(z). However, we will continue to consider lN and hN to be drawn from l2(z).
In terms of lN and hN ,and using the form (7)of the DWT, criteria (3),(4), and (5)become
            ΣlNn-2k lNn-2l=δk,l                       (10)
            ΣhNn-2khNn-2l=δk,l
            ΣlNn-2k hNn-2l= 0
whereδk,l denotes the Kronecker delta. Note that (11) and (12) follow from (10) with relation (9). Criterion (10)says that lN is orthogonal to shifted versions of itself when that shift is by an even integer. Criterion (11)says the same for hN . Criterion (12) says that lN and hN are orthogonal as are all of their even shifts.

There are additional conditions on lN which assure that (6) is true and that the corresponding continuous wavelet bases of L2(R), where the correspondence is through interpolation, have some degree of regularity. Maximum regularity for a particular choice of N is guaranteed by choosing the FIR low-pass filter associated with lN to have N zeros at -1. This regularity then increases as N increases. For an in-depth study of these conditions and a chart of lN ’s for N ≤10 we refer to 
(a) Original image and Level 3 Approximation        (b)Level 3 Approx. And Detial 01-03
Fig.4  The comparison of Original image and Level 3 Approximation
(One Dimension DWT)
[Daubechies, 88 ]. Here we will always assume that lN is such that (10), (11), (12), and (6) are satisfied. 

If lN corresponds to the impulse response of an FIR half-band low-pass filter, then the reversed impulse response hN represents what we will refer to as its conjugate FIR half-band high-pass filter meaning that I-L*L =H*H. The halfbandedness of the filters allows, according to the Nyquist sampling theorem, a reduction of the sampling rate by a factor of 2. This filter-and-decimate process is then repeated on the decimated output of the low-pass filter.

6.	Conclusions and suggestions
Image compression is a key issue in spatial data manipulating. This paper basically study the main feature of image formats, especially MrSid. MrSID utilizes a wavelet transform-based algorithm to achieve both the efficient storage and retrieval of digital images of very large dimensions. Image data compression improves the utilisation of storage and transmission resources, while MrSID multiscale image representation provides a multiresolution browsing capability. These features allow seamless DWT compression and smooth multi-scale browsing of image data sets of almost unlimited size. We know the MrSid is a patent technology. We must buy, and then can use it. So it is very important for us to understand MrSid, not only know how to use it. DWT has been used in image compression. It is our primary task to study the multiresolution and compression model of image data Using DWT. This paper gives the basic algorithms for DWT which can be used in algorithm design. 

7.	Acknowledgements
This paper is funded by Open Research Fund Program of LIESMARS under the grant No. WKL(98)0301 and Nature Science Fund of Shanxi Province under the grant No.991027

8.	References
[1] B.J. Lucier, Wavelets and image Compression, In: T. Lyche and L.L Schemaker, edtors, Mathrmatical Methods in Computer Aided Geometric Design II, Academic Press,1992
[2] Chui C. Wavelet analysis and its applications, Academic Press, Boston, MA, 1992.1
[3] Ingrid Daubechies, Orthonormal bases of compactly supported wavelets, Communications in Pure and Applied Mathematics ,41,1988.
[4] Ingrid Daubechies, Ten Lectures on Wavelets, SIAM,Philadelphia,PA, 1992.
[5] Neil Getz, A Fast Discrete Periodic Wavelet Transform, Memorandum No. UCB/ERL M92/138, Univesity of California, 1992.
[6] Michael Lounsbery, Tony D. DeRose and Joe Warren, Multiresolution Analysis for Surfaces of Arbitrary Topological Type, ACM Transaction on Graphics, 1997.16(3), pp.34-73
[7] Steven J. Gortler and Michael F. Cohen, Hierarchical and Variational Geometric Modeling with Wavelets, MSR-TR-95-25, Princeton University, 1995.
[8] S. Mallat, A Theory for multiresolution Signal Decomposition: The Wavelet Representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1998(11)7, pp.674-693
[9] Meyer Y., Wavelet and Operators, Cambridge University Press, 1993
[10] http://www.lizardtech.com/mrsid
[11] ftp://ftp.lizardtech.com/pub/software/pdf/MrSID-Geoinformatics.pdf
[12] http://www.adobe.com