Image Compression and Filtering Using Pyramid Data Structures

1. INTRODUCTION.

A new image compression scheme was described by Adelson and Burt (1961) . In this method, o. low-po.ss filtered image is subtracted from the origino.l image, giv­ ing an uncorrelated difference image. Given the original 'image Yo. it is low-pass filtered to yield y 1. The difference is given by l 0 =Yo - g 1. The difference l 0 is de correlated and can be encoded in fewer bits , and y 1 co.n be encoded in a coo.rser sampling. Thus, coding l 0 andy 1 rather than y 0 can result in image compression. The process can be iterated, and g 1 can be represented by it's low-pass filtered version Y2 and the ditierence l1 = g 1 - Y2 · Repeating this process yields a sequence of difference pictures, l 0 , L 1 , · · · · LN . each one smaller than it's predecessor.

Every y; is obtained from Yi-l using a convolution with a Gaussian-like weighting function w ot size 2m+1 by 2m+ 1. giVIng this structure the name Gaussian pyramid. Let f (x) be a function defined only at integer values of x, then in the one-dimensional case, for 0 < l ~ N :

The disto.nce between elements is multiplied by r from one level to the next, while the number or elements in each level is reduced by a factor or r and by r 2 in the two-dimensional case .

When using m = 2 the weighting function w has the form

A typical value or a is 0.4 . In the two-dimensional case w ls separable: w(i,j) = w(i)w(j).

To obtain the sequence lo , l 1 , · · · lN-I of difference pictures, we define the expansion of an NxN picture into an rN x rN as follows :

Thl .. rnearch has been aupported by the U.S. - Iuael Binational Science Foundation grant no. 2442/Bl .

where the sum includes only those terms for which =:..__ -i . r and ~are both integers.

r

The sequence l; is then defined by

In this sequence too, every l; has only ~ as many eler ments o.s l;_1. Every level is a difference of two levels in the Gaussian pyramid, making it equivalent to a convo­ lution with a Laplacian-like filter. and thus the struc­ ture is called the Laplacian pyramid.

The original image y 0 can be recovered by revers­ ing the steps of the generation of the Laplo.cian pyramid:

it is interesting to note that Laplacian operators were suggested as important steps in human visual percep­ tion (Marr 1962). A complete description of the pyramid representation can be found in Burt( 19BO) and Adelson and Burt(19B1). Example of building a picture using this scheme is shown in Figure 1.

2. COIIPRESSION

Compression can be achieved by requantization of the values in the Laplacian pyramid since they are mostly decorrelated. The quality of the reconstructed image will depend on the technique used for quantiza­ tion and on the number of quantization steps. Deciding on the number of quantization steps may depend on perceptual knowledge: less steps will be chosen in the pyramid levels corresponding to least sensed frequen­ cies. This perceptual question will not be addressed F'Lgure 8: Compression using the Laplacian pyramid. a) Four quantization steps at all levels (2.66 bits / pixel). Two steps at the lowest level. four steps at all other levels (1. 66 bits/pixel). c) Two steps at the lowest level , eight at all other levels ( 2 bits / pixel) . d) Two steps at all levels (1.33 bits !pixel) .

here, but given the number of quantization steps in each level. requantization is found . We propose the use of the well known optimal quantization for this purpose, using the following definitions :

p (x) - the gray level probability density function .

k - the number of quantization steps.

z; - decision limits .

q, - new quantization values .

The quantization changes the gray level x, such that z; s x s zH1 Into qH1. For the quantization to be optimal , in the least squares norm. we minimize :

This expression is minimized for:

No llllalytical solution is known for these equations , but it is clear that they define a unique solution. We applied an iterative algorithm to find the solution.

