Open access

Condition on Word Length of Signals and Coefficients for DC Lossless Property of DWT

Written By

Masahiro Iwahashi and Hitoshi Kiya

Submitted: 11 November 2010 Published: 29 August 2011

DOI: 10.5772/21104

From the Edited Volume

Discrete Wavelet Transforms - Algorithms and Applications

Edited by Hannu Olkkonen

Chapter metrics overview

2,003 Chapter Downloads

View Full Metrics

1. Introduction

A discrete wavelet transform (DWT) has been widely applied to various digital signal processing techniques. It has been designed under a certain condition such as perfect reconstruction, aliasing cancellation, regularity, vanishing moment, etc. This article introduces a new condition referred to “DC lossless”. It guarantees lossless reconstruction of a constant input signal (DC signal) instead of rounding of signal values and coefficient values inside a transform. The minimum word length of the values under the new condition is theoretically derived and experimentally verified.

Since JPEG 2000 algorithm based on the discrete wavelet transform (DWT) was adopted as an international standard for digital cinema video coding [1], high speed and low power implementation of a DWT has been becoming an issue of great importance [2,3]. In designing a DWT, its coefficient values and signal values are assumed to be real numbers. However, in implementation, they are rounded to rational numbers so that they are expressed with finite word length representation in binary digit. Therefore it is inevitable to have rounding errors inside a DWT processing unit.

In this article, we derive a condition on word length of coefficient values and that of signal values of a DWT such that the transform becomes lossless for a DC signal. Under this condition (DC lossless condition), it is theoretically guaranteed that an output signal contains no error in spite of rounding of coefficients and signals inside the DWT. We treat the irreversible 9-7 DWT adopted by the JPEG 2000 for lossy coding of image signals as an example.

In case of the 5-3 DWT in JPEG 2000 for lossless coding, benefiting from its lifting structure [4-6], lossless reconstruction of any signal is guaranteed even though signals and coefficients are rounded. On the contrary, it does not hold for the 9-7 DWT because of scaling for adjusting DC gain of a low pass filter in a forward transform [7]. However, we have pointed out that it became possible to be lossless for a DC signal under a certain condition on word length of coefficients and signals [8].

This DC lossless condition is a necessary condition for the regularity which has been analyzed by numerous researchers to improve coding performance of a transform. When the regularity is not satisfied, the DWT has some problems such as a checker board artifact which is observed in a reconstructed signal as unnecessary high frequency noise in flat or smooth region of a signal [9]. It also brings about DC leakage which decreases the coding gain of a transform [10].

The regularity has been structurally guaranteed for a two channel quadrature mirror filter bank (QMF) [9] and the DCT [10] respectively. However, since these previous methods were based on the lattice structure, these are not directly applicable to the lifting structure of the 9-7 DWT. Beside these relations to the regularity, the DC lossless condition itself is also considered to be important for white balancing of a video system in which the DC signal is used as a reference input for calibration [11].

This article aims at deriving the DC lossless condition theoretically and clarifying the minimum word length of signals and coefficients. In conventional analysis, errors due to shortening of word length of signals (signal errors) were described as 'additive' to a signal [7,12]. They were treated as independent and uniformly distributed white noise. On the other hand, errors due to rounding of coefficients (coefficient errors) were described as 'multiplicative' to a signal and evaluated with the sensitivity [13-15]. It should be noted that the signal error and the coefficient error have been treated independently. Unlike those conventional approaches, we utilize mutual effect between rounding of signals and that of coefficients. Introducing a new model which unifies the coefficient error and the signal error, we define tolerance for those errors as a parameter to simultaneously control both of word length of signals and that of coefficients.

As a result of our theoretical analysis, the minimum word length of signals and that of coefficients inside the lifting 9-7 DWT are derived under the DC lossless condition. We confirm that the minimum word length derived by our analysis is shorter than that determined by a conventional approach. We also confirm that the DWT under the condition does not have the checker board for a DC signal.

This article is organized as follows. Chapter 2 defines a rounding operation and a rounding error, describes their basic properties in algebraic approach, and derives 'addition' formula and 'multiplication' formula of the rounding (modulo) operation. Application of these formulas to scaling of a signal value is introduced in chapter 3. Chapter 4 introduces the DC lossless DWT. Its usefulness is also described. Derivation process of conditions on word length of signals and coefficients is described in chapter 5. The new condition derived from the basic properties in chapter 2 is summarized in chapter 6. Other related condition derived from a conventional approach is also summarized. Theoretical results are verified and the minimum word length of the DC lossless DWT is clarified in chapter 7. This article is concluded in chapter 8.

Advertisement

2. Rounding operation and its basic formulas

