Adaptive lifting schemes combining seminorms for lossless image compression

Adaptive Lifting Schemes Combining Seminorms for Lossless Image Compression Gemma Piella, Gr´egoire Pau and B´eatrice Pesquet-Popescu GET-ENST (Telecom Paris) Signal and Image Proc. Dept. 37-39 Rue Dareau, 75014 Paris, France Email: {piella,gpau,pesquet}@tsi.enst.fr

Abstract— We present a new class of adaptive wavelet decompositions that can capture the directional nature of picture information. Our method exploits the properties of seminorms to build lifting structures able to choose between different update filters, the choice being triggered by a local gradient of the input. In order to discriminate between different geometrical information, the system makes use of multiple criteria, giving rise to multiple choice of update filters. We establish the conditions under which these decisions can be recovered at synthesis, without the need for transmitting overhead information.

I. I NTRODUCTION Classical linear wavelet representations of images have the drawback of not being optimally suited to represent edge information. To overcome this problem, new multiresolution decompositions have been designed that can take into account the characteristics of the input signal/image [1], [2], [3], [4], [5], [6], [9], [7]. In [7], [11] we have introduced an adaptive wavelet decomposition based on an adaptive update lifting step. In particular, we have studied the case where the update filter coefficients are triggered by a binary decision obtained by thresholding the seminorm of the local gradient-type features of the input. The lifting scheme can therefore choose between two different update linear filters: if the seminorm of the gradient is above a threshold, it chooses one filter, otherwise it chooses the other. At synthesis, the decision is obtained in the same way but using the gradient computed from the decomposition coefficients available at synthesis. With such a thresholdingdecision scheme, perfect reconstruction amounts to the socalled Threshold Criterion, which says that the seminorm of the gradient at synthesis should be above the threshold only if the seminorm of the original gradient is. In [7] we have derived necessary and sufficient conditions for the invertibility of such adaptive schemes for various scenarios. Several simulation results have been given to illustrate the potential of our adaptive schemes for preserving the discontinuities in signals and images even at low resolutions. Furthermore, it has been shown that adaptive schemes often yield decompositions that have lower entropies than schemes with fixed update filters, a highly relevant property in the context of compression. However, the adaptive scheme proposed in [7] is not very flexible in the sense that it can only discriminate between two ‘geometric events’ (e.g., edge region or homogeneous region).

In this paper, we extend the aforementioned scheme so that it can use multiple criteria giving rise to multi-valued decision for choosing the update filters. In this way, we can discriminate between different geometric structures in order to capture the directional nature of picture information. The paper is organized as follows. Section II explains the general framework of adaptive update lifting. Section III studies a new decision criterion based on comparing two or more seminorms. General conditions for the invertibility of the resulting adaptive decompositions are provided. Section IV gives some examples and simulation results. Finally, concluding remarks are made in Section V. II. R EVISITING UPDATE LIFTING SCHEME Our wavelet decomposition uses an adaptive update lifting step, followed by a fixed prediction step, such as illustrated in Fig. 1. x′

x D

Ud

P1 ys′ 1

y s1 P2

ys′ 2

y s2 P3 y s3

ys′ 3

Fig. 1. 2D wavelet decomposition comprising an adaptive update lifting step (left) and three consecutive prediction lifting steps (right).

The input images x, ys1 , ys2 and ys3 are obtained by a polyphase decomposition of an original image x0 :  x(m, n) = x0 (2m, 2n)    ys1 (m, n) = x0 (2m, 2n + 1) ys (m, n) = x0 (2m + 1, 2n)    2 ys3 (m, n) = x0 (2m + 1, 2n + 1)

In this decomposition, x′ is called the approximation band and ys′ 1 , ys′ 2 , ys′ 3 are called the horizontal, the vertical, and the diagonal detail bands, respectively. In this section, we shall only discuss the adaptive update lifting step depicted in the left part of the scheme in Fig. 1. The prediction steps are always invertible and they will be specified in Section IV.

At every position n = (m, n), the update step is triggered by the outcome y2 (n)

dn = D(x, ys1 , ys2 , ys3 )(n) of the so-called decision map D. This map uses inputs from all four bands, and its output is a function representing an N-valued decision dn ∈ {0, 1, . . . , N − 1}. The output dn triggers the specific choice of the update step in the following sense: J X µdn ,j yj (n) , (1) x′ (n) = αdn x(n) +