The z; are initialized arbitrarily so that there is at least one element between each z; and z,+l .The new quantization levels q; are computed using equation (2) and then new decision levels z; are computed using (1) . The process iterates until the new decision level~ z; are equal to the previous ones . This is similar to the ISO­ DATA (Duda & Hart, 1973) algorithm. To prevent the problem of a section [z; , z;+l] from becoming empty, the new boundaries are not computed in parallel but sequentially. Results of this compression are displayed in Figure 2. Examples are shown for different numbers of quantization steps. Minimizing the quantization steps of the lowest level is the most significant, since this level has 75% of all pyramid elements . Choosing four quanti­ zation steps for the entire pyramid results in 2 bits per element in each level or 2.66 bits/pixel in the entire pyramid. Reducing the number of quantization steps to 2 in the lowest level only, leaving other levels with 4 quantization steps, results in compression of 1.66 bits/pixel.

3. FILTERING

Every level of the Gaussian pyramid is a low-pass version of the level underneath, filtered using a Gaussian-like filter . When we take the dit!erence of two Gaussian operators, we get a band limited operator which is Laplacian-like. In the Laplacian pyramid, the bottom level is a high pass filter while the middle levels are band pass filters . The top level is a low pass filter . When we reconstruct the picture back, we add up the Laplacian pyramid's levels . We define a filtering process in the reconstruction using a weighted sum:

where f f is the result of the filtering . The a; are the filtering coefficients and N is the number of pyramid levels . This filtering corresponds to frequency filtering in the Fourier domain . The frequency bands covered by the pyramid levels are displayed in Figure 3. It can be seen that by eliminating the lowest level all low­ frequencies are preserved, while high frequencies are reduced . Elimination of internal pyramid levels attenu­ ates frequencies in a circular region which grows smaller for higher levels . The coefficients will be given in a vector A, A =(aN, aN-I, a2 , a 1) . When A=( 1,1 , · · · , 1) the original picture will be reconstructed. Examples of filtered reconstructions using different coefficient vectors corresponding to frequency bands may be seen in Figure 4. The advantage of our filterin~ technique is that its computational complexity is O(n) in comparison with the FFT algorithm whose computa­ tional complexity is O(nlogn ) .

4. PICTURE NORIIALIZATION.

A Laplacian pyramid defines for every picture some frequency components, where the lower pyramid levels correspond to high frequencies and the higher pyramid levels correspond to lower frequencies. Each Ievell; can have a measure 171.t associated with it. A normalization filtering will be a filtering for which this measure will have prespecified values . One such filtering can be to equalize m; for all levels . being some "frequency equalization" .

F'Lgure 3: Effect or the Gaussian pyramid levels ln the Fourier spectrum. It was obtained by dividing the Fourier spectrum of the original picture by the Fourier spectrum or the filtered picture. a) Elimi­ nation of lowest level preserves low frequencies. b) Elimination of the second level attenuates an inte­ rior frequency band. c) Eltminatfon of the third level attenuates smaller interior frequencies .

As an example, define e, to be the energy per ele­ ment at each pyramid level

where M and N are the number of rows and column11 respectively. To equalize the energy at each level, the following filtering vector is used:

where

and e is the average energy in the pyramid. An example of a reconstruction such that the energy in all levels is equal is shown in Figure 5.

1. CONCLUDING REMARKS Efficient compression, filter­ ing and picture normalization were exhibited in the Gaussian and Laplacian pyramids . The compression results are better than Adelson and Burt( 198 1) original results, and approach the quality of other compression methods . The filtering process is computationally faster than filtering In the frequency domain, and should be preferred when there Is no need for directional filtering .

REFERENCES.

• [ 1] Adelson , E.H. and Burt , P.J. ( 1981 ), Image data compression with the Laplacian pyramid , IEEE Conference on Pa.ttern Recognition and Image Pro­ cessing, Dallas. 1981. pp . 218-223.
• Burt, P.J . (1980) , Fast hierarchical correlations with Gausslan-llke kernels. 5-th. Int . Conf. on Pa.t­ tern Recognition, Miami, 1980, pp. 828-830.
• Duda, R.O. and Hart , P .E. (1973), PrJ.ttern classification and scene analysis , New-York, Wiley.
• Marr, D. (1982) , Yision, W. H. Freeman, San­ Francisco.