This chapter introduces basic properties of the rounding operation focusing on 'quotient', rather than 'remainder', in modulo operation. So far, 'remainder' had been attracted numerous mathematicians' attention and various basic properties were found such as the Chinese remainder theorem in the commutative algebra (commutative ring theory). On the contrary, 'quotient' plays an important role as a 'practical' value in finite word length implementation in modern computer systems. This chapter introduces an algebraic approach of expressing 'quotient' as a practical value, and 'remainder' as a rounding error, so that it can be applied to analyzing exact behavior of rounding errors in a complex calculation procedure.

2.1. Definition of rounding operation and rounding error

In a digital calculation system, all the values of both of signals and coefficients are calculated and stored as a binary digit with finite word length. In this article, we treat a case such that a value x is expressed with a fixed point binary expression as

x=p=FI1bp2p,bp{0,1},I1,F0,IZ,FZE1

where bp, p{-F, ,I-1), is a set of binary digit for a value x. It has I bit integer part including one sign bit and F bit fraction part. Hereinafter, F is referred to as word length of a value x. This F bit value x has a range expressed as

x[2I1,2I12F][2I1,2I1)E2
.

For example, in case of I=1 and F=2, the maximum value is x=0.75 for [b0 b-1 b-2]=[0 1 1], and the minimum value is x=-1.00 for [b0 b-1 b-2]=[1 0 0].

When an F bit signal value is multiplied with a coefficient value, in a convolution of a filtering process in DWT for example, a resulting signal value has longer word length than its original value. Therefore it is rounded to F bit again. So far there are various types of rounding operations [16]. In this article, we deal with the rounding operation defined by

R0[x]=x+21orR0[x]=x'(x'mod1)forx'=x+21E3

as an example. This rounding operation generates a rounding error. We denote it as

Δ0[x]=xR0[x]orΔ0[x]={(x+21)mod1}21E4
.

Expanding these expressions to an F bit case, we can define the rounding operation and the rounding error as