y3 (n) x(n) y1 (n) y4 (n)

Fig. 2.

Labeling of samples in a 3×3 window centered at x0 (2m, 2n).

j=1

with yj (n) = ysj (n + lj ) , sj ∈ {s1 , s2 , s3 }, lj ∈ L. Here L is a window in Z2 centered around the origin. Note that the filter coefficients depend on the decision dn which may change depending on the local characteristics of the input bands. We assume that the decision map only depends of the gradient vector v(n) ∈ IRJ , with components vj (n) given by vj (n) = x(n) − yj (n) , j = 1, . . . , J . For the approximation coefficients in (1), we assume that αd +

J X

µd,j = 1 for d = 0, . . . , N − 1,

forming a partition of V : V =

N[ −1

Di ,

Di 6= ∅ and

D i ∩ Dj = φ

if i 6= j .

i=0

At synthesis, we have v ′ = Ad(v) v, and the decision rule is d ′ (v ′ ) = d(Ad(v) v). Then we have that: (i) PR holds if and only if ∀ v, d(Ad(v) v) = d(v). (ii) A necessary and sufficient condition for this to be satisfied is that ∀i ∈ {0, . . . , N − 1}, if d(v) = i, then d(Ai v) = i .

j=1

with αd 6= 0 for all d. It is easy to show that the gradient vector at synthesis v ′ (n) ∈ IRJ with components vj′ (n) = x′ (n) − yj (n), j = 1, . . . , J, is related to v(n) by means of the linear relation v ′ (n) = Ad v(n) , where Ad = I − ubTd , I is the J × J identity matrix, and u = (1, . . . , 1)T , bd = (µd,1 , . . . , µd,J )T are vectors of length J. The superindex ‘T’ denotes transposition and d = dn . To have Perfect Reconstruction (PR) we must be able to recover the decision dn from the gradient vector at synthesis v ′ (n) = Ad v(n). That is, for all n, D′ (x′ , ys1 , ys2 , ys3 )(n) = D(x, ys1 , ys2 , ys3 )(n) . Throughout the remainder of this paper we assume that the decision dn , as well as the output of the update filter, depend only on the values associated with a 3×3 window surrounding the sample n (see Fig. 2). For simplicity, we will henceforth suppress the argument n in our notation and write, e.g. , x, yj rather than x(n), yj (n). III. M AIN RESULTS The following result of this section (see [10] for the proof) provides necessary and sufficient conditions for Perfect Reconstruction to hold. Proposition 1: Let V be a vector space and v the gradient vector. Consider at analysis a decision map defined by d : V → {0, . . . , N − 1}, v 7→ d(v) , and the decision regions ∀i ∈ {0, . . . , N − 1},

Di = {v ∈ V | d(v) = i}

We now present a way of constructing the decision map by comparing different seminorms, each of them capturing different orientation features. Let us consider N seminorms, denoted by p0 , p1 , . . . , pN −1 , and a decision map which can take N values, d(v) ∈ {0, . . . , N − 1}. The same is true for the decision values at synthesis, d(v ′ ). The decision criterion will be based on the comparison, at each sample, between the values of the seminorms. To illustrate the above result, consider N = 3. A possible construction of the decision map, and hence of the decision regions, is described on the left part of the relations below. On the right, the necessary and sufficient conditions for PR in Proposition 1 are specified:   p0 (v) < p2 (v) p0 (A0 v) < p2 (A0 v) d=0⇔ ⇒ p0 (v) ≤ p1 (v) p0 (A0 v) ≤ p1 (A0 v)   p1 (v) < p2 (v) p1 (A1 v) < p2 (A1 v) d=1⇔ ⇒ p1 (v) < p0 (v) p1 (A1 v) < p0 (A1 v)   p2 (v) ≤ p0 (v) p2 (A2 v) ≤ p0 (A2 v) d=2⇔ ⇒ p2 (v) ≤ p1 (v) p2 (A2 v) ≤ p1 (A2 v) . IV. A

CASE OF STUDY

Here, we consider weighted gradient seminorms [11], i.e., J T X p(v) = a v = aj vj , (2) j=1

where a = (a1 , . . . , aJ )T are some weights with

J X

aj 6= 0.

j=1

Consider the seminorms p0 (v) = |aT0 v|, p1 (v) = |aT1 v| and p2 (v) = |aT2 v|. Assume that a0 , a1 , a2 are not pairwise

collinear and such that uT a0 = uT a1 = uT a2 = ξ 6= 0. Then a sufficient condition for PR (see [10] for the proof) is: bi =

βi ai , ξ

with

0 ≤ βi < 1 ,

i = 0, 1, 2 .

For example, if we take the vectors: a0 = (1, 0, 1, 0)T , a1 = (0, 1, 0, 1)T , a2 =

1 (1, 1, 1, 1)T , 2

then bi = β2i ai , with 0 ≤ βi < 1, for i = 0, 1, 2. For images (see indexing in Fig. 2) this criterion amounts to comparing gradients in horizontal and vertical directions with a gradient taking into account isotropic information from the closest four neighbors. We can also combine the comparison of seminorms with a Threshold Criterion (TC) [7] for each one of them. Assuming a binary decision d ∈ {0, 1}, we say that the Threshold Criterion holds if given a threshold T > 0, there exists a (possibly different) threshold T ′ > 0 such that: (i) if p(v) ≤ T then p(A0 v) ≤ T ′ ; (ii) if p(v) > T then p(A1 v) > T ′ . It is obvious that the Threshold Criterion guarantees PR. In the following, we give two examples of such combination. In both cases, after the update step, we compute the detail images with a symmetric prediction scheme:
ys′ 1 (n) = ys1 (n) − x′ (n + 1, m) + x′ (n) /2
ys′ 2 (n) = ys2 (n) − x′ (n, m + 1) + x′ (n) /2
ys′ 3 (n) = ys3 (n) − x′ (n + 1, m + 1) + x′ (n) /2 − ys′ 1 (n) − ys′ 2 (n) . Example 1 We can combine the comparison of two seminorms with a TC applied to two other seminorms. Each seminorm pi is associated with its corresponding vector ai . We end up with four decision regions, described by the following conditions: p0 (v) ≤ p1 (v) and p2 (v) ≤ T0 p0 (v) ≤ p1 (v) and p2 (v) > T0 p0 (v) > p1 (v) and p3 (v) ≤ T1

⇔ ⇔ ⇔

d=0 d=1 d=2

p0 (v) > p1 (v) and p3 (v) > T1

⇔

d = 3,

where p0 (v) = |v1 + v3 |, p1 (v) = |v2 + v4 |, p2 (v) = |v1 + 12 v2 + v3 + 12 v4 | and p3 (v) = | 21 v1 + v2 + 12 v3 + v4 |. We set T0 = T1 and choose b0 = 14 a2 , b2 = 41 a3 , corresponding, respectively, to a horizontal and a verticalpredominant filtering, and b1 = b3 = 0, which implies that no update filtering is performed. As an illustration, we apply this scheme to the synthetic image ‘Rect’. The multiresolution decomposition (for 2 levels) is shown in Fig. 3(a). We compare this scheme with the 5/3 integer wavelet transform used in lossless JPEG2000. Its corresponding decomposition is shown in Fig. 3(b). One can observe that the adaptive scheme avoids blurring the edges in the approximation as well as obtaining detail images with less detail information to code.

Example 2 Here, we compare the seminorms pi (v) = |aTi v|, i = 0, 1, 2 with vectors a0 = (1, 0, 1, 0)T , a1 = (0, 1, 0, 1)T , corresponding to the horizontal and vertical directions respectively, and with a2 = (1, 1, 1, 1)T , corresponding to an isotropic (in the vertical and horizontal sense) direction. We combine the comparison of the seminorms with the TC for each one of them. We choose the filter coefficients such that if either of the seminorms pi is above a given threshold, we do not update. In particular, for the 6 decision regions, we use the filters bj = 41 aj for j = 0, 1 (vertical and horizontal), b2 = 18 a2 (isotropic) and bj = 0 (no update) for j = 3, 4, 5. The decision criterion amounts to updating the image in the direction with the lowest gradient except if a discontinuity is detected (i.e., min{p0 (v), p1 (v), p2 (v)} > T ) in which case no update filtering is performed. Table I shows the entropy values for 4 levels of decomposition for different input images1 and various decomposition schemes. The ‘uniform’ scheme corresponds to the isotropic filtering by b2 in Example 2. The entropy of the original images is shown in the second row of the table. We observe that, in terms of the proposed entropy measure and for the chosen set of images, the adaptive decompositions work better than the non-adaptive (‘uniform’ and 5/3) ones. We further evaluate the wavelet schemes by attaching a lossless coder to compute the actual bitrate. We use the embedded image coding algorithm EZBC proposed in [8]. Table II gives the average bitrate needed to obtain lossless coding. Again, the adaptive schemes outperform the nonadaptive ones. An interesting observation is that, although Examples 1 and 2 have the same entropy for the synthetic images, the actual bitrate is smaller for Example 2. On the other hand, Example 1 has the lowest entropy and bitrate for the natural images. Moreover, as can be seen from the tables, numbers computed from entropies provide a good indication of the actual performance of the wavelet scheme. TABLE I E NTROPY VALUES USING 4 LEVELS OF DECOMPOSITION .

original uniform Example 1 Example 2 5/3 integer

Rect 2.016 1.303 0.374 0.374 1.737

Crosses 0.187 1.068 0.279 0.279 1.137

House 6.232 4.139 3.134 3.410 4.562

Peppers 7.402 3.730 2.822 3.079 3.954

V. C ONCLUSIONS We have presented an adaptive lifting scheme without side information, combining different seminorm-based criteria in order to provide content-aware multiresolution representations 1 The synthetic image ‘Crosses’ can be found at http://links.uwaterloo.ca/bragzone.base.html. For the synthetic images, where the edges are sharp, we use shorter prediction filters.

(a) Fig. 3.

(b)

Multiresolution decomposition with the adaptive scheme (a) and with the 5/3 integer wavelet transform (b)

TABLE II L OSSLESS CODING RATES FOR 4 LEVELS OF DECOMPOSITION .

uniform Example 1 Example 2 5/3 integer

Rect 1.411 0.613 0.596 1.716

Crosses 1.014 0.323 0.265 1.077

House 3.252 3.015 3.299 4.191

Peppers 3.016 2.731 3.001 3.751

of images. We have proven the interest of these decompositions for image approximation and lossless compression. Future work aims at extending this framework for lossy image and video compression. ACKNOWLEDGMENT The work of Gemma Piella is supported by a MarieCurie Intra-European Fellowships within the 6th European Community Framework Programme.

R EFERENCES [1] E. J. Cand`es. The curvelet transform for image denoising. In Proceedings of the IEEE International Conference on Image Processing, Thessaloniki, Greece, October 7-10 2001. [2] R. L. Claypoole, G. M. Davis, W. Sweldens, and R. G. Baraniuk. Nonlinear wavelet transforms for image coding via lifting. IEEE Transactions on Image Processing, 12(12):1449–1459, December 2003. [3] A. Cohen and B. Matei. Compact representation of images by edge adapted multiscale transforms. In Proceeding of the IEEE International Conference on Image Processing, Thessaloniki, Greece, October 7-10 2001. [4] M. N. Do and M. Vetterli. The contourlet transform. Submitted to IEEE Transactions on Image Processing, 2004. ¨ Gerek and A. E. C [5] O. ¸ etin. Adaptive polyphase subband decomposition structures for image compression. IEEE Transactions on Image Processing, 9(10):1649–1659, October 2000. [6] H. J. A. M. Heijmans and J. Goutsias. Nonlinear multiresolution signal decomposition schemes. Part II: Morphological wavelets. IEEE Transactions on Image Processing, 9(11):1897–1913, 2000. [7] H. J. A. M. Heijmans, B. Pesquet-Popescu and G. Piella. Building nonredundant adaptive wavelets by update lifting. To appear in Applied and Computational Harmonic Analysis. [8] S. Hsiang and J. Woods. Embedded image coding using zeroblocks of subband/wavelet coefficients and context modeling. In Proceedings of the IEEE International Symposium on Circuits and Systems (Geneva, Switzerland, May 28-31, 2000), pp. 662–664. [9] E. Le Pennec and S. G. Mallat. Sparse geometric image representation with bandelets. Submitted to IEEE Transactions on Image Processing, 2004. [10] G. Piella, B. Pesquet-Popescu, H. J. A. M. Heijmans and G. Pau. Combining seminorms in an Adaptive Lifting Scheme. Applications to Image Analysis and Compression. Submitted to Journal of Mathematical Imaging and Vision, 2005. [11] G. Piella, B. Pesquet-Popescu, H. J. A. M. Heijmans. Adaptive update lifting with a decision rule based on derivative filters. IEEE Signal Processing Letters 9, 10 (October 2002), 329–332.