17 2 Realization on the Direct Two-dimensional Wavelet Transform 1060341 2006 3 10
2 JPEG JPEG2000 [1] X-Y X 1 Y 1 VGA 1 1MBte LSI LSI 2 2 5/3 [2][3] 2 5/3 9/7 7 7 N X M Y 32N M 10N M X-Y 9/7 4 1.67 1 9/7 3 2 2 2 3 3 i
2 9/7 12N M 5.5N M 2 9/7 37.5% 55% X-Y 9/7 50% 8% VGA 1 1MBte LSI 16bit SN SN 67 [db] 2 ii
Abstract Realization on the Direct Two-dimensional Wavelet Transform Akihiro CHIBA Recentl, various standards are proposed to improve compression efficienc of an image. In JPEG2000, which is the net generation standard of still picture compression, Discrete Wavelet Transform (DWT) is used for the transformation[1]. Transformation efficienc of DWT depend on image size, where the larger the size is, the higher the efficienc is. Consider a processing of X-Y separable DWT. First, it is one dimension transformed in X direction. Then, the transformed result is recorded to temporal memor. Second, Y direction DWT processing starts using the recorded results. Therefore, the temporal memor size becomes nearl 1M Bte in VGA size picture processing. If a X-Y separable DWT is implemented in a LSI chip, this large memor causes large LSI chip size. On the other hand, multi-core LSI can increase operating performance as well as loweritspowerdissipationinrecentlsis. Therefore, even if a number of DWT operations increases, a method of ecluding large capacit memor should be chosen. The reported Direct Two-dimensional 5/3 Wavelet Transform without memor (2D 5/3 wavelet)[2] is derived, based on this strateg[3]. However, 9/7 wavelet transform processing without memor on the structure of the reported 2D 5/3 wavelet leads to a huge number of operations. The reason is that 9/7 wavelet transform use 7 order filters instead of 3 order filters. When a picture has N piels in X direction and M piels in Y direction, a number of required additions iii
becomes 32N M, and that of multiplications becomes 10N M. Thisis4times additions and 1.6 times more multiplications, compared to those for X-Y separable 9/7 DWT. This thesis proposes a new Direct Two-dimensional Wavelet Transform. The new methodisbasedonemploing3orderfilters for the one dimensional 9/7 lifting structure. This strateg means that a higher order filter should be constructed b the combination of lower order filters. A high order filter is realized b a tandem connection of 3 order filters. This strateg leads a general method to construct Direct Two-dimensional Wavelet Transform without memor. For instance, this strateg can generate higher order filter than 9 order filter which is used to 9/7 wavelet transform. This strateg decreases a required number of operations for 2D 9/7 wavelet transform without memor. As a result, a number of additions becomes 12N M and that of multiplications becomes 5.5N M. This result shows that a total number of additions becomes 37.5% and that of multiplications becomes 55%, compare to reported 9/7 transform on the 5/3 transform structure. When these operations are compared to those for X-Y separated DWT, a number of additions increases 50% but that of multiplications decreases about 8%. Although the proposed method increases number of additions, the method enables ecluding temporal memor. As a result, required LSI size will be decreased. In addition, this method is simulated for LSI sstem implementation. This simulation verif that 16 bit operations generate a lot of noise b rounding errors. The obtained signal to noise ratio (S/N) becomes 67 [db]. ke words Direct 2-D wavelet transform Lifting structure iv
1 1 2 4 2.1............................. 4 2.2.............................. 8 2.3 1 9/7.................... 12 3 2 16 3.1 2 5/3............. 16 3.2 2 5/3 2 9/7...................................... 19 4 2 9/7 21 4.1 2 9/7................. 21 4.2.......................... 24 5 26 5.1..................... 26 5.2 SN........................... 27 6 30 31 32 A 33 v
2.1 JPEG2000.............. 5 2.2 JPEG2000.............. 6 2.3 ( 2 ).................... 7 2.4 ( 2 ).................... 7 2.5 JPEG2000...... 9 2.6 1 5/3 (z )................ 9 2.7 1 5/3 (z )................ 11 2.8 1 9/7 ( ).................... 13 2.9 1 5/3 ( ).................... 14 3.1 2 5/3 HH............. 17 3.2 2 5/3................. 19 3.3 5/3 (HL).................... 20 3.4 9/7 (HL).................... 20 4.1 2 9/7 (1 )............ 23 4.2 2 9/7 ( )............. 24 A.1 1:Aerial............................... 33 A.2 2:Airplane.............................. 33 A.3 3:Girl................................ 34 A.4 4:Mandrill.............................. 34 A.5 5:Pepper............................... 34 vi
2.1 JPEG2000 5/3.......... 11 2.2 JPEG2000 9/7.......... 15 5.1 2 9/7 (HPF ).............. 27 5.2 SN.......................... 28 vii
1 JPEG JPEG2000 [1] LSI X-Y 1 X Y 2 X-Y 1 2 LSI 1 2 1 2 1
2 2 JPEG2000 5/3 2 2 5/3 [2] 9/7 2 9/7 [3] 9/7 2 5/3 2 9/7 1 9/7 1 7 7 2 5/3 2 9/7 X-Y 9/7 N X M Y 32N M 4 10N M 1.67 5/3 2 9/7 1 9/7 2 2 [2] 5/3 1 9/7 2 3 3 2 9/7 2 5/3 2 9/7 37.5% 55% X-Y 9/7 2
150% 92% 2 3 2 5/3 2 5/3 2 9/7 4 1 9/7 2 9/7 5 4 2 9/7 6 3
2 2.1 [4] 2 0 JPEG MPEG DC [1] JPEG2000 JPEG2000 2.1 4
2.1 2.1 JPEG2000 2.1 H 0 (z) HPF H 1 (z) LPF X(z) ( R0 (z) =H 0 (z)x(z) R 1 (z) =H 1 (z)x(z) (2.1) R 0 (z) R 1 (z) 1/2 S 0 (z) S 1 (z) ( S0 (z) ={H 0 (z 1/2 )X(z 1/2 )+H 0 ( z 1/2 )X( z 1/2 )}/2 S 1 (z) ={H 1 (z 1/2 )X(z 1/2 )+H 1 ( z 1/2 )X( z 1/2 )}/2 (2.2) 2.2 S 0 (z) S 1 (z) 5
2.1 2.2 JPEG2000 T 0 (z) T 1 (z) ( T0 (z) ={H 0 (z)x(z)+h 0 ( z)x( z)}/2 T 1 (z) ={H 1 (z)x(z)+h 1 ( z)x( z)}/2 (2.3) T 0 (z) T 1 (z) G 0 (z) G 1 (z) Y (z) Y (z) =T 0 (z)g 0 (z) T 1 (z)g 1 (z) =[{H 0 (z)g 0 (z) H 1 (z)g 1 (z)}x(z) +{H 0 ( z)g 0 (z) H 1 ( z)g 1 (z)}x( z)]/2 (2.4) (2.2) (2.3) (2.4) X( z) (2.5) ( G0 (z) =H 1 ( z) G 1 (z) =H 0 ( z) (2.5) 6
2.1 2.3 ( 2 ) 2.4 ( 2 ) JPEG2000 R 1 (z) JPEG2000 0 1 1 7
2.2 DCT 2.3 2.1 2.2 2.4 2.3 2.2 [5] 2 2.5(a) 2.5(b) 2.5 (a) (b) (a) (b) 1 2.5 1 5/3 (a) 2 (b) 2 1 9/7 1 9/7 2.1 8
2.2 2.5 JPEG2000 2.6 1 5/3 (z ) 2.2 2.5 (a) z 2.5 (a) z 2.6 2.6 X(z) A(z) B(z) X(z) 1/2 H(z) L(z) 9
2.2 2.6 A(z) B(z) A(z) = 1 2 {X(z 1 2 )+X( z 1 2 )} (2.6) B(z) = 1 2 {z 1 2 X(z 1 2 ) z 1 2 X( z 1 2 )} (2.7) 2.6 α β H(z) =α(1 + z 1 ) (2.8) L(z) =β(1 + z 1 ) (2.9) 1 5/3 1 5/3 H(z)X(z) H(z)X(z) =B(z)+α(1 + z 1 )A(z) (2.10) A(z) B(z) (2.6) (2.7) (2.10) H(z)X(z) = 1 2 {(α + z 1 2 + αz 1 )X(z 1 2 ) +(α z 1 2 + αz 1 )X( z 1 2 )} (2.11) (2.11) (α + z 1 + αz 2 )X(z) 1/2 (2.11) β H(z) =α + z 1 2 + αz 1 (2.12) L(z) =βh(z)+z 1 + βz 1 H(z) (2.13) L(z) L(z) =β{(α + z 1 2 + αz 1 )+z 1 (α + z 1 2 + αz 1 )} + z 1 = αβ + βz 1 2 +(2αβ +1)z 1 + βz 3 2 + αβz 2 (2.14) 10
2.2 2.7 1 5/3 (z ) 2.1 JPEG2000 5/3 α β 1 2 1 4 2.1 α β JPEG2000 1 5/3 1 5/3 2.5 (b) 2.5 (b) z 2.7 2.6 HX(z) 2.5 (a) LX(z) H r (z) L r (z) Y (z) 2.5 (b) HX(z) LX(z) 2 2.5 (b) 11
2.3 1 9/7 (a) L r (z) = β + z 1 βz 1 (2.15) H r (z) = αl r (z)+z 3 2 αz 1 L r (z) (2.16) (2.12) (2.16) X(z) Y (z) 1 5/3 (2.13) (2.15) 2 JPEG2000 5/3 2.5 (a) (b) 3 2.5 (a) (b) 1 1 5/3 2.1 2.2 3 5 2.3 1 9/7 1 5/3 1 5/3 JPEG2000 9/7 1 9/7 1 5/3 2 2.8 9/7 2.9 5/3 2 2.8 (a1) (a2) 2.9 (a) (a) (2.12) (2.13) (a1) 1 9/7 1 12
2.3 1 9/7 2.8 1 9/7 ( ) (a2) (a1) 7 9 (a1) (a1) H 1 (z) α L 1 (z) β (a2) H 2 (z) γ L 2 (z) δ H 1 (z) =α + z 1 2 + αz 1 (2.17) L 1 (z) =βh 1 (z)+z 1 + βz 1 H 1 (z) (2.18) H 2 (z) =γz 1 L 1 (z)+z 3 2 H1 (z)+γz 2 L 1 (z) (2.19) L 2 (z) =δz 1 H 2 (z)+z 2 L 1 (z)+δz 2 H 2 (z) (2.20) (2.17) (2.19) (2.18) (2.20) z 1 2.8 (a1) (a2) 13
2.3 1 9/7 2.9 1 5/3 ( ) 1 9/7 1 5/3 L 1r (z) = δ + z 1 δz 1 (2.21) H 1r (z) = γl 1r (z)+z 3 2 γz 1 L 1r (z) (2.22) L 2r (z) = βz 1 H 1r (z)+z 2 L 1r (z) βz 2 H 1r (z) (2.23) H 2r (z) = αz 1 L 2r + z 5 2 H1r (z) αz 2 L 2r (z) (2.24) JPEG2000 9/7 k k k k k (2.17) (2.24) JPEG2000 9/7 k 1 9/7 14
2.3 1 9/7 2.2 JPEG2000 9/7 α 1.586034342059924 β 0.052980118572961 γ 0.882911075530934 δ 0.443506852043971 k 1.230174104914001 1 9/7 (2.17) (2.18) 9/7 JPEG2000 5/3 9/7 15
3 2 3.1 2 5/3 1 2 X Y X Y X Y X Y 4 2.2 2 X Y X Y X Y X Y X-Y z X z Y F (z,z ) 2 F (z) 1 F (z,z )=F(z )F (z ) X Y 1 2 X Y 2 HH(z,z ) 16
3.1 2 5/3 3.1 2 5/3 HH HH(z,z )=H(z )H(z ) =(α + z 1 2 =(α 2 + αz 1 2 + αz 1 )(α + z 1 2 + α 2 z 1 ) +(αz 1 2 + z 1 2 z 1 2 +(α 2 z 1 + 1 αz 1 z 2 + αz 1 2 + αz 1 ) z 1 ) + α 2 z 1 z 1 ) (3.1) X Y α X Y α 2 3.1 3 3 X Y 2 HL(z,z ) HL(z,z )=H(z )L(z ) =(α + z 1 2 =(α + z 1 2 + αz 1 ){αβ + βz 1 2 + αz 1 )[β{(α + z 1 2 +(2αβ +1)z 1 + βz 3 2 + αz 1 )+z 1 (α + z 1 2 + αβz 2 } + αz 1 )} + z 1 ] = βhh(z,z )+βz 1 HH(z,z )+z 1 H(z ) (3.2) (3.2) (3.1) Y HH(z,z ) β X 17
3.1 2 5/3 X Y 2 LH(z,z ) (3.2) X Y LH(z,z )=βhh(z,z )+βz 1 HH(z,z )+z 1 H(z ) (3.3) (3.3) (3.2) (3.1) X HH(z,z ) β Y X Y 2 LL(z,z ) LL(z,z )=L(z )L(z ) = {αβ + βz 1 2 {αβ + βz 1 2 =[β{(α + z 1 2 [β{(α + z 1 2 = β 2 {HH(z,z )+z 1 +β{z 1 +(2αβ +1)z 1 + βz 3 2 +(2αβ +1)z 1 + βz 3 2 + αz 1 )+z 1 (α + z 1 2 H(z )+z 1 + αz 1 )+z 1 (α + 1 z 2 HH(z,z )+z 1 H(z )+z 1 z 1 + αβz 2 } + αβz 2 } + αz 1 )} + z 1 ] + αz 1 )} + z 1 ] HH(z,z )+z 1 z 1 HH(z,z )} H(z )+z 1 z 1 H(z )} + z 1 z 1 (3.4) (3.4) (3.1) (3.2) (3.3) β 2 β HL(z,z ) z 1 LH(z,z ) z 1 (3.4) LL(z,z )=β{hl(z,z )+z 1 HL(z,z )+LH(z,z )+z 1 LH(z,z )} β 2 {HH(z,z )+z 1 +z 1 z 1 HH(z,z )+z 1 HH(z,z )+z 1 z 1 HH(z,z )} (3.5) (3.1) (3.2) (3.3) (3.5) z 1 z 1 2 18
3.2 2 5/3 2 9/7 3.2 2 5/3 z 1 z 1 2 3.2 4 α 2.2 2.1 β 2.1 1 5/3 [2] 1 5/3 2 5/3 3.2 2 5/3 2 9/7 2 5/3 3 7 2 9/7 [3] 2 5/3 19
3.2 2 5/3 2 9/7 3.3 5/3 (HL) 3.4 9/7 (HL) 3.2 HL 3.3 3.4 3.3 3.4 2 2 5/3 2 9/7 1 N X M Y 10N M 32N M 1 9/7 6N M 8N M 4 1.67 20
4 2 9/7 4.1 2 9/7 2 2.3 1 9/7 1 5/3 2 9/7 1 5/3 2 5/3 1 9/7 2 9/7 3.1 X-Y z X z Y F (z,z ) 2 F (z) 1 F (z,z )=F(z )F (z ) X Y 1 2 3.1 1 2 (3.4) 3.1 (3.4) (3.2) (3.3) 1 9/7 2 9/7 3.1 3.2 2 2.3 2.8 21
4.1 2 9/7 (a1) 2 3.1 (3.1) (3.4) (3.1) (3.1) (4.1) HH(z,z )=(α 2 + αz 1 2 + α 2 z 1 ) +(αz 1 2 + z 1 2 z 1 2 +(α 2 z 1 + 1 αz 1 z 2 + αz 1 2 z 1 ) + α 2 z 1 z 1 ) (4.1) (3.2) (3.3) (3.4) (3.2) (3.3) (3.2) HL 1 (z,z ) (3.3) LH 1 (z,z ) HL 1 (z,z )=z 1 H(z ) (4.2) LH 1 (z,z )=z 1 H(z ) (4.3) 3.1 (3.4) (4.1) (4.2) (4.3) β (4.1) (4.2) (4.3) (3.4) (3.4) (4.4) LL(z,z )=β 2 {HH(z,z )+z 1 +β{z 1 H(z )+z 1 HH(z,z )+z 1 H(z )+z 1 z 1 HH(z,z )+z 1 z 1 HH(z,z )} H(z )+z 1 z 1 H(z )} + z 1 z 1 (4.4) (4.1) (4.4) 2 2.3 2.8 (a1) X Y X Y 22
4.1 2 9/7 4.1 2 9/7 (1 ) 3.1 (3.2) (3.3) X Y X Y (3.2) (4.2) (3.3) (4.3) (4.2) HL 2 (z) (4.3) LH 2 (z) HL 2 (z) =HL 1 (z)+β{hh(z,z )+z 1 HH(z,z )} (4.5) LH 2 (z) =LH 1 (z)+β{hh(z,z )+z 1 HH(z,z )} (4.6) (4.1) (4.6) z 1 z 1 2 z 1 z 1 2 4 4.1 2 2.2 (2.17) (2.20) (2.19) (2.20) (2.17) (2.18) 1 (2.17) (2.18) (2.19) (2.20) (2.17) (2.18) (2.19) (2.20) (4.4) (4.6) 1 9/7 1 23
4.2 4.2 2 9/7 ( ) 2 X Y k 2 1/k 2 k 1/k 1 2 9/7 4.2 4.2 2 9/7 3.2 2 5/3 α β 4.2 1 2 4.2 3.2 3.2 HH HL LH HL LH LL 2 4.2 HH HL 1 LH 1 24
4.2 LL HL 2 LH 2 1 CPU 4.2 1 2 9/7 2 9/7 2 9/7 JPEG2000 part2 25
5 5.1 2 9/7 4.1 4.2 1 4.1 4.1 4.1 N X M Y HH 2 5.1 2 9/7 4.2 4 12N M 5N M 2 9/7 4.2 1 9/7 X Y 2 X Y X Y X Y 2 1 2 9/7 2 2 0.5N M 26
5.2 SN 5.1 2 9/7 (HPF ) HH (1 + 1/2+1/2)N M (1/4+1/4+1/4)N M HL 1 1/2N M 1/4N M LH 1 1/2N M 1/4N M 3N M 5/4N M 2 9/7 12N M 5.5N M 1 9/7 2 ( 8N M 6N M) 1.5 8% 2 9/7 LSI 2 5.2 SN 2 9/7 JPEG2000 part1 LSI LSI bit 16bit 64bit SN 5.2 A 27
5.2 SN 5.2 SN SN (1) [db] SN (2) [db] Aerial 66.5723 74.4050 Airplane 67.4732 74.4050 Girl 67.2905 74.6963 Mandrill 67.6271 72.1978 Pepper 67.3687 73.3895 256piel 256piel 1 1 16bit X-Y 9/7 64bit 8bit 64bit 128 64bit 64bit S 0 X-Y 9/7 S 16bit S 00 S S 0 N S S 00 N 0 SN (1) 10log 10 (S 2 /N 2 ) 28
5.2 SN SN (2) 10log 10 (S 2 /N 02 ) 5 SN 67 [db] 64bit 11bit SN (2) X-Y 16bit 7[dB] 2 16bit 1 29
6 LSI 2 [2] 2 5/3 2 9/7 1 N X M Y 32N M 10N M X-Y 9/7 4 1.67 1 9/7 2 9/7 12N M 5.5N M X-Y 9/7 50% 8% 1 2 LSI 16bit 64bit 1 2 S N 67 [db] SN ALU SN 2 30
4 31
[1] JPEG2000 2003 [2] 20 11 2005 [3] Akihiro CHIBA Hiroshi SUZUKI and Takao NISHITANI Consideration on the Direct Two-dimensional Wavelet Transform (SJ- CIEE) 9 2005 [4] 1999 [5] Ingrid DAUBECHIES and Wim SWELDENS FACTORING WAVELET TRANSFORMS INTO LIFTING STEPS Journal of Fourier Analsis vol.4 Nr.3 pp.247 269, 1998. 32
A A.1 1:Aerial A.2 2:Airplane 33
A.3 3:Girl A.4 4:Mandrill A.5 5:Pepper 34