{RF[x]=R0[x2F]2FΔF[x]=Δ0[x2F]2FE5

for an F bit word length implementation case.

Fig.1 illustrates rounding operations expressed by these equations. The term RF[x] is a quotient, and ΔF[x] (= x - RF[x]) is related to a remainder. The former is an actual value treated in a digital system under a finite word length implementation, and the latter is a rounding error. We are now trying to develop an algebraic expression approach to exactly trace a practical value and a rounding error in a convolution processing inside a DWT.

Fig. 1. Definition of the rounding operation and the rounding error. (a) An integer implementation case. (b) An F bit word length implementation case.

2.2. Basic properties of the rounding operation

Since a convolution includes additions and multiplications, we should know behavior of an addition of two values x and y. Resulting value is RF[x+y] and its rounding error is ΔF[x+y]. A multiplication result RF[xy] and its error ΔF[xy] should be also investigated.

First of all, let's derive basic properties of the rounding operation starting with an obvious property;

yZR0[x+y]=R0[x]+yforxRE6
.

It represents that only a real number x can be rounded if y is an integer to calculate a rounded value of x+y. In this case, its rounding error becomes

yZΔ0[x+y]=Δ0[x]forxRE7
.

It suggests that an integer y can be ignored when only the rounding error is considered in an analysis. There is another obvious property;

R0[x]=0x[21,21)E8
.

Since the range of a rounding error is

Δ0[x][21,21)E9
,

we can add two more identities;

{R0[Δ0[x]]=0,Δ0[Δ0[x]]=Δ0[x].E10

The equations above for F=0 can be straightforwardly extended to an F≠0 case as follows.

y2FZ{RF[x+y]=RF[x]+yΔF[x+y]=ΔF[x]forxRE11
RF[x]=0x[21F,21F)E12
ΔF[x][21F,21F)E13
{RF[ΔF[x]]=0ΔF[ΔF[x]]=ΔF[x]E14

In addition, Eq.(12) can be extended to a more general case with an integer n as

RF[x]=n2Fx2F[21+n,21+n)fornZE15
.

2.3. Basic formulas of the rounding operation

Utilizing the basic properties in Eqs.(11)-(14), we can derive an addition formula and a multiplication formula of a practical value (quotient) of the rounding operation as follows.

Addition formula

RF[x+y]=RF[x]+RF[y+ΔF[x]]forx,yRE16

Proof:

RF[x+y]=RF[RF[x]+ΔF[x]+y](4)=RF[x]+RF[ΔF[x]+y](11)

Q.E.D.

Multiplication formula

RF[xy]=RF[xRF[y]]+RF[xΔF[y]+ΔF[xRF[y]]]forx,yRE17

Proof:

RF[xy]=RF[xΔF[y]+xRF[y]](4)=RF[xΔF[y]+ΔF[xRF[y]]+RF[xRF[y]]](4)=RF[xΔF[y]+ΔF[xRF[y]]]+RF[xRF[y]](11)

Q.E.D.

Formulas for a rounding error (remainder) can be also derived as

{ΔF[x+y]=ΔF[ΔF[x]+ΔF[y]]ΔF[xy]=ΔF[ΔF[x]RF[y]+RF[x]ΔF[y]+ΔF[x]ΔF[y]]E18

for real numbers x and y. These formulas have following variations;

Addition formula

y2FZ{RF[x+y]=RF[x]+yRF[x+y]=ΔF[x]+x+yΔF[x+y]=ΔF[x]E19

Multiplication formula

y2FZ{RF[xy]=RF[ΔF[x]y]+RF[x]yRF[xy]=ΔF[ΔF[x]y]+xyΔF[xy]=ΔF[ΔF[x]y]E20

Especially when two kinds of word lengths are mixed in a signal processing, the following variation of the multiplication formula is conveniently applied to analyzing behavior of signals and errors in a pair of encoder and decoder [17].

RF2[xRF1[y]]=RF2[xy]+RF2[xΔF1[y]+ΔF2[xy]]E21

Proof:

RF2[xRF1[y]]=R0[xΔF1[y]2F2+xy2F2]2F2=R0[xΔF1[y]2F2+Δ0[xy2F2]+R0[xy2F2]]2F2=R0[xΔF1[y]2F2+Δ0[xy2F2]]2F2+R0[xy2F2]2F2=RF2[xΔF1[y]+ΔF2[xy]]+RF2[xy]

Q.E.D.

Advertisement

3. Application of the formulas to basic signal processing

This chapter applies the formulas to some basic signal processing cases.

3.1. Mapping invariant condition

Fig.2 illustrates a scaling of a signal value x with a coefficient value h. As illustrated in Fig.2(a), this processing maps an input value x to an output value y* with an ideal (infinite word length) coefficient value h. Note that x has F bit word length. Output value of the multiplication is also rounded to F bit (y* has F bit word length). In implementation, as illustrated in Fig.2(b) , a coefficient value h is also rounded to W bit word length (h' has W bit word length). We aim at finding the minimum word length W of a coefficient h' such that the mapping is invariant (y -y* =0).

Figure 1.

Scaling of a signal value x with a coefficient value h. (a) This processing maps x to y* with h under a given F. (b) A mapped y should be equal to y* even though h is rounded to h'.

In case of Fig.2(b), an input value x is multiplied by a rounded value RW[h] (=h') of a given coefficient h. The result RW[h]x is rounded to RF[RW[h]x] (=y). When it is the same as RF[hx] (=y* ), the mapping of x is invariant. It means that effect of rounding of h is nullified. This mapping invariant case is expressed as

Em=0for{Em=RF[RW[h]x]RF[hx]RW[h]=hΔW[h]E22
.

From the basic properties, the mapping invariant condition is derived as

ΔW[h]xΔF[hx](21F,21F]E23
.

Proof:

RF[RW[h]x]RF[hx]=RF[hxΔW[h]x]RF[hx]=RF[ΔF[hx]ΔW[h]x]+RF[hx]RF[hx]=RF[ΔF[hx]ΔW[h]x]=0

ΔF[hx]ΔW[h]x[21F,21F)

Q.E.D.

The Eq.(23) also means

{ΔW[h](ΔF[hx]21x,ΔF[hx]+21x],x>0ΔW[h][ΔF[hx]+21x,ΔF[hx]21x),x<0E24

which gives tolerance to the rounding error of a coefficient [8]. This is the mapping invariant condition on word length W of a coefficient under a given word length F of signals. It represents exact (not approximated) behavior of rounding errors.

Unlike the condition above, a sufficient condition can be derived by substituting the upper bound of errors and signals;

|ΔW[h]|<21W,|ΔF[hx]|<21F,|x|<2I1E25
,

to Eq.(23). It results in the condition described as

W>F+I1E26
.

This condition is too strict and requires too long word length to guarantee the mapping invariance. In both cases of Eq.(24) and Eq.(26), the mapping invariant condition determines the minimum of word length W of a coefficient under a given word length F of signals.

3.2. Lossless condition on a scaling pair

Fig.3 illustrates a pair of two multipliers. In Fig.3(a), an input signal x has F2 bit word length. It is scaled with a coefficient h1, and its output value y is rounded to F1 bit. It is re-scaled with a coefficient h2 (=1/h1), and its final output value w is rounded to F2 bit. This scheme is embedded in a forward transform and a backward transform of DWT for example. It is required to regain w exactly the same as x, under a given word length set of F1 and F2. Note that rounding errors due to finite word length expression of coefficients h1 and h2 can be ignored as far as the mapping invariant condition is satisfied.

Figure 2.

Scaling pair has two coefficients h1 and h2 (=1/h1). (a) Output w is exactly the same as its original x. (b) This lossless property is guaranteed under a condition on F1 and F2.

We apply the formulas and the properties to derive the condition on F1 and F2. The lossless case in Fig.3(b) is described as

Ep=0for{Ep=RF2[h2RF1[h1x]]xh1h2=1E27
.

From the basic properties, the lossless condition on a scaling pair is derived as

h2ΔF1[h1x](21F2,21F2]E32
.

Proof:

RF2[h2RF1[h1x]]x=R0[h2ΔF1[h1x]2F2+h2h1x2F2]2F2x=R0[h2ΔF1[h1x]2F2]2F2+xx=RF2[h2ΔF1[h1x]]=0

h2ΔF1[h1x][21F2,21F2)

Q.E.D.

This condition determines the word length F1 and F2 of signals for an input value x. It represents exact condition such that total accumulated rounding error is nullified by the rounding just after the final multiplier with h2. As a result, the original value x is recovered as the final output without any loss.

Unlike the exact condition above, a sufficient condition can be derived by analyzing the upper bound as follows.

|h2ΔF1[h1x]|<|h2|21F1<21F2E29

As a results, when the sufficient condition given by

F1>F2+log2|h2|E30

holds, the scaling pair becomes lossless. However this condition is too strict and requires too long word length of signals.

Advertisement

4. Application of the formulas to DWT

This chapter introduces the DC lossless DWT [8, 18]. Definition and its usefulness are also described. The algebraic approach based on the formulas is applied to derive conditions on word length of signals and coefficients. Derivation process is described in chapter 5.

4.1. DWT and its word length of signals and coefficients

Fig.4 illustrates the irreversible 9-7 DWT of the JPEG 2000 standard [1]. The forward transform in Fig.4(a) decomposes an input signal x(n), nN, N={n | 1,2, , L} into band signals y1(m) and y2(m), mM, M={m | 1,2, , L/2}. The backward transform in Fig.4(b) reconstructs the signal w(n) from the band signals. In the figure, z-1 and ↓2 indicate the delay and the down sampler respectively.

Figure 3.

The irreversible 9-7 DWT of the JPEG 2000 standard.

The multiplier coefficients ci, iI, I={i | 1,2, , 6} are designed under the word length long enough to be treated as real numbers. When the DWT is implemented, coefficient values are rounded to the length as short as possible to minimize total hardware complexity. Similarly, signal values are also rounded. In the figure, fraction part of each signal is shortened to FS, FB or FX [bit] by a rounding operation illustrated as a circle.

Denoting the integer part as IS [bit], total word length WS [bit] of a signal s is defined as

WS=IS+FS+1E31

including 1 [bit] for the sign part. Similarly, total word length WC [bit] of a coefficient c is defined as

WC=IC+FC+1E32
.

In Fig.4, fraction part of the input signal x(n) is given as FX [bit]. Inside the DWT, fraction part of the signals are rounded to FS [bit] just after each of all the multiplications with ci, iI. Output signals from the forward and backward transforms are rounded to FB [bit] and FX [bit] respectively. Note that we do not truncate integer part of signals and that of coefficients. We are determining FS and FC such that the DC lossless property is satisfied.

4.2. Definition of DC lossless property and its necessity

In this article, we define the DC lossless as the conjunction of the following two propositions:

nN,mM(x(n)=dy1(m)=dy2(m)=0)E33
nN,mM(y1(m)=dy2(m)=0w(n)=d)E34

for a given constant value d with FX [bit] fraction part. When the proposition in Eq.(33) holds, the DWT has no DC leakage for the DC input signal with value d. Similarly, when the proposition in Eq.(34) is true, the reconstructed signal w(n) contains no checker board artifact for the DC input signal. In the following chapters, we investigate the minimum fraction part of signals FS [bit] which guarantees the DC lossless for given FX and FB [bit]. We also investigate the minimum fraction part FCi [bit] of a coefficient ci, iI with flexibility of trading off the signal error and the coefficient error.

Fig.5(a) illustrates an example of a video system. It contains an encoder and a decoder which are composed of a forward DWT and a backward DWT. In white balancing, a camera and a display are calibrated with a constant valued input signal (DC signal) [11,19]. Therefore, it is useful for this calibration if the forward DWT and its backward do not generate any error. In this case, the camera and the display can be calibrated ignoring existence of the encoder and the decoder as illustrated in Fig.5(b). Namely, the DC lossless condition provides a low complexity DWT useful for the white balancing.

Figure 4.

The DC lossless property is useful for white balancing in a video system.

In addition, the DC lossless condition is a necessary condition for the regularity which controls smoothness of basis functions and coding performance of a transform. A DWT under the regularity does not generate the checker board artifact or the DC leakage. Harada et. al. analyzed a condition for the regularity of a two channel quadrature mirror filter bank (QMF) [9]. They confirmed that a QMF under the condition has reduced checker board artifact for an input step signal. It is expanded to a multirate system under short word length expression [20]. The regularity was structurally guaranteed for a biorthogonal linear phase filter bank [21,22] and the DCT [10] respectively. However, since these previous methods are based on factorization of a transfer function including (1+z-1) or (1-z-1) in the lattice structure, these are not directly applicable to the lifting structure of the 9-7 DWT in Fig.4.

In this article, we derive the DC lossless condition theoretically in chapter 5, and determine the minimum word length of signals and that of coefficients under the condition in following chapters.

Advertisement

5. Derivation of condition for the DC lossless DWT

This chapter describes derivation process of the DC lossless condition.

5.1. New model for error analysis

Fig.6(a) illustrates a multiplier in the DWT circuit. An input value s has FS [bit] fraction part and multiplied by a coefficient c'. The coefficient is originally designed as a real number c. It is rounded to a rational number c' in implementation. It produces the coefficient error:

Δc=cc'E35
.

Just after the multiplication, the signal is rounded to s' with FS [bit] fraction part as

s'=RFS[c's]=c's+e'E36

where e' is the signal error. From Eq.(35) and (36), the final output becomes

s'=csΔcs+e'E42
.

where cs is the ideal output. This conventional model, illustrated in Fig.6(b), describes the coefficient error Δc as multiplicative to the signal s [13-15], and the signal error e' as additive [7,12]. In addition, these errors are treated independently as mutually uncorrelated noises.

Unlike these existing approaches, as illustrated in Fig.6(c), we describe the coefficient error e'' as

{s'=RFS[cs]+e'',e''=RFS[ΔFS[cs]ΔFC[c]s].E38

From Eq.(15), we utilize the fact that e'' is observed as a 'particle';

e''2FS=pE39

where p is an integer. Given the tolerable maximum to an integer p, word length of the coefficient c can be controlled independently of other coefficients in other sections inside the DWT. Furthermore, denoting the signal error as e' similarly to Eq.(36), the output value is described as

{s'=cs+ee=e'+e''E40

where

{e'=ΔFS[cs]e''=RFS[ΔFS[cs]ΔFC[c]s]E41

as illustrated in Fig.6(d). In this new model, both of the coefficient error e'' and the signal error e' are unified to the error e. Utilizing Eqs.(13) and (15), its absolute value is limited to

|e|(p+21)2FSE42
.

Note that the parameter p to control word length of a coefficient c is included in this equation. It is equivalent to

2FC+FS+IS1pE43

where its proof is given in appendix.

Benefitting from this inequality, it becomes possible to consider mutual effect of the coefficient error and the signal error.

Figure 5.

A multiplier in the DWT and its models for error analysis.

Inside the forward DWT, the error e is propagated and added up with other errors from other multipliers. When its maximum absolute value is less than21FB, the total error is nullified by the rounding at the final output of the forward DWT. In this article, we utilize this nullification of errors at output of the DWT to derive a condition on word length such that the DC lossless defined by Eq.(33) and (34) is satisfied.

5.2. DC equivalent circuit

When the input signal is restricted to a DC signal, x(n) can be described as a scalar x independent of n. The delay z-1 can be treated as 1 and (1+z-1) can be replaced by 2. Therefore, instead of the circuits in Fig.4, we can use their equivalent circuits for a DC input signal in Fig.7 to derive the condition.

In Fig.7(a) , a scalar x with FX [bit] fraction part is multiplied by the rational numbers ci, iI and rounded to FS [bit]. Finally, the signals are rounded to FB [bit] at its output to produce two scalars [y1 y2]. The unified errors inside the circuit are described as

ei=ei'+ei'',iIE44

where

{ei'=ΔFS[cisi]ei''=RFS[ΔFS[cisi]ΔFC[ci]si]

[s1s3s5s2s4s6]=[2x2(x+s'2)s42(x+s'1)2(s2+s'3)s3+s'4]

s'i=cisi+ei=RFS[cisi]

.

Similarly, for the backward transform in Fig.7(b), errors are described as

fi=fi'+fi'',iIE45

where

{fi'=ΔFS[citi]fi''=RFS[ΔFS[citi]ΔFC[ci]ti]

[t1t3t5t2t4t6]=[2(t3t'2)2(t'5t'4)y12(t4t'3)2t'6y2]

t'i=citi+fi=RFS[citi]E52

.

Similarly to Eq.(42), these errors are described with the parameters pi and qi to control word length of coefficients as

|ei|(pi+21)2FS,iIE46
|fi|(qi+21)2FS,iIE47

for a given word length Fs [bit] of signals.

Figure 6.

Equivalent circuits of the DWT for a DC input signal.

5.3. Nullification of accumulated errors

In Fig.7(a), the unified errors in Eq.(46) are propagated and accumulated inside the circuit. When the accumulated errors are nullified by the rounding at output of the forward transform, Eq.(33) is satisfied. In the figure, Y12=[y1 y2]T is described as

Y12=RFB[IUe6+ILe5+K(IUe4+H4(ILe3+H3(IUe2+H2(ILe1+H1IULx))))]E48

where

IU=[10]T,IL=[01]T,IUL=IU+IL

Hi{1,3}=[102ci1],Hj{2,4}=[12cj01],K=[c600c5].

It is described with the unified error matrices E1 and E2 as

Y12=RFB[(He1E1+He2E2)+KH4321x]E49

where

{He1=[IUKIUKH43IU]He2=[ILKH4ILKH432IL]H43=H4H3,

and

{E1=[e6e4e2]TE2=[e5e3e1]T.

Similarly, output values W12=[w1 w2]T from the backward transform in Fig.7(b) are

W12=RFX[(He3E3+He4E4)+(KH4321)1Y12]E50

where

{He3=[H11IUH1231IUH12341IU]He4=[ILH121ILH12341IL]H121=H11H21

and

{E3=[f2f4f5]TE4=[f1f3f6]T.

When the DWT is DC lossless, output values of the transforms are

[Y^12W^12]=[KH4321x(KH4321)1X^12]=[IUIUL]x.E51

Using this equation, the accumulated errors are defined as

[Ey12Ew12]=[Y12W12][Y^12W^12].E52

Substituting Eqs.(49), (50), (51) and using the property in Eq.(6), we have

[Ey12Ew12]=[RFB[(He1E1+He2E2)]RFX[(He3E3+He4E4)]].E53

Applying Eq.(12), it becomes clear that when the conditions;

{|He1E1+He2E2|IUL21FB|He3E3+He4E4|IUL21FXE54

are satisfied, the accumulated errors are nullified by the rounding operations at the final output of each of the forward transform and the backward transform.

Advertisement

6. Derived conditions on word length for the DC lossless DWT

This chapter summarizes the new condition derived from the basic properties in chapter 2, and other related condition derived from a conventional approach.

6.1. Critical condition on word length

Finally, we derive the condition on word length of coefficients and signals such that Eq.(54) is satisfied. Since the unified errors in E1, E2, E3 and E4 have the maximum in Eqs.(46) and (47) described with the parameters pi and qi, the DC lossless condition is also described with the parameters by substituting

{E1=([p6p4p2]T+I321)2FSE2=([p5p3p1]T+I321)2FSE3=([q2q4q5]T+I321)2FSE4=([q1q3q6]T+I321)2FSE55

for

I3=[111]T

into Eq.(54). This is the condition we derived based on the new model described in section 5.1. We investigate the fraction part FCi [bit] of a coefficient ci, iI as the minimum word length under the condition for a DC value x at the word length Fs [bit] of signals.

6.2. Sufficient condition on word length

As an example, in case of all the parameter in Eq.(55) are given as pi = qi = p and FCi = FC for iI, the condition in Eq.(54) becomes

{(He1L1+He2L1)2FS(p+21)IUL21FB(He3L1+He4L1)2FS(p+21)IUL21FXE56

where HL1 denotes a column vector whose component is a sum of absolute value of all components in each row. Substituting coefficients of the 9-7 DWT [1] into Eq.(56), we have

{p21+FSGE21GE=2.66[bit]E57

for FX = FB = 0. As a result, the DC lossless condition on the word length is given as

log2(2ΔWC+2ΔWS)GEE58

where

[ΔWCΔWS]=[FCISFS]

and GE is the lower bound. This means a sufficient condition for the DC lossless. Since it is too strict, the word length under this condition is redundant. Unlike this sufficient condition, our critical condition given as Eq.(54) under Eq.(55) determines the word length minimum and necessary for the DC lossless.

Advertisement

7. Simulation results

This chapter verifies theoretically derived conditions, and clarifies the minimum word length of the DC lossless DWT.

7.1. Word length under the sufficient condition

Utilizing the sufficient condition in section 6.2, we calculated the optimized word length under the cost function defined as J=2-1(FC +FS). The cost J is minimized for three examples. Ex.1 trades the word length between FC and FS, namely FC + FS = constant. Ex.2 and Ex.3 are FC = FS and WC = WS respectively. Results are summarized in table 1. Table 2 summarizes word length of signals and coefficients for an 8 bit system with Wx=8 (Ix=7 and Fx=0). Ex.1 requires (FS, FC)=(4, 12) [bit] for signals and coefficients respectively. Ex.2 and Ex.3 require FS =FC =11 [bit] and WS =WC =14 [bit] respectively. The condition in Eq.(58) is plotted as a solid line in Fig.8. According to the sufficient condition, it is impossible to be DC lossless for

{FCGE+ISFSGEE59

and it is also confirmed by the figure. It guarantees the DC lossless, however the condition is too strict. Therefore the word length is redundant and there is room for further reduction.

Table 1.

Theoretically derived word length under the sufficient condition for DC lossless. FS and FC denote fraction part of signals and coefficients. IS and IC denote integer part of signals and coefficients. WS=IS+FS+1, WC=IC+FC+1, J is a cost function.

Table 2.

Word length calculated with equations in table 1 for Wx=8 [bit].

7.2. Word length under the critical condition

In Fig.8, a cross "×" indicates a pair (FS, FC) which satisfies the critical condition in section 6.1 for any 8 bit integer x with WX=IX=8 and FX=0. Here in after, we denote an input DC value to a video system as

xin=x2IX1E60

where x is an input value to the DC equivalent circuit in Fig.7. The minimum of FC for each FS is indicated as a broken line. It is clear that the word length derived by the critical condition is shorter than that determined by the sufficient condition. For example in Fig.8(a), the fraction part FS (= FC) is reduced from 11 [bit] to 9 [bit] for Ex.2. The word length is not shortened for Ex.1 and Ex.3. In case of Fig.8(b), FS (= FC) is reduced from 13 [bit] to 12 [bit] for Ex.2. (FS, FC) is reduced from (14, 4) to (13, 3) or (12, 4) for Ex.1. WS (= WC) is reduced from 16 [bit] to 15 [bit] for Ex.3. It is confirmed that the word length is shortened due to the analysis in this article.

Figure 8.

Word length under the two conditions. "×" indicates (FS, FC) such that the DWT becomes DC lossless.

7.3. Word length for a specific value

Fig.9(a) and Fig.9(b) illustrate the word length under the conditions for the black value "16" and the white value "235" respectively. These specific values are utilized in white balancing of an 8-bit video system [19]. For example, (FS, FC) is reduced from (4, 12) in Fig.8(a) to (2, 9) in Fig.9(a) for Ex.1. Table 3 summarizes the minimum word length for these specific input DC values [23]. It is observed that the word length can be reduced by limiting input DC signals to a specific value. Fig.10 indicates the minimum word length FC of coefficients for an input value x at a given word length FS of signals. This is an example at (FS, WX)=(3, 8). The sufficient condition gives the same word length for any of input values. Unlike this conventional statistical analysis, our analysis gives the minimum word length shorter than that determined by the sufficient condition for each of input DC values.

Figure 9.

Word length under the two conditions for a specific value used in white balancing.

Figure 10.

The minimum word length of coefficients for each of input DC values at (FS, WX)=(3, 8). According to the sufficient condition, the word length is too long.

Table 3.

The minimum word length for a specific value for white balancing of a video system.

7.4. Optimum word length assignment

Since we described tolerance for the unified errors as parameters pi and qi in Eq.(46) and (47), it becomes possible to simultaneously control both of word length of signals and that of coefficients. Table 4 summarizes these parameters for an input value 16 and the word length of signals at FS=2 [bit] as an example. It indicates that [p1 p2 p6] in Eq.(46) are [0 0 0 0 0 1] for the word length of coefficients at FC=9 [bit]. In this case, all the coefficients ci in the forward transform have the same length. It is worth paying attention to the fact that the parameter p1 is the same for FC=9, 8 and 7 [bit] for example. It means that word length of the coefficient c1 can be reduced from 9 to 7 [bit] without any influence to the errors. Therefore, word length [FC1 FC2FC6] of coefficients [c1 c2 c6] can be reduced from [9 9 9 9 9 9] to [7 9 7 4 6 4] according to the table.

Table 5 summarizes results of this optimum word length assignment for the forward transform. Comparing to table 3, it is observed that word length of coefficients is reduced from 9.00 [bit] to 6.17 [bit] on average for an input value xin=16. Table 6 summarizes results for the backward transform. In this case, the word length is furthermore shortened. It is observed that c6 and c4 can be omitted since y2 is equal to zero under the DC lossless. Fig.11 illustrates image signals reconstructed by the DWT which does not satisfy the DC lossless condition. It demonstrates the checker board artifact for reference. It is confirmed that total word length is furthermore shortened utilizing the tolerance parameters pi and qi introduced in this article.

Table 4.

Tolerance parameters in Eq.(46) and (47) for xin=16 and FS=2 as an example.

Table 5.

The minimum word length of coefficients in the forward transform for a specific values xin for a given word length of signals FS.

Table 6.

The minimum word length of coefficients in the backward transform for a specific values xin for a given word length of signals FS.

Figure 11.

Example of reconstructed images for 1282 pixel DC input image with x=10. Intensity is multiplied by 16.

Advertisement

8. Conclusions

Introducing a new model which unifies the coefficient error and the signal error, and utilizing the nullification of the accumulated errors, this article theoretically derived a condition on word length of signals and coefficients such that the 9-7 DWT of JPEG 2000 becomes lossless for a DC input signal. It was confirmed that the minimum word length derived by the newly introduced 'critical' condition was shorter than that determined by a conventionally well known 'sufficient' condition. It was also confirmed that the DWT under the condition does not have the checker board for a DC signal. Analysis in this article contributes to build a low complexity DC lossless DWT.

Advertisement

9. Appendix

Proof of Eq.(43)

Eq.(39) with Eq.(41) means

|ΔFS[cs]ΔFC[c]s|(p+21)2FSEA1

according to Eqs.(13) and (15). Applying the triangle inequality to the left hand side, we have

|ΔFS[cs]ΔFC[c]s||ΔFS[cs]|+|ΔFC[c]||s|A2
.

According to Eq.(13), each terms in the right hand side are described as

{|ΔFS[cs]|21FS|ΔFC[c]||s|21FC2ISA3

Therefore (A.2) and (A.3) under (A.1) means

21FS+21FC2IS<(p+21)2FS

and finally we have Eq.(43) as

2FC+FS+IS1p

.

Q.E.D.

References

  1. 1. ISO/IEC FCD15444-1, "JPEG2000 image coding system," March 2000.
  2. 2. Descampeet.al.2006A flexible hardware JPEG 2000 decoder for digital cinema," IEEE Trans. circuits, systems on video technology, 161113971410Nov. 2006
  3. 3. Bing-FeiWu.Chung-FuLin.2006 Memory-efficient architecture for JPEG 2000 coprocessor with large tile image, IEEE Trans. circuits and systems II, 534304308April 2006.
  4. 4. KiyaH.YaeM.IwahashiM.1992 Linear phase two channel filter bank allowing perfect reconstruction", IEEE Proc. international symposium on circuits and systems (ISCAS), 2951954May 1992.
  5. 5. SweldensW.1994 The lifting scheme: A custom-design construction of biorthogonal wavelets," Technical Report 1994:7, industrial mathematics initiative, department of mathematics, university of South Carolina, 1994.
  6. 6. BruelersM. L.van den EndenA. W. M.1992 New Networks for Perfect Inversion and Perfect Reconstruction," IEEE Journal of selected areas in communications, 101130137Jan.1992.
  7. 7. RezaM.LianZhu.2005 Analysis of error in the fixed-point implementation of two-dimensional discrete wavelet transforms," IEEE Trans. circuits and systems, fundamental theory and applications, 523641655March 2005.
  8. 8. KiyaM.IwahashiO.Watanabe2008 A new class of lifting wavelet transform for guaranteeing losslessness of specific signals," IEEE international conference, acoustics, speech, and signal processing (ICASSP), 32733276March 2008.
  9. 9. HaradaY.MuramatsuS.KiyaH.1997 Two channel QMF bank without checker board effect and its lattice structure," IEICE Trans. on fundamentals, J80-A1118571867Nov. 1997.
  10. 10. WeiDaiTranT. D.2003 Regularity-constrained pre- and post- filtering for block DCT-based systems," IEEE Trans. signal processing, 511025682581Oct. 2003.
  11. 11. HirakawaParksT. W.2005Chromatic adaptation and white balancing problem," IEEE Proc. international conference, image processing (ICIP), vol. III, 984987Nov. 2005.
  12. 12. Grangettoet.al.2002 Optimization and implementation of the integer wavelet transform for image coding," IEEE Trans. Image Processing, 116596604June 2002.
  13. 13. Xiaoet.al.1998 Coefficient sensitivity and structure optimization of multidimensional state-space digital filters," IEEE Trans. circuits, systems I, 459993998
  14. 14. YamakiS.AbeM.KawamataM.2008 A closed form solution to L2-sensitivity minimization of second-order state-space digital filters subject to L2-scaling constraints," IEICT Trans. fundamentals of electronics, communications and computer sciences, E91A716971705July 2008.
  15. 15. TonomuraY.ChokchaitamS.IwahashiM.2004 Minimum hardware implementation of multipliers of the lifting wavelet transform," IEEE Proc. international conference, image processing (ICIP), 24992502Oct. 2004.
  16. 16. IEEE Standard 754-1985, IEEE standard for binary floating-point arithmetic.
  17. 17. IwahashiM.KiyaH.2008 Finite word length error analysis based on basic formula of rounding operation", the international symposium on intelligent signal processing and communication systems (ISPACS), 864952Dec. 2008.
  18. 18. IwahashiM.KiyaH. Word length condition for DC Lossless DWT," Asia pacific signal and information processing association (APSIPA) annual summit and conference, TA-P2469472Oct. 2009.
  19. 19. The society of motion picture and television engineers,Standard for television, 1920x1080 image sample structure, digital representation and digital timing reference sequences for multiple picture rates", SMPTE 274 M-2005, Feb.2005.
  20. 20. IwaiH.IwahashiM.KiyaK.Methods.foravoiding.thecheckerboard.distortioncaused.byfinite.wordlength.errorin.multiratesystem.TransI. E. I. C. E.fundamentals, E93-A3631635March, 2010
  21. 21. OraintaraS.TranT. D.NquenT. Q. A class of regular biorthogonal linear-phase filterbanks: Theory, structure, and application in image coding," IEEE Trans. signal processing, 511232203235Dec.2003.
  22. 22. TanakaY.IkeharaM. "First order linear phase filter banks with regularity constrains for efficient image coding," IEICE Trans. fundamentals, vol. J91-A, no.2, pp.192-201, Feb. 2008.
  23. 23. IwahashiM.KiyaH. "A lossless condition of lifting DWT for specific DC values", IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp.1458-1461, March 2010.

Written By

Masahiro Iwahashi and Hitoshi Kiya

Submitted: 11 November 2010 Published: 29 August 2011